Click here to return to the main course web page.

Let \(\mathcal{L}\) be a finite relational language. A class \(\mathfrak{F}\) of finite \(\mathcal{L}\)-structures is a Fraïssé class if it is nonempty, hereditary (closed under taking substructures), closed under isomorphism, and has the amalgamation property: if \(f:\mathcal{A} \to \mathcal{B}\) and \(g:\mathcal{A} \to \mathcal{C}\) are embeddings between elements of \(\mathfrak{F}\), there exists a \(\mathcal{D}\) in \(\mathfrak{F}\) and embeddings \(\bar f: \mathcal{B} \to \mathcal{D}\) and \(\bar g : \mathcal{C} \to \mathcal{D}\) such that \(\bar f \circ f = \bar g \circ g\). If \(\mathcal{M}\) is an \(\mathcal{L}\)-structure and every finite partial automorphism of \(\mathcal{M}\) extends to an automorphism, then we say that \(\mathcal{M}\) is ultrahomogeneous. A countable ultrahomogenous structure is called a Fraïssé strucure. (The terminology ultrahomogeneous is common in Fraïsse theory. Model theorists define homogeneous to mean something stronger than being ultrahomogeneous and equivalent in the class of countable structures.)

1. Show that if \(\mathcal{M}\) is a Fraïssé structure, then the class of finite \(\mathcal{L}\)-structures which are isomorphic to a substructure of \(\mathcal{M}\) is a Fraïssé class.
2. Show that if \(\mathfrak{F}\) is a Fraïssé class, then there is a Fraïssé structure \(\lim \mathfrak{F}\) such that \(\mathfrak{F}\) is the collection of isomorphism types of finite substructures of \(\lim \mathfrak{F}\). Show that \(\lim \mathfrak{F}\) is unique up to isomorphism. Remark: \(\lim \mathfrak{F}\) is called the Fraïssé limit of \(\mathfrak{F}\).
3. Show that the theory of the Fraïssé limit of a Fraïssé class is \(\aleph_0\)-categorical.
4. What are the Fraïssé limits of the following classes: finite linear orders, finite graphs, finite boolean algebras? ( In the last example we must modify the framework slightly to allow functions in \(\mathcal{L}\). ) You only need to justify your answer for one of the classes.