# A proper subset of $\Bbb Q$ that is order-isomorphic to $\Bbb Q$; An infinite set that is NOT order-isomorphic to any of its proper subset

While it's not hard to define an order isomorphism between $$\Bbb N$$ and one of its proper subset or between $$\Bbb Z$$ and one of its proper subset, I'm unable to find sets in below situations:

1. A proper subset of $$\Bbb Q$$ that is order-isomorphic to $$\Bbb Q$$. This required subset of $$\Bbb Q$$ is ordered under the usual ordering $$<$$.

2. An infinite set that is NOT order-isomorphic to any of its proper subset. This infinite set and all of its subsets have the same ordering.

• Very broad hint: for 1) you just need a Dense Linear Order with No Endpoints, since any such is order- isomorphic to $\mathbb{Q}$ by the usual back-and-forth argument. What subsets of the rationals that are dense within it do you know? (Note that being dense within $\mathbb{Q}$ isn't a requirement for being order-isomorphic, either; there are plenty of bounded subsets that are, too...) Sep 27, 2018 at 15:17
• Hi @StevenStadnicki! from your hints, I think $\mathbb{Q}\setminus \{0\}$ maybe fine. Is my choice of $\mathbb{Q}\setminus \{0\}$ correct? Sep 27, 2018 at 15:25
• @holo the cleanest version I can think of of a mapping from $\mathbb{Q}\setminus\{0\}$ to $\mathbb{Q}$ is to choose a pair of monotonic sequences $r_n, s_n$ of rationals converging to e.g. $\sqrt{2}$ from below and above; map $(-\infty, -1)$ to $(-\infty, r_0)$ and $(s_0, \infty)$ to $(1, \infty)$, then map the intervals $[-1, -1/2), [-1/2, -1/4), \ldots$ to $[r_0, r_1), [r_1, r_2), \ldots$ and likewise map the intervals $(2^{-(n+1)}, 2^{-n}]$ to $(s_{n+1}, s_n]$. Sep 27, 2018 at 18:00
• For the second question, see mathoverflow.net/questions/131933/… Sep 28, 2018 at 3:41
• Yes. You got it. BTW the "back-and-forth" technique is not the only way to prove that theorem of Cantor. I When I had it as homework I found a different proof. I DK what method Cantor used. Sep 29, 2018 at 2:56

This should have been posted as two separate questions.

1. The map $$x\mapsto\begin{cases}\ \ \ \ x\ \ \ \ \text{ if }\ x\lt0\\ x+1\ \text{ if }\ x\ge0\end{cases}$$ is an order-isomorphism from $$\mathbb Q$$ to $$\mathbb Q\setminus[0,1).$$

2. A dense subset $$S$$ of $$\mathbb R$$ which is not isomorphic to any of its proper subsets can be constructed by transfinite induction with the axiom of choice. In fact $$S$$ can be constructed so that the only strictly increasing function $$f:S\to S$$ is the identity function.

P.S. Constructing an order-isomorphism between $$\mathbb Q$$ and $$\mathbb Q\setminus\{0\}$$ is more complicated. Here is one way to do it. (Another, more general, way is Cantor's "back-and-forth" method.)

Lemma. Given $$a,b,c,d\in\mathbb Q$$, $$a\lt b$$, $$c\lt d$$, we can define an order-isomorphism $$f:\mathbb Q\cap[a,b]\to\mathbb Q\cap[c,d]$$.

Proof. Let $$f(x)=c\cdot\frac{x-b}{a-b}+d\cdot\frac{x-a}{b-a}$$.

Fix sequences $$a_1\lt a_2\lt a_3\lt\cdots$$ and $$b_1\gt b_2\gt b_3\gt\cdots$$ such that $$\lim_{n\to\infty}a_n=\lim_{n\to\infty}b_n=\sqrt2$$. (A nice way to do this is to use the continued fraction convergents: $$a_1=1$$, $$b_1=3/2$$, $$a_2=7/5$$, $$b_2=17/12$$, $$a_3=41/29$$, etc.)

Define $$c_n=-\frac1n$$ and $$d_n=\frac1n$$ so that $$c_1\lt c_2\lt c_3\lt\cdots$$ and $$d_1\gt d_2\gt d_3\gt\cdots$$ and $$\lim_{n\to\infty}c_n=\lim_{n\to\infty}d_n=0$$.

Theorem. There is an order-isomorphism $$f:\mathbb Q\to\mathbb Q\setminus\{0\}$$ such that $$f(a_n)=c_n$$ and $$f(b_n)=d_n$$ for $$n=1,2,3,\dots$$.

Proof. For $$x\in\mathbb Q\cap(-\infty,a_1)$$ define $$f(x)=x+c_1-a_1$$.

For $$x\in\mathbb Q\cap[a_1,a_2]$$ define $$f(x)=c_1\cdot\frac{x-a_2}{a_1-a_2}+c_2\cdot\frac{x-a_1}{a_2-a_1}$$.

Further details are left as an exercise for the reader.

• Hi @bof, can you please show me an isomorphism from $\mathbb Q$ to $\mathbb Q\setminus\{0\}$? Sep 28, 2018 at 9:34
– bof
Sep 28, 2018 at 10:51
• Thank you @bof! I have figured out what's going on and soon present a detailed proof. Sep 29, 2018 at 1:13

In response to a request in the Comments from the Proposer. A proof of a result of Cantor without using a back-and-forth method. It requires much preliminary work on the structure of a linear order, followed by the proof itself, which is short. The main idea is to employ the preliminary result (III). I dk how Cantor proved this theorem..

Theorem. (Cantor). Any countably infinite linear orders $$(A,<), (A',<')$$ which are order-dense and without end-points are order-isomorphic.

Preliminaries. Let $$<$$ be a linear order on a countably infinite $$A=\{a_n:n\in \Bbb N\}$$ with no end-points, and order-dense in itself (i.e. if $$x there exists $$z$$ with $$x Then

(I). There exists $$B\subset A$$ which is order-isomorphic to $$\Bbb N$$ and unbounded above in $$A.$$ Proof: Let $$f(1)=1.$$ Recursively, for $$n\in \Bbb N$$ let $$f(n+1)$$ be the least $$j\in \Bbb N$$ such that $$a_{f(n)} Let $$B=\{a_{f(n)}:n\in \Bbb N\}.$$ To show that $$B$$ is unbounded above in $$A,$$ by induction:

(I-i). $$a_1=a_{f(1)} so $$a_1$$ is not an upper bound for $$B.$$

(I-ii). Suppose $$n\in \Bbb N$$ and no member of $$\{a_j:j\leq n\}$$ is an upper bound for $$B.$$ Let $$n_0$$ be the least $$k$$ such that $$a_{f(k)}\geq \max \{a_j:j\leq n\}.$$ Then:

If $$a_{n+1}\leq a_{f(n+0)}$$ then $$a_{n+1}

If $$a_{n+1}>a_{f(n_0)}$$ then $$n+1$$ is the least $$j$$ such that $$a_j>a_{f(n_0)}$$... (because $$j\leq n\implies a_j\leq a_{f(n_0)}$$)... so by the recursive def'n of $$f(n_0+1)$$ we have $$n+1=f(n_0+1).$$ So $$a_{n+1}=a_{f(n_0+1)}

(II). There exists $$C\subset A$$ where $$C$$ is order-isomorphic to $$\Bbb Z$$ and $$C$$ is unbounded above and below in $$A.$$ Proof: Applying (I) to the reverse-order $$<^*$$ on $$A$$ (where $$x<^*y$$ iff $$y), we obtain $$B^*\subset A$$ with $$B^*$$ order-isomorphic to the set of negative integers. So with $$B$$ as in (I), let $$C= B\cup B^*$$.

(III). $$A= \{J_n:n\in \Bbb N\}$$ such that

(III-i). $$a_1\in J_1.$$

(III-ii). Each $$J_n$$ is order-isomorphic to $$\Bbb Z$$ and is unbounded above and below in $$A.$$

(III-iii). $$J_n\subset J_{n+1}$$ for all $$n.$$ And whenever $$x,y$$ are consecutive members of $$J_n$$ with $$x there is exactly one $$z \in J_{n+1}$$ \ $$J_n$$ such that $$x... (Note: $$x,y$$ are consecutive members of $$J_n$$ iff no member of $$J_n$$ is between $$x$$ and $$y$$).

Proof: Let $$J_1=\{a_1\}\cup C$$ where $$C$$ is as in (II). Recursively define $$J_{n+1}$$ \ $$J_n$$ as follows: For any consecutive $$x,y$$ in $$J_n$$ with $$x let $$m$$ be the least $$j$$ such that $$x and let $$a_m$$ be the unique member of $$J_{n+1}$$ \ $$J_n$$ that lies between $$x$$ and $$y$$. Then (III-i),(III-ii),(III-iii) are satisfied.

It remains to show, by induction, that the set $$J=\cup_{n\in \Bbb N}J_n$$ is equal to $$A$$. As follows, by induction:

(III-i'). $$a_1\in J_1\subset J.$$

(III-ii'). Suppose $$\{a_j:j\leq n\}\subset J.$$ Let $$n_0$$ be the least (or any ) $$k$$ such that $$\{a_j:j\leq n\}\subset J_k.$$

If $$a_{n+1}\in J_{n_0}$$ then $$a_{n+1} \in J.$$

If $$a_{n+1}\not \in J_{n_0}$$ then there are consecutive $$x,y$$ in $$J_{n_0}$$ with $$x but no member of $$J_{n_0},$$ and a fortiori no member of $$\{a_j:j\leq n\}$$ lies between $$x$$ and $$y$$, therefore $$n+1$$ is the least $$j$$ such that $$x By the recursive def'n of $$J_{n_0+1}$$ \ $$J_{n_0},$$ therefore $$a_{n+1}$$ is the unique member of $$J_{n_0+1}$$ \ $$J_{n+0}$$ between $$x$$ and $$y.$$ So $$a_{n+1}\in J_{n_0+1}\subset J.$$

$$\bullet$$. After all this preliminary work, to finally prove the Theorem: Let $$A=\cup_{n\in \Bbb N}J_n$$ and $$A'=\cup_{n\in \Bbb N}J'_n$$ as in (III). Since $$J_1$$ and $$J'_1$$ are each order-isomorphic to $$\Bbb Z,$$ let $$f$$ map $$J_1$$ order-isomorphically onto $$J'_1.$$

Inductively, define $$f$$ on each $$J_n$$ as follows: Suppose $$f$$ maps $$J_n$$ order-isomorphically onto $$J'_n.$$ If $$x,y$$ are any consecutive members of $$J_n$$ and $$z$$ is the unique member of $$J_{n+1} \setminus J_n$$ between $$x$$ and $$y$$ then let $$z'$$ be the unique member of $$J'_{n+1} \setminus J'_n$$ between $$f(x)$$ and $$f(y).$$ Now let $$f(z)=z'.$$ Then $$f$$ maps $$J_{n+1}$$ onto $$J'_{n+1}$$ order-isomorphically.

Since $$J_n\subset J_{n+1}$$ for all $$n$$ and since $$A=\cup_{n\in \Bbb N}J_n,$$ if $$x,y\in A$$ with $$x, then $$\{x,y\}\subset J_n$$ for some $$n$$, and $$f$$ is strictly order-preserving on $$J_n$$, so $$f(x)<'f(y)$$.

Remark: This theorem can be used to prove that the real interval $$(0,1)$$ is uncountable. Suppose not. Then there is an order-isomorphism $$f:(0,1)\to \Bbb Q\cap (0,1),$$ which we can extend to an order-isomorphism $$f:[0,1]\to [0,1]\cap \Bbb Q$$ by letting $$f(0)=0$$ and $$f(1)=1.$$ Using the fact that there is a rational beteen any two reals, we can readily show that $$f$$ is continuous when considered as a function from $$[0,1]$$ into $$[0,1].$$ And a basic result of analysis (the Intermediate Value Property) then implies that $$[0,1]=\{f(x): 0\leq x\leq 1\}.$$ But $$\{f(x):0\leq x\leq 1\}=\Bbb Q \cap[0,1],$$ a contradiction.

Another way is that if $$(0,1)$$ were countable there would be an order-isomorphism $$g:(0,1)\cap \Bbb Q\to (0,1),$$ but then $$\{g(q):q\in \Bbb Q\cap (0,1/\sqrt 2\,)\}$$ would be a non-empty subset of $$(0,1)$$ with no $$lub .$$

• As an amusing digression, I wonder whether anyone who takes the time to read all this notices that at no point do I say that $m\ne n \implies a_m\ne a_n.$ Oct 3, 2018 at 20:18
• Preliminary result (I) can also be obtained, perhaps more simply, using the Axiom of Choice (AC), but I chose to derive it, and all the rest, without AC. Oct 3, 2018 at 20:38
• Thank you @Daniel! I will read your proof as carefully as possible. I will soon inform you about my result. Oct 3, 2018 at 23:55
• It also implies that if $U$ is a non-empty open subset of $\Bbb R$ and if $A$ is a countable dense subset of $U$ then $A$ is order-isomorphic and reverse-order-isomorphic to $\Bbb Q$.... ("Reverse-order" means that $x<y\implies f(x)>f(y)$),..... which has further implications. But the back & forth proof is, I think, a lot simpler, and can also be phrased so as to avoid AC. Oct 4, 2018 at 3:02
• Hi @DanielWainfleet! After three days of working hard, I have presented a detailed proof here. Please have a check on it! Many thanks for your dedicated help! Honestly, I only look at your lemmas and don't dare to look at the proofs, so that I can try to give them a shot by myself. Oct 7, 2018 at 4:05
1. $$(-1,1)\cap \Bbb Q$$.
2. I doubt there is any.
• For 2., see the first A in the link in the comment ( to the Q) by Gerry Myerson for an example of an uncountable subset of $\Bbb R$ that satisfies 2.... For 1., we have a theorem of Cantor: For $i\in \{0,1\}$ let $A_i$ be a countably infinite set and let $<_i$ be a linear order on $A_i$ with no end-points, and order-dense (i.e. if $x<_iy$ there exists $z$ with $x<_iz<_iy)$... Then $(A_0,<_0)$ is order-isomorphic to $(A_1,<_1).$.. We may take $A_0=\Bbb Q$ and $A_1=\Bbb Q$ \ $\{0\}$ with the usual order on each of them Sep 28, 2018 at 7:19
• Or we may take $A_0=\Bbb Q$ and $A_1=(-1,1)\cap \Bbb Q,$ as in your A. Sep 28, 2018 at 7:23
• Could you please give me an explicit order isomorphism between $\Bbb Q$ and $\Bbb Q \setminus \{0\}$ without relying on that theorem? Sep 28, 2018 at 7:56
• In @StevenStadnicki's comment: the cleanest version I can think of of a mapping from $\mathbb{Q}\setminus\{0\}$ to $\mathbb{Q}$ is to choose a pair of monotonic sequences $r_n, s_n$ of rationals converging to e.g. $\sqrt{2}$ from below and above; map $(-\infty, -1)$ to $(-\infty, r_0)$ and $(s_0, \infty)$ to $(1, \infty)$, then map the intervals $[-1, -1/2), [-1/2, -1/4), \ldots$ to $[r_0, r_1), [r_1, r_2), \ldots$ and likewise map the intervals $(2^{-(n+1)}, 2^{-n}]$ to $(s_{n+1}, s_n]$. But I'm unable to understand this example. Sep 28, 2018 at 7:59