Filed under: Math, Set Theory | Tags: axiomatic, MaBloWriMo, Math, order theory, set theory

This post is going to be a bit more technical than most, so feel free to skim it if you find it difficult. You should know the statements of the theorems and the definition of well-ordering, though.

When I stated the ZFC set axioms, I put choice last for a reason. As I said there, it’s a bit like the parallel postulate in Euclidean geometry (if you don’t know this story, you should read about it — it’s fascinating). Unlike the other axioms, it’s non-constructive, and it looks complicated enough that you should be able to get it from the other axioms, though it’s in fact independent of them (meaning they can’t prove it or disprove it). For these reasons, many mathematicians in the early half of the century used choice sparingly, and made it very clear what pieces of their work required it. But as we’ve seen, we needed it to show that every infinite set contains a sequence, and likewise, many of its consequences are so useful that it’s common nowadays to use it without reservation. (And yes, Munroe, the Banach-Tarski paradox is a good thing.)

Besides important consequences, there are about four important equivalent statements to the axiom of choice, and that’s what I’ll be talking about today. Hopefully this will give you an idea of what a choice function is and how powerful it is. We’ll be showing the following statements are equivalent:

**The axiom of choice**: every set has a**choice function**such that for all .- Every Cartesian product of non-empty sets is non-empty.
**Zorn’s Lemma**: Every partially ordered set, in which every totally ordered subset has an upper bound, has a maximal element.**Hausdorff Maximum Principle**: Every partially ordered set has a maximal totally ordered subset.**Well-Ordering Theorem**: Every set can be well-ordered.

Below the fold, definitions of these terms and proofs of equivalence.

In the post on the ZFC axioms, I asked you to prove that (1) was equivalent to (2). If you didn’t figure it out, here’s the proof. For the record, we know that finite products of nonempty sets are nonempty by induction. The infinite case requires choice, though. Let be a set of sets indexed by . An element of is a ginormous ordered tuple, indexed by , whose th coordinate is an element of ; that is, it’s a simultaneous choice of an element out of for every . But if we know the axiom of choice, we can simply create a choice function on , and then the tuple whose th coordinate is is an element of . Conversely, if every infinite product of non-empty sets has an element, then given a set , find an element of ; the function sending to the th coordinate of this element is a choice function for .

For the latter three statements, we need some more terminology from order theory. Recall that a partially ordered set (or poset) is a set with a relation that is reflexive, antisymmetric, and transitive. This doesn’t mean the relation compares every pair of elements: if it does (so for any two elements, one is less than the other) we call the set a totally ordered set (I advocate the term “toset”). The **upper bound** of a subset is an element such that for all . This isn’t necessarily an element of . A **maximal element** is an element such that there is no element with . In the Hausdorff Maximum Principle, the word “maximal” is being used differently: a **maximal totally ordered subset** is a subset such that, if you added any other element to it, it would no longer be totally ordered. Finally, a **well-ordered set** is a toset such that every subset has a **least element**, an element such that for every .

The remaining equivalences can be proved using a cyclic proof: a proof that (1) implies (4), which implies (3), which implies (5), which implies (1). First assume the axiom of choice: we’re going to prove the Hausdorff Maximum Principle. This is the longest and hardest part. We start with a lemma:

**Lemma**. *Let be a set and . is a poset under inclusion. Assume that , that if then as well, and that contains the union (which is the least upper bound) of each of its totally ordered subsets. Then has a maximal element (in both senses).*

**Proof**. Let be a choice function for . We’ll first define a “growing map” that sends each element of to a larger element, if possible. Define by . So in general, and iff is maximal. But we don’t know that is in :

could have many more elements than , and we only know that adding any *one* of them gives a set in . So define by whenever , and if . Again, , and iff is maximal. But this time, only has one more element, at most, than .

We want to look at the things you can get from applying a ludicrous number of times. Let a **tower** be a subset of such that , contains the union of each of its totally ordered subsets, and for all . itself is a tower, so we know that a tower exists. Let be a *totally ordered* tower, and let . Then , but by definition, so . Thus is maximal. So we just need to find a totally ordered tower.

A common thing to do in these situations is to check the condition for the smallest possible thing. So I claim that the intersection of the set of towers, which I’ll call , is a totally ordered tower. It’s easy to check that it satisfies the tower definition. For the ordering condition, define as the set of elements of that are comparable (either supersets or subsets) with every element of . Then is totally ordered iff , because then every element of is comparable with every other. Since is a subset of every tower, we just have to show that is a tower.

Since the empty set is a subset of everything, . Let be a totally ordered subset of ; then if is not a subset of , it cannot be a subset of any element of , so it is a superset of every element of , and thus it is a superset of . So every set is comparable with , so . Finally, we need to show that for every , we have , which means that every element of is comparable with . Since , we can weaken this to or for every ; if this holds, then is a tower, so is a toset, and the theorem is true.

Brace yourself — the easiest way to prove this is to use yet another tower! But we’re near the end. Fix a set , and define to be the set of elements such that or . Again, if is a tower for an arbitrary , then , so , and since was arbitrary, we’re done. It’s obvious that ; likewise, if is a totally ordered subset of , then since is a tower, and if then is not a subset of any element of , so they all contain instead, so . Finally, we have to check that is closed under the action of . Let $B\in E_A$, so . If , then , so . If $B=A$, then , so . If , then by definition of , either or . But if , then since , we’ve added at least *two* elements to get from to . So , and then .

To summarize: we proved that ; since was arbitrary, then for *every* ; this proved the second part of the tower condition for ; since was a tower, it contained , and it was defined so that this meant was a toset; since was a tower toset, was a fixed point of ; thus, was the maximal totally ordered subset we wanted. This proves the lemma.

Armed with our faithful lemma, the Hausdorff Maximum Principle is just one step further.

**Proof**. Given a poset , let be the set of totally ordered subsets of . Clearly is totally ordered; subsets of totally ordered sets are still totally ordered; and given a toset under inclusion (a toset of tosets in ), if , then there are elements such that , and either or vice versa, but either way, and are comparable. So fits the lemma, and thus it has a maximal element.

**Theorem**. *The Hausdorff Maximum Principle implies Zorn’s Lemma*.

**Proof**. Let be a poset in which every totally ordered subset has an upper bound. Let be a maximal totally ordered subset by the HMP, and let be an upper bound for . If any element has , then is greater than all elements of by transitivity, so is a totally ordered subset. But was supposed to be maximal, so no has . Thus, is a maximal element of .

**Theorem**. Zorn’s Lemma implies the Well-Ordering Theorem.

**Proof**. Let be a set and let be the set of pairs where and is a well-ordering of . We can define a partial ordering on by saying whenever , agrees with on , and if , then for all with . (We say that is an **initial segment** of .) It’s easy to see that this is a partial order on . If is a totally ordered subset, then is an upper bound (the union of the relations means that if for some ). By Zorn’s lemma, has a maximal element for . If $x\in X-M$, then we can define by and restricting to on , but with larger than all members of . Then , which contradicts maximality. Thus, and well-orders .

**Theorem**. The Well-Ordering Theorem implies the Axiom of Choice.

**Proof**. Given a set , well-order it. The choice function just sends each subset to its least element!

That’s all, folks!

**2 Comments so far**

Leave a comment

[…] Gracious Living and the Two Meat Meal Just another WordPress.com site Skip to content HomeAboutMathematical LanguageTo Do ← The Axiom of Choice […]

Pingback by Ordinals | Gracious Living and the Two Meat MealNovember 6, 2010 @ 08:17[…] second thing is the sentence “pick an element out of each orbit of .” Without the Axiom of Choice, there’s no reason we should be able to do this. Most mathematicians today use choice […]

Pingback by Banach-Tarski part 2 « Gracious LivingNovember 21, 2010 @ 23:31