Universal order type

Question

Every countable order type, such as the countable ordinals, $\mathbb Z$, etc. can be embedded in $\mathbb Q$, so it is universal for countable order types. Is there a universal space for all linear orders of cardinality continuum? Or more generally, a universal space for all linear orders of any given cardinality?

Answer 1

You are looking for the concept of saturated model. A model $M$ is $\kappa$-saturated if any type consisting of fewer than $\kappa$ many assertions that is consistent with the elementary diagram of $M$ is realized in $M$. One can easily build saturated models simply by realizing more and more types. Any linear order that is $\kappa$-saturated will be universal for all linear orders of size $\kappa$, simply by a length $\kappa$ analogue of the forth part of Cantor's back-and-forth construction, which is how he proved the countable universal case you mentioned.

That is, the way that you prove that $\mathbb{Q}$ is universal for countable linear orders, is that if we have a countable linear order $\langle L,\leq\rangle$, then we enumerate the elements of $L$ as $a_0,a_1,a_2,\ldots$ and having assigned an order-preserving partial isomorphism on an initial segment of this order $a_i\mapsto q_i$, for $i\lt n$, we look at how $a_n$ sits with respect to the $a_i$ for $i\lt n$ and choose an image $q_n$ that sits the same way with respect to $q_i$ for $i\lt n$. That is to say, we pick a $q_n$ that realizes the same type over the earlier $q_i$ that $a_n$ realizes over the earlier $a_i$. In other words, the point is that $\mathbb{Q}$ is $\omega$-saturated, which amounts to the trivial fact that if we have finitely many rational numbers, then any type describing how an unknown point $x$ might relate to those finitely many points of course just says that $x$ is between two of them or on top or on the bottom and hence is realized in $\mathbb{Q}$, since this is an endless dense linear order.

This idea generalizes to transfinite constructions, provided that we can be guaranteed that the type will be realized. If the target model is $\kappa$-saturated, then any linear order of cardinality $\kappa$ can be enumerated $a_\alpha$ for $\alpha\lt\kappa$, and at stage $\beta$ we want to pick an image $q_\beta$ for $a_\beta$ that realizes the same type over the earlier $q_\alpha$ that $a_\beta$ realizes over the earlier $a_\alpha$. If the target is $\kappa$-saturated, then this type will be realized in $M$, and so we will have our desired target $q_\beta$ and the construction will proceed.

Apart from the abstract saturated concept, however, one can construct universal orders directly in a variety of ways. First, of course, there are only $2^\kappa$ many different order types for an order of size $\kappa$, and by simply placing them one after the other, one gets a linear order that is clearly universal. But the size of that order may be wastefully high.

If CH holds, then one can make a linear order of size $\aleph_1$ that is saturated for countable types. Given any other linear order of size $\aleph_1$, we may enumerate it in an $\omega_1$-sequence, and build an embedding by the "forth" construction as above, since the image of the next point will simply be any point in our saturated order that realizes the corresponding type.

If CH fails, however, then we cannot necessarily get a saturated model of size $\aleph_1$, but we can still build a $c$-saturated model of larger size, and this is enough to carry out the "forth" construction.

The Surreals. Lastly, let me say that the construction of the surreal numbers can be viewed as a construction focused relentlessly on building a universal linear order. That is, one way to construct the surreal numbers is to proceed in a transfinite recursion, which at each stage $\alpha$ we have the linear order constructed so far, and the next linear order simply fills all cuts in this order. So one starts with nothing, and then fills the empty cut, to get one point. Then, one fills the lower cut and the upper cut, which in effect adds a point below and a point above. Now, one adds points at the bottom, top and in between all the current points, and so on. At stage $\omega$, one can therefore constructed a countable dense linear order. At the next stage, all the Dedekind cuts are filled in, and also a lower point and an upper point are added. At the next stage, we start to get infinitesimals, by filling the cut between $0$ and all the positive numbers, and the same above and below any point. At each step of the construction, by filling a cut one is realizing the type that describes what it means to be the thing that fills that cut. It follows that the class of surreal numbers is universal for all set-sized linear orders.

The restriction of the surreals to the numbers born before any stage $\beta$ will be universal for linear orders of size $\beta$, since each next point in the original order fills some cut in that order, and so one can map it to the correspondingly newly-born surreal number filling the corresponding cut in the surreals.

Answer 2

One should distinguish two forms of the question. Given an infinite cardinal number $\kappa$, one can ask for some linear order $U$ into which all $\kappa$-sized linear orders embed, or one can ask for such a $U$ of size $\kappa$. Joel's answer is mostly (though not entirely) about positive results for the first version. The second version is also interesting, especially since one can sometimes get universal models in this sense even when one cannot get saturated models. There has been a good deal of work on this problem, much of it by Saharon Shelah, also in collaboration with Menachem Kojman or Mirna Dzamonja. You might want to look at the paper "Nonexistence of universal orders in many cardinals" by Kojman and Shelah [J. Symbolic Logic 57 (1992) pp. 875-891, available on JSTOR], especially the introduction, which describes the background of the problem.

Answer 3

Even though the question is almost a year old and already has an accepted answer, I think it is worth mentioning Sierpinskii´s article in Fundamenta (Tom 18, 1932):

"Généralisation d'un théoreme de Cantor concernant les ensembles ordonnés dénombrables",

Where he proves that under $CH$ there is a linear order of size $\mathfrak{c}$ into which all $\mathfrak{c}$-sized linear orders embed.

Answer 4

In Joel Hamkins' remark, "If CH fails, however, then we cannot necessarily get a saturated model of size $\aleph_1$," one can actually drop the "necessarily." The existence of a saturated linear order of size $\aleph_1$ is in fact equivalent to CH. If $(L, <)$ is a line, then one can show that $L$ is $\aleph_1$-saturated if and only if

1. For any countable increasing sequence $a_0 < a_1 < \ldots$ there exists $a \in L$ such that $a > a_n$ for all $n$. Similarly, any countable decreasing sequence $b_0 > b_1 > \ldots$ is bounded below by some $b$. This says there are no countable cofinal sequences in $L$.
2. If $a_0 < a_1 < \ldots < b_1 < b_0$ are sequences in $L$, then there exist points $a, b \in L$ such that $a_i < a < b < b_j$ for all $i, j$. This says that our line has no countable gaps.
3. If $a_0 < a_1 < \ldots < x < \ldots < b_1 < b_0$, then there exist points $a, b \in L$ such that $a_i < a < x < b < b_j$ for all $i, j$. This says that no $x$ in $L$ can be approached by a countable sequence from either side.

From this, one can prove that the order $(2^{\omega_1}, <_{lex})$ embeds into the Dedekind completion of any $\aleph_1$-saturated $L$. If such an $L$ has cardinality $\aleph_1$ (that is, if $L$ is saturated in the full sense), then we have that $(2^{\omega_1}, <_{lex})$ has a dense subset of size $\aleph_1$. But any dense subset of $(2^{\omega_1}, <_{lex})$ must have size at least $2^{<\omega_1}$. The equality $\aleph_1$ = $2^{<\omega_1}$ gives CH.

The saturated order $L$ plays much the same role in $(2^{\omega_1}, <_{lex})$ that $\mathbb{Q}$ plays in $\mathbb{R}$. The combinatorial characterization of saturation given above allows one to naturally generalize Cantor's proof that any countable dense linear order without endpoints is isomorphic to $\mathbb{Q}$. Indeed, if $(L_1, <)$ and $(L_2, <)$ are two orders both satisfying conditions 1–3, and $|L_1| = |L_2| = \aleph_1$, then a Cantor style back-and-forth argument shows that $L_1 \cong L_2$. One can also see why any such $L$ will be universal: the conditions 1–3 allow any countable partial embedding of an $\aleph_1$-sized linear order into $L$ to be extended without trouble to a full embedding.

The generalization of the above argument to higher cardinalities also goes through, showing that GCH not only implies but is equivalent to the statement "for every cardinal $\kappa$, there exists a saturated linear order of size $\kappa^+$."