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 $$


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 $?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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