Diagonalization

Now, can we say that every infinite set is countable? This would be nice since we would end up saying that all infinite sets are (roughly) the same. Unfortunately, this is false since the real numbers are not countable.

Theorem 32 (Cantor)

The real interval $[0,1]$ is uncountable (not countable).

Proof:

We prove this by contradiction. The proof uses a technique called diagonalization which is also used a lot when studying computational complexity. Let us assume for the sake of contradiction that the interval $[0,1]$ is countable and $f$ is a an onto mapping from ${\mathbb N}$ to $[0,1]$. So we could list all numbers $f(1),f(2), \ldots$ and this would end up enumerating every member of $[0,1]$. Notice that each number $y \in [0,1]$ is of the form $y = 0.y_1y_2 \cdots$ ($y_i$ is the $i$-th digit after the decimal point).

We construct a number $x = 0.x_1 x_2 \cdots$ as follows: The number $x_i$ is defined by taking the $i$-th digit of $f(i)$ and add $+1$ (modulo $10$). In particular, the number $x$ differs from $f(i)$ at the $i$-th digit, for all $i$. This implies that $x$ cannot be in the range of $f$, but since $x \in [0,1]$ and is a real number, this is a contradiction with the fact that $f$ is an onto mapping.

Another interesting fact is that the power set of an infinite set is bigger than the set itself. Denote by $\mathcal{P}(X)$ the power set of set $X$ (the set of all subsets of $X$). When $X$ is finite, we know that $|\mathcal{P}(X)|=2^{|X|}$. But what about when $X$ is infinite? For example, what is the cardinality of $\mathcal{P}({\mathbb N})$? Is it the same as the cardinality of ${\mathbb N}$?

Exercise 81

Use diagonalization to prove that $\mathcal{P}({\mathbb N})$ is uncountable.