As is well-known, ZFC proves the equipotency of $\mathbb{R}$ and $\mathcal{P}(\mathbb{Q}).$ Is there a nice characterization of those linearly ordered sets $L$ which, like $\mathbb{Q}$, have the property that their completion by Dedekind-cuts $\mathcal{C}(L)$ is equipotent with their powerset $\mathcal{P}(L)$?

Edit. At the risk of introducing a non-standard concept into a perfectly standard question, I am especially interested in the case where $L$ is unbounded and "locally homogeneous," in the sense that for all $x,y \in L$ and all $x',y' \in L,$ we have that if $x<y$ and $x'<y'$, then the interval $(x,y)$ is isomorphic to the interval $(x',y')$. (The purpose of this condition is just to cut out all the crazy mish-mash orders involving mixtures of scattered and dense linear orders with complete and incomplete segments all smashed together into some crazy pattern. See Arthur's answer here for an example of a homogeneous order different from $\mathbb{R}$ and $\mathbb{Q}$).

  • 1
    $\begingroup$ I think we can prove the following: Let $L$ be a countable linear order. Then $L$ has a subset isomorphic to $\mathbb{Q},$ iff the completion of $L$ has size continuum. $\endgroup$ Mar 31, 2014 at 11:51
  • $\begingroup$ Well, you didn't say whether you are more interested in various countable orderings - then I think Mohammad is correct, or in possible cardinalities of such sets - the latter case is more complicated and it is related to the possible sizes of almost disjoint families of subsets of $X$ (A family $F$ of subsets of $X$ is almost disjoint if for every $A\neq B$ in $F$ we have $|A|=|B|=|X|$ but $|A\cap B|<|X|$). $\endgroup$ Mar 31, 2014 at 12:21
  • $\begingroup$ @AdamPrzezdziecki, thanks for your input. I edited to clarify my interests, although at the risk of making the question far more complicated than it truly needs to be. $\endgroup$ Mar 31, 2014 at 13:07
  • $\begingroup$ In Arthur's example, which is the long rational line, the Dedekind completion is the long line, which has size continuum, and this is not $2^{\omega_1}$ if CH holds, so it is not actually an instance of the kind of order you seek. $\endgroup$ Mar 31, 2014 at 14:02
  • $\begingroup$ @JoelDavidHamkins, sure, but that question wasn't about the cardinality of the completion of totally ordered sets. I'm pretty sure Arthur's example is correct, insofar as being a locally homogeneous unbounded order that isn't globally homogeneous. $\endgroup$ Mar 31, 2014 at 14:18

2 Answers 2


This is a complement to Joel's answer. For uncountable orders, I don't think there will be a nice characterization in terms of embedding a canonical suborder, at least without some assumption about cardinal arithmetic, even if one only considers orders that are locally homogeneous. I'll argue that it's consistent that there are locally homogeneous orders $L_1, L_2$ of size $\aleph_1$ whose completions are of size $2^{\aleph_1}$ but that have the property that no uncountable order $X$ embeds into both $L_1$ and $L_2$.

First we need some preliminary facts. In general, if $L$ is uncountable, it falls into one of three categories:

1) $L$ embeds a copy of either $\omega_1$ or $-\omega_1$ (or both),

2) $L$ does not embed either $\omega_1$ or $-\omega_1$ but embeds an uncountable suborder of $\mathbb{R}$,

3) $L$ does not embed $\omega_1$, $-\omega_1$, or any uncountable suborder of $\mathbb{R}$.

The first is the broadest of the three categories, and I don't have much to say about it. The second and third have been widely studied, however. Lines of type 3 are called Aronszajn lines. They exist in ZFC, and it's relatively straightforward to show they necessarily have size $\aleph_1$. It follows that since they do not embed either $\omega_1$ or its reverse, that all of their gaps can be approached by countable sequences, and consequently their Dedekind completions always have size $[\omega_1]^{\omega}=2^{\aleph_0}$. Thus their completions will have the size of their powerset if and only if $2^{\aleph_0} = 2^{\aleph_1}$.

Lines of type 2 in general can be of size larger than $\aleph_1$. Yet it's possible to show, by a slightly more complicated argument, that their completions must also have size $2^{\aleph_0}$. So again, they will have the desired property iff $2^{|L|} = 2^{\aleph_0}$.

Now, as to the original claim: assume MA + $2^{\aleph_0}=\aleph_2$ + ``all $\aleph_1$-dense sets of reals are order-isomorphic." It's a result of Baumgartner that this is consistent relative to ZFC. Then $2^{\aleph_0}=2^{\aleph_1}=\aleph_2$. Let $L_1$ be any $\aleph_1$-dense subset of $\mathbb{R}$. Then in particular, since every open subinterval of $L_1$ will also be $\aleph_1$-dense, $L_1$ will be locally homogeneous.

We let $L_2$ be a particular type of Aronszajn line, called an $\aleph_1$-dense nonstationary Countryman line. The actual properties of such lines are irrelevant for our purposes except that they are Aronszajn and, by a result of Todorcevic, are isomorphic under MA$_{\aleph_1}$ to their restriction to every open interval (and so locally homogeneous).

Then $L_1$ and $L_2$ are as claimed. Both have size $\aleph_1$, and their completions are both of size $2^{\aleph_1}$. Further, there can be no uncountable order $X$ that embeds into both $L_1$ and $L_2$, since that would yield an uncountable suborder of $L_2$ isomorphic to an uncountable suborder of $\mathbb{R}$, contradicting the definition of being Aronszajn.

The relevant references are:

Baumgartner, "All $\aleph_1$-dense sets of reals can be isomorphic," Fund. Math. 79 (1973) 101-106;

Todorcevic, Walks on ordinals and their characteristics, Vol. 263 of Progress in Mathematics, Birkhäuser (2007).


For countable linear orders, there is a nice characterization, which I see is conjectured in the comments.

Theorem. The following are equivalent for a countable linear order $\langle L,\lt\rangle$.

  1. The Dedekind completion of $L$ has size continuum.

  2. The Dedekind completion of $L$ is uncountable.

  3. $L$ contains a copy of $\mathbb{Q}$.

Proof. Clearly $3\to 1\to 2$, so it remains to see that $2\to 3$. Suppose $L$ is countable, but has an uncountable Dedekind completion. Let's build a copy of $\mathbb{Q}$ in $L$ directly. Since the completion of $L$ has no increasing or decreasing $\omega_1$ sequence, there must be two nodes $a_0<a_1$ in $L$, such that the interval between them has an uncountable Dedekind completion. Continuing, we may find $a_{\frac12}$ between them, such that both intervals $[a_0,a_{\frac12}]$ and $[a_{\frac12},a_1]$ have uncountable Dedekind completion. Thus, by induction, we may construct a countable dense suborder of $L$, and so $\langle L,\lt\rangle$ contains a copy of $\mathbb{Q}$. QED

In the uncountable case, things are little more complicated. For example, there are complications caused by GCH-type issues. If $2^\omega=2^{\omega_1}$, then already a countable suborder of a linear order $L$ of size $\omega_1$ is sufficient to make the Dedekind completion have size $2^{\omega_1}$, since if $\mathbb{Q}$ is there the completion will have size continuum. In general, for orders of size $\delta$, one should look at the smallest $\kappa\leq\delta$ for which $2^\kappa>\delta$. There are some basis theorems for uncountable orders that will probably be useful.

Edit. I removed the previous second, alternative, proof of the theorem, which had appealed to the Cantor-Bendixson derivatives, because it doesn't actually work the way that I had claimed. For example, if $L$ is $\mathbb{Q}$ copies of $\mathbb{Z}$, then every point in $L$ is isolated, cast out on the first step, yet the Dedekind completion is still uncountable and there is still a copy of $\mathbb{Q}$ in $L$.

  • $\begingroup$ It is possible to use an order-theoretic "derivative" to prove this: identify two points of L if the interval between them is finite. Do the same on the quotient L', etc. After $\alpha<\omega_1$ steps you either you have found a homomorphic image $\mathbb Q$ (representatives will again have order type $\mathbb Q$), or the order was scattered and you end up with a finite order. In going from L to L' you lose only countably many unfilled cuts: some unfilled cuts $C$ in L (i.e., without supremum) may have an image which is filled by an element $x_C$ of L', but the map $C\mapsto x_C$ is 1-1. $\endgroup$
    – Goldstern
    May 4, 2014 at 23:26
  • $\begingroup$ Really $({\le 2})$-to-1. $\endgroup$
    – Goldstern
    May 5, 2014 at 7:00

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.