All proofs
Project-declaredLean 4.32.1 · mathlib@520045ab

Polynomial induction

LO.FirstOrder.Arithmetic.polynomial_induction

Project documentation

!⟪x, y, z, ...⟫ notation for Seq -/ syntax "⟪" term,* "⟫" : term macro_rules | (⟪$term:term, $terms:term,*⟫) => (pair termterm ⟪terms,*⟫) | (⟪$term:term⟫) => (term)@[appunexpanderpair]metadefpairUnexpander:Lean.PrettyPrinter.Unexpander(term) @[app_unexpander pair] meta def pairUnexpander : Lean.PrettyPrinter.Unexpander | `(_ termterm term2) => `(⟪term,term, term2⟫) | _ => throw () lemma pair_graph {a b c : V} : c = ⟪a, b⟫ ↔ (a...

Exact Lean statement

@[elab_as_elim]
lemma polynomial_induction [V↓[ℒₒᵣ] ⊧* 𝗣𝗔⁻] (Γ m) [V↓[ℒₒᵣ] ⊧* 𝗜𝗡𝗗 Γ m]
    {P : V → Prop} (hP : Γ-[m]-Predicate P)
    (zero : P 0) (even : ∀ x > 0, P x → P (2 * x)) (odd : ∀ x, P x → P (2 * x + 1)) : ∀ x, P x

Formal artifact

Lean source

Canonical source
Full Lean sourceLean 4
@[elab_as_elim]lemma polynomial_induction [V↓[ℒₒᵣ] ⊧* 𝗣𝗔⁻] (Γ m) [V↓[ℒₒᵣ] ⊧* 𝗜𝗡𝗗 Γ m]    {P : V  Prop} (hP : Γ-[m]-Predicate P)    (zero : P 0) (even :  x > 0, P x  P (2 * x)) (odd :  x, P x  P (2 * x + 1)) :  x, P x := by  have : V↓[ℒₒᵣ] ⊧* 𝗜𝗡𝗗 Γ m := inferInstance  have : V↓[ℒₒᵣ] ⊧* 𝗜𝗢𝗽𝗲𝗻 := models_of_subtheory this  intro x; induction x using InductionOnHierarchy.order_induction  · exact Γ  · exact m  · exact hP  case inst => exact inferInstance  case ind x IH =>    rcases Arithmetic.zero_le x with (rfl | pos)    · exact zero    · have : x / 2 < x := div_lt_of_pos_of_one_lt pos one_lt_two      rcases even_or_odd' x with (hx | hx)      · simpa [hx] using even (x / 2) (by by_contra A; simp at A; simp [show x = 0 from by simpa [A] using hx] at pos) (IH (x / 2) this)      · simpa [hx] using odd (x / 2) (IH (x / 2) this)
Project
Foundation
License
Apache-2.0
Commit
8dcdb3196454
Source
Foundation/FirstOrder/Arithmetic/IOpen/Basic.lean:771-788

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