Massachusetts Institute of Technology Handout 44 6.042J/18.062J: Mathematics for Computer Science October 30, 1998 Professors Nancy Lynch and Srinivas Devadas

Problem Set 7 Solutions

Read sections 4.1, 4.2, and 4.3 in Rosen.

Problem 1. (10 points) For each of the functions below, determine whether the function is injective, whether it is surjective, and whether it is bijective. No proofs are required.

(a) The function f : ℝ ↦ ℝ defined by f(x) = e^{x}

The function is injective because e^{x} = e^{y} if and only if x = y. The function is not surjective, because e^{x} never takes on non-positive values. The function is not bijective, because it is not surjective.

(b) The function f : ℝ ↦ ℝ^{+} defined by f(x) = e^{x}. (Here ℝ^{+} denotes the set of positive real numbers.)

The function is injective as before, but is now also surjective because for every y ∈ ℝ^{+}, there exists an x (namely x = ln y) such that y = e^{x}. Therefore, the function is bijective.

(c) The function f : ℝ ↦ ℝ defined by (x + 1)/(x^{2} + 1)

The function is not injective, because f(0) = f(1) = 1. The function is not surjective, because the function never takes on large positive or negative values. The function is not bijective because it is neither injective nor surjective.

(d) The function f : ℝ ↦ ℝ defined by

f(x) = \{ \begin{matrix}1/x & for x ≠ 0 \\ 0 & for x = 0. \end{matrix}

The function is injective, because f(x) = f(y) if and only if x = y. The function is surjective, because for all y ∈ ℝ, there exists an x (namely x = 1/y or x = 0) such that f(x) = y. Therefore, the function is also bijective.

Problem 2. (10 points) Suppose that f is a function of the form f : A ↦ B, and g is a function of the form g : B ↦ C. The composed function g ∘ f has domain A, range C, and is defined by (g ∘ f)(a) = g(f(a)).

(a) Prove that if the composition g ∘ f is a bijection, then f is an injection and g is a surjection.

Proof. Suppose that g ∘ f is a bijection.

Assume for the purpose of contradiction that f is not an injection. Then there exist elements a_{1}, a_{2} ∈ A, such that f(a_{1}) = f(a_{2}). This implies that g(f(a_{1})) = g(f(a_{2})). Therefore, g ∘ f is not an injection and thus not a bijection. This is a contradiction; therefore, f must be an injection.

Now assume for the purpose of contradiction that g is not a surjection. Then there exists an element c ∈ C such that for all b ∈ B, g(b) ≠ c. Therefore, for all a ∈ A, g(f(a)) ≠ c. This implies that g ∘ f is not a surjection and thus not a bijection. This is again a contradiction; therefore, g must be a surjection.

(b) If f is an injection and g is a surjection, then is g ∘ f necessarily a bijection?

No. For example, consider the following setup.

A = {1}
B = {1, 2}
C = {1, 2}
f(x) = x
g(x) = x

In this case, f is injective, g is surjective, but g ∘ f is not bijective.

Problem 3. (20 points) Prove or disprove the following statements about sets. (We use “collection” as a synonym for “set” to make some of the statements easier to read.)

(a) The product of a finite collection of countable sets is countable.

The statement is true. Proof. The proof is by induction. Let P (n) be the proposition that the product of n countable sets is countable. In the base case, P (1) is true because the product of a single countable set is itself. In the inductive step, for n ≥ 1 assume P (n) to prove P (n + 1). The product of n + 1 countable sets S_{1}, S_{2}, …, S_{n+1} can be written as shown below.

(S_{1} × S_{2} × … × S_{n}) × S_{n+1}

The first term is a countable set by induction, and the second term is a countable set by definition. The product of two countable sets is countable, as shown in lecture. Therefore, the product of n + 1 countable sets is countable. This shows that P (n) implies P (n + 1), and the claim is proved by induction.

(b) The product of a countable collection of finite sets is countable.

The statement is false. We will construct a bijection between the product of a countable number of finite sets and the power set of the natural numbers. Since the latter is uncountable, the former must be uncountable as well. Consider the countable collection of finite sets S_{1} = S_{2} = … = {0, 1}. The product S_{1}×S_{2}×… consists of all infinite binary sequences, e.g. (0, 1, 1, 0, 1, …). There is a natural bijection between such infinite binary sequences and the power set of the natural numbers. In particular, let the sequence (b_{0}, b_{1}, …) correspond to the set of all natural numbers i such that b_{i} = 1. This bijection implies that the set of infinite binary sequences is uncountable.

(c) The set of all finite subsets of a countable set is countable.

The statement is true. Proof. Let S be a countable set. For k ≥ 0, let S_{k} be the set of k-element subsets of S. The set of all finite subsets of S is then the union of the sets S_{k} for k ≥ 0. We will prove below that every set S_{k} is countable. This will imply that the set of all finite subsets of S is a union of a countable collection of countable sets and is therefore countable.

All that remains is to show that S_{k}, the set of k-element subsets of S, is countable for all k ≥ 0. We prove this by establishing an injection from S_{k} to S^{k}, the product of the set S with itself taken k times. In particular, the injection maps the set {s_{1}, s_{2}, … s_{k}} ∈ S_{k} to the tuple (s_{1}, s_{2}, …, s_{k}) ∈ S^{k}, where the elements in the tuple are ordered in an arbitrary way. Since S^{k} is countable, the injection implies that S_{k} is also countable.

(d) Suppose that the intersection of a countable collection of sets is finite. Then there exists a finite subcollection of the sets with finite intersection.

The statement is false. Let S_{k} be the set of integers divisible by k, for k ≥ 1. The intersection of this countable family of sets is finite; in fact, the intersection is {0}, since zero is the only integer divisible by every positive integer. However, there is no finite subfamily of sets S_{k} with finite instersection. In particular, the intersection of the finite subfamily

S_{a_{1}} ∩ S_{a_{2}} ∩ … ∩ S_{a_{n}}

contains all integers of the form m · a_{1} · a_{2} ⋯ a_{n} where m ∈ ℤ.

Problem 4. (20 points) A real number is algebraic if it is the root of a polynomial with rational coefficients. A number that is not algebraic is called transcendental.

(a) Prove that the set of polynomials of degree d with rational coefficients is countable, for all d ≥ 1.

There is a natural bijection between degree d polynomials and elements of the set (ℚ \ {0}) × ℚ^{d}. Specifically, a degree d polynomial is mapped to an element of this set by arranging the coefficients in a (d + 1)-tuple. The set of rational numbers, ℚ, was shown to be countable in lecture. In the preceding problem, we showed that a finite product of countable sets is countable. Therefore, the set (ℚ \ {0}) × ℚ^{d} is countable. The bijection then implies that the degree d polynomials are countable.

(b) Prove that the set of all real roots of degree d polynomials with rational coefficients is countable. (You may use the fact that a degree d polynomial with rational coefficients has at most d real roots).

Each specific polynomial of degree d has a finite number of roots, according to the fact in the problem statement. There are a countable number of polynomials of degree d, according to the previous problem part. Since the union of a countable collection of finite sets is countable, the set of all real roots of degree d polynomials with rational coefficients is countable.

(c) Prove that the set of algebraic numbers is countable.

The set of algebraic numbers is the union over all d of all the roots of polynomials of degree d. This is a countable union of countable sets, and is therefore countable.

(d) Prove there exists at least one transcendental number.

The set of real number is uncountable. The subset of algebraic numbers is countable. Therefore, the algebraic numbers form a proper subset of the real numbers, and so there is at least one transcendental number.

Problem 5. (15 points) Prove that among every set of 52 integers, there exists a pair with sum or difference divisible by 100.

We assign each of the 52 numbers to one of 51 bins, which are defined as follows.

First, we define 49 “ordinary” bins. Let bin 1 contain numbers congruent to 1 or 99 modulo 100. Let bin 2 contain numbers congruent to 2 to 98 modulo 100. Continuing in this vein, let bin 49 contain numbers congruent to 49 or 51 modulo 100. Now we define two “special” bins. Let bin 0 contain numbers congruent to 0 modulo 100, and let bin 50 contain numbers congruent to 50 modulo 100.

By the Pigeonhole Principle, at least two numbers are assigned to the same bin. If two numbers are assigned to an ordinary bin and are congruent modulo 100, then their difference is divisible by 100. If two numbers are assigned to an ordinary bin and are not congruent modulo 100, then their sum is divisible by 100. If two numbers are assigned to a special bin, then both their sum and their difference is divisible by 100.

Problem 6. (25 points) Theory Pig has often complained that the name “Pigeonhole Principle” is verbose and awkward. He proposes the more concise term “Pig Principle” for the same idea. Recently, he devised a couple problems involving this idea in order to promote his terminology.

(a) Suppose that m pigs are lined up, and each pig is given one or more tasty treats. Prove that there is always a set of pigs that are consecutive in the lineup and that all together receive a number of treats that is a multiple of m. For example, suppose that there are m = 5 pigs, and that they receive 1, 6, 2, 7, and 9 treats respectively. Then the claim holds in this case, because the second, third, and fourth pigs received 6 + 2 + 7 = 15 treats altogether, and 15 is a multiple of 5.

Let P_{i} be the total number of treats given out to the first i pigs. There are two cases. In the first case, suppose that at least one of P_{1}, P_{2}, …, P_{m} is congruent to 0 modulo m. In particular, suppose that P_{j} is congruent to 0 modulo m. This implies that the number of treats received by the first j pigs is a multiple of m, and so the claim holds. In the second case, suppose that none of P_{1}, P_{2}, …, P_{m} is congruent to 0 modulo m. Then each of the m terms P_{1}, P_{2}, …, P_{m} is congruent to one of the m − 1 values 1, 2, …, m − 1 modulo m. By the Pig Principle, there are at least two terms P_{j} and P_{k} that are congruent to the same value modulo m. Thus pigs j + 1, j + 2, …, k received a total of P_{k} − P_{j} treats, which is a multiple of m.

(b) Suppose that during each day of an 13-week term, a certain theoretically-inclined pig receives at least one affectionate pat. However, suppose that this pig never receives more than 12 pats in any one of the 13 weeks, on account of his being underappreciated by the TA staff. Prove that there exists a sequence of consecutive days during which the pig receives exactly 25 affectionate pats.

Let P_{i} be the total number of pats that the pig receives in the first i days. Since he gets least one pat every day, the sequence P_{1}, P_{2}, …, P_{91} is strictly increasing. Since he gets at most 12 pats per week, the final term, P_{91}, is at most 13·12 = 156. Now the sequence P_{1} + 25, P_{2} + 25, …, P_{91} + 25 is also strictly increasing, and the largest term, P_{91} + 25, is at most 156 + 25 = 181. Therefore, the 182 values P_{1}, …, P_{91} and P_{1} + 25, …, P_{91} + 25 all lie between 1 and 181. By the Pig Principle, at least two of these values must be the same. Since no two of the numbers P_{1}, …, P_{91} are equal, and no two of the numbers P_{1} + 25, …, P_{91} + 25 are equal, there must be an i and a j such that P_{i} = P_{j} + 25. This implies that on days j + 1, j + 2, … i, the pig receives exactly 25 affectionate pats.

Fat chance.