Peano arithmetic
Peano arithmetic is a formal theory of the natural numbers, built from axioms for zero, successor, addition, multiplication, and induction.
First-order logic: A formal system with variables, predicates, quantifiers, and rules for deriving conclusions. Standard Peano arithmetic uses first-order quantifiers to state properties of natural numbers.
Primitive recursion: A method for defining functions by specifying an initial value and a rule for each successive input. Addition and multiplication are specified by recursive equations over natural numbers.
Presburger arithmetic: The first-order theory of natural numbers with addition but without multiplication. It is decidable, unlike full Peano arithmetic, because multiplication is omitted.
Gödel's incompleteness theorems: Results showing that sufficiently expressive, consistent formal theories cannot prove every truth expressible in their language. Peano arithmetic is subject to incompleteness because it can represent enough elementary computation.
Nonstandard model of arithmetic: A model of first-order arithmetic containing elements beyond the standard natural numbers. First-order Peano arithmetic has such models because its axioms do not uniquely characterize the standard numbers.
Successor function: The function that maps each natural number to the next one. Peano arithmetic builds its number sequence by repeatedly applying successor to zero.
Peano axioms: Axioms describing zero, successor, and induction for the natural numbers. These axioms provide the core principles from which Peano arithmetic derives its claims.
Second-order arithmetic: A formal theory using variables for sets or properties as well as individual numbers. Second-order induction can characterize the natural numbers categorically under standard semantics.
Undecidability of Peano arithmetic: The result that no algorithm decides, for every sentence, whether it is provable in Peano arithmetic. Arithmetic’s capacity to encode computation prevents a general decision procedure for its theorems.
Completeness theorem: Gödel's result that every sentence true in all models of a first-order theory is provable from that theory. It distinguishes provability in Peano arithmetic from truth in its standard model.