Theory of Computation

We begin with some mathematics regarding uncountability. Let N = {0, 1, 2, 3, . . .} denote the set of natural numbers.

(a)Prove that the set of binary numbers has the same size as N by giving a bijection between the binary numbers and N.

(b)Let B denote the set of all infinite sequences over the English alphabet. Show that B is uncountable using a proof by diagonalization.