Delta Kernel Syntax Subst

Substitution in the delta kernel

In formal logic, substitution is the operation of replacing a variable with a term. The declaration subst in the Recognition Science framework's delta kernel defines this operation for its object language, a minimal arithmetic built from zero, successor, addition, and multiplication. The definition is deliberately spare: it works on plain data structures, not on the host system's propositions, and it performs no reasoning beyond structural recursion. The function takes a variable index and a replacement term, then walks through a formula and swaps in the replacement wherever that variable appears.

The substitution is binder-aware, meaning it respects the scope of quantifiers. When the function descends under a universal or existential quantifier, it shifts the replacement term and the target variable index so that a free variable inside the quantifier does not accidentally become bound. This is the standard de Bruijn-index discipline, and it is what makes substitution safe to compose. The definition is primitive recursive: it uses no choice axioms, no classical logic, and nothing beyond basic syntax manipulation. The module that contains it imports nothing beyond the Lean prelude and no external mathematics library.

The definition also includes a helper for the induction step of arithmetic proofs. The stepSucc function takes a formula and advances its bound variable by one successor step, effectively substituting the successor of zero for the innermost variable. This is the syntactic raw material for induction: it prepares the formula that says "if the property holds for n, it holds for n+1." The quantifier-free test, isQF, is a boolean check used to keep a later rule honest: Markov's principle is only posited for decidable, quantifier-free formulas.

What subst does not claim is as important as what it does. It does not define a notion of truth, a semantics, or a proof system. It does not introduce a universe hierarchy, dependent types, or propositions-as-types. It does not even assert that the object language can talk about its own substitution. The declaration is purely syntactic: it is the plumbing that lets formulas be manipulated before any derivation or checking happens. The framework's larger claims about forced structure and recognition costs live elsewhere, in modules that build on this syntax but are not part of it.

In the Recognition Science account, this syntax is the "forced base": the free distinction structure of the natural numbers with its recursion-licensed operations. The idea is that the natural numbers are not chosen but forced by the framework's starting point, and the operations of addition and multiplication are the canonical extensions licensed by that freeness. The substitution function is the tool that makes reasoning about this structure possible without smuggling in any assumptions. It is a foundation stone, and like a foundation stone, its virtue is that it supports weight without itself being load-bearing.

/-- Substitute `s` for variable `k` (binder instantiation: free variables
above `k` shift down by one). -/
def subst (k : Nat) (s : DTerm) : DTerm → DTerm
  | var n   => if n = k then s else if k < n then var (n - 1) else var n
  | zero    => zero
  | succ t  => succ (subst k s t)
  | add t u => add (subst k s t) (subst k s u)
  | mul t u => mul (subst k s t) (subst k s u)

/-- Substitute `s` for variable `k` (binder instantiation: free variables
above `k` shift down by one). -/
def subst (k : Nat) (s : DTerm) : DTerm → DTerm
  | var n   => if n = k then s else if k < n then var (n - 1) else var n
  | zero    => zero
  | succ t  => succ (subst k s t)
  | add t u => add (subst k s t) (subst k s u)
  | mul t u => mul (subst k s t) (subst k s u)

/-- Terms over the distinction signature: de Bruijn variables, zero,
successor (the distinction step), addition, multiplication.
`0` and `S` are the primitive signature of the free distinction structure;
`+` and `·` are the canonical recursion-licensed extensions (their defining
equations are axiom rules in `Check.lean`, licensed by initiality:
"freeness is forcing"). -/
inductive DTerm : Type where
  | var  : Nat → DTerm
  | zero : DTerm
  | succ : DTerm → DTerm
  | add  : DTerm → DTerm → DTerm
  | mul  : DTerm → DTerm → DTerm

/-- The induction-step body: `φ` with its bound variable advanced by one
distinction step, i.e. `φ[x ↦ S x]` for the de Bruijn variable 0,
leaving all other free variables fixed. -/
def stepSucc (φ : DFormula) : DFormula :=
  (φ.lift 1 1).subst 0 (DTerm.succ (DTerm.var 0))

What this page does not claim

Subst does not define a notion of truth or semantics for the object language. Subst does not introduce a universe hierarchy, dependent types, or propositions-as-types. The framework's claims about recognition costs are not established by this declaration.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/DeltaKernel/Syntax.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: