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

We shall show later that the axiom of choice implies the existence of a well-ordering on all sets. This is a bit difficult to prove but the converse is simple:

If all sets can be well-ordered then the axiom of choice can be deduced in the following way. If ∀x∈E, ∃y∈F, xRy, then with a well-ordering on F we can define f from E to F by f(x) = the smallest y such that xRy.

Thus without the axiom of choice we cannot assume that
ZF-ordinals which are cardinals represent all cardinals.

∀*n*∈ℕ, ∀*u*∈*H*, ∀*y*∈*E*, ∃*v*∈*H*,
*v _{n}*=

∀*R*⊂ℕ×*E*^{2}, ∀*n*∈ℕ,
(∀*i*<*n*, ∀*x*∈*E*, ∃*y*∈*E*, *R*(*i*,*x*,*y*))
⇒ ∀*a*∈*E*,
∃*u*∈*H*, *u*_{0}=*a* ∧ ∀*i*<*n*,
*R*(*i*,*u _{i}*,

As a particular case, comes the finite choice theorem written as

∀*R*⊂ℕ×*E*, ∀*n*∈ℕ,
(∀*i*<*n*, ∃*y*∈*E*, *R*(*i*,*y*))
⇒ ∃*u*∈*H*, ∀*i*<*n*,
*R*(*i*,*u _{i}*).

{(*n*,*u _{n}*) | (

- ∀
*R*⊂ℕ×*E*^{2}, (∀*n*∈ℕ, ∀*x*∈*E*, ∃*y*∈*E*,*R*(*n*,*x*,*y*)) ⇒ ∀*a*∈*E*, ∃*u*∈*E*^{ℕ},*u*_{0}=*a*∧ ∀*n*∈ℕ,*R*(*n*,*u*,_{n}*u*_{n+1}). - ∀
*R*⊂*E*^{2}, Dom*R*=*E*⇒ ∀*a*∈*E*, ∃*u*∈*E*^{ℕ},*u*_{0}=*a*∧ ∀*n*∈ℕ,*u*_{n}*R**u*_{n+1}. - ∀
*R*⊂*E*^{2}, Dom*R*=*E*⇒ ∃*u*∈*E*^{ℕ}, ∀*n*∈ℕ,*u*_{n}*R**u*_{n+1}. - Any relation not well-founded has a descending sequence (while the converse was already seen)

Being not well founded, means ∃

3. ⇒ 4. as any descending sequence of

4. ⇒ 3. with

DC implies AC

DC as expressed by 2. can be deduced from AC

Sometimes DC needs to be expressed in the generalized form ∀

DC is equivalent to a form of the Lowenheim Skolem theorem, stating that any system with countable language has a countable elementary subsystem. To deduce this statement from DC, the elementary countable subsystem comes as the union of a sequence of countable subsystems, each chosen to satisfy the truth of formulas with parameters in the previous one. The converse is quite easy. Reference : paper by Asaf Karagila - message and paper by Christian Espindola.

In practice, DC, or even AC

- DC gives the existence of a sequence such that ∀
*n*∈ℕ,*u*_{n}∉ {*u*}_{k}_{k<n}(by a choice function on the set of complements of all finite subsets of*E*); - AC
_{ℕ}suffices: if there exists a sequence*t*where each*t*_{n}is an injection from V_{n+1}to*E*, then there exists an injective sequence*u*such that*u*_{n}=*t*(min{_{n}*i*|∀*k*<*n*,*t*(_{n}*i*) ≠*u*_{k}}).

- Sets of several pure elements (these do not exist in ZF where all elements are sets)
- Infinite subsets of ℘(ℕ) (precisely, infinite sets of unconstructible 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 ℘(ℕ) cannot be.

But the image of this function, that is a set made of one representative per equivalence class, cannot be Lebesgue measurable (a candidate measure can neither be zero nor non-zero to fit both properties of Lebesgue measurability).

Actually, it is a very similar use of AC to this one that is used in the construction of the Banach Tarski paradox, where the non-mesurability of sets is just more spectacular.

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. Development of theories : definitions

4.5. Constructions

4.6. Second-order logic

4.7. Well-foundedness

4.8. Ordinals and cardinals

4.9.Undecidability of the axiom of choice

4.10. Second-order arithmetic

4.11. The Incompleteness Theorem