All proofs
Project-declaredLean 4.32.1 · mathlib@520045ab

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 `γ ⇜ ![...

Exact Lean statement

lemma bv_quote_fixitr (χ : _root_.LO.FirstOrder.Semiformula L ℕ 0) :
    bv (V := ℕ) L (⌜(Rew.fixitr 0 χ.fvSup ▹ χ : _root_.LO.FirstOrder.Semiformula L ℕ (0 + χ.fvSup))⌝ : ℕ)
      = χ.fvSup

Formal artifact

Lean source

Canonical source
Full Lean sourceLean 4
lemma bv_quote_fixitr (χ : _root_.LO.FirstOrder.Semiformula L  0) :    bv (V := ) L (⌜(Rew.fixitr 0 χ.fvSup ▹ χ : _root_.LO.FirstOrder.Semiformula L  (0 + χ.fvSup))⌝ : )      = χ.fvSup := by  -- the freevar-free closure body  have not_fvar_body :  x, ¬(Rew.fixitr 0 χ.fvSup ▹ χ).FVar? x := by    intro x    rw [Rew.eq_bind (Rew.fixitr 0 χ.fvSup)]    simp only [Function.comp_def, Rew.fixitr_bvar, Rew.fixitr_fvar, Fin.natAdd_mk, zero_add]    intro hh    rcases Semiformula.fvar?_rew hh with (z, hz | z, hz, hx)    · simp at hz    · have : z < χ.fvSup := Semiformula.lt_fvSup_of_fvar? hz      simp [this] at hx  have hbsemi := Semiformula.quote_isSemiformula (V := )    (Rew.fixitr 0 χ.fvSup ▹ χ : _root_.LO.FirstOrder.Semiformula L  (0 + χ.fvSup))  have hbU : IsUFormula L (⌜(Rew.fixitr 0 χ.fvSup ▹ χ : _root_.LO.FirstOrder.Semiformula L  (0 + χ.fvSup))⌝ : ) :=    hbsemi.isUFormula  -- `≤` direction: the body has `0 + fvSup` bound slots, so `bv ≤ fvSup` (model order over ℕ).  -- On ℕ the model cast is the identity (`natCast_nat`) and `<` is `Nat.lt`.  have hle := hbsemi.bv_le  simp only [Nat.zero_add, natCast_nat] at hle  -- the model `≤` on ℕ unfolds to `= ∨ <` with `<` the standard `Nat.lt`  rcases (hle : bv (V := ) L (⌜(Rew.fixitr 0 χ.fvSup ▹ χ : _root_.LO.FirstOrder.Semiformula L  (0 + χ.fvSup))⌝ : )      = χ.fvSup  bv (V := ) L (⌜(Rew.fixitr 0 χ.fvSup ▹ χ : _root_.LO.FirstOrder.Semiformula L  (0 + χ.fvSup))⌝ : )      < χ.fvSup) with heq | hlt  · exact heq  -- `hlt : bv ⌜body⌝ < χ.fvSup` ; this case is impossible (forbids vacuous leading `∀`s)  exfalso  set j := bv (V := ) L (⌜(Rew.fixitr 0 χ.fvSup ▹ χ : _root_.LO.FirstOrder.Semiformula L  (0 + χ.fvSup))⌝ : ) with hj  have hpos : 0 < χ.fvSup := by omega  have hsemi : IsSemiformula L j (⌜(Rew.fixitr 0 χ.fvSup ▹ χ : _root_.LO.FirstOrder.Semiformula L  (0 + χ.fvSup))⌝ : ) := by    have := IsUFormula.isSemiformula hbU; rwa [ hj] at this  obtain γ, hγ := IsSemiformula.sound hsemi  have hjle : j  0 + χ.fvSup := by omega  -- codes agree across levels, hence the formulas agree  have hcast : (Rew.castLE hjle ▹ γ : _root_.LO.FirstOrder.Semiformula L  (0 + χ.fvSup))      = (Rew.fixitr 0 χ.fvSup ▹ χ : _root_.LO.FirstOrder.Semiformula L  (0 + χ.fvSup)) := by    apply (Semiformula.quote_inj_iff (V := )).mp    rw [Semiformula.quote_castLE, hγ]  -- `γ` is free-variable-free  have hγfree : γ.freeVariables =:= by    have hb : (Rew.fixitr 0 χ.fvSup ▹ χ : _root_.LO.FirstOrder.Semiformula L  (0 + χ.fvSup)).freeVariables =:=      Finset.eq_empty_of_forall_notMem fun x hx  not_fvar_body x hx    have := Semiformula.freeVariables_castLE γ hjle    rw [hcast, hb] at this; exact this.symm  -- invert the closure: `χ = γ ⇜ ![&0, …, &(j-1)]`  have hχeq : χ = γ ⇜ (fun i : Fin j  (&↑i : SyntacticTerm L)) := by    have e1 : (Rew.fixitr 0 χ.fvSup ▹ χ : _root_.LO.FirstOrder.Semiformula L  (0 + χ.fvSup))        ⇜ (fun x : Fin (0 + χ.fvSup)  (&↑x : SyntacticTerm L)) = χ := Semiformula.subst_comp_fixitr χ    have hRewEq : (Rew.subst (fun x : Fin (0 + χ.fvSup)  (&↑x : SyntacticTerm L))).comp (Rew.castLE hjle)        = Rew.subst (fun i : Fin j  (&↑i : SyntacticTerm L)) := by      ext x <;> simp [Rew.comp_app]    symm    rw [ e1,  hcast]    unfold Rewriting.subst    rw [ TransitiveRewriting.comp_app, hRewEq]  -- contradiction: `&(fvSup-1)` occurs in `χ`, but the inversion bounds free vars by `j ≤ fvSup-1`  have hfv : (γ ⇜ (fun i : Fin j  (&↑i : SyntacticTerm L))).FVar? (χ.fvSup - 1) := by    rw [ hχeq]; exact Semiformula.fvar?_fvSup_pred χ hpos  unfold Rewriting.subst at hfv  rcases Semiformula.fvar?_rew hfv with (i, hi | z, hz, _)  · have hib : χ.fvSup - 1 = (i : ) := by      simpa [Rew.subst_bvar, Semiterm.FVar?, Semiterm.freeVariables_fvar] using hi    have hij := i.isLt    omega  · simp [Semiformula.FVar?, hγfree] at hz
Project
Foundation
License
Apache-2.0
Commit
8dcdb3196454
Source
Foundation/FirstOrder/Incompleteness/InductionSchemeDelta1.lean:296-361

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

Project-declaredLean 4.32.1

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.

formal logicmetatheoryproof theory

Source project: Foundation

Person-level attribution pending.

View proof record
Project-declaredLean 4.32.1

Conj

LO.FirstOrder.Arithmetic.Bootstrapping.Derivable.conj

Plain-language statement

Crucial inducion for formalized Σ1\Sigma_1-completeness.

formal logicmetatheoryproof theory

Source project: Foundation

Person-level attribution pending.

View proof record
Project-declaredLean 4.32.1

Fvar Vec val eq

LO.FirstOrder.Arithmetic.Bootstrapping.fvarVec_val_eq

Plain-language statement

fvarVec is the code of the typed substitution vector fun i ↦ ^&i (over a standard length).

formal logicmetatheoryproof theory

Source project: Foundation

Person-level attribution pending.

View proof record