Recursive definitions
Peano had observed that addition of natural numbers can be defined recursively thus: x + 0 = x, x + Sy = S(x + y). Other numerical functions ℕk → ℕ that can be defined with the help of such a recursion scheme (and with the help of 0, S, and substitution) are called primitive recursive. Gödel used this concept to make precise what he meant by “effectively enumerable.” A set of natural numbers is said to be recursively enumerable if it consists of all f(n) with n ∊ ℕ, where f ∶ ℕ → ℕ is a primitive recursive function.
This notion can easily be extended to subsets of ℕk and, by a simple trick called arithmetization, to sets of strings of words in a language. Thus Gödel was able to assert that the set of theorems of mathematics is recursively enumerable, and, more recently, the American linguist Noam Chomsky (born 1928) could say that the set of grammatical sentences of a natural language, such as English, is recursively enumerable.
It is not difficult to show that all primitive recursive functions can be calculated. For example, to calculate x + y when x = 3 and y = 2, making use of Peano’s recursive definition of x + y and of the definitions 1 = S0, 2 = S1, and so on, one proceeds as follows:
3 + 2 = S2 + S1 = S(S2 + 1) = S(S2 + S0)
= SS(S2 + 0) = SSS2 = SS3 = S4 = 5.
But primitive recursive functions are not the only numerical functions that can be calculated. More general are the recursive functions, where f ∶ ℕ → ℕ is said to be recursive if its graph is recursively enumerable—that is, if there exist primitive recursive functions u, v ∶ ℕ → ℕ such that, for all natural numbers x and y, y = f(x) if and only if, for some z ∊ ℕ, x = u(z) and y = v(z).
All recursive functions can be calculated with pencil and paper or, even more primitively, by moving pebbles (calculi in Latin) from one location to another, using some finite set of instructions, nowadays called a program. Conversely, only recursive functions can be so calculated, or computed by a theoretical machine introduced by the English mathematician Alan Turing (1912–54), or by a modern computer, for that matter. The Church-Turing thesis asserts that the informal notion of calculability is completely captured by the formal notion of recursive functions and hence, in theory, replicable by a machine.
Gödel’s incompleteness theorem had proved that any useful formal mathematical system will contain undecidable propositions—propositions which can be neither proved nor disproved. Church and Turing, while seeking an algorithmic (mechanical) test for deciding theoremhood and thus potentially deleting nontheorems, proved independently, in 1936, that such an algorithmic method was impossible for the first-order predicate logic (see logic, history of: 20th-century logic). The Church-Turing theorem of undecidability, combined with the related result of the Polish-born American mathematician Alfred Tarski (1902–83) on undecidability of truth, eliminated the possibility of a purely mechanical device replacing mathematicians.
Computers and proof
While many mathematicians use computers only as word processors and for the purpose of communication, computer-assisted computations can be useful for discovering potential theorems. For example, the prime number theorem was first suggested as the result of extensive hand calculations on the prime numbers up to 3,000,000 by the Swiss mathematician Leonhard Euler (1707–83), a process that would have been greatly facilitated by the availability of a modern computer. Computers may also be helpful in completing proofs when there are a large number of cases to be considered. The renowned computer-aided proof of the four-colour mapping theorem by the American mathematicians Kenneth Appel (born 1932) and Wolfgang Haken (born 1928) even goes beyond this, as the computer helped to determine which cases were to be considered in the next step of the proof. Yet, in principle, computers cannot be asked to discover proofs, except in very restricted areas of mathematics—such as elementary Euclidean geometry—where the set of theorems happens to be recursive, as was proved by Tarski.
As the result of earlier investigations by Turing, Church, the American mathematician Haskell Brooks Curry (1900–82), and others, computer science has itself become a branch of mathematics. Thus, in theoretical computer science, the objects of study are not just theorems but also their proofs, as well as calculations, programs, and algorithms. Theoretical computer science turns out to have a close connection to category theory. Although this lies beyond the scope of this article, an indication will be given below.
Category theory
Abstraction in mathematics
One recent tendency in the development of mathematics has been the gradual process of abstraction. The Norwegian mathematician Niels Henrik Abel (1802–29) proved that equations of the fifth degree cannot, in general, be solved by radicals. The French mathematician Évariste Galois (1811–32), motivated in part by Abel’s work, introduced certain groups of permutations to determine the necessary conditions for a polynomial equation to be solvable. These concrete groups soon gave rise to abstract groups, which were described axiomatically. Then it was realized that to study groups it was necessary to look at the relation between different groups—in particular, at the homomorphisms which map one group into another while preserving the group operations. Thus people began to study what is now called the concrete category of groups, whose objects are groups and whose arrows are homomorphisms. It did not take long for concrete categories to be replaced by abstract categories, again described axiomatically.
The important notion of a category was introduced by Samuel Eilenberg and Saunders Mac Lane at the end of World War II. These modern categories must be distinguished from Aristotle’s categories, which are better called types in the present context. A category has not only objects but also arrows (referred to also as morphisms, transformations, or mappings) between them.
Many categories have as objects sets endowed with some structure and arrows, which preserve this structure. Thus, there exist the categories of sets (with empty structure) and mappings, of groups and group-homomorphisms, of rings and ring-homomorphisms, of vector spaces and linear transformations, of topological spaces and continuous mappings, and so on. There even exists, at a still more abstract level, the category of (small) categories and functors, as the morphisms between categories are called, which preserve relationships among the objects and arrows.
Not all categories can be viewed in this concrete way. For example, the formulas of a deductive system may be seen as objects of a category whose arrows f : A → B are deductions of B from A. In fact, this point of view is important in theoretical computer science, where formulas are thought of as types and deductions as operations.
More formally, a category consists of (1) a collection of objects A, B, C, . . ., (2) for each ordered pair of objects in the collection an associated collection of transformations including the identity IA ∶ A → A, and (3) an associated law of composition for each ordered triple of objects in the category such that for f ∶ A → B and g ∶ B → C the composition gf (or g ○ f) is a transformation from A to C—i.e., gf ∶ A → C. Additionally, the associative law and the identities are required to hold (where the compositions are defined)—i.e., h(gf) = (hg)f and 1Bf = f = f1A.
In a sense, the objects of an abstract category have no windows, like the monads of Leibniz. To infer the interior of an object A one need only look at all the arrows from other objects to A. For example, in the category of sets, elements of a set A may be represented by arrows from a typical one-element set into A. Similarly, in the category of small categories, if 1 is the category with one object and no nonidentity arrows, the objects of a category A may be identified with the functors 1 → A. Moreover, if 2 is the category with two objects and one nonidentity arrow, the arrows of A may be identified with the functors 2 → A.
Isomorphic structures
An arrow f ∶ A → B is called an isomorphism if there is an arrow g ∶ B → A inverse to f—that is, such that g ○ f = 1A and f ○ g = 1B. This is written A ≅ B, and A and B are called isomorphic, meaning that they have essentially the same structure and that there is no need to distinguish between them. Inasmuch as mathematical entities are objects of categories, they are given only up to isomorphism. Their traditional set-theoretical constructions, aside from serving a useful purpose in showing consistency, are really irrelevant.
For example, in the usual construction of the ring of integers, an integer is defined as an equivalence class of pairs (m,n) of natural numbers, where (m,n) is equivalent to (m′,n′) if and only if m + n′ = m′ + n. The idea is that the equivalence class of (m,n) is to be viewed as m − n. What is important to a categorist, however, is that the ring ℤ of integers is an initial object in the category of rings and homomorphisms—that is, that for every ring ℝ there is a unique homomorphism ℤ → ℝ. Seen in this way, ℤ is given only up to isomorphism. In the same spirit, it should be said not that ℤ is contained in the field ℚ of rational numbers but only that the homomorphism ℤ → ℚ is one-to-one. Likewise, it makes no sense to speak of the set-theoretical intersection of π and Square root of√-1, if both are expressed as sets of sets of sets (ad infinitum).
Of special interest in foundations and elsewhere are adjoint functors (F,G). These are pairs of functors between two categories 𝒜 and ℬ, which go in opposite directions such that a one-to-one correspondence exists between the set of arrows F(A) → B in ℬ and the set of arrows A → G(B) in 𝒜—that is, such that the sets are isomorphic.
Topos theory
The original purpose of category theory had been to make precise certain technical notions of algebra and topology and to present crucial results of divergent mathematical fields in an elegant and uniform way, but it soon became clear that categories had an important role to play in the foundations of mathematics. This observation was largely the contribution of the American mathematician F.W. Lawvere (born 1937), who elaborated on the seminal work of the German-born French mathematician Alexandre Grothendieck (born 1928) in algebraic geometry. At one time he considered using the category of (small) categories (and functors) itself for the foundations of mathematics. Though he did not abandon this idea, later he proposed a generalization of the category of sets (and mappings) instead.
Among the properties of the category of sets, Lawvere singled out certain crucial ones, only two of which are mentioned here:
- There is a one-to-one correspondence between subsets B of A and their characteristic functions χ ∶ A → {true, false}, where, for each element a of A, χ(a) = true if and only if a is in B.
- Given an element a of A and a function h ∶ A → A, there is a unique function f ∶ ℕ → A such that f(n) = hn(a).
Suitably axiomatized, a category with these properties is called an (elementary) topos. However, in general, the two-element set {true, false} must be replaced by an object Ω with more than two truth-values, though a distinguished arrow into Ω is still labeled as true.
