# Cantor's diagonal argument

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
Citable Version  [?]

This editable Main Article is under development and subject to a disclaimer.

Cantor's diagonal argument provides a convenient proof that the set ${\displaystyle 2^{\mathbb {N} }}$ of subsets of the natural numbers (also known as its power set) is not countable. More generally, it is a recurring theme in computability theory, where perhaps its most well known application is the negative solution to the halting problem.

## Informal description

The original Cantor's idea was to show that the family of 0-1 infinite sequences is not countable. This is done by contradiction. If this family is countable then its members can be enumerated or enlisted. Such a list gives a table of digits, like in the following arbitrarily chosen example:

0, 1, 0, 1, 0, ...
1, 1, 1, 1, 0, ...
1, 0, 1, 0, 0, ...

Now, we construct a sequence s = (s1, s2, s3, ....), which is not on the list while still, ${\displaystyle s_{i}\in \{0,1\}}$ for all i. This is done as follows. Take ${\displaystyle s_{1}}$ to be different from the first digit of the first member on the list. In our example the digit is 0 (in boldface) and so ${\displaystyle s_{1}}$ is defined to be 1. Take ${\displaystyle s_{2}}$ to be different from the second digit of the second member on the list (in our example ${\displaystyle s_{2}=0}$). Generally, define ${\displaystyle s_{n}}$ as different from the n-th digit of the n-th entry on the list. In other words, the sequence s = (s1, s2, s3, ....) contains "the complement in ${\displaystyle \{0,1\}}$" of the diagonal of our table. It follows that the sequence s itself is not on the list, since it is different from every member by the definition. The list was supposed to contain all the 0-1 sequences. The contradiction shows that such sequences can not be enumerated (or they are not countable).

The role of the diagonal clearly explains the name of the argument.

## Formal argument

To prove that the family of all subsets of ${\displaystyle \mathbb {N} }$ is not countable, we associate to any set ${\displaystyle S\subset \mathbb {N} }$ its characteristic function ${\displaystyle \phi :\mathbb {N} \rightarrow \{0,1\}}$ by setting ${\displaystyle \phi (n)=1}$ if ${\displaystyle n\in S}$ and ${\displaystyle \phi (n)=0}$, otherwise. Conversely, every such function defines a subset. Observe also that every such function corresponds to a 0-1 sequence and vice-versa.

If power set is countable, there is a bijective map ${\displaystyle F:\mathbb {N} \rightarrow 2^{\mathbb {N} }}$, that allows us to assign an index ${\displaystyle i=F^{-1}(S)}$ to every subset S. In other words, all the functions ${\displaystyle \phi :\mathbb {N} \rightarrow \{0,1\}}$ can be enumerated as ${\displaystyle \{\phi _{1},\phi _{2},\phi _{3},\ldots \}}$. Assuming this has been done, we proceed to construct a function ${\displaystyle \psi :\mathbb {N} \rightarrow \{0,1\}}$ that is not in this list. Consequently, the corresponding set, ${\displaystyle T}$ cannot be in the range of ${\displaystyle F}$.

For each ${\displaystyle i}$, either ${\displaystyle \phi _{i}(i)=0}$ or ${\displaystyle \phi _{i}(i)=1}$, and so we define ${\displaystyle \psi (i)=1-\phi _{i}(i)}$. Clearly, ${\displaystyle \psi (i)\in \{0,1\}}$ and ${\displaystyle \psi (i)\not =\phi _{i}(i)}$.

It follows that ${\displaystyle \psi \not =\phi _{i}}$ for any ${\displaystyle i}$, and it must therefore correspond to a set not in the range of ${\displaystyle F}$. This contradiction shows that ${\displaystyle 2^{\mathbb {N} }}$ cannot be countable.

## Application to general sets

More generally, the argument shows that a set cannot be put into one-to-one correspondence with its power set: equivalently, the cardinality of a set is strictly less than that of its power set. The argument proceeds by showing that there cannot be a surjection from a set X to the set PX of subsets of X. Suppose if possible that there were such a surjection f. Form the set

${\displaystyle C=\{x\in X:x\not \in f(x)\}.\,}$

Since C is a subset of X then from the assumption that f is surjective there is an element c of X such that f(c) = C. We now ask whether c is in C. We find that

${\displaystyle c\in C\Leftrightarrow c\in \{x\in X:x\not \in f(x)\}\Leftrightarrow c\not \in f(c)\Leftrightarrow c\not \in C,\,}$

which is a contradiction. Hence the supposition that f is a surjection is untenable. In particular, then, f cannot be a bijection.