Friday, January 15, 2016

elementary set theory - Ordered sets $langle mathbb{N} times mathbb{Q}, le_{lex} rangle$ and $langle mathbb{Q} times mathbb{N}, le_{lex} rangle$ not isomorphic



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?).


Answer



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


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...