# isomorphism $\Bbb Q$ to $\Bbb Q \cap (0,1)$

I've got a question in my homework: Prove that $\langle \mathbb{Q},< \rangle$ and $\langle \mathbb{Q}\cap (0,1),< \rangle$ are isomorphic. I have tried to find a bijective function without any luck. Can anyone please help? Thanks,

-
Isomorphic? In what sense? Or do you mean there is a bijection between them?? – ncmathsadist Nov 24 '12 at 17:19
I think that he is looking for a strictly increasing bijection – Amr Nov 24 '12 at 17:19
Then as totally ordered sets. thanks. – ncmathsadist Nov 24 '12 at 17:20

Try the function $f:\mathbb Q \rightarrow \mathbb Q \cap (0,1)$ defined by $f(x)=\frac{1}{2}(1+\frac{x}{x+1})$ for $x \ge 0$ and $f(x)=\frac{1}{2}(1+\frac{x}{1-x})$ for $x < 0$. This one should yield an isomorphism.

-
This function can be described (in one case) as $f(x)=(1/2)(1+x/(1+|x|))$. I got that using "stereographic projection" onto $y=|x|$ from the point $(0,1)$ to a point on the line, etc, and it's the same as your function. +1 – coffeemath Nov 24 '12 at 21:50

Notice that both your posets are both countable dense linear orders without greatest or least elements. It can be proved that any two such posets are order-isomorphic as follows.

Let $\langle P, <_P \rangle$ and $\langle Q, <_Q \rangle$ be countable dense linear orders without greatest or least elements.

Let $P = \{ p_1, p_2, \dots \}$ and $Q = \{ q_1, q_2, \dots \}$. We'll relabel the elements of $P$ and $Q$ simultaneously to get $P = \{ \overline{p}_1, \overline{p}_2, \dots \}$ and $Q = \{ \overline{q}_1, \overline{q}_2, \dots \}$ in such a way that $\overline{p}_i \le \overline{p}_j$ if and only if $\overline{q}_i \le \overline{q}_j$.

To do this, proceed as follows. Choose $\overline{p}_1$ and $\overline{q}_1$ to be any elements of $P$ and $Q$ respectively.

Suppose that $\overline{p}_1, \dots, \overline{p}_{n-1}$ and $\overline{q}_1, \dots, \overline{q}_{n-1}$ have all been chosen.

If $n$ is is odd then let $k \in \mathbb{N}$ be least such that $p_k \ne \overline{p_{\ell}}$ for any $1 \le \ell \le n-1$, and define $\overline{p}_n = p_k$. Then let $\overline{q}_n$ be any element of $Q \setminus \{ \overline{q}_1, \dots, \overline{q}_{n-1}\}$ which satisfies $\overline{q}_n \le \overline{q}_i$ if and only if $\overline{p}_n \le \overline{p}_i$.

If $n$ is even then do the same but in the other direction (i.e. swap $p$ and $q$, and $P$ and $Q$, in the above).

Then the function $f : P \to Q$ defined by $f(\overline{p}_i) = \overline{q}_i$ for each $i$ is an order-isomorphism.

There are lots of details to be checked, e.g.:

• Do $\overline{p}_n$ and $\overline{q}_n$ always exist? [What conditions do we need to make them exist?]
• Is the function actually bijective and order-preserving? Is its inverse?

I leave that to you.

Aside: This way of doing things is nice because it proves that all countable dense linear orders without greatest or least elements are order-isomorphic, not just $\mathbb{Q}$ and $\mathbb{Q} \cap (0,1)$. The same construction shows that any countable linear order embeds into $\mathbb{Q}$, which is useful in proving results about countable ordinal numbers. The price to pay for this luxury is that you don't get an explicit bijection that you can just write down.

-