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