HTSEFP: Peano arithmetic

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)

1.2Examples¶

• 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¶

Later

2.2Examples¶

• Assignment 8, question 2

3Invalid theorems in Peano arithmetic¶

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

3.1General solution¶

Later

3.2Examples¶

• Assignment 8, question 2 (the last part)

4Expanded Peano arithmetic¶

Given an expanded Peano arithmetic, prove something.

4.1General solution¶

Later

4.2Examples¶

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

5.2Examples¶

• Assignment 9, question 1