To Infinity And...

So where is this hidden depth that makes this obvious axiom so controversial?

The answer is, and nearly always is in these cases, infinity.

If you have a finite collection of sets then you can prove that there is a choice function by induction - and you don't need the axiom of choice as it is a theorem of standard set theory. 

Things start to get a little strange when we work with infinite collections of sets. In this case, even if the collection is a countable infinity of sets, you cannot prove that there is a choice function for any arbitrary collection and hence you do need the axiom of choice. That is, to make set theory carry on working you have to assume that there is a choice function in all cases. 

In the case where you have a non-countable infinity of sets then things are more obviously difficult. Some non-countable collections do have obvious choice functions and others don't.

This only way to see what the difficulties are is to look at some simple examples.

First consider the collection of all closed finite intervals of the reals i.e. intervals like the set of points x satisfying a ≤ x ≤ b or [a,b] in the usual notation.Notice that the interval a to b includes its end-points, i.e. a and b are in the set due to the use of less-than-or-equals.This is an infinite and uncountable collection of sets but there is an obvious choice function. All you have to is define F([a,b]) as the mid point of the interval. Given you have found a choice function there is no need to invoke the axiom of choice.

Now consider a collection of sets that sound innocent enough - the collection of all subsets of the reals. It is clear that you can't use the mid-point of each subset as a choice function because not every subset would have a mid-point. You need to think of this collection of subsets as including sets that are arbitrary collections of points. Any rule that you invent for picking a point is bound to encounter sets that don't have a point with that property (note; this isn't a rigorous argument). You can even go a little further. If you invent a choice function, simply consider the sets that don’t have that point – they must exist as this is the set of all subsets!  (note; this isn't a rigorous argument). 

Now you can start to see the difficulty in supplying a choice function. No matter what algorithmic formulation you invent some sub-sets just wont have a point that satisfies the specification. You cannot for example use the smallest value in the sub-set to pick a point because open sets don't necessarily have a smallest value using the usual < relationship.  

So now the real problem is made clear - this is a problem to do with computability and this is why it is relevant to computer science. If there is no choice function for the collection of all subsets of the reals then the axiom of choice fails and so do all of the theorems that are proven using it. 

The axiom of choice simply asserts that there is such a function - it doesn't tell you how to find it. 

At the moment it looks as if the weight of mathematical opinion is that we can't find a choice function for the totality of sub-sets of the reals even though the axiom of choice insists that one exists. 

So this is a collection of sets where proof by intimidation (see the cartoon)  simply wouldn't be practical. 

Choice And Computability

If this sounds familiar from what you know of computer science then it should. The axiom of choice is roughly speaking asserting that the choice function is computable or realizable or whatever you want to call it even if we don't know what it is. In many cases where something is non-computable we can blame it on the fact that there aren't enough programs to go around. For example, there are only a countable number of programs, but there are an uncountable number of real numbers - hence the majority of real numbers aren't computable.

In this case though, the problem seems to be that the variability of the sub-sets is such that there isn't sufficient regularity for a program to specify one point in each subset. You might think that the solution is to allow computable functions that return an arbitrary point in the set, but it could be that there are sets so complex that there is no formal rule that can pick out such a point. For example, consider a set that is composed of just non-computable numbers - how can the choice function return one of them?

When you realize the connection between the axiom of choice and computability it seems less obvious that you can always exercise an arbitrary choice. Many mathematicians seem to satisfy themselves with a vague (or sometimes precise) idea that in situations like this the choice function could somehow be an arbitrary "pick one point of each set" - it doesn't matter what it is, just pick one. You can see that in simple cases the choice function is doing something we might be able to name - the mid-point, the smallest value, etc, but this new arbitrary choice function is more like a random selection.

British philosopher, logician and mathematician Bertrand Russell tried to explain this idea by the example of socks and shoes. If you have an infinite collection of pairs of shoes then the choice function could be either "pick the right shoe" or "pick the left shoe" with no need for the axiom of choice. Now consider a similar collection of pairs of socks. There is no obvious choice function because there is no way to distinguish between the socks making up the pair. In this case the axiom of choice has to be invoked to say that you can indeed pick a sock from each pair.

The sock example sounds reasonable, but is an arbitrary choice really a computable function? In the case of socks it seems reasonable, but in the case of all sub-sets of the reals it isn't as obvious. Consider for a moment the number line between 0 and 1, i.e. the closed set [0,1]. There are points that have “names” like ½, √2, and so on. However, as we have already revealed a number of times – the majority of the points don’t have a finite label. How can you then pick a point? Zoom in till you see a few points and then pick one of them “at random”? If you zoom in you always see an infinity of points. In fact, you always see an aleph-one of points. How can you pick one of something that forms a continuum? Only by giving a program or function that specifies the point can you “pick a point”. Of course, the program or function is a finite label for the point, so we have made no progress at all.

There are also many deep resonances here with other subjects. Do the pairs of shoes and socks remind you of the behavior of fermions and bosons? If you are a physicist, they do. The inability to provide a computable function without using a random choice in the case of the socks says something about algorithmic information, but what exactly isn't obvious. 

You can now also see why the axiom of choice comes into the proof of Zermelo's well-ordering theorem. If you can find a function that is irregular enough to pick an arbitrary point in each set then presumably there is no reason we can’t find a function that orders each set. In fact the two ideas, the axiom of choice and the well-ordering theorem, are equivalent – they both pick points from arbitrary sets.