Is this a characterization of well-orders?

Question

While grading some papers and thinking about a question related to well-orders (in particular, pointing a mistake in a solution), I came to think of a reasonable characterization for well-orders. I can immediately see it's true for countable orders, but not for uncountable orders.

Definition. Let $\cal L$ be a first-order language, and $\cal M$ an $\cal L$-structure. We say that $\cal M$ is rigid if $\text{Aut}(\cal M)=\{\rm id\}$.

Conjecture. Let $\cal L=\{<\}$. Then $\mathcal M=\langle M,<\rangle$ is rigid if and only if it is a well-order or its reverse order is a well-order.

One direction is trivial. Well-orders are rigid (and therefore their reversed orders are rigid as well). In the other direction, if $\cal M$ is countable, then it is easy. Suppose it's not a well-order.

If $\cal M$ contains a convex copy of $\Bbb Z$ then fix everything else and shift that copy by $1$.
Otherwise $\cal M$ contains a convex copy of $\Bbb Q$ and then we can shift that copy by $1$ (or multiply it by $\frac12$, whatever floats your boat).

The problem is that for uncountable order types the plot thickens and they might be $\kappa$-dense, so neither of the arguments would work (and there is no additive structure - that I know of - that we can exploit like in the countable case).

Question: Does the conjecture hold, or is there some intricate counterexample?

Perhaps it is not clear for countable. What about the backwards natural numbers? — André Nicolas, Jul 07 '13 at 01:05
@Andre: Ah. Yes, of course. I meant that in the broad sense, thank you for the correction! (I also thought that I managed to prove this for uncountable orders, but then I got stuck because not every two $\kappa$-dense orders are isomorphic!) — Asaf Karagila, Jul 07 '13 at 01:12
I am sure definition can be worked out, but what about natural numbers followed by backward natural numbers. The natural "automorphism" is technically not. — André Nicolas, Jul 07 '13 at 01:20
@Andre: Hm. That actually answers my question, although it leaves room for generalizations, and the natural extension (i.e. $M$ decomposes to a sum of an ordinal followed by an anti-ordinal over a rigid linearly ordered index). — Asaf Karagila, Jul 07 '13 at 01:23
OK, it took me a bit to locate this. This answer by Brian and the reference there shows the answer is negative. — Andrés E. Caicedo, Jul 07 '13 at 01:37
@Andres: Ah! Not quite a duplicate, but Brian's answer works nonetheless! Wonderful. — Asaf Karagila, Jul 07 '13 at 01:42
@Andre: By the way, your comment is a good answer to the question. So perhaps promote it to such? — Asaf Karagila, Jul 07 '13 at 02:01

score 15 · Accepted Answer · edited Apr 13 '17 at 12:21

The conjecture does not hold. For a simple counterexample, consider $\omega+\omega^*$.

In fact, there are rather dramatic counterexamples: In this answer, Brian M. Scott refers to

B. M. Scott. A characterization of well-orders, Fundamenta Mathematicæ, 111 (1), 71-76. MR0607921 (82i:06001),

where he proves that for every infinite $\kappa$ with $2^{<\kappa}=\kappa$ there is a rigid dense linear order of size $2^\kappa$. Moreover, this order does not even admit order-preserving injections into itself other than the identity.

For $\kappa=\omega$, this is a result of Dushnik and Miller, who even built such a set as a dense subset of the reals. This is Theorem 9.1 of

Joseph G. Rosenstein. Linear orderings, Pure and Applied Mathematics, 98. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. MR0662564 (84m:06001).

For an additional example, in his answer, Brian also mentions the set $$ X=\{(n,\alpha)\mid n\in\omega\,\&\,\alpha\in\omega_n\},$$ ordered by $(m,\alpha)\le(n,\beta)$ iff $m>n$ (as natural numbers), or else $m=n$ and $\alpha\le \beta$ (as ordinals). This order is rigid, and neither a well-order, nor a reverse well-order.

In his paper, Brian also characterizes well-orders: Say that a linear order $(X,<)$ is cushioned iff every order preserving injection $f:X\to X$ satisfies $x\le f(x)$ for all $x$.

Theorem. A linear order $(X,<)$ is a well-order iff it is cushioned and scattered.

There is a related notion of rigidity, where we require $(X,<)$ to be rigid iff it admits no isomorphism with a proper initial segment of itself. This notion has been studied by John L. Hickman, see

J. L. Hickman. Rigidity in order-types, J. Austral. Math. Soc. Ser. A, 24 (2), (1977), 203–215. MR0480217 (58 #397).

May I ask a related question? I am not sure if this is obvious from the above remarks. Can the following conjecture be true? Every rigid structure $\mathcal{M} = (M, <)$ contains a well ordering. — fnimic, Jul 07 '13 at 08:34
@fnimic I'm not sure I understand the question. Perhaps you mean: Either a well-ordering of length $|M|$, or a reverse well-ordering of such length? The set (X,<)$ mentioned after Rosenstein is a counterexample, in either case. Anyway, from Ramsey theory (rather, the Erdős-Rado theorem from partition calculus), any infinite order contains a copy of either $\omega$ or $\omega^$, any infinite order of a set of size $|\mathfrak c|^+$ or larger contains a copy of either $\omega_1$ or $\omega_1^$, etc. — Andrés E. Caicedo, Jul 07 '13 at 14:52
Thank you. Where can I find the proof that any infinite order contains a copy of either $\omega$ or $\omega^*$? — fnimic, Jul 07 '13 at 18:16
@fnimic I would imagine any book discussing the infinite Ramsey theorem would have this as an example: Let $(X,\prec)$ be infinite. Pick a countable infinite subset of $X$, listed as $x_1,x_2,\dots$ For $i<j$, color ${i,j}$ red iff $x_i\prec x_j$, and color it blue if $x_j\prec x_i$. Ramsey's theorem ensures the existence of an infinite set $H$ of numbers such that all pairs of elements of $H$ were painted with the same color. If red, the corresponding $x_i$, $i\in H$, give us a copy of $\omega$ in $X$. If blue, they give us a copy of $\omega^*$. — Andrés E. Caicedo, Jul 07 '13 at 18:29

Is this a characterization of well-orders?

1 Answers1

Linked

Related