Take the 2-minute tour ×

Which are the rigid suborders of the real line?

If A is any set of reals, then it can be viewed as an order structure itself under the induced order (A,<). The question is, when is this structure rigid? That is, for which sets A does the structure (A,<) have no nontrivial order automorphisms?

For example, the positive integers are rigid under the usual order. More generally, any well-ordered subset of R is rigid. Similarly, any anti-well-ordered set, such as the negative integers, is also rigid.

It is also true that the order sum of any well-order plus an anti-well-order is rigid. For example, a sequence converging upward to 0 plus a sequence converging downward to 0 will have order type ω+ω*, which is rigid. (Whereas it is easy to see that the sum of an infinite anti-well-order and an infinite well-order will not be rigid, since it has a copy of Z in the center.) A more elaborate example will be a well-ordered sum of anti-well-orders, such as the set consisting of k+1/n for any positive integers k and n.

All these examples are countable; are there uncountable examples?

Perhaps there will be some ZFC independence for certain types of examples? I am primarily interested in the situation under ZFC. In ZF without the Axiom of Choice, there can be weird anomalies of uncoutable sets that are Dedekind finite. All such sets are rigid, as I explained in this question. But if someone can provide a ZF characterization, that would also be interesting.

share|improve this question

2 Answers 2

up vote 19 down vote accepted

Here is a simple example of size continuum. Do the ordinary middle-third construction of the Cantor set, except that whenever you delete the $n$-th (numbered by level and then left to right, say) middle-third interval leave in exactly $n$ points from that interval. Let's call the resulting set $X$. Any automorphism of $X$ must map (resp. left-, right-) isolated points to (resp. left-, right-) isolated points. Since we left a different number of points in each middle-third interval, the automorphism must fix every inner point of each middle-third interval as well as its two endpoints. By density, it follows that the automorphism fixes every point of $X$.

All of your examples are scattered, I checked the Rosenstein's Linear Orderings to see if he had anything good to say about which scattered linear orders are rigid. To my dismay, this is what I found: "These considerations seem to make impossible an inductive argument (on $F$-rank or $VD$-rank) to determine which scattered types are rigid." (p. 133) However, he does cite a result of Anne Morel (Ordering relations admitting automorphisms, Fund. Math. 54 (1964), 279-284.) which says that a linear order $A$ is not rigid if and only if $A \cong A_1 + A_2\times\mathbb{Z} + A_3$ for some linear orderings $A_1,A_2,A_3$, with $A_2$ nonempty.

Dense examples of rigid subsets of $\mathbb{R}$ would be interesting to see. This is probably not too difficult to construct under CH. But a ZFC example might have to deal with important barriers such as Baumgartner's result that All ${\aleph_1}$-dense subsets of $\mathbb{R}$ can be isomorphic, Fund. Math. 79 (1973), 101-106. Maybe there are some examples in this classic paper of Sierpinski Sur les types d'ordre des ensembles linéaires, Fund. Math. 37 (1950), 253-264.

All three papers can be found here.

Addendum (after sdcvvc's comment): For the sake of completeness, I'm including a simplification of the Dushnik-Miller argument that produces a dense subset $X$ of $\mathbb{R}$ which is rigid (though not the stronger result that $X$ has no self-embeddings).

To ensure density, the set $X$ will contain all rational numbers. Note that an automorphism $f$ of $X$ is then completely determined by its restriction to $\mathbb{Q}$. Indeed, since $f[\mathbb{Q}]$ must be dense (in $X$ and) in $\mathbb{R}$, we always have

$f(x) = \sup\{f(q):q \in (-\infty,x)\cap\mathbb{Q}\} = \inf\{f(q):q \in (x,\infty)\cap\mathbb{Q}\}.$

There are only $c = 2^{\aleph_0}$ increasing maps $f:\mathbb{Q}\to\mathbb{R}$ with dense range. Let $\langle f_\alpha:\alpha<c \rangle$ enumerate all such maps, except for the identity on $\mathbb{Q}$.

We will define by induction a sequence $\langle (x_\alpha,y_\alpha) : \alpha<c \rangle$ of pairs of irrational numbers. The $x_\alpha$ will be points of $X$ while the $y_\alpha$ will be in the complement of $X$. For each $\alpha$, we will have $f_\alpha(x_\alpha) = y_\alpha$ (in the sense of the inf/sup definition above).

Suppose we have defined $(x_\beta,y_\beta)$ for $\beta<\alpha$. Since $f_\alpha$ is not the identity, there is a rational $q$ such that $f_\alpha(q) \neq q$. Let's suppose that $f_\alpha(q) > q$ (the case $f_\alpha(q) < q$ is symmetric). Since the real interval $(q,f_\alpha(q))$ has size $c$ and the extension of $f_\alpha$ to all of $\mathbb{R}$ is injective, we can always pick

$x_\alpha \in (q,f_\alpha(q)) \setminus(\mathbb{Q}\cup\{y_\beta:\beta<\alpha\})$

such that $y_\alpha = f_\alpha(x_\alpha) \notin \mathbb{Q}\cup\{x_\beta:\beta<\alpha\}$. Note that $x_\alpha < f_\alpha(q) < y_\alpha$ so $x_\alpha \neq y_\alpha$.

In the end, we will have

$\{x_\alpha: \alpha < c\} \cap \{y_\alpha : \alpha<c\} = \varnothing$

and any set $X$ such that

$\mathbb{Q}\cup\{x_\alpha:\alpha<c\} \subseteq X \subseteq \mathbb{R}\setminus\{y_\alpha:\alpha<c\}$

is necessarily rigid since $f_\alpha(x_\alpha) = y_\alpha \notin X$ for each $\alpha<c$.

share|improve this answer
Rosenstein gives an example of a dense suborder of $\mathbb{R}$ without any monotonic map into itself (that's stronger than rigid), without using CH in theorem 9.1. [Dushnik and Miller, Concerning similarity transformations of linearly ordered sets] –  sdcvvc Dec 28 '09 at 13:05
Thanks! I just updated my answer to include this example. –  François G. Dorais Dec 28 '09 at 22:17
Thanks for a beautiful example with the Cantor set! And the Morel result provides a characterization of sorts (although the stated fact is very easy to prove). I guess in Baumgartner's model, none of the omega_1 dense orders are rigid. Lastly, why is your answer community wiki? It is a pity, since this prevents you from earning the votes your answer has deserved. –  Joel David Hamkins Dec 29 '09 at 16:24
I had no idea I had pressed the community wiki button. I'll be more careful next time. –  François G. Dorais Dec 29 '09 at 17:02
If I start from a model of CH and add reals, not collapsing cardinals, to obtain $2^{\aleph_{0}} > \aleph_{1}$, is the old modified Cantor set (of François) still rigid? –  Avshalom Aug 29 '14 at 18:40

One can construct uncountable ones using transfinite induction.


J. van Mill, Sierpin ́ski’s Technique and subsets of R, Top. Appl. 44 (1992), 241–261.

has such examples, in ZFC.

One enumerates all candidate (in this case) homeomorphisms in a well-ordered sequence in length c and then constructs the set "killing" the candidate alpha at stage alpha of the recursion. Probably older examples exist, but I could recall this one. Check it out.

share|improve this answer
Thanks very much for this answer. Clearly this is the way to do it, and it easily produces dense examples. –  Joel David Hamkins Dec 29 '09 at 16:27
The set built by Sierpinski can also be built in Baumgartners' model? is it rigid because it is not $\aleph_1$-dense? –  Eran Mar 12 '14 at 8:16
@Eran: the key point is that the Sierpinski orders are of size $2^{\aleph_0}$, and can be arranged to be $2^{\aleph_0}$-dense. This way, in building them iteratively, one can diagonalize against every possible order-isomorphism onto a subset, since there are only continuum many candidates for such isomorphisms. So, in Baumgartner's model, where the continuum is $\aleph_2$, a Sierpinksi order is $\aleph_2$-dense. –  Garrett Ervin Aug 29 '14 at 21:09

Your Answer


