Russell's Paradox: Here's Why Math Can't Have A Set Of Everything

We recently wrote about how infinitely large sets are not all the same size as each other, but we were a bit vague about what we meant by a set.

The people who invented set theory also started out with a pretty vague idea of what sets are, and this vagueness led to some serious problems.

Mathematician Georg Cantor and the other early set theorists were operating in a world of what we now call "naive set theory". Their idea of what a set is was very loosely defined. We have an intuitive idea that a set should be a collection of things, and naive set theory basically takes this as the definition of a set.

Sets

There is good reason to have a fairly open-ended definition like this. We want sets to be extremely flexible objects, capable of taking on many roles in different parts of mathematics. A finite collection of variables, like {x, y, z}, should be a set. An infinite collection of numbers, like the natural numbers N = {1, 2, 3, 4, 5, ...} should also be a set. In geometry, we want the collection of all points between two given points - the line segment connecting the two given points - to be a set.

To make things more complicated, we also want to consider collections of sets. Above, we thought of a line segment in the plane as a set. So, in studying the geometry of line segments, we are analyzing the properties of the set of all line segments in the plane - a set whose component elements are themselves sets.

Sets Within Sets

In probability theory, we think of events as being sets of outcomes, and so a collection of events would also be a set made up of other sets.

Once they started nesting sets inside of other sets, the early set theorists considered an intriguing proposition - could a set contain itself as a member?

This comes about naturally from our open-ended, naive definition of a set. We have the set of all natural numbers. So, it makes sense that we would also have the set of everything that is not a natural number. This set would include quite a few things - the numbers -3, 1/2, and π are all not naturals, and so they would be members. The word "pizza" is not a natural number, so that would be a member. The state of California is not a natural number as well, so we would throw that in there too.

Since this set is itself pretty clearly not a natural number, but instead an enormous collection of everything ever that is not a natural number, it must be a member of itself.

Indeed, with our naive definition of a set, it is tempting to consider a set of everything, or a set of all sets. Naturally, being itself a set, the set of all sets would also have to contain itself as an element.

Russell's Paradox

Around the turn of the century, analytic philosopher extraordinaire Bertrand Russell identified a serious problem with this idea, known as Russell's Paradox.

Let's start by looking at the set of all sets that contain themselves as elements, and let's call this set A. We've seen a couple members of A - the set of everything that is not a natural number, and the set of all sets.

Does A contain itself? This is a bit of a problem, since the answer could go either way. If A contains itself, then great! A satisfies the condition we set up for being a member of A - containing itself. If A does not contain itself, no problem there - if A doesn't contain itself, then A doesn't satisfy the condition for being in A. This is an undecidable proposition - something that, given what we know, we cannot prove or disprove either way.

Undecidable propositions, while a little uncomfortable feeling, are not enough to constitute a paradox that completely blows up a logical system. The question of whether or not the set of self-containing sets contains itself just lies outside the scope of our system. So far, naive set theory seems to be holding up elsewhere, so we are still okay.

The paradox comes in when we think about the inverse of A - the set of all sets that do not contain themselves as members. Let's call this set B.

Does B contain itself?

We are now in trouble. Suppose B contains itself as a member. We defined B, however, as the set of all sets that do not contain themselves. So if B does contain itself, it goes against the condition we used to define B, and thus B does not contain itself.

But then if B does not contain itself, it does satisfy the condition to be a member of itself, and so it would have to contain itself!

This gives us a contradiction - the set of all sets that are not members of themselves simultaneously must and cannot be a member of itself. This contradiction makes naive set theory inconsistent - we have a statement that has to be simultaneously true and false.

This paradox, and other problems that emerge from having sets that contain themselves as members, and from having giant, poorly defined sets of everything, led to a more formal axiom-based idea of what sets are.

Modern Set Theory Axioms

The modern set theory axioms are very specific about how to build sets out of other sets. In particular, the axioms very quickly forbid a set from being a member of itself. We are also much more careful with constructions like "the set of everything that is not a natural number". Rather than using a broad universe of "everything", sets like this must be constructed as subsets of a larger set that we have already defined. So, I can define the set of all real numbers that are not natural numbers, but I cannot make a set of "everything" that is not a natural number.

Despite these restrictions, the modern set theory axioms are still sufficiently flexible that, combined with the rules of formal logic, they provide a solid grounding for basically all of modern mathematics.

Russell's Paradox and its resolution in modern axiomatic set theory show how our understanding of mathematics evolves and is refined over time. We often start with some intuitive idea of how something should work, but then see something strange or paradoxical in our intuition, and then find a way to deal with the strangeness or fix the problem.