Here is a definition from Munkres' book "Topology":

For any two sets $A$ and $B$ with order relations $<_A$ and $<_B$, respectively, we say that $A$ and $B$ have the same order type if there exists a bijective function $f:A \to B$ such that $$ a_1 <_A a_2 \implies f(a_1) <_B f(a_2)$$

My intuitive understanding of this definition is that a "larger" element in one set can stay "larger" in another set under some bijective map $f$, but then I feel that I am not really understanding what it means by a "type" of the order as I am having hard time understanding the following excerpt :

Let $Z_{+}$ denote the set of positive integers. Then, it can be easily checked that: $$Z_+ \tag 1 $$ $$\{1,...n\} \times Z_+ \tag 2$$ $$Z_+ \times Z_+ \tag 3$$ $$Z_+ \times (Z_+ \times Z_+) \tag 4$$

How do I check for instance that (1) and (2) have different order types, and what is the idea for different types?

  • $\begingroup$ What ordering do you use for $\{1,2,\dots,n\}\times Z_+$? $\endgroup$ – TomGrubb May 20 '15 at 0:31
  • $\begingroup$ I think Dictionary ordering $\endgroup$ – user74261 May 20 '15 at 0:34

Lets say we give $\{1,2,\dots,n\}\times Z_+$ the ordering $$ (a,b)<(c,d) $$ if $a<c$ or if $a=c$ and $b<d$. Also we must assume $n>1$.

Assume we had an order preserving bijection $\phi$ from $Z_+$ to $\{1,2,\dots,n\}\times Z_+$. As $(1,1)$ is the minimal element of $\{1,2,\dots,n\}\times Z_+$, it follows that $\phi(1)=(1,1)$. Now if $2$ did not get sent to $(1,2)$, then since $\phi$ is bijective and since $\phi(1)=(1,1)$, then $\phi(a)=(1,2)$ for some $a>2$. But now $\phi(2)>\phi(a)$, so indeed it must be that $\phi(2)=(1,2)$ for $\phi$ to be order preserving. Continuing in this fashion, we can see that the only way for $\phi$ to be a bijection and be order preserving is to have $\phi(a)=(1,a)$ for all $a$ in $Z_+$. This is clearly not a bijection (as $n>1$), so such a $\phi$ cannot exist. Thus the sets have different order types.


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.