formula with a single free variable x. Then the following formula is an axiom: (P(0) ∧ ∀x(P(x)→P(Sx))) → ∀y P(y). The last axiom (induction) can be replaced by the axioms For each integer n>0, the axiom ∀x SSS...Sx ≠ x (with n copies of S) ∀x ¬ x = 0 → ∃y Sy = x The theory of the natural numbers with a successor function is complete and decidable, and is κ-categorical for uncountable κ but not for countable κ. Presburger arithmetic is the theory of the natural numbers under addition, with signature consisting of a constant 0, a unary function S, and a binary function +. It is complete and decidable. The axioms are ∀x ¬ Sx = 0 ∀x∀y Sx = Sy → x = y ∀x x + 0 = x ∀x∀y x + Sy = S(x + y) Let P(x) be a first-order formula with a single free variable x. Then the following formula is an axiom: (P(0) ∧ ∀x(P(x)→P(Sx))) → ∀y P(y). Arithmetic Many of the first order theories described above can be extended to complete recursively enumerable consistent theories. This is no longer true for most of the following theories; they can usually encode both multiplication and addition of natural numbers, and this gives them enough power to encode themselves, which implies that Gödel's incompleteness theorem applies and the theories can no longer be both complete and recursively enumerable (unless they are inconsistent). The signature of a theory of arithmetic has: The constant 0; The unary function, the successor function, here denoted by prefix S, or by prefix σ or postfix ′ elsewhere; Two binary functions, denoted by infix + and ×, called "addition" and "multiplication." Some authors take the signature to contain a constant 1 instead of the function S, then define S in the obvious way as St = 1 + t. Robinson arithmetic (also called Q). Axioms (1) and (2) govern the distinguished element 0. (3) assures that S is an injection. Axioms (4) and (5) are the standard recursive definition of addition; (6) and (7) do the same for multiplication. Robinson arithmetic can be thought of as Peano arithmetic without induction. Q is a weak theory for which Gödel's incompleteness theorem holds. Axioms: ∀x ¬ Sx = 0 ∀x ¬ x = 0 → ∃y Sy = x ∀x∀y Sx = Sy → x = y ∀x x + 0