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

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