Suppose I have a set along with a relation which is a total order. The set has no minimum element. Now, I want to create an infinite decreasing sequence of elements in this set. For this I have to use axiom of choice. But I'm not able to figure from which family of sets should I pick the elements so that I can use AoC.
Using Axiom of Choice To Find Decreasing Sequences in Linear Orders
3 Answers
For each $x\in X$, let $L_x = \{y\in X \mid y\lt x\}$. Take the family $\{L_x\}_{x\in X}$. Let $f$ be an element of $\prod_{x\in X}L_x$.
Now pick $x_1\in X$. Use the recursion theorem to define a function $g\colon\mathbb{N}\to X$ by letting $g(1) = x_1$, and letting $g(n+1) = f(g(n))\in L_{g(n)}$. The sequence you want is $x_i=g(i)$.
In fact, you don't need all of AC to do the above, it suffices to use the Axiom of Dependent Choice which is implied by, but is not equivalent to, the full Axiom of Choice. Showing that you actually need ADC for the general result (as opposed to showing that it suffices to use it) requires arguments along the lines of Asaf's answer.
-
1[Two downvotes](http://math.stackexchange.com/questions/67627/do-morphisms-of-binary-operations-have-to-be-morphism-of-units/67676#67676), within a minute of each other, neither with an explanation. Someone's voting with their liver... – 2011-09-26
-
0Maybe today is the day of sudden downvotes? http://math.stackexchange.com/questions/67397/distribution-after-hitting – 2011-09-26
-
0@Gortaur: If it is the same individual, it should be caught by the system as an anomaly (if he does it enough times...) – 2011-09-26
-
2Arturo: I believe that DC is *more* than needed for the existence of such sequence. Axiom of countable choice seems more than enough too. I will have to check "The Bible" for more information. – 2011-09-26
-
0@Asaf, interesting point. I've started two comments now that were supposed to prove that countable choice is not enough, but I found bugs in both at the last moment. Please share your findings if you find anything definite. – 2011-09-26
-
0@AsafKaragila: The only difference I see between the statement here and the Axiom of Dependent Choice is that in DC you only require the relation to satisfy "for every $x$ there exists $y$ such that $xRy$", while here we have a total relation. That difference may, indeed, be enough to require only a *fragment* of DC, of course. – 2011-09-26
-
0@Henning: Please see my answer for that. It seems to me that only Dedekind-finite sets can be counterexamples to such theorem (existence of decreasing sequences), and their existence is exactly equivalent to $\lnot W_{\aleph_0}$ (the latter defined in my answer as well) – 2011-09-26
-
0@Arturo: It is unusual to fragmentize DC, although I am certain that you could. However your relation is not actually the total order but rather the chains ordered by extension. Regardless, I would think that a countable subset which is linearly ordered has a cofinal $\omega$-sequence or inverse $\omega$-sequence to the least. – 2011-09-26
-
0@Arturo: It seems that your guess was quite correct. Fragmenting DC is the exact choice strength needed. – 2011-09-27
-
0@Asaf: Interesting indeed. Thanks! – 2011-09-27
Consider all the ordinals which can be embedded into the order inversely, that is order type forming decreasing chains in the linear order.
Let $\alpha$ be the supremum of all ordinals. If $\alpha<\omega$ then there is a minimal element; if $\alpha>\omega$ then we can inversely-embed $\omega$ and have the chain.
If $\alpha=\omega$, then we can use Zorn's lemma as follows:
Take all the decreasing chains ordered by extension. Every chain is bounded since the union of such chain gives a decreasing sequence. Therefore there exists a maximal element. Since we know that a finite chain can be extended by another element (otherwise a minimal element exists) the maximal element has an infinite length.
As Arturo remarked this can be done with Axiom of Dependent Choice, which is a restricted version of Zorn's lemma for partial orders whose height is $\omega$.
To see that the axiom of choice is needed, take the Basic Cohen model, that is add a Dedekind-finite set of reals. This set is totally ordered, it is unbounded and it has no countable subset. In particular we cannot find a countable sequence in this totally ordered set.
The exact choice strength is actually the one suggested by Arturo in the comments as a fragment of the Principle of Dependent Choice.
Let $\operatorname{DC}_{\operatorname{lin}}$ be the assertion that every linear ordering in which every finite chain can be extended has an increasing $\omega$-sequence.
Clearly, $\operatorname{DC}\Rightarrow\operatorname{DC}_{\operatorname{lin}}$, as $\operatorname{DC}$ speaks on non-linear orders as well.
First note that this is obvious that $\operatorname{DC}_{\operatorname{lin}}$ implies that an ordering which is not bounded from below has a decreasing $\omega$-sequence. Inverse the order, as every finite (increasing) sequence can be extended (otherwise we hit a maximum) we have an $\omega$-sequence; inverse the order again and there we have it.
On the other hand, if $\operatorname{DC}_{\operatorname{lin}}$ does not hold then there is a linear order such that every finite increasing sequence can be extended but there is no $\omega$-sequence. In particular the inverse of such order will be a linear ordering with no least element, that has no decreasing $\omega$-sequence.
Question I: Suppose ZF+Exist an amorphous set. Since amorphous sets cannot be linearly ordered they cannot be used as counterexamples of $\operatorname{DC}_{\operatorname{lin}}$.
Can there be a model of ZF+Exists an amorphous set+$\operatorname{DC}_{\operatorname{lin}}$? Can we relax the requirement of amorphous to an infinite Dedekind-finite set?
Question II: Can we have a model of ZF+$\operatorname{DC}{\operatorname{lin}}$+$\lnot\operatorname{AC}\omega$?
That is a model in which ZF holds, $\operatorname{DC}_{\operatorname{lin}}$ holds but there is a countable family of sets without a choice function.
-
0Not sure which part of this is supposed to do it with only countable choice. For "if x is linearly ordered and infinite, take a countable subset of it", how can you be sure that the countable subset you take still has no minimum element? (For example, what if the original set were $\mathbb R$ and the countable subset your axiom gives you happens to be $\mathbb N$?) – 2011-09-26
-
0@Henning: I have to think about it. While the argument itself is good, my intuition tells me it is not true, and if there is a countable subset and no minimal element then we can find one which is decreasing. – 2011-09-26
-
0@Henning: This is a brain teaser, no doubt. Luckily, I am quite free for the next few days and might have some time to sit and think it through. Watch updates as they come! – 2011-09-26
-
0Before falling asleep five hours ago I started coming up with a possible idea. – 2011-09-27
-
0Funny, it was staring at me right in the fact. – 2011-09-27
-
0Is it clear that "has a countable chain" implies "has an infinite increasing sequence"? Consider the set of negative integers with the usual order. It has a chain (namely, the entire set) which is countably infinite, but there is no infinite increasing sequence. (Assuming that, as usual, a "chain" is any totally ordered subset, and a "countable" chain is a chain with cardinality $\aleph_0$). – 2011-09-27
-
0@Henning: Every increasing chain of negative integers is finite, and not every finite chain of negative integers can be extended. For example $\langle -1\rangle$. – 2011-09-27
-
0The [chain](http://en.wikipedia.org/wiki/Total_order#Chains) $\{-1\}$ can be extended with a new element $-2$ to produce the chain $\{-1,-2\}$. (Note that, in the usual terminology, chains are subsets of the poset, not indexed sequences). – 2011-09-27
-
0@Henning: The requirement in Dependent Choice is a function from $n$ into $X$ such that $f(k)
$\langle -1\rangle$ cannot be extended to an increasing sequence strictly longer, within the confines of the negative integers! :-) – 2011-09-27 -
0Okay, but then it seems to be you've just paraphrased the original problem, haven't you? Both are quite slight variations in wording of "The Principle of Dependent Choice holds when the relation is additionally assumed to be a total order". – 2011-09-27
-
0@Henning: I don't see how this is a rephrase of the problem. The exact choice-strength needed is Dependent Choice for Total Orders. Whether or not this is compatible with other, more familiar choice principles remains open; and I would believe that it is open. Given that every cardinality is comparable with either an ordinal or an amorphous cardinal should yield consistency with this restriction; but not even with $W_{\aleph_0}$ I mentioned in previous versions of this question. My question whether or not we can describe the exact amount of choice. It is a legitimate answer, I'd think. – 2011-09-27
-
0Of course "just a rephrasing" is fuzzy enough that reasonable people can agree to disagree about it, but wasn't it clear from the beginning that the question asked is exactly dependent choice for total orders (which very minor variations in wording such as $<$ versus $>$)? I thought the problem at hand was to find a _more_ well-known equivalent to dependent-choice-for-a-total-order. Declaring it to be exactly equivalent to itself is of course _true_, but not terribly enlightening. – 2011-09-27
-
0@Henning: I was actually thinking that this would be equivalent to some fine tuning of countable choice or so. However the more I think about it seems reasonable that this is compatible with statements contradicting even weaker statements than ACC. For me this is indeed an answer. It seems we had different questions in mind. – 2011-09-27
If you want to apply the axiom of choice directly, pay careful attention to what you're choosing:
- First, you choose an element $x_0 \in X$
- Second, you chose an element $x_1 \in \{ a \in X \mid a < x_0 \}$
Pay close attention to the second point -- we aren't really choosing an element from a set! Instead, we are choosing from a set-valued function of $x_0$, and so $x_1$ really should be a function of $x_0$!
Now how to apply choice is clear.
- First, you choose $x_0 \in x$
- Second, you choose $f_1$ from the subset $S_1$ of functions $X \to X$ satisfying $f(a) < a$
- Third, you choose $f_2$ from the subset $S_2$ of functions $X \times S_1 \to X$ satisfying $g(a,f) < a$ and $g(a,f) < f(a)$
- ...
But to make things easier on ourselves, I will simplify:
- First, you choose $x_0 \in X$
- Second, you choose $f_1 : X \to X$ satisfying $f(a) < a$
- Third, you choose $f_2 : X^2 \to X$ satisfying $f(a,b) < a$ and $f(a,b) < b$
- ...
Now, each of our sets is completely determined. We can show they are non-empty (by invoking induction and choice), and so we can apply choice to the collection.
Finally, our sequence is:
- $x_0$
- $x_1 = f_1(x_0)$
- $x_2 = f_2(x_0, x_1)$
- ...
EDIT: just to make it explicit, the simplified version defines the sets $S_n$ to be the set of functions $g : X^n \to X$ satisfying $g(\vec{x}) < x_i$ for all $1 \leq i \leq n$.
(Depending on your tastes, you may want to special case $S_0 = X$)
For a choice $g \in S_n$, the value $g(\vec{x})$ is meant to be interpreted as "the choice I would make at at time $n$ if I had previously made the choices $x_0, x_1, \ldots, x_{n-1}$ at times $0, 1, \ldots, n-1$".
Now apply the axiom of choice to get a family of choices $f_n \in S_n$. Under the intended interpretation, our chosen decreasing sequence is
$$x_n = f_n(x_0, x_1, \ldots, x_{n-1})$$
(If you're special casing $0$, then $x_0 = f_0$ instead)
Of course, while this approach is systematic, it did not lead to the simplest result. At some point we might have recognized that our choice at time $n$ could be made to depend only on the choice made at time $n-1$ rather than the entire family of choices made at times $0$ through $n-1$. And if we do that, we might have then realized a single choice would work for all positive times. This would result in Arturo's answer.
-
0How is this answer different from Arturo Magidin's answer? If you want to apply the Axiom of Choice directly, you have to come up with a family from which you choose elements. It seems to me that really you use the same family as Arturo and the same recursion to define the sequence, just in a slightly less explicit way. – 2011-09-27
-
0My intent was not just to answer the question posed, but to show a *thought process* that would lead to the answer. – 2011-09-27
-
1Yes, I understand that. But I think the difficulty in this argument is to get the actual choice function from your thought process. And Arturo very cleanly states for which family of set you choose elements. This is somewhat hidden in your answer. – 2011-09-29