Cantor's theorem
Let \( X \) be an arbitrary set (finite or infinite). Then the sets \( X \) and \( 2^X \) cannot have equal cardinality.
Proof, from Tao
Suppose for sake of contradiction that the sets \( X \) and \( 2^X \) had equal cardinality. Then, by the definition of cardinality, there exists a bijection \( f : \rightarrow 2^X \) between \( X \) and the power set of \( X \). Now consider the set:
This set is well defined since \( f(x) \) is an element of \( 2^X \) and is thus a subset of \( X \).
Clearly, \( A \) is a subset of \( X \), hence it is an element of \( 2^X \). Since \( f \) is a bijection, there must therefore exist \( x \in X \) such that \( f(x) = A \). There are now two cases:
- If \( x \in A \), then by definition of \( A \), we have \( x \notin f(x) \), hence \( x \notin A \), a contradiction.
- If \( x \notin A \), then \( x \notin f(x) \), which is sufficient for \( x \in A \), a contradiction.
Russell's paradox
This proof is very similar in spirit to Russell's paradox; the essence being that a bijection between \( X \) to \( 2^X \) would come dangerously close to the concept of a set containing itself.
Example
A consequence of Cantor's theorem is that the reals are uncountable.
The outline of a proof of this is:
- Take the uncountable set \( 2^\mathbb{N} \) and create a function \( f: 2^\mathbb{N} \rightarrow R \) from it to the reals.
- If you can choose \( f \) such that it is injective, then it will be a bijection from \( 2^\mathbb{N} \) to it's image, \( f(2^\mathbb{N}) \).
- The existance of the bijection is sufficient for \( 2^\mathbb{N} \) and \( f(2^\mathbb{N}) \) to have the same cardinality.
- But \( f(2^\mathbb{N}) \) is a subset of \( \mathbb{R} \), so \( \mathbb{R} \) must have cardinality greater than or equal to \( 2^\mathbb{N} \), and thus be uncountable.
Finding such a function \( f \) is the bulk of the work of the proof. An example function is:
This function can be imagined as creating a number represented in decimal:
Input: \( A \in 2^\mathbb{N} \).
Output: X.XXXXXXX.....
Example: \( f(\{1, 3, 5, 6, 7, 10\}) = 0.1010111001 \)
For every natural number \( i \), if \( i \in A \), then set the ith digit to be a 1, otherwise set it to 0.
This function is injective as no two non-equal subsets of the natural numbers can produce the same decimal number.
Proof 2, diagonal argument
A table where each row is an entry of a function from natural numbers to infinite sequences of digits (so we are investigating the cardinality of \( N \) and \( 2^N \)). Taking a diagonal through the table and adding 1 to each entry produces a sequence that can't possibly be in any row. (Might need to clean this up...)
\[ \begin{matrix} 0.& \color{red}9 & 7& 0& 6& \dots\\ 1.& 8 & \color{red}2& 4& 3& \dots\\ 2.& 4 & 5& \color{red}2& 8& \dots\\ 3.& 1 & 2& 5& \color{red}3& \dots\\ \vdots & \vdots & \vdots& \vdots& \vdots& \dots\\ \hline\\ 0.& 8 & 1& 1& 4& \dots\\ \end{matrix}\]
youtube 1