Cantor's Theorem

Published May 18, 2022  -  By Marco Garosi

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.


Cantor’s theorem states that:

NNN=R \lvert \N \rvert \lneq \lvert \N \rightarrow \N \rvert = \lvert \R \rvert

Cantor's Theorem - Statement

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


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 N=NN\lvert \N \rvert = \lvert \N \rightarrow \N \rvert.

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

f0 f1 f2 f3  fnˉ  f_{0}~f_{1}~f_{2}~f_{3}~\dots~f_{\bar{n}}~\dots

Enumerating Functions

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

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

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

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

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

In the end, we are stating that fnˉ(nˉ)=fnˉ(nˉ)+1f_{\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=21 = 2. Of course, that is impossibile: that is a contradiction. \square


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

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

Share on: