Existence of a set of all sets
Suppose that we have an axiomatic set theory having the following axiom:
The Axiom Schema of Comprehension: Let $\mathbf{P}(x)$ be a property of $x$. For any set $A$, there is a set $B$ such that $x\in B$ if and only if $x\in A$ and $\mathbf{P}(x)$.
Can a set of all sets exist within such an axiomatic system?
2 answers
Sure. You can simply add $\exists V.\forall x.x \in V$ as an axiom to ZF(C), and you will have such an axiomatic system. Such an addition to ZF(C) would make it inconsistent, but it would still prove the existence of a "set of all sets" (along with everything else).
As Peter Taylor points out in a comment on another answer, there are a multiple ways of accomplishing this consistently though most of them require fiddling with the logic in which the axiomatic system is formulated.
Peter Taylor suggests dropping the Law of Excluded Middle (LEM) leading to a constructive/intuitionistic logic. This does not work as the proof of the contradiction does not use LEM even implicitly. However, dropping the Law of Non-Contradiction leading to a paraconsistent logic immediately resolves the issue. You can still use Russell's proof to show $x\in x$ and $x \notin x$, but this does not render a paraconsistent logic trivial.
Peter Taylor also suggests that $x \in x$ can fail to be a well-formed formula. One way this could happen is by using a linear logic or some variant (e.g. an affine logic). Specifically, we could drop the structural rule of contraction which allows variables to be used multiple times in a formula. $x \in x$ is not a linear/affine formula as $x$ occurs twice in it. This use of contraction is unavoidable. Masaru Shirahata's Linear Set Theory (PDF) is an example of a set theory based on a linear logic which contains an "unrestricted" comprehension axiom.
There are various other ways the formula $x \in x$ could be disallowed. In modern type theories and structural set theories, membership, i.e. $\in$, is usually identified with (flipped) function application and has a type like ${\in_X} : X \times \Omega^X \to \Omega$ where $\Omega$ is a type of propositions, e.g. $\mathbf 2$ in the classical case. In this situation, $x \in_X x$ would be a type error (and thus not a "well-formed formula") as $x$ can't simultaneously have the type $X$ and the type $\Omega^X$. Indeed, Russell's initial attempts to avoid Russell's paradox were what led to modern type theory.
See also the nLab's page on Russell's paradox for a list of options for avoiding Russell's paradox, though it also includes modifications to comprehension.
0 comment threads
Let $V$ be a set of all sets. According to the Axiom Schema of Comprehension, we can have the following set:
$$U= \{ x\in V \mid x \not \in x \}.$$
Now, there are two cases:
-
$U \in U$, which, according to the definition of the set $U$, implies that $U \not \in U$, which is a contradiction;
-
$U \not \in U$, which, according to the definition of the set $U$, implies that $U \in U$, which is a contradiction.
Thus, a set of all sets cannot exist in such an axiomatic system.
0 comment threads