A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Peano Arithmetic (PA) is a first-order theory with axioms for zero, successor, addition, and multiplication, plus an induction schema. PA is powerful enough to express and prove a vast range of arithmetic truths. A key concept is representability: a function f is representable in PA if there is a formula φ(x, y) such that PA proves φ(n, f(n)) for each numeral n and PA proves ∀y(φ(n, y) → y = f(n)). Gödel showed that all primitive recursive functions are representable in PA, which is the technical foundation for encoding proofs as numbers (Gödel numbering).
Write out the Peano axioms explicitly and verify small arithmetic facts from them. Trace Gödel numbering on a simple formula to see how syntax becomes arithmetic. The induction schema is an axiom scheme, not a single axiom.
Peano Arithmetic (PA) is the standard first-order formalization of the natural numbers. Its non-logical axioms assert that 0 is a number, that the successor function S is injective and never returns 0, and that addition and multiplication satisfy their standard recursive definitions. These constraints look simple, but together with the induction schema they generate an enormous body of mathematics. Most theorems of elementary number theory — divisibility, primality, the Chinese Remainder Theorem — are provable in PA.
The induction axiom schema is often misunderstood as a single axiom. It is not. It is a template generating infinitely many axioms, one for each formula φ in the language. For any formula φ(n), PA contains: "if φ holds at 0 and φ holding at n implies φ holds at n+1, then φ holds for all n." Because there are infinitely many formulas in first-order logic, there are infinitely many induction axioms. This is why PA cannot be finitely axiomatized — a deep result connected to Gödel's theorem itself.
The concept of *representability* is the technical bridge between arithmetic and metamathematics. A function f is representable in PA if there is a formula φ(x, y) such that PA proves φ(n, f(n)) for each concrete numeral n, and PA also proves that f(n) is the *unique* value satisfying φ(n, y). This two-part condition — existence and uniqueness — ensures that φ captures exactly the graph of f. Gödel's key lemma is that all primitive recursive functions (addition, multiplication, exponentiation, the coding functions used in Gödel numbering) are representable in PA.
Why does representability matter? Gödel's incompleteness proof requires PA to reason about its own syntax — about which formulas are provable. To enable this, Gödel invented a coding scheme: each symbol, formula, and finite sequence of formulas (i.e., proof) is assigned a unique natural number, its *Gödel number*. Syntactic operations on proofs then become arithmetic functions on these numbers. Since those functions are primitive recursive, they are representable in PA. This means PA can literally express statements like "the number g codes a valid proof of the formula coded by n" as an arithmetic formula — the foundation on which the incompleteness theorems are built.