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:
In other words, that means that the cardinality of the set of natural numbers is strictly smaller than the cardinality of the functions from natural numbers to natural numbers .
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 .
Assuming that is true, then we can assign a number — in other words, enumerate — functions. So:
Let’s define a function . Since is a function from natural numbers to natural numbers, it follows that is in the enumeration discussed above. Let’s say it’s the function .
We could pass any natural number for . Let’s use .
It follows that, by definition, .
However, by construction .
In the end, we are stating that . Since we are working only with natural numbers, this equation is saying that a number is equal to its successor — much like saying that . Of course, that is impossibile: that is a contradiction.
We just proved that . In computability, this proves that there are much more problems to solve (functions ) than algorithms (which have the same cardinality as natural numbers, ).
The most important consequence then is that some — well, many actually — problems cannot be solved algorithmically.