# 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... –  Matt Pressland 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
Thank you! I edited the mistakes. But I am glad that you saw my point. If a set is defined in "naive way", then there is no reason to say that the set of all sets does not exist, right? Finally, do you actually agree that one can not use Cantor's theorem (proven using "naive" definition of a set) to prove that a set of all sets does not exist? Is there any set theory with axioms that do allow the existence of a set of all sets? –  Sergey Bond Oct 30 '13 at 1:02
@SergeyBond You are right that although Cantor's argument (later used by Russell) forces us to discard some of our naive assumptions, we have some liberty in choosing which to keep and which to discard. Although most modern mathematicians choose to keep the notions of power set and separation and discard the notions "all infinite sets are equinumerous" and "there is a set of all sets", it is possible to make different choices. See the link to "New Foundations" in my answer for a set theory that allows a universal set (it avoids contradiction by restricting separation instead.) –  Trevor Wilson Oct 30 '13 at 1:30
Wau, Thank you! I feel like I proved that the universe exists and I should be given a million dollar for pointing out where Cantor was wrong. This resolves another post on this site. –  Sergey Bond Oct 30 '13 at 3:19
@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

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 definable collection", we can define a set R as "the set of all sets that are not members of themselves". Now, if R itself does not contain itself, then by its definition it 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.

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 basically asserting that the collection of all sets that are not members of themselves is not itself a set, because it would contain itself and sets can't do so.

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, 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 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