flaw in the proof of Cantor's theorem? does the set of all sets exist?

I decided to improve my question since there were mistakes pointed out (THANK YOU!) and I realized that I did not mention if I put any kind of axiomatic conditions on the sets which I consider. I have a good math background (numerical analysis/mathematical statistics/linear algebra), but I am a biologist, so mathematicians please consider that, try defining what you are talking about.

Second, here is my question. Many books prove that the set of all sets does not exist using Cantor's theorem: for any set X its Cardinality is strictly less than the Cardinality of a set consisting of all subsets of X. I am here to say that I think that one can not use this theorem as a proof of this point: the set of all sets does not exist. Actually one member of the forum already asked this question: can we use this theorem to prove this fact? "Is this prove correct?" Note: nobody answered yes or no. My answer is solid NO. But I am not 100% sure. Thus, I am providing my explanation for my "NO" and I am asking members of this forum whether they think that I am wrong. And if I am wrong, I would like to know why.

If one assumes that all valid sets have to obey ZFC axioms, then one need not prove the point using Cantor's theorem, because "the set of all sets" is not a valid set in ZFC theory, because it does not obey the Axiom of Regularity, for example. If one assumes that all valid sets have to obey "naive" theory comprehension principle: then we are not talking about something logical, we are are not doing math. So forget about it. If one assumes that all valid sets have to obey New Foundation axioms, then, as member of this forum pointed out - the set of all sets does exist, it is ok-set, thus we do not need to prove that it does not exist. If one assumes that all valid sets have to obey Cantor's rules, then actually as a person on this forum pointed out, Cantor's conception of sets rules out the set of all sets. Thus, we do not need to prove the point, because the set of all sets does not exist under Cantor's conception. If one assumes that all valid sets have to obey "logical theory of sets", then it is easy to find one to one correspondence between the elements of set of all sets and elements of its power set: s=f(x)=x. So these sets are equinumerous, and one can not prove the opposite.

Finally, it is clear to see that the point (the sets of all sets does not exist) is easily proven from Cantor's theorem. Thus, if we proved that the point is not true (under the "logical set theory"), and I do think that it is not true (under the "logical set theory"), when we have to find a mistake in the prove given by Cantor, using logical set theory.

Here I am providing a proof by Cantor and point out the mistake later on:

The mistake leads to the conclusion that this theorem is true for any set X except for "a set of all sets" in the universe. Thus one can not derive that the "set of all sets does not exist" based on Cantor's theorem.

Here is the proof of Cantor's theorem:

Definitions: a)sets are called equinumerous if there exists one-to-one correspondence between its elements.

b)cardinality of set X is considered less than cardinality of set Y if a subset of Y is equinumerous to X, but no subset of X is equinumerous to Y.

Lemma: let S be a set of subsets of X such that S is equinumerous to X. Then there exists a subset of X (call it A), such that it is not contained in S (A ∉ S).

(PS, it is easy to see that the theorem automatically follows from the Lemma: lets assume that the theorem is not true, than there exists a set X such that it is equinumerous to the set consisting of all its subsets (call it S). But such a set S satisfies the conditions of the Lemma. Thus there exists a subset of X that is not contained in S. But this is absurd, thus we have a contradiction and S can not be equinumerous to X.)

Proof of Lemma: All we have to do is to define A and prove that is satisfies the conditions of lemma: it should be a subset of X, such that it is not contained in S (A ∉ S).

Lets take any S, that satisfies the conditions of lemma (a set of subsets of X such that S is equinumerous to X). Let f(x)=s is the one-to-one function that images the elements of X (x) into elements of S(s).

Then, A is defined as: A={x ∈ X: x ∉ f(x)}. That is A is a subset of X, such that for every element x of A: x is not contained in s=f(x).

Then we assume that A∈S and find a contradiction (explained below). Thus A∉S and the Lemma is proven. The contradiction is the following:

If A∈S, then exists element of X (call it e), such that A=f(e). If e∉A than e∉f(e)=A - contradiction (because from the definition of A follows that if e ∉ f(e): e should be contained in A). If e∈A than e∈f(e)=A, that is not possible by the definition of A, thus there is also a contradiction. Lemma (and the theorem) is proven. I saw other proofs on the internet and in books, but all of them define a set A={x ∈ X: x ∉ f(x)}.

I highlighted the mistake in bold. Indeed, lets ask, is A logically defined for a set X=set of all sets? Let X="set of all sets in the universe". Let S be a set that contains all subsets of X. Let s=f(x)=x (that is possible only for a "set of all sets in the universe"). Now look at the definition of A: the set A is not logically defined: there is no such a set with elements of X, such that x ∉ f(x), because x ∉ f(x) for all x. In fact A can not be even an empty set: because even for empty set: f(empty set)=empty set, thus empty set ≠ A. Thus A is still undefined.

I saw another proof of the fact that the "set of all sets" does not exist: they use Russell's paradox. But I already told that I am not operating under the comprehension principle, because it is nonsense.

Any mathematicians here? please let me know if there is a flaw in my arguments. Does the set of all sets exist? Is it still debated? Thank you!

• You must take $X$ to be a well-defined set, and by Russell's argument that you refer to, the "set of all sets" is not such a thing. But that's ok - Cantor's theorem only applies to well-defined sets in the first place. I claim that the set $A$ is well-defined providing $X$ is, but I don't know axiomatic set theory well-enough to be able to say exactly why this is the case. I imagine somebody who does will provide this detail soon... – mdp Oct 29 '13 at 16:15
• You seem to be misattributing the source of the contradiction, similar to what a lot of people do with Cantor's diagonal proof that the real numbers are uncountable. See my thread here: math.stackexchange.com/questions/527248/… – Keshav Srinivasan Oct 29 '13 at 17:23

Let $X$ be a set, and let $f$ be a function $X \to \mathcal{P}(X)$. To prove Cantor's theorem, we want to show that $f$ is not surjective. (There is no need to assume that $f$ is injective, by the way.)

Your objection is that it is not "logical" to define the set $A=\{x \in X: x \notin f(x)\}$. To the extent that this is a philosophical criticism, it may or may not be correct, but in any case wouldn't amount to showing a "mistake" in the proof. So let's stick to the mathematics.

The formal justification for the existence of $A$ is an instance of the Separation axiom schema: for every set $X$, formula $\varphi$, and parameter $p$ there is a set denoted $\{x \in X: \varphi(p,x)\}$ whose elements are the elements $x$ of $X$ such that $\varphi(p,x)$ holds.

Your objection seems to be that this definition of $A$ leads to a contradiction if $X$ is the "set of all sets" and $f$ is the identity function. This is a good and important observation. If the conjunction of two things leads to a contradiction, then (at least) one of them must be wrong. Either Cantor's argument is wrong, or there is no "set of all sets."

After having made this observation, to ensure that one has a consistent theory of sets one must either (1) disallow some step in Cantor's proof (e.g. the use of the Separation axiom) or (2) reject the notion of "set of all sets" as unjustified. Mainstream mathematics has done (2), for the reason that you (and Russell) pointed out. It is also possible to do (1) instead, as in New Foundations set theory.

EDIT: I missed some things on my first reading. Your third-to-last paragraph, if all its claims were true, would show that set theory as used by Cantor was inconsistent. Note that this would be quite different (mathematically, if not philosophically) from showing that there was a mistake in his proof! A proof of inconsistency would be a perfectly valid proof, not to mention an important one. In any case, some of your claims are not true, as I explain below.

Letting $f$ be the identity function, you argue that $A$ must be empty:

Now look at the definition of $A$: there is no element of $X$, such that $x \notin f(x)$...

This step is not right. There are plenty of possibilities for $x$ such that $x \notin x$. Perhaps you are confusing $x \notin x$ with $x \ne x$.

Then you argue that $A$ cannot be empty.

...in fact $A$ can not be even an empty set: because even for empty set: $f(\emptyset)=\emptyset$, thus $\emptyset \notin A$.

This step is not right either. First, as Greg Martin points out, $\emptyset \notin \emptyset$, so if $\emptyset \in X$ then $\emptyset \in A$. Second, even if $\emptyset \notin A$ it doesn't follow that $A \ne \emptyset$. Perhaps you are confusing "$\in$" with "$=$" again.

• Thanks for pointing out the last bit before your edit--that Cantor actually shows that a universal set is incompatible with arbitrary separation. Us NF nutters appreciate the distinction. – Malice Vidrine Oct 29 '13 at 17:33
• @SergeyBond I don't think that "Cantor was wrong" is an accurate characterization of anything that I have ever said. – Trevor Wilson Oct 30 '13 at 3:52
• @SergeyBond No, I don't think that is wrong either. Although perhaps slightly different from the original formulation, a version of Cantor's theorem says "for every set $X$ and every function $f$ on $X$, there is a subset $Y \subset X$ that is not an element of the range of $f$." Then one can argue (as Russell did) that for any set $X$, there is a subset $Y \subset X$ that is not an element of $X$, and therefore $X$ is not universal... – Trevor Wilson Oct 30 '13 at 15:42
• @SergeyBond If $T$ is a set theory that includes the statement "there is a universal set" then either (1) this theory is inconsistent (as with naive set theory) or (2) Cantor's theorem is not a theorem of this theory (as with New Foundations set theory.) A theorem is never "a theorem, period." It is always a "theorem of $T$" where $T$ is some theory. This theory $T$ is usually taken to be $\mathsf{ZFC}$. You may use a different theory if you like, but that doesn't make all $\mathsf{ZFC}$ theorems "wrong" just because you say so. – Trevor Wilson Oct 31 '13 at 1:11
• @SergeyBond Yes, I agree with this last comment. By the way, the consistency of NF is a tricky problem: see en.wikipedia.org/wiki/… – Trevor Wilson Oct 31 '13 at 3:12

Some mistakes in your reasoning (subtle mistakes - this is a subtle subject - but still mistakes):

1. As Matt pointed out, "the set of all sets" is not well-defined in modern set theory, so you can't define $X$ to be that object.
2. It is always logical to define $A$; indeed, it is always well-defined to consider the set of elements of a given set that satisfy a particular property (as opposed to trying to define the set of all objects in the world that satisfy a particular property). In fact this is precisely the axiom schema of specification.
3. In your third-to-last paragraph, you are mixing up the two very different statements $\emptyset \notin A$ and $\emptyset \neq A$.

The "mistake" you illustrate is known more formally, if I'm correct, as the Russell Paradox, and it is a contradiction in "naive" set theory which modern "axiomatic" set theories seek to resolve.

If we define a set naively as "any collection consisting of objects with a common property" (the "comprehension principle"), we can define a set R as "the set of all sets that are not members of themselves". Now, if the set R does not contain itself, then by its definition R is a member of itself. Conversely, if R contains itself, it is not a member of itself. So R both must and can't be a member of itself, hence the paradox.

In response to this, Ernst Zermelo and Abraham Frankel sought to more rigorously define sets using "axioms". If you accept a certain set of axioms as true (they are non-provable in themselves and so you are free to reject them if you have an alternate explanation to avoid logical contradiction), then these contradictions are resolved because collections that are contradictory to one or more axioms are not sets. The list of axioms Zermelo and Frankel came up with is, unimaginatively enough, known as Zermelo-Frankel Set Theory, and to this is commonly added Zermelo's Axiom of Choice ("the product of a set of non-empty sets is non-empty") to form "Zermelo-Frankel Set Theory with the Axiom of Choice", or ZFC, the most common axiomatic set theory in modern math.

In this theory, we first find the Axiom of Extensionality which is fundamental to a set's definition: two sets are equal (the same set) if they have the same elements, and are not equal (disjoint) if either set has an element not in the other. The axiom infers that both are possible, hence given any set X, there exists a set Y that is the union of all elements of X and an element not in X, and $X \neq Y$.

Next, and also very important to the definition of what can be a set, is the Axiom of Regularity; any nonempty set X contains an element Y such that X and Y are disjoint sets. Colloquially, a set cannot be a member of itself because then the set and its own member would be the same set. This resolves (sidesteps, really) the Russell paradox by asserting that the set R cannot contain R, and therefore any defined collection R containing R is not a set.

Another big one is the Axiom of Power Set; the set of all subsets of a set exists. This follows from some other axioms I'm skipping, like the Axiom of Pairing (given two sets X and Y, there is a set S which contains X and Y), the Axiom of Union (given two sets X and Y, there exists a set $S=X\bigcup Y$), and the Axiom of Infinity (for any arbitrary set W, and a set S = {W}, there exists a set X = {$\emptyset$, W, S})

Therefore, there is no set that is the set of all sets in ZFC, for two reasons; first, because such a set would have to contain itself which is "illegal" in ZFC, and second, because for any set, it's possible to construct a set not in the original set which contains all possible subsets of the set. The statement "there is no set that is the set of all sets" is equivalent to saying there is no highest number, because for any number N which can be constructed by $S(X)_0= \emptyset, S(X)_N = \{X, S(X)_{N-1}\}$, there is a number N+1 of construction $S(X)_{N+1}= \{X, S(X)_{N}\}$.

• Thank you! I understand now that if we define sets using axioms, the set of all sets may not be a valid set. Indeed, as you point out, if one uses ZFC axioms to define valid sets, the set of all sets would not be valid, because it violates the axiom of Regularity. But Cantor himself defined a set in a general way (you call it naive way) and I think it is ok to do so? You point out that this may lead to paradoxes. I do not think so. You defined R in 2nd paragraph in a way that is not logical, since definition itself leads to contradiction. R does not belong to "any definable collection". – Sergey Bond Oct 30 '13 at 1:38
• But in naive set theory, if we can say what a set contains, it is defined. Now, it may not fit any further definition of "well-defined", which I think is your point, however in naive set theory, "the set of all sets that are not members of themselves" is a set. There are no further rules that would expose a definition as "illogical". – KeithS Oct 30 '13 at 14:54
• Well, of course when we say that we define a set naively, as a "collection of definable objects", we should remember that for any collection there should be a definition of a collection, and this definition should be logical. If a definition leads to a paradox, then it is not logical. For example set X= [{x∈R:0>x>1} and X is nonempty] is not a logical definition, because it leads to a paradox: 0>1. Similarly, "the set of all sets that are not members of themselves" is not a valid definition, because it also leads to a paradox. – Sergey Bond Oct 30 '13 at 17:42
• Hooh, I just learned that naive set theory uses the comprehension principle: "Given any property, there is a set which consists of all objects having that property." Well, I guess that's where the dog is buried! I guess this is why paradoxes arise, but actually there are no paradoxes. It is just that the definitions of these sets are not logical. – Sergey Bond Oct 30 '13 at 17:56

In standard (e.g., Zermelo-Fraenkel or ZFC) formulations of set theory, sets are collections of objects that satisfy certain axioms; not every collection is a set. These axioms include the axiom schema of specification, which says that if $A$ is a set and $\varphi$ is a formula, then $\{x\in A : \varphi(x)\}$ is also a set. The formula $\varphi$ itself, or the expression $\{x : \varphi(x)\}$, can be seen as corresponding to a class, which may or may not be a set; a class that isn't a set is called a proper class.

In particular, the "set of all sets" is a proper class. Your argument, rather than showing a mistake in Cantor's theorem, demonstrates that fact (because assuming that there is a set of all sets, together with Cantor's theorem, leads to a contradiction).

• As Cantor, I operate using a naive definition of set, w/o referring to axioms. In ZFC theory a set of all sets is not a valid set(see why in KeithS answer). Thus no proof of its non-existence is needed in ZFC. – Sergey Bond Oct 30 '13 at 1:19
• @SergeyBond 1. Cantor had a conception of sets that ruled out the set of all sets. This conception is known as the "limitation of size doctrine". You can read about it in the book Cantorian Set Theory and Limitation of Size by Michael Hallett. 2. What exactly does "no proof of its non-existence is needed in ZFC" mean? You can certainly prove in ZFC that no set of all sets exists. And it is certainly possible in the language of ZFC to define a set of all sets. Otherwise, one couldn't show that it does not exist. – Michael Greinecker Oct 30 '13 at 9:02
• Set of all sets is invalid within ZFC because it does not satisfy the Regularity axiom. "Limitation of size doctrine" is new to me. This means that Cantor proved the theorem correctly within the frames of some axioms. I see in the books people use Cantor's theorem to prove that the set of all sets does not exist using naive definition of set, no axioms. I think they are wrong, because Cantor's theorem is not valid within naive definition of sets for a set X=set of all sets. For such X we can find one-to-one correspondence f(x)=x and I showed where exactly the mistake in the proof is hidden. – Sergey Bond Oct 30 '13 at 9:44
• PS, you say that you can define a set, and then prove that it does not exist. I think that if you do that, then it means that your object is still undefined. I can define a set X= [{x∈R:0>x>1} and X is nonempty]. This definition is not valid, do you agree? Because definition itself leads to absurd: 0>1. – Sergey Bond Oct 30 '13 at 17:30
• In naive set theory, whether a property defines a set or not is always unknown; if you reach a contradiction, then you conclude that the definition wasn't "logical" and there's no such set; but if you don't reach a contradiction, you're left in limbo. Maybe it's a set, maybe not. On the other hand, with axiomatic set theory you can at least prove that some sets exist. (There are still classes whose status is either unknown or strictly independent of ZFC, but at least you have a solid axiomatic basis to build on.) – mjqxxxx Oct 30 '13 at 19:33

So in light of the edits I feel I should make a couple of technical points that I'm not sure have been addressed yet.

First, when we say that naive comprehension is inconsistent, keep in mind that we're talking about an infinite collection of axioms, one positing $\{x:\phi\}$ for every sentence $\phi$. The problem isn't that the definitions "aren't logical"; it's that while almost all of them are perfectly good existence assumptions in isolation, not -all- of them can be true.

Second, $\{x:0>x>1\}$ is a perfectly good set. In fact, every set theory I'm familiar with has this set. It usually goes by the name $\emptyset$. Of course the defining sentence is inconsistent, but that only tells us that there are no elements that can meet that criterion. $\{x:x\notin f(x)\}$ is nothing of the sort. It has no instances that are outright contradictory in the way that $\{x:x\notin x\}$ does, either. If there is anything wrong with assuming the existence of $\{x:x\notin f(x)\}$ it's that it contradicts some other assumption.

Third, the idea that ZF disproves a universal set because of Foundation is a red herring A) because the -exact- same proof is used to show that $P(X) > X$, and B) if you remove Foundation you can still prove there is no universal set by way of both Cantor's and Russel's paradoxes.

Write out the existence assertions used in Cantor's paradox, in primitive notation, individually. See if you can -formally- derive a paradox from just any one of them.

• I was not referring to set {x:0>x>1}, I was referring to set X such that [{x∈R:0>x>1} and X ≠∅]. Notice AND X ≠∅. Such a set is not logically defined. Proof: lets assume that is is logically defined, then there exist a non-empty set X, such that for at least one of its elements x:0>x>1. But 0>1, paradox, end of proof. Thus such a set does not exist. – Sergey Bond Oct 30 '13 at 21:47
• Set A = {x∈X:x∉f(x)} is not logically defined for X=set of all sets and f(x)=x (where x - any element of X, including ∅). Proof: lets assume it is logically defined. Then such set should exist. But it does not exist. End of proof. – Sergey Bond Oct 30 '13 at 21:54
• True, I did misread that. In which case the point to note is that that expression is equivalent to $X\neq\emptyset\wedge X=\{x:0>x>1\}$ (if I'm guessing what you wrote correctly--my browser can't do unicode characters). Which involves a perfectly normal formal contradiction without further premises. Again, $\{x\in X:x\notin f(x)\}$ is nothing of the sort. It is not, all by itself, contradictory. – Malice Vidrine Oct 30 '13 at 22:10
• Any set theory is constructed for sets which should obey certain axioms. ZFC axiom of regularity states that "any nonempty set X contains an element Y such that X and Y are disjoint sets. Colloquially, a set cannot be a member of itself because then the set and its own member would be the same set." But universal set is a member of itself. Thus it does not obey the axiom and can not be considered as a valid set. Where is the lack of logic? – Sergey Bond Oct 30 '13 at 22:11
• Your 1st point I do keep in mind. It does not contradict to anything I said. – Sergey Bond Oct 30 '13 at 22:12

Your complaint that Cantor's theorem is inconsistent with 'the set of all sets' is quite correct. The historical problem here is that Cantor's original naive reasoning about sets actually was inconsistent - moreover, Cantor was aware of the fact! The odd thing (to us) is, he kind of took the inconsistency in stride - for example, in his writings he speaks of 'consistent multiplicities' and 'inconsistent multiplicities' as if both could exist (he even uses the latter in some proofs!). His work was done before the 20-th century movement to use formalism to establish better rigor - in fact, his work was a major impetus for that movement.

It was only later that a consistent notion of set theory was salvaged from Cantor's work. The first way used a 'limitation of size' principle, first developed by Zermelo [the Z of ZFC]; as noted, this leads to 'there is no set of all sets'. However, some mathematicians still wanted to talk about 'all sets' in some mathematically meaningful way; this led to the 'sets vs classes' concept put forth by von Neumann (no 'set of all sets', instead a 'class of all sets').

You have stumbled across what is known as Cantor's paradox. Cantor's Theorem states that there is no surjection from a set $X$ on to its power set $\mathcal P(X)$. We arrive at a paradox: let $V$ be the set of all sets - then $\mathcal P(V)=V$, so there is certainly a surjection $V\to\mathcal P(V)$.

This paradox does not prove that no universal set exists. Rather, it shows that any set theory in which the paradox can be formulated is inconsistent. We don't normally want our set theories to be inconsistent.

ZFC avoids this paradox by the axiom of foundation, which proves that the universal set $V$ does not exist. However, there are other set theories, such as Quine's New Foundations, in which there is a set of all sets $V$. New Foundations has two axioms: the usual axiom of Extensionality and the new axiom of Restricted Comprehension, which states that the set $$\{x\vert\phi\}$$ exists as long as $\phi$ is a stratifiable formula: that is, we can assign numbers called levels to the variables in $\phi$ such that if the phrase $x\in y$ occurs in $\phi$ then the level of $y$ is one greater than the level of $x$ and whenever $x=y$ occurs in $\phi$ then $x$ and $y$ have the same level.

In particular, this avoids Russell's paradox: we cannot create the set $$\{x\;\vert\; \neg(x\in x)\}$$ because whatever level we assign to $x$ on the left of the $\in$ sign, we have to have the same level for $x$ on the right.

How does New Foundations avoid Cantor's paradox? Well, recall that, in set theory, we define functions by their graphs: $$f:X\to Y" = \{(x,f(x))\;\vert\;x\in X\}$$ But this now means that Cantor's theorem makes no sense in New Foundations: if $Y=\mathcal P(X)$, then the level of $Y$ must be one greater than the level of $X$ (since the elements of $Y$ are subsets of $X$) and so $y$ must have level one greater than $X$. But this means that we cannot form a set of pairs of elements of $X$ and elements of $Y$.

Now, New Foundations would not be worth much as a theory if it were impossible to prove Cantor's theorem at all in it. It turns out that there is a simple way to modify Cantor's theorem so that it makes sense in NF. We define $\mathcal P_1(X)$ to be the set of one-element subsets of $X$. Then we can prove in NF that there is no surjection from $\mathcal P_1(X)$ on to $\mathcal P(X)$.

Morally, $\mathcal P_1(X)$ should have as many elements as $X$, but now its elements are the same type as the elements of $\mathcal P(X)$, so we can formulate (and prove) this version of Cantor's theorem inside NF.

But now we come back to our original problem. Let $V$ be the set of all sets. Then we have a surjection $\mathcal P_1(V)\to\mathcal P(V)$ given by $$\{X\}\mapsto X$$ This is certainly a surjection: let $Y\subset\mathcal P(V)$ be any subset. Then $Y$ is the image of $\{Y\}$ under our map. What saves New Foundations is that this map cannot actually be shown to exist using the axioms given above.

If we write out the formal definition of the above map, it becomes: \begin{align} f &= \{(\{X\},X)\} \\ &=\{p\;|\;\text{$p$ is a pair}\wedge\exists X \in\text{First}(p).(\forall Y\in\text{First}(p).Y=X)\wedge (X=\text{Second}(p))\} \end{align} The problem is that the clause on the right is not stratifiable, so $f$ cannot be shown to exist within NF. Indeed, it cannot exist in any model of NF because then it would be a witness to the negation of Cantor's Theorem.

• "ZFC avoids this paradox by the axiom of foundation, which proves that the universal set 𝑉 does not exist." That's not true: you can't avoid a paradox by adding an axiom. Rather, $\mathsf{ZFC}$ avoids the paradox by dropping full comprehension, having in its place only the weaker axiom schemes of separation and replacement. Foundation (together with the pairing axiom) does imply that there is no universal set, but that's separate from avoiding Russell's paradox. – Noah Schweber Nov 18 '20 at 5:07