Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. A mysterious predicate

Suppose we start with the standard Peano axioms

PA1: ∀x Sx ≠ 0.
PA2: ∀x ∀y Sx = Sy ⇒ x = y.
PA3: (P0 ∧ ∀x Px ⇒ PSx) ⇒ ∀x Px. (For any predicate P.)

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

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

Prove each of the following statements:

∀x Q(x, Sx).
∀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

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

f is surjective.
g is surjective.
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.