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
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
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?

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

0 comment threads

2 answers

+6
−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.

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

0 comment threads

+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.

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

1 comment thread

General comments (1 comment)

Sign up to answer this question »