Bijection between S x T and T x S

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$.


Then there exists a bijection from $S \times T$ to $T \times S$.


Proof

Let $\phi: S \times T \to T \times S$ be the mapping defined as:

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


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


The domain of $\phi$ is $S \times T$.

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

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

Thus $\phi$ is a surjection.


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

Then:

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

and so $\phi$ is an injection.

Hence the result by definition of bijection.

$\blacksquare$


Sources