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

Later

### 2.2Examples¶

• Assignment 8, question 2

## 3Invalid theorems in Peano arithmetic¶

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

Later

### 3.2Examples¶

• Assignment 8, question 2 (the last part)

## 4Expanded Peano arithmetic¶

Given an expanded Peano arithmetic, prove something.

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