Language of first-order logic

This file defines the language of first-order logic.

• LO.FirstOrder.Language.empty is the empty language.
• LO.FirstOrder.Language.constant C is a language with only constants of the element C.
• LO.FirstOrder.Language.oRing, ℒₒᵣ is the language of ordered ring.

structure LO.FirstOrder.Language : Type (u + 1)

• Func : ℕ → Type u
• Rel : ℕ → Type u

class LO.FirstOrder.Language.IsRelational (L : LO.FirstOrder.Language) : Prop

• func_empty : ∀ (k : ℕ), IsEmpty (L.Func (k + 1))

class LO.FirstOrder.Language.IsConstant (L : LO.FirstOrder.Language) extends L.IsRelational : Prop

• func_empty : ∀ (k : ℕ), IsEmpty (L.Func (k + 1))
• rel_empty : ∀ (k : ℕ), IsEmpty (L.Rel k)

class LO.FirstOrder.Language.ConstantInhabited (L : LO.FirstOrder.Language) extends Inhabited (L.Func 0) : Type u_1

• default : L.Func 0

instance LO.FirstOrder.Language.instInhabitedFuncOfNatNatOfConstantInhabited {L : LO.FirstOrder.Language} [L.ConstantInhabited] : Inhabited (L.Func 0)

Equations

• LO.FirstOrder.Language.instInhabitedFuncOfNatNatOfConstantInhabited = inferInstance

def LO.FirstOrder.Language.empty : LO.FirstOrder.Language

Equations

• LO.FirstOrder.Language.empty = { Func := fun (x : ℕ) => PEmpty.{?u.5 + 1} , Rel := fun (x : ℕ) => PEmpty.{?u.5 + 1} }

instance LO.FirstOrder.Language.instInhabited : Inhabited LO.FirstOrder.Language

Equations

• LO.FirstOrder.Language.instInhabited = { default := LO.FirstOrder.Language.empty }

inductive LO.FirstOrder.Language.GraphFunc : ℕ → Type

• start: LO.FirstOrder.Language.GraphFunc 0
• terminal: LO.FirstOrder.Language.GraphFunc 0

inductive LO.FirstOrder.Language.GraphRel : ℕ → Type

• equal: LO.FirstOrder.Language.GraphRel 2
• le: LO.FirstOrder.Language.GraphRel 2

def LO.FirstOrder.Language.graph : LO.FirstOrder.Language

Equations

• LO.FirstOrder.Language.graph = { Func := LO.FirstOrder.Language.GraphFunc, Rel := LO.FirstOrder.Language.GraphRel }

inductive LO.FirstOrder.Language.BinaryRel : ℕ → Type

• isone: LO.FirstOrder.Language.BinaryRel 1
• equal: LO.FirstOrder.Language.BinaryRel 2
• le: LO.FirstOrder.Language.BinaryRel 2

def LO.FirstOrder.Language.binary : LO.FirstOrder.Language

Equations

• LO.FirstOrder.Language.binary = { Func := fun (x : ℕ) => Empty, Rel := LO.FirstOrder.Language.BinaryRel }

inductive LO.FirstOrder.Language.EqRel : ℕ → Type

• equal: LO.FirstOrder.Language.EqRel 2

@[reducible]

def LO.FirstOrder.Language.equal : LO.FirstOrder.Language

Equations

• LO.FirstOrder.Language.equal = { Func := fun (x : ℕ) => Empty, Rel := LO.FirstOrder.Language.EqRel }

instance LO.FirstOrder.Language.instToStringFuncEqual (k : ℕ) : ToString (LO.FirstOrder.Language.equal.Func k)

Equations

• LO.FirstOrder.Language.instToStringFuncEqual k = { toString := fun (x : LO.FirstOrder.Language.equal.Func k) => "" }

instance LO.FirstOrder.Language.instToStringRelEqual (k : ℕ) : ToString (LO.FirstOrder.Language.equal.Rel k)

Equations

• LO.FirstOrder.Language.instToStringRelEqual k = { toString := fun (x : LO.FirstOrder.Language.equal.Rel k) => "\\mathrm{Eq}" }

instance LO.FirstOrder.Language.instDecidableEqFuncEqual (k : ℕ) : DecidableEq (LO.FirstOrder.Language.equal.Func k)

Equations

• LO.FirstOrder.Language.instDecidableEqFuncEqual k a b = Empty.casesOn (fun (x : LO.FirstOrder.Language.equal.Func k) => Decidable (x = b)) a

instance LO.FirstOrder.Language.instDecidableEqRelEqual (k : ℕ) : DecidableEq (LO.FirstOrder.Language.equal.Rel k)

Equations

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

instance LO.FirstOrder.Language.instEncodableFuncEqual (k : ℕ) : Encodable (LO.FirstOrder.Language.equal.Func k)

Equations

• LO.FirstOrder.Language.instEncodableFuncEqual k = IsEmpty.toEncodable

inductive LO.FirstOrder.Language.ORing.Func : ℕ → Type

• zero: LO.FirstOrder.Language.ORing.Func 0
• one: LO.FirstOrder.Language.ORing.Func 0
• add: LO.FirstOrder.Language.ORing.Func 2
• mul: LO.FirstOrder.Language.ORing.Func 2

inductive LO.FirstOrder.Language.ORing.Rel : ℕ → Type

• eq: LO.FirstOrder.Language.ORing.Rel 2
• lt: LO.FirstOrder.Language.ORing.Rel 2

@[reducible]

def LO.FirstOrder.Language.oRing : LO.FirstOrder.Language

Equations

• ℒₒᵣ = { Func := LO.FirstOrder.Language.ORing.Func, Rel := LO.FirstOrder.Language.ORing.Rel }

def LO.FirstOrder.Language.termℒₒᵣ : Lean.ParserDescr

Equations

• LO.FirstOrder.Language.termℒₒᵣ = Lean.ParserDescr.node `LO.FirstOrder.Language.termℒₒᵣ 1024 (Lean.ParserDescr.symbol "ℒₒᵣ")

instance LO.FirstOrder.Language.ORing.instToStringFuncORing (k : ℕ) : ToString (ℒₒᵣ.Func k)

Equations

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

instance LO.FirstOrder.Language.ORing.instToStringRelORing (k : ℕ) : ToString (ℒₒᵣ.Rel k)

Equations

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

instance LO.FirstOrder.Language.ORing.instDecidableEqFuncORing (k : ℕ) : DecidableEq (ℒₒᵣ.Func k)

Equations

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

instance LO.FirstOrder.Language.ORing.instDecidableEqRelORing (k : ℕ) : DecidableEq (ℒₒᵣ.Rel k)

Equations

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

instance LO.FirstOrder.Language.ORing.instEncodableFuncORing (k : ℕ) : Encodable (ℒₒᵣ.Func k)

Equations

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

instance LO.FirstOrder.Language.ORing.Func1IsEmpty : IsEmpty (ℒₒᵣ.Func 1)

Equations

• LO.FirstOrder.Language.ORing.Func1IsEmpty = ⋯

instance LO.FirstOrder.Language.ORing.FuncGe3IsEmpty (k : ℕ) : k ≥ 3 → IsEmpty (ℒₒᵣ.Func k)

Equations

• ⋯ = ⋯

instance LO.FirstOrder.Language.ORing.instEncodableRelORing (k : ℕ) : Encodable (ℒₒᵣ.Rel k)

Equations

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

inductive LO.FirstOrder.Language.Constant.Func (C : Type u_1) : ℕ → Type u_1

• const: {C : Type u_1} → C → LO.FirstOrder.Language.Constant.Func C 0

def LO.FirstOrder.Language.constant (C : Type u_1) : LO.FirstOrder.Language

Equations

• LO.FirstOrder.Language.constant C = { Func := LO.FirstOrder.Language.Constant.Func C, Rel := fun (x : ℕ) => PEmpty.{?u.11 + 1} }

instance LO.FirstOrder.Language.instCoeFuncConstantOfNatNat (C : Type u_1) : Coe C ((LO.FirstOrder.Language.constant C).Func 0)

Equations

• LO.FirstOrder.Language.instCoeFuncConstantOfNatNat C = { coe := LO.FirstOrder.Language.Constant.Func.const }

instance LO.FirstOrder.Language.instIsConstantConstant (C : Type u_1) : (LO.FirstOrder.Language.constant C).IsConstant

Equations

• ⋯ = ⋯

@[reducible, inline]

abbrev LO.FirstOrder.Language.unit : LO.FirstOrder.Language

Equations

• LO.FirstOrder.Language.unit = LO.FirstOrder.Language.constant PUnit.{?u.3 + 1}

def LO.FirstOrder.Language.ofFunc (F : ℕ → Type v) : LO.FirstOrder.Language

Equations

• LO.FirstOrder.Language.ofFunc F = { Func := F, Rel := fun (x : ℕ) => PEmpty.{?u.12 + 1} }

def LO.FirstOrder.Language.add (L₁ : LO.FirstOrder.Language) (L₂ : LO.FirstOrder.Language) : LO.FirstOrder.Language

Equations

• L₁.add L₂ = { Func := fun (k : ℕ) => L₁.Func k ⊕ L₂.Func k, Rel := fun (k : ℕ) => L₁.Rel k ⊕ L₂.Rel k }

instance LO.FirstOrder.Language.instAdd : Add LO.FirstOrder.Language

Equations

• LO.FirstOrder.Language.instAdd = { add := LO.FirstOrder.Language.add }

def LO.FirstOrder.Language.sigma {ι : Type u_1} (L : ι → LO.FirstOrder.Language) : LO.FirstOrder.Language

Equations

• LO.FirstOrder.Language.sigma L = { Func := fun (k : ℕ) => (i : ι) × (L i).Func k, Rel := fun (k : ℕ) => (i : ι) × (L i).Rel k }

class LO.FirstOrder.Language.Eq (L : LO.FirstOrder.Language) : Type u_1

• eq : L.Rel 2

class LO.FirstOrder.Language.LT (L : LO.FirstOrder.Language) : Type u_1

• lt : L.Rel 2

class LO.FirstOrder.Language.Zero (L : LO.FirstOrder.Language) : Type u_1

• zero : L.Func 0

class LO.FirstOrder.Language.One (L : LO.FirstOrder.Language) : Type u_1

• one : L.Func 0

class LO.FirstOrder.Language.Add (L : LO.FirstOrder.Language) : Type u_1

• add : L.Func 2

class LO.FirstOrder.Language.Mul (L : LO.FirstOrder.Language) : Type u_1

• mul : L.Func 2

class LO.FirstOrder.Language.Pow (L : LO.FirstOrder.Language) : Type u_1

• pow : L.Func 2

class LO.FirstOrder.Language.Exp (L : LO.FirstOrder.Language) : Type u_1

• exp : L.Func 1

class LO.FirstOrder.Language.Pairing (L : LO.FirstOrder.Language) : Type u_1

• pair : L.Func 2

class LO.FirstOrder.Language.Star (L : LO.FirstOrder.Language) : Type u_1

• star : L.Func 0

class LO.FirstOrder.Language.ORing (L : LO.FirstOrder.Language) extends L.Eq, L.LT, L.Zero, L.One, L.Add, L.Mul : Type u_1

• eq : L.Rel 2
• lt : L.Rel 2
• zero : L.Func 0
• one : L.Func 0
• add : L.Func 2
• mul : L.Func 2

instance LO.FirstOrder.Language.instORingORing : ℒₒᵣ.ORing

Equations

• LO.FirstOrder.Language.instORingORing = LO.FirstOrder.Language.ORing.mk

instance LO.FirstOrder.Language.instConstantInhabitedORing : ℒₒᵣ.ConstantInhabited

Equations

• LO.FirstOrder.Language.instConstantInhabitedORing = LO.FirstOrder.Language.ConstantInhabited.mk

instance LO.FirstOrder.Language.instStarUnit : LO.FirstOrder.Language.unit.Star

Equations

• LO.FirstOrder.Language.instStarUnit = { star := LO.FirstOrder.Language.Constant.Func.const () }

instance LO.FirstOrder.Language.instStarAdd (L : LO.FirstOrder.Language) (S : LO.FirstOrder.Language) [S.Star] : (L.add S).Star

Equations

• L.instStarAdd S = { star := Sum.inr LO.FirstOrder.Language.Star.star }

instance LO.FirstOrder.Language.instZeroAdd (L : LO.FirstOrder.Language) (S : LO.FirstOrder.Language) [L.Zero] : (L.add S).Zero

Equations

• L.instZeroAdd S = { zero := Sum.inl LO.FirstOrder.Language.Zero.zero }

instance LO.FirstOrder.Language.instOneAdd (L : LO.FirstOrder.Language) (S : LO.FirstOrder.Language) [L.One] : (L.add S).One

Equations

• L.instOneAdd S = { one := Sum.inl LO.FirstOrder.Language.One.one }

instance LO.FirstOrder.Language.instAddAdd (L : LO.FirstOrder.Language) (S : LO.FirstOrder.Language) [L.Add] : (L.add S).Add

Equations

• L.instAddAdd S = { add := Sum.inl LO.FirstOrder.Language.Add.add }

instance LO.FirstOrder.Language.instMulAdd (L : LO.FirstOrder.Language) (S : LO.FirstOrder.Language) [L.Mul] : (L.add S).Mul

Equations

• L.instMulAdd S = { mul := Sum.inl LO.FirstOrder.Language.Mul.mul }

instance LO.FirstOrder.Language.instEqAdd (L : LO.FirstOrder.Language) (S : LO.FirstOrder.Language) [L.Eq] : (L.add S).Eq

Equations

• L.instEqAdd S = { eq := Sum.inl LO.FirstOrder.Language.Eq.eq }

instance LO.FirstOrder.Language.instLTAdd (L : LO.FirstOrder.Language) (S : LO.FirstOrder.Language) [L.LT] : (L.add S).LT

Equations

• L.instLTAdd S = { lt := Sum.inl LO.FirstOrder.Language.LT.lt }

structure LO.FirstOrder.Language.Hom (L₁ : LO.FirstOrder.Language) (L₂ : LO.FirstOrder.Language) : Type (max u_1 u_2)

• func : {k : ℕ} → L₁.Func k → L₂.Func k
• rel : {k : ℕ} → L₁.Rel k → L₂.Rel k

theorem LO.FirstOrder.Language.Hom.ext {L₁ : LO.FirstOrder.Language} {L₂ : LO.FirstOrder.Language} {x y : L₁.Hom L₂} (func : @LO.FirstOrder.Language.Hom.func L₁ L₂ x = @LO.FirstOrder.Language.Hom.func L₁ L₂ y) (rel : @LO.FirstOrder.Language.Hom.rel L₁ L₂ x = @LO.FirstOrder.Language.Hom.rel L₁ L₂ y) : x = y

def LO.FirstOrder.«term_→ᵥ_» : Lean.TrailingParserDescr

Equations

• LO.FirstOrder.«term_→ᵥ_» = Lean.ParserDescr.trailingNode `LO.FirstOrder.«term_→ᵥ_» 25 26 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " →ᵥ ") (Lean.ParserDescr.cat `term 26))

def LO.FirstOrder.Language.Hom.id (L : LO.FirstOrder.Language) : L.Hom L

Equations

• LO.FirstOrder.Language.Hom.id L = { func := fun {k : ℕ} => id, rel := fun {k : ℕ} => id }

def LO.FirstOrder.Language.Hom.comp {L₁ : LO.FirstOrder.Language} {L₂ : LO.FirstOrder.Language} {L₃ : LO.FirstOrder.Language} (Ψ : L₂.Hom L₃) (Φ : L₁.Hom L₂) : L₁.Hom L₃

Equations

• Ψ.comp Φ = { func := fun {k : ℕ} => Ψ.func ∘ Φ.func, rel := fun {k : ℕ} => Ψ.rel ∘ Φ.rel }

def LO.FirstOrder.Language.Hom.add₁ (L₁ : LO.FirstOrder.Language) (L₂ : LO.FirstOrder.Language) : L₁.Hom (L₁.add L₂)

Equations

• LO.FirstOrder.Language.Hom.add₁ L₁ L₂ = { func := fun {k : ℕ} => Sum.inl, rel := fun {k : ℕ} => Sum.inl }

def LO.FirstOrder.Language.Hom.add₂ (L₁ : LO.FirstOrder.Language) (L₂ : LO.FirstOrder.Language) : L₂.Hom (L₁.add L₂)

Equations

• LO.FirstOrder.Language.Hom.add₂ L₁ L₂ = { func := fun {k : ℕ} => Sum.inr, rel := fun {k : ℕ} => Sum.inr }

theorem LO.FirstOrder.Language.Hom.func_add₁ {k : ℕ} (L₁ : LO.FirstOrder.Language) (L₂ : LO.FirstOrder.Language) (f : L₁.Func k) : (LO.FirstOrder.Language.Hom.add₁ L₁ L₂).func f = Sum.inl f

theorem LO.FirstOrder.Language.Hom.rel_add₁ {k : ℕ} (L₁ : LO.FirstOrder.Language) (L₂ : LO.FirstOrder.Language) (r : L₁.Rel k) : (LO.FirstOrder.Language.Hom.add₁ L₁ L₂).rel r = Sum.inl r

theorem LO.FirstOrder.Language.Hom.func_add₂ {k : ℕ} (L₁ : LO.FirstOrder.Language) (L₂ : LO.FirstOrder.Language) (f : L₂.Func k) : (LO.FirstOrder.Language.Hom.add₂ L₁ L₂).func f = Sum.inr f

theorem LO.FirstOrder.Language.Hom.rel_add₂ {k : ℕ} (L₁ : LO.FirstOrder.Language) (L₂ : LO.FirstOrder.Language) (r : L₂.Rel k) : (LO.FirstOrder.Language.Hom.add₂ L₁ L₂).rel r = Sum.inr r

@[simp]

theorem LO.FirstOrder.Language.Hom.add₂_star (L₁ : LO.FirstOrder.Language) (L₂ : LO.FirstOrder.Language) [L₂.Star] : (LO.FirstOrder.Language.Hom.add₂ L₁ L₂).func LO.FirstOrder.Language.Star.star = LO.FirstOrder.Language.Star.star

@[simp]

theorem LO.FirstOrder.Language.Hom.add₁_zero (L₁ : LO.FirstOrder.Language) (L₂ : LO.FirstOrder.Language) [L₁.Zero] : (LO.FirstOrder.Language.Hom.add₁ L₁ L₂).func LO.FirstOrder.Language.Zero.zero = LO.FirstOrder.Language.Zero.zero

@[simp]

theorem LO.FirstOrder.Language.Hom.add₁_one (L₁ : LO.FirstOrder.Language) (L₂ : LO.FirstOrder.Language) [L₁.One] : (LO.FirstOrder.Language.Hom.add₁ L₁ L₂).func LO.FirstOrder.Language.One.one = LO.FirstOrder.Language.One.one

@[simp]

theorem LO.FirstOrder.Language.Hom.add₁_add (L₁ : LO.FirstOrder.Language) (L₂ : LO.FirstOrder.Language) [L₁.Add] : (LO.FirstOrder.Language.Hom.add₁ L₁ L₂).func LO.FirstOrder.Language.Add.add = LO.FirstOrder.Language.Add.add

@[simp]

theorem LO.FirstOrder.Language.Hom.add₁_mul (L₁ : LO.FirstOrder.Language) (L₂ : LO.FirstOrder.Language) [L₁.Mul] : (LO.FirstOrder.Language.Hom.add₁ L₁ L₂).func LO.FirstOrder.Language.Mul.mul = LO.FirstOrder.Language.Mul.mul

@[simp]

theorem LO.FirstOrder.Language.Hom.add₁_eq (L₁ : LO.FirstOrder.Language) (L₂ : LO.FirstOrder.Language) [L₁.Eq] : (LO.FirstOrder.Language.Hom.add₁ L₁ L₂).rel LO.FirstOrder.Language.Eq.eq = LO.FirstOrder.Language.Eq.eq

@[simp]

theorem LO.FirstOrder.Language.Hom.add₁_lt (L₁ : LO.FirstOrder.Language) (L₂ : LO.FirstOrder.Language) [L₁.LT] : (LO.FirstOrder.Language.Hom.add₁ L₁ L₂).rel LO.FirstOrder.Language.LT.lt = LO.FirstOrder.Language.LT.lt

def LO.FirstOrder.Language.Hom.sigma {ι : Type u_1} (L : ι → LO.FirstOrder.Language) (i : ι) : (L i).Hom (LO.FirstOrder.Language.sigma L)

Equations

• LO.FirstOrder.Language.Hom.sigma L i = { func := fun {k : ℕ} (f : (L i).Func k) => ⟨i, f⟩, rel := fun {k : ℕ} (r : (L i).Rel k) => ⟨i, r⟩ }

theorem LO.FirstOrder.Language.Hom.func_sigma {ι : Type u_1} {k : ℕ} (L : ι → LO.FirstOrder.Language) (i : ι) (f : (L i).Func k) : (LO.FirstOrder.Language.Hom.sigma L i).func f = ⟨i, f⟩

theorem LO.FirstOrder.Language.Hom.rel_sigma {ι : Type u_1} {k : ℕ} (L : ι → LO.FirstOrder.Language) (i : ι) (r : (L i).Rel k) : (LO.FirstOrder.Language.Hom.sigma L i).rel r = ⟨i, r⟩

def LO.FirstOrder.Language.ORing.embedding (L : LO.FirstOrder.Language) [L.ORing] : ℒₒᵣ.Hom L

Equations

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

class LO.FirstOrder.Language.DecidableEq (L : LO.FirstOrder.Language) : Type u_1

• func : (k : ℕ) → DecidableEq (L.Func k)
• rel : (k : ℕ) → DecidableEq (L.Rel k)

instance LO.FirstOrder.instDecidableEqOfFuncOfDecidableEqRel (L : LO.FirstOrder.Language) [(k : ℕ) → DecidableEq (L.Func k)] [(k : ℕ) → DecidableEq (L.Rel k)] : L.DecidableEq

Equations

• LO.FirstOrder.instDecidableEqOfFuncOfDecidableEqRel L = { func := fun (x : ℕ) => inferInstance, rel := fun (x : ℕ) => inferInstance }

instance LO.FirstOrder.instDecidableEqFuncOfDecidableEq (L : LO.FirstOrder.Language) [L.DecidableEq] (k : ℕ) : DecidableEq (L.Func k)

Equations

• LO.FirstOrder.instDecidableEqFuncOfDecidableEq L k = LO.FirstOrder.Language.DecidableEq.func k

instance LO.FirstOrder.instDecidableEqRelOfDecidableEq (L : LO.FirstOrder.Language) [L.DecidableEq] (k : ℕ) : DecidableEq (L.Rel k)

Equations

• LO.FirstOrder.instDecidableEqRelOfDecidableEq L k = LO.FirstOrder.Language.DecidableEq.rel k

instance LO.FirstOrder.instDecidableEqRelOfDecidableEq_1 (L : LO.FirstOrder.Language) [L.DecidableEq] (k : ℕ) : DecidableEq (L.Rel k)

Equations

• LO.FirstOrder.instDecidableEqRelOfDecidableEq_1 L k = LO.FirstOrder.Language.DecidableEq.rel k