# A question about isomorphism between orders

Is there an isomorphism between the naturals with the regular order $\le$ and the set $\mathbb{N}\times \mathbb{N}$ with the order $R$ defined to be $\langle k_1,r_1\rangle\mathrel R\langle k_2,r_2\rangle$ iff $2^{k_1} (2r_1+1)\le 2^{k_2} (2r_2+1)$?

I may not be using the correct terms in English as I was unable to find out what they are. When I say isomorphism between relations I mean that there's a bijective function from say $A$ to $B$ such that if there's some relation order $L$ defined on $B$ and some relation order R defined on A, if $x\mathrel Ry$ then $f(x)\mathrel Lf(y)$.

What are general guidelines to know if such a function exists?

Thanks a million!

-

The order on the pairs should actually hint you what the function should be. In this case, think about the function which maps the pair $(n,k)$ to $2^n(2k+1)-1$.
(Often one picks a bijection of $\mathbb{N\times N}$ with $\mathbb N$ and only then defines the order of the product.)
Indeed it's not surjective. But note that given any infinite subset $A$ of $\Bbb N$, the restriction of $\leq$ to $A$ yields an order isomorphic to $\Bbb N$. In this case you probably need to take $2^n(2k+1)-1$. – Asaf Karagila Feb 16 '13 at 20:17