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$
Best Answer
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?