The Cardinality of the Real Numbers

November 7, 2021 Shreyas Comments 1 comment

1. Introduction

$0, 1, 2,…$ , The natural numbers are perhaps the most fundamental and intuitive set in mathematics. But they have a strange property: they never end (as some of you may have found out by attempting a “name the biggest number” game in childhood). Of course, these numbers may be extended by various logical arguments: what happens if we subtract a larger number from a smaller one, or divide a number into another number that is not its multiple, or take the square root of a non-perfect square (or even a negative number)? Clearly, all these sets $(\mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C})$ are infinite in size as well. But can we still say that one of these sets is “greater” than another, or that they are the same in size? As some of you are aware, this is indeed possible: if we can establish a 1-1 correspondence from the elements of the set (that is, pair them up in groups of 2 so that no element is repeated), then we can say that the sets have the same size, regardless of how large each set is. A function that takes in any element in the first set and outputs its corresponding pair in the second set is called a $\emph{bijection}$ .

For example, suppose we define a function from $\mathbb{N}$ to $\mathbb{Z}$ as follows: if $n$ is even, it maps to $\frac{n}{2}$ , and if $n$ is odd, it maps to $\frac{1 - n}{2}$ . Clearly, every integer is achieved by this mapping exactly once, so we conclude that $\mathbb{N}$ has the same size as $\mathbb{Z}$ (if you are new to this notion, take some time digesting it: it is quite counterintuitive that a $\mathbb{N}$ and $\mathbb{Z}$ have the same size despite the fact that $\mathbb{N}$ is contained inside $\mathbb{Z}$ )! Similarly, it is known that $\mathbb{Q}$ has the same size as these two sets (by a clever zigzagging bijection on a $2$ -D array). After these two surprising results, it may come as an even more surprising fact that the set of real numbers $\mathbb{R}$ , has been shown to be $\emph{larger}$ than $\mathbb{N}$ , $\mathbb{Z}$ and $\mathbb{Q}$ . The most famous proof of this fact is via Cantor’s diagonalization argument, which I encourage you to look up if you haven’t already. In this post, I will present another proof that I thought of regarding this interesting fact.

Note: The following proof was inspired by Problem 4.47 in the book Art of Problem Solving: Intermediate Counting & Probability by David Patrick (disclaimer: I have not read the book’s solution, so the following solution was obtained independently by me). The statement of the problem allows the usage of the following fact: if $X$ is any set, define $P(X)$ (called the power set of $X$ ) as the set containing all subsets of $X$ . For example, if $X=\{1, 3, 5\}$ $P(X)=\{\{\}, \{1\}, \{3\}, \{5\}, \{1, 3\}, \{1, 5\}, \{3, 5\}, \{1, 3, 5\}\}$ . Then, $P(X)$ cannot be put into a $1-1$ correspondence with $X$ . Clearly $|P(X)|\geq |X|$ , so this fact implies that $|P(X)| > |X|$ . This statement is very obvious for finite sets such as the previous example, but is not nearly so for infinite sets.

2. The Proof

We will prove that the set of real numbers has the same size as the power set of the positive integers, and then use the previous fact to conclude that it must be strictly larger in size than $\mathbb{N}$ . To do this, we will establish the following one-to-one correspondence between the two sets. Suppose we are given an element of the power set of $\mathbb{N}$ $A$ , a subset of $\mathbb{N}$ . We start with a decimal point, and then count a string of digits after that point in the following manner. For each positive integer $a \in A$ , we write $1$ as the $a$ -th digit after the decimal point, and we write $0$ for any digit whose position does not correspond to any element of $A$ . We will now interpret this decimal expansion as the binary expansion of a particular real number. Denote this number as $f(A)$ . Here are a few examples of our process:

$A = \{1, 2, 3\} \rightarrow f(A) = 0.111000\dots_{2} = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} = \frac{7}{8}$
$A = \{5\} \rightarrow f(A) = 0.0000100\dots_{2} = \frac{1}{32}$
$A = \{2, 4, 6, 8\dots\} \rightarrow f(A) = 0.01010101\dots_{2} = \frac{1}{3}$
$A = \{\} \rightarrow f(A) = 0.0000\dots = 0$

Similarly, any real number in $[0, 1]$ has a corresponding subset of $\mathbb{N}$ . For example, $\frac{1}{7}$ is $0.001001001\dots_{2}$ in binary, meaning it corresponds to the subset $A = {3, 6, 9, 12\dots}$ It may appear that we are finished after establishing this $1-1$ correspondence, but there is a small caveat. Notice that the real number 1/2 can be written as $0.1_{2}$ in binary, corresponding to $A + {1}$ . However, it may also be written as $0.0111111\dots_{2}$ , which corresponds to $A + {2, 3, 4, 5\dots}$ ! It turns out that not all real numbers have a unique binary expansion: specifically, if $x \neq 0$ is a number whose expansion terminates, it can alternatively be written with an infinite string of $1$ s at the end. We fix this problem by altering our function $f$ in the following way: if a particular subset $A \in \mathbb{N}$ corresponds to a number $x$ via the finite expansion, $f(A) = x$ as usual. However, if $A$ corresponds to $x$ via the infinite expansion, we define $f(A) = x + 1$ (we allow the exception of $x = 0$ and $x = 1$ because they only have one possible representation through our construction, $0.000\dots$ and $0.111\dots$ respectively). For example:

$A = \{2, 3\} \rightarrow x = \frac{1}{4} + \frac{1}{8} = \frac{3}{8}, f(A) = \frac{3}{8}$
$A = \{2, 4, 5, 6, 7, \dots\} \rightarrow x = \frac{1}{4} + \frac{1}{16} + \frac{1}{32} + \frac{1}{64}\dots = \frac{1}{4} + \frac{1}{8} = \frac{3}{8}, f(A) = \frac{3}{8} + 1 = \frac{11}{8}$

Observe that this new definition of $f$ ensures a precise bijection, but at the cost of altering the range of $f$ : what was once the interval $[0, 1]$ now becomes the union of $[0, 1]$ with a select few values in the interval $(1, 2)$ corresponding to the instances where we added $1$ to the value of $f$ . Denote the entire range of $f$ as $F$ . We have proven that $|P(\mathbb{N})| = |F|$ , but what can we say about $|F|$ ? Observe that $F$ clearly contains the interval $(0, 1)$ , and moreover $F$ is clearly contained within a larger interval, such as $(-1, 3)$ . Thus, we can say $|(0, 1)| \leq |F| \leq |(-1, 3)|$ . Here is the final step: observe that $|(-1, 3)| = |(0, 1)| = |\mathbb{R}|$ . This can be done by explicitly defining a bijection from $(-1, 3)$ to $(0, 1)$ as $b_1(x) = \frac{x+1}{4}$ and another bijection from $(0, 1)$ to $\mathbb{R}$ as $b_2(x) = \tan\left(\pi(x - \frac{1}{2})\right)$ . Finally, we may conclude that $|F| = |P(\mathbb{N})| = |\mathbb{R}|$ , and given that no set can be the same size as its power set, we finally conclude that $|\mathbb{N}| < |\mathbb{R}|$ .