Basic facts about AC, part I

Several standard proofs in algebra, analysis, and topology rarely appear without the proviso that they rely on the Axiom of Choice (AC): the proof that every vector space has a basis, that every field has an algebraic closure, of Tychonoff’s theorem, of the Hahn–Banach theorem, etc. (I contend these provisos show up because the easiest proofs of these facts use Zorn’s Lemma, so it’s less easy for the author/lecturer to slip in a choice function covertly than it is with proofs of standard technical lemmas. I’ll address this in part 3 of this series.) The purpose of this post and its (two?) successors is—without describing the set-theoretic machinery (forcing) necessary to prove some of the important results—to summarize those facts about AC that are relevant to the ‘working mathematician’. I expect the series to follow this outline:

  1. (This post) Preliminaries, basic equivalences;
  2. Vector spaces and groups: the proofs in ZF that AC if and only if every vector space has a basis, and that AC if and only if every set can be endowed with a group structure.
  3. “We used AC there?!” and “What happens without AC?” Few proofs here. Just fun facts.

The not-logically-inclined reader might profit from a quick stop at Wikipedia to recall what the Zermelo–Fraenkel (ZF) axioms for set theory are and what the ordinals are.

Much of the information in these posts will come from one of the following sources (some of it from the exercises):

  1. Jech, T. Set Theory. Academic Press, 1978. (That’s right. I use the 1978 edition.)
  2. Jech, T. The Axiom of Choice. Dover, 2008.

When something (e.g., Blass’s proof that [every vector space has a basis] implies AC) comes from a different source, I will try to remember to indicate that.


A choice function for a set S is a function f with domain S such that f(X) \in X for every X \in S. (Notice that the range of f will consequently be \bigcup X, the set of elements of  elements of X.) So f ‘chooses’ an element from each element of S.

Examples.

  • Recall that, if the real numbers are constructed using Dedekind cuts, a real number r is the set of rational numbers that are less than r. A choice function f for \mathbb{R} therefore assigns to each real number r a rational number f(r) less than r. (Note that f(r) \in r iff f(r) \in \mathbb{Q} \cap (-\infty,r).)
  • Consider the set A = \{ \{0,1,2,\dots\}, \{1,2,3,\dots\}, \{2,3,4,\dots\}, \{3,4,5, \dots\}, \dots \}. A choice function f for A can be viewed as a function \omega \to \omega whose graph always remains above the diagonal; that is, f(x) \ge x for every x. It’s interesting to note that there is an obvious choice function for this set, and its existence does not depend on AC: since every element of A is a well-ordered set, just define f(x) to be the (unique) least element of x. Already we start to see the strong connection between the ‘choosing’ a choice function does and the least-element property of well-orderings.

Axiom of Choice (AC). If S is a set and \emptyset \not\in S, then S has a choice function.

AC is often phrased ‘The product of nonempty sets is nonempty’. By thinking for a bit about what a product is, convince yourself that these two formulations are equivalent. (The mathematical statements are identical modulo a technicality (Exercise: what is the technicality?), but their English formulations disunite them.)

I prove two equivalences in this post, each of a mostly set-theoretic nature. The first is Zermelo’s theorem that every set can be well-ordered. Recall that a relation R on a set X is a well-ordering (I always like to say “a partial order is well”—teehee) if R is a partial order, and every subset of X has a R-minimal element. For instance, the usual order on the set \mathbb{N} of positive integers is a well-ordering.

Proposition 1. In ZF, AC if and only if every set can be well-ordered.

Proof. First suppose AC and let X be a set. By AC there is a choice function f on \mathcal{P}X \smallsetminus \{\emptyset\}, the set of all nonempty subsets of X. Define by induction a sequence x_\alpha:

Set x_0 = f(X); for \alpha > 0 set x_\alpha = f(X \smallsetminus \{ x_\beta : \beta < \alpha \}) as long as X \smallsetminus \{ x_\beta : \beta < \alpha \} is nonempty.

(The sequence is using the choice function on \mathcal{P}X to pick elements of X one by one, creating a well-ordering of X.)

There is a least ordinal \theta such that X = \{ x_\alpha : \alpha<\theta\}, so the sequence (x_\alpha)_{\alpha<\theta} enumerates X. That is, X is well-ordered by the order it inherits from the bijection (check that it’s a bijection!) \theta \to X,\, \alpha \mapsto x_\alpha.

Conversely, suppose that every set can be well-ordered and let X be a set of nonempty sets. The set \bigcup X can be well-ordered by assumption; define f\colon X \to \bigcup X by setting f(x) to be the minimal element of x. Such an f(x) exists since x \neq \emptyset and is unique since x is well-ordered by the ordering it inherits as a subset of \bigcup X. Then f is a choice function for X. \hfill \square

Since AC appears for the ‘working mathematician’ most often under the alias ‘Zorn’s Lemma’, I think it’s nice for every mathematician to see a proof of their equivalence.

Zorn’s Lemma. Let (P,\le) be a nonempty poset. If every chain C (i.e., totally ordered subset) in P has an upper bound (an element x \in P such that y \le x for every y \in C), then P has a maximal element.

Proposition 2. AC is equivalent to Zorn’s Lemma.

Proof. Assume AC and let (P,\le) be a nonempty poset with the property that every chain in (P,\le) has an upper bound. By Proposition 1, P can be well-ordered, say by \precsim.

We are going to use the well-ordering of P to construct a sequence that eventually picks out a maximal element of (P,\le). Let x_0 be the \precsim-minimal element of P. Now the set \{x_0\} is a chain and so has an upper bound. Let x_1 be the \precsim-minimal upper bound for \{x_0\} that isn’t x_0 itself. Then \{x_0, x_1\} is a chain with an upper bound. Define x_2 to be the \precsim-minimal upper bound not equal to x_0 or x_1. Continue:

For each ordinal \alpha (less than the order-type of (P,\precsim)) the set C_\alpha = \{x_\gamma : \gamma < \alpha\} is a chain and so has an upper bound. Either (\alpha is a successor ordinal and) the only such upper bound is x_{\alpha-1}, or there is an upper bound that doesn’t belong to the set C_\alpha. In the first case, the element x_{\alpha-1} is a maximal element of (P,\le), and we are done. In the second, we define x_\alpha to be the \precsim-minimal upper bound for the chain C_\alpha that isn’t itself a member of C_\alpha.

Since the process can’t go on forever, there is some least \theta for which the only upper bound for the chain C_\theta is x_{\alpha-1}; then x_{\alpha-1} is a maximal element of (P,\le).

Now assume Zorn’s Lemma and let S be a nonempty set of nonempty sets. Let P be the set of functions f that are choice functions for some subset of S, and order P by inclusion \subseteq. (Here we are identifying a function with its graph, and so f \subseteq g iff the domain \mathrm{dom}(f) of f is a subset of the domain of g, and g|_{\mathrm{dom}(f)} = f.) Evidently P is nonempty since S is nonempty: for any element x of S the function \{x\} \mapsto x belongs to P, for instance. A chain C in P has as an upper bound \bigcup C, the function f given by f(a) = b iff there is some g in C such that g(a) = b. (Exercise: convince yourself that this properly defines a function on \bigcup \{\mathrm{dom}(f) : f\in C \} since C is a chain.) Apply Zorn’s Lemma to conclude that P has a maximal element f, a function on some subset Z of S. If Z were a proper subset of S and a were an element of S \smallsetminus Z, then we could extend f by taking its union with the function \{a\} \mapsto a. Since this would contradict the maximality of f, it must be that Z = S; that is, f is a choice function for S. \hfill \square

(I should point out that in the final paragraph of this proof, by “the function \{x\} \mapsto x” I mean the function whose domain is \{\{x\}\} and whose range is \{x\}; this function is a choice function, since it selects for its only member \{x\} the only element of \{x\}.)

I leave the case S = \emptyset as an exercise. =^]

Advertisements
This entry was posted in AC, Logic. Bookmark the permalink.

8 Responses to Basic facts about AC, part I

  1. JCummings says:

    I was hoping you’d do a sequence on AC. And here it is already! If there’s anything to say on the topic, in a later post will you mention what you know about an explicit well-ordering of the reals? No one has found one, right? Is there a reason why? Is it just a very difficult problem or is it impossible for some reason? How is it different than explicit well-orderings of other uncountable sets? That may be a lot, so no worries if you can’t get to it or don’t already know much about it.

    • JCummings says:

      Impossible meaning something other than impossible but close.. essentially impossible, or something… Of course it’s not actually impossible since one exists by your Proposition 1.

    • Z Norwood says:

      I thought I could answer your question satisfactorily, but now I’m interested in looking into some of the details. I’ll get back to you, but don’t let me forget.

  2. Pingback: “Measuring” Sets: An Introduction to Measure Theory. | whateversuitsyourboat

  3. Pingback: “Measuring” Sets. An Introduction to Measure Theory (Part 1.) | Alexander Adam Azzam

  4. Pingback: Global choice and algebraic closures « Andy Soffer

  5. Pingback: AC, part III: Choice in context | whateversuitsyourboat

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s