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$

  • $\begingroup$ Isomorphic as what? $\mathbb{Z}\times \mathbb{Z}$ is a group, the other not. $\endgroup$ – Dietrich Burde Mar 22 '18 at 15:03
  • $\begingroup$ @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. $\endgroup$ – fragileradius Mar 22 '18 at 15:12
  • $\begingroup$ @fragileradius. The correct term for sets without structure is equinumerous. $\endgroup$ – William Elliot Mar 22 '18 at 19:22
  • 1
    $\begingroup$ @fragileradius. For the structure you are considering, be clear by stating order isomorphic. $\endgroup$ – William Elliot Mar 22 '18 at 19:26
  • $\begingroup$ What does a dot over a letter mean? @fragileradius Your proof is good if the first coordinate is the major index, ie dictionary order. $\endgroup$ – 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.$

  • $\begingroup$ 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. $\endgroup$ – DanielWainfleet Mar 25 '18 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.