# Bijection between R x (S x T) and (R x S) x T

## Theorem

Let $R$, $S$ and $T$ be sets.

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

Then there exists a bijection from $R \times \paren {S \times T}$ to $\paren {R \times S} \times T$.

Hence:

$\card {R \times \paren {S \times T} } = \card {\paren {R \times S} \times T}$

## Proof

Let $\phi: R \times \paren {S \times T} \to \paren {R \times S} \times T$ be the mapping defined as:

$\forall \tuple {r, \tuple {s, t} } \in R \times \paren {S \times T}: \map \phi {s, t} = \tuple {\tuple {r, s}, t}$

Then $\phi$ is the bijection required, as follows:

The domain of $\phi$ is $R \times \paren {S \times T}$.

Let $\tuple {\tuple {r, s}, t} \in \paren {R \times S} \times T$.

Then there exists $\tuple {r, \tuple {s, t} } \in R \times \paren {S \times T}$ such that $\map \phi {r, \tuple {s, t} } = \tuple {\tuple {r, s}, t}$.

Thus $\phi$ is a surjection.

Let $\map \phi {r_1, \tuple {s_1, t_1} } = \map \phi {r_2, \tuple {s_2, t_2} }$ for some $\tuple {r_1, \tuple {s_1, t_1} }$ and $\tuple {r_2, \tuple {s_2, t_2} }$ in $R \times \paren {S \times T}$.

Then:

 $\displaystyle \map \phi {r_1, \tuple {s_1, t_1} }$ $=$ $\displaystyle \map \phi {r_2, \tuple {s_2, t_2} }$ $\displaystyle \leadsto \ \$ $\displaystyle \tuple {\tuple {r_1, s_1}, t_1}$ $=$ $\displaystyle \tuple {\tuple {r_2, s_2}, t_2}$ Definition of $\phi$ $\displaystyle \leadsto \ \$ $\displaystyle \tuple {r_1, \tuple {s_1, t_1} }$ $=$ $\displaystyle \tuple {r_2, \tuple {s_2, t_2} }$ Definition of Ordered Pair

and so $\phi$ is an injection.

Hence the result by definition of bijection.

$\blacksquare$