How to write down a bijection from $\mathbb N$ onto $\mathbb N\times\mathbb N\times\mathbb N$?

Question

I'm looking for a bijection from $\mathbb N$ to $\mathbb N\times\mathbb N\times\mathbb N$.

• I know it exists
• I know an informal way to define one, ordering the triplets of natural numbers in a 3D array an counting them diagonally as they do here with 2D array.
• And I know a bijection from $\mathbb N\times\mathbb N\times\mathbb N$ to $\mathbb N$ from this answer which uses factorization

But how to write it explicitly?

Thank you very much.

Answer 1

Use Cantor's pairing function $\langle \cdot, \cdot \rangle: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ twice: $(a,b,c) \mapsto \langle \langle a,b \rangle, c \rangle$. Cantor's pairing function has an inverse which is easily-stated if a bit fiddly (see the proof of bijectivity on the linked Wikipedia page).

Answer 2

Hint: Can you find an explicit bijection from $\mathbb{N}\times \mathbb{N}$ to $\mathbb{N}$?

Answer 3

Since you ask for any such bijection, here is one random idea. Note that $\mathbb{N}$ excludes $0$ in following text.

Going from $\mathbb{N} \times \mathbb{N} \times \mathbb{N}$ can be done easily by realizing that each natural number can be expressed uniquely as a $$n=2^{a_0-1}(2a_1-1).$$ We can go even further and expand $2a_1$ and get unique form expressed as $$n=2^{a_0-1}(2^{a_1}(2a_2-1)-1).$$ Actually, this way we can get bijection from $\mathbb{N}^n$ to $\mathbb{N}$.

Now to go reverse, let's just denote $v_2(n)$ to be the exponent of prime $2$ in prime factorization of $n$. Then you can go backwards to get individual $a_i$'s:

\begin{align} a_0 &= v_2(n)+1 \\ a_1 &= v_2\left(\frac{n}{2^{a_0-1}}+1\right) \\ a_2 &= \frac{\frac{\frac{n}{2^{a_0-1}}+1}{2^{a_1}}+1}{2}\\ \end{align}

Then just sending $n$ to $(a_0, a_1, a_2)$ gives a bijection (because of uniqueness of such expression of each natural number).

First few numbers then map:

\begin{align} 1 = 2^{\color{red}{1}-1}(2^\color{red}{1}(2\cdot \color{red}{1}-1)-1) \to (\color{red}{1},\color{red}{1},\color{red}{1}) \\ 2 = 2^{\color{red}{2}-1}(2^\color{red}{1}(2\cdot \color{red}{1}-1)-1) \to (\color{red}{2},\color{red}{1},\color{red}{1}) \\ 3 = 2^{\color{red}{1}-1}(2^\color{red}{2}(2\cdot \color{red}{1}-1)-1) \to (\color{red}{1},\color{red}{2},\color{red}{1}) \\ 4 = 2^{\color{red}{3}-1}(2^\color{red}{1}(2\cdot \color{red}{1}-1)-1) \to (\color{red}{3},\color{red}{1},\color{red}{1}) \\ 5 = 2^{\color{red}{1}-1}(2^\color{red}{1}(2\cdot \color{red}{2}-1)-1) \to (\color{red}{1},\color{red}{1},\color{red}{2}) \\ \end{align}