Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics

Dashboard
Notifications
Mark all as read
Q&A

Existence of a set of all sets

+0
−1

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?

Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

0 comments

2 answers

+4
−0

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.

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comments

+0
−1

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.

Why does this post require moderator attention?
You might want to add some details to your flag.

1 comment

Or the property $P(x) = x \not\in x$ cannot exist in such an axiomatic system, or such an axiomatic system can contain a set of all sets but at the cost of consistency, or possibly such an axiomatic system can contain a set of all sets as long as it doesn't have the law of the excluded middle. Peter Taylor‭ 6 months ago

Sign up to answer this question »

This community is part of the Codidact network. We have other communities too — take a look!

You can also join us in chat!

Want to advertise this community? Use our templates!