Yes…I’m still alive and blogging. Just been very busy, as it is coming up to exam-time. Thankfully I think I can safely say that my exam-sitting days are behind me, but there are a lot of anxious students happy to pay good money to someone who will help them pass theirs! Anyway, I recently read an interesting blog post about the axiom of choice, and I thought it would be a good topic to give my usual treatment (that is an attempt to explain it to an interested and patient non-mathematician).
Now, unlike other sciences – in which theories and models are often proposed, used for while, and then modified or just plain discredited by subsequent discoveries – mathematics is constantly building on what has gone before. If sciences were buildings, then mathematics would be a vast complex structure that is constantly being added to: sometimes the foundations would be strengthened, sometimes an extension or a whole new wing would be added, but nothing would ever be demolished. Physics, on the other hand, would be a lot of separate buildings, some of which have long ago been abandoned, and most of the rest of which are in a constant state of being torn down and rebuilt in the modern style! This is part of what drew me to the subject in the first place; the fact that if you prove something mathematically, it is definitely true, and will never be disproved. We still use theorems proved by people that lived thousands of years ago, and it is reassuring to know that anything we prove now will still be being used by people in thousands of years.
So any addition to existing theory will be based on a whole chain of theorems, lemmas and propositions which follow logically from one another. But what is at the beginning of such a chain? At that point it is assumed that we know nothing; we can’t prove anything as we have no knowledge of anything with which to prove it! This is where axioms come in. Wikipedia has the following definition of an axiom:
“an axiom…is a proposition that is not proved or demonstrated but considered to be either self-evident, or subject to necessary decision. Therefore, its truth is taken for granted, and serves as a starting point for deducing and inferring other (theory dependent) truths.”
Now, assuming the truth of a self-evident statement seems like a perfectly reasonable thing to do, but the problem is that sometimes something that seems self-evident will be wrong. A Greek mathematician called Euclid was the first to propose an axiomatic mathematical system, indeed he could probably be credited with inventing the notion of an axiomatic system. He did it specifically for geometry, by proposing five postulates (axioms). From these five seemingly self-evident statements (for example: “there is a straight line between any two points”, and “all right angles are equal”), and a few other foundational assumptions, the whole subject of Euclidean geometry – which is what any non-mathematician thinks of simply as “geometry” – can be developed. However, Euclid’s fifth postulate (the “parallel postulate”) has become quite infamous in mathematics. It is not quite as self-evident as the other four, and says, basically, that two parallel lines will never intersect. Mathematicians were very uncomfortable with this, as it is fundamental to Euclidean geometry, and yet is not quite obvious enough to be called an axiom. So for around 2000 years they tried to prove it using the other four postulates, with very little success.
Finally, a few of them gave up trying, and instead started exploring the consequences of assuming that the parallel postulate did not hold. They discovered, to everyone’s great surprise, that completely correct and consistent (if rather odd) alternative theories do exist in which parallel lines can intersect. These are now called, collectively: “non-Euclidean geometry” (I mentioned some of them in my last post), and their discovery had a great impact on mathematics, not least in that people became even more unsure of what they knew to be true, and more sceptical about what consitutes self-evidence.
Permit me one more digression before I actually explain what the Axiom of Choice is…I want to mention the Pigeonhole Principle, partly because it is vaguely relevant, and partly just because I think it is funny. The pigeonhole principle says: given a certain number of objects, and less places to put them, if you put all the objects into the places then at least one place will have more than one object in it. For a long time I have found it very amusing that mathematicians have actually given this principle a name at all, let alone for some obscure reason formulated it in terms of pigeons. But actually this seemingly trivial fact has some not-so-trivial implications, and it is not uncommon to see the pigeonhole principle invoked in a proof. Continuing the theme of friends and strangers in a room I started on in a previous post, here is one such use of it:
Theorem
Suppose there are some people in a room, some of whom know each other, some of whom do not (but all of whom know at least one other person). Then at least two of them have the same number of acquaintances in the room.
The proof is deceptively simple: suppose that there are
Th Axiom of Choice is another example of an obvious-seeming statement which has far-reaching implications. Unlike the pigeonhole principle, it is impossible to prove. And unfortunately, like the parallel postulate, it is not quite obvious enough to accept as self-evident. The story of non-Euclidean geometry would seem to suggest that the worst thing we could do in this case would be to assume it is true and disregard alternative systems of mathematics in which it does not hold. But that is exactly what we’ve done!
The problem is that the Axiom of Choice is an axiom of set theory…and set theory is the most commonly-used foundational system for mathematics. Definitions of mathematical objects are almost always given in terms of sets (I gave a definition of numbers in terms of the empty set in this post), and the language and methods of set theory are used throughout mathematics. The consequence of this is that, if the Axiom of Choice were not assumed to be true, then much of mathematics would have to be reconsidered and reformulated. Many theorems use the axiom in their proofs, and a huge number of important statements are logically equivalent to it.
Thus it is a rather sensitive topic for mathematicians. Most of us take great pleasure in the consistency and completeness of the subject, and we find the fact that there exists an unprovable statement – the veracity of which is integral to much that we do – rather troubling. there used to be some controversy about it, with some radical souls refusing to accept any result predicated on the Axiom of Choice in any way. These days though, people have settled into a kind of slightly uneasy acceptance of it, and with the notable exception of a few brave set theorists who continue to explore alternative systems in which it does not hold, the vast majority of us have placed it (along with Gödel’s Incompleteness Theorem) firmly into the category of “things it is best to not think about”.
So without further ado, I suppose I’d better tell you what it is! I have avoided doing so up to now as it would have contributed nothing to the discussion: relative to its impact, the axiom itself is rather uninteresting. For continuity I will couch it in terms of pigeons and pigeonholes, I’m sure it will be no less enlightening that way than any other:
The Axiom of Choice
Suppose we have an infinite number of pigeonholes, each containing at least one pigeon. Then it is always possible to choose one pigeon from each pigeonhole, even if we have no instruction as to which pigeon to select from each hole.
Yet another blogging mathematician... 
Thanks for the comment. Glad you explained AC so well. I assumed that all knew it, so good to see this post.
“we are not doing philosophy here” – I’d say that’s exactly what we are doing.
You’ve assumed a foundational epistemology underpinned with unprovable foundations. Which I guess will always be the problem with that kind of approach – if you keep going back asking ‘why?’ you don’t get to some question with a satisfactory answer which goes something like ‘because it just is’ – you actually just keep on getting more ‘whys’.
Isn’t this the task that drove Bertrand Russell mad, producing his unreadable epic ‘Principia Mathematica’.
I’m probably wrong. But the we all are.
hmmm…that’s exactly the sort of thing a philosopher would say. I suppose the axiom of choice problem is a manifestation of exactly that impossibility of reducing things to first principles. Makes me glad I don’t have to worry about these things.
Bertrand Russell thought about the axiom of choice not in terms of pigeons, but socks and shoes. He said:
“To choose one sock from each of infinitely many pairs of socks requires the Axiom of Choice, but for shoes the Axiom is not needed.”
An Alternative is called Coherentistism. I thought I had come up with an analogy to a crossword puzzle, but I Googled it and someone else had beat me to it.
Here instead of a regression of beliefs back to some foundation all of our beliefs are mutually reinforcing:
“In the image of the crossword, the answers in the crossword form the corpus of our beliefs, each individual answer that we fill in representing a single belief. When we get an answer that fits with an answer that we have already, that fact helps to confirm the correctness of the second answer […] to some degree. But it is equally true that the second answer helps to confirm the correctness of the first answer. There is no asymmetry here in terms of confirmation […] Notice, too, that the more answers which we get that fit in with the answers which we already have, the better confirmed we regard all of the answers, both the original set and the later additions.”
Interesting. Certainly as regards AC this is exactly the reality: lots of different statements which are logically equivalent to the axiom, and hence no real sense of any of them being more or less foundational than any other.
The trouble with the crossword verification of the Axiom of Choice is that, for many mathematicians, it confirms some of our beliefs and conflicts with others. For example, it implies that every vector space has a basis (which many mathematicians would regard as, if not obvious, at least highly desirable), and also the Banach–Tarski paradox, that a unit ball can be decomposed into finitely many pieces which can be reassembled into two unit balls (which a lot of people find quite counter-intuitive).
About the pigeonhole problem you describe – I don’t see anything in the statement of the theorem that says a person can’t know nobody else either. Not too important, but still… =P
Thanks! That is exactly the sort of fastidious comment I would expect a fellow mathematician to make. Consider it corrected.
There are various forms of the AoC, some of which are more counterintuitive than others.
1. – that the pigeons you have chosen are a set.
2. – that every set has a choice function.
3. – that every set can be well ordered.
I can do very well without the AoC, although choice of a denumerable collection of things is OK. At least we can name them all and reason about them.
Grad student: Professor, of what possible use is this research topic?
Professor: You might be able to earn a doctorate in it.