Diagonal set complement differs from rows

Setting. Let R_1, R_2, R_3, ... be a list of subsets of the natural numbers (the "rows"). Draw a table whose entry (i, j) is 1 if j ∈ R_i and 0 otherwise.

        1  2  3  4  ...
R_1  [  1  0  1  0 ]
R_2  [  0  0  1  1 ]
R_3  [  1  1  0  1 ]
R_4  [  0  1  0  0 ]

The diagonal set is D = { i : i ∈ R_i }, i.e. the indices i whose diagonal entry (i, i) is 1. Its complement is

D̄ = { i : i ∉ R_i }, obtained by flipping every diagonal entry.

Diagonalization principle. The complement of the diagonal set, D̄, differs from every row R_i.

Justification

Take any row R_i. Look at the single element i.

• If i ∈ R_i, then i ∉ D̄ (by definition of D̄ it contains only those i with i ∉ R_i).
• If i ∉ R_i, then i ∈ D̄.

In both cases, i belongs to exactly one of R_i and D̄. So R_i and D̄ disagree on the element i, hence D̄ ≠ R_i.

Since i was arbitrary, D̄ differs from R_1, R_2, R_3, ... — it differs from the i-th row in the i-th position. Therefore D̄ is not in the list at all. ∎

Use. If every subset of N were in such a list, D̄ would have to be one of the rows, which is impossible. So the set of all subsets of N (and the set of real numbers) is uncountable.