Is the following a characterization of $\Bbb Q\cap\cal C$, where $\cal C$ is the Cantor set?

Question

Let $A$ be an ordered set, with the following properties:

• $A$ is countable
• $A$ has a least and greatest element
• Between any two points with successors are points without successors; between any two points without successors are points with successors

Must $A$ be order-isomorphic to $\mathbb Q\cap\mathcal C$, where $\mathcal C$ is the Cantor set?

I'm pretty sure this is true but I'm not quite sure how to prove it. (This is not for homework.)

Answer 1

Corrected. Not quite. First, it can be isomorphic to $\Bbb Q\cap(\mathscr{C}\cup F)$ for any $F\subseteq\{-1,2\}$, since the first point can have a successor, and the last can be a successor. More important, the third condition isn’t quite strong enough to do what you want. As Eric Wofsey reminded me in the comments, your conditions allow $A$ to be $(\Bbb Q\cap[0,1])\times\{0,1\}$ with the lexicographic order, and this isn’t order-isomorphic to $\Bbb Q\cap\mathscr{C}$: every point of this $A$ either has or is an immediate successor, something that is not true of $\Bbb Q\cap\mathscr{C}$. You need to strength the third condition to ensure that $A$ has not only a dense set of points with immediate successors, but also a dense set of points that neither have nor are immediate successors. Once you take care of these problems, however, a standard back-and-forth argument will yield the desired result.

Let $S$ be the set of points of $A$ having successors, and for each $x\in S$ let $x^+$ be the successor of $x$. Let $S^+=\{x^+:x\in S\}$, and enumerate $A\setminus S^+=\{x_n:n\in\Bbb N\}$. Let $Q=\Bbb Q\cap\mathscr{C}$, let $S_Q$ be the set of points of $Q$ with immediate successors in $Q$, for $x\in S_Q$ let $x^+$ be the successor of $x$, let $S_Q^+=\{x^+:x\in S_Q\}$, and enumerate $Q\setminus S_Q^+=\{y_n:n\in\Bbb N\}$.

Now just carry out a standard back-and-forth argument to construct an order-isomorphism $h:Q\to A$. Suppose that $n\in\Bbb N$, $h(x_k)$ has been defined for each $k<n$, and $h(x_k^+)$ has been defined for each $k<n$ for which $x_k\in S_Q$.

• If $x_n=0$, let $h(x_n)$ be the first element of $A$.
• If $x_n=1$, let $h(x_n)$ be the last element of $A$.
• If $x_n\in S_Q$, let $h(x_0)=y_m$, where $m$ is minimal such that $y_m\in S$ and $y_m$ is correctly situated with respect to $\{h(x_k):k<n\}$, and let $h(x_n^+)=y_m^+$.
• If $x_n\in Q\setminus S_Q$, let $h(x_n)=y_m$, where $m$ is minimal such that $y_m\in A\setminus S$ and $y_m$ is correctly situated with respect to $\{h(x_k):k<n\}$.

It’s clear that $h$ defines an order-isomorphism of $Q$ into $A$, and the usual argument shows that $h$ is surjective.

Answer 2

Given such an $A$, let $a\sim b$ if $a=b$ or $a$ is the successor of $b$ or $b$ is the successor of $a$. Your hypotheses imply this is an equivalence relation; let $B=A/{\sim}$ be the quotient. Then $B$ is a countable bounded dense linear order. Let $C\subseteq B$ be the set of equivalence classes that contain two points rather than one. Then your hypotheses imply that $C$ is a dense subset of $B$.

Conversely, given any countable bounded dense linear order $B$ and a dense subset $C\subseteq B$, we can obtain such an $A$ by starting with $B$ and replacing each point of $C$ with a pair of points. This construction is inverse to the construction in the previous paragraph (up to canonical isomorphism).

We can thus conclude that isomorphism classes of ordered sets $A$ satisfying your hypotheses are in bijection with isomorphism classes of pairs $(B,C)$ where $B$ is a countable bounded dense linear order and $C\subseteq B$ is a dense subset. Any such $B$ is isomorphic to $\mathbb{Q}\cap [0,1]$, but there are obviously many non-isomorphic choices of $C$ (for instance, the complement of $C$ could have any countable cardinality). When $A=\mathbb{Q}\cap\mathcal{C}$, the complement of $C$ is dense and contains the greatest and least elements of $B$. If you add this additional constraint, then $(B,C)$ is unique up to isomorphism. Indeed, this can be proven by a simple back-and-forth argument that is basically identical to the proof that any two countable dense linear orders are isomorphic (you just have to additionally keep track of whether points are in $C$).