Discrete Mathematics and Proof

Cantor's theorem: no set matches its power set

The real numbers are a bigger infinity than the natural numbers. Is there a biggest infinity of all, or can every set be outgrown?

You need

Uncountable sets and the diagonal argumentDiscrete Mathematics and Proof Power setDiscrete Mathematics and Proof

Where you are 4 in Infinite sets

Logic, proof and discrete math6

Sets15

Infinite sets4

Matching two sets one to one Countable sets Uncountable sets and the diagonal argument

Cantor's theorem: no set matches its power set

Why this exists

Uncountable sets and the diagonal argument showed that \mathbb{R} cannot be listed: infinite sets come in at least two sizes. Is \mathbb{R} as big as a set can get, or is there something bigger still, and something bigger than that?

Cantor’s theorem answers it for every set at once. No set A can be matched one to one with its Power set \mathcal{P}(A), and A always fits inside \mathcal{P}(A), so \mathcal{P}(A) is strictly bigger. Applying this over and over gives a ladder of larger and larger infinities that never stops. In a paper of 1891 Cantor gave this argument in the form of functions taking only the values 0 and 1, which (Example 5) is the same thing as subsets. Throughout, \mathbb{N} = \{0, 1, 2, \dots\}.

Definition

Recall from Matching two sets one to one that \lvert A \rvert = \lvert B \rvert means there is a bijection A \to B. Comparing sizes uses injections:

\lvert A \rvert \le \lvert B \rvert means there is an injection A \to B;
\lvert A \rvert < \lvert B \rvert means there is an injection A \to B and no bijection A \to B.

As with =, these compare a pair of sets; no number \lvert A \rvert is defined.

A function f : A \to \mathcal{P}(A) assigns to each member a of A a subset f(a) of A, and a itself either belongs to that subset or does not. The diagonal set of f collects the members that do not:

D_f = \{a \in A : a \notin f(a)\}.

It is carved out of A, so D_f \subseteq A and D_f \in \mathcal{P}(A).

Intuition

Figure 1The function f of Example 1. The shaded cell in row a answers “is a \in f(a)?” Flipping each answer gives the row D_f = \{1, 3\}, which differs from row a in column a and so is no f(a).

Write f as a table: row a marks with a 1 each member of f(a). Reading down the diagonal asks each a the question “are you in your own subset?” The set D_f is the row of flipped answers. It disagrees with row a in column a, for every a, so it is no row at all.

This is the diagonal argument in disguise. A subset X of \mathbb{N} is the same information as its indicator sequence, \chi_X(k) = 1 if k \in X and 0 if not. A function f : \mathbb{N} \to \mathcal{P}(\mathbb{N}) is then a list of binary sequences, row n being \chi_{f(n)}, and the diagonal digit \chi_{f(n)}(n) is 1 exactly when n \in f(n). The flipped diagonal t of Uncountable sets and the diagonal argument is \chi_{D_f}. Cantor’s theorem keeps only the flip, so it works for every set, listed or not.

Results

1. Cantor’s theorem. For every set A and every function f : A \to \mathcal{P}(A), the set D_f is not f(a) for any a \in A. So there is no surjection A \to \mathcal{P}(A), hence no bijection, and \lvert A \rvert \ne \lvert \mathcal{P}(A) \rvert.

2. The power set is strictly bigger. For every set A, \lvert A \rvert < \lvert \mathcal{P}(A) \rvert.

3. Schröder-Bernstein theorem (stated without proof). If there is an injection A \to B and an injection B \to A, then there is a bijection A \to B. So \lvert A \rvert \le \lvert B \rvert and \lvert B \rvert \le \lvert A \rvert together give \lvert A \rvert = \lvert B \rvert, and \lvert A \rvert < \lvert B \rvert holds exactly when there is an injection A \to B and no injection B \to A.

4. No way back. For every set A there is no injection \mathcal{P}(A) \to A.

5. No largest infinity. Every set has a strictly bigger one, its power set. In particular

\begin{aligned} \lvert \mathbb{N} \rvert &< \lvert \mathcal{P}(\mathbb{N}) \rvert \\ &< \lvert \mathcal{P}(\mathcal{P}(\mathbb{N})) \rvert < \cdots, \end{aligned}

and every set on this ladder after \mathbb{N} is uncountable.

6. Subsets of \mathbb{N} and real numbers. \lvert \mathcal{P}(\mathbb{N}) \rvert = \lvert \mathbb{R} \rvert (a sketch is given below).

7. There is no set of all sets.

Why it is true

Result 1. Proof. Let f : A \to \mathcal{P}(A) be any function, and let a \in A. We show f(a) \ne D_f by finding a member of one set that is not in the other; the member is a itself. Exactly one of two cases holds.

Case a \in f(a). Then a fails the condition that defines D_f, so a \notin D_f. Now a is in f(a) and not in D_f, so f(a) \ne D_f.

Case a \notin f(a). Then a meets the condition, so a \in D_f. Now a is in D_f and not in f(a), so again f(a) \ne D_f.

So D_f is a member of \mathcal{P}(A) that f never takes, and f is not onto. The function was arbitrary, so no function A \to \mathcal{P}(A) is onto, and since a bijection is onto, none is a bijection. \square

As a Proof by contradiction: if f(d) = D_f, then d \in D_f if and only if d \notin D_f.

Result 2. Proof. Define s : A \to \mathcal{P}(A) by s(a) = \{a\}; each \{a\} is a subset of A. If s(a) = s(b), then a \in \{a\} = \{b\}, so a = b, and s is an injection. By Result 1 there is no bijection. \square

Result 4. Proof. Suppose g : \mathcal{P}(A) \to A is an injection. Build f : A \to \mathcal{P}(A): if a = g(X) for some X, that X is unique because g is one to one, and we put f(a) = X; otherwise put f(a) = \varnothing. Every X \in \mathcal{P}(A) equals f(g(X)), so f is onto, against Result 1. \square

Result 5. Proof. Result 2 applied to A, then to \mathcal{P}(A), and so on, gives each inequality. Each rung after \mathbb{N} receives an injection from \mathcal{P}(\mathbb{N}): the singleton map s sends \mathcal{P}(\mathbb{N}) into \mathcal{P}(\mathcal{P}(\mathbb{N})), and composing such maps reaches every later rung. If a rung were countable, there would be an injection from it to \mathbb{N} (Countable sets, Result 4), and composing would give an injection \mathcal{P}(\mathbb{N}) \to \mathbb{N}, against Result 4. \square

Result 6. Sketch. An injection \mathcal{P}(\mathbb{N}) \to \mathbb{R}: send X to the number whose decimal digit in place n + 1 is 1 if n \in X and 0 if not. Two different subsets give two different digit strings using only 0 and 1, and two different expansions of one number require one of them to end in 9s (Result 3 of Uncountable sets and the diagonal argument), so the numbers differ. An injection \mathbb{R} \to \mathcal{P}(\mathbb{N}): match \mathbb{R} with (0, 1) (Matching two sets one to one), take the expansion 0.d_1 d_2 d_3 \dots that does not end in 9s, and send it to \{10(k - 1) + d_k : k \ge 1\}. The one member of this set lying between 10(k-1) and 10k - 1 gives back d_k, so the map is one to one. Result 3 joins the two injections into a bijection.

Result 7. Proof. Suppose V were a set whose members are all sets. Every subset of V is a set, so \mathcal{P}(V) \subseteq V, and X \mapsto X is an injection \mathcal{P}(V) \to V, against Result 4. \square

Running Result 1 directly shows what goes wrong. When every object is a set, f(x) = x is a function V \to \mathcal{P}(V) that is onto, and its diagonal set is

D_f = \{x : x \notin x\},

the set of all sets that are not members of themselves: the set of Russell’s paradox, named for Bertrand Russell. Asking whether D_f \in D_f gives “yes if and only if no”. The usual axioms of set theory let a condition define a set only inside a set already in hand, \{x \in A : \ldots\}, which is exactly the form D_f takes in Result 1.

Worked examples

Example 1

Finding the missed subset

Let A = \{1, 2, 3, 4\} and let f : A \to \mathcal{P}(A) be given by f(1) = \{2, 3\}, f(2) = \{1, 2, 4\}, f(3) = \varnothing, f(4) = \{1, 3, 4\}. Find D_f and check directly that f misses it.

Solution

Ask each member whether it lies in its own subset. 1 \notin \{2, 3\}, so 1 \in D_f. 2 \in \{1, 2, 4\}, so 2 \notin D_f. 3 \notin \varnothing, so 3 \in D_f. 4 \in \{1, 3, 4\}, so 4 \notin D_f. Hence D_f = \{1, 3\}, the bottom row of the figure.

\{1, 3\} is none of the four values, and each is ruled out by the member the proof names: 1 is in D_f and not in f(1), 2 is in f(2) and not in D_f, and likewise for 3 and 4. Here f misses 16 - 4 = 12 of the 2^4 = 16 subsets; the proof names one.

Example 2

The empty set

Check Results 1 and 2 when A = \varnothing.

Solution

\mathcal{P}(\varnothing) = \{\varnothing\} has one member. The only function \varnothing \to \{\varnothing\} is the empty function, which has no values at all, so it is not onto. The proof agrees: D_f = \{a \in \varnothing : a \notin f(a)\} = \varnothing, and \varnothing is exactly the member missed. The empty function is an injection (no two inputs to compare), so \lvert \varnothing \rvert < \lvert \{\varnothing\} \rvert.

Example 3

Prime divisors

Define f : \mathbb{N} \to \mathcal{P}(\mathbb{N}) by letting f(n) be the set of primes p with p \mid n. Find D_f and show directly that it is no f(n).

Solution

The question for n is whether n is a prime dividing n. Every number divides itself, so n \in f(n) exactly when n is prime. Hence D_f is the set of natural numbers that are not prime:

D_f = \{0, 1, 4, 6, 8, 9, 10, 12, \dots\}.

Directly: 0 \in D_f, while every f(n), such as f(12) = \{2, 3\}, f(1) = \varnothing or f(0), the set of all primes, contains only primes.

Example 4

The table behind the proof

Let f(n) be the set of multiples of n + 1 in \mathbb{N}. Write the first four rows of the indicator table, read D_f from the flipped diagonal, and confirm it for all n.

Solution

f(0) = \mathbb{N}, f(1) = \{0, 2, 4, \dots\}, f(2) = \{0, 3, 6, \dots\}, f(3) = \{0, 4, 8, \dots\}. In columns 0 to 4:

	0	1	2	3	4
\chi_{f(0)}	1	1	1	1	1
\chi_{f(1)}	1	0	1	0	1
\chi_{f(2)}	1	0	0	1	0
\chi_{f(3)}	1	0	0	0	1

The diagonal reads 1, 0, 0, 0; flipped, 0, 1, 1, 1. For every n \ge 1, 0 < n < n + 1, so n is not a multiple of n + 1 and n \notin f(n), while 0 \in f(0). So D_f = \{1, 2, 3, \dots\}, the positive integers. It is missed because 0 \notin D_f and 0, a multiple of everything, lies in every f(n).

Example 5

Functions from the real line to itself

Let \mathcal{F} be the set of all functions \mathbb{R} \to \mathbb{R}. Prove \lvert \mathbb{R} \rvert < \lvert \mathcal{F} \rvert.

Solution

An injection \mathbb{R} \to \mathcal{F}: send c to the constant function with value c; different constants give different functions.

No bijection: for X \subseteq \mathbb{R} let \chi_X be the function with \chi_X(x) = 1 for x \in X and 0 otherwise. If X \ne Y, some x lies in one and not the other, and there \chi_X(x) \ne \chi_Y(x); so X \mapsto \chi_X is an injection \mathcal{P}(\mathbb{R}) \to \mathcal{F}. (Every function to \{0, 1\} is some \chi_X, with X the set where it equals 1, which is why two-valued functions and subsets are the same thing.) If h : \mathcal{F} \to \mathbb{R} were a bijection, h \circ \chi would be an injection \mathcal{P}(\mathbb{R}) \to \mathbb{R}, which Result 4 forbids. So \lvert \mathbb{R} \rvert < \lvert \mathcal{F} \rvert.

Example 6

Schröder-Bernstein at work

Prove \lvert \mathbb{N} \times \mathcal{P}(\mathbb{N}) \rvert = \lvert \mathcal{P}(\mathbb{N}) \rvert, and find the image of (2, \{0, 3\}) under the injection you use.

Solution

\mathcal{P}(\mathbb{N}) \to \mathbb{N} \times \mathcal{P}(\mathbb{N}): X \mapsto (0, X), one to one because the second entry is X.

\mathbb{N} \times \mathcal{P}(\mathbb{N}) \to \mathcal{P}(\mathbb{N}): store X in the even numbers and n in one odd number,

(n, X) \mapsto \{2k : k \in X\} \cup \{2n + 1\}.

The even members halved give back X and the one odd member gives back n, so this is one to one. For instance (2, \{0, 3\}) \mapsto \{0, 6\} \cup \{5\} = \{0, 5, 6\}.

By Result 3 the sets are the same size.

Boundaries

The theorem names one missed subset, not all of them. A function on an n-member set misses at least 2^n - n subsets; D_f is the one the proof can always name. For finite sets Result 2 is just n < 2^n; the theorem matters for infinite sets.

“Bigger” means injections, and comparability is a separate fact. That any two sets at all can be compared, one injecting into the other, is equivalent to the axiom of choice and is not proved here.

The ladder does not say what lies between its rungs. Cantor’s theorem gives a set bigger than \mathbb{N}; it does not say \mathcal{P}(\mathbb{N}) is the next size up. Whether a set lies strictly between \mathbb{N} and \mathcal{P}(\mathbb{N}), which has the size of \mathbb{R}, is the continuum hypothesis, which the usual axioms neither prove nor refute.

The diagonal set must be carved out of a set. D_f is legitimate because it is \{a \in A : \ldots\} for a set A. Without a set A to carve from, the same recipe gives Russell’s \{x : x \notin x\}, which is not a set.

Where this goes next

The theorem closes this tour of Infinite sets: sizes are compared by injections, ordered with the help of Schröder-Bernstein, and have no top. The same self-reference returns in logic and computing, where it shows that some questions about all programs no program can answer.

Exercises

Running the proof

Let A = \{a, b, c\} with f(a) = \{a, c\}, f(b) = \{a\}, f(c) = \{b, c\}. Find D_f and check that it is not a value of f.
Let A = \{1, 2, 3\} and f(x) = A \setminus \{x\}. Find D_f and say why no f(x) equals it.
Let A = \{1, 2, 3, 4, 5\} and f(x) = \{y \in A : x + y \text{ is prime}\}. List the five values of f and find D_f.
Let A = \{1, 2\}. How many functions A \to \mathcal{P}(A) are there, and for how many of them is D_f = \varnothing?
A set A has 5 members. At least how many members of \mathcal{P}(A) does every function A \to \mathcal{P}(A) miss, and for which functions is that number exact?
Let f : \mathbb{N} \to \mathcal{P}(\mathbb{N}) be f(n) = \{k \in \mathbb{N} : k > n\}. Find D_f.
Let f(n) = \{k \in \mathbb{N} : k^2 \le n\}. Find f(0), f(3), f(4) and D_f, and show directly that D_f is no f(n).

Comparing sizes

Prove that g(a) = A \setminus \{a\} is an injection A \to \mathcal{P}(A) for every set A. For A = \{1, 2\}, which subsets does g miss?
Arrange \lvert \mathbb{N} \rvert, \lvert \mathbb{Q} \rvert, \lvert \mathbb{N} \times \mathbb{N} \rvert, \lvert \mathbb{R} \rvert, \lvert \mathcal{P}(\mathbb{N}) \rvert, \lvert \mathcal{P}(\mathbb{Q}) \rvert and \lvert \mathcal{P}(\mathbb{R}) \rvert in order, marking which are equal.
Prove that if \lvert A \rvert = \lvert B \rvert, then \lvert \mathcal{P}(A) \rvert = \lvert \mathcal{P}(B) \rvert.
Prove that if A \subseteq B, then \lvert \mathcal{P}(A) \rvert \le \lvert \mathcal{P}(B) \rvert. Give a proper subset A of \mathbb{N} with \lvert \mathcal{P}(A) \rvert = \lvert \mathcal{P}(\mathbb{N}) \rvert.
Let Z = \{X \subseteq \mathbb{N} : 0 \in X\} and u(X) = \{0\} \cup \{k + 1 : k \in X\}. Find u(\{0, 2\}) and prove that u : \mathcal{P}(\mathbb{N}) \to Z is a bijection.

Reasoning

Prove that if \lvert A \rvert < \lvert B \rvert and \lvert B \rvert < \lvert C \rvert, then \lvert A \rvert < \lvert C \rvert.
Let E_f = \{a \in A : a \in f(a)\}, the diagonal without the flip. Show by an example that E_f can be a value of f.
Find the flaw. Mael notes that s(n) = \{n\} misses \varnothing, so he patches the list: g(0) = \varnothing and g(n + 1) = \{n\}. “Each time a set is missed I put it at the front. Doing this forever lists all of \mathcal{P}(\mathbb{N}).” Find D_g and explain what is wrong.
Let U be the union of \mathbb{N}, \mathcal{P}(\mathbb{N}), \mathcal{P}(\mathcal{P}(\mathbb{N})) and so on. Prove that U is strictly bigger than every set on this ladder.
Prove that no function A \to \mathcal{P}(\mathcal{P}(A)) is onto.

Answers

D_f = \{b\}: a \in f(a), b \notin \{a\}, c \in f(c). The values are \{a, c\}, \{a\}, \{b, c\}, and \{b\} is none of them.
D_f = \{1, 2, 3\} = A, since x \notin A \setminus \{x\} always. Each f(x) has 2 members, and A has 3.
f(1) = \{1, 2, 4\}, f(2) = \{1, 3, 5\}, f(3) = \{2, 4\}, f(4) = \{1, 3\}, f(5) = \{2\}. Only 1 + 1 = 2 makes x \in f(x), so D_f = \{2, 3, 4, 5\}, which is not on the list.
4^2 = 16 functions. D_f = \varnothing needs 1 \in f(1) and 2 \in f(2): two choices for each, so 4 functions.
2^5 - 5 = 27. A function has at most 5 values; it misses exactly 27 when its five values are different, that is, when it is injective.
D_f = \mathbb{N}, since n > n is false, so n \notin f(n) for every n.
f(0) = \{0\}, f(3) = \{0, 1\}, f(4) = \{0, 1, 2\}. n \in f(n) means n^2 \le n, true only for n = 0 and n = 1, so D_f = \{2, 3, 4, \dots\}. D_f does not contain 0, and every f(n) does.
If A \setminus \{a\} = A \setminus \{b\} with a \ne b, then b \in A \setminus \{a\} = A \setminus \{b\}, which is false. For A = \{1, 2\}, g(1) = \{2\} and g(2) = \{1\}, so g misses \varnothing and \{1, 2\}.
In order, with equal sizes on one line:

\begin{aligned} \lvert \mathbb{N} \rvert &= \lvert \mathbb{Q} \rvert = \lvert \mathbb{N} \times \mathbb{N} \rvert \\ &< \lvert \mathbb{R} \rvert = \lvert \mathcal{P}(\mathbb{N}) \rvert = \lvert \mathcal{P}(\mathbb{Q}) \rvert \\ &< \lvert \mathcal{P}(\mathbb{R}) \rvert \end{aligned}

by Countable sets, Uncountable sets and the diagonal argument, Result 6, Exercise 10 and Result 2. 10. Proof. Let h : A \to B be a bijection and send X \subseteq A to h[X] = \{h(x) : x \in X\}. The inverse h^{-1} does the same in reverse, and the two maps undo each other, so this is a bijection \mathcal{P}(A) \to \mathcal{P}(B). \square 11. Proof. Every subset of A is a subset of B, so X \mapsto X is an injection. For the example, the even numbers E: \lvert E \rvert = \lvert \mathbb{N} \rvert, so Exercise 10 gives \lvert \mathcal{P}(E) \rvert = \lvert \mathcal{P}(\mathbb{N}) \rvert. \square 12. u(\{0, 2\}) = \{0, 1, 3\}. Proof. u(X) contains 0, so it lies in Z. Given Y \in Z, the set X = \{k : k + 1 \in Y\} has u(X) = Y, so u is onto, and this X is the only one, since u(X) determines each k by whether k + 1 is in it. \square 13. Proof. Composing injections A \to B \to C gives an injection A \to C. If there were a bijection A \to C, its inverse composed with the injection A \to B would be an injection C \to B; with the injection B \to C, Result 3 would give \lvert B \rvert = \lvert C \rvert, which is false. \square 14. Take A = \{1\} and f(1) = \{1\}. Then E_f = \{1\} = f(1): without the flip nothing forces a disagreement at a. 15. 0 \notin g(0) and n + 1 \notin \{n\}, so D_g = \mathbb{N}, which g misses. Each patch makes a new function, and Result 1 applies to every function, including whatever list “forever” ends with; there is always a new missed set. 16. Proof. Each rung L is a subset of U, so inclusion is an injection L \to U. The next rung \mathcal{P}(L) is also a subset of U. A bijection U \to L would make the inclusion of \mathcal{P}(L) followed by it an injection \mathcal{P}(L) \to L, against Result 4. \square 17. Proof. Suppose h : A \to \mathcal{P}(\mathcal{P}(A)) is onto. Put f(a) = X when h(a) = \{X\}, and f(a) = \varnothing when h(a) is not a one-member set. Each X \subseteq A has \{X\} = h(a) for some a, so f(a) = X and f : A \to \mathcal{P}(A) is onto, against Result 1. \square