# Bijection from the irrationals to the reals

Since the irrationals and the reals have the same cardinality, there must be a bijection between them. Somewhere on this forum I found something like this:

Map all of the numbers of the form $q + n \sqrt2$ where $q \in \mathbb Q$ and $n \in \mathbb N$ into $q + (n+1) \sqrt2$ and map the rest of these numbers into themselves.

The problem is that I can't see how this function could possibly work. For example, we will never get the value of $2$, since $2$ is not an irrational number and adding multiples of $\sqrt 2$ will never make a number rational. Could you please explain to me why this function works?

• This function is going from $\mathbb{R}$ to the irrationals. – Maxime Scott Feb 5 '18 at 18:15
• Could we use some other irrational number, like $e$ or $\pi$ instead of $\sqrt 2$ ? – Aemilius Feb 5 '18 at 18:17
• @Aemilius Yes, you could. – José Carlos Santos Feb 5 '18 at 18:17
• Why should you get the value $2$ if it is not an irrational number? – Asaf Karagila Feb 5 '18 at 18:23
• the map maps R to R/Q so there is no $f(x) = 2 \in \mathbb Q$. However $f^{-1}(2 + \sqrt 2) = 2$ as $f(2) = 2 +\sqrt 2$ so there IS a number that is mapped from 2. So the function works. It just goes in the opposite direction than you expected. – fleablood Feb 5 '18 at 19:04

(Let $\mathbb I$ be the notation for the irrationals).

This is actually a map from $f:\mathbb R \to \mathbb I$ and not the other way, so the fact that your don't ever get $2$ (or any other rational number) is a feature, not a bug.

Of course this means the there must be an inverse from $f^{-1}:\mathbb I \to \mathbb R$. This wold be. If $x = q + \sqrt 2*n; n\ge 1; n\in \mathbb Z$ then map $x \to q + (n-1)\sqrt 2$; otherwise map all things to themselves. Thus we can get $2$ via $2 + \sqrt 2 \to 2$.

And this seems weird because .... what does the $\sqrt 2$ have to do with anything. And as you probably guessed, and irrational $\omega$ will do as well.

So to demonstrate:

1) $f: \mathbb R \to \mathbb I$.

If $q \in \mathbb Q$ then $q = q + 0*\omega$ so $f(q) = q + \omega \in \mathbb I$.

If $x = q + k\omega; q\in \mathbb Q; k \in \mathbb Z; k \ge 1$ then $f(x) = q + (k+1) \omega\in \mathbb I$.

And if neither of those cases $f(x) = x \in \mathbb I$.

So $f: \mathbb R \to \mathbb I$.

2) $f$ is unto.

If $x \in \mathbb I$ then either $x = q + k\omega$ where $q$ is rational and $k$ is a positive number or .... $x$ doesn't.

If $x$ does then $f(x - \omega) = f(q + (k-1)\omega) = q + k\omega = x$.

And if $x$ doesn't then $f(x) = x$.

So either way there exist a real number that maps to $x$.

So $f$ is onto.

3) $f$ is one-to- one.

Let $f(w) = x \in \mathbb I$. If $x \ne q + k*\omega$ for any rational $q$ and positive integer $z$ then if $w = q + n*\omega$ for some rational $q$ and natural $n$ then $f(w) = q + (n+1)\omega \ne x$ so that's impossible. So $f(w) = w = x$. That's the only one possible value that maps to $x$.

If $x = q + k \omega$ for some rational $q$ and positive integer $k$ and $w$ does not equal any $r + n*\omega$ for any rational $r$ not any rational $n$ then $f(w) = w \ne q+k\omega = x$ so that's impossible. So $w = r + n*\omega$. So $f(w) = r + (n+1)\omega = q + k\omega$.

So $r-q = (k- n-1)\omega$. But if $k-n-1\ne 0$ then the RHS is irrational and that is impossible. So $k - n - 1 = 0$ and $n = k-1$ and $r = q$ and $w = q + (k-1)\omega$ and that is the only one possible value that maps to $x$.

So $f$ is one-to-one.

... and so $f$ is a bijection between $\mathbb R\to \mathbb I$.

====

Okay, this feels ... wierd. But why?

What's really going on is

$\mathbb I = \mathbb R \setminus \mathbb Q$ and $|\mathbb R| >|\mathbb Q|=$ countable. When we want to make a bijection from a set to itself minus a countable subset of itself the "trick" is to leave the vast majority of the subset alone but to shove the "chain" of countable members to a countable number of exceptions that just follow an infinite but countable chain out of the way. So we "shove" all rational $q$ to $q + \omega$ That obvioulsy works. But were do we shove all the $q + \omega$ to? Well, to $q + 2\omega$ of course! But where do we shove those to? Well, we just shove all the $q + k\omega$ to $q + (k+1)\omega$.

Hopefully seen like that (albeit informal and handwavy) it is clearer why id does (and must) work.