3.3: Power Sets

Definition

Given a set $A,$ we call the set of all subsets of $A$ the power set of $A,$ which we denote $\mathcal{P}(A)$.

Example $\PageIndex{1}$

If $A=\{1,2,3\},$ then

$$\mathcal{P}(A)=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}.$$

Proposition $\PageIndex{1}$

If $A$ is finite with $|A|=n,$ then $|\mathcal{P}(A)|=2^{n}$.

Proof

Let

$$B=\left\{\left(b_{1}, b_{2}, \ldots, b_{n}\right): b_{i}=0 \text { or } b_{i}=1, i=1,2, \ldots, n\right\}$$

and let $a_{1}, a_{2}, \ldots, a_{n}$ be the elements of $A .$ Define $\varphi: B \rightarrow \mathcal{P}(A)$ by letting

$$\varphi\left(b_{1}, b_{2}, \ldots, b_{n}\right)=\left\{a_{i}: b_{i}=1, i=1,2, \ldots, n\right\}.$$

Then $\varphi$ is a one-to-one correspondence. The result now follows from the next exercise. $\quad$ Q.E.D.

Exercise $\PageIndex{1}$

With $B$ as in the previous proposition, show that $|B|=2^{n}$.

In analogy with the case when $A$ is finite, we let $2^{|A|}=|\mathcal{P}(A)|$ for any nonempty set $A .$

Definition

Suppose $A$ and $B$ are sets for which there exists a one-to-one function $\varphi: A \rightarrow \bar{B}$ but there does not exist a one-to-one correspondence $\psi: A \rightarrow B .$ Then we write $|A|<|B| .$

Theorem $\PageIndex{2}$

If $A$ is a nonempty set, then $|A|<|\mathcal{P}(A)|$.

Proof

Define $\varphi: A \rightarrow \mathcal{P}\left(\mathbb{Z}^{+}\right)$ by

$$\varphi\left(\left\{a_{i}\right\}_{i=1}^{\infty}\right)=\left\{i: i \in \mathbb{Z}^{+}, a_{i}=1\right\}.$$

Then $\varphi$ is a one-to-one correspondence. $\quad$ Q.E.D.

Now let $B$ be the set of all sequences $\left\{a_{i}\right\}_{i=1}^{\infty}$ in $A$ such that for every integer $N$ there exists an integer $n>N$ such that $a_{n}=0 .$ Let $C=A \backslash B$,

$$D_{0}=\left\{\left\{a_{i}\right\}_{i=1}^{\infty}: a_{i}=1, i=1,2,3, \ldots\right\},$$

and

$$D_{j}=\left\{\left\{a_{i}\right\}_{i=1}^{\infty}: a_{j}=0, a_{k}=1 \text { for } k>j\right\}$$

for $j=1,2,3, \ldots$ Then $\left|D_{0}\right|=1$ and $\left|D_{j}\right|=2^{j-1}$ for $j=1,2,3, \ldots$ Moreover,

$$C=\bigcup_{j=0}^{\infty} D_{j},$$

so $C$ is countable. Since $A=B \cup C,$ and $A$ is uncountable, it follows that $B$ is uncountable. Now if we let

$$I=\{x: x \in \mathbb{R}, 0 \leq x<1\},$$

we have seen that the function $\varphi: B \rightarrow I$ defined by

$$\varphi\left(\left\{a_{i}\right\}_{i=1}^{\infty}\right)=a_{1} a_{2} a_{3} a_{4} \ldots$$

is a one-to-one correspondence. It follows that $I$ is uncountable. As a consequence, we have the following result.

Theorem $\PageIndex{4}$

$\mathbb{R}$ is uncountable.

Exercise $\PageIndex{2}$

Let $I=\{x: x \in \mathbb{R}, 0 \leq x<1\} .$ Show that

a. $|I|=|\{x: x \in \mathbb{R}, 0 \leq x \leq 1\}|$

b. $|I|=|\{x: x \in \mathbb{R}, 0<x<1\}|$

c. $|I|=|\{x: x \in \mathbb{R}, 0<x<2\}|$

d. $|I|=|\{x: x \in \mathbb{R},-1<x<1\}|$

Exercise $\PageIndex{3}$

Let $I=\{x: x \in \mathbb{R}, 0 \leq x<1\}$ and suppose $a$ and $b$ are real numbers with $a<b .$ Show that

$$|I|=|\{x: x \in \mathbb{R}, a \leq x<b\}|.$$

Exercise $\PageIndex{4}$

Does there exist a set $A \subset \mathbb{R}$ for which $\aleph_{0}<|A|<2^{\aleph_{0}} ?$ (Before working too long on this problem, you may wish to read about Cantor's continum hypothesis.)