Cartesian Product is Set Product

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ and $T$ be sets.

Let $S \times T$ be the Cartesian product of $S$ and $T$.

Let $\pr_1: S \times T \to S$ and $\pr_2: S \times T \to T$ be the first and second projections respectively on $S \times T$.


Then $\struct {S \times T, \pr_1, \pr_2}$ is a set product.


Proof

Consider any set $X$ and mappings $f_1: X \to S$ and $f_2: X \to T$.

Define $h: X \to S \times T$ by:

$\forall x \in X: \map h x = \tuple {\map {f_1} x, \map {f_2} x}$

Then for all $x \in X$ we have:

$\map {\paren {\pr_1 \mathop \circ h} } x = \pr_1 \tuple {\map {f_1} x, \map {f_2} x} = \map {f_1} x)$

and

$\map {\paren {\pr_2 \mathop \circ h} } x = \pr_2 \tuple {\map {f_1} x, \map {f_2} x} = \map {f_2} x$

So:

$\pr_1 \mathop \circ h = f_1$
$\pr_2 \mathop \circ h = f_2$

Thus $h$ is shown to exist.


Suppose there exists a mapping $k: X \to S \times T$ such that:

$\pr_1 \mathop \circ k = f_1$
$\pr_2 \mathop \circ k = f_2$

Let $x \in X$ and let $\map k x = \tuple {s, t}$.

Then:

$\map {f_1} x = \map {\paren {\pr_1 \mathop \circ k} } x = \map {\pr_1} {s, t} = s$
$\map {f_2} x = \map {\paren {\pr_2 \mathop \circ k} } x = \map {\pr_2} {s, t} = t$

and so:

\(\displaystyle \map k x\) \(=\) \(\displaystyle \tuple {s, t}\)
\(\displaystyle \) \(=\) \(\displaystyle \tuple {\map {f_1} x, \map {f_2} x}\)
\(\displaystyle \) \(=\) \(\displaystyle \map h x\)

and so $k = h$.


So $h$ is unique.

Hence the result.

$\blacksquare$


Sources