# Stuck on question regarding Cantor's theorem and sets

I'm trying to prove that a set of all sets does not exist, meaning that the following does not exist: $$D = \{ S \mid S \text{ is a set} \}$$ I can use Cantor's Theorem and the proof of cardinality of sets which says that if $A⊆B$ then $A≤B$. But I'm stuck with where to go next.

-

If there were a set $D$ containing every set $S$ as an element, consider the power set $P(D)$. The elements of $P(D)$ are subsets of $D$, so in particular they are sets, so we must have $P(D) \subseteq D$. Why does this contradict Cantor's Theorem?

One more technical push: if $\iota: A \hookrightarrow B$ is an injection of nonempty sets, then there is a surjection $s: B \rightarrow A$. To define $s$, let $a_0 \in A$. Then for $b \in B$, if $b$ lies in the image $\iota(A)$ then we must have $b = \iota(a)$ for a unique $a$, and we set $\sigma(b) = a$. If $b$ does not lie in $\iota(A)$, we set $\sigma(b) = a_0$. (For the cognoscenti: this does not use the Axiom of Choice. The converse does.)

-
It contradicts Cantor's Theorem because Cantor's Theorem says that the set of all subsets of a set must have a greater carindality than the set itself. But what D implies is that the set of all subsets of D is a subset of D, but because the cardinality of P(D) > D, we know that it's wrong. – Jose Jul 24 '13 at 20:40
Is my explanation correct? Do I need to formalize that more? – Jose Jul 24 '13 at 20:52
What you've said is correct. Some people might prefer more attention paid to subtleties in the meaning of $A \leq B$ for sets: this means (right?) that there is an injection $\iota: A \rightarrow B$; $A < B$ means $A \leq B$ and $A \not \equiv B$: there is no bijection between them. What Cantor's Theorem says is that there is no surjection $s: D \rightarrow P(D)$.... – Pete L. Clark Jul 24 '13 at 20:53
By the second paragraph in my answer, this implies that $P(D) \not \leq D$. To get from this to $P(D) > D$ you need (I believe) to use cardinal trichotomy, i.e., that for any two sets $A$ and $B$, either $A < B$, $A \equiv B$ or $A > B$, but this uses The Axiom of Choice. However, we don't need this since we already have both $P(D) \leq D$ and $P(D) \not \leq D$: contradiction. I don't know whether cardinal trichotomy is something you can make use of, so I phrased my answer so as to avoid it. – Pete L. Clark Jul 24 '13 at 20:56
Thanks Pete, I'm fine with keeping this simple as I haven't learned about The Axiom of Choice yet. If possible, can you expand on the subtleties of this proof? I think I have the overall concept right, but I'm missing some details that make it rigorous. – Jose Jul 24 '13 at 20:58

Since you seem to have an "is a set" predicate, I assume you are not using standard ZFC set theory. Not a problem. I also assume you are not necessarily prohibiting set self-membership. Much easier then, without using Cantor's theorem or cardinality, is to first assume to the contrary the existence of your $D$. Then select the subset $R$ of $D$ consisting of those and only those sets are that are not elements of themselves. This leads to the well known contradiction from Russell's Paradox since $R$, the so-called Russell Set, would also itself be a set. So, $D$, as defined here, cannot exist.

-