Elaborations of Russell's paradox
When Katara was five or six, I told her about Russell's paradox in the
following form: in a certain library, some books are catalogs that
contain lists of other books. For example, there is a catalog of all
the books on the second floor, and a catalog of all the books about
birds. Some catalogs might include themselves. For example, the
catalog of all the books in the library certainly includes itself.
Such catalogs have red covers; the other catalogs, which do not
include themselves, such as the catalog of all the plays of
Shakespeare, have blue covers. Now is there a catalog of all the
catalogs with blue covers?
I wasn't sure she would get this, but it succeeded much better than I
expected. After I prompted her to consider what color cover it would
have, she thought it out, first ruling out one color, and then, when
she got to the second color, she just started laughing.
A couple of days ago she asked me if I could think of anything that
was like that but with three different colors. Put on the spot, I
suggested she consider what would happen if there could be green
catalogs that might or might not include themselves. This is
somewhat interesting, because you now can have a catalog of
all the blue catalogs; it can have a green cover. But I soon thought
of a much better extension.
I gave it to Katara like this: say you have a catalog, let's call it
X. If X mentions a catalog that mentions X, it
has a gold stripe on the spine. Otherwise, it has a silver stripe.
And more interesting:
- Could there be a red catalog with a gold stripe?
- Could there be a red catalog with a silver stripe?
- Could there be a blue catalog with a gold stripe?
- Could there be a blue catalog with a silver stripe?
I knew that early 20th century logicians, trying to repair the Russell paradox,
first tried a very small patch: since comprehension over the predicate
X∉X causes problems, just forbid that
predicate. This unfortunately doesn't solve the problem at all; there
are an infinite number of equally problematic predicates. (Whitehead
and Russell's theory of types is an attempt to fix this; Quine's New
Foundations is a different attempt.) One of these predicates is
¬∃Y.X∈Y and Y∈X. You can't construct the set of all
X such that ¬∃Y.X∈Y and Y∈X because there is no
such set, for reasons similar to the reason why there's no set of all
X such that X∉X, so that's where I got the
silver stripe predicate.
- Is there a catalog of all the catalogs with gold stripes?
- Is there a catalog of all the catalogs with silver stripes?
Translating this into barber language is left as an exercise for the
[ Addendum 20231128: More about uncountable sets for seven-year-olds. ]
[Other articles in category /math]