Axiom of Constructibility

There is a discussion at the Everything Seminar about everyone’s favorite topic, the axiom of choice. The axiom of choice has various pathological consequences, such as the Banach-Tarski paradox and the existence of a non-Lebesgue-measurable set. The problem, everyone notes, is that by its very nature constructions that depend on the axiom of choice cannot be given explicitly. It’s tempting to dismiss the axiom of choice on those grounds as illegitimate (as Lebesgue himself did).

This philosophy can be taken further. What if we restrict ourselves to sets we can construct explicitly? One answer leads to constructivism, which entails rejecting many other basic principles of mathematics, such as the law of excluded middle, and has a dramatic impact on how every branch of mathematics is developed. A less dramatic course of action was proposed by Gödel: the axiom of constructibility. Gödel analyzed the types of sets that you can construct from a given collection of sets in terms of nine explicitly-given functions (these are familiar operations such as taking the direct product of two sets, or taking the image of a function between two sets). Gödel then defined a universe of sets in stages. At each stage, the sets defined by repeatedly applying the operations to the sets from the previous stage. He then iterated the construction of stages (allowing the stages to indexed by ordinals) to build the constructible universe. Any explicitly given set will appear somewhere in the constructible universe. The axiom of constructibility is that every set is in the constructible universe.

What happens to the axiom of choice under the axiom? It becomes a theorem. Even more amazingly, you can define a single well-ordering over the entire universe of sets. Choice functions can be found using the well-ordering. You can even define the well-ordering reasonably explicitly: at each stage, you define each new set in terms of a finite number of the nine operations on the old sets, so to order the sets at each stage you just need to define an order on the operations. You extend this to the whole universe by defining sets that first appear at later stages to be bigger than sets from earlier stages. To find an example of a non-measurable set, or the paradoxical decomposition in the Banach-Tarski paradox, you can just take the first one under the well-ordering.