AC, part III: Choice in context

Wow, it’s been a long time since my last post. Sorry about that. I intend (though I’ll make no promises) to post a bit more regularly now.

This final post in my ac series was advertised to be a post about surprising uses of choice, but it’s grown to be a general discussion of ac.

— 1. Important principles weaker than full ac

To start developing a picture of how ac relates to other mathematical assertions, we need to describe some so-called choice principles that are not provable in zf but are weaker than ac. (See the previous two posts in this series (I and II) for some assertions equivalent to ac.)

One of the most natural ways to weaken ac is to limit the number of choices you’re making or the size of the bins you’re choosing from. By this sort of weakening we come to one of the mildest choice principles, the Axiom of Countable Choice:

Definition 1. The Axiom of Countable Choice (acω) asserts that every countable family of nonempty sets has a choice function. (That is, if {\emptyset\notin X} and {X} is countable, then there is a function that assigns each member {x} of {X} a member of {x}.)

acω is substantially weaker than ac, but it’s sufficient to forbid many types of unpleasant sets. For example, it is a theorem of zf+acω that every infinite set has a countable subset, though this isn’t provable in zf alone (that is, there is a model of zf in which there is an infinite set with no countable subset). Many elementary facts about the real numbers can be established in zf+acω; for example, only zf+acω is necessary to prove that a countable union of countable sets is countable (though, again, some form of choice is necessary to prove this). In particular, in the presence of acω, {{\mathbb R}} is not a countable union of countable sets. (Apparently the assertion the countable union of countable sets is countable is actually strictly weaker than acω. I think I once found a reference for this.)

We need slightly more firepower to do real analysis properly, though. Proofs in (baby) real analysis often require the construction of a sequence, which is typically built inductively by choosing the {n}th term from, e.g., a ball of radius {1/2^n}. The proof of the Baire Category Theorem is a good example of this style of argument, which uses the Axiom of Dependent Choice:

Definition 2. The Axiom of Dependent Choice (dc) is the following assertion: If {R} is a relation on a nonempty set {X} such that for every {x\in X} there is a {y\in X} such that {xRy}, then there is a sequence {(x_n : n\in{\mathbb N})}, of members of {X} such that {x_nRx_{n+1}} for every {n\in{\mathbb N}}.

Apparently this paper gives a proof that the Baire Category Theorem is equivalent (in zf, of course) to dc.

It is straightforward to show that dc implies acω (exercise!). There are many choice principles (like dc and acω) that guarantee only the existence of choice functions for sets satisfying certain size restrictions. (acω restricts the size of the family; other useful choice principles restrict the size of each member of the family.) dc is sufficient to prove the results of basic analysis and is particularly appealing because it is too weak to prove that nasty things like nonmeasurable sets and Banach–Tarski decompositions of the sphere exist. (See section 2 below.)

Notice that acω and dc are local principles, in the sense that they are chiefly concerned with sets of cardinality near {\aleph_0} (this is less true of dc). For this reason, it shouldn’t be surprising that each of them is strictly weaker than full ac. Applications outside analysis often require global principles (for sets or spaces of arbitrary cardinality, e.g.), and a popular global choice principle weaker than full ac is the Ultrafilter Lemma.

Definition 3. The Ultrafilter Lemma (ul) asserts that every filter on a set can be extended to an ultrafilter.

The Prime Ideal Theorem (pit) asserts that every boolean algebra has a prime ideal, an ideal {I} such that {x} or {-x} is a member of {I} for every {x}.

Conveniently, the ul is equivalent to other interesting choice principles.

Theorem 4. In zf, the following are equivalent:

  1. The Ultrafilter Lemma;
  2. The Prime Ideal Theorem;
  3. The Compactness Theorem for first-order logic.

The proof of this theorem isn’t too difficult, so I won’t provide it here. We are taking on faith that the ul is strictly weaker than ac, but it would be nice to have a sense of just how much weaker it is. We have several different equivalent formulations of ac, each about a different sort of mathematical object:

Theorem 5. In zf, the following are equivalent:

  1. ac;
  2. Every set can be wellordered;
  3. Tychonoff’s Theorem: a product of compact spaces is compact;
  4. Every vector space has a basis.

(By the way, Exercise: prove that Tychonoff’s theorem implies ac. The proof I know of is short but requires a trick.)

By transferring choice principles over to new contexts (like topology) using the ideas from the proof that the assertions above are equivalent, we can provide a satisfying picture of how much weaker the ul is than ac.

Theorem 6. In zf, the following are equivalent:

  1. the ul;
  2. Every product of compact Hausdorff spaces is compact;
  3. Every product of 2 is compact.

[Edit (Nov 10 2012): the ul is not equivalent to the assertion that every set can be linearly ordered or ac with finite `bins’; in fact,

ul \Longrightarrow every set can be linearly ordered \Longrightarrow ac with finite bins,

but none of those implications is reversible. It has recently come to my attention (I believe it’s proved in this paper) that the ul is equivalent to Tychonoff’s Theorem for sober spaces.]

Exercise: (Since so many of our authors and readers are analysts) The pit implies Hahn–Banach. (This is apparently difficult, so comment if you think you have a solution. But don’t give it away; I haven’t thought about it much yet.)

— 2. Math(s) without choice —

I’ll say a few words about two results whose proofs don’t require choice, the Cantor–Schroeder–Bernstein Theorem and Ramsey’s Theorem.

That the csb doesn’t require choice is surprising; its conclusion asserts the existence of a function constructed rather mysteriously from the functions in its hypothesis. Of course, it’s easy to say ‘Obviously it doesn’t require choice: here’s a proof that doesn’t use it!’, but when you suppress the intuition you gain by understanding the proof of the csb, the surprise returns. One reason to expect this surprise is that the easiest proof of the csb in zfc (namely, reduce to the case when your sets are wellordered by appealing to ac) makes unavoidable use of choice. And csb provides a mysterious function, which is what ac usually does.

The dual csb theorem, which asserts that if there are surjections {X\rightarrow Y} and {Y\rightarrow X} then there is a bijection {X\rightarrow Y} (and is a theorem of zfc), is not provable in zf. Apparently it is an open question whether the dual csb implies ac.

Maybe it’s not so surprising that Ramsey’s Theorem doesn’t require ac, but it can be made into a nontrivial choice principle by recasting it as ‘For every {2}-coloring of the {n}-subsets of an infinite set {X}, there is an infinite monochromatic subset {Y} of {X}.’ (‘But can’t you just prove this from the normal statement of Ramsey’s Theorem by restricting to a countable subset of {X}?’, you ask? Remember that it is not provable in zf that every infinite set has a countable subset!)

One final note: Solovay proved that it is consistent with zf+dc that every subset of {{\mathbb R}} is (Lebesgue-)measurable. So we can do analysis somewhat familiarly in a setting where all of the standard theorems (Heine–Borel, etc.) are true, but pathological nasties like nonmeasurable sets don’t exist. What does such analysis look like? I don’t know, but I’d like to.

— 3. Obviously true? —

The temptation at this point, I think, is to point out theorems we are unable to prove without full ac, and then argue that any theory strictly weaker than zfc provides a somehow deficient concept of set, since it is unable to prove those theorems. My objection to this attitude is that there is a lot of choiceless mathematics to be understood (and alternative extensions of zf (e.g., by the Axiom of Determinacy) that are capable of proving quite powerful, interesting theorems) and we simply gain nothing by asserting (or believing or whatever) that some set of axioms is the gods-given ‘correct’ one and that we should blindly stick to it (in the same way, more absurdly, that a commutative algebraist gains nothing by asserting with religious fervor that noncommutative rings simply don’t exist, in whatever metaphysical sense). Anyway, this is a standard platonism-versus-pluralism issue, and philosophers of mathematics spend a lot of time thinking about it.

— 4. The ‘magic wand’ factor —

Another reason to be careful about (though not necessarily avoid altogether) use of ac is that it is notorious for clouding the ideas in proofs. For example, consider the standard proof in zfc that every countable union of countable sets is countable: Take a countable set of sets {A_n}, choose (by acω) an enumeration of each one, and zigzag through the enumerations just as in the proof that {{\mathbb N}\times{\mathbb N}} is countable. Contrast that statement and proof to the following:

Theorem 7. The counted union of counted sets is counted. That is, if {A_1,A_2,\dots} are countably many sets, and for each {n} the function {f_n\colon A_n\rightarrow {\mathbb N}} is a bijection, then there is a bijection {g\colon \bigcup_{n\in{\mathbb N}} A_n\rightarrow {\mathbb N}} (and we can write down a formula for it in terms of the {f_n}).

And, of course, the proof is the same as above, except that the enumerations are already chosen for us. My point is that the standard statement and proof hide the real idea, which is the construction of {g} from the {f_n}. If you want the stronger result, just take this theorem and snort the necessary amount of choice. Separating the choice-snorting from the real work gives us a deeper understanding of the result and its proof. Assuming ac carelessly is in the same spirit—though hardly as ridiculous—as assuming {0=1} would be: you can prove many things, but without understanding your subject as deeply as you would otherwise. (I should mention that I owe this example, related insight, and the expression ‘snorting choice’ to Thomas Forster.)

Recently I encountered another similar example, which I’ll quickly share. I mentioned earlier that the Baire Category Theorem is a theorem of zf+dc. The BCT for separable completely metrizable spaces is actually a theorem of zf. (This isn’t hard to prove, so you should do it if you’re interested. The point is that the countable dense set allows you to make your choices canonical, since you can always take from the countable dense set the lowest-indexed point that does what you need it to do. I think this is a standard trick for proving things about topological spaces without ac, but I don’t know of another example.) I don’t know of a way to get to full BCT from BCT for separable spaces by invoking dc, though, so this isn’t as good an example as the previous one.

— 5. Coming attractions —

I’ve recently gotten excited about infinitary combinatorics, so that will probably be the topic of my next major series. Combinatorial set theory should also show up soon, as will some set-theoretic topology.

I’ll almost certainly write about toposes [sic!] someday, too, but not until after I’ve written a post or two about general category theory.

In other news, Jay has promised to write a post in the next ten days, so stay tuned! P.S. This post is the first I’ve written using Luca Trevisan’s fantastic latex2wp. I recommend it to all math WordPress bloggers! (Quick test: Does WordPress render Erdős correctly? Yes.) Blue, no green!

Two standard references, from which most of this material comes:

Jech, Thomas J. The Axiom of Choice. 2008 Dover edition, originally published as: Studies in Logic and the Foundations of Mathematics, Vol. 75. North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. xi+202 pp. (MR0396271)

Howard, Paul; Rubin, Jean E. Consequences of the axiom of choice. Mathematical Surveys and Monographs, 59. American Mathematical Society, Providence, RI, 1998. viii+432 pp. (MR1637107)

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

6 Responses to AC, part III: Choice in context

  1. soffer801 says:

    It’s nearly impossible to get me to read a page that requires scrolling. Congratulations on that. And yes, latex2wp is incredible. I’ve tweaked that code a bit for my own purposes. Remind me to tell you about it.

  2. Ryan says:

    Zach, can you give some intuition about how to construct an infinite set with not countable subset (in the model of ZF you reference)? I can’t really wrap my mind around that idea.

    • Z Norwood says:

      Hi Hotovy!

      The model is constructed using forcing (maybe alternatively Mostowski models, though I think those work only for set theory with atoms). I’m not sure we should expect to wrap our minds around the idea in a strong sense (and I, at least, have little intuition for this kind of creature), though I can try to make you feel less upset about it.

      Hopefully you can imagine a situation in which we have two sets X and Y such that there is no injection X\to Y and no injection Y\to X. (That is, |X| and |Y| are incomparable.) (Of course, this can’t happen in ZFC.) The weird thing about a set with no countable subset is that its cardinality is incomparable to \aleph_0 = |\mathbb{N}|, which is very concrete. The infinite cardinals (not identified with initial ordinals) form a partially ordered class, and we usually think of \aleph_0 as being the least element. In the absence of choice, though, there can be lots of minimal elements incomparable to \aleph_0. You want to say (I assume) that you should just be able to iteratively select elements from any infinite set X until you have \aleph_0 of them. I guess you have to come to terms with the fact that this uses choice in an unavoidable way. Notice also that, in the presence of full AC, you could keep selecting elements from X (that is, define a(n ordinal-indexed) sequence in X by transfinite induction) until you have exhausted all of the elements of X; in fact, this is exactly how you prove (in ZFC) that every set can be wellordered. I think I provide this proof in the first post in this series.

      Since you’re a shameless choice-o-phile, you might think of it this way: the weird set A lacks a countable subset because it lives in a model of ZF that’s deficient, in that it lacks an injection \mathbb{N} \to A that should exist. Compare this to the metric space \mathbb{Q}, which lacks a limit to the sequence [your favorite sequence of rationals that converges to \sqrt{2}], though the sequence should have a limit, since it’s Cauchy and so has one in \mathbb{R}. For the algebraists in the audience, (integral) domains provide a similar example. Not every element in a domain need have an inverse, but it should have an inverse since it has one in the field of fractions. The other side to this story, though, is that it’s still quite useful to analyze incomplete metric spaces (maybe less so) and domains that aren’t fields (more so). You still get a coherent theory of sets when choice fails; but it can be a bit weird, especially when countable choice fails. (I realize that I don’t know the answer to a natural follow-up question: is there a canonical ‘completion’ \bar{V} (model of ZFC) of a typical model V of ZF? This completion \bar{V} should have all the wellorderings that V lacks, and it should be the smallest extension of V that satisfies AC. I’ll investigate this.)

      (Maybe I’ll also reiterate that there is a stark difference between a typical model of ZF in which countable choice fails (and there can be infinite sets without countable subsets, etc.) and a typical model of ZF in which the Ultrafilter Lemma holds but full AC fails. Most weird choice-related phenomena pop up either when dependent choice fails or when full AC holds (non-measurable sets, etc.).)

      P.S. I have a more satisfying answer to your ‘put a ring on it’ question from several years ago. Please don’t let me forget to blog about it.

  3. Z Norwood says:

    I haven’t seen proofs of these facts, but I believe that the following two equivalences hold:
    AC iff every ring (with identity) has a maximal ideal;
    UL iff every commutative ring (with identity) has a prime ideal.
    I believe it is also true that ‘commutative’ can be removed in the second equivalence.

Leave a Reply

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

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

Google photo

You are commenting using your Google 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 )

Connecting to %s