11.3 Power sets
We finish this section by showing that there are infinitely many different types of infinities.
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.
Suppose that A is a finite set with |A|=n for some n\in\mathbb{Z}_{\geq 0}. Then |\mathcal{P}(A)|=2^n.
Exercise.
□
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).
Exercise.
□
Let X be a set. Then |X|<|\mathcal{P}(X)|.
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)|.□
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.
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.