Question

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

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

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

Answer 1

a) is the set of binary numbers

The function is (converting it into the corresponding decimal number)

So that

This is onto as for every number there exists a unique binary representation

And it is one to one as

implies (remainder modulo 2), (remainder modulo 4, plus previous equation) and so on

Thus there is a bijection between

And so the set of binary numbers is exactly as large as the set of natural numbers

b) be the set of infinite sequences of English alphabet

Then if is countable, there exists a bijection from to

Let the enumerator be

Which means we can construct the infinite sequence where each

So this sequence must have a position in the above sequence say as position

But it must differ from (by construction)

Thus, , the set of all infinite sequences over the English alphabet must be uncountable!