Fraïssé Classes and Fraïssé Limits

This file pertains to the ages of countable first-order structures. The age of a structure is the class of all finitely-generated structures that embed into it.

Of particular interest are Fraïssé classes, which are exactly the ages of countable ultrahomogeneous structures. To each is associated a unique (up to nonunique isomorphism) Fraïssé limit - the countable ultrahomogeneous structure with that age.

Main Definitions

• FirstOrder.Language.age is the class of finitely-generated structures that embed into a particular structure.
• A class K is FirstOrder.Language.Hereditary when all finitely-generated structures that embed into structures in K are also in K.
• A class K has FirstOrder.Language.JointEmbedding when for every M, N in K, there is another structure in K into which both M and N embed.
• A class K has FirstOrder.Language.Amalgamation when for any pair of embeddings of a structure M in K into other structures in K, those two structures can be embedded into a fourth structure in K such that the resulting square of embeddings commutes.
• FirstOrder.Language.IsFraisse indicates that a class is nonempty, essentially countable, and satisfies the hereditary, joint embedding, and amalgamation properties.
• FirstOrder.Language.IsFraisseLimit indicates that a structure is a Fraïssé limit for a given class.

Main Results

• We show that the age of any structure is isomorphism-invariant and satisfies the hereditary and joint-embedding properties.
• FirstOrder.Language.age.countable_quotient shows that the age of any countable structure is essentially countable.
• FirstOrder.Language.exists_countable_is_age_of_iff gives necessary and sufficient conditions for a class to be the age of a countable structure in a language with countably many functions.
• FirstOrder.Language.IsFraisseLimit.nonempty_equiv shows that any class which is Fraïssé has at most one Fraïssé limit up to equivalence.
• FirstOrder.Language.empty.isFraisseLimit_of_countable_infinite shows that any countably infinite structure in the empty language is a Fraïssé limit of the class of finite structures.
• FirstOrder.Language.empty.isFraisse_finite shows that the class of finite structures in the empty language is Fraïssé.

Implementation Notes

• Classes of structures are formalized with Set (Bundled L.Structure).
• Some results pertain to countable limit structures, others to countably-generated limit structures. In the case of a language with countably many function symbols, these are equivalent.

References

• W. Hodges, A Shorter Model Theory
• K. Tent, M. Ziegler, A Course in Model Theory

TODO

• Show existence of Fraïssé limits

The Age of a Structure and Fraïssé Classes

def FirstOrder.Language.age (L : Language) (M : Type w) [L.Structure M] : Set (CategoryTheory.Bundled L.Structure)

The age of a structure M is the class of finitely-generated structures that embed into it.

Equations

• L.age M = {N : CategoryTheory.Bundled L.Structure | FirstOrder.Language.Structure.FG L ↑N ∧ Nonempty (L.Embedding (↑N) M)}

def FirstOrder.Language.Hereditary {L : Language} (K : Set (CategoryTheory.Bundled L.Structure)) : Prop

A class K has the hereditary property when all finitely-generated structures that embed into structures in K are also in K.

Equations

• FirstOrder.Language.Hereditary K = ∀ M ∈ K, L.age ↑M ⊆ K

def FirstOrder.Language.JointEmbedding {L : Language} (K : Set (CategoryTheory.Bundled L.Structure)) : Prop

A class K has the joint embedding property when for every M, N in K, there is another structure in K into which both M and N embed.

Equations

• FirstOrder.Language.JointEmbedding K = DirectedOn (fun (M N : CategoryTheory.Bundled L.Structure) => Nonempty (L.Embedding ↑M ↑N)) K

def FirstOrder.Language.Amalgamation {L : Language} (K : Set (CategoryTheory.Bundled L.Structure)) : Prop

A class K has the amalgamation property when for any pair of embeddings of a structure M in K into other structures in K, those two structures can be embedded into a fourth structure in K such that the resulting square of embeddings commutes.

Equations

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

class FirstOrder.Language.IsFraisse {L : Language} (K : Set (CategoryTheory.Bundled L.Structure)) : Prop

A Fraïssé class is a nonempty, essentially countable class of structures satisfying the hereditary, joint embedding, and amalgamation properties.

• is_nonempty : K.Nonempty
• FG (M : CategoryTheory.Bundled L.Structure) : M ∈ K → Structure.FG L ↑M
• is_essentially_countable : (Quotient.mk' '' K).Countable
• hereditary : Hereditary K
• jointEmbedding : JointEmbedding K
• amalgamation : Amalgamation K

theorem FirstOrder.Language.age.is_equiv_invariant (L : Language) (M : Type w) [L.Structure M] (N P : CategoryTheory.Bundled L.Structure) (h : Nonempty (L.Equiv ↑N ↑P)) : N ∈ L.age M ↔ P ∈ L.age M

theorem FirstOrder.Language.Embedding.age_subset_age {L : Language} {M : Type w} [L.Structure M] {N : Type w} [L.Structure N] (MN : L.Embedding M N) : L.age M ⊆ L.age N

theorem FirstOrder.Language.Equiv.age_eq_age {L : Language} {M : Type w} [L.Structure M] {N : Type w} [L.Structure N] (MN : L.Equiv M N) : L.age M = L.age N

theorem FirstOrder.Language.Structure.FG.mem_age_of_equiv {L : Language} {M N : CategoryTheory.Bundled L.Structure} (h : FG L ↑M) (MN : Nonempty (L.Equiv ↑M ↑N)) : N ∈ L.age ↑M

theorem FirstOrder.Language.Hereditary.is_equiv_invariant_of_fg {L : Language} {K : Set (CategoryTheory.Bundled L.Structure)} (h : Hereditary K) (fg : ∀ M ∈ K, Structure.FG L ↑M) (M N : CategoryTheory.Bundled L.Structure) (hn : Nonempty (L.Equiv ↑M ↑N)) : M ∈ K ↔ N ∈ K

theorem FirstOrder.Language.IsFraisse.is_equiv_invariant {L : Language} {K : Set (CategoryTheory.Bundled L.Structure)} [h : IsFraisse K] {M N : CategoryTheory.Bundled L.Structure} (hn : Nonempty (L.Equiv ↑M ↑N)) : M ∈ K ↔ N ∈ K

theorem FirstOrder.Language.age.nonempty {L : Language} (M : Type w) [L.Structure M] : (L.age M).Nonempty

theorem FirstOrder.Language.age.hereditary {L : Language} (M : Type w) [L.Structure M] : Hereditary (L.age M)

theorem FirstOrder.Language.age.jointEmbedding {L : Language} (M : Type w) [L.Structure M] : JointEmbedding (L.age M)

theorem FirstOrder.Language.age.fg_substructure {L : Language} {M : Type w} [L.Structure M] {S : L.Substructure M} (fg : S.FG) : { α := ↥S, str := inferInstance } ∈ L.age M

theorem FirstOrder.Language.age.has_representative_as_substructure {L : Language} (M : Type w) [L.Structure M] (C : Quotient equivSetoid) : C ∈ Quotient.mk' '' L.age M → ∃ (V : { V : L.Substructure M // V.FG }), ⟦{ α := ↥↑V, str := inferInstance }⟧ = C

Any class in the age of a structure has a representative which is a finitely generated substructure.

theorem FirstOrder.Language.age.countable_quotient {L : Language} (M : Type w) [L.Structure M] [h : Countable M] : (Quotient.mk' '' L.age M).Countable

The age of a countable structure is essentially countable (has countably many isomorphism classes).

theorem FirstOrder.Language.age_directLimit {L : Language} {ι : Type w} [Preorder ι] [IsDirected ι fun (x1 x2 : ι) => x1 ≤ x2] [Nonempty ι] (G : ι → Type (max w w')) [(i : ι) → L.Structure (G i)] (f : (i j : ι) → i ≤ j → L.Embedding (G i) (G j)) [DirectedSystem G fun (i j : ι) (h : i ≤ j) => ⇑(f i j h)] : L.age (DirectLimit G f) = ⋃ (i : ι), L.age (G i)

The age of a direct limit of structures is the union of the ages of the structures.

theorem FirstOrder.Language.exists_cg_is_age_of {L : Language} {K : Set (CategoryTheory.Bundled L.Structure)} (hn : K.Nonempty) (hc : (Quotient.mk' '' K).Countable) (fg : ∀ M ∈ K, Structure.FG L ↑M) (hp : Hereditary K) (jep : JointEmbedding K) : ∃ (M : CategoryTheory.Bundled L.Structure), Structure.CG L ↑M ∧ L.age ↑M = K

Sufficient conditions for a class to be the age of a countably-generated structure.

theorem FirstOrder.Language.exists_countable_is_age_of_iff {L : Language} {K : Set (CategoryTheory.Bundled L.Structure)} [Countable ((l : ℕ) × L.Functions l)] : (∃ (M : CategoryTheory.Bundled L.Structure), Countable ↑M ∧ L.age ↑M = K) ↔ K.Nonempty ∧ (∀ (M N : CategoryTheory.Bundled L.Structure), Nonempty (L.Equiv ↑M ↑N) → (M ∈ K ↔ N ∈ K)) ∧ (Quotient.mk' '' K).Countable ∧ (∀ M ∈ K, Structure.FG L ↑M) ∧ Hereditary K ∧ JointEmbedding K

def FirstOrder.Language.IsUltrahomogeneous (L : Language) (M : Type w) [L.Structure M] : Prop

A structure M is ultrahomogeneous if every embedding of a finitely generated substructure into M extends to an automorphism of M.

Equations

• L.IsUltrahomogeneous M = ∀ (S : L.Substructure M), S.FG → ∀ (f : L.Embedding (↥S) M), ∃ (g : L.Equiv M M), f = g.toEmbedding.comp S.subtype

structure FirstOrder.Language.IsFraisseLimit {L : Language} (K : Set (CategoryTheory.Bundled L.Structure)) (M : Type w) [L.Structure M] [Countable ((l : ℕ) × L.Functions l)] [Countable M] : Prop

A structure M is a Fraïssé limit for a class K if it is countably generated, ultrahomogeneous, and has age K.

• ultrahomogeneous : L.IsUltrahomogeneous M
• age : L.age M = K

theorem FirstOrder.Language.IsUltrahomogeneous.extend_embedding {L : Language} {M : Type w} [L.Structure M] (M_homog : L.IsUltrahomogeneous M) {S : Type u_1} [L.Structure S] (S_FG : Structure.FG L S) {T : Type u_2} [L.Structure T] [h : Nonempty (L.Embedding T M)] (f : L.Embedding S M) (g : L.Embedding S T) : ∃ (f' : L.Embedding T M), f = f'.comp g

Any embedding from a finitely generated S to an ultrahomogeneous structure M can be extended to an embedding from any structure with an embedding to M.

theorem FirstOrder.Language.isUltrahomogeneous_iff_IsExtensionPair {L : Language} {M : Type w} [L.Structure M] (M_CG : Structure.CG L M) : L.IsUltrahomogeneous M ↔ L.IsExtensionPair M M

A countably generated structure is ultrahomogeneous if and only if any equivalence between finitely generated substructures can be extended to any element in the domain.

theorem FirstOrder.Language.IsUltrahomogeneous.amalgamation_age {L : Language} {M : Type w} [L.Structure M] (h : L.IsUltrahomogeneous M) : Amalgamation (L.age M)

theorem FirstOrder.Language.IsUltrahomogeneous.age_isFraisse {L : Language} {M : Type w} [L.Structure M] [Countable M] (h : L.IsUltrahomogeneous M) : IsFraisse (L.age M)

theorem FirstOrder.Language.IsFraisseLimit.isFraisse {L : Language} (K : Set (CategoryTheory.Bundled L.Structure)) {M : Type w} [L.Structure M] [Countable ((l : ℕ) × L.Functions l)] [Countable M] (h : IsFraisseLimit K M) : IsFraisse K

If a class has a Fraïssé limit, it must be Fraïssé.

theorem FirstOrder.Language.IsFraisseLimit.isExtensionPair {L : Language} {K : Set (CategoryTheory.Bundled L.Structure)} {M : Type w} [L.Structure M] {N : Type w} [L.Structure N] [Countable ((l : ℕ) × L.Functions l)] [Countable M] [Countable N] (hM : IsFraisseLimit K M) (hN : IsFraisseLimit K N) : L.IsExtensionPair M N

theorem FirstOrder.Language.IsFraisseLimit.nonempty_equiv {L : Language} {K : Set (CategoryTheory.Bundled L.Structure)} {M : Type w} [L.Structure M] {N : Type w} [L.Structure N] [Countable ((l : ℕ) × L.Functions l)] [Countable M] [Countable N] (hM : IsFraisseLimit K M) (hN : IsFraisseLimit K N) : Nonempty (L.Equiv M N)

The Fraïssé limit of a class is unique, in that any two Fraïssé limits are isomorphic.

theorem FirstOrder.Language.empty.isFraisseLimit_of_countable_infinite (M : Type u_1) [Countable M] [Infinite M] [Language.empty.Structure M] : IsFraisseLimit {S : CategoryTheory.Bundled Language.empty.Structure | Finite ↑S} M

Any countable infinite structure in the empty language is a Fraïssé limit of the class of finite structures.

theorem FirstOrder.Language.empty.isFraisse_finite : IsFraisse {S : CategoryTheory.Bundled Language.empty.Structure | Finite ↑S}

The class of finite structures in the empty language is Fraïssé.