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$?
How do I show there isn't an order isomorphism b/w the two sets $\{1, 2, 3,...\}$ and $\{1, 2, 3, ..., \omega \}$
-
0Yes 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
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
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.
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
-
0You 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
Let $<$ be a well-order on a set $X.$ For $x\in X$ define pred$(x)=\{y:y
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
So $f(y)>y.$ But there exists $u\in $pred$(x)$ with $f(u)=y,$ while $v
But now $u>y$ and $f(u)=y
In your Q, let $X=\{\omega\}\cup \{1,2,3,...\}.$ Then $\{1,2,3,...\} =$pred$(\omega).$