Calculus

Set Theory

Set Theory Logo

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

\[a \in f\left( a \right),\;b \notin f\left( b \right),\;c \notin f\left( c \right),\;d \notin f\left( d \right),\;e \in f\left( e \right).\]

Hence,

\[B = \left\{ {x \in A \mid x \notin f\left( x \right)} \right\} = \left\{ {b,c,d} \right\}.\]

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

\[n = {n^2} - \left( {2m - 1} \right)n.\]

Solving it, we obtain:

\[n = {n^2} - \left( {2m - 1} \right)n,\;\; \Rightarrow n = {n^2} - 2mn + n,\;\; \Rightarrow {n^2} - 2mn = 0,\;\; \Rightarrow n\left( {n - 2m} \right) = 0.\]

Since \(n \gt 0,\) the solution is given by

\[n = 2m,\;\text{where}\;m \in \mathbb{N}.\]

Thus, the set \(B\) contains all even natural numbers:

\[B = \left\{ {n \in \mathbb{N} \mid n \notin f\left( n \right)} \right\} = \mathbb{E} = \left\{ {m \in \mathbb{N} \mid 2m} \right\}.\]

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.

Page 1 Page 2