6
$\begingroup$

That is, how can I prove there isn't a bijection $f$ from one set to the other such that $f(x) < f(y)$ iff $x < y$?

  • 0
    Yes that's correct. $\omega$ is the smallest/first of the infinite ordinals, greater than all the finite ordinals $0, 1, 2, \dots$.2012-09-01

4 Answers 4

12

Suppose that $f:\{1,2,3,\dots\}\to\{1,2,3,\dots,\omega\}$ is an order-preserving bijection. There must be some $n\in\{1,2,3,\dots,\}$ such that $f(n)=\omega$. What can $f(n+1)$ be?

  • 0
    @Bakhtiar: I wouldn’t say it quite that way, but I suspect that you have the right idea. If $f(n)=\omega$, then since n, we must have \omega; but no member of $\{1,2,3,\dots,\omega\}$ is greater than $\omega$, so no such function can exist.2012-08-26
8

Note that an order isomorphism preserves maximum properties, namely if $a$ is a maximum then $f(a)$ is a maximum of the image.

In particular a linearly ordered set with a maximum is never isomorphic to one without.

1

A. Order isomorphism is a bijection. So if A and B have different cardinality, they cannot be order isomorphic, i.e., they cannot have the same order type. https://en.wikipedia.org/wiki/Order_type (The converse is not true: $\mathbb N$ and $\mathbb Z$ are both countable but not order isomorphic, as only $\mathbb N$ has a minimum. Similarly, $\omega$ and $\omega+1$ are not order isomorphic.)

B. If A (resp., B) is order isomorphic to A' (resp., B'), and A' and B' are not order isomorphic, then A and B are not order isomorphic, as order isomorphism is an equivalence relation (proof: the above link).

C. If two ordinals are order isomorphic, then they are the same. (Proof: the above link.)

D. If A and B are order isomorphic to different ordinals, they cannot be order isomorphic to each other (Proof: B&C.)

E. Order isomorphism preserves some other properties too. So if some of those properties is possessed by A but not B, then they are not order isomorphic. Examples:
- having N maxima (if A is ordered, then N is 0 or 1, but if you are talking about partially ordered sets or preordered sets, then other cardinalities of N are possible too).
- having N minima
- having a countable set S that is order-dense in some way (e.g., for every $a,b\in A$, $a there exists $s\in S$ with $a\le s\le b$). (Or the same property with some other cardinality instead of "countable".)
- being well ordered - being complete - any other property depending solely on the order.

F. But sometimes you should just assume an order isomorphism $f:A\rightarrow B$ and somehow derive a contradiction.

Chapter 4 of this is about order types: http://www.math.wustl.edu/~freiwald/ch8.pdf

  • 0
    You have written in your point (E.) that order isomorphism preservers some other properties. How can we prove these properties ? I mean where can I find such theorems or lemmas about those properties ? Can you suggest a reference book ?2017-11-06
0

Let $<$ be a well-order on a set $X.$ For $x\in X$ define pred$(x)=\{y:y ("Pred" is for "predecessors".)

There is no order-isomorphism from pred$(x)$ onto $X.$

Proof: By contradiction. Suppose $f:$pred$(x)\to X$ is an order-isomorphism. Then the set $S= \{ z\in \text {pred}(x): f(z)\ne z\}$ is not empty (because $x\not \in $pred$(x)$ so $f^{-1}(x)\in S$ ).

Let $y=\min S.$ We cannot have $f(y)=w, else, by def'n of $y$ we have $f(w)=w,$ but then $f$ does not preserve order (because $y>w$ but $f(y)=f(w)$.)

So $f(y)>y.$ But there exists $u\in $pred$(x)$ with $f(u)=y,$ while $v, and also $f(y)\ne y.$ So $u>y.$

But now $u>y$ and $f(u)=y so $f$ does not preserve order.

In your Q, let $X=\{\omega\}\cup \{1,2,3,...\}.$ Then $\{1,2,3,...\} =$pred$(\omega).$