Construct a bijection from $\Bbb N$ to $\Bbb N \times [3]$ ??

Question

Can anyone help with this question? I’m having a lot of trouble understanding how to do this problem. Any help is appreciated!

Answer 1

Just divide the natural numbers by their residue modulo $3$, i.e. define the map $f \colon \mathbb{N} \rightarrow \mathbb{N} \times \{0,1,2 \}$ as follows \begin{equation} f(n)= \begin{cases} (n/3,0) \quad \text{if} \ 3|n \\ (\frac{n-1}{3},1) \quad \text{if} \ n=1 \ \text{mod} \ 3 \\ (\frac{n-2}{3},2) \quad \text{if} \ n=2 \ \text{mod} \ 3. \end{cases} \end{equation}

The basic idea is that since the cardinality of $\mathbb{N}$ is infinite then $3 \cdot |\mathbb{N}|= |\mathbb{N}|$. More concretely the set $\{ 3n : n \in \mathbb{N} \}$ is in bijection with $\mathbb{N}$ just by the map $n \mapsto 3n$, thus adding $0,1, 2$, i.e. shifting the multiples of $3$ by the possible residues of the division by $3$ we get all the natural numbers.