Question

Let S denote the set of all possible finite binary strings, i.e. strings of finite length made up of only 0s and 1s, and no other characters. E.g., 010100100001 is a finite binary string but 100ff101 is not because it contains characters other than 0, 1.

a. Give an informal proof arguing why this set should be countable. Even though the language of your proof can be informal, it must clearly explain the reasons why you think the set should be countable. HINT: Try to argue that it is possible to arrange the elements of S into an infinite sequence.

b. Now assume that we have proved that S is indeed countable. Use this fact to prove (formally, this time) that the following set, denoted by T, is also countable: T = {X ⊆ N| |X| is finite and is a prime number}. HINT: You might want to first argue that the set {X ⊆ N| |X| is finite} is countable.

Answer 1