Non-isomorphisms of orders

Question

Task: Let A = $\{ (x, y) \in \mathbb{N} \times \mathbb{N} : x ⩾ y \}$ and B = $\{ (x, y) \in \mathbb{N} \times \mathbb{N} : x ⩽ y\}$ . Consider the restriction of the lexicographic order $\mathbb{N} \times_{lex} \mathbb{N}$ on these sets: a pair $(x_{1} , y_{1})$ is less than a pair $(x_{2} , y_{2} )$ if $x_{1} < x_{2}$ or $x_{1} = x_{2}$ and $y_{1} < y_{2}$ . Are these orders isomorphic on sets A and B?

My thinking: Usually, when proving an isomorphism, it is enough to give a bijection $f$, which works as follows: $(x_{1}, y_{1}) < (x_{2}, y_{2}) \Rightarrow f((x_{1}, y_{1})) < f((x_{2}, y_{2}))$. No matter how much I try to bring such a bijection, I come to the conclusion that when constructing it, the condition $(x_{1}, y_{1}) < (x_{2}, y_{2}) \Rightarrow f((x_{1}, y_{1})) < f((x_{2}, y_{2}))$ is violated. It turns out that it is necessary to prove that these orders are not isomorphic. It seems impossible to prove that such a bijection does not exist, since both sets A and B are infinite, therefore there can also be an infinite number of bijections, at least it seems to me an irrational approach to solving this task. (if this is incorrect, then point out my mistake to me).

Usually non-isomorphisms are proved as follows:

1. the minimum/maximum/smallest/largest elements from one order do not pass into the minimum/maximum/smallest/largest elements of another order
2. each segment of power $[x, y]$ does not pass into the segment $[f(x), f(y)]$ which has the same power
3. limit elements they do not pass into limit elements of a different order

I'm not quite able to figure out how to use this to prove non-isomorphism. Please give me a hint or guide me on the right path...

Answer 1

These are not isomorphic. Say $(x_1,y_1)$ is a predecessor of $(x_2,y_2)$ if $(x_1,y_1)\leqslant (x_2,y_2)$.

Every member of $A$ has only finitely many predecessors in $A$. Indeed the predecessors in $A$ of $(m,n)$ with $m\geqslant n$ are $(1,1)$, $(2,1)$, $(2,2)$, $(3,1)$, $(3,2)$, $(3,3)$, $\ldots$, $(n,1)$, $(n,2)$, $\ldots$, $(n,m)$.

Every member $(x,y)$ of $B$ with $x>1$ has infinitely many predecessors, because the predecessors include $(1,1)$, $(1,2)$, $(1,3)$, $\ldots$.

The property that every member of a poset has only finitely many predecessors is preserved under order isomoprhisms, so $A$ and $B$ cannot be order isomorphic.

These are actually well-ordered sets (linearly/totally ordered sets in which every non-empty subset has a minimum). The set $A$ is order isomorphic to $\omega$ (which is order isomorphic to $\mathbb{N}$, which, up to isomorphism, is the unique infinite well-ordered set such that every member has only finitely many predecessors). The set $B$ is isomorphic to $\omega^2$, because it is essentially $\omega$ many copies of $\omega$, in order. That is, each of the sets $$N_x=\{(x,y):y\geqslant x\}$$ is order isomorphic to $\omega$, and each member of $N_1$ is less than each member of $N_2$ is less than each member of $N_3$ $\ldots$.

Answer 2

They are not isomorphic. To prove it, consider in each of them the notion of (immediate) successor $$S(z):=\min\{t\mid z<t\},$$

• in the subset $A$, starting from the smallest element $(1,1)$, the sequence of consecutive successors exhausts the whole subset:$$(1,1)\xrightarrow S(2,1)\xrightarrow S(2,2)\xrightarrow S(3,1)\xrightarrow S(3,2)\xrightarrow S(3,3)\xrightarrow S\dots$$
• in $B$, it doesn't: $$(1,1)\xrightarrow S(1,2)\xrightarrow S(1,3)\xrightarrow S(1,4)\xrightarrow S\dots$$ This ends the proof.

Moreover, these two maps $S$ help to understand that $A,B$ are respectively order isomorphic to the ordinals $\omega$ and $\omega^2$ ($>\omega$). Since any two distinct ordinals are non-isomorphic, this explains more deeply why $A$ and $B$ are non-isomorphic.