Let B be the set of all infinite sequences over Sigma 0 1 S

Let B be the set of all infinite sequences over Sigma = {0, 1}. Show that B is uncountable, using a proof by diagonalization.

Solution

Each element in B is an infinite sequence (b1, b2, b3, . . . . ). Suppose B is countable, then we can show a correspondence f between N = {1, 2, 3, . . .} and B. Let f_n = (b_n1, b_n2, b_n3, . . .) where b_ni is the ith bit in the nth sequence .

Now, the infinite sequence c = (c1, c2, c3, . . .) where c_i = 1-b_ii. Hence, the ith bit in c is the opposite of the ith bit in the ith sequence.

Now, for each c, it differs from the nth sequence in the nth bit. So, c_n is not equal to f(n) for any n, which is a contradiction. Hence, B is uncountable.