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

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
(*A _{i}*) with empty product, is absent from L because for
some

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

For any family of

∃*u* ∈ *E*^{ℕ}, *u*_{0}=*a* ∧ ∀*n*∈ℕ,
*u _{n}*

∀*n*∈ℕ, (*u _{k}*)

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 *t*_{n} is an injection from
V_{n+1} to *E*.
Indeed, this allows to determine a recursive sequence of all distinct elements
as *u*_{n} = *t _{n}*(

- Sets of several pure elements (these do not exist in ZF where all elements are sets)
- Infinite subsets of ℘(ℕ), namely (roughly speaking for intuitive understanding) made of undefinable subsets of ℕ.
- Subsets of ℘( ℘(ℕ)), more precisely sets of such infinite subsets of ℘(ℕ).

Exceptions to AC

- By the existence of an infinite set into which ℕ has no injection (a universe with such an infinite set of pure elements is easy to make; I am not sure of this possibility in a universe of ZF, which has no pure element).
- in the form of a formula
*F*(*x*,*y*) with variables*x*∈ℕ and*y*∈ ℘(ℕ) such that ∀*x*∈ℕ, ∃*y*∈ ℘(ℕ),*F*(*x*,*y*), where the formula*F*has at least 3 quantifiers (according to this reference, at least for second-order arithmetic, I don't know otherwise) - ℘(ℕ) may
be a countable union of countable sets ! while AC
_{ℕ}implies that any countable union of countable sets is countable, which ℘(ℕ) is not according to Cantor's theorem.

(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.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