HTSEFP: Peano arithmetic CC-BY-NC

Maintainer: admin

1Proving a theorem in Peano arithmetic

Given some theorem $\sigma$, prove that PA $\vdash \sigma$.

1.1General solution

Use the 7 axioms (and possibly others):

A1 - $x + 0 = x$
A2 - $x + Sy = S(x + y)$
M1 - $x \cdot 0 = 0$
M2 - $x \cdot Sy = x \cdot y + x$
L - $x < y \to \exists z(z \neq 0 \land x + z = y)$
S1 - $\forall x(Sx \neq 0)$ (0 is the successor to nothing)
S2 - $Sx = Sy \to x = y$ (the successor function is injective)


  • Assignment 8, question 1
  • Assignment 9, question 2
  • Fall 2009 final exam, question 6
  • Fall 2010 final exam, question 6

2Model satisfaction and Peano arithmetic

Given a model $\mathcal{M}$, show that $\mathcal{M} \models \sigma$ for some axiom $\sigma$ in Peano arithmetic.

2.1General solution



  • Assignment 8, question 2

3Invalid theorems in Peano arithmetic

Show that some statement should not be a theorem of Peano arithmetic.

3.1General solution



  • Assignment 8, question 2 (the last part)

4Expanded Peano arithmetic

Given an expanded Peano arithmetic, prove something.

4.1General solution



  • Assignment 8, question 3

5Euclidean algorithm

Find the GCD of two numbers using the Euclidean algorithm and by factoring the numbers into primes.

5.1General solution

Using the Euclidean algorithm is actually very simple - basically just repeated subtraction. See the example in the assignment for the procedure. Factoring a number into primes is also simple.


  • Assignment 9, question 1