Chocolates From the Trays:
The Axiom of Choice
The Question:
There is a famous shop in Zurich for all things chocolaty, called Sprüngli. Behind the counters, well protected by glass covers, are trays of pralinés and truffles, dark chocolates with pistachioes on top, chocolate covered orange slices, marzipan filled cubes and many more delicacies.
Customers point to the various trays and the neatly uniformed salesladies wielding tongs, pick one item from each of the trays to which the customers point. Then the chosen items are packed into little cardboard boxes and the happy customers leave with neat little packages filled with the goodies.
Right?
The Paradox:
According to some mathematicians, no, this is not right. In fact, according to their deeply held conviction, this is impossible.
Huh? I myself have gone through this procedure at Sprüngli many, many times, so how can anybody claim that I am unable to get the chocolates? Well, fortunately some mathematicians say that it is possible. Aha, so what exactly is possible according to some mathematicians, but impossible according to others? It’s the ladies wielding the tongs, that’s what.
The problem is that while the confections in the various baskets differ from each other, within each basket the delicacies are identical. The Amandines, the Nougatines, the Visitandines – each one quite unlike all the others – are indistinguishable among themselves. So how can the saleslady make a choice as to which Almond cookie to put into the box? Unsure which exact item to pick, she must be at a loss at every customer request, just like Buridan’s Ass was, immobilised between the two bales of hay. (See chapter ////). Only if the customer specifies “the leftmost Florentin”, or “the second Luxemburgerli from the bottom”, can she make her pick. It simply won’t do to say “please just give me one of those Champaign Truffes”.
The theoretical debate whether the salesladies are able to pick items from the various trays or whether they will hesitate at every request has kept philosophers and mathematicians busy for decades…though you would not believe it when observing the hustle and bustle at Sprüngli’s in Zurich.
An example by the philosopher Bertrand Russell renders this counterintuitive assertion – that it is impossible to make selections – more comprehensible. Lord Chichester has a big collection of shoes and must decide which pair to wear to the Queen’s Garden Party. To make up his mind, he asks his butler to bring exactly one shoe from each of the pairs. The butler has no problem with this request: he simply brings the left shoe of each pair for the lord’s appraisal.
Now for suitable socks. Lord Chichester asks the butler to bring one sock from each of the pairs of his sock collection. This time, the butler does have a problem. Which sock should he choose? Within each pair, the two socks are identical. As I shall describe below, in order to be able to follow the lord’s instruction the butler requires the so-called Axiom of Choice. Only if he accepts it, can he bring one sock of each of the pairs.
Background:
The deep mathematical question is whether choices can be made automatically, even if the number of trays is infinite. As pointed out above, some mathematicians believe they can, others believe they cannot. It is an indisputable fact, however, that the salesladies at Sprüngli’s are able to make choices among identical items (...albeit for a finite number of trays). Hence, the group of non-believers must somehow come to terms with this phenomenon.
It was the mathematician Ernst Zermelo (1871-1953) who provided the answer. Zermelo investigated a conjecture by Georg Cantor, the founder of set theory, which stated that every set of objects can be well ordered. In simple terms, his ‘Well Ordering Principle’ means that for any set there exists an ordering, such that a smallest element within that set can be identified. In a bit of a roundabout reasoning, this provides the loophole out of their dilemma for butlers, salesladies, but mainly for doubtful mathematicians.
Dénouement:
So what’s the way out for the conflicted mathematicians? On the one hand, they think that choices cannot be made; on the other hand, the salesladies at Sprüngli’s obviously do make these choices. The way out is typical for mathematicians: simply assume that choices can always be made. Even better, stipulate it as an axiom: “For any set X of nonempty sets [i.e., for all the trays filled with goodies at Sprüngli’s] there exists a choice function f defined on X [i.e., some sort of intuition tells the salesladies which item from the tray to choose].” The axiom states that a choice can always be made, without specifying how.
This is what Russells illustrated with the shoes and socks example: whenever a selection rule can be stated, as for example “always select the left shoe”, the axiom is not needed. But when no such rule can be specified because the items have no distinguishing features – as, for example, in “bring me a sock” – the axiom that he or she actually can make such a choice is required before the butler, the Sprüngly saleslady, the mathematician can proceed.
The Axiom of Choice is one of the most discussed axioms of mathematics. Many theorems utilize it in their proofs, some of them nearly without taking notice. Its importance is comparable to the importance in geometry of Euclid's parallel postulate. With it, we have geometry as we know it. Without it, we get elliptic and hyperbolic geometries. Similarly, with the Axiom of Choice many theorems can be proved. Without it, the theorems may be wrong. (See also the chapter on Shelah and Soifer.) By and large, the mathematical community accepts the Axiom of Choice nowadays. Hence, even those theorems that require it in their proofs are considered correct.
Technical Supplement:
Zermelo proved that the Axiom of Choice is true if one assumes that the ‘Well Ordering Principle’ is true. And vice versa.
But how can every conceivable set be well-ordered? Does, say, the set of real numbers have a smallest element? No, the set of real numbers does not have a ‘smallest’ element in the usual sense of the word because for every teeny-weeny number that you can think of, there exists an even smaller one. But that’s not the point. The ‘Well Ordering Principle’ simply says that if one accepts the Axiom of Choice, then there exists some kind of ordering and according to this ordering there exists a ‘smallest’ element. How the elements of the set are ordered – alphabetically, numerically, by temperature, by color… – and what ‘smallest’ means in terms of that ordering, is left unspecified.
All this may be confusing but human intuition does not always follow what is mathematically correct. The Axiom of Choice agrees with the intuition of most people; the Well Ordering Principle is contrary to the intuition of most mathematicians.
However, we may get an inkling of how the two are equivalent. The Well Ordering Principle says – without further specification – that there is some order which allows the smallest element to be picked. The Axiom of Choice says – without specifying how – that a choice can be made. If one can do one, one can do the other.
The problem with the Axiom of Choice is that it sometimes leads to counterintuitive results: see, for example the chapter on the Tarski-Banach paradox.
Comments, corrections, observations:
