# 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 ${\displaystyle A}$ , i.e. ${\displaystyle \{U\;|\;U\subseteq A\}}$ . That this is a set is the subject of the Power Set Axiom.

Axiom

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

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

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

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

Example If ${\displaystyle A=\{a,b,c\}}$  then ${\displaystyle {\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, ${\displaystyle (a,b)=\{\{a\},\{a,b\}\}}$  for ${\displaystyle a}$  and ${\displaystyle b}$  elements of a set ${\displaystyle A}$ . Note that ${\displaystyle \{a\}}$  and ${\displaystyle \{a,b\}}$  are both subsets of ${\displaystyle A}$ , i.e. they are elements of the power set ${\displaystyle {\mathcal {P}}(A)}$ .

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

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

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

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

Proof The set in question is given by ${\displaystyle \{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. ${\displaystyle \square }$

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

## Exercises

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