Cardinality of Cartesian Product/Corollary

From ProofWiki
Jump to: navigation, search

Corollary to Cardinality of Cartesian Product

Let $S \times T$ be the cartesian product of two sets $S$ and $T$ which are both finite.


Then:

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

where $\card {S \times T}$ denotes the cardinality of $S \times T$.


Proof 1

\(\displaystyle \left\vert{S \times T}\right\vert\) \(=\) \(\displaystyle \left\vert{S}\right\vert \times \left\vert{T}\right\vert\) $\quad$ Cardinality of Cartesian Product $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left\vert{T}\right\vert \times \left\vert{S}\right\vert\) $\quad$ Integer Multiplication is Commutative $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left\vert{T \times S}\right\vert\) $\quad$ Cardinality of Cartesian Product $\quad$

$\blacksquare$


Proof 2

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

$\forall \left({s, t}\right) \in S \times T: f \left({s, t}\right) = \left({t, s}\right)$

which is shown to be bijective as follows:


\(\displaystyle f \left({s_1, t_1}\right)\) \(=\) \(\displaystyle f \left({s_2, t_2}\right)\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \left({t_1, s_1}\right)\) \(=\) \(\displaystyle \left({t_2, s_2}\right)\) $\quad$ Definition of $f$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \left({s_1, t_1}\right)\) \(=\) \(\displaystyle \left({s_2, t_2}\right)\) $\quad$ Equality of Ordered Pairs $\quad$

showing $f$ is an injection.


Let $\left({t, s}\right) \in T \times S$.

Then:

$\exists \left({s, t}\right) \in S \times T: f \left({s, t}\right) = \left({t, s}\right)$

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