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 = x
- ∀x∀y x + Sy = S(x + y)
- ∀x x × 0 = 0
- ∀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Σ0 is often denoted by IΔ0. 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Σ0 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.
Read more about this topic: List Of First-order Theories
Famous quotes containing the word arithmetic:
“I hope I may claim in the present work to have made it probable that the laws of arithmetic are analytic judgments and consequently a priori. Arithmetic thus becomes simply a development of logic, and every proposition of arithmetic a law of logic, albeit a derivative one. To apply arithmetic in the physical sciences is to bring logic to bear on observed facts; calculation becomes deduction.”
—Gottlob Frege (1848–1925)
“‘Tis no extravagant arithmetic to say, that for every ten jokes,—thou hast got an hundred enemies; and till thou hast gone on, and raised a swarm of wasps about thine ears, and art half stung to death by them, thou wilt never be convinced it is so.”
—Laurence Sterne (1713–1768)
“Your discovery of the contradiction caused me the greatest surprise and, I would almost say, consternation, since it has shaken the basis on which I intended to build my arithmetic.... It is all the more serious since, with the loss of my rule V, not only the foundations of my arithmetic, but also the sole possible foundations of arithmetic seem to vanish.”
—Gottlob Frege (1848–1925)