Exercise 1.6.7

Question

%1.6.7
Return to the particular functions constructed in \href{./exercise_1-6-6}{Exercise 1.6.6} 
and construct the subset $B$ that results using the preceding rule. In each case, note that $B$ is not in the range of the function used.

Ulisse Mini · Accepted Answer

See the proof of Cantor's theorem:

\begin{theorem}[Cantor's Theorem]
  Given any set $A$, there does not exist a function $f: A ightarrow P(A)$ that is onto.
\end{theorem}

\begin{proof}
  Suppose $f : A 	o P(A)$ is onto. We want to use the self-referential nature of $P(A)$ to find a contradiction. Define
  $$
  B = \{a : a 
otin f(a)\}
  $$
  Since $f$ is onto we must have $f(a) = B$ for some $a \in A$. Then either
  \begin{enumerate}[label=(oman*)] 
  \item $a \in B$ implies $a \in f(a)$ which by the definition of $B$ implies $a 
otin B$, so $a \in B$ is impossible.
  \item $a 
otin B$ implies $a 
otin f(a)$ since $f(a) = B$. but if $a 
otin f(a)$ then $a \in B$ by the definition of $B$, contradicting $a 
otin B$.
   \end{enumerate}
  Therefore $f$ cannot be onto, since we have found a $B \in P(A)$ where $f(a) = B$ is impossible.

Stepping back, the pearl of the argument is that if $B = f(a)$ then $B = \{a : a 
otin B\}$ is undecidable/impossible.
\end{proof}

Exercise 1.6.7

Answers

Comments

Exercise 1.6.7

Answers

Comments

Add answer