# Diagonalization

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 is uncountable, you typically do a proof by contradiction: assume that 'is' countable, so that there is a surjection , and then find a contradiction by constructing a diabolical object that is not in the image of . This contradicts the surjectivity of , completing the proof.

To construct , you typically imagine an (infinite) table describing : the row describes . In the table, you represent each element of 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 .

You then find by changing every value on the diagonal: you ensure that differs from in the th column. Since for all , , cannot be in the image of , so cannot be surjective.