All proofs
Project-declaredLean 4.32.1 · mathlib@520045ab

Hierarchy of is Sigma1

LO.FirstOrder.Arithmetic.hierarchy_of_isSigma1

Plain-language statement

(⟹) A 𝚺₁-recognized code is the code of a 𝚺₁ formula. Meta-induction on the formula: atoms are 𝚺₁ unconditionally; ∧/∨/∃ recurse; the ^∀ case is forced into the bounded shape by the recognizer (IsSigma1.of_all), and the bound is a bShift-image (positivity via termBV_termBShift_le), so Hierarchy.ball applies.

Exact Lean statement

lemma hierarchy_of_isSigma1 {n : ℕ} (ψ : _root_.LO.FirstOrder.ArithmeticSemiformula ℕ n) :
    IsSigma1 (⌜ψ⌝ : ℕ) → Hierarchy 𝚺 1 ψ

Formal artifact

Lean source

Canonical source
Full Lean sourceLean 4
lemma hierarchy_of_isSigma1 {n : } (ψ : _root_.LO.FirstOrder.ArithmeticSemiformula  n) :    IsSigma1 (⌜ψ⌝ : )  Hierarchy 𝚺 1 ψ := by  induction ψ using Semiformula.rec' with  | hverum => intro _; simp  | hfalsum => intro _; simp  | hrel R v => intro _; exact Hierarchy.rel _ _ _ _  | hnrel R v => intro _; exact Hierarchy.nrel _ _ _ _  | hand φ ψ ihφ ihψ =>      intro h; rw [Semiformula.quote_and (V := ) φ ψ, IsSigma1.and_iff] at h      exact Hierarchy.and (ihφ h.1) (ihψ h.2)  | hor φ ψ ihφ ihψ =>      intro h; rw [Semiformula.quote_or (V := ) φ ψ, IsSigma1.or_iff] at h      exact Hierarchy.or (ihφ h.1) (ihψ h.2)  | hall φ ihφ =>      intro h      rw [Semiformula.quote_all (V := ) φ] at h      obtain u, q, t, ht, rfl, hq, hφeq := IsSigma1.of_all h      have hsf := Semiformula.quote_isSemiformula (V := ) φ      simp only [natCast_nat] at hsf      rw [hφeq, Arithmetic.qqNLT] at hsf      simp only [IsSemiformula.or, IsSemiformula.nrel] at hsf      obtain ⟨⟨_, hvec, hqsf := hsf      obtain φ₂, hφ₂ := Bootstrapping.IsSemiformula.sound hqsf      have htmsf := hvec.nth (i := 1) (show (1 : ) < 2 by simp)      simp only [nth_adjoin_one, nth_adjoin_zero] at htmsf      obtain s, hs := Bootstrapping.IsSemiterm.sound        ((IsSemiterm.def (L := ℒₒᵣ)).mpr ht,          (termBV_termBShift_le (L := ℒₒᵣ) ht _).mp ((IsSemiterm.def (L := ℒₒᵣ)).mp htmsf).2)      have heq : (¹ φ) = ¹[“#0 < !!(Rew.bShift s)”] φ₂ := by        apply (Semiformula.quote_inj_iff (L := ℒₒᵣ) (V := )).mp        rw [Semiformula.quote_all (V := ) φ, hφeq, quote_ball, hs, hφ₂]        rfl      have hφ : Hierarchy 𝚺 1 φ := ihφ (by rw [hφeq]; simp [IsSigma1.or_iff, hq, Arithmetic.qqNLT])      have hφ2 : Hierarchy 𝚺 1 φ₂ := by        have hform : φ = (“#0 < !!(Rew.bShift s)” 🡒 φ₂) :=          (Semiformula.all_inj _ _).mp (by rw [ Semiformula.ball_eq]; exact heq)        rw [hform, Semiformula.imp_eq, Hierarchy.or_iff] at hφ        exact hφ.2      rw [heq]      exact Hierarchy.ball (Rew.positive_iff.mpr s, rfl) hφ2  | hexs φ ihφ =>      intro h; rw [Semiformula.quote_ex (V := ) φ, IsSigma1.ex_iff] at h      exact Hierarchy.exs (ihφ h)
Project
Foundation
License
Apache-2.0
Commit
8dcdb3196454
Source
Foundation/FirstOrder/Incompleteness/InductionSchemeDelta1.lean:1178-1220

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

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

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