Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $\mathcal{T}_\kappa$ be the set of all linear order types of cardinality $\kappa$. Let $\prec$ denote a binary relation on $\mathcal{T}_\kappa$ representing embeddability of order types (note that $\prec$ is a quasi-order).

  • What is the cardinality of a subset of $\mathcal{T}_\kappa$ of the largest size that can be equipped with a linear order $<$ consistent with $\prec$ (such that $\tau<\mu$ implies $\tau\prec\mu$)?

  • What is the cardinality of a subset of $\mathcal{T}_\kappa$ of the largest size such that all its elements are mutually embeddable?

I am particularly interested in cases where $\kappa$ is $\aleph_0$, $\aleph_1$ and $\mathfrak{c}$.

share|improve this question
I think that the more interesting question is to ask about linear orders in the poset that you get when factoring out the quasiorder by bi-embeddability (as suggested in Noah S's answer). –  Goldstern Aug 13 '13 at 17:17
Related question: math.stackexchange.com/questions/459258/… –  Vladimir Reshetnikov Aug 17 '13 at 18:35
add comment

3 Answers

If you only consider countable linear orders, then for example the order types $\eta+2+\eta+2+\eta+3+\eta+\cdots$ and $\eta+3+\eta+2+\eta+3+\eta+\cdots$ are not isomorphic. (Where $\eta$ is the order type of the rationals.)

This way you can get continuum many nonisomorphic orders, any two of which are bi-embedable. You can linearly order them in any way you want.

ADDED: As Joel points out in his comment, this can be generalized to cardinals $\kappa$ satisfying $\kappa^{<\kappa}=\kappa$ as follows:

Use the assumption $\kappa^{<\kappa}=\kappa$ to find a universal linear order of size $\kappa$ (i.e., one into which any other such order embeds). Without loss of generality you may assume that this order is dense; let us call this order $H$ (capital eta). Now consider well-ordered sums of length $\kappa$ in which $H$ alternates with 2-element and/or 3-element linear orders. All these orders will be non-isomorphic, because the places where the 2's and 3's appear can be recovered from the abstract order type, using the fact that $H$ is dense.

There are $2^\kappa$ many of these order types, and they are pairwise bi-embeddable.

(I previously wrote $2^{<\kappa}=\kappa$ instead of $\kappa^{<\kappa}=\kappa$, but it is not obvious that this assumption suffices.)

share|improve this answer
This same idea works for any $\kappa$ with $\kappa^{\lt\kappa}=\kappa$, and in particular for every infinite regular $\kappa$ under the GCH. –  Joel David Hamkins Aug 12 '13 at 18:47
...what I mean is to replace $\eta$ with a dense order that is universal for all orders of size $\kappa$, and then look at $\kappa$-length sums of this order interspersed with either $2$ or $3$ so as to code a given subset of $\kappa$. –  Joel David Hamkins Aug 12 '13 at 19:02
Can you get a $\kappa$-universal order of size $\kappa$ just from $2^{\lt\kappa}=\kappa$, or do you need $\kappa^{\lt\kappa}=\kappa$? –  Joel David Hamkins Aug 12 '13 at 19:12
At least not obviously. My mistake. –  Goldstern Aug 12 '13 at 19:35
It is required for a saturated order, by an argument that embeds $\kappa^{\lt\kappa}$ into the given saturated order---as Jiachen recently explained to me in Shanghai---but I don't quite recall now if one needs it for mere universality, and I'm inclined to think it is... –  Joel David Hamkins Aug 12 '13 at 20:25
show 4 more comments

(Really a comment, but too long:)

If you strengthen your first question to demand that the subset actually be linearly ordered by $\prec$ (that is, strict chains) - which rules out, for example, Goldstern's construction - then the answer is different.

In the case $\kappa=\aleph_0$, we can divide the countable ordertypes into the scattered (does not embed $\eta$) and unscattered cases. Since unscattered linear orders all embed $\eta$, any countable linear order embeds into any countable unscattered order, so in any strict chain $C$, at most one unscattered order occurs, and if it occurs it occurs as the maximal element. So the question reduces to how long a strict chain of scattered orders can be.

Clearly there are strict chains of cardinality $\aleph_1$ (e.g., the countable ordinals). This answers the question fully, in case $2^{\aleph_0}=\aleph_1$, since there are exactly continuum many isomorphism types of countable linear orders. Now, I believe that this can be extended to the case where $CH$ fails - that is, no matter what the value of the continuum, strict chains of ordertypes under embeddability have cardinality $\le\aleph_1$ - as follows: there is a way of assigning a countable ordinal to a countable scattered linear order, called the Hausdorff rank of the linear order, and it can be shown (I believe) by induction on rank that any strict chain of (countable scattered) linear orders of bounded rank is countable. It then follows that the maximum cardinality of a strict chain of scattered countable linear orders (and hence countable linear orders) is $\aleph_1$. What this means, concretely, is that we can have universes of ZFC in which there are no strict chains of countable linear orders of length continuum.

Even better, this actually shows that for any strict chain $\mathcal{C}$, we have $$ \omega_1+2\not\prec \mathcal{C},$$ which is better than just a cardinality bound.

I have no idea what happens in the case $\kappa>\aleph_0$, if we look at strict chains.

CAVEAT: this is all just a sketch, and it may well be wrong; it's been a while since I've looked at this stuff.

share|improve this answer
add comment

You seem to be asking: what is the cardinality of the longest chain (under embeddability) of orders of size $\kappa$. Since there are $2^\kappa$ many orders of size $\kappa$, the cardinality of the longest chain is of course $2^\kappa$. And furthermore, this bound is achievable.

For example, when $\kappa=\aleph_0$, then consider the chain consisting of cuts in the rational line. There are continuum many such orders, and each smaller one is a suborder of each larger one. So we've got a chain of cardinality continuum.

More generally, if $2^{{\lt}\kappa}=\kappa$, then you may consider the tree $2^{{\lt}\kappa}$ under the lexical order, where again we have $2^\kappa$ many cuts, and then again we find a chain of size $2^\kappa$ under embeddability. So under the GCH, we attain the largest possible cardinalities for every infinite $\kappa$. I think there are some interesting things to say when GCH fails.

(But I wonder whether you really want to ask about the order types of the chains, rather than merely the cardinality...)

share|improve this answer
Do you count linear orders or linear order types? It looks like all possible cuts in the rational line result only in a finite number of order types. –  Vladimir Reshetnikov Aug 12 '13 at 18:33
Ah, perhaps that is what the OP meant? If so, this answer doesn't suffice. –  Joel David Hamkins Aug 12 '13 at 18:36
Yes, I was asking of linear order types (equivalence classes under order isomorphism). –  Oksana Gimmel Aug 12 '13 at 18:39
OK, let me modify my answer. –  Joel David Hamkins Aug 12 '13 at 18:39
But as I was editing, I see that Goldstern posted an answer with the same idea... –  Joel David Hamkins Aug 12 '13 at 18:46
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.