foundations of mathematics Foundational logic

The prominence of logic in foundations led some people, referred to as logicists, to suggest that mathematics is a branch of logic. The concepts of membership and equality could reasonably be incorporated into logic, but what about the natural numbers? Kronecker had suggested that, while everything else was made by man, the natural numbers were given by God. The logicists, however, believed that the natural numbers were also man-made, inasmuch as definitions may be said to be of human origin.

Russell proposed that the number 2 be defined as the set of all two-element sets, that is, X ∊ 2 if and only if X has distinct elements x and y and every element of X is either x or y. The Hungarian-born American mathematician John von Neumann (1903–57) suggested an even simpler definition, namely that X ∊ 2 if and only if X = 0 or X = 1, where 0 is the empty set and 1 is the set consisting of 0 alone. Both definitions require an extralogical axiom to make them work—the axiom of infinity, which postulates the existence of an infinite set. Since the simplest infinite set is the set of natural numbers, one cannot really say that arithmetic has been reduced to logic. Most mathematicians follow Peano, who preferred to introduce the natural numbers directly by postulating the crucial properties of 0 and the successor operation S, among which one finds the principle of mathematical induction.

The logicist program might conceivably be saved by a 20th-century construction usually ascribed to Church, though he had been anticipated by the Austrian philosopher Ludwig Wittgenstein (1889–1951). According to Church, the number 2 is the process of iteration; that is, 2 is the function which to every function f assigns its iterate 2(f) = f ○ f, where (f ○ f)(x) = f(f(x)). There are some type-theoretical difficulties with this construction, but these can be overcome if quantification over types is allowed; this is finding favour in theoretical computer science.