[Math] Application of Fraïssé construction in set theory

descriptive-set-theorylo.logicmodel-theoryreference-requestset-theory

As you know Fraïssé limit construction and its generalization, Hrushovski's construction, have many applications in model theory to build models with interesting property.

Now I would like to know the application of Fraïssé construction in set theory.

Question: What are the major applications of Fraïssé construction in set theory?

Any reference will be appreciated.

Best Answer

A Fraïssé construction lies at the heart of the proof of my embedding theorems.

Theorem. (J. D. Hamkins, Every countable model of set theory embeds into its own constructible universe, JML 13(2), 2014).

  1. For any two countable models of set theory $\langle M,\in^M\rangle$ and $\langle N,\in^N\rangle$, one of them embeds into the other.

  2. Indeed, a countable model of set theory $\langle M,{\in^M}\rangle$ embeds into another model of set theory $\langle N,{\in^N}\rangle$ if and only if the ordinals of $M$ order-embed into the ordinals of $N$.

  3. Consequently, every countable model $\langle M,\in^M\rangle$ of set theory embeds into its own constructible universe $\langle L^M,\in^M\rangle$.

  4. Furthermore, every countable model of set theory embeds into the hereditary finite sets $\langle \text{HF},{\in}\rangle^M$ of any nonstandard model of arithmetic $M\models\text{PA}$. Indeed, $\text{HF}^M$ is universal for all countable acyclic binary relations.

The sense of embedding here is $j:M\to N$ for which $x\in y\iff j(x)\in j(y)$, which is the model-theoretic sense of embedding, and this is weaker than those usually considered in set theory because they need not be elementary nor even $\Delta_0$-elementary. An embedding $j:M\to N$ is simply an isomorphism of $M$ with a substructure of $N$, not necessarily transitive.

The proof proceeds by finding sufficiently universal substructures of any model of set theory, using essentially a Fraïssé limit construction, as you can see in the paper. Basically, this construction shows that every countable model of set theory $\langle M,\in^M\rangle$ has a submodel that is universal for all countable $\text{Ord}^M$-graded digraphs. A grading of a digraph is a linear pre-order on that digraph, such that the linear order strictly increases when following any edge of the digraph. Any model of set theory $\langle M,\in^M\rangle$ admits an $\text{Ord}^M$ grading by means of the von Neumann rank, since whenever $x\in y$, then the rank of $y$ strictly exceeds that of $x$.

It happens that I am speaking today on this topic at the CUNY set theory seminar, in about an hour.

Related Question