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

Definition Given a set $A$, the set of all subsets of $A$ is called the power set of $A$. It is denoted $𝒫(A)$.

Example If $A=\{a,b,c\}$ then $𝒫(A)=\{\mathrm{\varnothing },\{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 $𝒫(A)$.

This means that $(a,b)$ is a subset of $𝒫(A)$, i.e. $(a,b)\in 𝒫(𝒫(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 𝒫(𝒫(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 𝒫(𝒫(A\cup B))|x=(a,b),a\in A\text{and}b\in B\}$. This is a set by the axioms of Power Set, Union and the Axiom Schema of Comprehension. $◻$

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