Prove that $\mathbb{Z}\times\mathbb{N}$ is not isomorphic to $\mathbb{Z}\times\mathbb{Z}$ (both strictly ordered): is my proof correct?

Question

I must prove that $\mathbb{Z}\times\mathbb{N}$ and $\mathbb{Z}\times\mathbb{Z}$ (both strictly ordered, the second coordinate is the 'main' one) are not isomorphic.

I wrote a proof, but I don't know if it's rigourous enough or even correct, and I would be grateful for pointing out mistakes and guiding to how to do it better.

The proof is:

$\triangleleft$ In $\mathbb{Z}\times\mathbb{Z}$, for every ordered pair $\langle x, y\rangle $ (including the pairs of type $\langle x, n\rangle $) there exists a subset of ordered pairs that have the same first coordinate and lesser second coordinate: $\{\langle x, y-1\rangle , \langle x, y-2\rangle , \langle x, y-3\rangle , \dots\}$. The cardinality of this set is $\aleph_0$.

In $\mathbb{Z}\times\mathbb{N}$, for every ordered pair of type $\langle x, n\rangle $ there exists a subset of ordered pairs that have the same first coordinate and lesser second coordinate: $\{\langle x,n-1\rangle ,\langle x, n-2\rangle ,\dots\langle x, 1\rangle \}$. The cardinality of this set is $n-1$, where $n$ is a natural (and, therefore, finite) number.

Since isomorphism preserves the order, if sets $A$ and $B$ are isomorphic, then their subsets $\dot A \subset A$ and $\dot B \subset B$ constructed by the same rule should also be isomorphic. However, in our construction even cardinalities don't match: one is infinite, another one is not. The Cartesian products in question are not isomorphic, therefore. $\triangleright$

I did search through the stackexchange and clicked the proposed links while writing this question, but, unfortunately, found nothing.

Thank you a lot!

---

Here's a new proof (note: in the proof above, $0$ was not considered a natural number; in the proof below, it is):

$\triangleleft$ The ordering: the major index is the second coordinate.

Assume the contrary: $\mathbb{Z}\times\mathbb{N}$ is isomorphic to $\mathbb{Z}\times\mathbb{Z}$. Then, $\langle 0, 0\rangle $ from $\mathbb{Z}\times\mathbb{N}$ is mapped to some $\langle a, b\rangle $ in $\mathbb{Z}\times\mathbb{Z}$.

With both $\langle 0, 0\rangle $ and $\langle a, b\rangle $ there is associated a subset of either $\mathbb{Z}\times\mathbb{N}$ or $\mathbb{Z}\times\mathbb{Z}$ comprised of lesser elements:

$\{\dots, \langle -z, 0\rangle , \dots, \langle -2, 0\rangle , \langle -1, 0\rangle \}$ $\subset$ $\mathbb{Z}\times\mathbb{N}$ for $\langle 0, 0\rangle $,

$\{\dots, \langle x, b-1\rangle , \dots, \langle a-2, b\rangle , \langle a-1, b\rangle \}$ $\subset$ $\mathbb{Z}\times\mathbb{Z}$ for $\langle a, b\rangle $.

Since isomorphism preserves the order,

$\langle a-1, b\rangle \mapsto \langle -1, 0\rangle , $

$\langle a-2, b\rangle \mapsto \langle -2, 0\rangle $ and so on.

Now, where would we map $\langle x, b-1\rangle $? We would have to map it to some element given by formula $\langle -z, 0\rangle $ (it's the only available option). However, between $\langle -z, 0\rangle $ and, say, $\langle -2, 0\rangle $ there is a finite amount of pairs, and between $\langle x, b-1\rangle $ and $\langle a-2, b\rangle $ there is an infinite one. But for isomorphism to exist, these amounts must be equal. Contradiction. $\triangleright$

Answer 1

All orders are in dictionary order.
(a,b) <= (x,y) when a < x or (a = x and b <= y)
N is set of positive integers.

NxZ not order isomorphic to ZxZ. Proof.
Every subset of the lower set of (1,1) in NxZ has a maximum.
The subset {a-1}xZ of the lower set of (a,b) in ZxZ
does not have a maximum.

Is ZxN order isomorphic to ZxZ?

Answer 2

In your proof you seem to have overlooked the fact that in the lexicographic order $<_L$ on either $\Bbb Z\times \Bbb N$ or on $\Bbb Z\times \Bbb N,$ there are infinitely many members between $(a-1,b)$ and $(a,b).$ The order being defined by $(x,y)<_L(x',y') \iff (x<x'\lor (x=x'\land y<y')). $

Suppose $f:\Bbb Z\times \Bbb N\to \Bbb Z\times \Bbb Z$ were an order-isomorphism and $f(1,1)=(a,b).$ Then for $n\in \Bbb N$ we must have $f(1,n)=(a,b+n-1).$

For brevity of notation let $A=\{1\}\times \Bbb N$ and let $B=\{a\}\times \{b+n-1:n\in \Bbb N\}.$ Then $f$ must map the set $C=\{P\in \Bbb Z\times \Bbb N: \forall Q\in A\;( Q<_LP)\}$ onto the set $D=\{P'\in \Bbb Z\times \Bbb Z: \forall Q'\in B: (Q'<_LP')\}.$

But $C$ has a $<_L$-least member $(2,1)$ and $D$ has no $<_L$-least member because if $(p'_1,p'_2)=P'\in D$ then $p_1'\geq 2$ so $P'>_L(p'_1,p'_2-1)\in D.$