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 terms,*⟫) | (⟪$term:term⟫) => (_ term2) => `(⟪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 xFormal artifact
Lean source
@[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
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.