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

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$

• Isomorphic as what? $\mathbb{Z}\times \mathbb{Z}$ is a group, the other not. – Dietrich Burde Mar 22 '18 at 15:03
• @DietrichBurde Isomorphic as sets. This exercise is from an 'Introduction to the Basics of the Set Theory' textbook for undergraduate freshmen students (it can be read after finishing High School, I believe). I am sorry, but I don't know yet what a group is, and the textbook also does not mention it. – fragileradius Mar 22 '18 at 15:12
• @fragileradius. The correct term for sets without structure is equinumerous. – William Elliot Mar 22 '18 at 19:22
• @fragileradius. For the structure you are considering, be clear by stating order isomorphic. – William Elliot Mar 22 '18 at 19:26
• What does a dot over a letter mean? @fragileradius Your proof is good if the first coordinate is the major index, ie dictionary order. – William Elliot Mar 22 '18 at 19:32

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?

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

• We could also consider the equivalence relation $\sim$ on either set, where $P\sim Q$ iff the set of $R$ that are $<_L$-between $P$ and $Q$ is finite, And show that an order-isomorphism must map $\sim$-equivalence classes of $\Bbb Z\times \Bbb N$ onto $\sim$-equivalence classes of $\Bbb Z\times \Bbb Z.$ But equivalence classes, in the former, have least members, while equivalence classes in the latter do not. – DanielWainfleet Mar 25 '18 at 6:52