# Application of Fraïssé construction in set 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.

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.

If you are willing to allow uncountable generalizations of Fraisse's/Hrushovski construction then the conditions you need essentially are those that make up an Abstract Elementary Class. Abstract elementary classes are a framework for studying abstract logics introduced by Shelah and generalize many important known examples of logics. As for the relationship to set theory, Will Boney has recently proved from large cardinals the Shelah's categoricity conjecture (see Tameness).

If you are willing to generalize just a little further then you get the notion of an accessible category. Accessible categories have strong connections to Vopenka's principle.

• I believe Sebastien Vasey also gave a (near?-)proof - the other day! - of Shelah's categoricity conjecture: arxiv.org/abs/1503.01366 Mar 6, 2015 at 8:54
• First off, thanks for the link, that paper looks interesting! That said, while I am far from an expert in AEC, it seems from the abstract that Vasey is proving various structural properties from tameness and a categoricity assumption. And while this is very interesting (and I am sure if I understood more I would have an even better appreciation) his proof of the categoricity conjecture (like Boney's) uses a proper class of strongly compacts. Mar 6, 2015 at 9:56
• While even having a relative consistency result is a substantial step forward, to really have a proof of the categoricity conjecture (in my opinion) one needs to either prove it from ZFC, show it is independent from ZFC, or show that it is equivalent to some large cardinal assumption. Mar 6, 2015 at 9:58
• @NateAckerman, probably you mean: equiconsistent with some large cardinal assumption, rather than equivalent? Mar 6, 2015 at 13:55
• For AECs, one of the main uses of "uncountable Fraisse" is that, under the assumptions of amalgamation, joint embedding, and no maximal models, there are monster models as in first order. The construction is exactly the same as the normal Fraisse, except "finite" is replaced with "<\kappa"; for the strongest result you need that \kappa is inaccessible. The relation with large cardinals is (in my mind) a bit of a red herring: the compact cardinals allow you to derive amalgamation, joint embedding, and no maximal models, which then plug into preexisting construction. They also give you tameness.
– Will
Mar 20, 2015 at 18:23

Here's one (I'm not sure if you'd place it in "set theory" or "model theory," but I put it in both):

Vaught's conjecture - for now - is the statement that there is no first-order theory $$T$$ in a countable language such that (1) $$T$$ has countable models of arbitrarily high Scott rank below $$\omega_1$$, but (2) $$T$$ has only countably many countable models of Scott rank $$<\alpha$$ for any fixed $$\alpha<\omega_1$$. (This is the absolute version of Vaught's conjecture; the snappier "Every countable theory has either $$\aleph_0$$ or $$2^{\aleph_0}$$ many countable models" trivializes in case CH holds.)

Now, there's a lot of work on what sort of weird properties a counterexample to Vaught's conjecture must have. For instance, Harrington (unpublished) showed that if $$T$$ is a counterexample to Vaught's conjecture, then $$T$$ has models of size $$\aleph_1$$ with Scott rank arbitrarily high below $$\omega_2$$. Recently$$^*$$, Julia Knight, Antonio Montalban, and I gave a proof of Harrington's result using a Fraisse-type argument:

• Fix $$\alpha<\omega_2$$. Consider a generic extension $$V[G]$$ in which $$\omega_1$$ is made countable but $$\omega_2$$ is kept uncountable.

• Now in $$V[G]$$, since "is a counterexample to Vaught's conjecture" is absolute (see How do we know if Vaught's Conjecture is Absolute?), there is a model $$B$$ of $$T$$ which is countable in $$V[G]$$ and has Scott rank $$\beta>\alpha$$.

• Let $$\nu$$ be a $$\mathbb{P}$$-name in $$V$$ with $$\nu[G]=B$$. Then there must be some $$p\in G$$ such that $$(p, p)\Vdash_{\mathbb{P}^2}\nu[G_0]\cong\nu[G_1];$$ otherwise, it's not hard to show that we could add a perfect set of nonisomorphic models of $$T$$ with Scott rank $$\beta$$, without collapsing $$\omega_1^{V[G]}=\omega_2^V$$, which would contradict the assumption that $$T$$ is a counterexample to Vaught's conjecture.

• Now it turns out we can show that there is a copy of $$B$$ already living inside $$V$$ - specifically, there is a structure $$A\in V$$ such that $$V[G]\models A\cong B$$. Then $$\vert A\vert^V=\aleph_1$$ (it can't be countable since the Scott rank is $$>\omega_1^V$$, and it can't have cardinality $$>\aleph_1$$ since $$\aleph_2$$ isn't collapsed) and the Scott rank of $$A$$ is $$>\alpha$$, so Harrington's result is proved.

Okay, so what on earth does this have to do with Fraisse limits? Well, it's the "it turns out . . ." bit above. The crucial combinatorial gadget being used is that, essentially, ages of size $$\aleph_1$$ have Fraisse limits! The structure $$B\in V[G]$$ gives rise to a family of finite structures in an enriched language (basically, naming all the orbits - just the language coming from the Scott analysis); this family can easily be shown to exist in $$V$$, and any limit of this age must (in $$V[G]$$) be isomorphic to $$B$$ (or rather, have a reduct isomorphic to $$B$$).

It turns out, by work of Shelah and Laskowski, that this fails for ages of size $$\aleph_2$$; in particular, I think it's unknown if a counterexample to Vaught's conjecture must have models of size $$\aleph_2$$ with Scott rank arbitrarily high below $$\omega_3$$. But I'm not sure about this. (EDIT: See Nate Ackerman's comment below.)

$$^*$$ Baldwin/Friedman/Koerwien/Laskowski around the same time and Paul Larson about a year earlier each also proved Harrington's result. I haven't read their papers in detail, but I believe the proofs are similar.

• Actually by work of Hjorth, if there is a counterexample to Vaught's conjecture there must be a ($L_{\omega_1,\omega}$) counterexample which has no models of size greater than $\aleph_1$. So in particular it need not have models of size $\aleph_2$ with arbitrary high Scott rank below $\aleph_3$. Mar 6, 2015 at 8:45
• Oh, neat! I didn't know that! Do you have a citation? (My google-fu seems to be failing me . . .) Mar 6, 2015 at 8:49
• So the original paper is "A note on counterexamples to the Vaught conjecture" by Hjorth. The proof, while short, is very descriptive set theoretic. There is also a model theoretic version of the proof in the Baldwin/Friedman/Koerwien/Laskowski paper you mentioned. Also, to help me and some friends understand the Hjorth proof I wrote up a model theoretic version as well which you can find at Hjorth. Mar 7, 2015 at 3:40
• I appreciate the reference to my paper. I wouldn't say, however, that the three proofs were produced at pretty much the same time. My proof was circulated in January 2013. Fundamentally, the three proofs are probably the same, but the techniques used are different. Apr 4, 2015 at 2:14
• Sorry, I didn't realize that - fixed. Apr 5, 2015 at 7:37

While not strictly set theory, but rather a result connecting Ramsey theory and topological dynamics, two areas that are rather close to set theory, you might find the following example interesting:

In http://arxiv.org/pdf/math/0305241.pdf Kechris, Pestov and Todorcevic showed that a Fraisse class of finite structure is Ramsey iff the automorphism group of the Fraisse limit is extremely amenable.

Let me explain: The Fraisse limits that we are talking about here are countable structures and the automorphism groups of these structures carry a natural topology, the topology of pointwise convergence, which in this situation is separable and metric. Given a topological group $G$, a continuous action of $G$ on a compact space $X$ is minimal if every orbit is dense in $X$. We call a compact space $X$ together with a continuous $G$-action a $G$-flow. Using Zorn's lemma, we see that every $G$-flow contains a minimal $G$-flow. It turns out that there is a universal minimal $G$-flow, i.e., one that maps onto every other minimal $G$-flow by a $G$-equivariant map (a map that respects the group action). Now the construction of the universal minimal flow can be phrased in various ways, but concepts like ultrafilters and other applications of Zorn's lemma show up here. So this is, in some sense, set theory.

Now a topological group is extremely amenable if its universal minimal flow has just one point, or equivalently, if every $G$-flow has a fixed point.

On the other hand, a class of finite structures is Ramsey if for all $A$ and $B$ in the class there is $C$ in the class such that for every coloring of all copies of $A$ inside $C$ with two colors, there is a copy $B'$ of $B$ in $C$ such that all copies of $A$ in $B'$ have the same color. The usual Ramsey theorem shows that the class of finite linear orders is a Ramsey class and the Nesetril-Rödl theorem is precisely the statement that the class of finite ordered graphs is a Ramsey class.

As corollaries from the Kechris, Pestov, Todorcevic theorem we get that the automorphism groups of the countable dense linear order without endpoint $(\mathbb Q,\le)$ and of the ordered random graph are extremely amenable.

• Hi Stefan, could you say something about why extreme amenability is of interest? May 7, 2019 at 20:21
• Hi Monroe, minimal flows are in some sense building blocks of flows in general. Hence we want to understand them. In the case of extremely amenable groups we do. They consist of a single point. Amenabilty (which follows from extreme amenabilty) was considered after the Banach-Tarski paradox used an action of the free group with two generators to get the pathological decomposition of the three-dimensional ball. Amenable groups where introduced by von Neumann precisely because they avoid such paradoxical decompositions. May 28, 2019 at 15:21

I add a few more references and applications:

(A) Trevor Irwin's thesis Fraïssé limits and colimits with applications to continua'':

Abstract: The classical Fraïssé construction is a method of taking a direct limit of a family of finite models of a language provided the family fulfills certain amalgamation conditions. The limit is a countable model of the same language which can be characterized by its (injective) homogeneity and universality with respect to the initial family of models. A standard example is the family of finite linear orders for which the Fraïssé limit is the rational numbers with the usual ordering.

We present this classical construction via category theory, and within this context we introduce the dual construction. This respectively constitutes the Fraïssé colimits and limits indicated in the title. We provide several examples.

We then present the projective Fraïssé limit as a special case of the dual construction, and as such it is the categorical dual to the classical (injective) Fraïssé limit. In this dualization we use a notion of model theoretic structure which has a topological ingredient. This results in the countable limit structures being replaced by structures which are zero-dimensional, compact, second countable spaces with the property that the relations are closed and the functions are continuous.

We apply the theory of projective Fraïssé limits to the pseudo-arc by first representing the pseudo-arc as a natural quotient of a projective Fraïssé limit. Using this representation we derive topological properties of the pseudo-arc as consequences of the properties of projective Fraïssé limits. We thereby obtain a new proof of Mioduszewski’s result that the pseudo-arc is surjectively universal among chainable continua, and also a homogeneity theorem for the pseudo-arc which is a strengthening of a result due to Lewis and Smith. We also find a new characterization of the pseudo-arc via the homogeneity property.

We continue with further applications of these methods to a class of continua known as pseudo-solenoids, and achieve analogous results for the universal pseudo-solenoid.

(B) Wieslaw Kubiś, ''Fraisse sequences - a category-theoretic approach to universal homogeneous structures'':

Abstract: We present a category-theoretic approach to universal homogeneous objects, with applications in the theory of Banach spaces and in set-theoretic topology,

This is a comment on something Nate Ackerman posted two days ago in the context of Shelah's categoricity conjecture for Abstract Elementary Classes. As I according to math overflow I don't have the necessary credentials to comment directly, I encloed this.

At present even the consistency of that conjecture is open. The best ZFC result is for AECs that satisfy extra conditions assuming that the class is categorical in a successor (Grossberg & VanDieren). Boney managed to derive the above "extra conditions" from a class-many strongly compact cardinals. In all approximations in the last 25 years to the categoricity conjecture for AECs one had to assume categoricity in \lambda^+ removal for the successor assumptionis considered one of teh major open problems.

Last week Sebastien Vasey posted on the arXiv a rather long paper, his Theorem 1.7(2) establishes the consistency of the eventual categoricity conjecture (removing the successor). In his proof he is using several major recent results (total of about 500-600 pages) that I am sure are correct. However he is also using a Theorem that Shelah announced several years ago, the draft of that paper of Shelah is more than 150 pages long and he is working on it several years now.

• Welcome to MO, Professor Grossberg. Mar 8, 2015 at 20:14
• Dear Professor Grossberg, Welcome to MathOverFlow. Mar 9, 2015 at 7:53