I'm doing this exercise:
Prove that ordered sets $\langle \mathbb{N} \times \mathbb{Q}, \le_{lex} \rangle$ and $\langle \mathbb{Q} \times \mathbb{N}, \le_{lex} \rangle$ are not isomorphic ($\le_{lex}$ means lexigraphic order).

I don't know how to start (I know that to prove that ordered sets are isomorphic I would make a monotonic bijection, but how to prove they aren't isomorphic?).


Recall that the lexicographic order on $A\times B$ is essentially to take $A$ and replace each point with a copy of $B$.

So only in one of these lexicographic orders every element has an immediate successor. And having an immediate successor is preserved under isomorphisms.

(Generally, to show two orders are not isomorphic you need to show either there are no bijections between the sets (e.g. $\Bbb Q$ and $\Bbb R$ are not isomorphic because there is no bijection between them) or that there are properties true for one ordered and set and not for the other that are preserved under isomorphisms, like having minimum or being a linear order, or having immediate successors.)

  • 2
    $\begingroup$ I'd say cardinality is a property of ordered sets preserved under isomorphism . . . :P $\endgroup$ – Noah Schweber Jan 18 '16 at 20:04
  • 1
    $\begingroup$ Yes, and I'd say that two sets are not isomorphic if they are not of the same cardinality. $\endgroup$ – Asaf Karagila Jan 18 '16 at 20:21
  • $\begingroup$ I just meant that the first option is a special case of the second. $\endgroup$ – Noah Schweber Jan 18 '16 at 20:28
  • 1
    $\begingroup$ Ah. Yeah, well. I find it sometimes that specifying a particular "odd case" can be helpful. The lack of a bijection is very different from the case of having a maximum only in one of the orders. $\endgroup$ – Asaf Karagila Jan 18 '16 at 20:29

To prove two structures aren't isomorphic, one good approach is to find a property that one structure satisfies that the other doesn't; and then show that property is preserved by isomorphisms.

For the specific example: have you tried drawing the two linear orders in question? What's a property $\mathbb{Q}$ has, that $\mathbb{Z}$ doesn't?


Suppose there is an isomorphism $\phi:\mathbb{Q} \times \mathbb{N} \to \mathbb{N} \times \mathbb{Q} $.

Let $(n,q) = \phi((0,0))$ and let $(a,b) = \phi^{-1}((n,q-1))$. Note that we must have $a<0$ since $(n,q-1) < (n,q)$.

Note that we have $(a,b) < (a,b+1) < (0,0)$.

Note that there are no elements in $\mathbb{N} \times \mathbb{Q}$ between $(n,q-1)$ and $(n,q)$ and since we must have $(n,q-1) = \phi(a,b) < \phi(a,b+1) < \phi(0,0) = (n,q)$ we have a contradiction.

  • $\begingroup$ The notation for the ordered pairs seems reversed. For example, $\phi(0,0)$ is in $\mathbb N\times\mathbb Q$, so its first component should be in $\mathbb N$ and the second in $\mathbb Q$. Your notation $(q,n)$ suggests (though it doesn't strictly imply) the opposite; later, you use that there's nothing between $(q,n-1)$ and $(q,n)$, which does imply that you meant for $n$ to be in $\mathbb N$, not $\mathbb Q$. $\endgroup$ – Andreas Blass Jan 18 '16 at 20:50
  • $\begingroup$ @AndreasBlass: Thanks, I reversed the domain & range of $\phi$ midway and never cleaned up. I have fixed the notation, hopefully without introducing typos. as I am wont to do. $\endgroup$ – copper.hat Jan 18 '16 at 20: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.