Closure inversion
LO.FirstOrder.Arithmetic.closure_inversion
Plain-language statement
Closure inversion (forward keystone). A freevar-free level-m formula β whose internal bv is m and which substitutes back to succInd γ is exactly the fixitr-image, so its m-fold closure is (succInd γ).univCl'. Mirror of bv_quote_fixitr's ≥-direction inversion; the genuine remaining math.
Exact Lean statement
theorem closure_inversion {m : ℕ} (β : _root_.LO.FirstOrder.ArithmeticSemiformula ℕ m) (γ : _root_.LO.FirstOrder.ArithmeticSemiformula ℕ 1)
(hfree : β.freeVariables = ∅) (hbv : Bootstrapping.bv (V := ℕ) ℒₒᵣ (⌜β⌝ : ℕ) = m)
(hβγ : β ⇜ (fun i : Fin m ↦ (&↑i : SyntacticTerm ℒₒᵣ)) = succInd γ) :
(∀¹* β : _root_.LO.FirstOrder.ArithmeticSemiformula ℕ 0) = (succInd γ).univCl'Formal artifact
Lean source
theorem closure_inversion {m : ℕ} (β : _root_.LO.FirstOrder.ArithmeticSemiformula ℕ m) (γ : _root_.LO.FirstOrder.ArithmeticSemiformula ℕ 1) (hfree : β.freeVariables = ∅) (hbv : Bootstrapping.bv (V := ℕ) ℒₒᵣ (⌜β⌝ : ℕ) = m) (hβγ : β ⇜ (fun i : Fin m ↦ (&↑i : SyntacticTerm ℒₒᵣ)) = succInd γ) : (∀¹* β : _root_.LO.FirstOrder.ArithmeticSemiformula ℕ 0) = (succInd γ).univCl' := by set χ : _root_.LO.FirstOrder.ArithmeticSemiformula ℕ 0 := succInd γ with hχ -- (*) code-level: `⌜fixitr 0 m ▹ χ⌝ = ⌜β⌝` (rebind composite = castLE on freevar-free β; codes -- erase the level index, sidestepping the `0 + m` vs `m` cast) have hcodeβ : (⌜(Rew.fixitr 0 m ▹ χ : _root_.LO.FirstOrder.ArithmeticSemiformula ℕ (0 + m))⌝ : ℕ) = ⌜β⌝ := by have hcompcast : ((Rew.fixitr 0 m).comp (Rew.subst (fun i : Fin m ↦ (&↑i : SyntacticTerm ℒₒᵣ)))) ▹ β = (Rew.castLE (Nat.le_add_left m 0) ▹ β : _root_.LO.FirstOrder.ArithmeticSemiformula ℕ (0 + m)) := by apply Semiformula.rew_eq_of_funEqOn · intro x; simp [Rew.comp_app, Rew.fixitr_fvar, Fin.ext_iff] · intro x hx; rw [Semiformula.FVar?, hfree] at hx; simp at hx have heq : (Rew.fixitr 0 m ▹ χ : _root_.LO.FirstOrder.ArithmeticSemiformula ℕ (0 + m)) = (Rew.castLE (Nat.le_add_left m 0) ▹ β : _root_.LO.FirstOrder.ArithmeticSemiformula ℕ (0 + m)) := by rw [← hcompcast, TransitiveRewriting.comp_app, show (Rew.subst (fun i : Fin m ↦ (&↑i : SyntacticTerm ℒₒᵣ)) ▹ β) = χ from hβγ] rw [heq, Semiformula.quote_castLE (V := ℕ) β (Nat.le_add_left m 0)] -- free vars of `χ = β ⇜ (&·)` are all `< m`, so `χ.fvSup ≤ m` have hfvbound : ∀ x, χ.FVar? x → x < m := by intro x hx rw [show χ = β ⇜ (fun i : Fin m ↦ (&↑i : SyntacticTerm ℒₒᵣ)) from hβγ.symm] at hx rcases Semiformula.fvar?_rew hx with (⟨i, hi⟩ | ⟨z, hz, _⟩) · have : x = (↑i : ℕ) := by simpa [Rew.subst_bvar, Semiterm.FVar?, Semiterm.freeVariables_fvar] using hi rw [this]; exact i.isLt · rw [Semiformula.FVar?, hfree] at hz; simp at hz have hfvle : χ.fvSup ≤ m := by rcases Nat.eq_zero_or_pos χ.fvSup with h0 | hpos · omega · have := hfvbound (χ.fvSup - 1) (Semiformula.fvar?_fvSup_pred χ hpos); omega -- (A) `m = χ.fvSup`: `fixitr 0 m ▹ χ` shares the *code* of `fixitr 0 χ.fvSup ▹ χ` (castLE), whose -- `bv` is `χ.fvSup` (bv_quote_fixitr); but `bv ⌜β⌝ = m` (hbv), and `⌜β⌝ = ⌜fixitr 0 m ▹ χ⌝`. have hcast_eq : (Rew.fixitr 0 m ▹ χ : _root_.LO.FirstOrder.ArithmeticSemiformula ℕ (0 + m)) = (Rew.castLE (by omega : (0 + χ.fvSup) ≤ (0 + m)) ▹ (Rew.fixitr 0 χ.fvSup ▹ χ : _root_.LO.FirstOrder.ArithmeticSemiformula ℕ (0 + χ.fvSup))) := by rw [← TransitiveRewriting.comp_app] apply Semiformula.rew_eq_of_funEqOn₀ intro x hx have hxlt : x < χ.fvSup := Semiformula.lt_fvSup_of_fvar? hx simp [Rew.comp_app, Rew.fixitr_fvar, hxlt, show x < m from by omega] have hcode : (⌜(Rew.fixitr 0 m ▹ χ : _root_.LO.FirstOrder.ArithmeticSemiformula ℕ (0 + m))⌝ : ℕ) = ⌜(Rew.fixitr 0 χ.fvSup ▹ χ : _root_.LO.FirstOrder.ArithmeticSemiformula ℕ (0 + χ.fvSup))⌝ := by rw [hcast_eq, Semiformula.quote_castLE (V := ℕ) (Rew.fixitr 0 χ.fvSup ▹ χ : _root_.LO.FirstOrder.ArithmeticSemiformula ℕ (0 + χ.fvSup)) (by omega)] have hm : m = χ.fvSup := by rw [← hbv, ← hcodeβ, hcode]; exact Bootstrapping.bv_quote_fixitr χ -- conclude via codes: `⌜∀¹* β⌝ = qqAlls ⌜β⌝ m = qqAlls ⌜fixitr 0 χ.fvSup ▹ χ⌝ (0+χ.fvSup) = ⌜χ.univCl'⌝` apply (Semiformula.quote_inj_iff (L := ℒₒᵣ) (V := ℕ)).mp rw [Bootstrapping.quote_allClosure (V := ℕ) β, Semiformula.univCl', Bootstrapping.quote_allClosure (V := ℕ) (Rew.fixitr 0 χ.fvSup ▹ χ), ← hcodeβ, hcode, hm] simp- Project
- Foundation
- License
- Apache-2.0
- Commit
- 8dcdb3196454
- Source
- Foundation/FirstOrder/Incompleteness/InductionSchemeDelta1.lean:975-1027
Reuse this declaration
Bring the exact result into your workflow
The import identifies the source module. Your project still needs the pinned package dependency shown on this page.
What this badge means
This completion status comes from the project or community source. It has not yet been represented here as an independent rebuild and axiom audit.
Continue in this project
Related declarations
Computable Pred iff decoded pred
ComputablePred.iff_decoded_pred
Plain-language statement
Computability of a predicate on a Primcodable type is equivalent to the computability of the corresponding predicate on ℕ obtained by decoding.
Source project: Foundation
Person-level attribution pending.
Bv quote fixitr
LO.FirstOrder.Arithmetic.Bootstrapping.bv_quote_fixitr
Plain-language statement
bv-pin bridge (over ℕ): bv ⌜fixitr 0 (fvSup χ) ▹ χ⌝ = fvSup χ. - ≤ is immediate from quote_univCl_eq + bv_qqAlls (closing fvSup quantifiers reaches a sentence, whose bv is 0). - ≥ is by level-factoring: were the body an IsSemiformula j for some j < fvSup, IsSemiformula.sound + castLE-invariance would re-express χ as `γ ⇜ ![...
Source project: Foundation
Person-level attribution pending.
Conj
LO.FirstOrder.Arithmetic.Bootstrapping.Derivable.conj
Plain-language statement
Crucial inducion for formalized -completeness.
Source project: Foundation
Person-level attribution pending.