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:

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.