Hints on Homework.

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 {a₀, a₁, a₂, . . . } 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₀, b₁, b₂, . . . } Choose a₀ to be the first element in this list that is in A, a₁ be the 2nd element in this list that is in A, a₂ be the 3rd element in this list that is in A, etc. Consider the set {a₀, a₁, a₂, . . . }. 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.7-A, the elements of A and B\A can be listed as A = {a₀, a₁, a₂, . . . } and B\A = {c₀, c₁, c₂, . . . } Then A È B = A È (B\A) = {a₀, c₀, a₁, c₁, a₂, c₂, . . . } 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 S₀, S₁, . . . 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₀ È S₁ È S₂ È . . . which is therefore countable. Hence T is countable, being a subset of S₀ È S₁ È S₂ È . . .

    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₁ of bit strings of length 1 has cardinality 2. The set S_n of bit strings of length n has cardinality 2ⁿ. S is the union S₁ÈS₂È. . . 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² + b x + c = 0 where a,b,c are integers, is countable.
    Proof. Let Z³ 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₀, z₁, z₂, . . . }.
    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³ = S₀ È S₁ È S₂ È . . ., so that Z³ is the union of a countable family of countable sets S_n. Hence Z³ is countable. So let us relist the elements of Z³ as {(a₀ , b₀ , c₀ ), (a₁ , b₁ , c₁), . . . } where each a_i , b_i , c_i Î Z. Each (a_i , b_i , c_i) corresponds to a quadratic equation a_i x² + 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₀, y₀, x₁, y₁, x₂, y₂, . . . } 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₁ÈS₂È. . . 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 ₀ , f ₁ , f ₂ , etc., where
    f ₀ is the sequence a_0,0 a_0,1 a_0,2 . . .
    f ₁ is the sequence a_1,0 a_1,1 a_1,2 . . .
    f ₂ 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₀ m₁ m₂ . . . 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 k-th member of the list, then the k-th digit of the k-th member is a_k,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