Let $(P, \leq)$ be a total ordering (some of you prefer the name linear order). Can we find a subset $R\subseteq P$ which is well ordered (with respect to $\leq\upharpoonright R$) and cofinal in $P$, that is for each $p\in P$ there is $r\in R$ such that $p\leq r$?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
0
1
|
||||||
|
closed as too localized by Simon Thomas, Andres Caicedo, Emil Jeřábek, Henry Cohn, Ryan Budney Dec 6 2011 at 4:20 |
|
5
|
Yes, it is called the cofinality of the order. Just apply Zorn's lemma to the class of all well-ordered suborders of $P$, ordered by end-extension. If you've got a maximal such order, then it must be cofinal, since otherwise you could end-extend it. Note that Zorn's lemma applies, since the union of chain of end-extensions of well-orders is still a well-order. It would seem to be a weak choice principle to assert that every linear order has a cofinality, and I'm not sure exactly how this assertion relates to AC and its variations. Meanwhile, in the case of partial orders, we cannot necessarily find such a cofinal subset, even when the partial order is upward directed. For example, the collection of all finite subsets of an uncountable set, ordered by inclusion. There can be no linearly ordered cofinal subset, since every node in the order has only finitely many predecessors. |
|||||||||||||||||||
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
6
|
Assuming the axiom of choice, the answer is yes. Pick an element $x_0\in P$. If $x_0$ is not maximal then $\lbrace x\in P\mid x_0 < x\rbrace$ is nonempty. We can choose some $x_1$. Suppose for $\alpha<\beta$ we chose $x_\alpha$, and $\lbrace x_\alpha\mid\alpha<\beta\rbrace$ is well ordered by $\le$. If this set is cofinal, we are done. Otherwise, we can choose $x_\beta$ from $\lbrace x\in P\mid \forall \alpha<\beta: x_\alpha< x\rbrace$, since it is nonempty. The process has to terminate, otherwise we found an injection from a proper class into a set. Without the axiom of choice it is possible to have a linear order which has no well ordered cofinal set. For example if we add a Dedekind-finite set of reals, it is infinite linearly ordered and every well ordered subset is finite, hence bounded. |
||
|
|
|
2
|
Nice argumant. BTW Hausdorff's name must be mentioned, who proved a stronger form of the statement and who started the investigation of ordered sets in general. |
||||||
|
