Cantor's Theorem

Cantor’s theorem is a fundamental result in mathematical set theory. In computability, it may be even more fundamental, since it proves that there are much more problems than algorithmically solvable ones.

Also, the way the proof works — commonly known as diagonalization — is a simple yet extremely powerful technique based on contradiction.

Statement

Cantor’s theorem states that:

In other words, that means that the cardinality of the set of natural numbers $\N$ is strictly smaller than the cardinality of the functions from natural numbers to natural numbers $\N \rightarrow \N$.

Proof

This is a proof by contradiction — which means we’ll make an assumption; derive consequences from that assumption; show that consequences conflict with the initial assumption.

Let’s suppose $\lvert \N \rvert = \lvert \N \rightarrow \N \rvert$.

Assuming that is true, then we can assign a number — in other words, enumerate — functions. So:

Any function is thus $f_{x} \in \lvert \N \rightarrow \N \rvert$.

Let’s define a function $g(x) \coloneqq f_{x}(x)+1, x \in \N, g(x) \in \lvert \N \rightarrow \N \rvert$. Since $g$ is a function from natural numbers to natural numbers, it follows that $g$ is in the enumeration discussed above. Let’s say it’s the function $f_{\bar{n}}$.

We could pass any natural number for $x$. Let’s use $\bar{n}$.

It follows that, by definition, $g(\bar{n}) = f_{\bar{n}}(\bar{n})$.

However, by construction $g(\bar{n}) = f_{\bar{n}}(\bar{n}) + 1$.

In the end, we are stating that $f_{\bar{n}}(\bar{n}) = f_{\bar{n}}(\bar{n}) + 1$. Since we are working only with natural numbers, this equation is saying that a number is equal to its successor — much like saying that $1 = 2$. Of course, that is impossibile: that is a contradiction. $\square$

Consequences

We just proved that $\lvert \N \rvert \lneq \lvert \N \rightarrow \N \rvert$. In computability, this proves that there are much more problems to solve (functions $\N \rightarrow \N$) than algorithms (which have the same cardinality as natural numbers, $\lvert \N \rvert = \omega$).

The most important consequence then is that some — well, many actually — problems cannot be solved algorithmically.