Ordered Pair Projections

Why

The product of two sets is a (sub)set of ordered pairs. Is every set of ordered pairs a subset of a product of two sets?

Result

The answer is easily seen to be yes. Let $R$ denote a set of ordered pairs. So for $x \in R$, $x = \set{\set{a}, \set{a, b}}$. First consider $\bigcup R$. Then $\set{a} \in \bigcup R$ and $\set{a, b} \in \bigcup R$. Next consder $\bigcup\bigcup R$. Then $a, b \in \bigcup\bigcup R$. So if we want two sets—denote them by $A$ and $B$—so that $R \subset A \times B$, we can take both $A$ and $B$ to be the set $\bigcup\bigcup R$.

Projections

We often want to shrink the sets $A$ and $B$ to include only the relevant members. In other words, to include only those members which appear as either the first coordinate (for $A$) or second coordinate (for $B$) in an element of $R$. We can do this by specifying the elements of $\bigcup\bigcup R$ which are actually a first coordinate or second coordinate for some ordered pair in the set $R$.

Define

\[ A' = \Set{a \in A}{(\exists b)((a, b) \in R)}, \]

and likewise

\[ B' = \Set{b \in B}{(\exists a)((a, b) \in R)}. \]

We call $A'$ the projection onto the first coordinate and $B'$ the projection onto the second coordinate.