# Linearly ordered sets “somewhat similar” to $\mathbb{Q}$

Let's say that a linear order type is q-like if every proper initial segment of an instance of this type is order-isomorphic to $\pmb{\eta}$ or $\pmb{\eta}+\pmb{1}$. For example, $\pmb{\eta}$, $\pmb{\eta}+\pmb{1}$, $\pmb{\eta}\cdot\pmb{\omega_1}$ and $\pmb{\eta}+(\pmb{1}+\pmb{\eta})\cdot\pmb{\omega_1}$are q-like.

Question: How many distinct q-like order types exist?

-
A related question: math.stackexchange.com/questions/174043/… –  Vladimir Reshetnikov Jul 23 '12 at 3:39
This question would be well placed at mathoverflow. –  JDH Jul 23 '12 at 13:58
Two things we know: a) $\pmb{\eta}$ and $\pmb{\eta}+\pmb{1}$ are the only countable q-like order types (since the order type of a countably finite densely ordered set depends only on the (non-)existence of a minimum or a maximum, see Wikipedia); and b) an uncountable q-like order type has no maximum, since otherwise the initial segment it determines would be uncountable. –  joriki Jul 23 '12 at 16:14

This is a great question!

There are a large uncountable number of these orders.

Consider as a background order the long rational line, the order $\mathcal{Q}=([0,1)\cap\mathbb{Q})\cdot\omega_1$. For each $A\subset\omega_1$, let $\mathcal{Q}_A$ be the suborder obtained by keeping the first point from the $\alpha^{\rm th}$ interval whenever $\alpha\in A$, and omitting it if $\alpha\notin A$. That is,

$$\mathcal{Q}_A=((0,1)\cap\mathbb{Q})\cdot\omega_1\ \cup\ \{(0,\alpha)\mid\alpha\in A\}.$$

This corresponds to adding $\omega_1$ many copies of $\eta$ or $1+\eta$, according to the pattern specified by $A$ as a subset of $\omega_1$.

I claim that the isomorphism types of these orders, except for the question of a least element, correspond precisely to agreement-on-a-club for $A\subset\omega_1$.

Theorem. $\mathcal{Q}_A$ is isomorphic to $\mathcal{Q}_B$ if and only if $A$ and $B$ agree on having $0$ and also agree modulo the club filter, meaning that there is a closed unbounded set $C\subset\omega_1$ such that $A\cap C=B\cap C$. In other words, this is if and only if $A$ and $B$ agree on $0$ and are equivalent to $B$ in $P(\omega_1)/\text{NS}$, as subsets modulo the nonstationary ideal.

Proof. If $A$ and $B$ agree on $0$ and agree on a club $C$, then we may build an isomorphism between $\mathcal{Q}_A$ and $\mathcal{Q}_B$ by transfinite induction. Namely, for each $\alpha\in C$, we will ensure that $f$ restricted to the cut below $(0,\alpha)$ is an isomorphism of the segment in $\mathcal{Q}_A$ to that in $\mathcal{Q}_B$. The point is that $(0,\alpha)$ is actually a point in $\mathcal{Q}_A$ if and only if it is point in $\mathcal{Q}_B$, and so these points provide a common frame on which to carry out the transfinite recursion. If we have an isomorphism up to such a point, we can continue it to the next point, since this is just adding a copy of $\eta$ or of $1+\eta$ on top of each (the same for each), and at limits we take the union of what we have built so far, which still fulfills the property because $C$ is closed. So $\mathcal{Q}_A\cong\mathcal{Q}_B$.

Conversely, if $f:\mathcal{Q}_A\cong\mathcal{Q}_B$, then $A$ and $B$ must agree on $0$. Let $C$ be the set of closure ordinals of $f$, that is, the set of $\alpha$ such that $f$ respects the cut determined by the point $(0,\alpha)$. This set $C$ is closed and unbounded in $\omega_1$. Furthermore, it is now easy to see that $(0,\alpha)\in \mathcal{Q}_A$ if and only if $(0,\alpha)\in \mathcal{Q}_B$ for $\alpha\in C$, since this point is the supremum of that cut, and it would have to be mapped to itself. Thus, $A\cap C=B\cap C$ and so $A$ and $B$ agree modulo the club filter. QED

Corollary. There are $2^{\aleph_1}$ many distinct q-like linear orders up to isomorphism.

Proof. The theorem shows that there are as many different q-like linear orders as there are equivalence classes of subsets of $\omega_1$ modulo the non-stationary ideal. So the number of such orders is $|P(\omega_1)/\text{NS}|$. This cardinality is $2^{\aleph_1}$ because we may split $\omega_1$ into $\omega_1$ many disjoint stationary sets, by a theorem of Solovay and Ulam, and the union of any two distinct subfamilies of these differ on a stationary set and hence do not agree on a club.

So there are at least $2^{\aleph_1}$ many distinct q-like orders up to isomorphism, and there cannot be more than this, since every such order has cardinality at most $\omega_1$. QED

Finally, let me point out, as Joriki mentions in the comments, that every uncountable q-like linear order is isomorphic to $\mathcal{Q}_A$ for some $A$. If $L$ is any such order, then select an unbounded $\omega_1$ sequence in $L$, containing none of its limits, chop $L$ into the corresponding intervals these elements and define $A$ according to whether these corresponding intervals have a least element or not. Thus, we have a complete characterization of the q-like linear orders: the four countable orders, and then the orders $\mathcal{Q}_A$ with two $A$ from each class modulo the nonstationary ideal, one with $0$ and one without.

-
You meant to say "There is a large number ..." in the first line, no? :-) –  Asaf Karagila Jul 23 '12 at 21:16
@Asaf: Both versions are idiomatic. –  Brian M. Scott Jul 23 '12 at 21:20
@Brian. Hmm, I see. I suppose I can live with that, but using "are a ..." seems weird to me. On the other hand, "many a ..." used to seem strange several years ago too... –  Asaf Karagila Jul 23 '12 at 21:22
I would say, "there are a large number of people in the room." But I don't think I would say, "there is a large number of people in the room." But somehow the adjective "uncountable" throws off one's grammatical sense. Perhaps it is a question for english.stackexchange.com. –  JDH Jul 23 '12 at 21:30
Could you please explain why the set of closure ordinals of $f$ is closed and unbounded? It seems this is related to the answers to this question, but I don't quite see it. –  joriki Jul 23 '12 at 22:14