Determine whether each of these sets is countable or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set. (a) all bit strings not containing the bit 0 (b) all positive rational numbers that cannot be written with denominators less than 5 (c) the real numbers not containing 0 in their decimal representation (d) The real numbers containing only a finite number of 1s in their decimal representation

If A is countable then there exists an injective mapping f : A → Z+ which, for any S ⊆ A gives an injective mapping g : S → Z+ thereby establishing that S is countable. The contrapositive of this is: if a set is not countable then any superset is not countable.

(a) The rational numbers are countable (done in class) and this is a subset of the rational. Hence this set is also countable.

(b) this set is not countable. For contradiction suppose the elements of this set in (0,1) are enumerable. As in the diagonalization argument done in class we construct a number, r, in (0,1) whose decimal representation has as its i th digit (after the decimal) a digit different from the i th digit (after the decimal) of the i th number in the enumeration. Note that r can be constructed so that it does not have a 0 in its representation. Further, by construction r is different from all the other numbers in the enumeration thus yielding a contradiction