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$?
$\begingroup$
$\endgroup$
2
-
4$\begingroup$ This question is far from research level, and would have fit just as well on math.stackexchange.com in my opinion. $\endgroup$– Asaf Karagila ♦Commented Dec 4, 2011 at 19:49
-
1$\begingroup$ In support of Asaf's assertion that this is below research level: This is an exercise from Halmos (Naive Set Theory, page 68). $\endgroup$– Nathan ReadingCommented Mar 28, 2014 at 18:11
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
7
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.
answered Dec 4, 2011 at 19:41
-
$\begingroup$ The assertions that every linearly ordered set has a cofinal well ordered subset, along with the order extension principle (every poset can be extended into a linear order) imply the axiom of choice. Each does not imply the other, though. $\endgroup$– Asaf Karagila ♦Commented Dec 4, 2011 at 19:48
-
$\begingroup$ Thanks, Asaf. So you are saying that it is a strictly weak choice principle, then? What are the models separating it from ZF and also from ZFC? $\endgroup$ Commented Dec 4, 2011 at 19:51
-
$\begingroup$ @Joel: I mentioned Cohen's basic model in my answer. The Dedekind-finite set of reals is linearly ordered but has no cofinal well-ordered subset. $\endgroup$– Asaf Karagila ♦Commented Dec 4, 2011 at 19:52
-
1$\begingroup$ Finding a somewhat newer reference, Paul Howard and Hartmut Höft show in projecteuclid.org/euclid.ndjfl/1040511347 some results regarding this principle, while in ZFA it is rather understood, there seem to me that some questions remain open regarding its provability in ZF. While no final word is said about whether or not CF implies AC or not; if they only conjecture that "Well orders have no decreasing chains" do not imply CF over ZF, then I'd assume they could not find a good reference for the fact that CF implies AC; nor they mention otherwise. $\endgroup$– Asaf Karagila ♦Commented Dec 4, 2011 at 23:09
-
2$\begingroup$ As a side remark, the fact that a general poset won't have cofinal linearly ordered subsets is one motivation for looking at filters (or ideals) on partial orders rather than linearly ordered subsets. For example, every maximal filter $F$ on a poset is cofinal in the sense that there is no element of the poset strictly below all elements of $F$. $\endgroup$ Commented Dec 5, 2011 at 13:19
$\begingroup$
$\endgroup$
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.
answered Dec 4, 2011 at 19:47
$\begingroup$
$\endgroup$
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.
answered Dec 5, 2011 at 13:45
-
$\begingroup$ Sorry, I meant this as a comment to Asaf's comment. $\endgroup$ Commented Dec 5, 2011 at 13:46
-
$\begingroup$ I believe you can delete your own answer. It should be to the right of the "edit" button there. Either way, thanks :-) $\endgroup$– Asaf Karagila ♦Commented Dec 5, 2011 at 15:18