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