Preperations for arithmetic

• NOTE: To avoid the duplicate definitions of Tarski.Structure ℒₒᵣ for models, we basically use ORingStructure, and generated standardStructure instead of Tarski.Structure ℒₒᵣ itself.

class FFL.ORingStructure (α : Type u_1) extends Zero α, One α, Add α, Mul α, LT α : Type u_1

• zero : α
• one : α
• add : α → α → α
• mul : α → α → α
• lt : α → α → Prop

@[instance_reducible]

instance FFL.instORingStructureOfZeroOfOneOfAddOfMulOfLT {α : Type u_1} [Zero α] [One α] [Add α] [Mul α] [LT α] : ORingStructure α

Equations

• FFL.instORingStructureOfZeroOfOneOfAddOfMulOfLT = { toZero := inst✝⁴, toOne := inst✝³, toAdd := inst✝², toMul := inst✝¹, toLT := inst✝ }

def FFL.ORingStructure.numeral {α : Type u_1} [ORingStructure α] : ℕ → α

Equations

• FFL.ORingStructure.numeral 0 = 0
• FFL.ORingStructure.numeral 1 = 1
• FFL.ORingStructure.numeral n.succ.succ = FFL.ORingStructure.numeral (n + 1) + 1

@[simp]

theorem FFL.ORingStructure.zero_eq_zero {α : Type u_1} [ORingStructure α] : numeral 0 = 0

@[simp]

theorem FFL.ORingStructure.one_eq_one {α : Type u_1} [ORingStructure α] : numeral 1 = 1

@[simp]

theorem FFL.Nat.numeral_eq (n : ℕ) : ORingStructure.numeral n = n

@[reducible, inline]

abbrev FFL.FirstOrder.ArithmeticTheory : Type

Equations

• FFL.FirstOrder.ArithmeticTheory = FFL.FirstOrder.Theory ℒₒᵣ

@[reducible, inline]

abbrev FFL.FirstOrder.ArithmeticSemiterm (ξ : Type u_1) (n : ℕ) : Type u_1

Equations

• FFL.FirstOrder.ArithmeticSemiterm ξ n = FFL.FirstOrder.Semiterm ℒₒᵣ ξ n

@[reducible, inline]

abbrev FFL.FirstOrder.ArithmeticTerm (ξ : Type u_1) : Type u_1

Equations

• FFL.FirstOrder.ArithmeticTerm ξ = FFL.FirstOrder.Term ℒₒᵣ ξ

@[reducible, inline]

abbrev FFL.FirstOrder.ArithmeticSemiformula (ξ : Type u_1) (n : ℕ) : Type u_1

Equations

• FFL.FirstOrder.ArithmeticSemiformula ξ n = FFL.FirstOrder.Semiformula ℒₒᵣ ξ n

@[reducible, inline]

abbrev FFL.FirstOrder.ArithmeticFormula (ξ : Type u_1) : Type u_1

Equations

• FFL.FirstOrder.ArithmeticFormula ξ = FFL.FirstOrder.Formula ℒₒᵣ ξ

@[reducible, inline]

abbrev FFL.FirstOrder.ArithmeticSemisentence (n : ℕ) : Type

Equations

• FFL.FirstOrder.ArithmeticSemisentence n = FFL.FirstOrder.Semisentence ℒₒᵣ n

@[reducible, inline]

abbrev FFL.FirstOrder.ArithmeticSentence : Type

Equations

• FFL.FirstOrder.ArithmeticSentence = FFL.FirstOrder.Sentence ℒₒᵣ

@[reducible, inline]

abbrev FFL.FirstOrder.ArithmeticSemiproposition (n : ℕ) : Type

Equations

• FFL.FirstOrder.ArithmeticSemiproposition n = FFL.FirstOrder.Semiproposition ℒₒᵣ n

@[reducible, inline]

abbrev FFL.FirstOrder.ArithmeticProposition : Type

Equations

• FFL.FirstOrder.ArithmeticProposition = FFL.FirstOrder.Proposition ℒₒᵣ

def FFL.FirstOrder.Semiterm.toStringORing {ξ : Type u_1} [ToString ξ] {n : ℕ} : ArithmeticSemiterm ξ n → String

Equations

• (FFL.FirstOrder.Semiterm.bvar x_1).toStringORing = "x_{" ++ toString (n - 1 - ↑x_1) ++ "}"
• (FFL.FirstOrder.Semiterm.fvar x_1).toStringORing = "a_{" ++ toString x_1 ++ "}"
• (FFL.FirstOrder.Semiterm.func FFL.FirstOrder.Language.ORing.Func.zero a).toStringORing = "0"
• (FFL.FirstOrder.Semiterm.func FFL.FirstOrder.Language.ORing.Func.one a).toStringORing = "1"
• (FFL.FirstOrder.Semiterm.func FFL.FirstOrder.Language.ORing.Func.add v).toStringORing = "(" ++ (v 0).toStringORing ++ " + " ++ (v 1).toStringORing ++ ")"
• (FFL.FirstOrder.Semiterm.func FFL.FirstOrder.Language.ORing.Func.mul v).toStringORing = "(" ++ (v 0).toStringORing ++ " \\cdot " ++ (v 1).toStringORing ++ ")"

@[instance_reducible]

instance FFL.FirstOrder.instReprArithmeticSemiterm {ξ : Type u_1} [ToString ξ] {n : ℕ} : Repr (ArithmeticSemiterm ξ n)

Equations

• FFL.FirstOrder.instReprArithmeticSemiterm = { reprPrec := fun (t : FFL.FirstOrder.ArithmeticSemiterm ξ n) (x : ℕ) => Std.Format.text (FFL.FirstOrder.Semiterm.toStringORing t) }

@[instance_reducible]

instance FFL.FirstOrder.instToStringArithmeticSemiterm {ξ : Type u_1} [ToString ξ] {n : ℕ} : ToString (ArithmeticSemiterm ξ n)

Equations

• FFL.FirstOrder.instToStringArithmeticSemiterm = { toString := FFL.FirstOrder.Semiterm.toStringORing }

def FFL.FirstOrder.Semiformula.toStringORing {ξ : Type u_1} [ToString ξ] {n : ℕ} : ArithmeticSemiformula ξ n → String

Equations

• One or more equations did not get rendered due to their size.
• FFL.FirstOrder.Semiformula.verum.toStringORing = "\\top"
• FFL.FirstOrder.Semiformula.falsum.toStringORing = "\\bot"
• (FFL.FirstOrder.Semiformula.rel FFL.FirstOrder.Language.ORing.Rel.eq v).toStringORing = (v 0).toStringORing ++ " = " ++ (v 1).toStringORing
• (FFL.FirstOrder.Semiformula.rel FFL.FirstOrder.Language.ORing.Rel.lt v).toStringORing = (v 0).toStringORing ++ " < " ++ (v 1).toStringORing
• (FFL.FirstOrder.Semiformula.nrel FFL.FirstOrder.Language.ORing.Rel.eq v).toStringORing = (v 0).toStringORing ++ " \\not = " ++ (v 1).toStringORing
• (FFL.FirstOrder.Semiformula.nrel FFL.FirstOrder.Language.ORing.Rel.lt v).toStringORing = (v 0).toStringORing ++ " \\not < " ++ (v 1).toStringORing
• (FFL.FirstOrder.Semiformula.and φ ψ).toStringORing = "[" ++ FFL.FirstOrder.Semiformula.toStringORing φ ++ "]" ++ " \\land " ++ "[" ++ FFL.FirstOrder.Semiformula.toStringORing ψ ++ "]"
• (FFL.FirstOrder.Semiformula.or φ ψ).toStringORing = "[" ++ FFL.FirstOrder.Semiformula.toStringORing φ ++ "]" ++ " \\lor " ++ "[" ++ FFL.FirstOrder.Semiformula.toStringORing ψ ++ "]"
• (FFL.FirstOrder.Semiformula.all φ).toStringORing = "(\\forall x_{" ++ toString x✝ ++ "}) " ++ "[" ++ FFL.FirstOrder.Semiformula.toStringORing φ ++ "]"
• (FFL.FirstOrder.Semiformula.exs φ).toStringORing = "(\\exists x_{" ++ toString x✝ ++ "}) " ++ "[" ++ FFL.FirstOrder.Semiformula.toStringORing φ ++ "]"

@[instance_reducible]

instance FFL.FirstOrder.instReprArithmeticSemiformula {ξ : Type u_1} [ToString ξ] {n : ℕ} : Repr (ArithmeticSemiformula ξ n)

Equations

• FFL.FirstOrder.instReprArithmeticSemiformula = { reprPrec := fun (φ : FFL.FirstOrder.ArithmeticSemiformula ξ n) (x : ℕ) => Std.Format.text (FFL.FirstOrder.Semiformula.toStringORing φ) }

@[instance_reducible]

instance FFL.FirstOrder.instToStringArithmeticSemiformula {ξ : Type u_1} [ToString ξ] {n : ℕ} : ToString (ArithmeticSemiformula ξ n)

Equations

• FFL.FirstOrder.instToStringArithmeticSemiformula = { toString := FFL.FirstOrder.Semiformula.toStringORing }

@[instance_reducible]

instance FFL.FirstOrder.Arithmetic.instGödelNumberORing {α : Type u_1} [Encodable α] : Semiterm.Operator.GödelNumber ℒₒᵣ α

Equations

• FFL.FirstOrder.Arithmetic.instGödelNumberORing = FFL.FirstOrder.Semiterm.Operator.GödelNumber.ofEncodable

theorem FFL.FirstOrder.Arithmetic.gödelNumber_def {α : Type u_1} [Encodable α] (a : α) : Semiterm.Operator.GödelNumber.gödelNumber a = Semiterm.Operator.encode ℒₒᵣ a

theorem FFL.FirstOrder.Arithmetic.gödelNumber'_def {α : Type u_2} [Encodable α] {ξ : Type u_1} {n : ℕ} (a : α) : ⌜a⌝ = ↑(Semiterm.Operator.encode ℒₒᵣ a)

theorem FFL.FirstOrder.Arithmetic.gödelNumber'_eq_coe_encode {α : Type u_2} [Encodable α] {ξ : Type u_1} {n : ℕ} (a : α) : ⌜a⌝ = ↑(Encodable.encode a)

@[simp]

theorem FFL.FirstOrder.Arithmetic.encode_encode_eq {α : Type u_1} [Encodable α] (a : α) : Semiterm.Operator.GödelNumber.gödelNumber (Encodable.encode a) = Semiterm.Operator.GödelNumber.gödelNumber a

@[simp]

theorem FFL.FirstOrder.Arithmetic.rew_gödelNumber' {α : Type u_3} [Encodable α] {ξ₁ : Type u_1} {n₁ : ℕ} {ξ₂ : Type u_2} {n₂ : ℕ} (ω : Rew ℒₒᵣ ξ₁ n₁ ξ₂ n₂) (a : α) : ω ⌜a⌝ = ⌜a⌝

Semantics of arithmetic

class FFL.FirstOrder.Tarski.Structure.ORing (L : Language) [L.ORing] (M : Type w) [ORingStructure M] [Structure L M] extends FFL.FirstOrder.Tarski.Structure.Zero L M, FFL.FirstOrder.Tarski.Structure.One L M, FFL.FirstOrder.Tarski.Structure.Add L M, FFL.FirstOrder.Tarski.Structure.Mul L M, FFL.FirstOrder.Tarski.Structure.Eq L M, FFL.FirstOrder.Tarski.Structure.LT L M : Prop

• zero : Semiterm.Operator.val ![] op(0) = 0
• one : Semiterm.Operator.val ![] op(1) = 1
• add (a b : M) : Semiterm.Operator.val ![a, b] op(+) = a + b
• mul (a b : M) : Semiterm.Operator.val ![a, b] op(*) = a * b
• eq (a b : M) : Semiformula.Operator.val ![a, b] op(=) ↔ a = b
• lt (a b : M) : Semiformula.Operator.val ![a, b] op(<) ↔ a < b

@[simp]

theorem FFL.FirstOrder.Tarski.Structure.numeral_eq_numeral {L : Language} [Semiterm.Operator.Zero L] [Semiterm.Operator.One L] [Semiterm.Operator.Add L] {M : Type u} [ORingStructure M] [Structure L M] [Structure.Zero L M] [Structure.One L M] [Structure.Add L M] (z : ℕ) : Semiterm.Operator.val ![] (Semiterm.Operator.numeral L z) = ORingStructure.numeral z

def FFL.FirstOrder.Semiformula.ballLTSucc {L : Language} [L.LT] [L.Zero] [L.One] [L.Add] {ξ : Type u_2} {n : ℕ} (t : Semiterm L ξ n) (φ : Semiformula L ξ (n + 1)) : Semiformula L ξ n

Equations

• FFL.FirstOrder.Semiformula.ballLTSucc t φ = FFL.FirstOrder.Semiformula.ballLT (‘(!!t + 1)’) φ

def FFL.FirstOrder.Semiformula.bexsLTSucc {L : Language} [L.LT] [L.Zero] [L.One] [L.Add] {ξ : Type u_2} {n : ℕ} (t : Semiterm L ξ n) (φ : Semiformula L ξ (n + 1)) : Semiformula L ξ n

Equations

• FFL.FirstOrder.Semiformula.bexsLTSucc t φ = FFL.FirstOrder.Semiformula.bexsLT (‘(!!t + 1)’) φ

theorem FFL.FirstOrder.Semiformula.eval_ballLTSucc {L : Language} [L.LT] [L.Zero] [L.One] [L.Add] {M : Type u_1} {s : Tarski.Structure L M} [LT M] [One M] [Add M] [Tarski.Structure.LT L M] [Tarski.Structure.One L M] [Tarski.Structure.Add L M] {ξ : Type u_2} {n : ℕ} {φ : Semiformula L ξ (n + 1)} {t : Semiterm L ξ n} {fv : Fin n → M} {bv : ξ → M} : (Eval fv bv) (ballLTSucc t φ) ↔ ∀ x < Semiterm.val fv bv t + 1, (Eval (x :> fv) bv) φ

theorem FFL.FirstOrder.Semiformula.eval_bexsLTSucc {L : Language} [L.LT] [L.Zero] [L.One] [L.Add] {M : Type u_1} {s : Tarski.Structure L M} [LT M] [One M] [Add M] [Tarski.Structure.LT L M] [Tarski.Structure.One L M] [Tarski.Structure.Add L M] {ξ : Type u_2} {n : ℕ} {φ : Semiformula L ξ (n + 1)} {t : Semiterm L ξ n} {fv : Fin n → M} {bv : ξ → M} : (Eval fv bv) (bexsLTSucc t φ) ↔ ∃ x < Semiterm.val fv bv t + 1, (Eval (x :> fv) bv) φ

def FFL.FirstOrder.BinderNotation.«first_order_formula∀_<⁺_,_» : Lean.ParserDescr

Equations

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

def FFL.FirstOrder.BinderNotation.«first_order_formula∃_<⁺_,_» : Lean.ParserDescr

Equations

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