Cartesian Product of Bijections is Bijection/General Result

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $I$ be an indexing set.

Let $\left\langle{S_i}\right\rangle_{i \mathop \in I}$ and $\left\langle{T_i}\right\rangle_{i \mathop \in I}$ be families of sets indexed by $I$.

Let $\displaystyle \mathcal S := \prod_{i \mathop \in I} S_i$ and $\displaystyle \mathcal T := \prod_{i \mathop \in I} T_i$ be the Cartesian products of $\left\langle{S_i}\right\rangle_{i \mathop \in I}$ and $\left\langle{T_i}\right\rangle_{i \mathop \in I}$ respectively.


For all $i \in I$, let $f_i: S_i \to T_i$ be a bijection.


Let $\displaystyle \mathcal F: \mathcal S \to \mathcal T := \prod_{i \mathop \in I} \left({f_i: S_i \to T_i}\right)$ be the Cartesian product of $\left\langle{f_i}\right\rangle_{i \mathop \in I}$ defined as:

$\displaystyle \forall \mathbf s \in \mathcal S: \mathcal F \left({\mathbf s}\right) := \prod_{i \mathop \in I} \left({f_i \left({s_i}\right)}\right)$

where $\mathbf s := \left\langle{s_i}\right\rangle_{i \mathop \in I}$ is an arbitrary element of $\left\langle{S_i}\right\rangle_{i \mathop \in I}$.


Then $\mathcal F$ is a bijection.


Proof

Because $f_i$ are bijections, it follows by definition that they are surjections.

Let $\mathbf t := \left\langle{t_i}\right\rangle_{i \mathop \in I} \in \mathcal T$.

Then as $f_i$ is a surjection:

$\forall i \in I: \exists s_i \in S_i: f_i \left({s_i}\right) = t_i$

Thus:

$\exists \mathbf s \in \mathcal S: \mathcal F \left({\mathbf s}\right) = \mathbf t$

So $\mathcal F$ is a surjection.


Because $f_i$ are bijections, it follows by definition that they are injections.

Let:

$\mathbf t_1 := \left\langle{t_{i 1} }\right\rangle_{i \mathop \in I} \in \mathcal T$
$\mathbf t_2 := \left\langle{t_{i 2} }\right\rangle_{i \mathop \in I} \in \mathcal T$

Let:

$\mathcal F \left({\mathbf s_1}\right) = \left({\mathbf t_1}\right), \mathcal F \left({\mathbf s_2}\right) = \left({\mathbf t_2}\right)$

for some $\mathbf s_1, \mathbf s_2 \in \mathcal S$ where:

$\mathbf s_1 := \left\langle{s_{i 1} }\right\rangle_{i \mathop \in I}$
$\mathbf s_2 := \left\langle{s_{i 2} }\right\rangle_{i \mathop \in I}$


Suppose $\mathbf t_1 = \mathbf t_2$.

Then:

$\forall i \in I: t_{i 1} = t_{i 2}$

By definition of $\mathcal F$:

$\forall i \in I: f_i \left({s_{i 1} }\right) = t_{i 1}$
$\forall i \in I: f_i \left({s_{i 2} }\right) = t_{i 2}$

As $f_i$ is an injection for all $i \in I$:

$\forall i \in I: t_{i 1} = t_{i 2 }\implies s_{i 1} = s_{i 2}$

Thus it follows that:

$\mathbf t_1 = \mathbf t_2 \implies \mathbf s_1 = \mathbf s_2$

and so $\mathcal F$ is an injection.


So $\mathcal F$ is a surjection and also an injection.

Hence by definition, $\mathcal F$ is a bijection.

$\blacksquare$