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 "mathoverflow.net")
$\begingroup$
$\endgroup$
asked Jan 15, 2013 at 18:37
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
answered Jan 15, 2013 at 19:02
-
4$\begingroup$ 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. $\endgroup$ Commented Jan 16, 2013 at 2:52
$\begingroup$
$\endgroup$
3
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.
answered Jan 15, 2013 at 20:09
-
$\begingroup$ 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. $\endgroup$ Commented Jan 21, 2013 at 18:54
-
$\begingroup$ 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. $\endgroup$ Commented Jan 21, 2013 at 19:58
-
$\begingroup$ 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. $\endgroup$ Commented Jan 24, 2013 at 20:27