# Is $(\mathbb{N\times N\times N}, \leq_{lex})$ isomorphic to $(\mathbb{N\times N}, \leq_{lex})$?

Is $(\mathbb{N\times N\times N}, \leq_{lex})$ isomorphic to $(\mathbb{N \times N}, \leq_{lex})$? Prove it.

$\leq_{lex}$ - lexicographical order

I think that $(\mathbb{N\times N\times N}, \leq_{\text{lex}})$ is isomorphic to $(\mathbb{N\times N}, \leq_{\text{lex}})$. I defined function $f(l,m,n)=l, \frac{(m+n)(m+n+1)}{2}+m$.

I want to show that if $l_1, m_1, n_1 \leq l_2, m_2, n_2$, then $f(l_1, m_1, n_1) \leq f(l_2, m_2, n_2)$, and in this case that is always true (should I show it somehow or is it enough just to state it?).

Can you tell me if my reasoning is correct? If not, where am I making the mistake?

• Use $\times$ for $\times$. – Shaun Aug 28 '17 at 12:37
• I think you need to show it, because nobody's going to believe it without proof. Do you also believe that $(\mathbb N\times\mathbb N,\le_{lex})$ is isomorphic to $(\mathbb N,\le)$? – bof Aug 28 '17 at 12:43
• $(0,0,1) \le (0,1,0)$ but $f(0,1,0) = (0,1) \le (0,2) = f(0,0,1)$ – Kenny Lau Aug 28 '17 at 12:45
• They aren't isomorphic as $\omega^3$ and $\omega^2$ aren't isomorphic. I'm figuring out a better proof though. – Kenny Lau Aug 28 '17 at 12:55
• Can you show that the set of all non-successor elements of $\mathbb N\times\mathbb N\times\mathbb N$ is isomorphic to $\mathbb N\times\mathbb N,$ while the set of all non-successor elements of $\mathbb N\times\mathbb N$ is isomorphic to $\mathbb N?$ – bof Aug 28 '17 at 13:03

$\varphi: (m,n) \mapsto \dfrac{(m+n)(m+n+1)}{2}$ is kind of the standard bijection between $\Bbb N \times \Bbb N$ and $\Bbb N$, so your proposed function is indeed a bijection.
However, the homomorphism property is not satisfied, as $(0,0,1) \le (0,1,0)$ but $f(0,0,1) = (0,2) \not\le (0,1) = f(0,1,0)$.