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

## 2.1. Solution

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.

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.