Lesson 5

Arguably the first big leap in logic was the attempt to characterize the notion of a set by Georg Cantor. Cantor's set theory essentially defined sets intuitively–A set is a collection of things that are defined by some axioms.

Mathematicians began to rely heavily on this concept of a set defined by axioms by the turn of the century, and it proved to be very useful. For example, distilling out the concept of a set allowed mathematicians to more easily talk about sets that contained other sets. In particular, Dedekind and Cantor together used this new paradigm to formalize the concept of the real numbers; they each defined the real numbers in a different way as a set of sets. These were the first truly rigorous and modern definitions of the reals, and they used these definitions to discover many of the real numbers' most important properties. In short, they discovered extremely important facts about the mathematical world and finally put a fundamental concept in mathematics on stable, modern footing.

Well, not quite… It turns out that Cantor's intuitive set theory simply doesn't work–It allows you to define paradoxical objects, and is therefore inconsistent.

The classic example is Russell’s paradox: Bertrand Russell pointed out that if a set can contain other sets, then surely it can contain itself. Russell then considered the set of all sets that do not contain themselves–Call it \(S\). Russell then asked “Does \(S\) contain itself?” If \(S\) contains itself then it should not be included in \(S\) by definition, but then it doesn't contain itself, which means that it should be included in \(S\) by definition, which means it contains itself...

This particular paradox might seem a bit cheap, but it's merely the simplest example in a long list of paradoxes discovered in what is now called naive set theory. Because such objects exist in naive set theory, the theory allows you to “prove” two contradictory facts (e.g., that \(S\) contains itself and doesn't contain itself). Obviously, nothing “proven” in such a theory can be trusted because someone might “prove” its opposite as well! Indeed, it's not hard to see that any fact, true or false, can be “proven” starting from naive set theory.

In the terminology of logicians, naive set theory is inconsistent.