52
$\begingroup$

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.

$\endgroup$
10
  • 3
    $\begingroup$ Define "constructive". $\endgroup$
    – Asaf Karagila
    Oct 2, 2013 at 17:39
  • 3
    $\begingroup$ @Daniel You will be surprised at how straightforward it is. $\endgroup$
    – MJD
    Oct 2, 2013 at 17:51
  • 1
    $\begingroup$ 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? $\endgroup$ Oct 2, 2013 at 18:05
  • 2
    $\begingroup$ @Trevor: Actually, mathoverflow.net/a/123485/7206 $\endgroup$
    – Asaf Karagila
    Oct 2, 2013 at 18:08
  • 2
    $\begingroup$ This discussion of constructivism is misguided in this context. Everything is explicit here. $\endgroup$ Oct 2, 2013 at 18:31

7 Answers 7

77
$\begingroup$

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.

$\endgroup$
8
  • 11
    $\begingroup$ What a beautiful, simple answer. $\endgroup$ Oct 2, 2013 at 19:25
  • 1
    $\begingroup$ 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. $\endgroup$
    – String
    Oct 2, 2013 at 22:52
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 3, 2013 at 0:27
  • 3
    $\begingroup$ @atomic: That's not true; you must be misreading the answer. $\endgroup$
    – ruakh
    Oct 3, 2013 at 2:20
  • 6
    $\begingroup$ @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. $\endgroup$
    – String
    Oct 3, 2013 at 4:26
30
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
0
4
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ This is the same construction I gave in my answer. $\endgroup$
    – MJD
    Oct 28, 2018 at 13:51
  • $\begingroup$ @MJD While I gave the answer, I didn't see your answer! $\endgroup$
    – user422112
    Oct 28, 2018 at 13:56
2
$\begingroup$

A rather simple explicit formula for an injection $f:\mathbb{R} \rightarrow \mathbb{R/Q}$ is $f(x)=\frac{x}{1+|x|}+1$ if $x\in \mathbb{R/Q}$ and $f(x)=\sqrt{2}(\frac{x}{1+|x|}-1)$ if $x\in\mathbb{Q}$.

This function does not rely on the fact the rationals are countable or the properties of transcendental numbers. It moves away from the classic displacement technique, where a sequence of irrationals are defined and then the function bumps each term of the sequence to a different term of the sequence to make room for the rationals. It does rely on the existence of $\sqrt{2}\in \mathbb{R}/\mathbb{Q}$, but any irrational number can be used in its place.

It can be shown to be well defined because rational numbers are closed under addition and multiplication (and subtraction and division), but multiplying a rational and an irrational results in an irrational and adding a rational and an irrational results in an irrational. It is also useful to note $\frac{x}{|x|} = $sgn$(x)\in \mathbb{Q}$ for any $x\in \mathbb{R/Q}$.

It can be shown to be an injection directly from the definition of injective. It certainly is not a surjection, but the graph is fun.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ $f(1\cdot e^n)=e\cdot e^n$ and $f(e^n)=e^{n+2}$? $\endgroup$
    – Did
    Oct 2, 2013 at 21:26
0
$\begingroup$

Here is a general approach that can be applied here. Suppose $A$, $B$, and $C$ are disjoint sets, where $A$ and $B$ are countably infinite. Then, we can construct an bijective function $\phi$ from $A\cup B\cup C$ to $B\cup C$, which maps $A\cup B$ onto $B$, and $C$ onto $C$. To do this, arrange the terms of $A$ and $B$ into sequences of distinct elements, so that $A=\{a_0,a_1,a_2,\dots\}$ and $B=\{b_0,b_1,b_2,\dots\}$. Define $\phi$ as follows: $$ \phi(x)= \begin{cases} b_{2i} &\text{if $x=a_i$ for some $i\in\mathbb N$} \, , \\ b_{2i+1} &\text{if $x=b_i$ for some $i\in\mathbb N$} \, , \\ x &\text{otherwise.} \end{cases} $$ This function maps the members of $A$ to the members of $B$ with even indices, and the members of $B$ to the members of $B$ with odd indices, while keeping the members of $C$ fixed in place.

To apply this method to construct a bijection between $\mathbb R$ and $\mathbb R\setminus\mathbb Q$, we can set:

  • $A=\mathbb Q$
  • $B=\{k\sqrt{2}:k\in\mathbb Z^+\}$
  • $C=\mathbb R\setminus(A\cup B)$

Let $f$ be a bijection from $\mathbb N$ to $\mathbb Q$ (see here for an explicit example), and put $a_i=f(i)$. Then, put $b_i=(i+1)\sqrt2$.

Finally, note that WimC's elegant answer uses the same principle. We split $\mathbb R$ into three disjoint sets:

  • $A=\mathbb Q$
  • $B=\{q+k\sqrt2:q\in\mathbb Q,k\in\mathbb Z^+\}$
  • $C=\mathbb R\setminus(A\cup B)$

Then, we map $A\cup B$ onto $B$, and $C$ onto $C$. The only difference between his and my approach is the way in which $A\cup B$ is mapped onto $B$.

$\endgroup$

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.