The Axiom Of Choice, some history, some ideas
Gregory Moore is a historian of mathematical logic. One connection he has to things dear to us is that he edited the first two volumes of Kurt Gödel’s Collected Works, as well as some of the work of Bertrand Russell.
Today I want to talk about making choices and in particular the axiom of choice.
I just spent a week at the beach, where I had a chance to read quite a bit while listening to the waves. One book I read was hard to put down—it is a book by Moore titled Zermelo’s Axiom of Choice. Okay I am a math type. I did read a couple of thrillers, but Moore’s book really is a fascinating read.
Moore’s book calls the axiom of choice “The Axiom.” It really is Zermelo’s Axiom of Choice, but `Axiom’ is much shorter and probably cuts the length of the book by quite a bit. The Axiom was first stated explicitly by Ernst Zermelo in 1904.
You probably know it: The Axiom states that for any family of non-empty sets, there is a function so that for each set in the family , is an element of . There is no other constraint on : there can be sets so that . The critical point is that is always an element from .
Intuitively the Axiom says that there always is a choice function . The function chooses some element from each set . The point of the Axiom is that while there is often a way to define an explicit rule for , this is not always possible. The Axiom therefore states that no many how complex—in any sense—the sets in are, there is a way to select the required elements.
“The Axiom of Choice is necessary to select a set from an infinite number of socks, but not an infinite number of shoes.” — Bertrand Russell
The story of the Axiom—and the reaction to the Axiom—form the subject of the book. See the book for details, it really is fun. I would like to say something about the book, but I would like to first give some good news and bad news.
Good News And Bad News
You probably know some of the consequences of the famous Axiom. Essentially there are two types of results. Some results would be classified by most people as good results, while other results would be classified by many as bad results. There are weaker versions of the Axiom that miss some of the bad consequences, and they also miss some of the good results. To avoid complication let’s just list some results obtained with the Axiom: we will label them into good and bad ones.
Good: The real numbers are not the union of a countable set of countable sets of reals. The Axiom is used to prove this. Note that the famous diagonal result of Georg Cantor shows that the reals are not a countable set. Yet his proof does not rule out that the reals could be the union of a countable list of countable sets of reals. Strange, but true. So for all those who doubt the reals are countable—we have discussed this before—here is some hope. If you deny the Axiom, then you get something close to countable.
Let me explain this more carefully, since it seems crazy. How can the countable union of countable sets be anything but countable? When I saw this I thought: hey that is easy to prove. So let’s go and “prove it.”
Suppose that is a countable set where each is also countable. Let’s prove that the union of all these elements is itself countable—that is, that
is countable. It clearly follows that each has as its members
Then is countable by the same argument that Cantor used to show that the rationals are countable. Done.
This does not use the Axiom. Right? Wrong. The Axiom is used in a subtle manner that is nearly invisible. If you want a challenge, take a moment and see if you can see where the Axiom is used.
The Axiom was invoked when we enumerated the elements of all the sets . There are infinitely many , and each has infinitely many bijections onto the positive integers. We used the Axiom to select one of these bijections to make well-defined. Indeed, using forcing methods there are models of set theory without the Axiom where the reals—though uncountable—are the countable union of countable sets. Amazing.
Good: The Lebesgue measure is countably additive. This is one of the basic features that make measure theory work. The Axiom is used to prove this. Its use is related to the previous “good” result.
Bad: There are non-measurable sets. Life would be much simpler if all sets were measurable, but the Axiom shows that this is false.
Bad: There is no finitely additive measure on three-dimensional space that is invariant under Euclidean transformations. This follows from the famous Banach-Tarski paradox: the unit ball can be divided into a finite number of pieces and reassembled into two identical unit balls.
What I found interesting is the confusion that surrounded the early days of set theory, especially with regard to the Axiom. Zermelo introduced the Axiom to prove Cantor’s claim that the reals could be well-ordered. Of course the reals have a simple order defined on them, but a well-order is more. It requires that every non-empty set has a least element. This fails for the usual order—just consider all positive reals. They clearly have no least element.
Zermelo showed that the Axiom implies that every set can be well ordered. At the time many doubted that every set could be well ordered, but the Axiom seemed more reasonable. This is the reason that Zermelo introduced it. Many doubted the Axiom. Their doubts came from various sources. Initially the idea that there is always a choice function seemed quite powerful. Later as consequences of the Axiom were discovered, especially “bad” ones, many disliked the Axiom.
What I thought was cool about the story is that Zermelo had a simple point. Throughout analysis, for years, the Axiom had been used repeatedly by mathematicians, without knowing they were using it. So Zermelo’s point was that you have already used the Axiom in your work—so why can’t I use it to prove the well-ordering result? I found it extremely interesting that people could use the Axiom in their research, and still fight against it.
Read the book for all the details and much more about the Axiom.
Complexity Theory Version?
While reading the book, I did think about whether or not there is some finite version that is relevant for us. We tend to worry mostly about finite sets, but actually when talking about decision problems we are concerned with countable sets. Indeed. Is there some connection between the Axiom and our basic unsolved questions?
One possible connection is the notion of, what is a finite set anyway? There are many ways to define what makes a set finite. The standard notion is is finite provided there is a bijection between and for some . But there are other definitions. What is relevant is these definitions seem to capture the same notion of finite, but without the Axiom that is not provable. So if we think in complexity theory about these other notions of finite, could that lead us to some new insights about complexity theory? I wonder.
Here is one of the most famous alternative definitions, due to Richard Dedekind. A set is Dedekind-infinite provided there is a bijection between a proper subset of and . It is Dedekind-finite if it is not Dedekind-infinite. See here and here for more details. Note the Axiom is required to show that this definition is the same as the standard one. Okay, a weaker choice axiom is enough, but some form is required.
Are you a believer of the Axiom? Or are you a doubter?
Can we relate Dedekind finite in some way to fundamental questions in complexity theory?