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:
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 arepeople. We are assuming that a person cannot “know themself” (we are not doing philosophy here), and so each person must know betweenandother people. If everyone knows a different number of people, then we would be able to assign each of thepeople a different number fromto That would be like trying to putpigeons inpigeonholes!
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.