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.

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