Set Theory/Zorn's Lemma and the Axiom of Choice

Two dual ideas in set theory have to do with finding the "largest" possible objects in some set under a given ordering and with making a simultaneous selection of objects from many sets. These notions are phrased in terms of Zorn's Lemma, and the Axiom of Choice; and though they sound very different, they are equivalent to one another. That is, given Zorn's Lemma one can derive the Axiom of Choice, and vice versa. The Axiom of Choice is named as such because it is independent from Zermelo-Fraenkel set theory axioms. Thus, the addition of Choice to ZF enables work not previously possible.

Zorn's Lemma edit

Zorn's Lemma, as usually stated, takes the form:

1) If every chain in a partially ordered set S has an upper bound, then S has a maximal element.

As Zorn's Lemma (ZL) has no proof or disproof from the axioms of Zermelo-Fraenkel set theory (ZF) (by famous work of Kurt Gödel and Paul Cohen), it makes sense to speak of certain propositions P logically equivalent to Zorn's Lemma (over ZF). "Logically equivalent" means the existence of implications, provable in ZF, that say ZL ==> P and P ==> ZL. "Provable," here, means provable in classical logic; often classically equivalent forms turn out independent with respect to, say, intuitionistic logic. (Topos theory provides a context for separating, via counterexamples, classically equivalent but intuitionistically inequivalent statements.)

We immediately establish the logical equivalence of ZL with two similar propositions.

2) Let S be a set with partial order ≤. If every chain has a least upper bound, then a maximal element exists in S.

3) (Hausdorff Maximality Principle) Let S be a set with partial order ≤ such that every chain of S has an upper bound. Then S contains a maximal chain (maximal with respect to set inclusion).

(1 => 2) If every chain has a least upper bound, a fortiori every chain has an upper bound, so the conclusion of 1) follows, and so that of 2).

(2 => 3) Write Chains(S) for the partially ordered set of chains contained in S, ordered by set inclusion. (We shall apply 2) to Chains(S), not to S itself!) Since every chain in Chains(S) has a least upper bound, namely its union, 2) grants us a maximal element in Chains(S), i.e. a maximal chain.

Some details edit

The union U of a chain (C_i) in Chains(S) itself has the form of a chain. For given x and y in U, we must have x in C_j and y in C_k, say, and j < k without loss of generality. But having x and y both in C_k makes them comparable.

U, as a chain, then constitutes the least upper bound for (C_i) because it does as a set!

(3 => 1) If a maximal chain C in a partially ordered set S has an upper bound u, then u belongs to C and constitutes a maximal element for S. (If u does not belong to C, then C+{u} gives a larger chain; if u does belong to C but v>u, then C+{v} gives a larger chain.

Though one might expect no content from the tautology 1) ==> 1) that results from combining the three implications above, actually, combining the proofs, we see that whenever Zorn's Lemma fails for a partially ordered set S, it must also fail for Chains(S), the chains of S ordered by inclusion. Thus if Zorn's Lemma holds for partial orders based on set inclusion, then it holds in general!

The Axiom of Choice edit

Often, Choice is stated "For every nonempty set S, there exists a function f from the set   of all nonempty subsets of S to S such that f(A) is in A". Parsing this, we assert that given a set, there is a way to simultaneously pick an element from each subset of the set. This function is usually referred to as a "choice function".

Further Equivalents of the Axiom of Choice edit

There are literally hundreds of mathematical statements that are known to be logically equivalent to the Axiom of Choice. Some of these statements are pure set-theoretic statements, such as Zorn's Lemma, above, while others are grounded in other mathematical disciplines.

In this section we will present some of these, mostly without proof.

Zermelo's Well-Ordering Theorem edit

Perhaps the most important equivalent of the Axiom of Choice (at least from the viewpoint of pure set theory) is Zermelo's Well-Ordering Theorem.

Before we state it, we must introduce some terminology:

A binary relation   on a set   is said to be well-founded if there is no infinite sequence   of elements of   satisfying the following:

  1.   for each  , and
  2.   for each  .

A partial order relation   on a set   is called a well-order relation if

  1. for each   either  , or  , and
  2.   is well-founded.

Zermelo's Well-Ordering Theorem is then the following simple statement: Every set   can be well-ordered.

Tychonoff's Theorem edit

States that the cartesian product of any arbitrary family of compact topological spaces is itself compact.

Existence of Non-Lebesgue Measurable Sets edit

Consider the unit interval   and the equivalence relation defined the interval by  . Certainly, this is an equivalence relation:

  •   because  , which is rational.
  •   implies   is rational. Then   is rational, and so  .
  •   implies that   are rational. Then,   is rational too. This implies  .

Now, choose one representative from each equivalence class. Call this set  . Can   be Lebesgue measurable? The answer is no.

To prove this, we note that any element of   differs by the chosen representative of its equivalence class   by a rational number in  , However, there are only countably many rational numbers in  ; enumerate them as  . Define the set  , the translate of   by  .

Suppose   is Lebesgue measurable. Then, by translation independence,   is also measurable, and has the same measure. Note that by the choice procedure, the sets   are all distinct. Take the union of all the translates:


If   has measure zero, then   has measure zero too, by countable additivity.

If   has positive measure, then   has measure  , by countable additivity. However,

 , and so  . But   cannot fall within this range, and so   is nonmeasurable.

Exercises edit

  1. Show that any partially ordered set contains a maximal antichain (a subset in which no two elements are comparable).

Orderings · Ordinals

Orderings · Set Theory · Ordinals