Show Question
Math and science::Analysis::Tao::08. Infinite sets

# 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:

$A := \{ x \in X : x \notin f(x) \}$

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.

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:

$f(A) := \sum_{n \in A} 10^{-n} \text{, where } A \in 2^\mathbb{N}$

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 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}$