4.3. Infinity and the axiom of choice

The undecidability of the axiom of choice

The lesson of the completeness theorem is that the decidability of a formula in a theory, can be reformulated in terms of the existence of models where it is true or false, and this is actually the way in which undecidability results are usually proven. In particular, a big success of mathematical logic has been the proof (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.

In 1938, Gödel proved the relative consistency of AC by showing that any universe includes another one where AC is true (with the same ∈ but a different powerset). It is defined as the class L of "constructible" sets (that can be 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 showed that AC is unprovable in ZF. The proof is even harder, so we cannot sketch it here. The general possibility to make it would seem intuitively clear exept for why it does not conflict with how the constructible universe L satisfies AC. Here is the explanation: since Cantor's theorem holds in L while each construction step can only add countably many sets to a given countable universe, an uncountable infinity of steps is needed to fill uncountably infinite sets; therefore, a non-standard countable model of this uncountable hierarchy of construction times results in the possibility to omit constructible objects whose time of construction is not represented in the model.

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. Infinity and the axiom of choice
4.4. Non-standard models of Arithmetic
4.5. How theories develop
4.6. The Incompleteness Theorem