# 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 i^{th}
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 are the entries 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}

\]