Supporting results for pointwise provable equality.

Fixpoint Construction

structure PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Blueprint (k : ℕ) : Type

Data specifying the encoded construction in FFL.FirstOrder.Arithmetic.Fixpoint.

• core : ∆₁.Semisentence (k + 2)

  The core construction in FFL.FirstOrder.Arithmetic.Fixpoint.Blueprint.

@[instance_reducible]

instance PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Blueprint.instCoeSemisentenceDeltaOneHAddNatOfNat {k : ℕ} : Coe (Blueprint k) (∆₁.Semisentence (k + 2))

Equations

• PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Blueprint.instCoeSemisentenceDeltaOneHAddNatOfNat = { coe := PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Blueprint.core }

def PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Blueprint.succDef {k : ℕ} (φ : Blueprint k) : Σ₁.Semisentence (k + 3)

The succ Def construction in FFL.FirstOrder.Arithmetic.Fixpoint.Blueprint.

Equations

• One or more equations did not get rendered due to their size.

def PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Blueprint.prBlueprint {k : ℕ} (φ : Blueprint k) : PR.Blueprint k

The pr Blueprint construction in FFL.FirstOrder.Arithmetic.Fixpoint.Blueprint.

Equations

• One or more equations did not get rendered due to their size.

def PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Blueprint.limSeqDef {k : ℕ} (φ : Blueprint k) : Σ₁.Semisentence (k + 2)

The lim Seq Def construction in FFL.FirstOrder.Arithmetic.Fixpoint.Blueprint.

Equations

• φ.limSeqDef = φ.prBlueprint.resultDef

@[irreducible]

def PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Blueprint.fixpointDef {k : ℕ} (φ : Blueprint k) : Σ₁.Semisentence (k + 1)

The fixpoint Def construction in FFL.FirstOrder.Arithmetic.Fixpoint.Blueprint.

Equations

• One or more equations did not get rendered due to their size.

def PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Blueprint.fixpointDefΔ₁ {k : ℕ} (φ : Blueprint k) : ∆₁.Semisentence (k + 1)

The fixpoint DefΔ₁ construction in FFL.FirstOrder.Arithmetic.Fixpoint.Blueprint.

Equations

• One or more equations did not get rendered due to their size.

structure PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction (V : Type u_1) [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} (φ : Blueprint k) : Type u_1

Data and laws for Construction in FFL.FirstOrder.Arithmetic.Fixpoint.

• Φ : (Fin k → V) → Set V → V → Prop

  The Φ construction in FFL.FirstOrder.Arithmetic.Fixpoint.Construction.

• defined : HierarchySymbol.Defined (fun (v : Fin (k + 1 + 1) → V) => self.Φ (fun (x : Fin k) => v x.succ.succ) {x : V | x ∈ v 1} (v 0)) φ.core
• monotone {C C' : Set V} (h : C ⊆ C') {v : Fin k → V} {x : V} : self.Φ v C x → self.Φ v C' x

class PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.Finite (V : Type u_1) [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) : Prop

Data and laws for Finite in FFL.FirstOrder.Arithmetic.Fixpoint.Construction.

• finite {C : Set V} {v : Fin k → V} {x : V} : c.Φ v C x → ∃ (m : V), c.Φ v {y : V | y ∈ C ∧ y < m} x

class PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.StrongFinite (V : Type u_1) [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) : Prop

Data and laws for Strong Finite in FFL.FirstOrder.Arithmetic.Fixpoint.Construction.

• strong_finite {C : Set V} {v : Fin k → V} {x : V} : c.Φ v C x → c.Φ v {y : V | y ∈ C ∧ y < x} x

instance PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.instFiniteOfStrongFinite (V : Type u_1) [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) [Construction.StrongFinite V c] : Construction.Finite V c

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.eval_formula {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) (v : Fin k.succ.succ → V) : (Semiformula.Evalb v) ↑φ.core ↔ c.Φ (fun (x : Fin k) => v x.succ.succ) {x : V | x ∈ v 1} (v 0)

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.succ_existsUnique {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) (v : Fin k → V) (s ih : V) : ∃! u : V, ∀ (x : V), x ∈ u ↔ x ≤ s ∧ c.Φ v {z : V | z ∈ ih} x

noncomputable def PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.succ {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) (v : Fin k → V) (s ih : V) : V

The succ construction in FFL.FirstOrder.Arithmetic.Fixpoint.Construction.

Equations

• c.succ v s ih = PointwiseComposition.Classical.chooseUnique ⋯

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.mem_succ_iff {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) {x : V} {v : Fin k → V} {s ih : V} : x ∈ c.succ v s ih ↔ x ≤ s ∧ c.Φ v {z : V | z ∈ ih} x

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.succ_defined {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) : HierarchySymbol.DefinedFunction (fun (v : Fin (k + 2) → V) => c.succ (fun (x : Fin k) => v x.succ.succ) (v 1) (v 0)) φ.succDef

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.eval_succDef {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) (v : Fin (k + 3) → V) : (Semiformula.Evalb v) ↑φ.succDef ↔ v 0 = c.succ (fun (x : Fin k) => v x.succ.succ.succ) (v 2) (v 1)

noncomputable def PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.prConstruction {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) : PR.Construction V φ.prBlueprint

The pr Construction construction in FFL.FirstOrder.Arithmetic.Fixpoint.Construction.

Equations

• c.prConstruction = { zero := fun (x : Fin k → V) => ∅, succ := c.succ, zero_defined := ⋯, succ_defined := ⋯ }

noncomputable def PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.limSeq {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) (v : Fin k → V) (s : V) : V

The lim Seq construction in FFL.FirstOrder.Arithmetic.Fixpoint.Construction.

Equations

• c.limSeq v s = c.prConstruction.result v s

@[simp]

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.limSeq_zero {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) {v : Fin k → V} : c.limSeq v 0 = ∅

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.limSeq_succ {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) {v : Fin k → V} (s : V) : c.limSeq v (s + 1) = c.succ v s (c.limSeq v s)

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.termSet_defined {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) : HierarchySymbol.DefinedFunction (fun (v : Fin (k + 1) → V) => c.limSeq (fun (x : Fin k) => v x.succ) (v 0)) φ.limSeqDef

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.eval_limSeqDef {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) (v : Fin (k + 2) → V) : (Semiformula.Evalb v) ↑φ.limSeqDef ↔ v 0 = c.limSeq (fun (x : Fin k) => v x.succ.succ) (v 1)

instance PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.limSeq_definable {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) : Σ₁.DefinableFunction fun (v : Fin (k + 1) → V) => c.limSeq (fun (x : Fin k) => v x.succ) (v 0)

instance PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.limSeq_definable' {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) {m : ℕ} (Γ : SigmaPiDelta) : { Γ := Γ, rank := m + 1 }.DefinableFunction fun (v : Fin (k + 1) → V) => c.limSeq (fun (x : Fin k) => v x.succ) (v 0)

@[simp]

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.mem_limSeq_succ_iff {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) {v : Fin k → V} {x s : V} : x ∈ c.limSeq v (s + 1) ↔ x ≤ s ∧ c.Φ v {z : V | z ∈ c.limSeq v s} x

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.limSeq_cumulative {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) {v : Fin k → V} {s s' : V} : s ≤ s' → c.limSeq v s ⊆ c.limSeq v s'

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.mem_limSeq_self {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) {v : Fin k → V} [StrongFinite V c] {u s : V} : u ∈ c.limSeq v s → u ∈ c.limSeq v (u + 1)

def PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.IsFixedPoint {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) (v : Fin k → V) (x : V) : Prop

The Fixpoint construction in FFL.FirstOrder.Arithmetic.Fixpoint.Construction.

Equations

• c.IsFixedPoint v x = ∃ (s : V), x ∈ c.limSeq v s

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.fixpoint_iff {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) {v : Fin k → V} [StrongFinite V c] {x : V} : c.IsFixedPoint v x ↔ x ∈ c.limSeq v (x + 1)

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.fixpoint_iff_succ {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) {v : Fin k → V} {x : V} : c.IsFixedPoint v x ↔ ∃ (u : V), x ∈ c.limSeq v (u + 1)

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.finite_upperbound {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) {v : Fin k → V} (m : V) : ∃ (s : V), ∀ z < m, c.IsFixedPoint v z → z ∈ c.limSeq v s

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.case {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) {v : Fin k → V} {x : V} [Finite V c] : c.IsFixedPoint v x ↔ c.Φ v {z : V | c.IsFixedPoint v z} x

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.fixpoint_defined {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) : HierarchySymbol.Defined (fun (v : Fin (k + 1) → V) => c.IsFixedPoint (fun (x : Fin k) => v x.succ) (v 0)) φ.fixpointDef

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.eval_fixpointDef {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) (v : Fin (k + 1) → V) : (Semiformula.Evalb v) ↑φ.fixpointDef ↔ c.IsFixedPoint (fun (x : Fin k) => v x.succ) (v 0)

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.fixpoint_definedΔ₁ {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) [StrongFinite V c] : HierarchySymbol.Defined (fun (v : Fin (k + 1) → V) => c.IsFixedPoint (fun (x : Fin k) => v x.succ) (v 0)) φ.fixpointDefΔ₁

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.eval_fixpointDefΔ₁ {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) [StrongFinite V c] (v : Fin (k + 1) → V) : (Semiformula.Evalb v) ↑φ.fixpointDefΔ₁ ↔ c.IsFixedPoint (fun (x : Fin k) => v x.succ) (v 0)

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.Fixpoint.Construction.induction {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {φ : Blueprint k} (c : Construction V φ) {v : Fin k → V} {Γ : SigmaPiDelta} [StrongFinite V c] {P : V → Prop} (hP : { Γ := Γ, rank := 1 }-Predicate P) (H : ∀ (C : Set V), (∀ x ∈ C, c.IsFixedPoint v x ∧ P x) → ∀ (x : V), c.Φ v C x → P x) (x : V) : c.IsFixedPoint v x → P x