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.