Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 2 down vote accepted


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

share|cite|improve this answer
This function doesn't look surjective on N, does it matter? – NBP Feb 16 '13 at 20:15
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
@Cameron: Your comment is no longer true. :-) – Asaf Karagila Feb 16 '13 at 20:20
Ah! I see the edit now. Irrelevant comment deleted. – Cameron Buie Feb 16 '13 at 20:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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