# Bijection from Cartesian Product of Initial Segments to Initial Segment

Jump to navigation
Jump to search

## Theorem

Let $\N_k$ be used to denote the set of the first $k$ non-zero natural numbers:

- $\N_k := \set {1, 2, \ldots, k}$

Then a bijection can be established between $\N_k \times \N_l$ and $\N_{k l}$, where $\N_k \times \N_l$ denotes the Cartesian product of $\N_k$ and $\N_l$.

## Proof

Let $\phi: \N_k \times \N_l \to \N_{k l}$ be defined as:

- $\forall \tuple {m, n} \in \N_k \times \N_l: \map \phi {m, n} = \paren {m - 1} \times l + n$

First it is confirmed that the codomain of $\phi$ is indeed $\N_{k l}$.

## Sources

- 1971: Allan Clark:
*Elements of Abstract Algebra*... (previous) ... (next): Chapter $1$: Mappings: $\S 13 \alpha$