Introduction
Suppose you had infinitely many pairs of shoes, and somebody told you to pick one shoe from each pair. Then you could, for instance, pick all the left shoes. Suppose instead you had infinitely many pairs of socks, and you could not tell the two socks in a pair apart. Then, if somebody told you to pick one sock from each pair, it would not be obvious how to do so.
The axiom of choice allows mathematicians to make an infinite number of arbitrary choices. We know it is possible to make a finite number of arbitrary choices, or sometimes an infinite number of non-arbitrary choices, but with the infinite number of pairs of socks, you would need the axiom of choice to arbitrarily choose one sock from each pair. In general, the axiom of choice says that if we have an infinite collection of sets, we can simultaneously pick one element from each set. We usually represent this choosing by a choice function, a function that maps each set to the element of that set we want to choose. Without the axiom of choice, there could be collections without choice functions.
Axioms have a special status in logic. Theorems are the things we can prove from the axioms, but in order to be able to prove anything, we need some base to prove those things from. These base statements from which everything else is proved are called axioms. For a long time, it wasn’t known whether the axiom of choice was actually an axiom. If it could be proved from the other axioms, we would not have to assume it as true. If it could be disproved, we could not assume it as true. Fraenkel showed in 1922 that the axiom of choice could not be proved, by proving that it was consistent for the axiom of choice to be false. Cohen strengthened this result in 1964 using a powerful technique known as forcing. Meanwhile, Gödel showed in 1940 that the axiom of choice could not be disproved, by proving that it was consistent for the axiom of choice to be true. Together, these two results tell us that the axiom of choice is a genuine axiom, a statement that can neither be proved nor disproved, but must be assumed if we want to use it.
The axiom of choice has generated a large amount of controversy. While it guarantees that choice functions exist, it does not tell us how to construct those functions. All the other axioms that tell us that sets exist also tell us how to construct those sets.
For example, the powerset operator is very well defined. Given a set X , the powerset P (X ) is the set of subsets of X. The powerset is obviously uniquely defined, and if anyone were to give you a set, you could figure out what its powerset was directly. Such is not true with choice functions. There are many choice functions for a particular set, and it is not always obvious how to find a choice function for a particular set.
What makes the axiom of choice even more controversial is the Banach-Tarski paradox, a non-intuitive consequence of the axiom of choice. It says that if we accept the axiom of choice, it is possible to cut up a sphere into a dozen or so pieces and rearrange the pieces like a tangram to get two spheres each the same volume as the first. This is very counterintuitive. Clearly, we cannot assign all of the pieces mass, or we would get a violation of the conservation of mass. However, when one looks at the pieces, which are non-constructive and fractal, it should perhaps surprise us less that this is possible.
Despite these reasons why we might wish to reject the axiom of choice, when we look at its equivalents, we find several intuitive and highly desirable statements. For instance, the well-ordering principle, which allows us to list out the elements of any set in order, implies and is implied by the axiom of choice. Note that well-ordering a set requires an infinite number of arbitrary choices, which we should expect. Other equivalent statements include the Vector Space Theorem (every vector space has a basis), Zorn’s Lemma, and the Principle of Compactness. Zorn’s Lemma is a very useful theorem related to induction on infinite sets. The Principle of Compactness says that given a set of statements such that any finite subset holds true for some set, then the whole set of statements hold true for some set.
One troublesome aspect of set theory is that there are many ways to satisfy the axioms of set theory. This is a consequence of Gödel’s Incompleteness Theorem. A collection of sets that satisfies the axioms of set theory is called a model of set theory. For example, the collection of sets that can be explicitly constructed only using the operations of set theory forms a model of set theory for the standard set axioms with the axiom of choice. In this case, we can tell two sets apart by looking at their constructions. We do not need to worry about having to choose between two indistinguishable sets, so there are no arbitrary choices that need to be made. In larger models, the status of the axiom of choice is more interesting. The situation can range between all sets having choice functions, and only sets with constructable choice functions having choice functions.
Between these two extremes is a vast space of possibilities. I am working on mapping out this space, looking at how the various equivalents are related. For instance, if we know the axiom of choice fails in some strong way, what does that tell us about the vector space theorem? I will prove the following are equivalent:
• (NAC): There is some countable set X of pairs with no choice functions on any infinite subset. That is, we have an infinite set of pairs of socks, each labeled with a natural number, such that we cannot pick an infinite number of socks out without picking two from the same pair.
• (NWO): There is a countable set of pairs with no infinite well- orderable subset. That is, we have an infinite set of pairs of socks, but cannot find a way of lining an infinite number of the socks up in a row, even though each pair is labeled with a natural number.
• (NVS): There is some real normed vector space V, spanned by countably many 1-dimensional subspaces, with no infinite linearly independent subset.
A set is said to be countable if we can assign a unique natural number to each element of the set. This is equivalent to being able to line up the elements of the set so they resemble the natural way the natural numbers are lined up. There is a whole theory behind countability and how to count the number of elements in infinite sets in general that is highly interesting but beyond the scope of this article. However, the only really important things to remember about countable sets (besides the definition) are: they are not finite (depending on your definition); they are not too infinite – for instance there are just too many real numbers for them to be countable; and they have a large amount of structure encoded in the well-ordering.
Proof: (NAC) ⇒ (NWO)
Assume we have our countable set of pairs X with no infinite choice function. I claim that the union of this set, that is, the set of all socks, has no infinite well-orderable subset. That is, even though we can line up the pairs of socks so that one of them is the first pair, and one of them is the second pair and so on (just use the numbering on the pairs), we cannot line up an infinite number of individual socks in this way, picking one sock to be the first, another sock to be the second, and so on. We will suppose we can construct such a sequence and prove a contradiction.
Consider the set of all pairs from which at least one sock shows up in our sequence. I claim that this set is infinite, by a version of the infinite pigeon-hole principle – if you try to stick infinitely many pigeons into holes that only accept at most two pigeons each, you are going to need infinitely many holes. Similarly, we cannot fit all the elements of our sequence into only a finite number of our pairs of socks. I claim we can construct a choice function on this infinite set of pairs of socks. If only one sock in the pair shows up in our sequence, we just pick that sock. If both socks in the pair show up in our sequence, we pick the one that shows up first in the sequence. Thus we have produced an infinite choice function on a set we said has no infinite choice function, a contradiction, so our assumption that we could well-order an infinite subset of socks was false.
Proof: (NWO) ⇒ (NAC)
Suppose we have a countable set of pairs whose union has no infinite well-orderable subset. I claim that this set of pairs has no infinite subset with a choice function. That is, if we have an infinite set of pairs of socks that can be nicely ordered as usual, but cannot thusly line up any infinite set of socks, we also cannot pick out one sock from an infinite number of pairs. Again, we will suppose we can and prove a contradiction.
Consider the set of pairs from which we pick a sock. Construct an infinite well-orderable subset as follows. Let the first sock be the sock we picked from the first pair we pickedd a sock from. Let the second sock be the sock we picked from the second pair we picked a sock from. Since we picked a sock from an infinite number of pairs, we can keep doing this to construct an infinite well-orderable set of socks, contradicting our original assumption. So our assumption that we had an infinite choice function on our set was false.
In order for this next part about vector spaces to make sense, it is necessary to understand what a vector space is, and how a mathematician’s notion of a vector space differs from the naive notion of a vector space. Naively, a vector space is a collection of vectors, where vectors are n-tuples of numbers. So if we pick an n, 3 for instance, and a set for our numbers to come from, for instance, R, the real numbers, then we have a vector space, called R3 , which consists of all triples of real numbers.
This notion works well for finite (dimensional) vector spaces. However, mathematicians like looking at infinite vector spaces as well. To a mathematician, vector spaces are fundamentally about linear combi- nations. Given a finite set of vectors v1 , . . . , vn , a linear combination of them looks something like a1 v1 + a2 v2 + · · · + an vn , a sum of multiples of the vectors (some of the ai can be 0). A vector space is any set that is “closed” under this operation. For instance, every linear combination of triples of real numbers is also a triple of real numbers, so the set R3 is a vector space, as are all the other finite vector spaces.
However, strange sets, like the set of all sequences, also fall under this category. In order to resolve our new notion of vector space with the old naive notion, we need a basis. Every element of a vector space can be written as a linear combination of vectors from its basis in exactly one way, and the basis itself is linearly independent, i.e. no nontrivial linear combination equals zero. For R3 , the set {e1 , e2 , e3 } forms a basis, where ei has a 1 in the ith place and 0s everywhere else, since:
[a, b, c] = ae1 + be2 + ce3
Take, for instance, our three-dimensional real world. Points in our real world do not have any special coordinates associated with them, but once we pick a set of three vectors corresponding to the unit x, y, and z axes, we can write our points in terms of triples of coordinates. This is the purpose bases serve: they allow us to take vector spaces and look at them from the more naive perspective of coordinates.
Finally, I should mention a particularly nice vector space, R∞ (read: R-infinity). R∞ consists of all finite-length vectors, with the idea that to add together two vectors of different lengths, we add zeroes onto the end of the shorter one until they are the same length. For instance:
[a, b] + [c, d, e] = [a + c, b + d, 0 + e]
Or rather,
(ae1 + be2 ) + (ce1 + de2 + ee3 ) = (a + c)e1 + (b + d)e2 + ee3
A basis for this space is the set of all ei , since every vector can be written as a linear combination of finitely many of the ei . In fact, we can define R∞ to be the set of all linear combinations of finitely many ei . Note that linear combinations must always be finite.
Proof: (NAC) ⇒ (NVS)
Suppose we have a countable collection of pairs of socks X , with no infinite choice function. In our proof, we will construct a vector space similar to R∞, except we will be using our socks to do so. We will then prove that this vector space cannot have a basis.
Instead of constructing the set of all linear combinations of finitely many ei , we will construct the set of all linear combinations of our socks. This may seem a little strange. How do you add two socks? Well, how do you add e1 to e2 ? They do not add, so we just write the result as e1 + e2 . In our sock-space, we do the same thing, except we introduce a new rule: matching socks are negatives of each other. Yes, this is weird, but it gets the job done.
Suppose we had an infinite linearly independent set S in this vector space. If S was ordered, I could construct a choice function in the following way: given a pair of socks as input, if a sock from the pair we are looking at appears somewhere in S , then look at the first vector in S in which one such sock appears. Using simple identities, we can write this term as a positive multiple of one of the socks in the pair; for instance, if the coefficient is negative, we just write it as a positive multiple of the other sock. We pick this sock. If neither sock shows up anywhere in the basis, we do not define the choice function for that pair.
Nevertheless, I claim that we still have an infinite choice function. Suppose we had a finite choice function. That means only finitely many socks show up in an infinite linear independent set. Well, this is silly. We can specify a vector written as a linear combination of finitely many socks in terms of finitely many real numbers – the coefficients. So our infinitely many vectors come from a finite-dimensional space. You can have only at most n linearly independent vectors in an n dimensional space, so we have a contradiction.
So everything is all well and good if we have an ordered infinite linearly independent set. However, as we have seen, not all infinite sets need to be ordered. So what if S is not ordered? To each vector, we assign it a sock-number. The sock-number of a vector is the largest number on a sock needed to write the vector. We group the socks in S by their sock-number. Some of these groups will be empty, but infinitely many of them will be nonempty, and there is a natural ordering on them.
We note that each of these groups must be finite in size; as we have seen it is impossible to have only finitely many socks show up in an infinite linear independent set. For each nonempty group, we take its sum, which is nonzero since our S is linearly independent. The set of sums is also linearly independent; any non-trivial identity on our sums is a non-trivial identity on elements of S themselves. So we have an infinite ordered set of linearly independent vectors, as desired.
Proof: (NVS) ⇒ (NAC)
It turns out that every vector space satisfying the properties in the hypothesis looks like the sock-space constructed from some set of socks. Essentially, we look at the two vectors in each 1-dimensional subspace that have length one, and make those our pairs of socks. Obviously, they wind up being negatives of each other, and all of our pairs of socks span the space the way we want them to.
We know our sock-space does not have an infinite linearly independent set. Now suppose the set of socks our space is based upon has an infinite choice function, since we would like to show that it does not. Well, our choice function would give us an infinite collection of distinct socks, which are linearly independent. So there cannot be an infinite choice function.
Of course, in order for these proofs to mean something, we need to prove that there actually is a countable set of pairs without an infinite choice function. If our set of socks cannot exist, we can prove anything we like about it without meaning anything.
This is all just a formalization of the intuition we have about making arbitrary choices, working with our hypothetical set of infinitely many pairs of socks. Being able to make some infinite set of arbitrary choices allows us to make other arbitrary choices, and it is interesting when two infinite sets of arbitrary choices are equivalent in this sense. For instance, with the socks, if we can pick a sock from all but three pairs, we can just manually make those three extra choices. In continuing my research, I am looking for other interesting equivalences similar to the ones presented in this article.
For more information on Equivalents of the Axiom of Choice, see either my thesis “Equivalents of Failures of the Axiom of Choice,” or see the following references.
References
1. H. Rubin and J. E. Rubin: Equivalents of the Axiom of Choice II, North Holland Publ. Comp., Amsterdam (1985).
2. B. Russell: On some difficulties in the theory of transfinite numbers and order types, Proc. London Math. Soc. 2, 29-53 (1906).