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
(*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 present two results which do not depend on it.

For any family of

Such a bijection can be defined as

It is easy to understand once

∃*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

3.1. Morphisms of relational systems and concrete categories

3.2. Special morphisms

3.3. Algebras

3.4. Algebraic terms and term algebras

3.5. Integers and recursion

3.6. Arithmetic with addition

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