Explicit ordering on set with larger cardinality than R

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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