Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
No. There are arbitrarily large totally ordered sets. See en.wikipedia.org/wiki/Hartogs_number . –  Qiaochu Yuan Dec 10 '12 at 4:16
14  
Perhaps it was because OP's name is Voldemort, but I originally read Qiaochu's link as the "Hogwarts number." –  JavaMan Dec 10 '12 at 5:12
    
@JavaMan: Yours should be the comment of the day. I wish I could give you +50 for it. –  Haskell Curry Dec 10 '12 at 5:32
add comment

6 Answers

up vote 20 down vote accepted

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.

share|improve this answer
1  
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.) –  andybenji Dec 10 '12 at 10:07
    
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. –  Haskell Curry Dec 10 '12 at 17:30
    
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. –  Haskell Curry Dec 10 '12 at 17:34
    
The point of my construction is that one does not have to resort to larger cardinalities in order to exhibit a counterexample. –  Haskell Curry Dec 10 '12 at 17:57
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$. –  Andres Caicedo Feb 10 '13 at 3:48
add comment

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

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

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 $\{(w,S(w)):w\in W'\}$ would be disjoint, which cannot be for the same reason pointed out by Haskel Curry in his answer.

share|improve this answer
add comment

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.

share|improve this answer
3  
You do not need the well-ordering theorem to exhibit arbitrarily large total orders. See en.wikipedia.org/wiki/Hartogs_number . –  Qiaochu Yuan Dec 10 '12 at 4:16
    
He's not saying arbitrarily large numbers - he's saying any set. –  andybenji Dec 10 '12 at 10:10
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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.