Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 38 ยท Countable and Uncountable Sets

Power Sets and Cantor's Theorem

Prove that |A| < |P(A)| for every set A with the diagonal set D, check it by brute force on small sets, and see why there is no largest infinity.

The diagonal argument showed that the subsets of โ„• cannot be listed. Cantor's theorem says this is not a quirk of โ„•. For every set A, finite or infinite, the power set P(A) is strictly bigger. Applied again and again, this produces an endless tower of larger and larger infinities.

The statement

Cantor's theorem. For every set A, there is no surjection from A onto P(A). Consequently |A| < |P(A)|.

The second sentence needs two facts. First, |A| โ‰ค |P(A)|, because a โ†ฆ {a} is an injection from A into P(A). Second, there is no bijection, since a bijection would be a surjection.

For finite sets, n < 2โฟ is old news. The theorem's power is that it also works for infinite A, where we cannot count.

The proof

Let f: A โ†’ P(A) be any function. Each f(x) is a subset of A. Define the diagonal set

Text
D = { x โˆˆ A : x โˆ‰ f(x) }

D collects the elements that are not members of the subset assigned to them. It is a subset of A, so D โˆˆ P(A).

Is D equal to f(a) for some a โˆˆ A? Suppose it were: D = f(a). Ask whether a โˆˆ D.

  • If a โˆˆ D, then by the definition of D, a โˆ‰ f(a). But f(a) = D, so a โˆ‰ D. Contradiction.
  • If a โˆ‰ D, then a โˆˆ f(a) by the definition of D (since a fails the test a โˆ‰ f(a)). But f(a) = D, so a โˆˆ D. Contradiction.

Either way we get a contradiction, so no such a exists. D is not in the image of f, and f is not surjective. This holds for every f, so no surjection A โ†’ P(A) exists.

This is exactly the diagonal argument. Think of f(x) as a row of a 0/1 table indicating which elements it contains. D is the diagonal with every bit flipped.

Brute force on a small set

Let A = {0, 1, 2}. There are 8 subsets, and 8ยณ = 512 functions A โ†’ P(A). We can check every one of them: for each, build D and verify it is not a value of f.

Python Check Cantor's theorem for every function on a 3-element set

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The diagonal set D is missing from the image for every function, and no function is surjective. For three elements this is obvious by size (a 3-element set cannot cover 8 subsets), but the check confirms the proof's claim function by function.

The diagonal set in action

For a specific f, we can see D appear. Take A = {1, 2, 3, 4} and f(1) = {1, 2}, f(2) = {3}, f(3) = {1, 2, 3}, f(4) = โˆ…. Then 1 โˆˆ f(1), 2 โˆ‰ f(2), 3 โˆˆ f(3), 4 โˆ‰ f(4), so D = {2, 4}. And {2, 4} is not among f(1), ..., f(4).

Python Compute the diagonal set D for any f

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the second example f(x) = {y : y < x} has x โˆ‰ f(x) for all x, so D = A. And A is not in the image: the largest f(x) is missing the top element.

A tower of infinities

Apply the theorem repeatedly:

Text
|โ„•| < |P(โ„•)| < |P(P(โ„•))| < |P(P(P(โ„•)))| < ...

So there are infinitely many different infinite cardinals; there is no largest set. If there were a set V containing everything, then P(V) would be a subset of V, forcing |P(V)| โ‰ค |V|, which contradicts Cantor's theorem. This is one way to see why the "set of all sets" causes trouble, a theme of Russell's paradox.

Where the power is used

Since a subset of A corresponds to a function A โ†’ {0, 1}, |P(A)| = 2^|A| in cardinal arithmetic. Cantor's theorem reads ฮบ < 2^ฮบ for every cardinal ฮบ. In particular โ„ตโ‚€ < 2^โ„ตโ‚€, and we call 2^โ„ตโ‚€ the cardinality of the continuum, ๐” . The next lesson shows it is also the cardinality of the real line.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the proof of Cantor's theorem, what is the diagonal set D?

    D collects the elements that are not members of the set f assigns to them.
  2. 2. Why is D not equal to f(a) for any a?

    If a โˆˆ D then a โˆ‰ f(a) = D; if a โˆ‰ D then a โˆˆ f(a) = D. Both are impossible.
  3. 3. Which map shows |A| โ‰ค |P(A)|?

    Sending each element to its own singleton is injective, so A injects into P(A).
  4. 4. What does Cantor's theorem imply about infinite cardinals?

    Taking power sets repeatedly gives strictly larger cardinals without end.

Summary

  • Cantor's theorem: |A| < |P(A)| for every set A, finite or infinite.
  • The proof builds D = {x โˆˆ A : x โˆ‰ f(x)}, which no f(a) can equal.
  • Repeated power sets give an endless tower of infinities; there is no largest set.
  • |P(A)| = 2^|A|, so the theorem says ฮบ < 2^ฮบ, and โ„ตโ‚€ < 2^โ„ตโ‚€ = ๐” .

Next: The Continuum and the Real Numbers