# 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$ .