3
$\begingroup$

During my Topology class the following question was brought up:

Question: Suppose that $A$ and $B$ are ordered countable sets. If there are two order preserving injections $f:A \to B$ and $g:B \to A$, is there an order preserving bijection between $A$ and $B$?

I do know that one can construct a bijection using two injections, it is a classic problem. However, I couldn't adapt the proof for order preserving injections.

False or not, I was hoping to find a proof for the following preposition:

Proposition: Every densely totally ordered countable set without lower or upper bound is isomorphic to $\mathbb{Q}$.

$\endgroup$
3
  • 1
    $\begingroup$ The Proposition is true (Cantor proved it). Its usual proof now uses the "back and forth" or "zig-zag" method, which came later -- see en.wikipedia.org/wiki/Cantor's_back-and-forth_method. Re your Question: by "ordered" do you mean totally ordered? $\endgroup$ – BrianO Apr 4 '16 at 16:34
  • $\begingroup$ Note that while the answer to your question is 'no' (see below), it is true if you require well-orders instead of merely linear orders. $\endgroup$ – Stefan Mesken Apr 4 '16 at 16:52
  • $\begingroup$ I didn't mean totally ordered, I was just wondering as stated during my class. For the proposition, thank you for the hyperlink. I read a little and it is the same proof used in class. I may take a look for others uses of the method. Thank you. $\endgroup$ – B. Rivas Apr 4 '16 at 17:20
5
$\begingroup$

It appears that your conjecture as stated is false. Indeed, let $A=(0,1)\cap \Bbb Q$ and $B=\Bbb N \cup A$, $f:A\to B$ be the identity mapping, $g:B\to A$ be defined by $$ g(b)=\begin{cases} \frac b2\ ;\ b\in A \\ 1-\frac 1{b+1}\ ;b\in \Bbb N \end{cases}$$ , then both $f$ and $g$ are order preserving injections. However, $A$ and $B$ have different order type so there cannot be any order isomorphism between them.

Nevertheless, your proposition is true and, as Mr. BrianO has commented, was proved by Cantor. The wikipedia link is a nice place to visit but if you want a book, then Raymond Wilder's Introduction to the Foundations of Mathematics devotes some pages talking about order isomorphism of rational, real etc.

$\endgroup$
3
  • 5
    $\begingroup$ A simpler example: consider $(0, 1)\cap\mathbb{Q}$ versus $[0, 1]\cap\mathbb{Q}$. Also, another source you may be interested in is Rosenstein's book "Linear orderings". $\endgroup$ – Noah Schweber Apr 4 '16 at 16:52
  • $\begingroup$ Or even simpler $(0, 1)\cap\mathbb{Q}$ vs. $(0, 1]\cap\mathbb{Q}$, $g$ being $g(x)=x/2$ :) $\endgroup$ – BigbearZzz Apr 4 '16 at 17:05
  • 1
    $\begingroup$ Thank you for your answer. So the main point I was missing is the order type. :) Cheers. $\endgroup$ – B. Rivas Apr 4 '16 at 17:17

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.