2
$\begingroup$

I am trying to understand this proof of Zorn's lemma.

I think the notation is clear to me and I can follow the proof until the point where the author defines conforming subsets although I am not entirely sure if I get the part using the axiom of choice.

Now my questions are:

1) Why do we need the axiom of choice? Until now I have viewed the axiom of choice as "we can create a new set from other sets even if we have uncountably many sets". Now wikipedia states it somewhat differently, i.e. that the axiom of choice gurantess a choice function, but I can see this formalizes my intuition since if such a function exists then we can use this function to pick elements from each set in a collection of sets. However, I am not entirely sure why the argument in the proof of Zorn's lemma requires a choice function. Given the assumptions we know that every chain in $X$ has a strict upper bound, so what's the use of the axiom of choice now?

2) Why does the author define the conforming property for arbitrary subsets? In the definition he uses an initial segment $P(A,x)$, but in the notation part he defined an initial segment only for chains. It also makes sense to define it only for chains since if a subset does not have a total order, then some elements might simpy not be in $P(A,x)$ because there is no relation between $x$ and those other elements.

I am quiet new to such deep set theory arguments and only want to understand this since it is relevant for a lemma on extensions of solutions to ODEs.

Thanks for any help and suggestions!

$\endgroup$
  • $\begingroup$ We know that each chain has at least one strict upper bound, but perhaps it has many and there is no way to systematically describe a specific such bound (e.g., in general there will not be a minimal bound). Therefore, we have to make a choice among these bounds - not once, not twice, not countably often, but size-of-big-involved-sets many times $\endgroup$ – Hagen von Eitzen Feb 24 at 17:21
  • $\begingroup$ Thanks for your comment. So we need the axiom of choice to pick one strict upper bound from possibly uncountably many? I don't understand the particular meaning of "size-of-big-involved-sets many times". $\endgroup$ – DerivativesGuy Feb 24 at 17:23
  • $\begingroup$ @HagenvonEitzen A chain $C$ in $(X,\le)$ has definitely infinitely many strict upper bounds under the assumption that $X$ does not have a maximal element. Moreover, there is no procedure to select one of these. The only possibilty to do so would be if there always exists a least strict upper bound, but that cannot be derived from the given assumptions. $\endgroup$ – Paul Frost Feb 24 at 17:29
3
$\begingroup$

1) You know that for each chain in $X$ there exists an upper bound, but there might be infinitely many upper bounds for each chain, and there might be infinitely many chains. Humans don't really have experience of this: when did you last (consciously) make infinitely many decisions, each with infinitely many choices of outcome? The Axiom of Choice is precisely the assumption (taken to be self-evident) that this is always an allowable procedure in set-theoretical reasoning (no matter how "big" the "infinities" involved are). Saying "there exists a choice function such that..." is just a way of formalizing this notion.

2) Recall that a chain is a totally ordered subset. Condition (a) of being "conforming" is that the set $A$ is well ordered. In particular, note that well ordered implies totally ordered. So you are correct that a conforming set will always be a chain. The author just wrote things that way because they thought it would be easier to read than the alternative; restricting the definition to chains might seem weird to experienced readers, for two reasons:

  • the definition makes complete sense in the more general context that $A$ is an arbitrary subset of $X$; and
  • part of the definition means making another restriction to well ordered subsets anyway, so you don't gain anything by restricting the context at the outset.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your detailed answer. I think I got the point regarding the definition of conforming sets. I have one more question regarding the axiom of fhoice though. Do I interpret your answer correctly that the axiom of choice would even be necessary if we only had to pick a strict upper bound for one chain? This also involves a choice from infinitely many elements. Because I am pretty sure that there often arise situation where I have to chose an arbitrary element of an infinte collection, but so far in none of these cases I can remember the axiom of choice was mentioned. $\endgroup$ – DerivativesGuy Feb 24 at 17:39
  • $\begingroup$ If you only have finitely chains, then you can just say "let $x_{1},\ldots,x_{s}$ be [elements of the kind you want]" (provided you have proven existence). The problem comes when you want to talk about infinitely many things, each chosen arbitrarily, i.e., you don't have any systematic way of describing the choices you make. This means you don't have any sensible way to describe the choice function; your only way to attempt it would be to write down a table of inputs and outputs, which fails if the domain is infinite (especially if the domain is uncountable). $\endgroup$ – Will R Feb 24 at 18:12
  • $\begingroup$ Ok, I think I get it now. The problem is not that we have to choose from infinitely many elements but that we have to make infinitely many choices. Thanks. $\endgroup$ – DerivativesGuy Feb 24 at 18:30
  • $\begingroup$ @derivativesguy Yes, and more specifically, the fact that infinitely many of them are arbitrary (not specified by some rule you can describe such as "take the least element") essentially means that the other axioms of set theory - the other rules of the game, if you like - fail to provide you with a way to actually construct the choice function. Your only option is to assume that such a function exists, and that's exactly what AC says you can do. $\endgroup$ – Will R Feb 24 at 18:38
  • $\begingroup$ Great, thanks again for the clarification. So far I did not need to dive that deep into ZFC set theory since a naive approach suffices for real analysis and finite dimensional linear algebra. $\endgroup$ – DerivativesGuy Feb 24 at 18:44
2
$\begingroup$

Just because a chain has an upper bound, it does not mean it has exactly one upper bound, or even a canonically chosen upper bound. In fact, in the generic case, it won't have one.

So that means that we need to choose one. Well, fine, doing it once is easy. But when you need to choose them in succession, in a conforming way, then you already find yourself in a pickle after doing so for every natural number, as you've essentially had to make infinitely many arbitrary choices. And god forbid your partial order is even larger than that...

As for the definition of a conforming subset, note that by requiring the order induced by $\leq$ to be a well-ordering you've already required that the set is a chain since it is linearly ordered by $\leq$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer. Could you please elaborate on the part "choose them in succession in a conforming way". The proof does not mention anything about conforming sets before the definition of conforming sets and the author does not mention that the choices need to relate to each other. It is also clear that conformin sets must be relevant to show a contradiction, but I cannot see that yet. I will need more time to understand the rest of the proof. $\endgroup$ – DerivativesGuy Feb 25 at 18:51
  • 1
    $\begingroup$ @DerivativesGuy The result being proved here (which was well known long before this proof, of course) is that in the statement of Zorn's Lemma one can settle for "well ordered chains". But let me ask this, what do you think is going on in this proof? $\endgroup$ – Asaf Karagila Feb 25 at 18:58
  • $\begingroup$ As I've said I haven't worked through all the details yet, but the author chose a proof by contradiction. This first leads to the fact that we can find a strict upper bound for any chain. Then he proves that for a special type of chain, i.e. a conforming subset we can show that one must be an initial segment of the other. From this we then know that the union of all conforming subsets is also conforming since it is simply the largest one. After that point I am not sure what is going on anymore. I think I am also not 100% sure what the second property of conforming sets should tell me as well. $\endgroup$ – DerivativesGuy Feb 25 at 19:19
  • 1
    $\begingroup$ The second property tells you that every element is "the chosen upper bound" of the initial segment before it. In other words, that you've constructed this well-ordered chain in succession by applying the choice function for upper bound, starting from the empty set (which is a chain). $\endgroup$ – Asaf Karagila Feb 25 at 19:22
  • 1
    $\begingroup$ Yes, exactly. This is just a clever way of doing transfinite recursion without talking about ordinals. $\endgroup$ – Asaf Karagila Feb 25 at 19:35

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.