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.

Fresh bound-variable renaming preserves truth

Statement

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.

Facts & Assumptions

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

[F1]

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.1F1

No binder in $ψ$ uses $z$ , so substitution introduces no capture. At an assignment $s [z : = a]$ , the free-for identity gives truth of $ψ [z / y]$ exactly when $ψ$ is true at $s [z : = a] [y : = a]$ .

2.1F1step 1.1

Since $z$ is absent from $ψ$ , coincidence (as used in the free-for lemma) removes the update at $z$ when evaluating $ψ$ . The last assignment therefore gives the same truth as $s [y : = a]$ . Quantifying over the same $a \in M$ proves the claimed equivalence. Inner binders for $y$ were untouched by the raw substitution rule.

3.1given∎

A finite set of variable indices is bounded in $ω$ , by induction over its finite listing and taking successive maxima. There is an index outside it, and the least such index is uniquely specified by the natural order. This proves the fresh-variable assertion without choosing from a family of sets.

Fresh bound-variable renaming preserves truth

Statement

Facts & Assumptions

Proof

Depends on

Dependency tree · 2 levels

Sources