1
$\begingroup$

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.

Please help me find some examples (if exist) for these sets!

$\endgroup$
31
  • 2
    $\begingroup$ 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...) $\endgroup$ Sep 27, 2018 at 15:17
  • 1
    $\begingroup$ Hi @StevenStadnicki! from your hints, I think $\mathbb{Q}\setminus \{0\}$ maybe fine. Is my choice of $\mathbb{Q}\setminus \{0\}$ correct? $\endgroup$
    – Akira
    Sep 27, 2018 at 15:25
  • 2
    $\begingroup$ @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]$. $\endgroup$ Sep 27, 2018 at 18:00
  • 2
    $\begingroup$ For the second question, see mathoverflow.net/questions/131933/… $\endgroup$ Sep 28, 2018 at 3:41
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 29, 2018 at 2:56

3 Answers 3

3
$\begingroup$

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.

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

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<y$ there exists $z$ with $x<y<z).$ 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)}<a_j. $ 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)}<a_{f(2)}$ 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}<a_{f(n_0+1}\in B.$

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)}<a_{f(n_0+2)}\in B.$

(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<x$), 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<y,$ there is exactly one $z \in J_{n+1}$ \ $J_n$ such that $x<z<y$... (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<y$ let $m$ be the least $j$ such that $x<a_j<y,$ 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<a_{n+1}<y,$ 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<a_j<y.$ 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<y$, 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 .$

$\endgroup$
5
  • $\begingroup$ 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.$ $\endgroup$ Oct 3, 2018 at 20:18
  • $\begingroup$ 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. $\endgroup$ Oct 3, 2018 at 20:38
  • $\begingroup$ Thank you @Daniel! I will read your proof as carefully as possible. I will soon inform you about my result. $\endgroup$
    – Akira
    Oct 3, 2018 at 23:55
  • $\begingroup$ 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. $\endgroup$ Oct 4, 2018 at 3:02
  • $\begingroup$ 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. $\endgroup$
    – Akira
    Oct 7, 2018 at 4:05
0
$\begingroup$
  1. $(-1,1)\cap \Bbb Q$.
  2. I doubt there is any.
$\endgroup$
4
  • 1
    $\begingroup$ 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 $\endgroup$ Sep 28, 2018 at 7:19
  • $\begingroup$ Or we may take $A_0=\Bbb Q$ and $A_1=(-1,1)\cap \Bbb Q,$ as in your A. $\endgroup$ Sep 28, 2018 at 7:23
  • $\begingroup$ Could you please give me an explicit order isomorphism between $\Bbb Q$ and $\Bbb Q \setminus \{0\}$ without relying on that theorem? $\endgroup$
    – Akira
    Sep 28, 2018 at 7:56
  • $\begingroup$ 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. $\endgroup$
    – Akira
    Sep 28, 2018 at 7:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .