PropositionStatement: 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.

Canonical capture-avoiding substitution

Statement

There is a canonical total capture-avoiding substitution $ϕ ⟨ t / x ⟩$ on formulas, obtained by renaming obstructing binders using least unused variable indices. It replaces the original free occurrences of $x$ and satisfies

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

Canonicity refers to the specified coding and traversal, not to literal invariance under other fresh-variable conventions.

Facts & Assumptions

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

[F1]

If $z \neq y$ is absent from $Var (ψ)$ , then $z$ is free for $y$ in $ψ$ , and $\exists y ψ$ and $\exists z (ψ [z / y])$ have the same truth in every structure and assignment. Here raw substitution replaces only occurrences free in $ψ$ , hence only those bound by the displayed outer binder. A least fresh variable exists outside any specified finite set of variables. (Fresh bound-variable renaming preserves truth)

[F2]

If $t$ is free for $x$ in $ψ$ , then for every structure $M$ and assignment $s$ , $M, s ⊨ ψ [t / x] ⟺ M, s [x : = ⟦ t ⟧_{s}] ⊨ ψ .$ (Free-for substitution commutes with satisfaction)

Proof

1.1

Traverse the original parse tree in preorder, visiting the left child before the right child. Begin with the finite forbidden set $Var (ϕ) \cup Var (t) \cup {x}$ . Rename every binder whose variable belongs to $FV (t) \cup {x}$ to the least index outside the current forbidden set, add that variable to the forbidden set, and rename exactly the occurrences governed by that binder. At each operation the new name is absent from the entire current formula, so the fresh-renaming lemma applies.

F1construct

2.1

There are only finitely many original binder nodes. Renaming changes names but neither the tree nor the number of nodes; hence the traversal terminates and produces a uniquely specified formula $ϕ^{*}$ . Repeated fresh-renaming equivalence gives the same truth as $ϕ$ at every assignment. Original free occurrences are unchanged; all remaining binders avoid $x$ and $FV (t)$ .

F1step 1.1

3.1

Set $ϕ ⟨ t / x ⟩ = ϕ^{*} [t / x]$ . Now $t$ is free for $x$ in $ϕ^{*}$ , so F2 identifies its truth at $s$ with the truth of $ϕ^{*}$ at $s [x : = ⟦ t ⟧_{s}]$ . Step 2.1 changes that last formula back to $ϕ$ . This proves both directions and totality.

F2step 2.1∎

Depends on

Used by

Semantic equivalence is preserved by substitution Corollary
Variable capture changes satisfaction Counterexample
Relativization to sets and definable classes Definition
V has a definable truth predicate False statement

Dependency tree · two levels

4 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

Weiss, An Introduction to Set Theory (2014) — chapter 1 pp.17–18. (standard reference, not scraped)