# Cardinality of Cartesian Product/Corollary

Jump to navigation
Jump to 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

\(\ds \card {S \times T}\) | \(=\) | \(\ds \card S \times \card T\) | Cardinality of Cartesian Product | |||||||||||

\(\ds \) | \(=\) | \(\ds \card T \times \card S\) | Integer Multiplication is Commutative | |||||||||||

\(\ds \) | \(=\) | \(\ds \card {T \times S}\) | Cardinality of Cartesian Product |

$\blacksquare$

## Proof 2

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:

\(\ds \map f {s_1, t_1}\) | \(=\) | \(\ds \map f {s_2, t_2}\) | ||||||||||||

\(\ds \leadsto \ \ \) | \(\ds \tuple {t_1, s_1}\) | \(=\) | \(\ds \tuple {t_2, s_2}\) | Definition of $f$ | ||||||||||

\(\ds \leadsto \ \ \) | \(\ds \tuple {s_1, t_1}\) | \(=\) | \(\ds \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

- 1965: J.A. Green:
*Sets and Groups*... (previous) ... (next): Chapter $3$. Mappings: Exercise $9 \ \text {(i)}$ - 2000: James R. Munkres:
*Topology*(2nd ed.) ... (previous) ... (next): $1$: Set Theory and Logic: $\S 5$: Cartesian Products: Exercise $1$