Is there a simple, constructive, 1-1 mapping between the reals and the irrationals?

I know that the Cantor–Bernstein–Schroeder theorem implies the existence of a 1-1 mapping between the reals and the irrationals, but the proofs of this theorem are nonconstructive.

I wondered if a simple (not involving an infinite set of mappings) constructive (so the mapping is straightforwardly specified) mapping existed.

I have considered things like mapping the rationals to the rationals plus a fixed irrational, but then I could not figure out how to prevent an infinite (possible uncountably infinite) regression.

  • 2
    Define "constructive". – Asaf Karagila Oct 2 '13 at 17:39
  • 2
    @Daniel You will be surprised at how straightforward it is. – MJD Oct 2 '13 at 17:51
  • 1
    I don't know of any reasonable sense in which the usual proof of the Cantor–Bernstein–Schroeder theorem is non-constructive. Could you clarify? – Trevor Wilson Oct 2 '13 at 18:05
  • 2
    @Trevor: Actually, – Asaf Karagila Oct 2 '13 at 18:08
  • 2
    This discussion of constructivism is misguided in this context. Everything is explicit here. – Andrés E. Caicedo Oct 2 '13 at 18:31
up vote 52 down vote accepted

Map numbers of the form $q + k\sqrt{2}$ for some $q\in \mathbb{Q}$ and $k \in \mathbb{N}$ to $q + (k+1)\sqrt{2}$ and fix all other numbers.

  • 4
    What a beautiful, simple answer. – Stefan Smith Oct 2 '13 at 19:25
  • 1
    I am having trouble understanding how this should work: if $k$ is even this will map a rational number to an irrational, if $k$ is odd that will be reversed. – String Oct 2 '13 at 22:52
  • 1
    This isn't technically an answer to his question, though. It's not 1-1. In particular, all irrational numbers are fixed by your map, so the rationals get mapped on top of them. – Chris Bonnell Oct 3 '13 at 0:27
  • 3
    @atomic: That's not true; you must be misreading the answer. – ruakh Oct 3 '13 at 2:20
  • 3
    @madth3: Ok, got it now. We must allow $k=0$ to have the rationals $\mathbb Q$ mapped to $\mathbb Q+\sqrt 2$. And then these irrationals must be moved 'to make space etc. – String Oct 3 '13 at 4:26

Let $\phi_i$ be an enumeration of the rationals. Let $\eta_i$ be some countable sequence of distinct irrationals; say for concreteness that $$\eta_i = \frac{\sqrt2}{2^{i}}.$$

Then define $$f(x) = \begin{cases} \eta_{2i} & \text{if $x$ is rational and so equal to $\phi_i$ for some $i$} \\ \eta_{2i+1} & \text{if $x$ is irrational and equal to $\eta_i$ for some $i$} \\ x & \text{otherwise} \end{cases}$$

$f$ is now a bijective mapping between the reals and the irrationals.

This mapping was found by Cantor in 1877; I saw it in the paper "Was Cantor Surprised?" by Fernando Q. Gouvêa. (American Mathematical Monthly, 118, March 2011, pp. 198–209.) The construction is described at the middle of page 208.

There's a map between the irrational numbers and the non-eventually zero sequences of natural numbers, namely continued fractions.

We can prove, easily (using the Cantor-Bernstein theorem, anyway), that there is a bijection between $\Bbb R$ and the set of these non-eventually zero sequences of integers.

Now the composition works out just fine as a bijection from $\Bbb R$ and $\Bbb{R\setminus Q}$. But it's not nearly as sleek as MJD's solution.

Consider $A = \{ \pi + n : n\in\Bbb N\}$. Clearly $A$ is countable. (Consider the bijection $n\rightarrow\pi + n, \forall n\in\Bbb N$). So elements of $A$ can be expressed as, $A = \{a_k : k \in \Bbb N\}$. And we also can have $\Bbb Q = \{b_k : k \in \Bbb N\}$.

Now consider the bijection $\phi : \Bbb R \rightarrow \Bbb R \setminus \Bbb Q$ by,

$$\phi(x) := \begin{cases} a_{2k+1} &\text{if}\;x = b_k, x \in \Bbb Q\\ a_{2k} &\text{if}\;x = a_k, x \in A\\ x &\text{if}\;x \in \Bbb R \setminus (A\cup \Bbb Q) \end{cases}$$

This example can be seen as a very general bijection from a general uncountable set to a proper subset of it which is also uncountable!

  • This is the same construction I gave in my answer. – MJD Oct 28 at 13:51
  • @MJD While I gave the answer, I didn't see your answer! – Coherent Oct 28 at 13:56

Rather similar, take your favorite transcendental-mine is $e$ because it is easy to type. For a first cut take each rational $q$ to $qe$, each number of the form $qe$ to $qe^2$, each $qe^2$ to $qe^3$ and so on. As $e$ is transcendental, we never run into a problem with coming back into the rationals. Unfortunately, this leaves us with a problem at $0$, but one point is easy to take care of. The final answer is (with $n$ being any non-negative integer)$$f(x)=\begin {cases}e&x=0\\e^{n+2}&x=e^n\\ex&x=qe^n, q \in \Bbb Q\\x&\text{otherwise} \end{cases}$$

  • 2
    $f(1\cdot e^n)=e\cdot e^n$ and $f(e^n)=e^{n+2}$? – Did Oct 2 '13 at 21:26

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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