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

For any family of

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

Sometimes DC needs to be expressed in the generalized form ∀

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.

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. Second-order logic

4.7. The Incompleteness Theorem