Peano Arithmetic

Peano Arithmetic (PA) is the standard first-order axiomatization of the natural numbers, formulated by Giuseppe Peano in 1889 and refined by formal logicians in the twentieth century. Its axioms specify zero, a successor function, and the principle of mathematical induction applied to first-order formulas. Peano Arithmetic is strong enough to formalize all of elementary number theory, including the prime number theorem and Dirichlet's theorem on primes in arithmetic progressions.

PA occupies a central position in the foundations of mathematics because it is the system against which logical strength is typically calibrated: a system is often called "stronger than PA" or "weaker than PA" to locate it in the hierarchy of proof-theoretic strength. Gödel's incompleteness theorems, in their most precise form, apply to any consistent extension of PA: any such system contains true arithmetic statements it cannot prove, and cannot prove its own consistency.

The Gödel Incompleteness and PA

The first incompleteness theorem as applied to PA constructs a specific sentence G_PA — a sentence of arithmetic that asserts, in coded form, its own unprovability in PA. G_PA is true (since if it were false, PA would be inconsistent) but unprovable within PA. Adding G_PA as a new axiom yields PA + G_PA, which has its own Gödel sentence, and so on — a transfinite sequence of stronger systems studied in ordinal analysis.

The proof-theoretic ordinal of PA is ε₀ (epsilon-naught), established by Gerhard Gentzen in 1936. This ordinal measures, in a precise sense, the inferential resources PA contains: Gentzen proved that PA is consistent using exactly ε₀-induction — neither more nor less. Any system provably consistent within PA has proof-theoretic ordinal strictly below ε₀; any system requiring ε₀-induction for its consistency proof has the same proof-theoretic strength as PA.

Non-Standard Models

By the compactness theorem of first-order logic, PA has non-standard models — models containing elements that are not the standard natural numbers, including infinite "natural numbers" and arithmetic pathologies. The existence of non-standard models is a consequence of the first-order nature of PA: induction in PA applies to first-order formulas only, and the second-order statement that every set containing zero and closed under succession is all of ℕ — which would rule out non-standard models — is not expressible in first-order PA.

Non-standard models are not curiosities but tools: they witness the independence of certain arithmetic statements from PA, and they have been used to prove combinatorial independence results that connect proof theory to Ramsey theory in unexpected ways.

That a system as intuitive as Peano Arithmetic cannot prove the consistency of Peano Arithmetic is not a defect in the formalism — it is a discovery about the nature of mathematical knowledge. The demand that foundations be self-certifying was always confused. PA cannot prove its own consistency for the same reason that an instrument cannot calibrate itself: measurement requires a fixed point external to what is being measured.