3
$\begingroup$

If two sets are well ordered, then one of them is isomorphic to the subset of another.

Is the same true for totally (or linearly) ordered sets? I think it is probably not true, but I struggle to find counterexamples of it.

So, my goal is: to find two totally ordered sets such that neither of them is isomorphic to the subset of another.

Or can we find more than two ($\geq 3$) of such sets? i.e. finding three totally ordered sets, such that none of them is isomorphic to the subsets of any one of the other two.

My thought is pretty restrictive at the moment because the only totally ordered set I can think of now is subsets of $\mathbb R$, which doesn't help solve the problem.

$\endgroup$
  • 2
    $\begingroup$ Another example: $\mathbb R$ and $\omega_1$. $\endgroup$ – Andrés E. Caicedo Nov 15 '19 at 2:24
4
$\begingroup$

For two sets you can take $\omega$ (i.e. the natural numbers as an ordinal) with the usual order and $\omega^*$, which is the same set with the reverse order. If one would be order-isomorphic to a subset of the other you would have an infinite descending chain in $\omega$, which cannot happen in an ordinal.

For three sets, you can take $\omega_1$ (the first uncountable ordinal), $\omega + \omega^*$ (i.e. the concatenation) and $\omega^* + \omega$. Clearly, $\omega_1$ cannot be injected in the other two due to cardinality. If one of $\omega + \omega^*$ and $\omega^* + \omega$ would be order-isomorphic to a subset of $\omega_1$ we would again obtain an infinite descending chain in an ordinal. So we are left to check that $\omega + \omega^*$ cannot be order-isomorphic to a subset in $\omega^* + \omega$ (the other case is symmetric). Suppose there is such an injection, then the image of $\omega$ under this injection cannot be contained in $\omega^*$ (i.e. the first half of $\omega^* + \omega$), but then the image of $\omega^*$ would be contained in $\omega$ (i.e. the second half of $\omega^* + \omega$), which gives a contradiction.

$\endgroup$
  • $\begingroup$ What about finding three or more such sets? $\endgroup$ – Ma Joad Nov 15 '19 at 0:41
  • $\begingroup$ @Jethro Well, the trick works for any two infinite ordinals $\alpha$ and $\beta$ by considering one with the reverse order. So that gives a proper class of examples. $\endgroup$ – Mark Kamsma Nov 15 '19 at 0:43
  • $\begingroup$ I am sorry. Let me clarify: finding three totally ordered sets, such that none of them is isomorphic to the subsets of any one of the other two. $\endgroup$ – Ma Joad Nov 15 '19 at 0:47
  • $\begingroup$ @Jethro I edited with an example of three such sets. $\endgroup$ – Mark Kamsma Nov 15 '19 at 0:58
4
$\begingroup$

For $n\in\mathbb N$ here is an easy example of $2^n$ pairwise incomparable countable order types: the types of the form $\varphi_1+\varphi_2\cdots+\varphi_n$ where each $\varphi_i$ is either $\omega$ or $\omega^*$, i.e., the order type of the positive integers or the negative integers.

That's the best (or worst) you can do with countable order types: Riohard Laver proved that the countable order types are well-quasi-ordered by embeddability, meaning that for any infinite sequence $A_1,A_2,\dots$ of countable totally ordered sets, $A_i$ is embeddable in $A_j$ for some $i\lt j$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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