Uniqueness of Fraïssé limits
ProvedFamousTheorems.fraisse_limit_uniquenessUniqueness of Fraïssé limits. Let be a first-order language with countably many function symbols and let be a class of -structures. If and are countable structures that are both Fraïssé limits of , then and are isomorphic.
A Fraïssé limit of is a countable ultrahomogeneous structure whose age (class of finitely generated substructures) is . The uniqueness theorem, proved by a back-and-forth argument, is what makes objects such as the rational order , the Rado random graph and the countable atomless Boolean algebra canonical.
Formalization note. Mathlib's FirstOrder.Language.IsFraisseLimit.nonempty_equiv. IsFraisseLimit K M says that is countable and ultrahomogeneous with age , and L.Equiv M N is the type of -isomorphisms. The countability of the function symbols is the hypothesis Countable ((l : ℕ) × L.Functions l). Both structures live in the same universe.
import Mathlib
namespace FamousTheorems
universe u
theorem fraisse_limit_uniqueness {L : FirstOrder.Language} {K : Set (CategoryTheory.Bundled L.Structure)} {M N : Type u}
[L.Structure M] [L.Structure N] [Countable ((l : ℕ) × L.Functions l)] [Countable M] [Countable N]
(hM : FirstOrder.Language.IsFraisseLimit K M) (hN : FirstOrder.Language.IsFraisseLimit K N) :
Nonempty (L.Equiv M N) := by sorry
end FamousTheorems