\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \)

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

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.

In either case, 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}
\]

youtube 1