It is easy to prove that if $E$ is well-ordered, and if $f$ is a strictly increasing map from $E$ to $E$, then, for all $x$ in $E$, $f(x) \ge x$ (just consider the sequence $x$, $f(x)$, $f(f(x))\dots$). But is the converse true, i.e. for any totally ordered set $E$ which is not well-ordered, does it exist a strictly increasing map $f$ from $E$ to $E$ and an element $a$ in $E$ such that $f(a) < a$ ? Even assuming choice, I couldn't find a proof (or a counterexample) ; Cantor-Bendixon (or its generalisation to surreals) seems involved, but it could be a red herring. Any hint?

  • 1
    Consider linear functions on the real numbers, or even the rationals. Gerhard "Ask Me About System Design" Paseman, 2011.08.15 – Gerhard Paseman Aug 15 '11 at 17:13
  • 2
    Sorry, but what is the relation? – Feldmann Denis Aug 15 '11 at 17:18
  • 1
    Okay, I've considered them. Now what? – user5810 Aug 15 '11 at 17:19
  • I misread your question, so the above suggestion is not helpful. You may need some machinery such as a classification of countable total orders. One is tempted to modify the identity function on an infinite decreasing chain, but that may mess things up on elements in between. If you can well order the order types, you may be able to find an inductive argument that will produce such a function. Gerhard "Ask Me About System Design" Paseman, 2011.08.15 – Gerhard Paseman Aug 15 '11 at 17:26
  • The Dushnik-Miller theorem seems highly relevant, in the form: every countable linear order admits a self-embedding. See The question would be whether one can carry out the argument with a non-wellorder to always have at least one subdiagonal point, $a\lt f(a)$. – Joel David Hamkins Aug 15 '11 at 17:33
up vote 9 down vote accepted

There are dense subsets $X$ of the real line with the usual order (hence not well-ordered) such that the only strictly increasing map from $X$ to itself is the identity. Here's a sketch of the construction. First note that, for any dense set $X$ of reals, an increasing map from $X$ to itself extends to an increasing map on the reals (not necessarily uniquely, beacuse there may be countably many jumps). Such extensions $f$ are determined by their values at the rationals plus some information about jumps; in particular, there are only continuum ($\mathfrak c$) many possibilities. Well-order the set of all such possibilities $f$ in a sequence of length $\mathfrak c$ (the initial ordinal). Build the desired $X$ in $\mathfrak c$ stages, putting one number into $X$ and one into the complement of $X$ at each step, choosing these numbers so as to defeat one possible $f$ at each step.

  • Can you make a countable counterexample, or will the Dushnik Miller phenomenon prevent it? – Joel David Hamkins Aug 15 '11 at 18:38
  • 5
    Laver's theorem states that if $(A_0,<)$, $(A_1,<)$, .. are countable ordered sets, then $(A_i,<)$ embeds into $(A_j,<)$, for some $i<j$. Assume therefore that $(A,<)$ is an ill ordered countable set. Let $a_0>a_1>\cdots$ be a decreasing sequence, and consider the ordered sets $(A|a_i,<)$. Laver's theroem says that $(A|a_i,<)$ embeds into $(A|a_j,<)$ for some $i<j$, and this can be extended to a mapping $f:(A,<)\to (A,<)$ with $f(a_i)=a_j<a_i$ and which is the identity above $a_i$. – Péter Komjáth Aug 15 '11 at 18:57
  • Fantastic ! – Joel David Hamkins Aug 15 '11 at 19:19
  • I was considering a variant of Peter Komjath's construction where the a_i were chosen and then the order types of the intervals (a_{i+1},a_i) were considered. If I had Laver's theorem for uncountable order types, I might be able to argue either that one of the intervals could dip below the identity, or else I would have a decreasing sequence of nonembeddable order types. I guess Andreas Blass suggests I look for the latter. Gerhard "Ask About System Design" Paseman, 2011.08.15 – Gerhard Paseman Aug 15 '11 at 21:37
  • With $X$ the set defined by Andreas Blass, let $A_n=X\cap (-\infty,-n)$; it is easy to check that the $A_j$ (with the usual order) dont verify Laver's theorem... – Feldmann Denis Aug 24 '11 at 2:45

In the context of ZF, rather than ZFC, it is consistent that the properties are not equivalent. This is because it is known to be consistent with ZF that there can be an infinite sets of reals that is Dedekind finite, meaning that it has no countably infinite subset. Such a set is linearly ordered by the usual relation on the reals, but it is not well-ordered by this relation and indeed, has no well-order at all, because any such well-order would allow us to find a countably infinite subset. But meanwhile, there can be no order-preserving function $f$ with $f(a)\lt a$, since by iterating such a function, we would produce a descending sequence, which would give a countably infinite subset, a contradiction. So these sets are not well-ordered by the usual order on the reals, but they have no witnessing function as you request.

So the real question, it seems, should be about the ZFC context, for which I am keen to see an answer.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.