Cantor's Diagonal Argument - An Uncountable Set

An Uncountable Set

Cantor's original proof considers an infinite sequence S of the form (s₁, s₂, s₃, ...) where each element s_i is an infinite sequence of 1s or 0s. This sequence s_i is countable, as to every natural number n we associate one and only one element of the sequence. We might write such a sequence as a numbered list:

s₁ = (0, 0, 0, 0, 0, 0, 0, ...)

s₂ = (1, 1, 1, 1, 1, 1, 1, ...)

s₃ = (0, 1, 0, 1, 0, 1, 0, ...)

s₄ = (1, 0, 1, 0, 1, 0, 1, ...)

s₅ = (1, 1, 0, 1, 0, 1, 1, ...)

s₆ = (0, 0, 1, 1, 0, 1, 1, ...)

s₇ = (1, 0, 0, 0, 1, 0, 0, ...)

...

For each m and n let s_m,n be the nth element of the mth sequence on the list. So, for instance, s_2,1 is the first element of the second sequence.

It is possible to build a sequence s₀ in such a way that its first element is different from the first element of the first sequence in the list, its second element is different from the second element of the second sequence in the list, and, in general, its nth element is different from the nth element of the nth sequence in the list. That is to say, if s_n,n is 1, then s_0,n is 0, otherwise s_0,n is 1. For instance:

s₁ = (0, 0, 0, 0, 0, 0, 0, ...)

s₂ = (1, 1, 1, 1, 1, 1, 1, ...)

s₃ = (0, 1, 0, 1, 0, 1, 0, ...)

s₄ = (1, 0, 1, 0, 1, 0, 1, ...)

s₅ = (1, 1, 0, 1, 0, 1, 1, ...)

s₆ = (0, 0, 1, 1, 0, 1, 1, ...)

s₇ = (1, 0, 0, 0, 1, 0, 0, ...)

...

s₀ = (1, 0, 1, 1, 1, 0, 1, ...)

The elements s_1,1, s_2,2, s_3,3, and so on, are here highlighted, showing the origin of the name "diagonal argument". Each element in s₀ is, by definition, different from the highlighted element in the corresponding column of the table above it. In short, s_0,n ≠ s_n,n.

Therefore this new sequence s₀ is distinct from all the sequences in the list. This follows from the fact that if it were identical to, say, the 10th sequence in the list, then we would have s_0,10 = s_10,10. In general, we would have s_0,n = s_n,n, which, due to the construction of s₀, is impossible. In short, by its definition s₀ is not contained in the countable sequence S.

Let T be a set consisting of all infinite sequences of 0s and 1s. By its definition, this set must contain not only the sequences included in S, but also s₀, which is just another sequence of 0s and 1s. However, s₀ does not appear anywhere in S. Hence, T cannot coincide with S.

Because this argument applies to any countable set S of sequences of 0s and 1s, it follows that T cannot be equal to any such set. Thus T is uncountable: it cannot be placed in one-to-one correspondence with the set of natural numbers .