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