# Prove: there exist an order $R$ on $\mathbb{Q}$ s.t $\left\langle \mathbb{Q},R\right\rangle \simeq\left\langle \mathbb{N},R\right\rangle$

I need to prove that there exist an order relation, let it be: $R$, such that $$\left\langle \mathbb{Q},R\right\rangle \simeq\left\langle \mathbb{N},R\right\rangle$$

CORRECTION:

I understand that I need to prove that there exist a function: $$f: \mathbb{Q} \longrightarrow \mathbb{N}$$

what is the relation between the fact that $|\mathbb{Q}| = |\mathbb{N}|$ and the existence of a relation that satisfies : $\left\langle \mathbb{Q},R\right\rangle \simeq\left\langle \mathbb{N},R\right\rangle$?

• Is it the same $R$ on $\Bbb N$? – Asaf Karagila Aug 20 '18 at 9:43
• The second $R$ is the restriction of $R$ to $\mathbb{N}$ ? – Max Aug 20 '18 at 9:43
• @AsafKaragila yes – Jneven Aug 20 '18 at 9:44
• do you want this order to satisfy any condition? Like being a total order? – JayTuma Aug 20 '18 at 9:49
• Why is this tagged well orders? – Asaf Karagila Aug 21 '18 at 10:10

Concretely you can let $f:\mathbb N\to\mathbb Q$ be your favorite enumeration of the rationals and define that

$x\mathrel R y$ if $x\in\mathbb N$ and $y\notin\mathbb N$ or if $x$ and $y$ are both in $\mathbb N$ and $f(x)<f(y)$ or if neither $x$ nor $y$ is in $\mathbb N$ and $x<y$.

Then $(\mathbb Q,R)$ and $(\mathbb N,R)$ are both countable dense total orders without a first or last element, and it is known in general that any such two orders are isomorphic.

Alternatively, you could just define $x\mathrel R y$ iff $f^{-1}(x)<f^{-1}(y)$, where $f$ is still your favorite enumeration from before. $(\mathbb Q,R)$ and $(\mathbb N,R)$ would then both be ordered as infinite subsets of $(\mathbb N,{<})$, and all of those are also isomorphic.

This can be done in many different ways.

The key point is that there are many countable linearly ordered sets $(X,<)$ such that $X$ can be split into two parts both of which are isomorphic to $X$ itself.

For example, $\Bbb N$ can be split into even/odds, or really any two infinite sets. $\Bbb Z$ can too, but here we need to make sure that we also take the negative integers into account. Even $\Bbb Q$ can be split that way, for example all those rationals whose reduced form has an even numerator vs. odd numerator.

Now, using the countability of $\Bbb N$ and $\Bbb Q$, we can fix such countable $X$ that has a partition into $X_0$ and $X_1$, and map $\Bbb N$ to $X_0$, map $\Bbb{Q\setminus N}$ to $X_1$, and use transport of structure to define $R$.

One way of applying the above in a simple scenario, though, is to note that if $X$ is any infinite subset of $\Bbb N$, then $(X,\leq)\cong(\Bbb N,\leq)$. So just by picking $X$ to be $\Bbb N$, this will happen automatically without the need to partition and separate.