This page does not represent the most current semester of this course; it is present merely as an archive.

1 The Proof

N<R|\mathbb N| < |\mathbb R|

Before we get to the main proof, let’s do a lemma:

NR|\mathbb N| \leq |\mathbb R|

The lemma is easily proven by showing a total injection:

Consider the function f:NRf : \mathbb N \rightarrow \mathbb R defined as f(x)=xf(x) = x. The function ff is total (it is defined for all xNx \in \mathbb N) and injective (f(x)=f(y))(x=y)\big(f(x) = f(y)\big) \rightarrow (x = y). Hence, there exists a total injection from N\mathbb N to R\mathbb R, which means NR|\mathbb N| \leq |\mathbb R|

With this lemma, all we need to prove that N<R|\mathbb N| < |\mathbb R| is to prove that NR|\mathbb N| \neq |\mathbb R|.

We proceed by contradiction.

Assume N=R|\mathbb N| = |\mathbb R|. Then there exists a total invertible function f:NRf : \mathbb N \rightarrow \mathbb R. Let ff' be one such function.

Let xRx \in \mathbb R be defined such that the nnth digit of xx is one more than the nnth digit of f(n)f'(n). Formally, that means:

x=nN(f(n)10n+1mod  10)10nx = \sum_{n \in \mathbb N} \Big(\big\lfloor f'(n) 10^{n}\big\rfloor + 1 \mod 10\Big) 10^{-n}

Because xx is a real number and ff' is invertible, there must exist some nxNn_x \in \mathbb N such that f(nx)=xf'(n_x) = x. But by construction the nxn_xth digit of xx differs from the nxn_xth digit of f(nx)f'(n_x); formally, that is

x10nx=f(nx)10nx+1mod  10\big\lfloor x 10^{n_x}\big\rfloor = \big\lfloor f'(n_x) 10^{n_x}\big\rfloor + 1 \mod 10

That means f(nx)xf'(n_x) \neq x, which contradicts our definition of ff' and nxn_x.

Because assuming N=R|\mathbb N| = |\mathbb R| led to a contradiction, it must be the case that NR|\mathbb N| \neq |\mathbb R|.

Because of our lemma, we know that NR|\mathbb N| \leq |\mathbb R|, which must mean N<R|\mathbb N| < |\mathbb R|

2 Discussion

Why does the above proof technique not work for integers? Because if we try to apply it to integers, we end up with an infinite string of digits on the left side of the decimal point, which is not an integer.

Why does the above proof technique not work for rationals? Because the decimal expansion of any rational repeats, and the diagonal construction of xx does not repeat, and thus is not rational.

There is no magic to the specific xx we picked; it would just as well to do a different base, like binary

x1=nN(1f(n)2n)2nx_1 = \sum_{n \in \mathbb N} \Big( 1 - \big\lfloor f'(n) 2^{n}\big\rfloor\Big) 2^{-n}

or to use a different digit-changing rule like

x2=nN(9f(n)10n)10nx_2 = \sum_{n \in \mathbb N} \Big( 9 - \big\lfloor f'(n) 10^{n}\big\rfloor\Big) 10^{-n}

or to grab a different set of digits

x3=nN(f(n)10n+2(nmod  2)+1mod  10)10n2(nmod  2)x_3 = \sum_{n \in \mathbb N} \Big(\big\lfloor f'(n) 10^{n + 2(n \mod 2)}\big\rfloor + 1 \mod 10\Big) 10^{-n - 2(n \mod 2)}

etc.