Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer
(+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? – Jing Zhang 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$.

share|cite|improve this answer
Thanks but see the comment above. Sorry. – Jing Zhang 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,<)$.

share|cite|improve this answer
Sorry, just edited the question, those two sets are uncountable now. – Jing Zhang Jan 30 '13 at 16:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.