Calculus

Set Theory

Set Theory Logo

Cantor’s Theorem

Cantor's theorem is one of the few major results in set theory. It states that, for any set A, the power set of A has a strictly greater cardinality than A itself:

\[\left| {\mathcal{P}\left( A \right)} \right| \gt \left| A \right|.\]

This statement is obvious for finite subsets because

\[\left| A \right| = n,\;\;\left| {\mathcal{P}\left( A \right)} \right| = {2^n},\;\;\text{and }{2^n} \gt n\; \forall n \ge 0.\]

For example, the cardinality of the set {1, 2, 3, 4} is 4, while the cardinality of its power set is

\[\left| {\mathcal{P}\left( {\left\{ {1,2,3,4} \right\}} \right)} \right| = {2^4} = 16.\]

But the theorem applies to both finite and infinite sets, so to prove \(\left| {\mathcal{P}\left( A \right)} \right| \gt \left| A \right|\) we must use functional relations between the sets.

Proof

We need to show that there is an injection \(f:A \to \mathcal{P}\left( A \right)\) but no surjection \(f:A \to \mathcal{P}\left( A \right).\)

To define an injection from \(A\) to \(\mathcal{P}\left( A \right),\) we just map \(x \in A\) to the singleton set \(\left\{ x \right\} \in \mathcal{P}\left( A \right):\)

\[f\left( x \right) = \left\{ x \right\}.\]

Clearly, this mapping is one-to-one. Hence, \(\left| A \right| \le \left| {\mathcal{P}\left( A \right)} \right|.\)

Suppose by contradiction that \(f\) is surjective. Consider the set

\[B = \left\{ {x \in A \mid x \not\in f\left( x \right)} \right\}.\]

In words, the set \(B\) contains all those elements \(x \in A\) whose image under the function \(f\) does not include \(x\) itself. For example, if \(A = \left\{ {1,2,3} \right\},\) we could map

\[1 \to \varnothing,\;\;2 \to \left\{ {1,3} \right\},\;\;3 \to \left\{ 2 \right\}.\]

The set \(B\) is a subset of \(A,\) so \(B \in \mathcal{P}\left( A \right).\) Since \(f\) is assumed to be surjective, there is an element \(a \in A\) such that \(f\left( a \right) = B.\) There are two possibilities: either \(a \in B\) or \(a \not\in B.\) We consider these two cases separately.

  1. If \(a \in B,\) then \(a \in f\left( a \right).\) By the definition of \(B,\) this means that \(a \not\in B,\) which is a contradiction.
  2. If \(a \not\in B,\) then \(a \not\in f\left( a \right),\) and hence, \(a \in B,\) which is again a contradiction.

Therefore, the initial assumption is false and \(\left| A \right| \ne \left| {\mathcal{P}\left( A \right)} \right|.\) Thus, we have proved the strict inequality

\[\left| A \right| \lt \left| {\mathcal{P}\left( A \right)} \right|.\]

We see that taking the power set of a set creates a set of larger cardinality. Starting with \({\aleph_0} = \left| \mathbb{N} \right|\) and applying this operation successively, we get an infinite sequence of sets with increasing cardinality:

\[{\aleph_0} = \left| \mathbb{N} \right| \lt \left| {\mathcal{P}\left( \mathbb{N} \right)} \right| \lt \left| {\mathcal{P}\left( {\mathcal{P}\left( \mathbb{N} \right)} \right)} \right| \lt \left| {\mathcal{P}\left( {\mathcal{P}\left( {\mathcal{P}\left( \mathbb{N} \right)} \right)} \right)} \right| \lt \cdots \]

Continuum Hypothesis

According to Cantor's theorem, \(\left| {\mathcal{P}\left( \mathbb{N} \right)} \right|\) is strictly greater than \(\left| \mathbb{N} \right|.\) From the other side, it is known that the set of real numbers \(\left| \mathbb{R} \right|\) has the same cardinality as \(\left| {\mathcal{P}\left( \mathbb{N} \right)} \right|,\) so we have

\[{\aleph_0} = \left| \mathbb{N} \right| \lt \left| \mathbb{R} \right|.\]

The question is, does there exist a set \(A\) whose cardinality is strictly between that of the integers and the real numbers?

\[\left| \mathbb{N} \right| \lt \left| A \right| \lt \left| \mathbb{R} \right|?\]

The continuum hypothesis states that there is no set \(A\) whose cardinality lies between \(\left| \mathbb{N} \right|\) and \(\left| \mathbb{R} \right|.\)

Cantor and other mathematicians tried for decades to prove or disprove the continuum hypothesis without any success. The problem was considered so important that Hilbert put it at the top of his famous list of open problems published in \(1900.\) Ultimately, Gödel and Cohen showed that the continuum hypothesis is independent of axiomatic set theory. We can either accept it as true or accept it as false. Any of these choices leads to a consistent (but different) version of set theory.

See solved problems on Page 2.

Page 1 Page 2