a finite algorithm mapping from $\omega \times \omega$ to $\omega$ possible?

Question

We know that $\omega \times \omega$ is isomorphic to $\omega$, but I am not sure if there would exist a finite algorithm mapping from $\omega \times \omega$ to $\omega$. An algorithm would of course be recursive enumerable, if it exists and I am not sure if when given an input that is any set in $\omega \times \omega$ there would be an algorithm that converts it to a unique set in $\omega$.

The algorithm mapping has to be bijective.

By $\omega \times \omega$, I mean cartesian product of $\omega$ with $\omega$. As in set theoretic use. (so $\times$ is not ring/field multiplication!)

Answer 1

The function $f:\mathbb N \times \mathbb N \to \mathbb N-\{0\}$ given by $f(m,n)=2^m\cdot (2n+1)$ (I take $0\in \mathbb N$ by convention) is bijective, so in particular gives an algorithm for a bijective mapping as (I think) you want. Does this answer your question?

Answer 2

Think of $\omega$ as the set $\{0,1,2,3,\dots\}$.

Map $(x,y)$ to $2^x (2y+1)-1$.

Answer 3

The Cantor pairing function is primitive recursive, the function $f\colon\Bbb{N\times N\to N}$ is defined as follows:

$$f(m,n)=\frac{(m+n)(m+n+1)}2+m=\sum_{i=1}^{m+n} i + m$$