MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let us assume ZFC and let Q be the set of rational numbers ordered according to size. There is a well known theorem which implies that if S is any totally ordered countable set containing a subset ordinally similar to Q, then S contains well ordered subsets having arbitrarily large countable ordinal numbers. Is there a converse to this theorem which implies that if S has the second of these properties, then it has the first? I have been unable to find any mention of such a converse theorem or to come up with any obvious counter-examples. (I apologize if my question is not considered appropriate for "")

share|cite|improve this question
up vote 12 down vote accepted

If a linear order doesn't contain a copy of $\mathbb Q$, then, by a theorem of Hausdorff, it can be obtained by a transfinite sequence of steps, starting with singletons, and at each step forming well-ordered or reverse-well-ordered sums of previously constructed orderings. If the final result is to be a countable set, then the transfinite sequence will be only countably long, and each of the well-ordered or reverse-well-ordered index sets used along the way will also be countable. I believe this will allow a proof, by induction along the transfinite sequence, that at no stage does it become possible to embed arbitrarily large countable ordinals. Unfortunately, I don't have time to work out the details right now. I'll come back to it later if no one else does it first.

share|cite|improve this answer
Linear orders that do not contain a copy of $\Bbb{Q}$ are known in the literature as scattered; the Hausdorff theorem on scattered orders mentioned in the nice solution by Andreas Blass can be found in Rosenstein's text on Linear Orders (among other places). Indeed, Exercise 5.19.2 of Rosenstein's text is precisely what Blass shows in his outline. It is also worth pointing out that Hausdorff's result from 1908 was re-discovered in a 1962-paper of Erdős and Hajnal. – Ali Enayat Jan 16 '13 at 2:52

The converse is a theorem of Đ. Kurepa in:

Sur les ensembles ordonnés dénombrables, Hrvatsko Prirodoslovno Društvo. Glasnik Mat.-Fiz. Astr. Ser. II. 3, (1948). 145–151.

share|cite|improve this answer
I could not get access to a computer until now to reply to your responses. Many thanks to all of you for explaining so clearly how my question can be answered. Ali, I knew about scattered sets from topology but did not realize that the concept could be applied to arbitrary countable total orderings with no mention of topology. Furthermore, the proposition that an ordering of the set of non-negative integers is scattered can be expressed by a sentence of first order arithmetic-whereas well-ordering is a second order concept which cannot be expressed in this language. – Garabed Gulbenkian Jan 21 '13 at 18:54
If X is any total and scattered ordering of the set N of all non-negative integers, let Su(X) denote the smallest ordinal number that is not the ordinal number of a well-ordered subset of X. Suppose that T is a formalized mathematical theory. Consider all the formulae of T containing two free variables which can be proved in T to represent a total scattered ordering X of the set N. If W(T) is the least upper bound of Su(X) for all such X, I wonder if W(T) is the proof theoretical ordinal number of T. – Garabed Gulbenkian Jan 21 '13 at 19:58
Sorry. This is all wrong. I thought I had a definition for a countable ordering being "scattered" which could be expressed in a first order language, but I found a counter-example which shows that my definition does not work. It seems as if being "scattered" is just as much of a second order concept as being "well ordered". I was hoping to use my mistaken idea to come up with an easily understandable definition of the so-called "proof theoretical" ordinal numbers. How embarrassing. – Garabed Gulbenkian Jan 24 '13 at 20:27

Your Answer


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.