Subset of Cartesian Product

From ProofWiki

Jump to: navigation, search

Theorem

Then $S$ is the subset of the cartesian product of two sets.

Let $x \in S$ such that $x = \left\{{\left\{{a}\right\}, \left\{{a, b}\right\}}\right\}$ as defined in Kuratowski Formalization of Ordered Pair.

Since the elements of $S$ are sets, we can form the union $\mathbb S = \bigcup S$ of the sets in $S$.

Since $x \in S$ it follows that the elements of $x$ are elements of $\mathbb S$.

Since $\left\{{a, b}\right\} \in x$ it follows that $\left\{{a, b}\right\} \in \mathbb S$.

Now we can form the union $\mathbb S' = \bigcup \mathbb S$ of the sets in $\mathbb S$.

Since $\left\{{a, b}\right\} \in \mathbb S$ it follows that both $a$ and $b$ are elements of $\mathbb S' = \bigcup \bigcup S$.

Thus from the Kuratowski Formalization of Ordered Pair we have that $S$ is a subset of some $A \times B$.

We can at this stage take both $A$ and $B$ as being equal to $\bigcup \bigcup S$.

Finally, the axiom of subsets is applied to construct the sets:

$A = \left\{{a: \exists b: \left({a, b}\right) \in S}\right\}$

and

$B = \left\{{b: \exists a: \left({a, b}\right) \in S}\right\}$

$A$ and $B$ are seen to be the first and second projections respectively of $S$.

$\blacksquare$