# A bijection from N^2 to N that is not Cantor's pairing function [duplicate]

Is there any other bijection from $$\mathbb{N}^{2}$$ to $$\mathbb{N}$$ other than the pairing function? My search so far has come up empty.

• There are $2^\omega=\mathfrak c$ such bijections. Are you asking for explicit examples different from the Cantor pairing function $\pi$? One easy one is given by $\pi'(m,n)=\pi(n,m)$. – Brian M. Scott Mar 25 at 16:32
• One common trick is to use the fundamental theorem of arithmetic. The map $(i,j) \mapsto 2^i 3^j$ is an injection $\mathbb{N}^2 \rightarrow \mathbb{N}$; then map the $i$th element of this image to the $i$th element of $\mathbb{N}$ to get a bijection. – Jair Taylor Mar 25 at 16:33
• I don't know what this pairing function that we have to avoid is, but try composing it with any nontrivial permutation of $\Bbb{N}$ on the left, or $\Bbb{N}^2$ on the right, and you can guarantee a bijection different from the one you started with. – user759562 Mar 25 at 16:33
• I assumed the OP just wants, informally, a different approach to this problem. – Jair Taylor Mar 25 at 16:35
• @user759562: Presumably the Cantor pairing function. – Brian M. Scott Mar 25 at 16:38

Yes. Here's an example. Let$$S=\{2^a3^b\mid a,b\in\mathbb N\}=\{6,12,18,\ldots\}.$$There is a bijection $$\beta\colon\mathbb N\longrightarrow S$$: just define $$\beta(n)$$ as the $$n$$th element of $$S$$. And there is a bijection $$\varphi\colon\mathbb N^2\longrightarrow S$$: $$\varphi(a,b)=2^a3^b$$. Now take $$\varphi^{-1}\circ\beta$$.
• @AsafKaragila I personally really like this one! It combines two basic ideas: recursive constructions (when we unfold $b$, that's what it is) and coding via prime factorization. Additionally it takes basically no effort to verify that it works (unlike Cantor's). It's also a good exercise to show that this is computable without using Church's thesis (whereas for the Cantor pairing function this follows immediately from the computability of basic algebraic operations). – Noah Schweber Mar 25 at 17:06
• @Nikolaj-K I've changed the name of my map from $b$ to $\beta$. – José Carlos Santos May 16 at 13:41