9
$\begingroup$

The main idea of Russel's paradox is that, in Naive Set Theory, if we define $R = \{x\ |\ x \not\in x \}$, then $R \in R \Leftrightarrow R \not \in R$.

ZFC deals with this by making unrestricted set comprehension illegal, while type theory creates a hierarchy of sets such that there is no place in it for $R$. Both of these approaches stop one from defining $R$ in these versions of set theory.

However, what if we were to allow one to define such a set, but restrict the statements that one could make about it? In other words, is there a version of set theory which allows one to define $R$ as shown above, but in which the statement $R \in R$ is not a paradox, but rather simply doesn't make sense?

I'm not sure how one would define such a version of set theory, but it seems to me like something like this could be essentially equivalent to Naive Set Theory for "normal" sets while disallowing certain kinds of statements about "pathological" sets.

$\endgroup$
  • $\begingroup$ In the set theory that is the basis for my proof software, whether a set can be an element of itself is left as an open question. AFAICT, this sort of self-reference in itself does not lead to any contradictions if you don't allow unrestricted comprehension. Russell's Paradox does not cause any problems in my system, and I have nothing equivalent to the Axiom of Regularity in ZFC. I can prove the non-existence of both the Russell Set and the so-called universal set of everything. $\endgroup$ – Dan Christensen Jun 6 '15 at 14:57
  • $\begingroup$ @Aleksejs: I remembered a way your plan could arguably work; see updated answer. $\endgroup$ – Henning Makholm Jun 6 '15 at 17:23
16
$\begingroup$

This wouldn't be possible in ordinary first-order logic, because no matter what the axioms say about $R\in R$, it is necessarily a well-formed formula.

But there's a more conceptual problem here: If you're defining $R$ as "the set that consists of all sets that don't contain themselves", you're already implicitly assuming that it makes sense to ask of any set whether or not it contains itself, and get a definite answer back -- because that question is what you want to use as the defining property of $R$. You can't then suddenly turn around and say you can ask any set whether it is a member of itself, but you can't ask it of $R$.

If you need to change something, you have to change the underlying logic such that it's not two-valued anymore. Even so, whenever the logic allows you to assert (under a quantifier) that two (generalized) truth values are equal, and you can somehow construct a truth function that has no fixed points, Russell's paradox will be recreatable in that logic.


Edit for an alternative answer:

I'm not sure how one would define such a version of set theory, but it seems to me like something like this could be essentially equivalent to Naive Set Theory for "normal" sets while disallowing certain kinds of statements about "pathological" sets.

To some extent, this is done in Morse-Kelley set theory. There, your "pathological sets" are called proper classes, and have the restriction that you're not allowed to put have a proper class to the left of $\in$. (Or if you do, the result is always considered to be "false").

You get "unrestricted" comprehension in that you're allowed to make a collection of all the normal sets that satisfy any condition you can write down, but sometimes the result turns out to be "pathological".

Thus, you can define $R$ as the collection of all normal sets that don't contain themselves. You don't get $\forall x(x\in R\leftrightarrow x\notin x)$, but you do get $$ \forall x\in \mathit{NormalSets}\,(x\in R\leftrightarrow x\notin x) $$

However, it is debatable whether this really implements your program, because in Morse-Kelley, the conditions for a collection to be a "normal set" are more or less the same as the conditions for a set to exist at all in ZFC. So there's not much more new you can really do with the flexibility.

$\endgroup$
  • $\begingroup$ Excellent answer! $\endgroup$ – Asaf Karagila Jun 2 '15 at 18:06
  • $\begingroup$ For arbitrary binary predicate $E$, does $E(R,R)$ "make sense?" I don't see anything wrong with simply leaving it an open question. Likewise $R\in R$ (for binary predicate $\in$). See my comment to the OP. $\endgroup$ – Dan Christensen Jun 6 '15 at 15:08
  • $\begingroup$ @DanChristensen: In ordinary first-order logic, $E(R,R)$ is always a well-formed formula, and $E(R,R)\leftrightarrow \neg E(R,R)$ is always a contradiction. If you want to declare that it sometimes doesn't make sense, you need to use something other than ordinary first-order logic to interpret it in. $\endgroup$ – Henning Makholm Jun 6 '15 at 15:31
  • $\begingroup$ $R\in R$ is also a well-formed formula. I don't see that it is necessary to declare that it somehow doesn't "make sense", however you may formalize the notion. Again, AFAICT, if you disallow unrestricted comprehension, this kind of self-reference shouldn't be problematic. $\endgroup$ – Dan Christensen Jun 6 '15 at 16:01
  • $\begingroup$ @DanChristensen: I'm confused here. Declaring that $R\in R$ doesn't make sense is not something I want to do, but was the OPs proposal for avoiding Russell's paradox. Specifically, the OP wants to have enough comprehension to get $\forall x(x\in R\leftrightarrow x\notin x)$ -- what I'm saying is that he cannot get that without either changing the logic or creating a paradox. $\endgroup$ – Henning Makholm Jun 6 '15 at 16:07
1
$\begingroup$

If $R$ is a set such that $x\in R\leftrightarrow x\notin x$, and the law of excluded middle holds, then either $R\in R$ or $R\notin R$, but not both since it is impossible that both a statement and its negation are true.

But now if $R\in R$ then $R\notin R$; and if $R\notin R$ then $R\in R$.

So it's a no-go. Regardless to allowing or disallowing comprehension. Or any properties of $\in$, really. Just that it's a binary relation.

$\endgroup$
  • $\begingroup$ Can't we add restrictions on what $x$ can be in a statement of the form of $x \in y$? $\endgroup$ – Aleksejs Popovs Jun 2 '15 at 18:01
  • $\begingroup$ @Aleksejs: This has nothing to do with anything. If you want "the set of all sets which do not contain themselves", then you are looking at an object in your universe satisfying this property. I showed that no such object can exist. This is not about "defining this set" or not, just showing that a set cannot have this property. $\endgroup$ – Asaf Karagila Jun 2 '15 at 18:04
  • $\begingroup$ I had made some comment about what if we do not let sets be members of sets at all, noting that the resulting set theory would not be very useful; of course it doesn't allow defining the set in the question title. $\endgroup$ – David K Jun 2 '15 at 18:07
  • $\begingroup$ @David: You just get type theory like that (well, you have to push "forward" with this idea, but it's the first step towards type theory). $\endgroup$ – Asaf Karagila Jun 2 '15 at 18:08
  • $\begingroup$ I don't think the law of excluded middle is responsible here. Even in intuitionistic logic, $\varphi\leftrightarrow\neg\varphi$ is a contradiction. $\endgroup$ – Henning Makholm Jun 2 '15 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.