nLab Fraïssé limit

Idea

Given a collection of finite(ly-generated) first-order structures which formally resemble collections of finite(ly-generated) substructures found inside an infinite structure, there are additional assumptions on such collections we can make which ensure that they can be amalgamated into an infinite structure which somehow captures the “generic theory” of the collection we started with.

Definition

A class of finitely-generated structures closed under substructures and isomorphisms such that:

1. (Amalgamation) every span of embeddings (not necessarily elementary) admits a cocone, and

2. (Joint embedding) Every pair of structures admits a cocone

is called a Fraïssé class.

A Fraïssé limit $\underset{\rightarrow}{\operatorname{Flim}}(\mathcal{C})$ of a Fraïssé class $\mathcal{C}$ is the unique (existence and uniqueness was Fraïssé‘s theorem) countable ultrahomogeneous (every isomorphism of finitely-generated substructures extends to an automorphism of $M$) structure into which every member of $\mathcal{C}$ embeds.

Constructing Fraïssé limits

[Will fill this in after I learn how to typeset diagrams]

Examples

• The countable dense linear order is the Fraisse limit of the class of finite linear orders.

• The countable random graph is the Fraisse limit of the class of finite graphs.

• The Henson graph? (the generic triangle-free graph) is the Fraisse limit of the class of finite triangle-free graphs.

• A modification (Hrushovski constructions?) to the Fraïssé construction was used by Ehud Hrushovski to produce a counterexample to Zilber's trichotomy conjecture? classifying the possible combinatorial geometry on a strongly minimal? set.

Remarks

• Olivia Caramello remarks in her topos-theoretic Fraïssé paper (linked below) that the classifying topos of an omega-categorical? structure $A$ presentable as a Fraïssé limit is precisely the category of continuous Aut(A)-sets, where the automorphism group of $A$ is equipped with the topology of pointwise convergence.

• It is interesting when a structure is presentable as both a Fraïssé limit and (an elementary submodel of) an ultraproduct of finite structures. In more suggestive terminology, this means that the generic and the almost-sure (one way of obtaining the almost-sure theory of a collection of finite structures is to take the theory of their ultraproduct) theories of the underlying collection of finite structures coincide. For example, the countable random graph above satisfies a zero-one law.

• Recently, Zilber has been trying to study F_1-geometry by ‘fusing’ the algebraic closures of finite fields together with a Hrushovski construction and studying a nonstandard extension (ultrapower) of the result.

Related concepts

omega-categorical structure

homogeneous structure?

References

• David Corfield, Fraïssé limits

• Hodges, A shorter model theory

• Olivia Caramello, Fraïssé‘s construction from a topos-theoretic perspective