2
$\begingroup$

Two ordered sets have the same order type if there exists an order-preserving bijection between them whose inverse is also order-preserving. My question is, what are the order types of all the total orders on the set of natural numbers.

Can you start with all the countable ordinals, as well as the order type of the rational numbers, and then construct all the order types using order type addition, order type multiplication, and the dual operation? Or is there some total order on $\mathbb{N}$ whose order type cannot be constructed in this way?

$\endgroup$

2 Answers 2

1
$\begingroup$

This isn't a full answer, but classifying total orders on $\mathbb N$ is the same as classifying countable total orders (since we don't use any structure on $\mathbb N$ except the set itself).

Now, any countable total order is order-isomorphic to a subset of $\mathbb Q$ with its natural order. A proof can be found here.

$\endgroup$
4
  • $\begingroup$ I said "Can you start with all the countable ordinals, as well as the order type of the rational numbers, and then construct all the order types using order type addition, order type multiplication, and the dual operation?" So the starting point already includes one dense total order. $\endgroup$ Sep 30, 2018 at 15:45
  • $\begingroup$ @KeshavSrinivasan Indeed, I missed that. $\endgroup$
    – lisyarus
    Sep 30, 2018 at 16:19
  • $\begingroup$ So now do you think the answer to my second question is yes or no? $\endgroup$ Sep 30, 2018 at 18:52
  • $\begingroup$ While correct, I don't think this answers the question of what order types are possible. Clearly every countable ordinal is, but we can put in descending chains as well. $\endgroup$ Oct 2, 2018 at 22:27
1
$\begingroup$

[It seems to me that the order type of $\mathbb{Q} \sqcup 2 \sqcup \mathbb{Q} \sqcup 2 \sqcup ...$ does not fall in this category.] edit: as you pointed out, it does on the contrary. In fact, only $\aleph_1$ many order types can be constructed using your conditions, "while" there are $2^{\aleph_0}$ countable linear order types.

Indeed, for each binary sequence $u: \mathbb{N} \rightarrow \{0;1\}$, consider the transfinite sum $L_u= \sum \limits_{n\in \mathbb{N}} Q_{u(n)}$ where $Q_1= \mathbb{Q}+\mathbb{Z}$ and $Q_0 = 2$. I would say that $L_u$ can be constructed using your rules iff $u$ is eventually periodic, but a proof would require a bit of care. Perhaps a form of "pumping lemma" would apply here.

$\endgroup$
6
  • $\begingroup$ Isn't the order type you're describing just $(\rho+2)\omega$ where $\rho$ is the order type of the rational numbers? $\endgroup$ Oct 2, 2018 at 19:52
  • $\begingroup$ Indeed! However, using non eventually periodic binary sequences will yield order types outside of your "rational category". $\endgroup$
    – nombre
    Oct 2, 2018 at 20:36
  • $\begingroup$ What do you mean by a total order generated by a binary sequence? $\endgroup$ Oct 2, 2018 at 20:40
  • $\begingroup$ I added more information, but so far this is not a proof (at least without HC). $\endgroup$
    – nombre
    Oct 2, 2018 at 21:02
  • $\begingroup$ Why couldn't you make $Q_1=\mathbb{Z}$ and $Q_0=1$, wouldn't that make things simpler? Also, assuming your example is valid, what if I added "countable sum" to my list of operations, then would it suffice to produce all the order types? $\endgroup$ Oct 2, 2018 at 21:35

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.