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