# Subset of Cartesian Product

## Theorem

Let $S$ be a set of ordered pairs.

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

## Proof

Let $S$ be a set of ordered pairs.

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$

## Sources

- 1960: Paul R. Halmos:
*Naive Set Theory*... (previous) ... (next): $\S 6$: Ordered Pairs