Bundled First-Order Structures

This file bundles types together with their first-order structure.

Main Definitions

• FirstOrder.Language.Theory.ModelType is the type of nonempty models of a particular theory.
• FirstOrder.Language.equivSetoid is the isomorphism equivalence relation on bundled structures.

TODO

• Define category structures on bundled structures and models.

instance CategoryTheory.Bundled.structure {L : FirstOrder.Language} (M : Bundled L.Structure) : L.Structure ↑M

Equations

• M.structure = M.str

def Equiv.bundledInduced (L : FirstOrder.Language) {M : Type w} [L.Structure M] {N : Type w'} (g : M ≃ N) : CategoryTheory.Bundled L.Structure

A type bundled with the structure induced by an equivalence.

Equations

• Equiv.bundledInduced L g = { α := N, str := g.inducedStructure }

@[simp]

theorem Equiv.bundledInduced_str (L : FirstOrder.Language) {M : Type w} [L.Structure M] {N : Type w'} (g : M ≃ N) : (bundledInduced L g).str = g.inducedStructure

@[simp]

theorem Equiv.bundledInduced_α (L : FirstOrder.Language) {M : Type w} [L.Structure M] {N : Type w'} (g : M ≃ N) : ↑(bundledInduced L g) = N

def Equiv.bundledInducedEquiv (L : FirstOrder.Language) {M : Type w} [L.Structure M] {N : Type w'} (g : M ≃ N) : L.Equiv M ↑(bundledInduced L g)

An equivalence of types as a first-order equivalence to the bundled structure on the codomain.

Equations

• Equiv.bundledInducedEquiv L g = g.inducedStructureEquiv

instance FirstOrder.Language.equivSetoid {L : Language} : Setoid (CategoryTheory.Bundled L.Structure)

The equivalence relation on bundled L.Structures indicating that they are isomorphic.

Equations

• FirstOrder.Language.equivSetoid = { r := fun (M N : CategoryTheory.Bundled L.Structure) => Nonempty (L.Equiv ↑M ↑N), iseqv := ⋯ }

structure FirstOrder.Language.Theory.ModelType {L : Language} (T : L.Theory) : Type (max (max u v) (w + 1))

The type of nonempty models of a first-order theory.

• Carrier : Type w

  The underlying type for the models

• struc : L.Structure ↑self
• is_model : ↑self ⊨ T
• nonempty' : Nonempty ↑self

instance FirstOrder.Language.Theory.ModelType.instCoeSort {L : Language} (T : L.Theory) : CoeSort T.ModelType (Type w)

Equations

• FirstOrder.Language.Theory.ModelType.instCoeSort T = { coe := FirstOrder.Language.Theory.ModelType.Carrier }

def FirstOrder.Language.Theory.ModelType.of {L : Language} (T : L.Theory) (M : Type w) [L.Structure M] [M ⊨ T] [Nonempty M] : T.ModelType

The object in the category of R-algebras associated to a type equipped with the appropriate typeclasses.

Equations

• FirstOrder.Language.Theory.ModelType.of T M = { Carrier := M, struc := inst✝², is_model := inst✝¹, nonempty' := inst✝ }

@[simp]

theorem FirstOrder.Language.Theory.ModelType.coe_of {L : Language} (T : L.Theory) (M : Type w) [L.Structure M] [M ⊨ T] [Nonempty M] : ↑(of T M) = M

instance FirstOrder.Language.Theory.ModelType.instNonempty {L : Language} (T : L.Theory) (M : T.ModelType) : Nonempty ↑M

instance FirstOrder.Language.Theory.ModelType.instInhabited {L : Language} : Inhabited ∅.ModelType

Equations

• FirstOrder.Language.Theory.ModelType.instInhabited = { default := FirstOrder.Language.Theory.ModelType.of ∅ PUnit.{?u.13 + 1} }

def FirstOrder.Language.Theory.ModelType.equivInduced {L : Language} {T : L.Theory} {M : T.ModelType} {N : Type w'} (e : ↑M ≃ N) : T.ModelType

Maps a bundled model along a bijection.

Equations

• FirstOrder.Language.Theory.ModelType.equivInduced e = { Carrier := N, struc := e.inducedStructure, is_model := ⋯, nonempty' := ⋯ }

instance FirstOrder.Language.Theory.ModelType.of_small {L : Language} {T : L.Theory} (M : Type w) [Nonempty M] [L.Structure M] [M ⊨ T] [h : Small.{w', w} M] : Small.{w', w} ↑(of T M)

noncomputable def FirstOrder.Language.Theory.ModelType.shrink {L : Language} {T : L.Theory} (M : T.ModelType) [Small.{w', w} ↑M] : T.ModelType

Shrinks a small model to a particular universe.

Equations

• M.shrink = FirstOrder.Language.Theory.ModelType.equivInduced (equivShrink ↑M)

def FirstOrder.Language.Theory.ModelType.ulift {L : Language} {T : L.Theory} (M : T.ModelType) : T.ModelType

Lifts a model to a particular universe.

Equations

• M.ulift = FirstOrder.Language.Theory.ModelType.equivInduced Equiv.ulift.symm

def FirstOrder.Language.Theory.ModelType.reduct {L : Language} {T : L.Theory} {L' : Language} (φ : L →ᴸ L') (M : (φ.onTheory T).ModelType) : T.ModelType

The reduct of any model of φ.onTheory T is a model of T.

Equations

• FirstOrder.Language.Theory.ModelType.reduct φ M = { Carrier := ↑M, struc := φ.reduct ↑M, is_model := ⋯, nonempty' := ⋯ }

@[simp]

theorem FirstOrder.Language.Theory.ModelType.reduct_struc {L : Language} {T : L.Theory} {L' : Language} (φ : L →ᴸ L') (M : (φ.onTheory T).ModelType) : (reduct φ M).struc = φ.reduct ↑M

@[simp]

theorem FirstOrder.Language.Theory.ModelType.reduct_Carrier {L : Language} {T : L.Theory} {L' : Language} (φ : L →ᴸ L') (M : (φ.onTheory T).ModelType) : ↑(reduct φ M) = ↑M

noncomputable def FirstOrder.Language.Theory.ModelType.defaultExpansion {L : Language} {T : L.Theory} {L' : Language} {φ : L →ᴸ L'} (h : φ.Injective) [(n : ℕ) → (f : L'.Functions n) → Decidable (f ∈ Set.range fun (f : L.Functions n) => φ.onFunction f)] [(n : ℕ) → (r : L'.Relations n) → Decidable (r ∈ Set.range fun (r : L.Relations n) => φ.onRelation r)] (M : T.ModelType) [Inhabited ↑M] : (φ.onTheory T).ModelType

When φ is injective, defaultExpansion expands a model of T to a model of φ.onTheory T arbitrarily.

Equations

• FirstOrder.Language.Theory.ModelType.defaultExpansion h M = { Carrier := ↑M, struc := φ.defaultExpansion ↑M, is_model := ⋯, nonempty' := ⋯ }

@[simp]

theorem FirstOrder.Language.Theory.ModelType.defaultExpansion_Carrier {L : Language} {T : L.Theory} {L' : Language} {φ : L →ᴸ L'} (h : φ.Injective) [(n : ℕ) → (f : L'.Functions n) → Decidable (f ∈ Set.range fun (f : L.Functions n) => φ.onFunction f)] [(n : ℕ) → (r : L'.Relations n) → Decidable (r ∈ Set.range fun (r : L.Relations n) => φ.onRelation r)] (M : T.ModelType) [Inhabited ↑M] : ↑(defaultExpansion h M) = ↑M

@[simp]

theorem FirstOrder.Language.Theory.ModelType.defaultExpansion_struc {L : Language} {T : L.Theory} {L' : Language} {φ : L →ᴸ L'} (h : φ.Injective) [(n : ℕ) → (f : L'.Functions n) → Decidable (f ∈ Set.range fun (f : L.Functions n) => φ.onFunction f)] [(n : ℕ) → (r : L'.Relations n) → Decidable (r ∈ Set.range fun (r : L.Relations n) => φ.onRelation r)] (M : T.ModelType) [Inhabited ↑M] : (defaultExpansion h M).struc = φ.defaultExpansion ↑M

instance FirstOrder.Language.Theory.ModelType.leftStructure {L : Language} {L' : Language} {T : (L.sum L').Theory} (M : T.ModelType) : L.Structure ↑M

Equations

• M.leftStructure = FirstOrder.Language.LHom.sumInl.reduct ↑M

instance FirstOrder.Language.Theory.ModelType.rightStructure {L : Language} {L' : Language} {T : (L.sum L').Theory} (M : T.ModelType) : L'.Structure ↑M

Equations

• M.rightStructure = FirstOrder.Language.LHom.sumInr.reduct ↑M

def FirstOrder.Language.Theory.ModelType.subtheoryModel {L : Language} {T : L.Theory} (M : T.ModelType) {T' : L.Theory} (h : T' ⊆ T) : T'.ModelType

A model of a theory is also a model of any subtheory.

Equations

• M.subtheoryModel h = { Carrier := ↑M, struc := M.struc, is_model := ⋯, nonempty' := ⋯ }

@[simp]

theorem FirstOrder.Language.Theory.ModelType.subtheoryModel_struc {L : Language} {T : L.Theory} (M : T.ModelType) {T' : L.Theory} (h : T' ⊆ T) : (M.subtheoryModel h).struc = M.struc

@[simp]

theorem FirstOrder.Language.Theory.ModelType.subtheoryModel_Carrier {L : Language} {T : L.Theory} (M : T.ModelType) {T' : L.Theory} (h : T' ⊆ T) : ↑(M.subtheoryModel h) = ↑M

instance FirstOrder.Language.Theory.ModelType.subtheoryModel_models {L : Language} {T : L.Theory} (M : T.ModelType) {T' : L.Theory} (h : T' ⊆ T) : ↑(M.subtheoryModel h) ⊨ T

def FirstOrder.Language.Theory.Model.bundled {L : Language} {T : L.Theory} {M : Type w} [LM : L.Structure M] [ne : Nonempty M] (h : M ⊨ T) : T.ModelType

Bundles M ⊨ T as a T.ModelType.

Equations

• h.bundled = FirstOrder.Language.Theory.ModelType.of T M

@[simp]

theorem FirstOrder.Language.Theory.coe_of {L : Language} {T : L.Theory} {M : Type w} [L.Structure M] [Nonempty M] (h : M ⊨ T) : ↑h.bundled = M

def FirstOrder.Language.ElementarilyEquivalent.toModel {L : Language} (T : L.Theory) {M : T.ModelType} {N : Type u_1} [LN : L.Structure N] (h : L.ElementarilyEquivalent (↑M) N) : T.ModelType

A structure that is elementarily equivalent to a model, bundled as a model.

Equations

• FirstOrder.Language.ElementarilyEquivalent.toModel T h = { Carrier := N, struc := LN, is_model := ⋯, nonempty' := ⋯ }

def FirstOrder.Language.ElementarySubstructure.toModel {L : Language} (T : L.Theory) {M : T.ModelType} (S : L.ElementarySubstructure ↑M) : T.ModelType

An elementary substructure of a bundled model as a bundled model.

Equations

• FirstOrder.Language.ElementarySubstructure.toModel T S = FirstOrder.Language.ElementarilyEquivalent.toModel T ⋯

instance FirstOrder.Language.ElementarySubstructure.toModel.instSmall {L : Language} (T : L.Theory) {M : T.ModelType} (S : L.ElementarySubstructure ↑M) [h : Small.{w, x} ↥S] : Small.{w, x} ↑(toModel T S)