(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$?
$\begingroup$
$\endgroup$
12
asked Nov 26, 2009 at 16:31
-
1$\begingroup$ No. This is a homework problem. $\endgroup$– Sam NeadCommented Nov 26, 2009 at 16:36
-
1$\begingroup$ I agree, this is a homework problem: -1. $\endgroup$– Alicia Garcia-RabosoCommented Nov 26, 2009 at 17:06
-
3$\begingroup$ 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. $\endgroup$– David E SpeyerCommented Nov 26, 2009 at 17:47
-
3$\begingroup$ 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. $\endgroup$– Sune JakobsenCommented Nov 26, 2009 at 18:26
-
2$\begingroup$ 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." $\endgroup$– David E SpeyerCommented Nov 27, 2009 at 0:16
|
Show 7 more comments
2 Answers
$\begingroup$
$\endgroup$
2
There is a counterexample in the long line L. It is totally ordered and every sequence has a limit in L. see the following:
answered Nov 26, 2009 at 17:13
-
7$\begingroup$ As long as we are answering homework questions (grump!) a simpler counter-example is provided by the first uncountable ordinal. $\endgroup$– Sam NeadCommented Nov 26, 2009 at 17:46
-
1$\begingroup$ 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. $\endgroup$ Commented Dec 1, 2009 at 17:05
$\begingroup$
$\endgroup$
4
Keyword: cofinality.
http://en.wikipedia.org/wiki/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$.
answered Nov 27, 2009 at 16:37
-
-
$\begingroup$ @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. $\endgroup$ Commented Jun 7, 2016 at 21:46
-
$\begingroup$ i think you're supposed to actually answer the question in a stackexchange answer to a question. meta.stackexchange.com/a/8259/206371 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. $\endgroup$ Commented Jun 8, 2016 at 2:38
-
1$\begingroup$ @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. $\endgroup$ Commented Jun 8, 2016 at 3:17