# Motivating implications of the axiom of choice?

What are some motivating consequences of the axiom of choice (or its omission)? I know that weak forms of choice are sometimes required for interesting results like Banach-Tarski; what are some important consequences of a strong formulation of the axiom of choice?

-
By "strong formulation" do you mean for "classes"? –  AD. Dec 2 '10 at 19:50

Each of the following is equivalent to the Axiom of Choice:

• Every vector space (over any field) has a basis.

• Every surjection has a right inverse.

• Zorn's Lemma.

The first is extremely important and useful. The third is used all the time, especially in algebra, also very important and useful.

You could write an entire book on important consequences (and equivalents) of the Axiom of Choice.

Unfortunately, any publisher worth his salt would reject it, since both have already been written:

1. Rubin, Herman; Rubin, Jean E. Equivalents of the axiom of choice. North-Holland Publishing Co., Amsterdam 1963 xxiii+134 pp.

2. Rubin, Herman; Rubin, Jean E. Equivalents of the axiom of choice. II. Studies in Logic and the Foundations of Mathematics, 116. North-Holland Publishing Co., Amsterdam, 1985. xxviii+322 pp. ISBN: 0-444-87708-8

3. 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. ISBN: 0-8218-0977-6

These books are probably not the best place to start, though; the first book is okay, listing some of the most important equivalents as they were known before Cohen's work, but at least the last is pretty difficult to slough through.

If you want a good introduction to the Axiom of Choice and some idea of its uses, Horst Herrlich's Axiom of Choice, Lecture Notes in Mathematics v. 1876, Springer-Verlag (2006) ISBN: 3-540-30989-6 is pretty good, discussing some of the bad things that happen if you don't have AC, some of the bad things that happen if you do have AC, and some alternative axioms that contradict AC but lead to very nice theorems.

-
Thank you for the reading suggestions, highly appreciated! –  Joseph Weissman Dec 2 '10 at 19:57
@Joe: Actually, those are very hard books to read; they are meant mostly for logicians. Let me add this to the answer and some better sources if you want more accessible discussions. –  Arturo Magidin Dec 2 '10 at 19:57
Thank you, accepted. –  Joseph Weissman Dec 2 '10 at 20:19

Axiom of Choice $\iff$ A non-empty product of non-empty sets is non-empty.

-
That was interesting! Exact my answer... I remove mine :) –  AD. Dec 2 '10 at 19:54
I changed my mind and added Tychonff's theorem to mine. :) –  AD. Dec 2 '10 at 19:58
What really intrigues me about this one is that "non-empty products are non-empty" sounds so obviously true, yet it is equivalent to the well-ordering theorem - "which is obviously false" ;) –  kahen Dec 2 '10 at 20:08
I think "non-empty products are non-empty" begins to sound much less reasonable if you take a sufficiently constructive point of view: you should think of it as a problem of writing down an algorithm which constructs elements of a product, and if it gets harder and harder to write down algorithms which construct elements of each factor... –  Qiaochu Yuan Dec 2 '10 at 20:21
@kahen You do not need to require that the collection of multipliers is non-empty. In the case of empty collection the product is a singleton set containing just the empty set (having exactly one element from each of zero multipliers). –  Piotr Shatalin Jun 4 at 19:30

The Axiom of choice is required to prove for example that every ring has a maximal ideal (or a minimal prime), or the existence of an algebraic closure.

-
Oh, I forgot: The Tychonoff theorem of point set topology - that an arbitrary product of compact spaces is compact - depends on the axiom of choice. –  Fredrik Meyer Dec 2 '10 at 20:45

There Lebesgue measure is non-trivial - there are non-measurable sets in $\mathbb{R}$.

-
What applications of Lebesgue measure actually require you to know that there exist non-measurable sets? Also, this is strictly weaker than choice; it follows from, for example, the ultrafilter lemma. –  Qiaochu Yuan Dec 2 '10 at 20:10
Well, as I have heard Banach-Tarski needs non-measurable sets. Anyway, providing such examples illustrates that theory of measurable sets is non-trivial and can not be hand-waved away. –  AD. Dec 2 '10 at 21:10

The Hahn-Banach theorem and Tychonoff's theorem are two major ways in which the axiom of choice gets used in analysis (I am echoing other answers here because these are really important). In addition to Zorn's lemma, the third "classic" theorem known to be equivalent to AC is the well-ordering theorem.

Here's a somewhat surprising one I was recently made aware of: you cannot prove that a countable union of countable sets is countable without some form of countable choice. The problem is that in order for any of the standard proofs to go through, you need to choose, for each countable set in the union, a bijection of it with $\mathbb{N}$, and there is no way to do this canonically in general. (Fortunately, for most countable sets we encounter in practice we can define explicit bijections, so there's usually no problem.)

A weak form of choice, the Boolean prime ideal theorem (or equivalently the ultrafilter lemma), also has many useful consequences. For example, it is equivalent (I think) to Tychonoff's theorem for compact Hausdorff spaces. It is equivalent to Gödel's completeness theorem, as well as to the compactness theorem. It allows you to construct ultraproducts, which has a whole genre of uses such as, for example, defining nonstandard models of $\mathbb{R}$ or more exotic things. Terence Tao has written several good blog posts, including this one, on these and related subjects.

You might be interested in browsing http://consequences.emich.edu/CONSEQ.HTM for more consequences of AC. There are really quite a lot.

-
Beautiful, thank you! –  Joseph Weissman Dec 2 '10 at 20:20

A consequence that motivates me is: If $I$ is some non-empty class and $X_i$ is a non-empty class $i\in I$, then $$\prod_{i\in I}X_i\ne\emptyset$$

EDIT

An other consequence that motivates me is: If $I$ is some non-empty set and $X_i$ is a compact topological space $i\in I$, then $\prod_{i\in I}X_i\ne\emptyset$ is compact.

Of course these are known equivalences of the Axiom of choice.

-
Curiously, Tychonoff's theorem for compact Hausdorff spaces does not require the full strength of AC, but only the strictly weaker Ultrafilter Lemma –  kahen Dec 2 '10 at 20:05

I think that one of the most important implications of the axiom of choice is actually the equivalence of continuity between the Cauchy definition of $\epsilon$-$\delta$ and the Heine definition using sequences.

-

To construct left- and right inverses of functions where the domain is not well-ordered we need the axiom of choice. Also, we can always get a well-ordering (this is equivalent to the axiom of choice) so that way we also could obtain this result (then you take for the many inverses the smallest one).

Also, it is important in functional analysis, for example Hahn-Banach depends on it. The axiom of choice implies Hahn-Banach but not the other way around.

-

Adding a 2nd answer in order to keep things to one example per answer.

There was some time ago a question on MO about whether Arzelà-Ascoli requires choice, and the answer turns out to be that it indeed does require choice - though not the full strength of AC.

-