17
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Lexicographic order on R^R? $\endgroup$ Jun 2, 2010 at 22:23
  • 6
    $\begingroup$ 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. $\endgroup$ Jun 3, 2010 at 1:09

4 Answers 4

20
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Doh! I was only trying to define a total ordering on the powers set of R or on R^R. Is this possible? $\endgroup$ Jun 2, 2010 at 20:54
  • 1
    $\begingroup$ "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. $\endgroup$ Jun 2, 2010 at 21:01
  • 1
    $\begingroup$ 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... $\endgroup$ Jun 2, 2010 at 21:12
  • 3
    $\begingroup$ @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. $\endgroup$ Jul 29, 2012 at 3:01
  • $\begingroup$ Andreas, yes, I agree. $\endgroup$ Jul 30, 2012 at 17:30
16
$\begingroup$

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.]

$\endgroup$
9
  • 1
    $\begingroup$ Thanks, Andres. Would it be possible for you briefly to explain why $R/\sim$ cannot be linearly ordered under AD? $\endgroup$ Jun 3, 2010 at 5:15
  • $\begingroup$ 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 $\endgroup$ Jun 3, 2010 at 11:21
  • $\begingroup$ 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.) $\endgroup$ Nov 24, 2010 at 17:00
  • 4
    $\begingroup$ 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. $\endgroup$ Nov 30, 2010 at 15:14
  • 1
    $\begingroup$ @AkivaWeinberger This is (a special case of) Kolmogorov's zero-one law. See for example en.wikipedia.org/wiki/Kolmogorov%27s_zero%E2%80%93one_law $\endgroup$ Jun 28, 2022 at 12:07
4
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ If one thinks of $P(\kappa)$ as $2^\kappa$, then François' order is also known as the lexical order. $\endgroup$ Jun 2, 2010 at 21:16
2
$\begingroup$

[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.

$\endgroup$
0

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.