Peano Arithmetic

Mathematical Logic · Axiom Academy

The formal foundation of natural number arithmetic and the proving ground for Gödel's incompleteness theorems Before we can state axioms, we need to define the language of Peano Arithmetic. This language provides the basic symbols we use to express arithmetic statements. Function symbols: S (successor), + (addition), × (multiplication) Logical symbols: ∧, ∨, ¬, →, ↔, ∀, ∃ Variables: x, y, z, ... (ranging over natural numbers) The successor function S is fundamental: S(n) represents the "next" number after n. For instance, S(0) represents 1, S(S(0)) represents 2, and so on. Peano Arithmetic consists of axioms in two groups: the basic axioms that characterize the natural numbers, and the induction schema that captures mathematical induction. PA1: ∀x (S(x) ≠ 0) — Zero is not the successor of any number PA2: ∀x ∀y (S(x) = S(y) → x = y) — Successor is injective PA3: ∀x (x + 0 = x) — Addition base case PA4: ∀x ∀y (x + S(y) = S(x + y)) — Addition recursive case PA5: ∀x (x × 0 = 0) — Multiplication base case PA6: ∀x ∀y (x × S(y) = (x × y) + x) — Multiplication recursive case 3. What PA Can Express and Prove Peano Arithmetic is remarkably expressive. It can represent virtually all ordinary arithmetic statements about natural numbers. "x is prime": x > 1 ∧ ∀y∀z(x = y × z → (y = 1 ∨ z = 1)) Goldbach's conjecture: ∀x(x > 2 ∧ even(x) → ∃p∃q(prime(p) ∧ prime(q) ∧ x = p + q)) PA can prove many fundamental arithmetic facts: Commutativity and associativity of addition and multiplication

This is the written version of the interactive lesson above. See the full Mathematical Logic course.