I want to show that $$ \{1,2\}\times Z_+\ \text{and} \ Z_+ \times\{1,2\}\ \text{have different order type}$$

If we define $$f(i,j)=(j,i)\ \text{for}\ i\ \text{in }\{1,2\}\ \text{and} \ j\ \text{in}\ Z_+$$

It seems like that this is bijective map between two sets.

However, to show that they are not order isomorphic, how shall I start to show that bijection does not preserve ordering?

It seems like that the way I defined the bijection is not the only way.

I am wondering if there exists any bijection between two sets and that bijection does not preserve order, can I conclude that they have different order type?

  • 1
    $\begingroup$ Hint: Consider elements with no immediate predescessor. $\endgroup$ – Tobias Kildetoft Feb 27 '16 at 19:49
  • $\begingroup$ (2,1) on the left has no immediate predescessor? $\endgroup$ – jessie Feb 27 '16 at 19:55
  • $\begingroup$ Correct. Are there any such on the right? $\endgroup$ – Tobias Kildetoft Feb 27 '16 at 19:57
  • $\begingroup$ (1,1) in the left-hand order also has no immediate predecessor. $\endgroup$ – DanielWainfleet Feb 27 '16 at 19:59
  • $\begingroup$ None exists on the right, yes I see. it seems like an isomorphism between two sets in a sense that they have two different structures $\endgroup$ – jessie Feb 27 '16 at 19:59

For simplicity I'm going to use $2$ itself to denote the two-element set $\{0,1\}$ (not a total fiction: this is true in ZF. But you can just take it as abuse of notation).

$2\times \Bbb Z$ is $\Bbb Z + \Bbb Z$, two copies of $\Bbb Z$ laid end to end: $$ 2\times \Bbb Z = \left(\cdots + -1_{0} + 0_{0} + 1_{0} + \cdots\right) \,+\, \left(\cdots + -1_{1} + 0_{1} + 1_{1} + \cdots \,+\, \cdots\right)$ $$

On the other hand, $\Bbb Z \times 2$ is $\Bbb Z$-many copies of $\{0,1\}$, which is $$ \Bbb Z \times 2 = \cdots + \left(0_{-1} + 1_{-1}\right) + \left(0_{0} + 1_{0}\right) + \left(0_{1} + 1_{1}\right) + \cdots. $$ It's easy to find an order-theoretic property that distinguishes between these sets:

$2\times \Bbb Z$ has the property that there are strictly increasing sequences of its elements that are bounded above. An order isomorphism preserves strict increasing sequences and maps upper bounds of their elements to upper bounds of what it maps the elements to. So this same property has to be true of the target ordering. However, in $\Bbb Z \times 2$, no strictly increasing sequence has an upper bound.


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.