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
    is 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
  • 4
    You show it yourself in the title of the question: The first set doesn't have a maximal element, the second does.2012-08-26
  • 0
    I'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
  • 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
    So 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
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).$