Supporting results for pointwise provable equality.

Primitive Recursive Functions in $\mathsf{I} \Sigma_1$

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

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

• zero : Σ₁.Semisentence (k + 1)

  The zero construction in FFL.FirstOrder.Arithmetic.PR.Blueprint.

• succ : Σ₁.Semisentence (k + 3)

  The succ construction in FFL.FirstOrder.Arithmetic.PR.Blueprint.

def PointwiseComposition.FFL.FirstOrder.Arithmetic.PR.Blueprint.cseqDef {k : ℕ} (p : Blueprint k) : Σ₁.Semisentence (k + 1)

The cseq Def construction in FFL.FirstOrder.Arithmetic.PR.Blueprint.

Equations

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

@[irreducible]

def PointwiseComposition.FFL.FirstOrder.Arithmetic.PR.Blueprint.resultDef {k : ℕ} (p : Blueprint k) : Σ₁.Semisentence (k + 2)

The result Def construction in FFL.FirstOrder.Arithmetic.PR.Blueprint.

Equations

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

def PointwiseComposition.FFL.FirstOrder.Arithmetic.PR.Blueprint.resultDeltaDef {k : ℕ} (p : Blueprint k) : ∆₁.Semisentence (k + 2)

The result Delta Def construction in FFL.FirstOrder.Arithmetic.PR.Blueprint.

Equations

• p.resultDeltaDef = PointwiseComposition.FFL.FirstOrder.Arithmetic.HierarchySymbol.Semiformula.graphDelta p.resultDef

structure PointwiseComposition.FFL.FirstOrder.Arithmetic.PR.Construction (V : Type u_1) [ORingStructure V] {k : ℕ} (p : Blueprint k) : Type u_1

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

• zero : (Fin k → V) → V

  The zero construction in FFL.FirstOrder.Arithmetic.PR.Construction.

• succ : (Fin k → V) → V → V → V

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

• zero_defined : HierarchySymbol.DefinedFunction self.zero p.zero
• succ_defined : HierarchySymbol.DefinedFunction (fun (v : Fin (k + 1 + 1) → V) => self.succ (fun (x : Fin k) => v x.succ.succ) (v 1) (v 0)) p.succ

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

The CSeq construction in FFL.FirstOrder.Arithmetic.PR.Construction.

Equations

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

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

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

Helper lemmas for Cseqs

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.PR.Construction.CSeq.seq {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {p : Blueprint k} {c : Construction V p} {v : Fin k → V} {s : V} (h : c.CSeq v s) : Seq s

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.PR.Construction.CSeq.zero {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {p : Blueprint k} {c : Construction V p} {v : Fin k → V} {s : V} (h : c.CSeq v s) : ⟪0, c.zero v⟫ ∈ s

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.PR.Construction.CSeq.succ {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {p : Blueprint k} {c : Construction V p} {v : Fin k → V} {s : V} (h : c.CSeq v s) (i : V) : i < lh s - 1 → ∀ (z : V), ⟪i, z⟫ ∈ s → ⟪i + 1, c.succ v i z⟫ ∈ s

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.PR.Construction.CSeq.unique {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {p : Blueprint k} {c : Construction V p} {v : Fin k → V} {s₁ s₂ : V} (H₁ : c.CSeq v s₁) (H₂ : c.CSeq v s₂) (h₁₂ : lh s₁ ≤ lh s₂) {i : V} (hi : i < lh s₁) {z₁ z₂ : V} : ⟪i, z₁⟫ ∈ s₁ → ⟪i, z₂⟫ ∈ s₂ → z₁ = z₂

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.PR.Construction.CSeq.initial {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {p : Blueprint k} {c : Construction V p} {v : Fin k → V} : c.CSeq v !⟦c.zero v⟧

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.PR.Construction.CSeq.successor {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {p : Blueprint k} {c : Construction V p} {v : Fin k → V} {s l z : V} (Hs : c.CSeq v s) (hl : l + 1 = lh s) (hz : ⟪l, z⟫ ∈ s) : c.CSeq v (s ⁀' c.succ v l z)

Result of primitive recursion

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.PR.Construction.CSeq.exists {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {p : Blueprint k} (c : Construction V p) (v : Fin k → V) (l : V) : ∃ (s : V), c.CSeq v s ∧ l + 1 = lh s

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.PR.Construction.cSeq_result_existsUnique {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {p : Blueprint k} (c : Construction V p) (v : Fin k → V) (l : V) : ∃! z : V, ∃ (s : V), c.CSeq v s ∧ l + 1 = lh s ∧ ⟪l, z⟫ ∈ s

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

The result construction in FFL.FirstOrder.Arithmetic.PR.Construction.

Equations

• c.result v u = PointwiseComposition.Classical.chooseUnique ⋯

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.PR.Construction.result_spec {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {p : Blueprint k} (c : Construction V p) (v : Fin k → V) (u : V) : ∃ (s : V), c.CSeq v s ∧ u + 1 = lh s ∧ ⟪u, c.result v u⟫ ∈ s

@[simp]

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.PR.Construction.result_zero {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {p : Blueprint k} (c : Construction V p) (v : Fin k → V) : c.result v 0 = c.zero v

@[simp]

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.PR.Construction.result_succ {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {p : Blueprint k} (c : Construction V p) (v : Fin k → V) (u : V) : c.result v (u + 1) = c.succ v u (c.result v u)

theorem PointwiseComposition.FFL.FirstOrder.Arithmetic.PR.Construction.result_graph {V : Type u_1} [ORingStructure V] [V↓[ℒₒᵣ] ⊧* 𝐈Σ₁] {k : ℕ} {p : Blueprint k} (c : Construction V p) (v : Fin k → V) (z u : V) : z = c.result v u ↔ ∃ (s : V), c.CSeq v s ∧ ⟪u, z⟫ ∈ s

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

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

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

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

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