Usage: refnametitledateout Massachusetts Institute of Technology Handout 9 6.042J/18.062J: Mathematics for Computer Science September 26, 1995 Professors David Karger and Tom Leighton

Problem Set 4

Due: Start of Class, October 3.

Reading: Sections 1.6, 4.2, 6.2, 6.3 and 6.5 of Discrete Mathematics and its Applications by Kenneth H. Rosen.

Problem 4-1. (a) The following is a matrix that depicts the binary relation “reachable by a non-stop flight” on the set of cities i, 1 ≤ i ≤ 5. In other words entry (i, j) is 1 iff there is a non-stop flight from i to j.

( \begin{matrix}1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{matrix} )

Compute the matrix that represents the relation “reachable by at most two intermediate connections.”

(b) Prove or give a counterexample to the following statement : “Let R be a relation. Then R^{2} = R iff R is transitive and reflexive.”

Problem 4-2. (a) State for each of the following functions (f : ℝ → ℝ) whether

it is a injection, surjection or a bijection. Also, give the inverse if it exists. • sin(x)

• x^{1994}

• x^{1995}

• x/(x^{2} + 5)

(b) Let f(x) = x + 1, g(x) = 2x and h(x) = x^{2} be three functions from ℝ to ℝ. Compute f ∘ g, g ∘ h and f ∘ g ∘ h.

(c) Prove that the composition of two surjective functions is surjective.

Problem 4-3. Show that for all odd natural numbers m there exists an n ≥ 1 such that m|2^{n} − 1.

Problem 4-4. There are n players playing a chess championship in one big hall. Each chess game is between two players and ends in either a draw or win/loss. Furthermore, each player plays any other player at most once. At some point, during the championship the lights in the hall go out. Prove that, at this point, there exist two players, among the n, who have completed the same number of chess games.

Problem 4-5. (a) Show that any subset of a countable set is countable.

(b) Let S_{i}, 1 ≤ i ≤ ∞ be a family of countable sets. Prove that ⋃_{i=1}^{∞}S_{i} is countable.

(c) Is ℝ − ℚ countable? Prove your answer.

Problem 4-6. (a) Use an diagonalization argument to prove that P(ℕ) is not

countable.

(b) Show that |ℝ^{+}| = |ℝ| by exhibiting an explicit bijection. ℝ^{+} denotes the positive reals.