Cantor's Theorem

set-theory

Definition

Cantor's Theorem

Every infinite set contains a countable subset and is thus, so to speak, “at least countable”.

Cantor showed, however, that the converse does not hold: not every infinite set is countable. There exists infinite sets that cannot be “exhausted” by a counting process.

Examples

Power Set of Natural Numbers

Goal: Show that the power set of the natural numbers is not countable. Equivalently: there is no surjective function .

Proof: Let be a function that attempts to list all subsets of :

with .

Let . This is a well-defined and clearly a subset of , therefore .

Intuition

is built by “flipping the diagonal” decision for each :

• If lies in the -th listed set , then we exclude it from .
• If it does not lie in , we include it in .

In other words, is the set of all natural numbers than cannot generate a set containing themselves using themselves.

Suppose appears as an image for an . Is ?

By definition of :

But if , a contradiction emerges:

Therefore, there cannot be an s.t. .

Conclusion: Thus, is not in the image of , i.e. . Since was an arbitrary listing attempt, no function from can hit every subset. Therefore, is uncountable.

To illustrate, let’s pick a concrete . Given that the set , a diagonal emerges:

This diagonal, which is definitely not a subset of the co-domain of , is . Trivially, since , , etc.