Diagonalization

From CS2800 wiki

A common technique to prove that a set is uncountable is called diagonalization.

The most famous examples of diagonalization are the proofs that the power set of the naturals is uncountable and the set of reals is uncountable.

To use diagonalization to prove that a set [math]X [/math] is uncountable, you typically do a proof by contradiction: assume that [math]X [/math] 'is' countable, so that there is a surjection [math]f : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%5Cto}{\to} X [/math], and then find a contradiction by constructing a diabolical object [math]x_D \href{/cs2800/wiki/index.php/%E2%88%88}{∈} X [/math] that is not in the image of [math]f [/math]. This contradicts the surjectivity of [math]f [/math], completing the proof.

To construct [math]x_D [/math], you typically imagine an (infinite) table describing [math]f [/math]: the [math]i [/math] row describes [math]f(i) [/math]. In the table, you represent each element of [math]X [/math] as an infinite sequence of values; so that the table has a column for each natural number. The exact structure of the table depends on the set [math]X [/math].

You then find [math]x_D [/math] by changing every value on the diagonal: you ensure that [math]x_D [/math] differs from [math]f(i) [/math] in the [math]i [/math]th column. Since for all [math]k [/math], [math]x_D ≠ f(k) [/math], [math]x_D [/math] cannot be in the image of [math]f [/math], so [math]f [/math] cannot be surjective.