Peano arithmetic

Peano arithmetic is the first-order theory of the natural numbers with zero, successor, addition, multiplication, order, and the induction scheme.

This subsystem of second-order arithmetic allows comprehension for arithmetical formulas and induction in its standard restricted presentation. Its first-order arithmetical consequences are those of Peano arithmetic. It is a useful base for comparing well-quasi-ordering principles with ordinal notation systems without assuming their global well-foundedness.

Primitive recursive arithmetic formalizes primitive recursive functions, their defining equations, and quantifier-free induction. It is a weak arithmetic base for coding finite syntax and checking effective proof reductions. Assertions that a combinatorial principle implies formal consistency statement must specify such a base or another arithmetic metatheory.

Gentzen's consistency argument associates finite arithmetic derivations with effective ordinal notations below epsilon zero. An alleged contradiction admits an effective proof reduction preserving the contradictory end-sequent and strictly decreasing the assigned ordinal. Termination would therefore produce a normal contradiction, excluded by inspection of the logical rules and true atomic axioms. This explains why the relevant transfinite induction principle implies formal consistency statement. For a finite slow-well-ordering formulation one additionally needs the controlled-termination miniaturization theorem, rather than assuming that ordinary proof reductions have linearly growing size. The reduction program is discussed in math.stanford.edu/~feferman/papers/reductive.pdf .

An internally finite subset of $\{0,\dots ,c-1\}$ can be represented in Peano arithmetic by a product of distinct prime numbers: multiply the $e$th prime number exactly when $e$ belongs to the subset. Divisibility by that prime recovers membership. Arithmetic induction proves existence of this code even for a definable subset with a nonstandard cutoff in a nonstandard model of Peano arithmetic.

The theory of true arithmetic consists of all first-order arithmetic sentences true in the standard natural-number structure. It is complete but not computably enumerable.

Every nonempty definable set of natural numbers has a least element. Over the usual arithmetic language, this principle is equivalent to the induction scheme.

The well-ordering principle quantifies over all nonempty subsets of the natural numbers; in first-order arithmetic this entry is its definable-set schema.

A nonstandard model of Peano arithmetic is a model not isomorphic to the standard natural-number structure. It contains the standard numerals as an initial segment and also contains elements larger than every standard numeral.

In a model of Peano arithmetic, an element realizes this partial type exactly when it is not a standard numeral. A model omitting it is isomorphic to the standard natural-number structure. For a complete consistent extension $T$ of arithmetic, the type is nonprincipal exactly when $T$ is the theory of true arithmetic: apply the omitting types theorem in one direction and use an actual standard witness to refute any proposed isolating formula in the other. For incomplete theories, a principal partial type can still be omitted by some models.

The standard cut is the external initial segment consisting of the interpretations of the standard numerals. It is not definable, even with parameters, inside the nonstandard model.

If a definable property in a nonstandard model of Peano arithmetic holds of every standard natural number, then it holds of some nonstandard element. Equivalently, a definable set containing the entire standard cut of a nonstandard model of arithmetic must overspill beyond it.

This is the arithmetic case of overspill, which also applies to internal subsets of nonstandard extensions in analysis.