Exercise 9.6

Question

\def\ca{\mathcal{A}}
\def\cb{\mathcal{B}}
Most of the famous paradoxes of naive set theory are associated in some way or another 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 $\ca$ denotes the ``set of all sets.''
\begin{enumerate}[label=(\alph*)]
\item Show that $\mathcal{P}\left(\caight) \subset \ca$; derive a contradiction.
\item (\emph{Russell's paradox.}) Let $\cb$ be the subset of $\ca$ consisting of all sets that are not elements of themselves:
\begin{gather*}
\cb = \left\{A \mid 	ext{$A \in \ca$ and $A 
otin A$}ight\} \,.
\end{gather*}
(Of course, there may be \emph{no} set $A$ such that $A \in A$;
If such is the case, then $\cb = \ca$.)
Is $\cb$ an element of itself or not?
\end{enumerate}

Dan Whitman · Accepted Answer

\def\ca{\mathcal{A}}
\def\cb{\mathcal{B}}
(a) We show that $\mathcal{P}\left(\caight) \subset \ca$ and that a contradiction results.
\begin{proof}
Consider any set $A \in \mathcal{P}\left(\caight)$.
Since $A$ is a set and $\ca$ is the set of all sets, clearly $A \in \ca$ and hence $\mathcal{P}\left(\caight) \subset \ca$ since $A$ was arbitrary.
Therefore the identity function $i_{\mathcal{P}\left(\caight)}$ is clearly an injection from $\mathcal{P}\left(\caight)$ to $\ca$.
However, this is impossible by Theorem~7.8!
Hence we have reached a contradiction.
\end{proof}

(b) We show that the existence of $\cb$ is a contradiction by showing that supposing either $\cb \in \cb$ or $\cb 
otin \cb$ results in a contradiction.
\begin{proof}
Suppose that $\cb \in \cb$ so that by definition we have $\cb \in \ca$ and $\cb 
otin \cb$, the latter of which clearly contradicts our initial supposition.
On the other hand, suppose that $\cb 
otin \cb$.
Then, since clearly also $\cb \in \ca$ since it is a set, it follows that $\cb \in \cb$ by definition.
This again contradicts the initial supposition.
Since one or the other ($\cb \in \cb$ or $\cb 
otin \cb$) must be true, we are then guaranteed to have a contradiction.
\end{proof}

Exercise 9.6

Answers

Comments

Exercise 9.6

Answers

Comments

Add answer