# 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.7-A. A set S is countable if and only if its elements can be put into a list {a0, a1, a2, . . . } where ai ¹ aj whenever i ¹ j.
Proof. Suppose such a list is possible, then the mapping f (n) = an for n = 0,1,2,... is a mapping from N onto S. Each member an will be an image of some n, hence f is surjective. If i < j, then ai will precede aj in the list, so that ai ¹ aj. 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 {b0, b1, b2, . . . } Choose a0 to be the first element in this list that is in A, a1 be the 2nd element in this list that is in A, a2 be the 3rd element in this list that is in A, etc. Consider the set {a0, a1, a2, . . . }. Define a mapping f : N®A with f (n) = an for n = 0, 1, 2, . . . If i < j in N, then ai ¹ aj. Hence f is injective. Conversely, any element of A must appear as bm for some m Î N, and will inevitably be taken up as ak for some k. Hence bm = 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.7-A, the elements of A and B\A can be listed as A = {a0, a1, a2, . . . } and B\A = {c0, c1, c2, . . . } Then A È B = A È (B\A) = {a0, c0, a1, c1, a2, c2, . . . } is a list whose elements are all distinct and also includes all elements of A È B. Hence by Thm. 1.7-A, 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 S0, S1, . . . Each of these sets is countable, hence we can list its elements by Si = {ai,0 , ai,1 , ai,2 , . . . }. Let T be the union of all the Si's. Since the Si's may overlap, T is made up of a subset of the list of elements {a0,0 , a0,1 , a1,0 , a2,0 , a1,1 , a0,2 , a3,0 , a2,1 , a1,2 a0,3 , . . . } which is a union of the sublists
a0,0
a0,1 , a1,0
a2,0 , a1,1 , a0,2
a3,0 , a2,1 , a1,2 a0,3
. . . . .
Obviously, this list exhausts all the elements of S0 È S1 È S2 È . . . which is therefore countable. Hence T is countable, being a subset of S0 È S1 È S2 È . . .

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 S1 of bit strings of length 1 has cardinality 2. The set Sn of bit strings of length n has cardinality 2n. S is the union S1ÈS2È. . . 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 x2 + b x + c = 0 where a,b,c are integers, is countable.
Proof. Let Z3 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 {z0, z1, z2, . . . }.
For each n Î N, let Sn =def { (zi, zj, zk) : i + j + k = n and i,j,k ³ 0}. Let (a,b,c) be any ordered triple of integers in Z. Then a = zi, b = zj, c = zk for some i, j, k. Let n = i + j + k. Hence (a,b,c) Î Sn. This proves that Z3 = S0 È S1 È S2 È . . ., so that Z3 is the union of a countable family of countable sets Sn. Hence Z3 is countable. So let us relist the elements of Z3 as {(a0 , b0 , c0 ), (a1 , b1 , c1), . . . } where each ai , bi , ci Î Z. Each (ai , bi , ci) corresponds to a quadratic equation ai x2 + bi x + ci = 0, which has at most 2 roots, which we represent as xi and yi. Then the list {x0, y0, x1, y1, x2, y2, . . . } 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 Sm of possible strings of length m has cardinality Nm. Hence S" = S1ÈS2È. . . 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 n-th 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 a0,0 a0,1 a0,2 . . .
f 1 is the sequence a1,0 a1,1 a1,2 . . .
f 2 is the sequence a2,0 a2,1 a2,2 . . .
and so on, where each ai,j is a digit between 0 and 9.
Now consider the sequence M = m0 m1 m2 . . . where mi = 1 if ai,i ¹ 1, and 2 if ai,i = 1. This sequence represents some function g from N to N', yet g cannot appear in the list. If g were the k-th member of the list, then the k-th digit of the k-th member is ak,k, different from the k-th 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