23
$\begingroup$

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

$\endgroup$
5
  • 2
    $\begingroup$ Trivial answer: take a finite subset. You are looking for any infinite subset? $\endgroup$
    – The User
    May 26, 2013 at 18:18
  • $\begingroup$ @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$. $\endgroup$
    – The User
    May 26, 2013 at 18:30
  • $\begingroup$ @TheUser Thanks! Yes, I had in mind an infinite subset. $\endgroup$ May 26, 2013 at 18:33
  • $\begingroup$ Isomorphic as what? I assume you mean as sets, and not, say, topological spaces, but if so, please edit the question to clarify. $\endgroup$ May 26, 2013 at 19:36
  • 7
    $\begingroup$ Theo, the question says "order isomorphic." $\endgroup$ May 26, 2013 at 19:53

3 Answers 3

15
$\begingroup$

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!

$\endgroup$
0
18
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Oh, now I see that François's construction already has this same idea! $\endgroup$ May 26, 2013 at 20:30
  • 1
    $\begingroup$ The real credit goes to sdcvvc who told us both about this construction back in 2009... $\endgroup$ May 26, 2013 at 20:37
  • 2
    $\begingroup$ Vote up this comment if I should delete. $\endgroup$ May 26, 2013 at 20:39
  • 6
    $\begingroup$ No, it's good for MO to have multiple variants of the same question & answer. $\endgroup$ May 26, 2013 at 20:41
  • 1
    $\begingroup$ See also mathoverflow.net/questions/72935/… . $\endgroup$ May 26, 2013 at 22:00
8
$\begingroup$

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.

$\endgroup$
6
  • 3
    $\begingroup$ References: Jech, The Axiom of Choice Chapter 5, Cohen's first model; also Chapter 10 section 1. :-) $\endgroup$
    – Asaf Karagila
    May 26, 2013 at 18:27
  • $\begingroup$ Thanks! I am interested in $\mathsf{ZFC}$, an explicit construction or at least an existence proof. $\endgroup$ May 26, 2013 at 18:38
  • $\begingroup$ 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. $\endgroup$ May 26, 2013 at 18:40
  • 1
    $\begingroup$ 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. $\endgroup$ May 26, 2013 at 18:42
  • 1
    $\begingroup$ 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. $\endgroup$ May 26, 2013 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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