MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is it possible to construct an infinite subset of $\Bbb R$ that is not order isomorphic to any proper subset of itself?

share|cite|improve this question
Trivial answer: take a finite subset. You are looking for any infinite subset? – The User May 26 '13 at 18:18
@Benjamin It is not the case for every choosen subset $T\subset S$. For example consider $S=\left\{0\right\}\cup\left\{\frac{1}{n}\mid n\in\mathbb{N}\right\}$. If you remove the $0$, this subset is not order isomorphic to $S$. – The User May 26 '13 at 18:30
@TheUser Thanks! Yes, I had in mind an infinite subset. – Marty Colos May 26 '13 at 18:33
Isomorphic as what? I assume you mean as sets, and not, say, topological spaces, but if so, please edit the question to clarify. – Theo Johnson-Freyd May 26 '13 at 19:36
Theo, the question says "order isomorphic." – François G. Dorais May 26 '13 at 19:53
up vote 12 down vote accepted

There is no such countably infinite set, but there is such a set with size $2^{\aleph_0}$. These are classic results of Dushnik & Miller [Concerning similarity transformations of linearly ordered sets, Bull. Amer. Math. Soc. 46 (1940), 322-326]. I also outlined the idea behind this construction in my first MathOverflow answer!

share|cite|improve this answer

The answer is yes in ZFC. We can construct a dense infinite set $A\subset\mathbb{R}$ such that the only order-preserving map $f:A\to A$ is the identity. In particular, $A$ is not order-isomorphic with any proper subset of itself.

To see this, note first that any order-preserving map $f:B\to\mathbb{R}$ defined on a dense set $B\subset\mathbb{R}$ can be extended to a total order-preserving map $\bar f:\mathbb{R}\to\mathbb{R}$ defined on the closure of $B$, by defining $\bar f(x)=\sup_{y\leq x, y\in B}f(y)$. Further, note that any such monotone map will have at most countably many points of discontinuity, since every discontinuity will be a jump discontinuity. Thus, there are precisely continuum many such order-preserving functions $\mathbb{R}\to\mathbb{R}$, since any one of them is determined by countably much information about their values on a countable dense set and the information about what their values are on the countably many points of discontinuity.

We may therefore enumerate all order-preserving functions $f_\alpha:\mathbb{R}\to\mathbb{R}$ in a sequence of length continuum, $\alpha\lt\mathfrak{c}$.

Let's now build the set $A$ by a transfinite process, making promises at each stage about some reals being definitely in $A$ and other promises about keeping some reals out of $A$, in such a way that we kill off $f_\alpha$ at stage $\alpha$ as a possible order-preserving map from $A$ to $A$. We may begin at stage $0$ by placing all the rational numbers into $A$, so that it will definitely be dense. Suppose we have carried out our process up to stage $\alpha$, and $f_\alpha$ is the next non-identity order-preserving map $\mathbb{R}\to\mathbb{R}$ presented for our consideration. Since $f_\alpha$ is order-preserving and not the identity, it must be that there is an interval $(a,b)$ with $(f(a),f(b))$ disjoint from $(a,b)$. Since we've made fewer than continuum many promises so far, there must be an $x\in (a,b)$ such that we've made no promises about $x$ or $f_\alpha(x)$. In this case, we place $x$ into $A$ and promise to keep $f_\alpha(x)$ out of $A$. This will prevent $f_\alpha$ from being an order-isomorphism of $A$ to a proper subset of $A$.

The end result is that $A$ is dense, but is strongly rigid in the sense that there is no non-identity order-preserving map from $A$ to $A$. In particular, $A$ is not order-isomorphic with any proper subset of itself.

share|cite|improve this answer
Oh, now I see that François's construction already has this same idea! – Joel David Hamkins May 26 '13 at 20:30
The real credit goes to sdcvvc who told us both about this construction back in 2009... – François G. Dorais May 26 '13 at 20:37
Vote up this comment if I should delete. – Joel David Hamkins May 26 '13 at 20:39
No, it's good for MO to have multiple variants of the same question & answer. – François G. Dorais May 26 '13 at 20:41
See also… . – Andreas Blass May 26 '13 at 22:00

EDIT: The other answers show that my intuition was wrong, and that in fact there is such a linear order in $ZFC$, so this answer (except the bit about determinacy) is superfluous.

Although it seems likely that $ZFC$ proves there is no such order, choice will certainly be necesary for such a proof: it is consistent with $ZF$ that $\mathbb{R}$ has infinite, Dedekind-finite subsets, which is exactly what you're asking for. (I'm looking for a reference . . . EDIT: Asaf gives a good reference in a comment, below.)

There can be no countable example of such an order, however; such an order can't embed $\mathbb{Q}$, and hence is scattered, and a result (I believe) of Jullien then lets us write it as a finite sum of indecomposable orders; it is then easy to see that the whole order embeds into a proper subset of itself.

If we assume the Axiom of Determinacy, then every uncountable set of reals has a perfect subset; this means there is no uncountable example of such an order, and hence by the above fact the answer to your question is no.

Under choice, things look a bit more complicated, but I suspect the answer is no; I'll post more if I can figure it out.

share|cite|improve this answer
References: Jech, The Axiom of Choice Chapter 5, Cohen's first model; also Chapter 10 section 1. :-) – Asaf Karagila May 26 '13 at 18:27
Thanks! I am interested in $\mathsf{ZFC}$, an explicit construction or at least an existence proof. – Marty Colos May 26 '13 at 18:38
Note that by work of Richard Laver, any such linear order has to not be a countable union of scattered orders. This is still massive overkill; I suspect there is a straightforward impossibility proof I'm not seeing. – Noah Schweber May 26 '13 at 18:40
Also, note that (assuming large cardinals) we can't hope for an example which is "nicely definable" in the sense of being projective, for the same reason that $AD$ implies there is no such order at all. So this might mean, depending on your definition of "explicit," that there is no explicit construction. – Noah Schweber May 26 '13 at 18:42
Noah, I like your answer very much, but your way of saying, "Yes, if we do not assume AC" could be misinterpreted as claiming that the answer is yes provably in ZF. But this is not what you mean, since you are claiming only the weaker assertion that a positive answer is relatively consistent with ZF. – Joel David Hamkins May 26 '13 at 20:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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