In America, every state has a governor which represents it. Can you imagine a country where this is not possible? That is, can you picture a country (such that each state has at least one person living it to avoid trivialities) where we could not select a governor to represent each state? Such an idea seems preposterous. After all, we can simply go through each state one-by-one and choose a random person to designate as governor.
If we translate the above statement into an abstract mathematical setting, we are saying that given any collection of nonempty sets, we may choose one object from each set. This seemingly trivial statement is known as the Axiom of Choice (since it says that we may choose a representative from each set) and has had a remarkable influence on the development of mathematics since the beginning of the twentieth century. How could such an obvious principle have such an impact?
To first understand the subtleties of the Axiom of Choice, one has to realize that when phrased in such an general setting, the statement is not as obvious as one would originally think. When considering countries in the example above, you probably never thought about a country that has infinitely many states. What happens if you imagine such a country? If we tried to list the states in some order and one-by-one to pick out representatives, then we would never finish after a finite number of steps. Imagine the federal government trying to finalize the results of the election from an infinite number of states. It takes some nontrivial amount of time to fill out the necessary paperwork and swear in a governor, so if only one federal office was in charge of the election, then they would never finish the entire task. To further complicate the matter, we know that there are different sizes of infinity!
The power of the Axiom of Choice lies in the fact that it allows you to make infinitely many arbitrary choices at one time. If you are given only finitely many nonempty sets, then you can go ahead and pick out an element from each (this is justified by the other axioms of set theory. See the Set Theory section to view the remaining axioms). Also, if there is a clear unambiguous way to choose a specific element from each set (see the sections on Mathematical Logic and Set Theory to see how a mathematician formalizes the notion of a well-defined unambiguous definition), then choosing these well-defined objects is also justified (by the other axioms of set theory). For example, if every state held an election, and each had a clear winner, then you would not need the Axiom of Choice to collect all of the winners into one set. For a precise mathematical example, if you are given a collection of nonempty sets of natural numbers (recall that the natural numbers are 0,1,2,3,...), then you can choose the smallest element out of each set. Think about what you would do if you are given a collection of nonempty sets of real numbers. Can you give a clear rule that unambiguously determines a unique element from each set? (Notice that taking the smallest real number from each set may not make sense because the set of real numbers strictly greater than 0 has no smallest element).
An example of Bertrand Russell may help clarify matters. Suppose that you are handed an infinite collection of pairs of shoes. Then, without using the Axiom of Choice, you can choose one shoe from each pair by stating that you will take the left shoe from each pair. This is a well-defined unambiguous choice. Suppose instead that you are handed an infinite collection of pairs of socks. Then there is no clear rule that you can employ to choose one sock from each pair. You need to make infinitely many arbitrary choices all at once, and this is what the Axiom of Choice allows you to do.
Despite all this, the Axiom of Choice probably still seems to be obviously true. Mathematicians up until the first decade of the twentieth century certainly thought so, and employed the Axiom of Choice in many arguments without giving it a second thought or realizing that anyone would consider their arguments controversial. However, not long after the seedlings of set theory were planted, Zermelo claimed that he had a proof that every set could be well-ordered.
What does it mean for a set to be well-ordered? Intuitively, a set is
well-ordered if we can order the elements in a way that mimics the very nice
ordering of the natural numbers. What's so nice about the natural numbers?
The order on the natural numbers has the following 3 properties:
1) We never have a < a.
2) Whenever a < b and b < c, we have a < c.
3) For any a and b, either a < b, a = b, or b < a.
These are all nice properties, but the one that really sets the natural
numbers apart is the following:
4) Every nonempty subset has a smallest element.
A well-ordered set is one with an order that satisfies the above properties. This definition probably seems mysterious when encountered for the first time, but there is another way to characterize well-ordered sets. Recall from The Different Sizes of Infinity that we call a set countable if we can list the elements one-by-one like the natural numbers. A well-ordered set is a generalization of a countable set. Instead of insisting that we can count it off one-by-one like the natural numbers, where each particular element is reached at some finite stage, we call a set well-ordered if we allow our list to continue on past the natural numbers into the transfinite. Imagine that you start counting through the natural numbers 0,1,2,3, ... . Of course, you'll never finish this process in a finite amount of time. Suppose, however, that after counting for an infinite amount of time, you surprise yourself by finishing the task of counting the natural numbers. What should you do now? You just passed through an eternity, and can't think of anything else to do, so why not start counting again? Maybe, for a change of pace, we'll start counting the rational numbers with denominator 2. So we start 1/2, 3/2, 5/2, ... . Once we finish this infinite task, we go for the ones with denominator 3, counting 1/3, 2/3, 4/3, ... . Writing down all our numbers into a list, we get: 0,1,2,3, ... 1/2, 3/2, 5/2, ... 1/3, 2/3, 4/3, ... . Notice that the 1/2 in this list does not appear at a finite stage, and so we say that this list is transfinite. Of course, there is no reason to stop here. Once we finish this task, we can still keep right on going, exploring further reaches of the transfinite.
At this point, one may wonder if we've wandered into the realm of mysticism and theology. What exactly is this "transfinite"? Can we build a coherent theory around it? The answer is a resounding yes, but the details are somewhat technical and are best left to the discussion of Set Theory.
Above, I alluded to Zermelo's proof, using the Axiom of Choice, that every set could be well-ordered. This was a defining moment in the history of the Axiom of Choice, because soon thereafter many mathematicians began to have misgivings about it. If the argument is correct, then we should be able to well-order the real numbers. That is, we should be able to list them in a manner that goes into the transfinite. Did Zermelo show mathematicians a clear way to do this? No. Did he give a clear method that, when applied, put the real numbers into a nice transfinite list? No. Zermelo's result simply claims that this could be done without giving any constructive way to do it, and this made mathematicians uneasy. If you examine the Axiom of Choice closely, you can see where this nonconstructive aspect enters the picture. Recall the Axiom of Choice says that given an arbitrary collection of nonempty sets, we may choose an element from each of them, without any sort of rule, m ethod, or scheme to do so. Thus, by adopting the Axiom of Choice, we commit ourselves to a new kind of nonconstructive mathematics.
Now that we've discussed what the Axiom of Choice says, we should look at its utility within mathematics. Of course, if the Axiom of Choice wasn't used many times within the main body of mathematics, there wouldn't be such a fuss over it. At its core, the Axiom of Choice says that infinite collections of objects behave like finite collections in a certain manner (by being able to choose representatives). Once we adopt it as an axiom, the structure of the infinite within mathematics becomes more transparent.
Zorn's Lemma Every vector space has a basis Tychonoff Theorem Maximal Ideals Analysis and sequences Set Theory
Mathematical abnormalities Consistency and Independence