# Mathematical Proof and the Principles of Mathematics/Sets/Power sets

## Power sets

Power sets allow us to discuss the class of all subsets of a given set $A$ , i.e. $\{U\;|\;U\subseteq A\}$ . That this is a set is the subject of the Power Set Axiom.

Axiom

Given a set $A$  there exists a set of sets $S$  such that $U\in S$  iff $U\subseteq A$ .

Theorem Given a set $A$ , there exists a unique set whose elements are the subsets of $A$ .

Proof If $S_{1}$  and $S_{2}$  are two such sets of subsets then $U\in S_{1}$  if and only if $U\subseteq A$ . But the same is true of $S_{2}$ . Thus $U\in S_{1}$  iff $U\in S_{2}$ , and so $S_{1}=S_{2}$  by the Axiom of Extensionality. $\square$

Definition Given a set $A$ , the set of all subsets of $A$  is called the power set of $A$ . It is denoted ${\mathcal {P}}(A)$ .

Example If $A=\{a,b,c\}$  then ${\mathcal {P}}(A)=\{\emptyset ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$ .

## Cartesian products

Recall the Kuratowski definition of an ordered pair, $(a,b)=\{\{a\},\{a,b\}\}$  for $a$  and $b$  elements of a set $A$ . Note that $\{a\}$  and $\{a,b\}$  are both subsets of $A$ , i.e. they are elements of the power set ${\mathcal {P}}(A)$ .

This means that $(a,b)$  is a subset of ${\mathcal {P}}(A)$ , i.e. $(a,b)\in {\mathcal {P}}({\mathcal {P}}(A))$ .

We can generalise this slightly with a simple trick. We can define $(a,b)$  with $a\in A$  and $b\in B$  for sets $A$  and $B$ . In order to do this, we simply take the elements $a$  and $b$  from the union of sets $A\cup B$ .

In other words, we have $(a,b)\in {\mathcal {P}}({\mathcal {P}}(A\cup B))$  with $a\in A$  and $b\in B$ .

Theorem The class of all ordered pairs $(a,b)$  of elements of $A\cup B$  with $a\in A$  and $b\in B$ , is a set.

Proof The set in question is given by $\{x\in {\mathcal {P}}({\mathcal {P}}(A\cup B))\;|\;x=(a,b),a\in A\;{\mbox{and}}\;b\in B\}$ . This is a set by the axioms of Power Set, Union and the Axiom Schema of Comprehension. $\square$

Definition The set of ordered pairs $(a,b)$  with $a\in A$  and $b\in B$  is called the cartesian product of $A$  and $B$ , and is denoted $A\times B$ .

## Exercises

• Show that for sets $A,B,C,D$  we have $(A\cap B)\times (C\cap D)=(A\times C)\cap (B\times D)$ .
• Show that for sets $A,B,C$  we have $A\times (B\cap C)=(A\times B)\cap (A\times C)$ .
• Show that for sets $A,B,C$  we have $A\times (B\cup C)=(A\times B)\cup (A\times C)$ .
• Show that for sets $A,B,C$  with $A\subseteq B$  we have $A\times C\subseteq B\times C$ .