# Incomparable subsets of real numbers with usual order relation

Consider linear order $(R,<)$, would there be two sub-orders $(X,<), (Y,<)$ of it such that $X,Y$ are uncountable, which are incomparable in the following sense: There does not exist order preserving embeddings from $X$ to $Y$ or $Y$ to $X$. If so, how many would those subsets be? Thanks in advance! By saying an embedding f from Y to X, it is required that f is a function and $x<y \rightarrow f(x) < f(y)$ but f does not need to be surjective.

-

Theorem. There is a family $\{X_\alpha:\alpha<2^\omega\}$ of subsets of $\Bbb R$ such that each is a dense linear order of cardinality $2^\omega$, and if $f:X_\alpha\to X_\beta$ is an order-preserving injection, then $\alpha=\beta$, and $f$ is the identity on $X_\alpha$.

Proof. (The proof uses the axiom of choice.) Let $\mathscr{F}$ be the set of order-preserving injections from $\Bbb R$ to $\Bbb R$, and enumerate $\mathscr{F}=\{f_\xi:\xi<2^\omega\}$. Let $\mathscr{V}=\{V_\xi:\xi<2^\omega\}$ be an enumeration of the non-empty open intervals of $\Bbb R$. Let $\{t_\xi:\xi<2^\omega\}$ be an enumeration of $2^\omega\times 2^\omega\times 2^\omega$, and let $\pi_0,\pi_1,\pi_2,:2^\omega\to 2^\omega$ be such that $t_\xi=\langle\pi_0(\xi),\pi_1(\xi),\pi_2(\xi)\rangle$ for $\xi<2^\omega$.

By recursion on $\xi<2^\omega$ choose points $x_\xi,y_\xi\in\Bbb R$ so that for each $\xi<2^\omega$

\begin{align*} (i)&\quad x_\xi\in V_{\pi_2(\xi)}\setminus\big(\{x_\eta:\eta<\xi\}\cup\{y_\eta:\eta<\xi\}\big)\;;\\ (ii)&\quad y_\xi=f_{\pi_0(\xi)}(x_\xi)\notin\{x_\eta:\eta<\xi\}\cup\{y_\eta:\eta<\xi\}\;;\text{ and}\\ (iii)&\quad\text{if }f_{\pi_0(\xi)}\upharpoonright V_{\pi_2(\xi)}\text{ is not the identity on }V_{\pi_2(\xi)},\text{ then }y_\xi\ne x_\xi\;. \end{align*}

Conditions $(i)$ and $(ii)$ are satisfiable because $|V_{\pi_2(\xi)}|=2^\omega>\left|\{x_\eta:\eta<\xi\}\cup\{y_\eta:\eta<\xi\}\right|$ and $f_{\pi_0(\xi)}$ is injective. Condition $(iii)$ is satisfiable because $f_{\pi_0(\xi)}$ is monotone. (E.g., if $f_{\pi_0(\eta)}>x_\eta$ for some $\eta<\xi$, fix $u\in V_{\pi_2(\xi)}\cap\big(x_\eta,f_{\pi_0(\xi)}(x_\eta)\big)$, and note that $f_{\pi_0(\xi)}(z)>z$ for all $z\in(x_\eta,u)$.)

For $\alpha<2^\omega$ let $X_\alpha=\{x_\xi:\pi_1(\xi)=\alpha\}$. Clearly $|X_\alpha\cap V_\xi|=2^\omega$ for each $\xi<2^\omega$, so $X$ is a dense linear order of cardinality $2^\omega$. Suppose that $\alpha,\beta<2^\omega$ and $f:X_\alpha\to X_\beta$ is an order-preserving injection. $\Bbb R$ is complete, so $f$ may be extended to a function $g:\Bbb R\to\Bbb R$ by setting

$$g(x)=\begin{cases} f(x),&\text{if }x\in X_\alpha\\ \sup\{f(y):y\in X_\alpha\text{ and }y<x\},&\text{if }x\in\Bbb R\setminus X_\alpha\;. \end{cases}$$

Clearly $g\in\mathscr{F}$; say $g=f_\gamma$. If $g$ is not the identity map on $\Bbb R$, there is an $\eta<2^\omega$ such that $g\upharpoonright V_\eta$ is not the identity map on $V_\eta$. Choosing $\xi<2^\omega$ such that $t_\xi=\langle\gamma,\alpha,\eta\rangle$, we see that

$$f(x_\xi)=f_\gamma(x_\xi)=y_\xi\notin\bigcup_{\zeta<2^\omega}X_\zeta\supseteq X_\beta\;,$$

which is absurd. $\dashv$

This is adapted from Theorem 3.2 of my old paper A characterization of well-orders, Fundamenta Mathematicae 111.1 (1981) 71-76.

-
(+1) Shameless self promotion at its very best! –  Asaf Karagila Jan 30 '13 at 20:17
Nice answer! Thanks. Is axiom of choice a must here? Would this result be independent of ZF? –  JZ13 Jan 31 '13 at 4:47
@JingZhang: You’re welcome. I don’t know whether AC is necessary; it’s not something that I worry about, since I take AC for granted. It wouldn’t surprise me greatly, though, if the result were independent of ZF, at least in this strong form. –  Brian M. Scott Jan 31 '13 at 5:02

I believe $X = \{0, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \ldots \}$ and the set $Y = 1 - X$ would work, with the induced orders. If $f$ is an order-preserving injection $f:X \rightarrow Y$, then $f(0)$ certainly can't be 1, so it must have the form $f(0) = 1 - \frac{1}{n}$. Now, $f(\frac{1}{3})$ can't be 1 either, since $\frac{1}{3} < \frac{1}{2}$, so $f(\frac{1}{3}) = 1 - \frac{1}{m}$ for some $m$, and so now we have infinitely elements of $Y$ lying between $1 - \frac{1}{n}$ and $1 - \frac{1}{m}$, which is false.

A symmetric argument should give no injections from $Y$ to $X$.

-
Thanks but see the comment above. Sorry. –  JZ13 Jan 30 '13 at 16:37

To give a concrete example based on Asaf's answer: let $X=\{1,2,3,\ldots\}$, and let $Y=\{\ldots,-3,-2,-1\}$. If $f:X\rightarrow Y$ is one-to-one and satisfies $f(1)=a$, then we need $f(X-\{1\}) \subseteq \{a+1,a+2,\ldots,-2,-1\}$ in order for $f$ to be order-preserving. But the latter set is finite, so this is impossible; there is no order-preserving map from $(X,<)$ to $(Y,<)$.

-
Sorry, just edited the question, those two sets are uncountable now. –  JZ13 Jan 30 '13 at 16:36