State the diagonalization principle

Statement (Lewis & Papadimitriou). Let R be a binary relation on a set A, that is R ⊆ A × A. Let the diagonal set be

D = { a ∈ A : (a, a) ∉ R }

and for each a ∈ A let R_a = { b ∈ A : (a, b) ∈ R } be the "row" of a. Then D is different from every row R_a.

Reason. For any a, a ∈ D iff (a, a) ∉ R iff a ∉ R_a. So D and R_a disagree on the element a, hence D ≠ R_a.

        a1  a2  a3  a4
 a1  [  1   0   1   0 ]   diagonal 1, 0, 0, 1 flipped:
 a2  [  0   0   1   1 ]   D = {a1: 0, a2: 1, a3: 1, a4: 0}
 a3  [  1   1   0   1 ]     = {a2, a3}
 a4  [  0   1   0   1 ]   differs from row i at column i

Consequence. Taking A = N shows that the set of all subsets of N, 2^N, cannot be put in one-to-one correspondence with N, so it is uncountable. The same idea proves that the real numbers are uncountable and that there are languages that are not recursively enumerable.