4
$\begingroup$

Many mathematicians outside mathematical logic dislike wellorderings, ordinals and corresponding transfinite arguments. They use zorn's lemma instead and claim one does not need ordinals at all. Examples are

  • Every vector space has a basis
  • Every filter can be extended to an ultrafilter
  • Hahn-Banach theorem

However many cases are not that easy. I often have difficulties to convert a simple proof that uses ordinals and transfinite induction into one using zorn's lemma instead. For example, how would one proove the following assertions with zorn's lemma?

  1. $\mathbb{R}^3$ is the union of pairwise disjoint unit-circles.
  2. There is a set of reals of the cardinality of the continuum that has no perfect subset.
  3. There is a non-determined set of reals.
$\endgroup$
  • 4
    $\begingroup$ They do? Who are these mathematicians? $\endgroup$ – Chris Eagle Mar 1 '13 at 20:28
  • $\begingroup$ Not sure why you'd have to choose, due to equivalence. I have a very vague memory that someone told me that you could do most of commutative algebra without choice by altering definitions to not reference maximal elements when you need them, but rather reference chains, thus essentially "bypassing" Zorn in some ways. But that was 20+ years ago, and even then I was only told such an idea existed. $\endgroup$ – Thomas Andrews Mar 1 '13 at 20:34
  • $\begingroup$ @Thomas: The other way around. The equivalence between "every increasing chain is finite" to "every non-empty collection of ideals has a maximal element" requires some choice; but without choice it would be smarter to work with the definition guaranteeing the maximal element, rather the one with the chains. $\endgroup$ – Asaf Karagila Mar 1 '13 at 20:38
  • 1
    $\begingroup$ If they are completely uninterested in logic and set theory, why would they care about these theorems? If they are interested, why would they have trouble with well-orderings? $\endgroup$ – Thomas Andrews Mar 1 '13 at 20:55
  • 1
    $\begingroup$ @user64573: I would prove the well-ordering principle and deduce the wanted corollaries. But the point is that it is possible. It might be the case that there is even a very short and amazing proof for these facts using this choice equivalent. But It makes no sense to do so; similarly some things are better suited for Zorn's lemma and others are not as well suited for it. $\endgroup$ – Asaf Karagila Mar 1 '13 at 20:59
3
$\begingroup$

Every proof with transfinite induction on a well-ordering can be essentially translated into a proof by Zorn's lemma. However this is an issue of simplicity. One can write a very long and difficult proof that a injective polynomial map from $\Bbb C^n\to\Bbb C^n$ is surjective, or one can use the correct tools from model theory and prove this quickly.

Sometimes things are easier to prove by well-ordering a set and going by induction, and sometimes things are easier to do with Zorn's lemma. Sometimes things are difficult in either case, and sometimes they are easy in either case. The idea is to identify the needed property for the proof and use the most suitable choice principle for that.

Equally you don't see people prove that there is a Bernstein set using the fact that every vector space has a Hamel basis; or using Tychonoff's theorem.

$\endgroup$
  • $\begingroup$ The result is that an injective polynomial map is surjective. Your version is obviously wrong. $\endgroup$ – Chris Eagle Mar 1 '13 at 20:38
  • $\begingroup$ @Chris: Thanks. $\endgroup$ – Asaf Karagila Mar 1 '13 at 20:39
  • $\begingroup$ I don't know of any example where using zorn's lemma would be essentially easier than using wellordering. However i can't think of a remotely comprehensible proof using zorn for one of the three cases i mentioned. $\endgroup$ – user64573 Mar 1 '13 at 20:53
  • $\begingroup$ @user64573: Hausdorff's Maximality Principle; Kurepa's Maximal Antichain Principle. $\endgroup$ – Asaf Karagila Mar 1 '13 at 20:55
  • $\begingroup$ @Asaf: Very easy. Enumerate the set, proceed by induction, add elements to your (anti-)chain als long as possible. It's just as easy and essentially the same argument as the zorn version. This seems to be true of any example of proof by zorn i know of. But not the other way round. $\endgroup$ – user64573 Mar 1 '13 at 21:02
1
$\begingroup$

I think of Zorn's Lemma as a tool for efficiently presenting certain proofs whose intuitive content consists of transfinite induction. (I think people like Zorn and Kuratowski would have agreed with this.)

In more detail: The natural (for me) proofs of all six of the theorems you quoted are proofs by transfinite induction, and I believe these are the proofs people would have given in the early days of set theory. It turned out that many such proofs (like the first three of your six) used transfinite induction in the same way, and a very simple way. Rather than repeating that simple argument over and over, people abstracted it as Zorn's Lemma, a lemma that can simply be quoted every time that particular argument is needed.

A side benefit was that, for these simple arguments, people no longer needed to learn about well-orderings and transfinite induction.

But, as you observed, Zorn's Lemma abstracts only some, not all uses of transfinite induction. In principle, any application of the axiom of choice could be based on Zorn's Lemma, since Zorn's Lemma implies the axiom of choice. But that's "in principle"; it would just make the natural proof longer by prepending a proof of AC from Zorn. It's entirely contrary to the purpose of Zorn's Lemma, which is to simplify certain proofs, not to make proofs longer and harder.

In your last three examples, the usual proof uses transfinite induction in a way that's different from (and a bit more complicated than) the way that Zorn's Lemma is designed to abstract. So those proofs should be left in the form of transfinite inductions.

Even when a proof uses Zorn's Lemma, I tend to visualize it as a transfinite induction that just happened to be of the sort that Zorn's Lemma can efficiently abbreviate.

By the way, there is a version of Zorn's Lemma, which I've seen attributed to Kneser, that might be able to abbreviate more transfinite induction arguments. Instead of requiring upper bounds for all chains, Kneser's version requires them only for well-ordered chains. (If you're thinking, "Wait, that makes no difference, because every chain has a cofinal well-ordered subset," you're right about the existence of cofinal well-ordered subsets, but that fact depends on AC.)

Finally, I should point out, in connection with the last of your six examples, that, although the natural construction of an undetermined set of reals uses transfinite induction, there's an alternative proof that works nicely with just Zorn's Lemma: If $U$ is any nonprincipal ultrafilter on $\mathbb N$, then the following game is undetermined. The two players alternately "take" finite subsets of $\mathbb N$, subject to the constraint that any set they take must be disjoint from all the sets previously taken (by either player). The first player wins iff the unino of the sets he takes is in $U$.

$\endgroup$
  • $\begingroup$ When I was teaching set theory in Jerusalem I realized after explaining the students about the "usual use of Zorn's lemma" that the "right" choice-lemma is in fact Teichmüller–Tukey... $\endgroup$ – Asaf Karagila Jan 2 at 18:09
0
$\begingroup$

I remember using Zorn's lemma to prove that every vector space has a basis, and I remember my professor at the time giving us a warning that not all mathematicians entirely agree with Zorn's lemma. As to one of your questions, I believe this paper does use Zorn's lemma, though I have not read it fully: http://www.math.chalmers.se/~wastlund/partitions.ps .

I'm not really sure where you got 'many mathematicians' from. I was only aware that the stubborn few did not like it, and not the majority of the community.

$\endgroup$
  • 1
    $\begingroup$ This doesn't seem to have anything to do with the question at hand. We're talking about people who prefer Zorn to other forms of choice, not people who reject choice in all its variants. $\endgroup$ – Chris Eagle Mar 1 '13 at 20:40
  • $\begingroup$ @Chris he asked a question for an example of a proof that $\mathbb{R}^3$ is the union of disjoint circles without using AOC. $\endgroup$ – noobProgrammer Mar 1 '13 at 20:42
  • $\begingroup$ No, the OP asked for such a proof "with Zorn's lemma". $\endgroup$ – Chris Eagle Mar 1 '13 at 20:43
  • $\begingroup$ The proof linked seems to be using both well-orderings and Zorn's lemma. $\endgroup$ – Asaf Karagila Mar 1 '13 at 20:43
  • $\begingroup$ @AsafKaragila I'll edit my post accordingly, thanks. $\endgroup$ – noobProgrammer Mar 1 '13 at 20:44

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.