Fraïssé limit

Fix a language ${\displaystyle {\mathcal {L}}}$. By an ${\displaystyle {\mathcal {L}}}$-structure, we mean a logical structure having signature ${\displaystyle {\mathcal {L}}}$.

Given an ${\displaystyle {\mathcal {L}}}$-structure ${\displaystyle {\mathcal {M}}}$ with domain ${\displaystyle M}$, and a subset ${\displaystyle A\subseteq M}$, we use ${\displaystyle \langle A\rangle ^{\mathcal {M}}}$ to denote the least substructure of ${\displaystyle {\mathcal {M}}}$ whose domain contains ${\displaystyle A}$ (i.e. the closure of ${\displaystyle A}$ under all the function and constant symbols in ${\displaystyle {\mathcal {L}}}$).

A substructure ${\displaystyle {\mathcal {N}}}$ of ${\displaystyle {\mathcal {M}}}$ is then said to be finitely generated if ${\displaystyle {\mathcal {N}}=\langle A\rangle ^{\mathcal {M}}}$ for some finite subset ${\displaystyle A\subseteq M}$.[4] The age of ${\displaystyle {\mathcal {M}}}$, denoted ${\displaystyle \operatorname {Age} ({\mathcal {M}})}$, is the class of all finitely generated substructures of ${\displaystyle {\mathcal {M}}}$.

One can prove that any class ${\displaystyle \mathbf {K} }$ that is the age of some structure satisfies the following two conditions:

Hereditary property (HP)

If ${\displaystyle A\in \mathbf {K} }$ and ${\displaystyle B}$ is a finitely generated substructure of ${\displaystyle A}$, then ${\displaystyle B}$ is isomorphic to some structure in ${\displaystyle \mathbf {K} }$.

Joint embedding property (JEP)

If ${\displaystyle A,B\in \mathbf {K} }$, then there exists ${\displaystyle C\in \mathbf {K} }$ such that both ${\displaystyle A}$ and ${\displaystyle B}$ are embeddable in ${\displaystyle C}$.

A commutative diagram illustrating the amalgamation property.

As above, we noted that for any ${\displaystyle {\mathcal {L}}}$-structure ${\displaystyle {\mathcal {M}}}$, ${\displaystyle \operatorname {Age} ({\mathcal {M}})}$ satisfies the HP and JEP. Fraïssé proved a sort-of-converse result: when ${\displaystyle \mathbf {K} }$ is any non-empty, countable set of finitely generated ${\displaystyle {\mathcal {L}}}$-structures that has the above two properties, then it is the age of some countable structure.

Furthermore, suppose that ${\displaystyle \mathbf {K} }$ happens to satisfy the following additional properties.

Amalgamation property (AP)

For any structures ${\displaystyle A,B,C\in \mathbf {K} }$, such that there exist embeddings ${\displaystyle f:A\to B}$, ${\displaystyle g:A\to C}$, there exists a structure ${\displaystyle D\in \mathbf {K} }$ and embeddings ${\displaystyle f':B\to D}$, ${\displaystyle g':C\to D}$ such that ${\displaystyle f'\circ f=g'\circ g}$ (i.e. they coincide on the image of A in both structures).

Essential countability (EC)

Up to isomorphism, there are countably many structures in ${\displaystyle \mathbf {K} }$.

In that case, we say that K is a Fraïssé class, and there is a unique (up to isomorphism), countable, homogeneous structure ${\displaystyle \operatorname {Flim} (\mathbf {K} )}$ whose age is exactly ${\displaystyle \mathbf {K} }$.[5] This structure is called the Fraïssé limit of ${\displaystyle \mathbf {K} }$.

Here, homogeneous means that any isomorphism ${\displaystyle \pi :A\to B}$ between two finitely generated substructures ${\displaystyle A,B\in \mathbf {K} }$ can be extended to an automorphism of the whole structure.

The archetypal example is the class ${\displaystyle \mathbf {FCh} }$ of all finite linear orderings, for which the Fraïssé limit is a dense linear order without endpoints (i.e. no smallest nor largest element). By Cantor's isomorphism theorem, up to isomorphism, this is always equivalent to the structure ${\displaystyle \langle \mathbb {Q} ,<\rangle }$, i.e. the rational numbers with the usual ordering.

As a non-example, note that neither ${\displaystyle \langle \mathbb {N} ,<\rangle }$ nor ${\displaystyle \langle \mathbb {Z} ,<\rangle }$ are the Fraïssé limit of ${\displaystyle \mathbf {FCh} }$. This is because, although both of them are countable and have ${\displaystyle \mathbf {FCh} }$ as their age, neither one is homogeneous. To see this, consider the substructures ${\displaystyle {\big \langle }\{1,3\},<{\big \rangle }}$ and ${\displaystyle {\big \langle }\{5,6\},<{\big \rangle }}$, and the isomorphism ${\displaystyle 1\mapsto 5,\ 3\mapsto 6}$ between them. This cannot be extended to an automorphism of ${\displaystyle \langle \mathbb {N} ,<\rangle }$ or ${\displaystyle \langle \mathbb {Z} ,<\rangle }$, since there is no element to which we could map ${\displaystyle 2}$, while still preserving the order.

Another example is the class ${\displaystyle \mathbf {Gph} }$ of all finite graphs, whose Fraïssé limit is the Rado graph.[1]

Suppose our class ${\displaystyle \mathbf {K} }$ under consideration satisfies the additional property of being uniformly locally finite, which means that for every ${\displaystyle n}$, there is a uniform bound on the size of an ${\displaystyle n}$-generated substructure. This condition is equivalent to the Fraïssé limit of ${\displaystyle \mathbf {K} }$ being ω-categorical.[6]

For example, the class of finite dimensional vector spaces over a fixed field is always a Fraïssé class, but it is uniformly locally finite only if the field is finite.

• Structural Ramsey theory
• Hrushovski construction