Welcome to MathOverflow

Question

8

1

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?

edited Aug 15 2011 at 22:39

Gerry Myerson
15.8k●1●47●87

asked Aug 15 2011 at 16:46

Feldmann Denis
1,768●2●15

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 2011 at 17:13

2

Sorry, but what is the relation? – Feldmann Denis Aug 15 2011 at 17:18

1

Okay, I've considered them. Now what? – Ricky Demer Aug 15 2011 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 2011 at 17:26

The Dushnik-Miller theorem seems highly relevant, in the form: every countable linear order admits a self-embedding. See homepages.ecs.vuw.ac.nz/~downey/publications/…. 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 2011 at 17:33

Andreas Blass · Accepted Answer · 2011-08-15 18:00:28Z UTC

9

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.

answered Aug 15 2011 at 18:00

Andreas Blass
33.8k●4●59●111

Can you make a countable counterexample, or will the Dushnik Miller phenomenon prevent it? – Joel David Hamkins Aug 15 2011 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 2011 at 18:57

Fantastic ! – Joel David Hamkins Aug 15 2011 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 2011 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 2011 at 2:45

show 1 more comment

Joel David Hamkins · Answer 2 · 2011-08-15 17:24:13Z UTC

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.

A characterisation of well-ordering ?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.