MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

(Edit: The first formulation is wrong. See the second answer) Does every totally ordered set contain an unbounded countable subset. In other words: If S is a totally ordered set, can we find a (edit: at most) countable subset A, such that for every $s \in S$, there is a $a \in A, a\geq s$?

share|cite|improve this question
No. This is a homework problem. – Sam Nead Nov 26 '09 at 16:36
I agree, this is a homework problem: -1. – Alberto García-Raboso Nov 26 '09 at 17:06
I am baffled as to why people think this is a homework problem. It could be assigned in a set theory class, but it is a very natural question and the counter-examples are not elementary. I'll bow to peer pressure and not give an explicit construction, but the basic hint here is to read up on ordinal numbers. – David Speyer Nov 26 '09 at 17:47
It was not a homework problem, but it was inspired by a homework problem. The problem was: Show that if $K_1\supset K_2\supset \dots$ is a decreasing sequence of non-empty compact sets, the intersection $\cap_{i=1}^{\infty} K_i$ is non-empty. I was wondering if this could be generalized: Let $(K_i)_{i\in I}$ be a system of non-empty compact sets, such that for for all $i,j\in I: K_i\subset K_j \vee K_i\supset K_j$. Is the intersection $\cap_{i\in I} K_i$ non-empty? This is why thought of the problem, but I got interested in the problem for its own rights. – Sune Jakobsen Nov 26 '09 at 18:26
For the record, I remember inventing and thinking about this question when I was first learning set theory. My motivation went as follows: An equivalent formulation of Zorn's lemma is "In a nonempty poset where every totally ordered subset has an upper bound, there is a maximal element." At the time I found it hard to think about arbitrary totally ordered sets, so I wondered if I could replace this by "In a nonempty poset where every ascending sequence $(a_i)_{i \in Z}$ has an upper bound, there is a maximal element." – David Speyer Nov 27 '09 at 0:16
up vote 4 down vote accepted

There is a counterexample in the long line L. It is totally ordered and every sequence has a limit in L. see the following:

share|cite|improve this answer
As long as we are answering homework questions (grump!) a simpler counter-example is provided by the first uncountable ordinal. – Sam Nead Nov 26 '09 at 17:46
The fact that the long line is a counterexample is completely derivative on the fact that omega_1 (the first uncountable ordinal) is a counterexample. Thus, Sam Nead's answer in the comment here is far better. – Joel David Hamkins Dec 1 '09 at 17:05

Keyword: cofinality.

Added MUCH later: To be slightly more explicit, for any cardinal $\kappa$, the cofinality of the successor cardinal $\kappa^+$ is $\kappa^+$, so not only can we not in general find an unbounded (=cofinal) countable subset, there is no fixed cardinality $\kappa$ such that every totally ordered set has an unbounded subset of cardinality at most $\kappa$.

share|cite|improve this answer
care to explain? – thejoshwolfe Jun 7 at 20:20
@thejoshwolfe: The OP's question is equivalent to: "does every totally ordered set have countable cofinality?" So learning about cofinality -- say from the linked to article -- will answer the question. – Pete L. Clark Jun 7 at 21:46
i think you're supposed to actually answer the question in a stackexchange answer to a question. cofinality seems like it would be a cool concept to use to answer the question, but I can't figure out how it would work. For example, I had no idea the OP's question was equivalent to your sentence; I wouldn't have figured that out on my own without spending hours reading several interlinking wikipedia articles. – thejoshwolfe Jun 8 at 2:38
@thejoshwolfe: This answer is almost seven years old and in fact predates mathoverflow being part of the stackexchange system and predates the site math.SE. As it is an undergraduate level set theory question, if it were asked today it would probably be closed and/or migrated. The existence of totally ordered sets -- e.g. cardinals -- of uncountable cofinality is the answer to the question, and that is discussed in the article. If you have further questions, please feel free to ask on math.SE. – Pete L. Clark Jun 8 at 3:17

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.