11.3 Power sets

We finish this section by showing that there are infinitely many different types of infinities.

Definition 11.16:
Let A be a set. We define the power set of A, denoted by \mathcal{P}(A), to be the set \mathcal{P}(A)=\{C: C\subseteq A\}.
Example:

We have the following examples:

  • \mathcal{P}(\emptyset)=\{\emptyset\}, so |\mathcal{P}(\emptyset)|=1.

  • \mathcal{P}(\{1,2\})=\{\emptyset,\{1\},\{2\},\{1,2\}\}, so |\mathcal{P}(\{1,2\})|=4=2^2.

  • \mathcal{P}(\{1,2,3\})=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}. So |\mathcal{P}(\{1,2,3\})|=8=2^3.

Note that, for any nonempty set X, we know that \emptyset, X are distinct subsets of X. Hence, we have that |\mathcal{P}(X)|\ge 2. We have the following two results, whose proofs are left as an exercise.

Lemma 11.17:

Suppose that A is a finite set with |A|=n for some n\in\mathbb{Z}_{\geq 0}. Then |\mathcal{P}(A)|=2^n.

Proof.

Exercise.

Proposition 11.18:

Let A,B be sets. Then

  • A\subseteq B if and only if \mathcal{P}(A)\subseteq\mathcal{P}(B).

  • \mathcal{P}(A)\cup\mathcal{P}(B)\subseteq\mathcal{P}(A\cup B).

  • \mathcal{P}(A)\cap\mathcal{P}(B)=\mathcal{P}(A\cap B).

Proof.

Exercise.

Theorem 11.19:

Let X be a set. Then |X|<|\mathcal{P}(X)|.

Proof.

Suppose X=\emptyset. Then |X|=0<1=|\mathcal{P}(X)|.

So suppose X is nonempty, and define f:X\to\mathcal{P}(X) by f(x)=\{x\}, for all x\in X. We show that f is injective. Let x_1,x_2\in X be such that f(x_1)=f(x_2). Then \{x_1\}=\{x_2\}. Hence, we have that x_1=x_2. Therefore, f is injective, so |X|\le|\mathcal{P}(X)|.

Next, we use contradiction to show that there exists no bijection between X and \mathcal{P}(X). Suppose there exists such a bijection g:X\to\mathcal{P}(X). Note that for every x\in X, g(x)\in \mathcal{P}(X) means g(x)\subseteq X. Define A=\{x\in X: x\not\in g(x)\} . Then A is a subset of X, so A\in\mathcal{P}(X). Furthermore, since g is bijective, there exists some z\in X such that g(z)=A. By the definition of A, we have z\in A if and only if z\not\in g(z)=A, which is a contradiction (namely z\in A \iff z\not\in A). Therefore, our assumption that there exists a bijection g:X\to\mathcal{P}(X) is false. So |X|\neq |\mathcal{P}(X)|.

It follows that |X|<|\mathcal{P}(X)|.

History:

The above theorem is sometimes known as Cantor’s theorem. For a finite set, the result is clear, and Cantor re-used the diagonalisation method to prove the above for infinite set.

Corollary 11.20:

We have:

  • \mathcal{P}(\mathbb{Z}_+) is uncountable.

  • |\mathcal{P}(\mathbb{R})|>|\mathbb{R}|, i.e. there are different type of uncountability.

We can extend on our last bullet point to see that |\mathbb{R}|<|\mathcal{P}(\mathbb{R})|<|\mathcal{P}(\mathcal{P}(\mathbb{R}))|<|\mathcal{P}(\mathcal{P}(\mathcal{P}(\mathbb{R})))|<...., i.e. there are infinitely many different type of infinities.