Regarding the "smallest" nontrivial, dense order type.

196 Views Asked by At
  1. Is $\eta$, the order type of the rationals, necessarily the smallest nontrivial, dense order type?

By "smallest" I mean that there is no dense order which embeds into $\eta$, into which $\eta$ does not embed. Note that the left/right/total closure of $\eta$ will also have this property, so $\eta$ won't be unique in this regard; what matters is whether or not there can be a dense order strictly smaller than $\eta$.

Obviously, the smallest dense order is $0$ (because "$(\forall x,y\in\emptyset)(\exists z\in\emptyset)(x<z<y)$" holds vacuously), and any finite order type larger than $0$ is sparse. I just want to be sure that every smaller [nontrivial] order type is necessarily sparse, and that there isn't some bizarre order type $\tau$ which is provably dense, and which provably embeds into $\eta$, for which "$\eta$ embeds into $\tau$" cannot be proven.

  1. Is the non-existence of a dense order type $\kappa$, such that $\eta<\kappa<\lambda$, where $\lambda$ is the order type of the reals, such that $\kappa$ is not the sum of countably-many copies of $\eta$ (or closures thereof), equivalent to the continuum hypothesis?

I suspect that there may be dense, countable order types into which $\eta$ embeds which do not embed into $\eta$. However, I imagine that every such order type is of the form $\sum_{i\in\varphi_\flat(\omega_{0^\star}^{\spadesuit})}\eta_i$, where each $\eta_i$ is either $\eta$ itself or a closure of $\eta$, and $\varphi_\flat(\omega_{0^\star}^\spadesuit)$ is "some stupid-large countable ordinal." So it stands to reason that if there are any other dense orders between $\eta$ and $\lambda$ they must be inaccessible from below. The only way I can see this happening is if $\kappa$ contains more than countably many points, but fewer than continuum many points - which is the negation of the continuum hypothesis. But there might be some other way to get dense orders $<\lambda$ besides pasting together copies of $\eta$, in which case there might still be countable, dense order types which are strictly larger than $\eta$ independently of CH. Intuitively, I would think the exclusion of sums is equivalent to the non-existence of $\kappa$ with the same number of limit points ($2$) as $\eta$ and $\lambda$. If this is the case, it might be easier to show equivalence with CH.

2

There are 2 best solutions below

2
On BEST ANSWER

It's easy to see that $\eta$ embeds into any nontrivial dense linear order $J$ (of any cardinality whatsoever), at least assuming the axiom of choice: we can just use a "greedy algorithm" to embed $\eta$ into $J$ by well-ordering the elements of $\eta$ and sending the $i$th rational in this well-ordering to some element of $J$ which "fits the pattern so far" (this is where density of $J$ is used). In more detail, let $\eta=\{q_i:i\in\mathbb{N}\}$, let $J=\{\alpha_\mu: \mu\in\kappa\}$, and recursively define a map $F:\eta\rightarrow J$ by sending $q_i$ to $\alpha_\mu$ where $\mu$ is the least element of $\kappa$ satisfying $$\forall j<i[F(q_j)<\alpha_\mu\iff q_j<q_i].$$ The existence, for each $i$, of such a $\mu$ uses the density of $J$.

(Actually, technically there's a gap here: we need to assume that $J$ has no endpoints. But we can do this WLOG: just remove any endpoints that $J$ may have before starting the construction!)

In fact, this same argument shows that every countable linear order whatsoever embeds into $\eta$. To give a bit more detail, given a countable linear order $L=\{l_i:i\in\mathbb{N}\}$, we recursively define an embedding $F:L\rightarrow\eta$ by setting $F(l_i)$ to be the lexicographically-least rational $q$ satisfying $$\forall j<i[l_j<_Ll_i\iff F(l_j)<q].$$ The existence of such a $q$ at each stage is where density of $\eta$ (+ absence of endpoints) is used. Note that this is only half of a "back-and-forth" argument; building isomorphisms, rather than just embeddings, in related situations often require thinking about both directions simultaneously.

Putting everything together, this means that any two countable dense nontrivial linear orders are bi-embeddable. It's worth noting that bi-embeddability is a much coarser relation than isomorphism; for example, there are continuum-many scattered (= do not contain a copy of $\eta$) countable linear orders up to isomorphism, but only $\aleph_1$-many up to bi-embeddability, and it's consistent with $\mathsf{ZFC}$ that $\aleph_1<\mathfrak{c}$. See this old MSE question.

(And the axiom of choice is necessary here, since in $\mathsf{ZF}$ alone there may be nontrivial dense sets of reals which are incomparable with $\eta$ with respect to embeddability; this happens in Cohen's original model of $\mathsf{ZF+\neg AC}$, for instance.)

3
On

There's a lot of overlap between my answer and Noah's, but I'm posting it anyway, because addresses your second question and contains some additional points about your first question.

A few comments first:

(a) The empty linear order is not the only finite dense linear order: the one-element linear order is also dense. This is because "density" means $\forall x\forall x\, (x<y\to \exists z\, x < z < z)$. This axiom is satisfied in the one-element linear order, since there are no $x$ and $y$ with $x < y$ in this order. However, it is true that any dense linear order with at least two elements is infinite.

(b) Disregarding these two finite dense linear orders, let's write $\leq$ for the embeddability preorder on the class of infinite dense linear orders, i.e., $L\leq L'$ iff $L$ embeds in $L'$. Like any preorder, $\leq$ induces an equivalence relation $\sim$, by $L\sim L'$ iff $L\leq L'$ and $L'\leq L$.

Then you write:

By "smallest" I mean that there is no dense order which embeds into $\eta$, into which $\eta$ does not embed.

i.e., for all $L$, if $L\leq \eta$, then $\eta \leq L$ (and hence $\eta\sim L$). This notion should be called "minimal". The term "smallest" or "minimum" usually means: for all $L$, $\eta \leq L$. Note that this is a stronger sense of "smallest": a minimum element of a preorder is automatically a minimal element, but not conversely.

(c) You write "I suspect that there may be dense, countable order types into which $\eta$ embeds which do not embed into $\eta$." No, in fact every countable linear order $L$ embeds in $\eta$. (There is no hypothesis on $L$ other than countability, i.e., $L$ need not be dense, and $\eta$ need not embed in $L$.) This is a simple "forth" argument: Enumerate $L$ as $(a_i)_{i\in \omega}$ and build a function $L\to \eta$ by recursion, mapping each new element to an element of $\eta$ that sits in the correct place relative to the images of the previous elements.


Now to address your questions.

(1) In fact, $\eta$, the order type of the rationals, is not just minimal (i.e., "smallest" in your sense), it is actually smallest in the stronger sense mentioned above.

Proof: Let $L$ be an infinite dense linear order. Removing the endpoints (if $L$ has a greatest or least element), we obtain $L'$, an infinite dense linear order without endpoints. By Löwenheim-Skolem, $L'$ has a countably infinite elementary substructure $L''$, which is again a dense linear order without endpoints. By Cantor's theorem, $L''$ is isomorphic to $\eta$. This isomorphism gives an embedding $\eta\to L$, so $\eta \leq L$.

(2) By the discussion above, there is definitely no countable "intermediate order type" $\kappa$. So your stipulation "such that $\kappa$ is not the sum of countably-many copies of $\eta$ (or closures thereof)" is unnecessary, since any such countable union of countable orders will be countable, and hence equivalent to $\eta$. But there are intermediate order types of cardinality $2^{\aleph_0}$.

In this MathOverflow answer by Joel David Hamkins, a construction is given of a dense set $A\subseteq \mathbb{R}$ of cardinality $2^{\aleph_0}$ such that there is no non-identity order-preserving map $A\to A$. It follows that there is no embedding $f\colon \mathbb{R}\to A$, since the restriction $f|_A\colon A\to A$ would be a non-identity order preserving map.

Thus, we can prove (without assuming CH) that there is an order type $\kappa$ (the order type of the set $A$) such that $\eta < \kappa < \lambda$, where $\lambda$ is the order type of $\mathbb{R}$. We have $\eta\leq \kappa$ by (1) since $\kappa$ is dense, but $\kappa\not\leq\eta$ because of its cardinality. And we have $\kappa\leq \lambda$ since $A\subseteq \mathbb{R}$, but $\lambda\not\leq\kappa$ as shown above.