Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 7 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.