**Maintainer:**admin

*1*Proving a theorem in Peano arithmetic¶

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

*1.1*General 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)

*1.2*Examples¶

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

*2*Model satisfaction and Peano arithmetic¶

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

*2.1*General solution¶

Later

*2.2*Examples¶

- Assignment 8, question 2

*3*Invalid theorems in Peano arithmetic¶

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

*3.1*General solution¶

Later

*3.2*Examples¶

- Assignment 8, question 2 (the last part)

*4*Expanded Peano arithmetic¶

Given an expanded Peano arithmetic, prove something.

*4.1*General solution¶

Later

*4.2*Examples¶

- Assignment 8, question 3

*5*Euclidean algorithm¶

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

*5.1*General 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.

*5.2*Examples¶

- Assignment 9, question 1