LemmaStatement: AI-adaptedProof: AI-generatedPipeline-generatedjudge pass (gpt-5.6-terra)audited 2026-09-07

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Free-for substitution commutes with satisfaction

Statement

If $t$ is free for $x$ in $ϕ$ , then for every structure $M$ and assignment $s$ ,

$M, s ⊨ ϕ [t / x] ⟺ M, s [x : = ⟦ t ⟧_{s}] ⊨ ϕ .$

Facts & Assumptions

Given: Work in ZF unless the statement explicitly weakens or supplements it; fix the objects and hypotheses of the statement.

[F1]

For any terms $u, t$ , variable $x$ , structure $M$ and assignment $s$ , put $b = ⟦ t ⟧_{s}$ . Then $⟦ u [t / x] ⟧_{s} = ⟦ u ⟧_{s [x : = b]}$ . (Term substitution commutes with evaluation)

[F2]

Assignments agreeing on $FV (e)$ give equal denotations when $e$ is a term and the same truth value when $e$ is a formula. Also, passage to a reduct preserves denotations and satisfaction for expressions in the smaller signature. In particular sentence truth is independent of assignment; the truth of a formula can be specified by any tuple assigning all its free variables. (Coincidence for term values and satisfaction)

Proof

1.1F1

Write $b = ⟦ t ⟧_{s}$ . The term substitution identity proves the assertion for both kinds of atoms. Negation and conjunction transport the inductive equivalences through their truth clauses.

1.2F2

At $\exists y ψ$ , if $y = x$ , raw substitution leaves this quantified formula unchanged and updating its bound variable externally cannot affect its truth by coincidence. If $x \notin FV (ψ)$ , substitution again changes nothing and coincidence gives the result.

1.3F1F2

Otherwise $y \neq x$ and $x \in FV (ψ)$ . The free-for hypothesis gives $y \notin FV (t)$ and the free-for condition in $ψ$ . For each $a \in M$ , coincidence makes $⟦ t ⟧_{s [y : = a]} = b$ . The two distinct-variable updates commute: $s [y : = a] [x : = b] = s [x : = b] [y : = a]$ . Applying the induction hypothesis to $ψ$ at $s [y : = a]$ therefore gives the same truth at each witness $a$ on both sides.

2.1step 1.1step 1.2step 1.3∎

Existential quantification over these pointwise equivalent assertions proves both directions for $\exists y ψ$ . The cases above exhaust its possibilities, so structural induction gives the result for every formula.

Depends on

Used by

Agreement at one assignment is insufficient Counterexample
Fresh bound-variable renaming preserves truth Lemma
Models of the elementary diagram yield elementary embeddings Lemma
Canonical capture-avoiding substitution Proposition
Soundness for arbitrary set signatures Theorem
Truth lemma for the term quotient Theorem

Dependency tree · two levels

5 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Moschovakis, Lecture Notes in Logic (2014) — x1.1.3, p.48 (formula case). (standard reference, not scraped)