23
$\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?

  • 0
    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.2015-07-01

6 Answers 6

25

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.

  • 1
    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$.2013-02-10
8

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

  • 2
    @Michael: I know; after all, $\Bbb R$ is ccc, hereditarily separable, etc. I was deliberately concentrating on the cardinality aspect.2012-12-10
6

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) iff $x 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.

3

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.

3

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}. $

  • 0
    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.2014-07-09
2

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.

  • 0
    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 http://math.stackexchange.com/a/211621/62940.)2015-11-06