Rusell’s Paradox Reversed
Bertrand Russell once wrote to the eminent mathematician and philosopher
Gottlob Frege to ask him how his system would handle the set of all sets that are not members of themselves.
Frege famously wrote this in the epilogue to the second volume of Basic Laws of Arithmetic:
A scientific writer can scarcely encounter anything more undesirable than, after completing a work, to have one of the foundations shaken. I became aware of this situation through a letter from Mr. Bertrand Russell as the printing of this volume neared completion.
In fact, today Frege is perhaps better remembered for this failure than for all his other work combined. At least this was an interesting mistake that taught mathematicians something. It’s much worse to publish a two-volume 500 page proof only to have an undergraduate notice an obvious mistake on page 2.
Russell’s paradox is a simple way of expressing the statement, “This statement is false” into the set theory Frege had laid out. It’s commonly responded to by removing the Principle of Unrestricted Comprehension, as well as some other changes eventually made in Zermelo-Fraenkel set theory instead of what mathematicians now call naive set theory. How successful this is I’m not sure since Godel’s Theorem still applies, even with ZF. Regardless, today I found myself thinking of an alternate problem with the Principle of Unrestricted Comprehension. What about the set of all sets that do contain themselves?
Let \(\Phi\) be the set of all sets that do contain themselves. Is \(\Phi\) a member of \(\Phi\)? If \(\Phi\) contains itself, then it is a member of itself and thus contains itself. Everything’s copacetic.
But now suppose \(\Phi\) does not contains itself. Then it is not a member of itself and thus does not contain itself. Everything’s still copacetic. So which is it?
I can’t see a way to resolve this. Pick either one as a postulate, and everything still works. It seems that not only does the Principle of Unrestricted Comprehension lead to Russell’s Paradox and is thus inconsistent. It also can’t handle the question of whether \(\Phi \in \Phi\). Double whammy.
ZF handles the problem by not allowing sets to be members of themselves, so within ZF set theory you can’t even mak this statement and the concern does not arise.
A little digging shows others have noticed this, going back quite a while. In logic this becomes, “This sentence is true” which can be either true or false, and which Saul Kripke called “ungrounded”. The set of all sets that contain themselves is also an example of a “reflexive” or “non-well-founded set” which I had never heard of before today, but which apparently has applications in computer science.
