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 \}$
-
0is the first set infinite and the second finite? Its not really clear what you're asking. – 2012-08-26
-
0@dustanalysis: Both infinite with equal cardinality, but with different order-types. Order type of the first set being $\omega$ and of the other, $\omega + 1$. – 2012-08-26
-
0@dustanalysis: I was asking to understand in what sense are different ordinals different. The two sets I put have the same size but different in the sense that different ordinals correspond with each. – 2012-08-26
-
4You show it yourself in the title of the question: The first set doesn't have a maximal element, the second does. – 2012-08-26
-
0I'd like to see a bijection from the first set to the second. Can you provide an example? Specifically, if $f(n)=\omega$, then what is $n$? – 2012-08-26
-
0@TestSubject528491: You can say $n=1$ (or any other number from the set). Pair the numbers from the first set with those in the second like this: match $1$ with $\omega$, $2$ with $1$, ..., $n+1$ with $n$ and so on and you get your bijection. – 2012-08-26
-
0@BakhtiarKasi: good one. I'm assuming your bijection does not preserve order? If it does, it would disprove your conjecture. – 2012-09-01
-
0@dustanalysis : No, I would not take the notation to mean the second set is finite. I think $\omega$ is intended to be the smallest infinite ordinal, and it's preceded by all finite ordinals. – 2012-09-01
-
0@TestSubject528491: No it's not an order-isomporphism because $f(1)=\omega$ doesn't precede $f(2)=1$. It's proven that there can't in fact be any order preserving bijection. – 2012-09-01
-
0@BakhtiarKasi I guess I'm just not familiar with the ordering rules of $\omega$. It's an infinite ordinal number that is greater than every finite ordinal number? – 2012-09-01
-
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?
-
0So because $f(n+1)$ doesn't exist, there can't be any such bijection? – 2012-08-26
-
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).$