

Hints on Homework.
Rosen's Discrete Math Section 1.7
by Peter Y. Woo, Revised: 3/06/2000
Warning. Even if you memorized and reproduce the following
proofs, you still only get 70% score, unless you draw a good diagram
for each problem.
Preliminaries.
Theorem 1.7A. A set S is countable if and only if
its elements can be put into a list {a_{0}, a_{1}, a_{2}, . . . } where a_{i}
¹ a_{j} whenever i ¹ j.
Proof. Suppose such a list is possible, then the
mapping f (n) = a_{n} for n = 0,1,2,... is a mapping from N onto S.
Each member a_{n} will be an image of some n, hence f is surjective.
If i < j, then a_{i} will precede a_{j} in the list, so that a_{i}
¹ a_{j}. Thus f is injective, so that f is a bijection from N
onto S. Thus S is countable.
Conversely, if S is countable, there is then some bijection
f : N ® S. Thus {f(0), f(1), f(2), . . . } is a list which exhausts
all elements of S and that no two elements in the list are the same.
QED
Problem 34. Prove that a subset A of a countable set
B is countable.
Proof. If A is finite, then A is countable, by
definition. Hence henceforth asume A is infinite. Thus B is infinite too.
Since B is countable, we can list its elements as {b_{0}, b_{1}, b_{2}, . . . }
Choose a_{0} to be the first element in this list that is in A,
a_{1} be the 2nd element in this list that is in A,
a_{2} be the 3rd element in this list that is in A, etc.
Consider the set {a_{0}, a_{1}, a_{2}, . . . }. Define a mapping f : N®A
with f (n) = a_{n} for n = 0, 1, 2, . . . If i < j in N, then a_{i}
¹ a_{j}. Hence f is injective. Conversely, any element of A
must appear as b_{m} for some m Î N, and will inevitably be taken
up as a_{k} for some k. Hence b_{m} = f (k) for some k. Thus
f is surjective, and then is a bijection from N onto A.
Hence A is countable.
Problem 36. Show that the union of two countable
sets is countable.
Proof. Let A and B be the two countable sets.
Then B\A is countable due to Prob. 34. From Thm. 1.7A, the elements
of A and B\A can be listed as A = {a_{0}, a_{1}, a_{2}, . . . } and
B\A = {c_{0}, c_{1}, c_{2}, . . . } Then A È B = A È (B\A)
= {a_{0}, c_{0}, a_{1}, c_{1}, a_{2}, c_{2}, . . . } is a list whose
elements are all distinct and also includes all elements of A È B.
Hence by Thm. 1.7A, A È B is countable.
Problem 33. Prove that if A is uncountable and B is
countable, then A\B is uncountable.
Proof. If A\B were countable, then A = B È
(A\B) is the union of the countable sets B and A\B, hence by Prob. 36
A is countable, which is absurd.
Problem 35. Prove that if A is uncountable and
A Í B, then B is uncountable.
Proof. Suppose the contrary. Then B is countable,
so A, which is a subset of B, is countable, by Prob. 34. This is absurd.
Problem 37**. Prove that the union of a countable
family of countable sets is countable.
Proof. Since the family is countable, we can
name the sets as S_{0}, S_{1}, . . . Each of these sets is countable,
hence we can list its elements by S_{i} = {a_{i,0} , a_{i,1} ,
a_{i,2} , . . . }. Let T be the union of all the S_{i}'s.
Since the S_{i}'s may overlap, T is made up of a subset of the
list of elements {a_{0,0} , a_{0,1} , a_{1,0} , a_{2,0} ,
a_{1,1} , a_{0,2} , a_{3,0} , a_{2,1} , a_{1,2} a_{0,3} , . . . }
which is a union of the sublists
a_{0,0}
a_{0,1} , a_{1,0}
a_{2,0} , a_{1,1} , a_{0,2}
a_{3,0} , a_{2,1} , a_{1,2} a_{0,3}
. . . . .
Obviously, this list exhausts all the elements of
S_{0} È S_{1} È S_{2} È . . . which is therefore countable.
Hence T is countable, being a subset of S_{0} È S_{1} È S_{2} È . . .
Problem 38*. Prove that the set S of rational numbers
between 0 and 1 is countable.
Proof. Consider the list L = {0, 1, 1/2,
1/3, 2/3, 1/4, 2/4, 3/4, 1/5, 2/5, 3/5, 4/5, ... } which obviously
exhausts all rational numbers in S, plus some more, because 1/2
and 2/4 and 3/6 all appear in the list but they represent the same
rational number. Hence the set S of rational numbers is a subset of L,
and hence is countable, by Prob. 34.
Problem 39*. Show that the set of all bit strings
is countable.
Proof. Let S be this set. Each bit string
is of finite length. The set S_{1} of bit strings of length 1 has cardinality 2.
The set S_{n} of bit strings of length n has cardinality 2^{n}. S is
the union S_{1}ÈS_{2}È. . . Hence S is a union of a countable number
of countable sets. By Problem 37. S is countable. QED
Problem 40*. Prove that the set S of real numbers
that are solutions of some quadratic equation a x^{2} + b x + c = 0
where a,b,c are integers, is countable.
Proof. Let Z^{3} denote the set of ordered
triples (a,b,c) where a,b,c Î Z. Z is countable because its elements
can be listed as {0, 1, 1, 2, 2, 3, 3, . . . }, which we shall
rename as {z_{0}, z_{1}, z_{2}, . . . }.
For each n Î N, let S_{n} =_{def}
{ (z_{i}, z_{j}, z_{k}) : i + j + k = n and i,j,k ³ 0}.
Let (a,b,c) be any ordered triple of integers in Z. Then a = z_{i},
b = z_{j}, c = z_{k} for some i, j, k. Let n = i + j + k. Hence
(a,b,c) Î S_{n}. This proves that Z^{3} = S_{0} È S_{1} È
S_{2} È . . ., so that Z^{3} is the union of a countable family of
countable sets S_{n}. Hence Z^{3} is countable.
So let us relist the elements of Z^{3} as
{(a_{0} , b_{0} , c_{0} ), (a_{1} , b_{1} , c_{1}), . . . } where each a_{i} ,
b_{i} , c_{i} Î Z. Each (a_{i} , b_{i} , c_{i})
corresponds to a quadratic equation a_{i} x^{2} + b_{i} x + c_{i} = 0,
which has at most 2 roots, which we represent as x_{i} and y_{i}.
Then the list {x_{0}, y_{0}, x_{1}, y_{1}, x_{2}, y_{2}, . . . } exhausts
all the elements of S. Hence S is countable.
Problem 41*. Prove that the set of all computer
programs in a particular programming language is countable.
Proof. Each such program is a finite string of
a finite alphabet A, with N characters. For example, if A is the ASCII
set, N = 96. The set S of all possible programs
is a subset of the set S" of all finite strings built from the alphabet.
The set S_{m} of possible strings of length m has
cardinality N^{m}. Hence S" = S_{1}ÈS_{2}È. . . is a union
of countable number of finite sets, hence S" is countable. Hence S
Í S" is also countable, due to Problem 34.
Problem 42*. Prove that the set of functions
from N to N' =_{def} {0, 1, 2, . . . , 9} is uncountable.
1st Proof. Let F be the set of such functions.
Suppose F were countable, then there is some bijection f: N®F.
Denote f(n) by f _{n}. Now define a function g: N®N' such
that for each i Î N, g(i) = 1 if f _{i}(i) ¹ 1, and 0 otherwise.
Then g Î F because it is a function from N into N'. But there is
no n such that f(n) = f _{n} = g. For if there is such an n, f _{n}(n)
should = g(n), which contradicts g(n) ¹ f _{n}(n). Hence f(F)
does not contain g, contradicting the surjectivity of f. Conclusion:
F cannot be countable. Hence F is uncountable. QED
2nd Proof. Each such function f is representable by
an infinite sequence of digits between 0 and 9, so that the nth digit
represent f (n). Now suppose F were countable. Then all its functions
can be listed as f _{0} , f _{1} , f _{2} , etc., where
f _{0} is the sequence a_{0,0} a_{0,1} a_{0,2} . . .
f _{1} is the sequence a_{1,0} a_{1,1} a_{1,2} . . .
f _{2} is the sequence a_{2,0} a_{2,1} a_{2,2} . . .
and so on, where each a_{i,j} is a digit between 0 and 9.
Now consider the sequence M = m_{0} m_{1} m_{2} . . .
where m_{i} = 1 if a_{i,i} ¹ 1, and 2 if a_{i,i} = 1.
This sequence represents some function g from N to N', yet g cannot
appear in the list. If g were the kth member of the list, then
the kth digit of the kth member is a_{k,k}, different from the
kth digit of sequence M. This defies the assumption that all functions
of F can be put into a list. Hence F is not countable. QED
Problem 43*. Define a function is computable if there
is a computer program that finds the values of the function. Show that
there are functions that are not computable.
Proof. The set S of possible computer programs is
countable. The set of computer programs, each can compute only one function
is a subset of S, hence is countable. Hence the set F of
computable functions are countable. Let f: N®F be a bijection.
Define a function g: N®N'={0,1,2,3,4,5,6,7,8,9}, so that
for each n Î N, g(n) = 1 if f(n)(n) ¹ 1, and 0 otherwise.
Then g cannot be a member of F. Hence g is not computable. QED
