Bijection from Cartesian Product of Initial Segments to Initial Segment

From ProofWiki
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