4.4. Infinity and the axiom of choice

The undecidability of the axiom of choice

As the powerset allows to write bounded formulas to mean what may otherwise in simple cases be understood as mere statements with open quantifiers (and even escape that altogether in more complex cases), the persisting relativity of their meaning explains how these formulas may remain undecidable.
Thanks to the completeness theorem, the unprovability of a formula, respectively its irrefutability also called "consistency" (the consistency of the theory where it is added as an axiom), amounts to the existence of models where it is false (resp. true), and the construction of such models is actually the way in which undecidability results are usually proven. But for set theories and other founding theories, for which the incompleteness theorem kills any hope of ever proving their consistency in the absolute, we only talk about the relative consistency of a statement, which means that the theory with that added axiom remains consistent if it was consistent without it.
In particular, a big success of mathematical logic has been the proof (much too difficult to be explained here) of the independence of AC in set theory: each universe where it is true includes another one where it is false, and vice versa. Both sides of this result were proven separately as follows.

In 1938, Gödel proved the relative consistency of AC by showing that any universe includes one where AC is true (with the same ∈ but a different powerset). It is defined as the class L of "constructible" sets, obtained by successively adding sets definable from previously defined ones, in such a way that it forms a universe. There, each nonempty set is only made of "constructed" objects, thus has a "first constructed element" that can be used as a choice. Any exception to AC in the external universe, in the form of a family of sets (Ai) with empty product, is absent from L because for some i, the whole set Ai is disjoint from L (it has no constructed element).

In 1966, Paul Cohen proved the relative unprovability of AC. The proof is even harder, so we cannot sketch it here. Let us only explain how, from a constructible universe, it is possible to produce different ones. Since Cantor's theorem holds in L while each construction step of "adding all definable sets" to a given countable part of universe can only add countably many sets, an uncountable infinity of steps is needed to fill uncountable sets; therefore, sub-universes can interpret "constructibility" differently, by admitting a non-standard countable model of this "uncountable" hierarchy of construction times, with respect to which the objects whose time of construction is not represented in the model, are considered unconstructible.

Before illustrating the possibilities for the axiom of choice to be false, let us mention the case where it must be true.

Proving the finite choice theorem

Let us finally give a sketch of rigorous proof of the finite choice theorem.
For any family of n nonempty sets (∀i<n, Ai ≠ ⌀) we have
B={kn| ∏i<k Ai ≠ ⌀} ⇒ (0∈B ∧ ∀k<n, kBSkB) ⇒ nB.∎

Axiom of dependent choice (DC)

The axiom of dependent choice is a statement stronger than AC. It says that, for any graph RE×E with domain E and any aE,

uE, u0=a ∧ ∀n∈ℕ, un R un+1.

This cannot be deduced from AC but it can be deduced from either ACE or the existence of a choice function on Im R. But focusing on Im R allows to keep it a set of nonempty subsets of E for the equivalent "generalized" expression of DC in the style of the above form of recursion :

n∈ℕ, (uk)k<n R un

whose change of Dom R would not let ACE suffice as a justification.

Injections of ℕ into infinite sets

The existence of a non-surjective injection from E to E, or equivalently an injection from ℕ to E, implies that E is infinite. But to prove the converse requires the axiom of choice.
An easy proof that any infinite set E has an injection from ℕ to E, uses the above extended expression of DC, more precisely a choice function on the set of complements of all finite subsets of E.

But it can also be deduced from the mere countable choice AC, picking a sequence t where each tn is an injection from Vn+1 to E. Indeed, this allows to determine a recursive sequence of all distinct elements as un = tn(i) for the smallest i such that tn(i)∉ {uk|k<n}.

Counter-examples to the axiom of choice

The possible counterexamples to AC are families of sets where an infinity of them are without choice tool (fixed formula for "this kind of" sets, that can systematically, throughout a collection of such sets, choose an element in each). The sets with no choice tool, are mainly
Indeed, in a finite set of subsets of ℕ, you may choose "the smallest one" for a total order roughly defined as the order between real numbers between 0 and 1, seeing subsets of ℕ as binary expressions of these numbers; but an infinite set of them needs not contain any smallest one for this order: if an infinity of them contain 0 while an infinity don't, you can select those which don't, then continue choosing between those which contain 1 and those which don't, but after an infinity of such exclusion steps you may end up with nothing at all.
Exceptions to AC may appear: In practice, DC, or even AC, may resolve most practical mathematical questions which depend on AC. The full AC only becomes important for higher, more abstract questions of set theory beyond ordinary purposes. It is then usually accepted as true for the questions that depend on it, as it intuitively feels more true and usually leads to rather uniform and effective consequences. Any statement of its falsity would beg for details about which kind of exceptions may it have, so as to reduce the margin of undecidability which occurs in its absence. Here is an important example.

AC vs measurability

The Lebesgue measure of the sets of reals have 2 properties: countable additivity and translation invariance. Specialists found that the statement that all sets of reals are Lebesgue measurable, does not contradict DC. But it contradicts AC for the following reason. Any choice function of the partition of ℘(ℕ) defined by the equivalence relation of finiteness of difference (A,B ↦ (AB is finite)), which can be seen in [0,1] as the equivalence relation of differing by a dyadic rational number, cannot be Lebesgue measurable (a candidate measure can neither be zero nor non-zero to fit both properties of Lebesgue measurability).
(The abstractness of this question may be debatable, as illustrated by this video in French).
Actually, the construction of the Banach Tarski paradox is based on a very similar use of AC as this one.

But as (unlike the powerset) the axiom of choice is unnecessary for the core (vital) constructions at the foundation of mathematics, we shall generally do without it in this work.


Back to homepage :
Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
4. Model Theory
4.1. Finiteness and countability
4.2. The Completeness Theorem
4.3. Non-standard models of Arithmetic
4.4. Infinity and the axiom of choice
4.5. How theories develop
4.6. The Incompleteness Theorem