Cardinality of Cartesian Product/Corollary/Proof 2

From ProofWiki
Jump to navigation Jump to search

Corollary to Cardinality of Cartesian Product

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


Proof

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

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

which is shown to be bijective as follows:


\(\displaystyle \map f {s_1, t_1}\) \(=\) \(\displaystyle \map f {s_2, t_2}\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \tuple {t_1, s_1}\) \(=\) \(\displaystyle \tuple {t_2, s_2}\) Definition of $f$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \tuple {s_1, t_1}\) \(=\) \(\displaystyle \tuple {s_2, t_2}\) Equality of Ordered Pairs

showing $f$ is an injection.


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

Then:

$\exists \tuple {s, t} \in S \times T: \map f {s, t} = \tuple {t, s}$

showing that $f$ is a surjection.


So we have demonstrated that there exists a bijection from $S \times T$ to $T \times S$.

The result follows by definition of set equivalence.

$\blacksquare$


Sources