- Related Topics:
- logic
With the exception of its first-order fragment, the intricate theory of Principia Mathematica was too complicated for mathematicians to use as a tool of reasoning in their work. Instead, they came to rely nearly exclusively on set theory in its axiomatized form. In this use, set theory serves not only as a theory of infinite sets and of kinds of infinity but also as a universal language in which mathematical theories can be formulated and discussed. Because it covered much of the same ground as higher-order logic, however, set theory was beset by the same paradoxes that had plagued higher-order logic in its early forms. In order to remove these problems, the German mathematician Ernest Zermelo undertook to provide an axiomatization of set theory under the influence of the axiomatic approach of Hilbert.
Zermelo-Fraenkel set theory (ZF)
Contradictions like Russell’s paradox arose from what was later called the unrestricted comprehension principle: the assumption that, for any property p, there is a set that contains all and only those sets that have p. In Zermelo’s system, the comprehension principle is eliminated in favour of several much more restrictive axioms:
- Axiom of extensionality. If two sets have the same members, then they are identical.
- Axiom of elementary sets. There exists a set with no members: the null, or empty, set. For any two objects a and b, there exists a set (unit set) having as its only member a, as well as a set having as its only members a and b.
- Axiom of separation. For any well-formed property p and any set S, there is a set, S1, containing all and only the members of S that have this property. That is, already existing sets can be partitioned or separated into parts by well-formed properties.
- Power-set axiom. If S is a set, then there exists a set, S1, that contains all and only the subsets of S.
- Union axiom. If S is a set (of sets), then there is a set containing all and only the members of the sets contained in S.
- Axiom of choice. If S is a nonempty set containing sets no two of which have common members, then there exists a set that contains exactly one member from each member of S.
- Axiom of infinity. There exists at least one set that contains an infinite number of members.
With the exception of (2), all these axioms allow new sets to be constructed from already-constructed sets by carefully constrained operations; the method embodies what has come to be known as the “iterative” conception of a set. The list of axioms was eventually modified by Zermelo and by the Israeli mathematician Abraham Fraenkel, and the result is usually known as Zermelo-Fraenkel set theory, or ZF, which is now almost universally accepted as the standard form of set theory. (See Set theory: Axiomatic set theory.)
The American mathematician John von Neumann and others modified ZF by adding a “foundation axiom,” which explicitly prohibited sets that contain themselves as members. In the 1920s and ’30s, von Neumann, the Swiss mathematician Paul Isaak Bernays, and the Austrian-born logician Kurt Gödel (1906–78) provided additional technical modifications, resulting in what is now known as von Neumann-Bernays-Gödel set theory, or NBG. ZF was soon shown to be capable of deriving the Peano Postulates by several alternative methods—e.g., by identifying the natural numbers with certain sets, such as 0 with the empty set (Ø), 1 with the singleton empty set—the set containing only the empty set—({Ø}), and so on.
Since Zermelo was working within the axiomatic tradition of Hilbert, he and his followers were interested in the kinds of questions that concern any axiomatic theory, such as: Is ZF consistent? Can its consistency be proved? Are the axioms independent of each other? What other axioms should be added? Other logicians later asked questions about the intended models of axiomatic set theory—i.e., about what object-domains and rules of symbol interpretation would render the theorems of set theory true. Some of these questions were subsequently answered as a result of other developments in logic; for example, since elementary arithmetic can be reconstructed within axiomatic set theory, from Gödel’s proof of the incompleteness of elementary arithmetic (see below Logical semantics and model theory), it follows that axiomatic set theory is also inevitably incomplete.
The continuum problem and the axiom of constructibility
Another way in which Hilbert influenced research in set theory was by placing a set-theoretical problem at the head of his famous list of important unsolved problems in mathematics (1900). The problem is to prove or to disprove the famous conjecture known as the continuum hypothesis, which concerns the structure of infinite cardinal numbers. The smallest such number has the cardinality ℵo (aleph-null), which is the cardinality of the set of natural numbers. The cardinality of the set of all sets of natural numbers, called ℵ1 (aleph-one), is equal to the cardinality of the set of all real numbers. The continuum hypothesis states that ℵ1 is the second infinite cardinal—in other words, there does not exist any cardinality strictly between ℵo and ℵ1. Despite its prominence, the problem of the continuum hypothesis remains unsolved.
In axiomatic set theory, the continuum problem is equivalent to the question of whether the continuum hypothesis or its negation can be proved in ZF. In work carried out from 1938 to 1940, Gödel showed that the negation of the continuum hypothesis cannot be proved in ZF (that is, the hypothesis is consistent with the axioms of ZF), and in 1963 the American mathematician Paul Cohen showed that the continuum hypothesis itself cannot be proved in ZF.
The methods by which these results were obtained are interesting in their own right. Gödel showed how to construct a model of ZF in which the continuum hypothesis is true. This model is known as the “constructive universe,” and the axiom that restricts models of ZF to the constructive universe is known as the axiom of constructibility. The construction of the model proceeds stepwise, the steps being correlated with the finite and infinite ordinal numbers. At each stage, all the sets that can be defined in the universe so far reached are added. At a stage correlated with a limit ordinal (an ordinal number with no immediate predecessor), the construction amounts to taking the sum of all the previously reached sets. What is characteristic of this process is not so much that it is constructive as that it is impredicative. It can be considered an extension of Russell and Whitehead’s ramified hierarchy to sets corresponding to transfinite (larger than infinite) ordinal numbers.
The axiom of constructibility is a possible addition to the axioms of ZF. Most logicians, however, have chosen not to adopt it, because it imposes too great a restriction on the range of sets that can be studied. Nevertheless, its consequences have been the object of intensive investigation.
The axiom of choice
Among the axioms of ZF, perhaps the most attention has been devoted to (6), the axiom of choice, which has a large number of equivalent formulations. It was first introduced by Zermelo, who used it to prove that every set can be well-ordered (i.e., such that each of its nonempty subsets has a least member); it was later discovered, however, that the well-ordering theorem and the axiom of choice are equivalent. Once the axiom was formulated, it became clear that it had been widely used in mathematical reasoning, even by some mathematicians who rejected the explicit version of the axiom in set theory. Gödel proved the consistency of the axiom with the other axioms of ZF in the course of his proof of the consistency of the continuum hypothesis with ZF; the axiom’s independence of ZF (the fact that it cannot be proved in ZF) was likewise proved by Cohen in the course of his proof of the independence of the continuum hypothesis.
Problems and new directions
Axiomatic set theory is widely, though not universally, regarded as the foundation of mathematics, at least in the sense of providing a medium in which all mathematical theories can be formulated and an inventory of assumptions that are made in mathematical reasoning. However, axiomatic set theory in a form like ZF is not without its own peculiarities and problems. Although Zermelo himself was not clear about the distinction, ZF is a first-order theory despite the fact that sets are higher-order entities. The logical rules used in ZF are the usual rules of first-order logic. Higher-order logical principles are introduced not as rules of inference but as axioms concerning the universe of discourse. The axiom of choice, for example, is arguably a valid principle of higher-order logic. If so, it is unnatural to separate it from the logic used in set theory and to treat it as independent of the other assumptions.
Because of the set-theoretic paradoxes, the standard (extensional) interpretation of set theory cannot be fully implemented by any means. However, it can be seen what direction possible new axioms would have to take in order to get closer to something like a standard interpretation. The standard interpretation requires that there exist more sets than are needed on a nonstandard interpretation; accordingly, set theorists have considered stronger existence assumptions than those implied by the ZF axioms. Typically, these assumptions postulate larger sets than are required by the ZF axiomatization. Some sets of such large cardinalities are called “inaccessible” and others “nonmeasurable.”
Meanwhile, pending the formulation of such large-cardinal axioms, many logicians have proposed as the intended model of set theory what is known as the “cumulative hierarchy.” It is built up in the same way as the constructive hierarchy, except that, at each stage, all of the subsets of the set that has already been reached are added to the model.
Assumptions postulating the existence of large sets are not the only candidates for new axioms, however. Perhaps the most interesting proposal was made by two Polish mathematicians, Hugo Steinhaus and Jan Mycielski, in 1962. Their “axiom of determinateness” can be formulated in terms of an infinite two-person game in which the players alternately choose zeros and ones. The outcome is the representation of a binary real number between zero and one. If the number lies in a prescribed set S of real numbers, the first player wins; if not, the second player wins. The axiom states that the game is determinate—that is, one of the players has a winning strategy. Weaker forms of the axiom are obtained by imposing restrictions on S.
The axiom of determinateness is very strong. It implies the axiom of choice for countable sets of sets but is incompatible with the unrestricted axiom of choice. It has been shown that it holds for some sets of sets S, but it remains unknown whether its unrestricted form is even consistent.
Theory of logic (metalogic)
Contrary to a widespread misconception, mathematical theories do not consist entirely of axioms and the various theorems derived from them. Much of the actual work of constructing such a theory falls under what some philosophers call “metatheory.” A mathematician tries to obtain an overview of the entire theory—e.g., by classifying different models of the axioms or by demonstrating their common structure. Likewise, beginning about 1930 most of the work done in logic consisted of metalogic. The form taken by this enterprise depended on the logician’s assumptions about what metalogic could accomplish. In this respect, there have been sharp differences of opinion.
Understanding this difference requires distinguishing between two conceptions of logic, which, following the French-American mathematician and historian of logic Jean van Heijenoort (1912–86), may be called logic as calculus and logic as language. According to the latter conception, a logical system like Frege’s Begriffsschrift (1879; “Conceptual Notation”) or the notation of the Principia Mathematica provides a universal medium of communication, what Gottfried Wilhelm Leibniz called a lingua universalis. If so, however, then the semantics of this logic—the specification of what the individual terms of the logical system refer to—cannot be discussed in terms of the logic itself; the result would be either triviality or nonsense. Thus, one consequence of this view is a thesis of the inexpressibility of logical semantics: only the purely formal or syntactic features of the logic can be discussed. In contrast, according to the conception of logic as a calculus, logic is primarily a tool for drawing inferences, what Leibniz called a calculus ratiocinator. Such a calculus can be discussed, theorized about, and changed altogether, if need be.
The contrast between the two conceptions is reflected in the difference between two research traditions in 19th-century logic. The algebraic tradition starting with George Boole represented, by and large, the view of logic as a calculus, whereas thinkers such as Frege treated logic as an important component of language. One example of these differences is that while Frege and Russell conceived of logical truths as the most general truths about the world, the logic of algebraically oriented logicians dealt with all possible universes of discourse, though one of them might be selected for attention in some particular application.
Several major logicians of the late19th and 20th centuries subscribed to the view of logic as language, including, in addition to Frege and Russell, the early Wittgenstein, W.V.O. Quine, and Alonzo Church. Because of the strength of the traditional view of logic as a lingua universalis, systematic studies of the semantic aspects of logic developed rather slowly.
