Cantor’s Theorem
Solved Problems
Example 1.
Let \(A = \left\{ {a,b,c,d,e} \right\}.\) The mapping \(f:A \to \mathcal{P}\left( A \right)\) is defined by
\(f\left( a \right) = \left\{ {a,d,e} \right\},f\left( b \right) = \left\{ {a,c} \right\},\) \(f\left( c \right) = \left\{ {a,b,d,e} \right\},f\left( d \right) = \varnothing,\) \(f\left( e \right) = \left\{ {b,c,e} \right\}.\)
Determine the set \(B = \left\{ {x \in A \mid x \not\in f\left( x \right)} \right\}.\)
Solution.
This set is used in the proof of Cantor's theorem. We see that
Hence,
Example 2.
The mapping function \(f:\mathbb{N} \to \mathcal{P}\left( \mathbb{N} \right)\) is defined by \[f\left( n \right) = \mathbb{N}\backslash \left\{ {{n^2} - \left( {2m - 1} \right)n} \right\},\] where \(n,m \in \mathbb{N}.\) Determine the set \(B = \left\{ {n \in \mathbb{N} \mid n \not\in f\left( n \right)} \right\}.\)
Solution.
The condition \(n \not\in f\left( n \right)\) is met if \(n\) satisfies the equation
Solving it, we obtain:
Since \(n \gt 0,\) the solution is given by
Thus, the set \(B\) contains all even natural numbers:
Example 3.
Prove that the set of all sets does not exist.
Solution.
Assume, by contradiction, that the set of all sets exists and denote it by \(S.\) Then its power set \(\mathcal{P}\left( S \right)\) exists as well.
Every element of \(\mathcal{P}\left( S \right)\) is a set. Therefore \(\mathcal{P}\left( S \right)\) is contained in \(S,\) and we get \(\left| \mathcal{P}\left( S \right)\right| \le \left|S\right|.\)
From the other side, according to Cantor's theorem, we know that \(\left|S\right| \lt \left|\mathcal{P}\left( S \right)\right|.\)
We have a contradiction. This means that the set of all sets does not exist.