I am wondering whether this is a valid proof in ZF.
Claim
The set of all sets does not exist.
Proof
Suppose the set $V$ of all sets exists and consider the property $P(x): x\notin x$. By the axiom of separation, there is some set $B$ such that $x\in B$ iff $x \in V$ and $x \notin x$.
Now, either $B \in B$ or $B \notin B$.
Suppose $B \in B$. It follows that $B \notin B$.
On the other hand, suppose $B \notin B$. Since $B \in V$ ($V$ being the set of all sets) and $B\notin B$, we conclude $B \in B$.
We have shown that $B \in B$ iff $B \notin B$. This is a contradiction! So our original assumption was false, and the set of all sets does not exist.
Questions
I know that in classical logic, a contradiction has the from $P$ and not $P$. Is that equivalent to $P$ iff not $P$? Thinking of the truth table in my head this seems right, but just want to make sure.
Historically speaking, I am curious when this theorem was deduced. I know that there was Russel's paradox, presented to Frege in a letter prior to the formulation of the ZF axioms. However, this is obviously a different argument. Is it formulated after the ZF axioms are a thing?
Are there other ZF proofs that the set of all sets does not exist? What about non-ZF proofs? Are there other axiomatic settings where the existence of the set of all sets does not lead to a contradiction?
Best Answer
Historically speaking, I am curious when this theorem was deduced.
The earliest results go back to Cantor, who proved the set of all sets is not a set itself, but a class. This was indeed way before ZF was 'a thing'. Zermelo published letters sent by Cantor to Hilbert and Dedekind, in which Cantor was quite explicit about this finding about the (later called) class of all sets.
Theorem: There is no greatest cardinal number.
Proof: Assume the contrary, and let $C$ be the largest cardinal number. Then $C$ is a set and therefore has a power set $2^C$ which, by Cantor's theorem, has cardinality strictly larger than $C$. Demonstrating a cardinality (namely that of $2^C$) larger than $C$, which was assumed to be the greatest cardinal number, falsifies the definition of $C$. This contradiction establishes that such a cardinal cannot exist.
Are there other ZF proofs that the set of all sets does not exist? What about non-ZF proofs?
Indeed, you can work with Russell's refutation of Frege's idea. However, due to the historic genesis of ZF and later ZFC via Cantor's ideas, these are deeply linked with one another. - One non-ZF proof was given by - well, Cantor of course; he was pioneering.
Are there other axiomatic settings where the existence of the set of all sets does not lead to a contradiction?
Yes, there are. For example, one such non-well-founded set theory is Quine's New Fondations. Another important one is Peter Aczel’s hyperset theory. Also, Vopěnka's Alternative Set Theory comes to mind.
Since you asked for a read up:
G. Cantor, E. Zermelo (ed.), Gesammelte Abhandlungen, Springer (1932).
G. Cantor, "Beiträge zur Begründung der transfiniten Mengenlehre", Math. Ann. 49 (1897), pp. 207–246.