cozilikethinking

4 out of 5 dentists recommend this WordPress.com site

Tag: Zorn’s lemma

Zorn’s lemma

This is another rant on Zorn’s lemma. And hopefully the final one. It is something that has puzzled me for more than a year now!

In a partially ordered set P, let every chain have an upper bound. Why is it not obvious that P has a maximal element?

The whole concept depends on the following construction: can we construct an ascending chain such that for every element a in the chain, if there is a greater element(s) in P, then we add one of those greater elements to the chain after a? For example, take P to be \Bbb{Z}, and construct the chain 1<2<3. We know that 4,5,6,7,\dots, all these elements are greater than 3. Hence, we can choose any of those greater elements and add it to the chain, we can form a bigger chain.

If we continue adding such greater elements to the chain until we cannot add anymore, then the greatest element 'm' is clearly the maximal element of the whole of P, and not just the chain. Because is m was not the maximal element, then we could add another element from P in front of M in the chain, contradicting the fact that we cannot add any other element to the chain.

Rephrasing the earlier question: if in a partially ordered set P every chain has an upper bound, can we prove the existence of a chain in which for every element in the chain if a greater element exists, one of those elements has been added to the chain? Other similar questions would be: can we prove the existence of a chain in which is isomorphic to \Bbb{Z}, or can we prove the existence of a chain which contains all numbers between 5 and 73? The point to be taken away from this is that proving the existence of such chains is not trivial or “obvious”.

Where does Zorn’s lemma come in? Zorn’s lemma allows us to make an infinite number of arbitrary decisions. For example, if we have infinite pairs of shoes, Zorn’s lemma would allow us to arbitrarily choose one shoe from each pair in that infinite set, without detailing which shoe we picked from each pair, or how we went about choosing the shoe. Making this more clear, picking the left (or right) shoe from each pair does not require Zorn’s lemma, as the choice made for each pair is explicitly clear. However, selecting any *random* show from each of the infinite pairs requires the use of Zorn’s lemma, as we’re making an infinite number of decisions without really giving details.

How is this relevant to proving the existence of the aforementioned chain? As we can make an infinite (possibly uncountable) number of arbitrary choices without detailing how, we can, for each element in the chain with a greater element in P, add one of those elements (this is the decision making part) to the chain, and continue doing so infinitely.

Note that for each element a in the chain, if the set of greater elements in P had a lowest greater element or something similar, we wouldn’t need Zorn’s lemma. We could just state “we choose the lowest greater element”. However, such a distinct element in the set of elements greater than a need not exist in every partially ordered set P. Hence we need Zorn’s lemma.

Note that Zorn’s lemma does not imply that this chain has an upper bound in P! However, if it does, as assumed in the statement of the lemma, then that will undoubtedly be a maximal element of P.

Peace.

The strange difference between “divergent sequences” in real analysis and abstract algebra

I have been working on Commutative Algebra. A lot of the initial proofs that I’ve come across use Zorn’s lemma. The statement of Zorn’s lemma is simple enough (which I have blogged about before):

Suppose a partially ordered set P has the property that every chain (i.e. totally ordered subset) has an upper bound in P. Then the set P contains at least one maximal element.

I came across the proof of the fact that every field has an algebraic closure, which also uses Zorn’s lemma. The argument was: continue adding field extensions infinitely. So the sequence that we have generated is something like F_1\leq F_2\leq \dots (ad infinitum). Now \bigcup_{i=1}^{\infty} F_i is also a field (or rather can be made into a field). Also, \bigcup_{i=1}^{\infty} F_i is the limit of the sequence. We then argue that as \bigcup_{i=1}^{\infty} F_i is the maximal element in the chain of nested fields, it is the algebraic closure (use Zorn’s lemma here).

An analogy in real analysis would be: take a divergent sequence. Can we say anything about its limit except for the fact that it is \infty (or -\infty)? There’s really not that much to say. Say we have two divergent sequences \{n\} and \{n^2\} for n\in\Bbb{N}. All we can say is \{n^2\} approaches \infty faster than \{n\}. Nothing else.

But here, we’ve taken something like a divergent sequence, and said something intelligent about it. This has to do with the fact that the limit of the divergent sequence is still a field, and satisfies all the axioms of a field, while the limit of a divergent sequence in real algebra does not act like a real number by any stretch of imagination. This is a rather strange fact, and should be noted for a full appreciation of the argument.

Also, we did not know right away that the limit of the sequence of field extensions would be a field. We had to make a minor argument that the limit is exactly the union of all fields in the sequence.

So ya.

Breaking down Zorn’s lemma

Today I’m going to talk about Zorn’s lemma. No. I’m not going to prove that it is equivalent ot the Axiom of Choice. All I’m going to do is talk about what it really is. Hopefully, I shal be able to create a visually rich picture so that you may be able to understand it well.

First, the statement.

“Suppose a partially ordered set P has the property that every chain (i.e. totally ordered subset) has an upper bound in P. Then the set P contains at least one maximal element.”

Imagine chains of elements. Like plants. These may be intersecting or not. Imagine a flat piece of land, and lots of plants growing out of it. These may grow straight, or may grow in a crooked fashion, intersecting. These plants are totally ordered chains of elements. Now as all such chains have a maximal elements, imagine being able to see the tops of each of these plants. Not three things: 1. Each tree may have multiple tops (or maximal elements). 2. There may be multiple points of intersection between any two trees. 3. Different plants may have the same maximal element.

Moreover, there may be small bits of such plants lying on the ground. These are elements that are not part of any chain. If any such bit exists on the ground, then we have a maximal element. Proof: If it could be compared to any other element, it would be on a chain. If it can’t be compared to any other element, it’s not smaller than any element.

Let us suppose no such bits of plants exist. Then a maximal element of any chain will be the maximal element of the whole set! Proof: It is not smaller than any element in its own chain. It can’t be compared with the chains which do not intersect with this chain. And as for chains that intersect with this chain, if the maximal element is the same, then we’re done. If the maximal elements are not the same, then too the two maximal elements can’t be compared. Hence, every distinct maximal element is a maximal element of the whole set.

Assuming that the set is non-empty, at least one plant bit or chain has to exist. Hence, every partially ordered set has at least one maximal element. The possible candidates are plant bits (elements not in any chain) and plant tops (maximal elements of chains).