Theorem. Whenever $X$ and $Y$ are sets, $X \times Y$ is also a set.

Proof.

The definition of the Cartesian product of two sets states that $$X \times Y := \{ (x,y) : x \in X \wedge y \in Y \}.$$ If we're now applying Kuratowski's definition of an ordered pair $$(x,y) := \{ \{ x \}, \{ x, y \} \},$$ $X \times Y$ becomes a subset of the power set of the power set of $X \cup Y$: $$X \times Y \subseteq 2^{2^{X \cup Y}}.$$ Since $X \cup Y$ is set due to the axiom of pairwise union (3.4), $2^{X \cup Y}$ is a set due to lemma 3.4.9 for the set of all subsets and $2^{2^{X \cup Y}}$ is a set for the same reason, the subset $X \times Y$ of the set $2^{2^{X \cup Y}}$ is also a set.

For an example of a power set of a power set of $X \cup Y$, let $X := \{ x_1, x_2 \}$ and $Y:=\{ y_1, y_2 \}$, such that $X \cup Y = \{ x_1, x_2, y_1, y_2 \}$. The power set of $X \cup Y$ is then the set of all sub sets of $X \cup Y$: $$2^{X \cup Y} = \{ \emptyset, \{x_1\}, \{x_2\}, \{y_1\}, \{y_2\}, \{x_1, x_2\}, \{x_1, y_1\}, ..., \{ x_1, x_2, y_1 \}, \{ x_1, x_2, y_2 \}, ..., \{ x_1, x_2, y_1, y_2 \} \}.$$ Accordingly, the power set of the power set of $X \cup Y$ is the set of all sub sets of $2^{X \cup Y}$: $$2^{2^{X \cup Y}} = \{ \emptyset, \{\{ x_1 \}\}, ..., \{\{ x_1 \}, \{ x_1, x_2 \}\}, ..., \{ \{x_1\}, \{x_2\}, ..., \{ x_1, x_2, y_1, y_2 \} \} \}.$$
2015 FEB 08 (v1.0)
Contact me: m.herrmann followed by an -at- followed by blaetterundsterne.org.

This document created with the help of MathJax (Thank you guys!)