## Universal sets and the Russell paradox

by

I was working with some students on set theory recently, and we were momentarily puzzled by their textbook’s definition of subset:

Let A and B be two sets contained in some universal set U. […] The set A is a subset of a set B if each element of A is an element of B….  More formally, A is a subset of B provided that for all x ε U, if x ε A then x ε B.

What threw us was the reference to a universal set U.  Why bother with that?  Why wouldn’t we just quantify over all x in A, instead of all x in U?

After a bit of thought, I realized there were a few reasons:

1. This makes defining set equality a bit cleaner:  A=B provided for each x in U, x ε A iff x ε B.  (If we didn’t have a universal set U to refer to, we’d presumably have to do two separate if-then statements, one quantifying over A, the other over B.)
2. It places the formal discussion of set theory in the familiar setting of Venn diagrams.
3. It sets the stage for dealing with set operations (union, intersection, and especially complements).

There is a 4th reason:  a desire to avoid impredicative definitions (according to the Oxford Dictionary of Philosophy, “Term coined by Poincaré ; for a kind of definition in which a member of a set is defined in a way that presupposes the set taken as a whole”;  more loosely, definitions that can potentially be self-referential).

Sidestepping the technicalities,   I wondered if we could easily craft a compelling reason to work within a universal set: what are the consequences of ignoring it?  The obvious place to worry is in computing set complements.  And thinking about self-reference, I wondered what could go wrong in building Øc without reference to a universal set?

If we call that complement M (for “monster”, or “massively huge”, or…), we see a set that contains everything that isn’t in the empty set.   “Cool!”, you’re thinking — that’s a great choice for a universal set U!

Well, hold on a bit.  This M has lots of stuff in it.  17, and {17}, and cool mathy stuff like that.  But it also has my old 82 Impala, and every sock I’ve ever lost, and every subset of the set of all socks that I’ve lost.   Everything you can imagine is an element of M.

For that matter, M even contains itself as an element, since M contains every thing as an element.

Once you see that this monster has the bizarre property that MεM, you probably begin to worry.  Maybe we want a smaller universe, that only has the well-behaved stuff, those things in M that aren’t elements of themselves.

Thus we define $R := \{ x \in M \quad : \quad x \not \in x \}$, the set of reasonable objects.  This set is a better candidate for our universe: it avoids those strange objects that are members of themselves.  (It still has my 82 Impala, though.)

B ut now, is R itself a reasonable object?  Is R ε R ?  If R is a reasonable object, then it should be a member of R, which is a very unreasonable thing for it to do. (That is, if R ε R, then R doesn’t satisfy the membership criteria for R, and shouldn’t be a member of R.)

So apparently then R is unreasonable.  But then we’d expect $R \not \in R$, which is to say that R is a reasonable object, and thus should be a member of R.

In this way, we’re led to a variation on the Russell Paradox.
Apparently building Øc without first pinning down our universe is a bad idea.

The image above is a public-domain harbor map, showing the canning docks in Liverpool England.

Bertrand Russell  first discovered the self-referential paradox of building a set of all sets that are not members of themselves.   He was not (so far as I am aware) related to Baron Russell of Liverpool (Sir Edward Russell), but in any event I shall henceforth look at that image and see “Russell’s Pair of Docks”.