11
$\begingroup$

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?

  • 2
    A related question: http://math.stackexchange.com/questions/174043/is-pmb1-pmb-eta-cdot-pmb-omega-1-pmb1-pmb-eta-cdot-pmb-o2012-07-23
  • 5
    This question would be well placed at mathoverflow.2012-07-23
  • 2
    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](http://en.wikipedia.org/wiki/Back-and-forth_method)); and b) an uncountable q-like order type has no maximum, since otherwise the initial segment it determines would be uncountable.2012-07-23

1 Answers 1

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.

  • 0
    You meant to say "There is a large number ..." in the first line, no? :-)2012-07-23
  • 0
    @Asaf: Both versions are idiomatic.2012-07-23
  • 0
    @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...2012-07-23
  • 0
    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 http://english.stackexchange.com.2012-07-23
  • 0
    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](http://math.stackexchange.com/questions/174043/is-pmb1-pmb-eta-cdot-pmb-omega-1-pmb1-pmb-eta-cdot-pmb-o), but I don't quite see it.2012-07-23
  • 0
    Every function $g:\omega_1\to\omega_1$ has a closed unbounded set of closure points, that is, $\beta$ such that $g[\beta]\subset\beta$. The set of such $\beta$ is clearly closed under limits, and to see that it is unbounded, just iterate $\omega$ many times and take a supremum. That is, $\beta_0$ is arbitrary, $\beta_{n+1}=\sup g[\beta_n]+1$ and then $\beta=\sup_n\beta_n$ exhibits the desired closure. The same idea works for $f$ on the long rational line, by considering the ordinals associated with each unit interval.2012-07-23
  • 0
    Thanks! My proof had a gap, but I started out with the same idea of the sets $\mathcal Q_A$. In fact it seems that with uncountable choice all q-like orders are isomorphic to one of these, since we can construct $A$ transfinitely by at each stage $\alpha$ picking an arbitrary remaining element, removing everything below it and adding $\alpha$ to $A$ if the removed set had a first element. Is that right?2012-07-23
  • 0
    Yes, I agree with that. Another way to do it is just to pick any $\omega_1$ ordered subset of your order, and then $A$ is determined by whether the limits points exist in the order or not.2012-07-23
  • 0
    I edited my answer to ensure in the theorem also that $A$ and $B$ agree on $0$, to ensure that $\mathcal{Q}_A$ and $\mathcal{Q}_B$ either both have a minimal element or neither, which gets the transfinite recursion started.2012-07-24
  • 0
    @JDH - in the definition of $\mathcal{Q}_A$, shouldn't we use $\cap$? also, how does it select just one element from $(0,\alpha)$?2013-05-07