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

Problem Set 7

Due: Start of class on October 27, 1998.

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}

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

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

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

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

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.

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

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.

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

(c) The set of all finite subsets of a countable set is 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.

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.

(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).

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

(d) Prove there exists 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.

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.

(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.