Section 9: Problem 6 Solution

Working problems is a crucial part of learning mathematics. No one can learn topology merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

Most of the famous paradoxes of naive set theory are associated in some way or other with the concept of the "set of all sets." None of the rules we have given for forming sets allows us to consider such a set. And for good reason--the concept itself is self-contradictory. For suppose that $\mathcal{A}$ denotes the "set of all sets."

(a) Show that $\mathcal{P}(\mathcal{A})\subset\mathcal{A}$ ; derive a contradiction.

(b) (Russell’s paradox.) Let $\mathcal{B}$ be the subset of $\mathcal{A}$ consisting of all sets that are not elements of themselves; $\mathcal{B}=\{A|A\in\mathcal{A}\mbox{ and }A\notin A\}.$ (Of course, there may be no set $A$ such that $A\in A$ ; if such is the case, then $\mathcal{B}=\mathcal{A}$ .) Is $\mathcal{B}$ an element of itself or not?

(a) $\mathcal{P}(A)$ is the set of all subsets of $\mathcal{A}$ , and every subset is a set itself and is in the "set of all sets", hence, $\mathcal{P}(\mathcal{A})\subset\mathcal{A}$ . Therefore, there is a surjection $f$ from $\mathcal{A}$ onto $\mathcal{P}(\mathcal{A})$ , contradicting Theorem 7.8. Namely, let $\mathcal{B}=\{B\in\mathcal{A}|B\notin f(B)\}$ . We have $\mathcal{B}\in\mathcal{P}(\mathcal{A})$ , but for every $B\in\mathcal{A}$ : $B\in f(B)$ iff $B\notin\mathcal{B}$ , implying $f(B)\neq\mathcal{B}$ . Therefore, $f$ is not surjective. The second part of the proof is based on the Cantor's theorem.

(b) Neither. In other words, for every $B\in\mathcal{A}$ , $B\in\mathcal{B}$ iff $B\notin B$ , implying $B\neq\mathcal{B}$ . In particular, $\mathcal{B}\neq\mathcal{B}$ .

Subpages

Section 9: Problem 6 Solution

Section 9: Problem 6 Solution