Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is it possible to construct (without using Axoim of Choice) a totally ordered set S with cardinality larger than $\mathbb{R}$?

Motivation: A total ordering is often called a “linear ordering”. I have heard the following explanation: “If you have a total ordering on a set S, you can plot the set on the real line such that elements to the right are greater than elements to the left”. Formally this means that there exist a function $\phi:S\rightarrow \mathbb{R}$ such that for all $ a$ ,$b\in S$, x < y $ \Leftrightarrow \phi(x)$ < $\phi(y)$. This is of course correct if the set is finite or countable (and it gives a good intuition on what a total ordering is), but obviously not if $|S|>|\mathbb{R}|$, and using the axiom of choice it is easy to “construct” a total ordering on, say, the power set of $\mathbb{R}$. But I would prefer to have a more concrete counterexample, and this is why I asked myself this question.

Later I realized that is was possible to construct a total ordering on a set $|S|=|\mathbb{R}|$, such that no such function $\phi$ exist, but I still think that the above question is interesting.

share|improve this question
Lexicographic order on R^R? –  Qiaochu Yuan Jun 2 '10 at 22:23
For lexicographic, the exponent should be well-ordered (or maybe reverse well-ordered). With the usual ordering on the exponent R, you can have two members of R^R but no least spot where they disagree. –  Gerald Edgar Jun 3 '10 at 1:09
add comment

5 Answers

up vote 13 down vote accepted

Yes. By Hartogs' theorem, there is an ordinal that has no injection into $R$. The minimal such ordinal is the smallest well-ordered cardinal not injecting into $R$. It is naturally well-ordered by the usual order on ordinals. None of this needs AC.

One can think very concretely about the order as follows: Consider all subsets of $R$ that are well-orderable. By the Axiom of Replacement, each well-order is isomorphic to a unique ordinal. Let $\kappa$ be the set of all ordinals that inject into $R$ in this way. One can show that $\kappa$ itself does not inject into $R$, and this is the Hartogs number for the reals.

More generally, of course, there is no end to the ordinals, and they are all canonically well-ordered, without any need for AC.

But in terms of the remarks in your "motivation" paragraph, there are linear orders that do not map order-preservingly into $R$ that are not larger than $R$ in cardinality. For example, the ordinal $\omega_1$ cannot map order-preservingly into $R$, since if it did so, then there would be an uncountable family of disjoint intervals (the spaces between the successive ordinals below $\omega_1$), but every such family is countable by considering that the rationals numbers are dense. Another way to see this is to observe that the real line has countable cofinality for every cut, but $\omega_1$ has uncountable cofinality.

Lastly, there is a subtle issue about your request that the order by "larger than $R$". The examples I give above via Hartog's theorem are not technically "larger than $R$", although they are not less than $R$ in size. The difficulty is that without AC, the cardinals are not linearly ordered, and so these two concepts are not the same. But you can turn the Hartogs argument into a strict example of what you requested by using the lexical order on $R\times\kappa$, where $\kappa$ is the Hartog number of $R$. This order is strictly larger than $R$ in size, and it is canonically linearly ordered by the lexical order.

share|improve this answer
Doh! I was only trying to define a total ordering on the powers set of R or on R^R. Is this possible? –  Sune Jakobsen Jun 2 '10 at 20:54
"there are linear orders that do not map order-preservingly into R that are not larger than R in cardinality". Yes, the example I thought of was R^2 with lexicographical ordering. –  Sune Jakobsen Jun 2 '10 at 21:01
Sune, in general it is a weak choice principle that every set admits a linear order. I'm not sure if this extends down to $R^R$, but I think it might. Perhaps $2^R$ is also a natural case: Can you linearly order $2^R$ without AC? I think that in the usual model with $\neg AC$, the set $2^R$ has no linear order... –  Joel David Hamkins Jun 2 '10 at 21:12
@Joel: The original question has a slightly cheaper answer than the product of $\mathbb R$ and its Hartogs ordinal. You could just use the disjoint union of $\mathbb R$ and its Hartogs ordinal, ordered by putting all of $\mathbb R$ before all the ordinals. –  Andreas Blass Jul 29 '12 at 3:01
Andreas, yes, I agree. –  Joel David Hamkins Jul 30 '12 at 17:30
add comment

This is a response to Joel's comment about whether $2^{\mathbb R}$ can be linearly ordered without choice. In general, no. There is a concrete obstacle, actually: Vitali's equivalence relation. Recall that this relation is defined by $x\sim y$ iff $x-y\in{\mathbb Q}$. Now consider ${\mathbb R}/\sim$, the collection of equivalence classes. This is a concrete subset of $2^{\mathbb R}$ that in general cannot be linearly ordered without some appeal to choice.

For example, under determinacy, this set is not linearly orderable, so in $L({\mathbb R})$ there is no linear ordering of it in the presence of large cardinals. In short, under reasonable assumptions, there is no way of linearly order this set without appealing to choice.

Things get interesting. For example, in $L({\mathbb R})$ (the smallest model of ZF that contains all the reals), in the presence of large cardinals, a set is linearly orderable iff ${\mathbb R}/\sim$ does not inject into it, and a set is well-orderable iff ${\mathbb R}$ does not inject into it.

Here are some details, it is not a complete argument, it requires knowing some descriptive set theory (and there may be some typos), but the sketch should give a decent idea.

I'll actually work with $2^\omega/E_0$ (which is another manifestation of Vitali's relation). I learned this from Benjamin Miller, by the way, and it immediately became key for some results Richard Ketchersid and I have been working on. The result itself, that under AD this quotient does not admit a linear ordering, has been known to descriptive set theorists for ages, I am not sure who first noticed it.

Recall that $x\mathrel{E_0}y$, for $x,y\in2^\omega$, iff there is some $n$ such that for all $m\ge n$ we have $x(m)=y(m)$. It suffices to assume that all sets of reals have the Baire property.

Suppose $R$ is a linear ordering of $2^\omega/E_0$. Then the pullback $\hat R$ of $R$ is a quasi-ordering of $2^\omega$. Begin by noticing that $\hat R$ is not meager. Otherwise, $2^\omega$ itself would be meager, being the union of $\hat R$ and $\hat R^{-1}$ (its ``flip'').

Note that the set

{$x \mid${ $y \mid x \mathrel{\hat R} y$} is non-meager }

is itself non-meager, by the Kuratowski-Ulam theorem, so we can fix some $s \in 2^{<\omega}$ such that

{$ x \mid${ $y \mid x \mathrel{\hat R} y $} is co-meager in $N_s$}

is non-meager, where $N_s$ is the basic neighborhood consisting of sequences in $2^\omega$ that begin with $s$.

The key point is that if a set has the Baire property and $E_0$ restricted to that set is smooth (i.e.,there is a Borel reduction to the identity on that set), then the set is actually meager (this follows from the Glimm-Effros dichotomy of Harrington-Kechris-Louveau).

Note that $E_0$ is smooth on the set

{$x\mid$ there are $y$, $z$ such that $x \mathrel{E_0} y \mathrel{E_0} z$, and exactly one of {$y'\mid y' \mathrel{\hat R} y$}, {$z'\mid z \mathrel{\hat R} z'$ } is co-meager in $N_s$}.

This is not hard, but needs a tiny bit of thought. The point is that any $E_0$-class admits a natural ${\mathbb Z}$-ordering, and on the set above we can pick representatives from each class, since we actually have a way of ``assigning an origin'' to this ordering.

It follows that that the set

{ $x \mid$ for all $x' E_0 x$ the set { $y \mid x' R y$ } is co-meager in $N_s$ }

is non-meager.

Now: This set is $E_0$-invariant, and therefore it must actually be co-meager.

But then $\hat R$ itself is co-meager in $N_s \times N_s$. Now let $E$ be the equivalence relation $\hat R\cap \hat R^{-1}$. Then $E$ is also co-meager in $N_s \times N_s$. But then it admits an equivalence class which is co-meager in $N_s$. Since $E$ actually contains $E_0$, we then have that it is co-meager in all of $2^\omega$.

But then $R$ cannot be a linear order, as it cannot distinguish between co-meager many $E_0$-classes.

[As a final remark: One can of course organize the whole thing using Lebesgue measurability rather than the property of Baire, and Fubini's theorem rather than Kuratowski-Ulam. But the argument using the Baire property shows that this is equiconsistent with ZF (by Shelah), while using measurability would in consistency require an inaccessible.]

share|improve this answer
Thanks, Andres. Would it be possible for you briefly to explain why $R/\sim$ cannot be linearly ordered under AD? –  Joel David Hamkins Jun 3 '10 at 5:15
An easier solution was given by Sierpinski, see Theorem 6 of Sur une proposition qui entraîne l'exsistence des ensembles non-mesurables, Fund. Math. 34 - matwbn.icm.edu.pl/ksiazki/fm/fm34/fm34121.pdf –  François G. Dorais Jun 3 '10 at 11:21
François : Sorry for not replying earlier, I just noticed I hadn't. First, thanks for the reference, I didn't know this dated to Sierpinski. And I guess it is a matter of taste, but to me his argument is nit simpler. His looks more direct since he argues in terms of Lebesgue measurability (which I don't for consistency strength issues) and for the reals and the Vitali relation rather than $2^\omega$ and $E_0$ (but this is mainly because it is in this fashion that one usually needs to apply the result nowadays in descriptive set theory, so it made sense to give the presentation that way.) –  Andres Caicedo Nov 24 '10 at 17:00
Here's a yet easier (in my opinion) solution, probably due to Mycielski in one of the early papers on AD. Given a linear ordering of $2^\omega/E_0$, let $A$ be the set of those $x\in2^\omega$ such that the $E_0$-class of $x$ precedes that of its reflection (i.e., $n\mapsto 1-x(n)$). If $A$ were Lebesgue measurable, it would have measure 0 or 1, because it's $E_0$-invariant. But it's sent to its complement by reflection, which preserves measure, so the measure of $A$ must be 1/2 --- contradiction. –  Andreas Blass Nov 30 '10 at 15:14
@Andreas: This is better, thanks! Pretty sure I read it at some point. I need to stop forgetting these things... –  Andres Caicedo Nov 30 '10 at 15:32
add comment

As Joel pointed out, for every set there $X$ is a first ordinal $\aleph(X)$ which does not inject into $X$ — the Hartogs number of $X$. If $X$ is a linear ordering of any kind, there cannot be an order embedding of $\aleph(X)$ into $X$.

If all you want is a linear ordering that does not order-embed into $\mathbb{R}$ then $\aleph(\mathbb{R})$ might be much bigger than necessary. The first uncountable ordinal $\aleph_1$ has this property. Indeed, if $\phi:\aleph_1\to\mathbb{R}$ were an order-embedding, then for every $\alpha \in \aleph_1$, we could find a rational number in the interval $(\phi(\alpha),\phi(\alpha+1))$. These rationals must all be distinct so this gives an injection of $\aleph_1$ into $\mathbb{Q}$. Since $\mathbb{Q}$ is countable and $\aleph_1$ isn't, such an injection cannot exist.

Finally, the powerset of any ordinal number $\kappa$ has a natural ordering which can be described as follows. Given distinct $x, y \in \mathcal{P}(\kappa)$, let $\delta(x,y)$ be the minimal element of the symmetric difference $(x \cup y) \setminus (x \cap y)$. Note that $\delta(x,y)$ belongs to exactly one of $x$ or $y$. Define $x < y$ if $\delta(x,y) \in y$. It's a nice exercise to verify that this is transitive.

share|improve this answer
If one thinks of $P(\kappa)$ as $2^\kappa$, then François' order is also known as the lexical order. –  Joel David Hamkins Jun 2 '10 at 21:16
add comment

[edited nonsense]

With regard to the motivational problem, we have the following theorem:

If $(X,\leq)$ is a total order, then there exists a function $\phi:X\to\mathbb{R}$ such that $x< y$ iff $\phi(x)<\phi(y)$ if and only if there exists a countable set $C$ such that whenever $x < y$, there exists $c\in C$ with $x\leq c\leq y$.

Proof: Suppose such a function $\phi$ exists. We call a pair of elements in X a jump if they are different and there is no other element strictly between them. If $(x_1,x_2)$ and $(x_3,x_4)$ are jumps, then the intervals $(\phi(x_1),\phi(x_2))$ and $(\phi(x_3),\phi(x_4))$ are disjoint. Since there are at most countably many disjoint open intervals of real numbers, there are at most countably many jumps. Let $J$ be the set of all elements that occur in a jump. J is countable.
Pick for each pair of rational numbers $q_1, q_2$ with $q_1< q_2$ such that $\phi(X)\cap(q_1,q_2)\neq\emptyset$ a point x such that $\phi(x)\in\phi(X)\cap(q_1,q_2)$ and collect them in a set B. Since there are countable many such pairs, B is countable. Let $C=B\cup J$. Now if $x< y$, then either $x,y$ form a jump in which case we are done, or there is an element in B strictly between them.

On the other hand, if such a countable set $C=${$ c_1,c_2,\ldots$} exists, the function $\phi:X\to\mathbb{R}$ given by $\phi(x)=\sum_{c_n< x}1/2^n-\sum_{c_n > x}1/2^n$ is easily seen to do the job.

The sufficiency of such a set C is due to Debreu: "Representation of a Preference Ordering by a Numerical Function (Lemma II). I don't know who has first shown the necessity part, but it can be found in many books on decision theory.

share|improve this answer
add comment

Is this not a trivial question? First thing I thought of was the set of real-valued functions on the unit interval. The ordering is just the obvious lexicographic ordering. This is of course not a well-ordering, but you didn't say you wanted one.

share|improve this answer
I suppose that means that $f < g$ if for the least $x\in[0,1]$ such that $f(x)\ne g(x)$ one has $f(x) < g(x)$. So, if $f(x)=x\sin(1/x)$ for $x > 0$ and $f(0)=0$ and $g(x)=-f(x)$, then does $f < g$ or does $g < f$? –  Robin Chapman Nov 30 '10 at 10:25
add comment

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.