List of First-order Theories - Arithmetic

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:

1. ∀x ¬ Sx = 0
2. ∀x ¬ x = 0 → ∃y Sy = x
3. ∀x∀y Sx = Sy → x = y
4. ∀x x + 0 = x
5. ∀x∀y x + Sy = S(x + y)
6. ∀x x × 0 = 0
7. ∀x∀y x × Sy = (x × y) + x.

IΣ_n is first order Peano arithmetic with induction restricted to Σ_n formulas (for n = 0, 1, 2, ...). The theory IΣ₀ is often denoted by IΔ₀. This is a series of more and more powerful fragments of Peano arithmetic. The case n = 1 has about the same strength as primitive recursive arithmetic (PRA). Exponential function arithmetic (EFA) is IΣ₀ with an axiom stating that xy exists for all x and y (with the usual properties).

First order Peano arithmetic, PA. The "standard" theory of arithmetic. The axioms are the axioms of Robinson arithmetic above, together with the axiom scheme of induction:

• for any formula φ in the language of PA. φ may contain free variables other than x.

Kurt Gödel's 1931 paper proved that PA is incomplete, and has no consistent recursively enumerable completions.

Complete arithmetic (also known as true arithmetic) is the theory of the standard model of arithmetic, the natural numbers N. It is complete but does not have a recursively enumerable set of axioms.