10
$\begingroup$

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}$.

$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – Goldstern
    Aug 13, 2013 at 17:17
  • 2
    $\begingroup$ Related question: math.stackexchange.com/questions/459258/… $\endgroup$ Aug 17, 2013 at 18:35

3 Answers 3

8
$\begingroup$

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.)

$\endgroup$
9
  • $\begingroup$ This same idea works for any $\kappa$ with $\kappa^{\lt\kappa}=\kappa$, and in particular for every infinite regular $\kappa$ under the GCH. $\endgroup$ Aug 12, 2013 at 18:47
  • $\begingroup$ ...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$. $\endgroup$ Aug 12, 2013 at 19:02
  • 1
    $\begingroup$ Can you get a $\kappa$-universal order of size $\kappa$ just from $2^{\lt\kappa}=\kappa$, or do you need $\kappa^{\lt\kappa}=\kappa$? $\endgroup$ Aug 12, 2013 at 19:12
  • $\begingroup$ At least not obviously. My mistake. $\endgroup$
    – Goldstern
    Aug 12, 2013 at 19:35
  • $\begingroup$ 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... $\endgroup$ Aug 12, 2013 at 20:25
2
$\begingroup$

(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.

$\endgroup$
1
$\begingroup$

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...)

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 12, 2013 at 18:33
  • $\begingroup$ Ah, perhaps that is what the OP meant? If so, this answer doesn't suffice. $\endgroup$ Aug 12, 2013 at 18:36
  • $\begingroup$ Yes, I was asking of linear order types (equivalence classes under order isomorphism). $\endgroup$ Aug 12, 2013 at 18:39
  • $\begingroup$ OK, let me modify my answer. $\endgroup$ Aug 12, 2013 at 18:39
  • $\begingroup$ But as I was editing, I see that Goldstern posted an answer with the same idea... $\endgroup$ Aug 12, 2013 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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