1. A mysterious predicate

Suppose we start with the standard Peano axioms

and add a new predicate Q(x,y), defined by the axioms

  1. ∀x Q(0, x).
  2. ∀x Q(x, 0) ⇒ x = 0.
  3. ∀x ∀y Q(x,y) ⇔ Q(Sx, Sy).

Prove each of the following statements:

  1. ∀x Q(x, Sx).
  2. ∀x ∀y Q(x, y) ∧ Q(y, x) ⇒ x = y.

You may find it helpful to use the theorem proved in class that ∀x x ≠ 0 ⇒ ∃y x = Sy. (You do not need to prove this theorem.)

1.1. Solution

  1. By induction on x. For x = 0, we have Q(0, S0) from the first Q axiom. Now suppose the statement holds for x, i.e. that Q(x, Sx). From the last Q axiom, we have Q(Sx, SSx); but this is the statement for Sx.
  2. Again by induction on x. Our induction hypothesis is ∀y Q(x, y) ∧ Q(y, x) ⇒ x = y. When x = 0, this becomes ∀y Q(0, y) ∧ Q(y, 0) ⇒ 0 = y. But Q(y, 0) by itself implies y = 0 by the second Q axiom. Now suppose the hypothesis holds for some x, and consider the hypothesis for Sx: ∀y Q(Sx, y) ∧ Q(y, Sx) ⇒ Sx = y. Fix y, and suppose Q(Sx, y) ∧ Q(y, Sx). From Q(Sx, y) we have that y ≠ 0 (otherwise we have Sx = 0, which is forbidden by PA1). Write y as Sz; then Q(Sx, Sz) ∧ Q(Sz, Sx), from which we get Q(x, z) ∧ Q(z, x) using the last Q axiom. The induction hypothesis then gives x = z, from which Sx = Sz = y follows.

(If you haven't figured it out already, Q(x,y) is true precisely when x ≤ y.)

2. Some sums

Compute a closed-form expression for each of the following sums:

\begin{align} \sum_{i=1}^{n} \sum_{j=1}^{m} &(i+j) \\ \sum_{i=1}^{n} \sum_{j=1}^{m} &ij \end{align}

2.1. Solution

\begin{align*} \sum_{i=1}^{n} \sum_{j=1}^{m} (i+j) &= \sum_{i=1}^{n} \sum_{j=1}^{m} i + \sum_{i=1}^{n} \sum_{j=1}^{m} j \\ &= \sum_{j=1}^{m} \sum_{i=1}^{n} i + \sum_{i=1}^{n} \sum_{j=1}^{m} j \\ &= \sum_{j=1}^{m} \frac{n(n+1)}{2} + \sum_{i=1}^{n} \frac{m(m+1)}{2} \\ &= \frac{mn(n+1)}{2} + \frac{nm(m+1)}{2} \\ &= \frac{nm}{2}(n+m+2). \end{align*}

Quick check, just to make sure we didn't make a mistake: for n=2, m=3, we get (2+3+4)+(3+4+5) = 21 by summing directly and (6/2)(7) = 21 from the formula.

The second one is easier, since we can split the sum into a product of two sums using the distributive law.

\begin{align*} \sum_{i=1}^{n} \sum_{j=1}^{m} ij &= \left(\sum_{i=1}^{n} i\right) \left(\sum_{j=1}^{m} j\right) \\ &= \left(\frac{n(n+1)}{2}\right) \left(\frac{m(m+1)}{2}\right) \\ &= \frac{nm(n+1)(m+1)}{4}. \end{align*}

Quick check for this one, again with n=2, m=3: (1+2+3)+(2+4+6) = 18, vs (2⋅3⋅3⋅4)/4 = 18.

3. Injections

Let f:A→B, g:B→C, and h:C→D be functions. Suppose h∘g∘f is surjective. For each of the following statements, prove it or give a counterexample:

  1. f is surjective.
  2. g is surjective.
  3. h is surjective.

3.1. Solution

First, let's show that f and g need not be surjective. Let D = {1} and let {A} = {B} = {C} = {1,2}. Let f, g, and h all be constant functions that always output 1. Then h∘g∘f is surjective (it covers the only element 1 of D}, but f and g aren't (they miss 2).

However, we can show that h must be surjective. Let x be any element of D. Then there is some y in A such that h∘g∘f(y) = x. Rewrite this as h(g∘f(y)) = x to show that there exists a value z = g∘f(y) such that h(z) = x.

CS202/Assignments/HW02/Solutions (last edited 2010-10-03 21:11:04 by JamesAspnes)