3

I am trying to find out if it is possible to create an invertible function from $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$?

Can you help me? Where should I start? Is it related with the Cantor pairing function?

Xoque55
  • 4,384
user290335
  • 930

3 Answers3

3

The following function, used to produce a total order on $\mathbf N^*$ different from the usual order, is a bijection: \begin{align*} \mathbf N\times\mathbf N&\longrightarrow\mathbf N^*\\ (n,p)&\longmapsto 2^n(2p+1) \end{align*} Hence the function $$f(n,p)= 2^n(2p+1)-1$$ satisfies the requirements.

Bernard
  • 175,478
  • I saw that example on the internet, but I do not understand how to prove that this function has an inverse function. So I did : f(x,y)=59 so f(x,y)=2^x(2x+1)-1=59 it becomes f(x,y)=2^x(2x+1)+60. Now if we factorize 60 it becomes : f(x,y)=2^x(2x+1)+25^2,after that I don't know how to proceed can anyone help? thanks – user290335 Dec 12 '15 at 00:21
  • Can you help me on the comment above? Thanks – user290335 Dec 14 '15 at 14:30
2

The Cantor pairing function is exactly an example of an invertible function $\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$, so you need to just show that it is invertible. The wikipedia page on the Cantor Pairing function provides such an inverse, but it's probably a good exercise to see if you can find it yourself first.

(That being said, there are many invertible functions from $\mathbb{N}\times \mathbb{N}$ to $\mathbb{N}$.)

Hayden
  • 16,737
0

think about the following let $f$ map $(0,0) \to 0, (0,1)\to 1, (1,0) \to 2, (2,0) \to 3, (1,1) \to 4$ etc. Continue following these diagonal-like paths until the entire $\mathbb{N}^2$ is covered. $f$ is a bijection...

gt6989b
  • 54,422