0
$\begingroup$

This is based on this question: How strong is the axiom of well-ordered choice?

The "axiom of well-ordered choice" says that any transfinitely-indexed family of sets has a choice function. The individual sets within the family need not be well-ordered, but the family must be. We also assume the family is set-sized, so that the indices only go up to some ordinal.

I was going to give a direct example of where I'm stuck with Zorn's lemma, but it seems like it's easier to go with the Well-Ordering Principle (which indirectly uses Zorn's lemma anyway).

The usual proof sketch is, you begin with some set $S$ and select an initial element $e_0$. Then, via transfinite recursion you select an element $e_\alpha$ for any ordinal $\alpha$ from the set $S \setminus \{e_n: n < \alpha\}$. This process must "run out" of elements to select at some point, or else $S$ would have as many elements as ordinals, which it can't because it's a set. The resulting sequence of $e_n$'s is a well-ordering on $S$.

Of course, one cannot simply "select" elements from this family of sets without something like the axiom of choice. With AC, we can define a choice function on the power set $P(S) \setminus \{\}$, so that we know that we are always able to choose an element. This can be thought of as a choice function on a "partially ordered family of sets."

However, we don't really need a choice function on all of $P(S) \setminus \{\}$ for this. We only need a choice function on a particular transfinitely-indexed family of subsets of $S$ - each of which contains one less element than the last, or is equal to the intersection of all previous subsets at a limit ordinal. So rather than a partially ordered family of sets, we get a well-ordered family of sets. Since this is transfinitely-indexed, why can't we use the "well-ordered AC" here?

The same basic question applies to Zorn's lemma above, although I thought the above example was clearer. You begin with an initial element in some poset which has upper bounds for every chain, then transfinitely choose a sequence of larger elements until you run out. This is typically formalized by mapping a chain to the set of its larger elements, and then using AC to create a choice function selecting exactly one larger element from each set. This is equivalent to using AC on a partially ordered family of sets, however we only need to use it on one particular chain, which is a well-ordered family of sets. Why can't we use the well-ordered AC here?

Basically, why isn't the well-ordered AC equivalent to the usual AC?

$\endgroup$
  • 1
    $\begingroup$ Well. Not every set can be well-ordered. $\endgroup$ – Asaf Karagila Mar 9 at 19:46
3
$\begingroup$

You can indeed reduce AC to "AC for well-ordered processes" - however, AWC is "AC for well-ordered index sets," which is quite a different (and weaker) thing.

To see the difference, let's follow your idea for a two-element set $X=\{a,b\}$. Our first "stage" is: pick an element $e_0$ from the set $X$. Our second stage is: pick an element $e_1$ from the set $X\setminus\{e_1\}$.

On the face of it this may seem like we've used the (trivial) axiom of choice for two sets. However, we haven't really done that, since our second set depended on our first choice. For AWC you need to set forth ahead of time a well-ordered set of choices you want to make. But you need a bit more than that to prove WOP: basically, you need "well-ordered dependent choice" rather than simply well-ordered choice. And the problem is that while the set of "stages" in your construction is well-orderable, the set of sets you might need to choose from isn't (at least, a priori), and so mere AWC won't help you here.

Incidentally, note that DC - which is basically "dependent choice for $\omega$-many stages" - is indeed strictly stronger than the axiom of countable choice, which is the "index-set-instead-of-stages" version. So there's a pattern here.

$\endgroup$
  • $\begingroup$ Aha! Ok, so "well-ordered dependent choice" is equivalent to AC, but this is weaker. Thank you! $\endgroup$ – Mike Battaglia Mar 10 at 2:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.