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

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}$

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.