22
$\begingroup$

Because I find any totally ordered set can be "lined up" in a straight line, I'm guessing that the set of all the real numbers is the biggest totally ordered set possible. In the sense that any other totally ordered set is isomorphic (order-preserving) to a subset of real numbers. Is that right?

$\endgroup$
  • 5
    $\begingroup$ No. There are arbitrarily large totally ordered sets. See en.wikipedia.org/wiki/Hartogs_number . $\endgroup$ – Qiaochu Yuan Dec 10 '12 at 4:16
  • 18
    $\begingroup$ Perhaps it was because OP's name is Voldemort, but I originally read Qiaochu's link as the "Hogwarts number." $\endgroup$ – JavaMan Dec 10 '12 at 5:12
  • $\begingroup$ @JavaMan: Yours should be the comment of the day. I wish I could give you +50 for it. $\endgroup$ – Haskell Curry Dec 10 '12 at 5:32
  • $\begingroup$ Related question: Any example of how to order a set of aleph-2 cardinality (for example the set of sets of reals?) $\endgroup$ – Giulio Prisco May 17 '15 at 10:25
  • $\begingroup$ The set of real numbers is the largest totally ordered group only in the sense that having no nontrivial convex subgroups. This means any totally ordered group having convex subgroups only zero subgroup is isomorphic to subgroup of R as a ordered group. $\endgroup$ – CAA Jul 1 '15 at 17:35
24
$\begingroup$

Elementary Construction

Without going into too much set theory, it is possible to produce an explicit example of a totally ordered set that cannot be embedded into $ (\mathbb{R},\leq_{\mathbb{R}}) $ in an order-preserving manner.

Define a total ordering $ \preceq $ on $ \mathbb{R}^{2} $ as follows: $$ \forall a,b,c,d \in \mathbb{R}: \quad (a,b) \prec (c,d) ~ \stackrel{\text{def}}{\iff} ~ (a <_{\mathbb{R}} c) ~~ \text{or} ~~ (a = c ~~ \text{and} ~~ b <_{\mathbb{R}} d). $$ Observe that $ \{ \{ r \} \times \mathbb{R} ~|~ r \in \mathbb{R} \} $ is an uncountable collection of pairwise-disjoint non-degenerate $ \preceq $-intervals of $ \mathbb{R}^{2} $. Hence, $ (\mathbb{R}^{2},\preceq) $ cannot be embedded into $ (\mathbb{R},\leq_{\mathbb{R}}) $ in an order-preserving manner; if this were not the case, then $ \mathbb{R} $ would contain uncountably many pairwise-disjoint non-degenerate intervals, so by picking a rational number from each of these intervals, we would end up with uncountably many rational numbers ⎯ contradiction.


Model-Theoretic Construction

There is a neat way to prove the existence of totally ordered sets with arbitrarily large cardinality. It relies on the Compactness Theorem in logic and model theory. Let $ \kappa $ be a cardinal and $ \mathcal{L} $ the first-order language consisting of

  • a set $ \mathcal{C} $ of $ \kappa $-many constant symbols and

  • a single binary relation symbol $ \leq $.

Next, define $ T $ to be the first-order $ \mathcal{L} $-theory consisting of:

  1. For distinct $ c,d \in \mathcal{C} $, the sentence $ \neg(c = d) $.

  2. The Axiom of Reflexivity: $ (\forall x)(x \leq x) $.

  3. The Axiom of Antisymmetry: $ (\forall x)(\forall y)(((x \leq y) \land (y \leq x)) \Longrightarrow (x = y)) $.

  4. The Axiom of Transitivity: $ (\forall x)(\forall y)(\forall z)(((x \leq y) \land (y \leq z)) \Longrightarrow (x \leq z)) $.

  5. The Total-Ordering Axiom: $ (\forall x)(\forall y)((x \leq y) \lor (y \leq x)) $.

Although $ T $ has infinitely many sentences (by (1)), it is easy to see that $ (\mathbb{N},\leq_{\mathbb{N}}) $ is a model of any finite number of these sentences. Therefore, by the Compactness Theorem, $ T $ has a model $ (\mathcal{M},\leq^{\mathcal{M}}) $. Clearly, if we choose $ \kappa > {\frak{c}} $, then we cannot embed $ (\mathcal{M},\leq^{\mathcal{M}}) $ into $ (\mathbb{R},\leq_{\mathbb{R}}) $ in an order-preserving manner.


Set-Theoretic Construction

The model-theoretic approach above suffers from a mild drawback, in the sense that the Compactness Theorem is equivalent to the Boolean Prime Ideal Theorem, which is a weak form of the Axiom of Choice. If one wishes to work strictly within the framework of the Zermelo-Fraenkel axioms, then one can use Hartogs’ result that for any set $ X $, it is possible to find an ordinal $ \alpha $ that cannot be mapped injectively into $ X $. In particular, there exists an ordinal $ \alpha $ that cannot be mapped injectively into $ \mathbb{R} $, much less embedded into $ \mathbb{R} $ in an order-preserving manner.

$\endgroup$
  • 1
    $\begingroup$ But $\mathbb{R} \times \mathbb{R}$ is the same size as $\mathbb{R}$. I think the poster is looking for a set strictly larger than $\mathbb{R}$ (For instance if there existed an ordering on $\mathcal{P}(\mathbb{R})$, that would be good.) $\endgroup$ – Andrew Maurer Dec 10 '12 at 10:07
  • $\begingroup$ An ordering on $ \mathcal{P}(\mathbb{R}) $ requires some form of the Axiom of Choice (AC). I wanted to avoid using AC when providing an answer. However, as Qiaochu has mentioned, Hartog's Theorem gives us a way of producing an ordinal that does not inject into a given set. For example, by Hartog's Theorem, there exists an ordinal $ \alpha $ that does not inject into $ \mathbb{R} $, much less inject into $ \mathbb{R} $ in an order-preserving manner. $\endgroup$ – Haskell Curry Dec 10 '12 at 17:30
  • $\begingroup$ The great thing about Hartog's Theorem is that it is a theorem of ZF. Naturally, as Hartog's Theorem is about well orderings, it is a harder result. My example only deals with total orderings, so it is simple to construct. It is clear that my example is not a well-ordered set. $\endgroup$ – Haskell Curry Dec 10 '12 at 17:34
  • $\begingroup$ The point of my construction is that one does not have to resort to larger cardinalities in order to exhibit a counterexample. $\endgroup$ – Haskell Curry Dec 10 '12 at 17:57
  • 1
    $\begingroup$ Let me just add that there are certain models of set theory without choice where the reals are maximal in a sense: Define $\mathbb R/E_0$ as the set of equivalence classes of the relation that identifies two reals iff their difference is in $\mathbb Q$. In natural models of the axiom of determinacy, the size of $\mathbb R/E_0$ is a successor of the size of $\mathbb R$: It is strictly larger, and there are no intermediate sizes. This set is not linearly orderable and, if a set $X$ is not linearly orderable, then $\mathbb R/E_0$ can be injected into $X$. $\endgroup$ – Andrés E. Caicedo Feb 10 '13 at 3:48
8
$\begingroup$

No, absolutely not. Assuming the axiom of choice, let $\kappa$ be any cardinal greater than $2^\omega=|\Bbb R|$; then $\kappa$ in its natural order is a linear order of greater cardinality than $\Bbb R$. If the axiom of choice fails in such a way that $\Bbb R$ cannot be well-ordered, there is still a well-ordered set that cannot be embedded in $\Bbb R$, the Hartogs ordinal of $\Bbb R$.

$\endgroup$
  • 3
    $\begingroup$ Actually, no uncountable ordinal can be embedded in $\mathbb{R}$. I give the argument in my answer. $\endgroup$ – Michael Greinecker Dec 10 '12 at 7:20
  • 2
    $\begingroup$ @Michael: I know; after all, $\Bbb R$ is ccc, hereditarily separable, etc. I was deliberately concentrating on the cardinality aspect. $\endgroup$ – Brian M. Scott Dec 10 '12 at 7:22
6
$\begingroup$

The real line is the largest order separable linearly ordered set. That is, if $(L,\preceq)$ is a linearly ordered set such that a countable set $C\subseteq L$ exists satisfying that for all $x,y\in L$ with $x\prec y$ there is $c\in C$ with $x\preceq c\preceq y$, then there exists a function $f:L\to\mathbb{R}$ such that $f(x)<f(y)$ iff $x<y$ for all $x$ and $y$ in $L$. The existence of such a set $C$ is also necessary. A proof of these facts is given here.

Here is yet another counterexample without order separability: Let $(W,\preceq)$ be an uncountable well-ordered set. Let $W'$ be $W$ without the maximum of $W$ if such a maximum exists. For each $w\in W'$, let $S(w)$ be its immediate sucessor given by $S(w)=\min\{w'\in W:w'\succ w\}$. It is easily seen that $x\prec y$ implies $x\prec S(x)\preceq y\prec S(y)$. So if a strictly increasing function $f:W\to\mathbb{R}$ would exist, the uncountable family of intervals $\{(f(w),f(S(w))):w\in W'\}$ would be disjoint, which cannot be for the same reason pointed out by Haskel Curry in his answer.

$\endgroup$
  • $\begingroup$ I think you mean: the uncountable family of intervals $\{(f(w), f(S(x))) : w\in W'\}$. $\endgroup$ – Anguepa May 26 at 19:55
  • $\begingroup$ @Anguepa That family of intervals is clearly exactly disjoint when the given family of order intervals is disjoint. $\endgroup$ – Michael Greinecker May 26 at 19:59
  • $\begingroup$ I must insist, I think you mean $\{(f(w),f(S(w))) : w\in W'\}$ is place of $\{(w,S(w)): w\in W'\}$. The intervals $(w, S(w))$ are empty. $\endgroup$ – Anguepa May 26 at 20:15
  • $\begingroup$ @Anguepa You are right. I'll edit it. $\endgroup$ – Michael Greinecker May 26 at 20:19
3
$\begingroup$

EDIT: this may be order isomorphic to the reals, but not as a field, as it is not Archimedean.

As an elementary example, the rational functions $\mathbb R(x)$ are an ordered field. The quotient $p(x) / q(x),$ with leading terms $p_m x^m$ and $q_n x^n,$ is called positive if $p_m / q_n$ is positive. Comparison of two rational functions is given by taking the difference and checking the sign as above. So, for example, $1/x$ is positive but is smaller than any positive real number, as with positive $A$ we find $$ A - \frac{1}{x} = \frac{Ax-1}{x}. $$

$\endgroup$
  • $\begingroup$ Regarding your EDIT: Your construction is not order-isomorphic to the reals because $\{(p-1/x,p+1/x):p\in\Bbb R\}$ is an uncountable set of pairwise-disjoint nontrivial intervals, so as in Haskell Curry's answer you get an uncountable set of rational numbers in these sets. $\endgroup$ – Mario Carneiro Jul 9 '14 at 16:22
3
$\begingroup$

Some linearly ordered sets are not isomorphic to any subset of the reals even though there are not more of them than there are reals. The set of all countable ordinals is an example.

$\endgroup$
2
$\begingroup$

No, in fact it's a famous result that ANY set can be totally ordered--this is known as the Well-Ordering Theorem and is equivalent to the Axiom of Choice.

For more information, see here.

$\endgroup$
  • 3
    $\begingroup$ You do not need the well-ordering theorem to exhibit arbitrarily large total orders. See en.wikipedia.org/wiki/Hartogs_number . $\endgroup$ – Qiaochu Yuan Dec 10 '12 at 4:16
  • $\begingroup$ He's not saying arbitrarily large numbers - he's saying any set. $\endgroup$ – Andrew Maurer Dec 10 '12 at 10:10
  • $\begingroup$ The well-ordering theorem (equivalent to AC) is strictly stronger than the Ordering Principle (that every set admits a total order). The Ordering Principle can be proved from the Ultrafilter Lemma, which is weaker than AC. (nice answer at math.stackexchange.com/a/211621/62940.) $\endgroup$ – Owen Barrett Nov 6 '15 at 23:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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