The Axiom of Choice and Well-Ordering
Page last updated 25 Sept 2023
The Axiom of Choice and Well-Ordering
The so-called “axiom of choice” is an assumption that is sometimes used in set theories as the basis for an argument that gives a certain desired result. One of the most striking things about the term “axiom of choice” is the huge variety of different statements in circulation that are all claimed to be this axiom of choice. Furthermore, it is said that the terms “well-ordering”, the “axiom of choice” and “Zorn’s lemma” are all different sides of the same coin, since they all essentially amount to saying the same thing, but in different ways. One might wonder why there should be so many different versions of the same thing.
The reason for the original invention of what is now called the axiom of choice can be traced back 150 years to the writings of Georg Cantor, whose ideas were deeply influenced by his religious beliefs. Amongst his beliefs was his notion that all sets can possess what he called a “well-ordering” where every element has an “immediate successor” and where every set has a “first element” in this “ordering” (see for example Section 2 of Cantor’s Grundlagen). Although it was a crucial aspect of his philosophy and his theories, Cantor had no proof whatsoever of these notions, but he turned a blind eye to the difficulties and continued to make his claims, and his followers did likewise.
Cantor’s assumption of what he called “well-ordering” did not even have the virtue of having some sort of inherent plausibility - on the contrary, its implausibility is one of its principal characteristics, and this made it very troubling to Cantor and his supporters. The notion was closely associated with his belief that there could be limitlessly large sets with fewer elements than other limitlessly large sets, a belief that most mathematicians still hold today, despite the fact that there has never been a proof of this assumption. It is not at all surprising that there has never been any such proof, since the notion is directly contradictory, see Proof of more real numbers than natural numbers?
Cantor also believed that his “well-ordering” was some kind of an extension of the concept of counting by natural numbers. For example, although he had proved that the real numbers cannot be enumerated, his Grundlagen, Section 2 shows that he really believed the real numbers could nevertheless somehow be “counted” by his transfinite numbers.
The invention of the “axiom of choice”
There is an English translation by Stefan Bauer-Mengelberg: “Proof that every set can be well-ordered”, it is available in the book From Frege to Gödel, ed. Van Heijenoort, Harvard University Press, 1967, pp:139-141.
Zermelo subsequently published another “proof ” which supposedly clarifies some matters arising from the previous version, and includes a lengthy philosophical justification for the axiom of choice:
Ernst Zermelo, “Neuer beweis für die möglichkeit einer wohlordnung”, Mathematische Annalen Vol 65.1, 1907, pp.107-12.
There is an English translation by Stefan Bauer-Mengelberg: “A new proof of the possibility of a well-ordering”, it is available in the book From Frege to Gödel, ed. Van Heijenoort, Harvard University Press, 1967, pp:183-198.) Although this is called a theorem, it simply replaces the implausible claim of “well-ordering” by another implausible claim, which is the so-called “axiom of choice”, and which is simply another way of stating the same assumption. Only the gullible will be fooled by such chicanery. (Footnote: In his 1904 paper, Zermelo stated it as: “A set S that can be decomposed into a set of disjoint parts A, B, C, …, each containing at least one element, possesses at least one subset S1 having exactly one element in common with each of the parts A, B, C, … considered.”) (Footnote: Incidentally I note that at the time of writing, Jan 2022, Wikipedia states that ‘Georg Cantor considered the well-ordering theorem to be a “fundamental principle of thought”.’ with the source quoted as being from a Cantor work of 1883. This of course is incorrect, as Zermelo’s so-called “theorem” was only published in 1904.)
What is “well-ordering”?
A typical attempt at a description of “well-ordering” is:
A well-ordering on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. The set S together with the well-order relation is then called a well-ordered set.
Such attempts fail to provide any real clarification of the intended meaning of terms such as “order”, “least” and “ordering” in the context of the expression. Clearly, it cannot mean that the elements can be enumerated, since the set of real numbers, for example, cannot be enumerated, yet it is assumed that they can be “well-ordered”. The description is written in such a way that the reader is nudged into mentally jugging some sort of association of the terms “order” and “ordering” with the well-defined notion of enumeration, but somehow without any enumeration. The reader is also expected to mentally juggle the term “least” as having some sort of isomorphism to the well-defined notion of numerically smaller, but there is no clear statement as to how this might be the case.
This is not insightful mathematics, and it fails to provide a satisfactory underlying philosophical basis.
A statement of the axiom of choice
The basis for the usage of the term “choice” can be seen to have arisen from a consideration of finite sets - for a finite quantity of sets it is a simple matter to define another set by choosing a particular element from each one of the sets - one can simply list a selection by choosing an individual element of each set.
However, for infinite sets things are not so simple, and clearly, one cannot define a set by making infinitely many such choices. This is why it was rather unfortunate that the term “choice” was used (and continues to be used) to indicate a notion where choice is not involved at all, unless one wants to assume that there is some sort of deity or other metaphysical being that does the choosing. Hence it is better to avoid any use of the term “choice”, and indeed it is better to avoid any suggestion whatsoever that choice is involved.
The key point is that whatever the notion of the “well-ordering” of a set might be, it has to be something that must depend on the properties of the elements of the set. The acknowledgment of this key point leads directly to a clarification of the intention behind terms such as the “axiom of choice” and “well-ordering”. The principle can be summarized quite simply in a statement such as:
We assume that every element of every set has a specific quantity of an indefinable variable property, where:
- no two different elements can ever have the same quantity of the indefinable property, and
- in every set there is always one element with the smallest quantity of that indefinable property.
While one can immediately see that the notion of “ordering” implies some such indefinable property, one should not be side-tracked by the use of the term “ordering”, because this indefinable property is completely unlike any normal ordering. It assumes that for every element of every set the indefinable property “exists” completely independently of any properties that are actually defined for that element, and which “exists” completely independently of any human or machine.
Furthermore, its nature is that it can never be defined - unlike orderings for which there are associated natural numbers, where there is a first, a second, a third, and an nth for every item in the ordering. For example, according to the axiom of choice real numbers are assumed to have this indefinable property, but at the same time this indefinable property has no definable relationship whatsoever to numerical quantities; if there could be such a definable relationship, then the real numbers could be enumerated, which is impossible as shown by Cantor’s 1891 diagonal argument and his 1874 non-denumerability proof. It follows that Cantor’s assumption that every set could be “well-ordered” is an assumption that there “exist” some sort of functions that bestow the “existence” of non-existing properties onto elements; this in turn requires that such functions must necessarily be indefinable. (Footnote:
One might be bemused by the fact that Cantor also appeared to reject the notion of indefinable entities. He wrote in a letter:
‘Infinite definitions (which are not possible in finite time) are absurdities. … Am I wrong or am I right?’
Letter to Hilbert, 1906, quoted in the book Cantor, ed. Herbert Meschkowski and Winfried Nilson, Briefe Berlin: Springer, 1991.) Note that by the assumption of the indefinable property there must be one real number that has the smallest quantity, of all real numbers, of the indefinable property.
Conventional attempts to state the axiom of choice are careful to try to avoid any suggestion of mysticism or magic that are implicit in the assumption of a property which is both indefinable and also completely independent of the definitions of a mathematical system. An example of a favored “definition” which superficially appears to avoid any such implication is by way of the notion of what is called a “choice function” where a typical definition is:
For any set X of nonempty sets, there exists a choice function f that is defined on X and maps each set of X to an element of that set X.
That means that for every set whose elements consist of an infinite quantity of sets, the claim is that there is a function that can specify, for each individual set, one specific element of that set. The expression hides the fact that at least some such functions must be some sort of magical functions that can never be defined, and which ‘exist’ as metaphysical Platonist ‘things’ that are completely independent of any human or machine.
This is because, for sets of numbers, the only property that any number has is its numerical property, and it has no other distinguishing properties. And although some aspects of that numerical property can be referred to, there is no aspect of the numerical property of a real or rational number that can, for example, always make it the smallest number in any set of numbers. That means that some other property is required by the magical function - a magical property that is to be found nowhere in the definition of a well-defined mathematical system - and this is why it has to be added on as a magical axiom. The term “ordering” is not in fact well-defined where it is used in relation to “well-ordering” and the axiom of choice, and in fact it relies on an implicit assumption of the existence of a magical indefinable property.
We can also observe that, in the same way that it is impossible to define an infinite set unless one refers to a property that is common to infinitely many elements (see One-to-one Correspondences and Properties), it is also impossible to define a function whose domain is a set of infinitely many elements unless there is a property that is common to the infinitely many elements of that domain that the function can refer to. And since the magical property is undefinable - the property does not actually exist - the magical function is indefinable.
Logical Principles and Contradictions
“In first place we here consider the objections that are directed against the ‘postulate of choice’ formulated above and therefore strike at both of my proofs in the same way. I concede that they are to some extant justified, since I just cannot prove this postulate, as I expressly emphasized at the end of my note, and therefore cannot compel anyone to accept it apodictically.”
And in fact, in that paper, he himself gives us reasons as to why we should reject it:
“Actually, principles must be judged from the point of view of science, and not science from the point of view of principles fixed once and for all.”
“Thus, in order to reject such a fundamental principle, one would have had to ascertain that in some particular case it did not hold or to derive contradictory consequences from it;”
As pointed out on this page, the Banach-Tarski contradiction does provide us with a good reason to consider that the Axiom of Choice is neither unobjectionable nor logical.)
However, since the axiom of choice is a claim that mathematical objects possess magical properties, it should come as no surprise whatsoever that by various manipulations contradictions can be generated, such as the Banach-Tarski contradiction where the volume of one sphere is proved equal to the volume of two spheres, where all three spheres are identical - a result that any magician would be proud to achieve. (Footnote:
Most mathematicians prefer to call this a paradox rather than a contradiction, and maintain that within conventional set theory, it is not contradictory. In fact, many mathematicians call it the Banach-Tarski “theorem”, and appear to be delighted rather than appalled by its contradictory nature. The original paper (in French) can be seen at PDF Sur la décomposition des ensembles de points en parties respectivement congruentes by Stefan Banach & Alfred Tarski, Fundamenta Mathematicae 6: pp.244‑277, 1924.
For more on set theory, see the pages that give an overview of set theory, starting at Overview of set theory: Part 1: Different types of set theories.)
A few years after his first paper on well-ordering, Zermelo published another paper which included an attempt to justify his axiom of choice by remarking that it could be used to prove various results that he deemed desirable, (Footnote: See part 2 of Zermelo’s paper: “Neuer beweis für die möglichkeit einer wohlordnung”, Mathematische Annalen Vol 65.1, 1907, pp.107-12. There is an English translation by Stefan Bauer-Mengelberg: “A new proof of the possibility of a well-ordering”, it is available in the book From Frege to Gödel, ed. Van Heijenoort, Harvard University Press, 1967, pp:183-198.) and since then others have followed his lead, and try to justify the assumption by pleading that certain results that can be achieved by the use of the assumption are desirable. But this turns the entire ethos of mathematical proofs on its head - it is a classic case of the end becoming more important than the means.
A sensible and measured conclusion regarding the axiom of choice is that, in the same way that a belief in an afterlife or a god does not somehow make the belief correct, a belief in the axiom of choice does not somehow confirm that real numbers have a magical property that does not actually emanate from their definition.
It can be noted that the unfounded assumption of the existence of indefinable entities generally results in numerous problems, as can be seen at Indefinable Numbers, which analyses the problems arising from the notion of indefinable entities.
An example of the application of the assumption of the axiom of choice/
Bertrand Russell and pairs of socks
Attempts at explaining the notion of the axiom of choice often refer to an analogy first mooted by Bertrand Russell, where if there are infinitely many pairs of socks, and if one is to take just one sock from each pair, then the question arises as to how is one to choose which sock is to be taken in each case, since ideal socks of a pair might be said to have no distinguishing property.
“…when the number of classes concerned is infinite, we cannot make an infinite number of arbitrary acts of choice, and we cannot be sure that a selection is possible unless there is some intension which secures the desired result. I will give an illustration: there was once a millionaire who bought an infinite number of pairs of shoes and, whenever he bought a pair of shoes, he also bought a pair of socks. We can make a selection choosing one out of each pair of shoes, because we can choose always the right shoe or always the left shoe. Thus, so far as the shoes are concerned, selections exist. But, as regards the socks, where there is no distinction of right and left, we cannot use this rule of selection. If we are to be able to make a selection out of the socks, we shall have to adopt some much more elaborate method. We could, for example, find a point such that, in each pair of socks, one of the pair is nearer to this point than to the other. We should then obtain a selection by choosing from each pair the one nearer the point in question.”)
The failure to mention this aspect tends to obscure an important point, which is that for non-real world mathematical systems, the elements of sets have very well-defined and well-delineated properties, and those properties may not be such as to enable a selection over infinitely many such sets in some cases - in the same way that this would apply for infinitely many hypothetical non-physical socks that do not have any physical location. This is where the axiom of choice comes in, where despite the fact that there is no applicable distinguishing property over infinitely many elements, one pretends that all the elements possess some sort of magical property that bestows on the elements the notion of a function that can define a specific element for each set.