Arithmetic, foundations of
Arithmetic, foundations of
Arithmetic (i.e., the mathematical theory of the non-negative integers, 0, 1, 2, . . .) may be based on the five following postulates, which are due to Peano (and Dedekind, from whom Peano’s ideas were partly derived)
N(0)
N(x) ?x N(S(x)).
N(x) ?x [N(y) ?y [[S(x) = S(y)] ?x [x = y]]].
N(x) ?x ~[S(x) = 0].
F(0)[N(x)F(x) ?x F(S(x))] ?F [N(x) ?x F(x)]
The undefined terms are here 0, N, S, which may be interpreted as denoting, respectively, the non-negative integer 0, the propositional function to be a non-negative integer, and the function +1 (so that S(x) is x+l). The underlying logic may be taken to be the functional calculus of second order (Logic, formal, 6), with the addition of notations for descriptions and for functions from individuals to individuals, and the individual constant 0, together with appropriate modifications and additions to the primitive formulas and primitive rules of inference (the axiom of infinity is not needed because the Peano postulates take its place). By adding the five postulates of Peano as primitive formulas to this underlying logic, a logistic system is obtained which is adequate to extant elementary number theory (arithmetic) and to all methods of proof which have found actual employment in elementary number theory (and are normally considered to belong to elementary number theory). But of course, the system, if consistent, is incomplete in the sense of Gdel’s theorem (Logic, formal, 6).
If the Peano postulates are formulated on the basis of an interpretation according to which the domain of individuals coincides with that of the non-negative integers, the undefined term N may be dropped and the postulates reduced to the three following
(x)(y)[[S(x) = S(y)] ?[x = y]].
(x) ~[S(x) = 0].
F(0)[F(x) ?x F(S(x))] ?F (x)F(y).
It is possible further to drop the undefined term 0 and to replace the successor function S by a dyadic propositional function S (the contemplated interpretation being that S(x,y) is the proposition y = x+l). The Peano postulates may then be given the following form
(x)(Ey)S(x, y).
(x)[S(x,y) ?y [S(x,z) ?x [y = z]]].
(x)[S(y,x) ?y [S(z,x) ?x [y = z]]].
(Ex)[[(x) ~S(x,y)] =y [y = z]].
[(x) ~S(x,z)] ?x [F(z)[F(x) ?x [S(x, y) ?y F(y)]] ?F (x)F(x)].
For this form of the Peano postulates the underlying logic may be taken to be simply the functional calculus of second order without additions. In this formulation, numerical functions can be introduced only by contextual definition as incomplete symbols.
In the Frege-Russell derivation of arithmetic from logic (see the article Mathematics) necessity for the postulates of Peano is avoided. If based on the theory of types, however, this derivation requires some form of the axiom of infinity — which may be regarded as a residuum of the Peano postulates.
See further the articles Recursion, definition by, and Recursion, proof by. — A.C.
B. Russell, Introduction to Mathematical Philosophy, London, 1919.