Mathematical logic seminar - November 13, 2002

It is the working assumption of set theorist that sets of reals whose existence is solely granted by the Axiom of Choice are in general pathological, as opposed to those which can be `explicitly' defined.

A well-ordering of the reals (w.o.) is an example of such sets. Choice guarantees that the reals can be well-ordered, but no w.o. is Lebesgue measurable or has the Baire property. A natural question to ask is how difficult is to define a w.o.

The answer is heavily dependent on the particular universe of sets one considers. For example, in Godel's constructible universe, the reals admit a w.o. whose complexity is Sigma-1-2, i.e., one whose definition only requires of an existential and a universal quantifiers ranging over reals, followed by an arithmetic relation. Any set of reals whose definition is simpler (say, Sigma-1-1) is Lebesgue measurable, and therefore cannot be a w.o. On the other hand, if the reals admit a w.o. of such complexity, then every real belongs to the constructible universe, a situation which contradicts the standard picture of the universe set theorists share.

In this talk I will present some results (due to Woodin, Abraham, Shelah, Solovay, and myself) illustrating the interplay between the combinatorial properties of the universe and the definability of w.o.'s.