Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
A related question:… – 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
up vote 13 down vote accepted

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.

share|cite|improve this answer
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 – 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

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.