Projection is Surjection

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ and $T$ be non-empty sets.

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

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


Then $\pr_1$ and $\pr_2$ are both surjections.


General Version

For all non-empty sets $S_1, S_2, \ldots, S_j, \ldots, S_n$, the $j$th projection $\operatorname{pr}_j$ on $\displaystyle \prod_{i \mathop = 1}^n S_i$ is a surjection.


Family of Sets

Let $\family {S_\alpha}_{\alpha \mathop \in I}$ be a family of sets.

Let $\displaystyle \prod_{\alpha \mathop \in I} S_\alpha$ be the Cartesian product of $\family {S_\alpha}_{\alpha \mathop \in I}$.

Let each of $S_\alpha$ be non-empty.

For each $\beta \in I$, let $\displaystyle \pr_\beta: \prod_{\alpha \mathop \in I} S_\alpha \to S_\beta$ be the $\beta$th projection on $\displaystyle S = \prod_{\alpha \mathop \in I} S_\alpha$.


Then $\pr_\beta$ is a surjection.


Proof

Let $S$ and $T$ be sets such that neither is empty.


Let $\pr_1: S \times T \to S$ be the first projection on $S \times T$.

Then by definition of first projection:

$\displaystyle \forall x \in S: \exists \tuple {x, t} \in S \times T: \map {\pr_1} {x, t} = x$


Similarly, let $\pr_2: S \times T \to T$ be the second projection on $S \times T$.

Then by definition of second projection:

$\displaystyle \forall x \in T: \exists \tuple {s, x} \in S \times T: \map {\pr_2} {s, x} = x$


Hence the result.

$\blacksquare$


Sources