0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Brian M. Scott Mar 25 at 16:32
  • $\begingroup$ 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. $\endgroup$ – Jair Taylor Mar 25 at 16:33
  • $\begingroup$ 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. $\endgroup$ – user759562 Mar 25 at 16:33
  • $\begingroup$ I assumed the OP just wants, informally, a different approach to this problem. $\endgroup$ – Jair Taylor Mar 25 at 16:35
  • $\begingroup$ @user759562: Presumably the Cantor pairing function. $\endgroup$ – Brian M. Scott Mar 25 at 16:38
2
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ That is a terrible suggestion. $\endgroup$ – Asaf Karagila Mar 25 at 16:36
  • $\begingroup$ I've seen this before. I still hate it $\endgroup$ – Don Thousand Mar 25 at 16:36
  • $\begingroup$ @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). $\endgroup$ – Noah Schweber Mar 25 at 17:06
  • $\begingroup$ @DonThousand See my previous comment. $\endgroup$ – Noah Schweber Mar 25 at 17:07
  • 1
    $\begingroup$ @Nikolaj-K I've changed the name of my map from $b$ to $\beta$. $\endgroup$ – José Carlos Santos May 16 at 13:41

Not the answer you're looking for? Browse other questions tagged or ask your own question.