set theory

the branch of mathematics that deals with relations between sets.

[1940-45]

* * *

Branch of mathematics that deals with the properties of sets.

It is most valuable as applied to other areas of mathematics, which borrow from and adapt its terminology and concepts. These include the operations of union (∪), and intersection (∩). The union of two sets is a set containing all the elements of both sets, each listed once. The intersection is the set of all elements common to both original sets. Set theory is useful in analyzing difficult concepts in mathematics and logic. It was placed on a firm theoretical footing by Georg Cantor, who discovered the value of clearly formulated sets in the analysis of problems in symbolic logic and number theory.

* * *

▪ mathematics

Introduction

      branch of mathematics that deals with the properties of well-defined collections of objects, which may or may not be of a mathematical nature, such as numbers or functions. The theory is less valuable in direct application to ordinary experience than as a basis for precise and adaptable terminology for the definition of complex and sophisticated mathematical concepts.

      Between the years 1874 and 1897, the German mathematician and logician Georg Cantor (Cantor, Georg) created a theory of abstract sets of entities and made it into a mathematical discipline. This theory grew out of his investigations of some concrete problems regarding certain types of infinite sets of real numbers. A set, wrote Cantor, is a collection of definite, distinguishable objects of perception or thought conceived as a whole. The objects are called elements or members of the set.

      The theory had the revolutionary aspect of treating infinite sets as mathematical objects that are on an equal footing with those that can be constructed in a finite number of steps. Since antiquity, a majority of mathematicians had carefully avoided the introduction into their arguments of the actual infinite (i.e., of sets containing an infinity of objects conceived as existing simultaneously, at least in thought). Since this attitude persisted until almost the end of the 19th century, Cantor's work was the subject of much criticism to the effect that it dealt with fictions—indeed, that it encroached on the domain of philosophers and violated the principles of religion. Once applications to analysis began to be found, however, attitudes began to change, and by the 1890s Cantor's ideas and results were gaining acceptance. By 1900, set theory was recognized as a distinct branch of mathematics.

      At just that time, however, several contradictions in so-called naive set theory were discovered. In order to eliminate such problems, an axiomatic (axiomatic method) basis was developed for the theory of sets analogous to that developed for elementary geometry. The degree of success that has been achieved in this development, as well as the present stature of set theory, has been well expressed in the Nicolas Bourbaki (Bourbaki, Nicolas) Éléments de mathématique (begun 1939; “Elements of Mathematics”): “Nowadays it is known to be possible, logically speaking, to derive practically the whole of known mathematics from a single source, The Theory of Sets.”

Introduction to naive set theory

Fundamental set concepts

      In naive set theory, a set is a collection of objects (called members or elements) that is regarded as being a single object. To indicate that an object x is a member of a set A one writes x ∊ A, while x ∉ A indicates that x is not a member of A. A set may be defined by a membership rule (formula) or by listing its members within braces. For example, the set given by the rule “prime numbers less than 10” can also be given by {2, 3, 5, 7}. In principle, any finite set can be defined by an explicit list of its members, but specifying infinite sets requires a rule or pattern to indicate membership; for example, the ellipsis in {0, 1, 2, 3, 4, 5, 6, 7, …} indicates that the list of natural numbers ℕ goes on forever. The empty (or void, or null) set, symbolized by {} or Ø, contains no elements at all. Nonetheless, it has the status of being a set.

      A set A is called a subset of a set B (symbolized by A ⊆ B) if all the members of A are also members of B. For example, any set is a subset of itself, and Ø is a member of any set. If both A ⊆ B and B ⊆ A, then A and B have exactly the same members. Part of the set concept is that in this case A = B; that is, A and B are the same set.

Operations on sets

      The symbol ∪ is employed to denote the union of two sets. Thus, the set A ∪ B—read “A union B” or “the union of A and B”—is defined as the set that consists of all elements belonging to either set A or set B (or both). For example, suppose that Committee A, consisting of the 5 members Jones, Blanshard, Nelson, Smith, and Hixon, meets with Committee B, consisting of the 5 members Blanshard, Morton, Hixon, Young, and Peters. Clearly, the union of Committees A and B must then consist of 8 members rather than 10—namely, Jones, Blanshard, Nelson, Smith, Morton, Hixon, Young, and Peters.

      The intersection operation is denoted by the symbol ∩. The set A ∩ B—read “A intersection B” or “the intersection of A and B”—is defined as the set composed of all elements that belong to both A and B. Thus, the intersection of the two committees in the foregoing example is the set consisting of Blanshard and Hixon.

      If E denotes the set of all positive even numbers and O denotes the set of all positive odd numbers, then their union yields the entire set of positive integers, and their intersection is the empty set. Any two sets whose intersection is the empty set are said to be disjoint.

      When the admissible elements are restricted to some fixed class of objects U, U is called the universal set (or universe). Then for any subset A of U, the complement of A (symbolized by A′ or U − A) is defined as the set of all elements in the universe U that are not in A. For example, if the universe consists of the 26 letters of the alphabet, the complement of the set of vowels is the set of consonants.

      In analytic geometry, the points on a Cartesian grid are ordered pairs (x, y) of numbers. In general, (x, y) ≠ (y, x); ordered pairs are defined so that (a, b) = (c, d) if and only if both a = c and b = d. In contrast, the set {x, y} is identical to the set {y, x} because they have exactly the same members.

      The Cartesian product of two sets A and B, denoted by A × B, is defined as the set consisting of all ordered pairs (a, b) for which a ∊ A and b ∊ B. For example, if A = {x, y} and B = {3, 6, 9}, then A × B = {(x, 3), (x, 6), (x, 9), (y, 3), (y, 6), (y, 9)}.

Relations in set theory

      In mathematics, a relation is an association between, or property of, various objects. Relations can be represented by sets of ordered pairs (a, b) where a bears a relation to b. Sets of ordered pairs are commonly used to represent relations depicted on charts and graphs, on which, for example, calendar years may be paired with automobile production figures, weeks with stock market averages, and days with average temperatures.

      A function f can be regarded as a relation between each object x in its domain and the value f(x). A function f is a relation with a special property, however: each x is related by f to one and only one y. That is, two ordered pairs (x, y) and (x, z) in f imply that y = z.

      A one-to-one correspondence between sets A and B is similarly a pairing of each object in A with one and only one object in B, with the dual property that each object in B has been thereby paired with one and only one object in A. For example, if A = {x, z, w} and B = {4, 3, 9}, a one-to-one correspondence can be obtained by pairing x with 4, z with 3, and w with 9. This pairing can be represented by the set {(x, 4), (z, 3), (w, 9)} of ordered pairs.

      Many relations display identifiable properties. For example, in the relation “is the same colour as,” each object bears the relation to itself as well as to some other objects. Such relations are said to be reflexive. The ordering relation “less than or equal to” (symbolized by ≤) is reflexive, but “less than” (symbolized by <) is not. The relation “is parallel to” (symbolized by ∥) has the property that, if an object bears the relation to a second object, then the second also bears that relation to the first. Relations with this property are said to be symmetric. (Note that the ordering relation is not symmetric.) These examples also have the property that whenever one object bears the relation to a second, which further bears the relation to a third, then the first bears that relation to the third—e.g., if a < b and b < c, then a < c. Such relations are said to be transitive.

      Relations that have all three of these properties—reflexivity, symmetry, and transitivity (transitive law)—are called equivalence relations. In an equivalence relation, all elements related to a particular element, say a, are also related to each other, and they form what is called the equivalence class of a. For example, the equivalence class of a line for the relation “is parallel to” consists of the set of all lines parallel to it.

Essential features of Cantorian set theory

      At best, the foregoing description presents only an intuitive concept of a set. Essential features of the concept as Cantor understood it include: (1) that a set is a grouping into a single entity of objects of any kind, and (2) that, given an object x and a set A, exactly one of the statements x ∊ A and x ∉ A is true and the other is false. The definite relation that may or may not exist between an object and a set is called the membership relation.

      A further intent of this description is conveyed by what is called the principle of extension—a set is determined by its members rather than by any particular way of describing the set. Thus, sets A and B are equal if and only if every element in A is also in B and every element in B is in A; symbolically, x ∊ A implies x ∊ B and vice versa. There exists, for example, exactly one set the members of which are 2, 3, 5, and 7. It does not matter whether its members are described as “prime numbers less than 10” or listed in some order (which order is immaterial) between small braces, possibly {5, 2, 7, 3}.

      The positive integers {1, 2, 3, …} are typically used for counting the elements in a finite set. For example, the set {a, b, c} can be put in one-to-one correspondence with the elements of the set {1, 2, 3}. The number 3 is called the cardinal number, or cardinality, of the set {1, 2, 3} as well as any set that can be put into a one-to-one correspondence with it. (Because the empty set has no elements, its cardinality is defined as 0.) In general, a set A is finite and its cardinality is n if there exists a pairing of its elements with the set {1, 2, 3, … , n}. A set for which there is no such correspondence is said to be infinite.

      To define infinite sets, Cantor used predicate formulas. The phrase “x is a professor” is an example of a formula; if the symbol x in this phrase is replaced by the name of a person, there results a declarative sentence that is true or false. The notation S(x) will be used to represent such a formula. The phrase “x is a professor at university y and x is a male” is a formula with two variables. If the occurrences of x and y are replaced by names of appropriate, specific objects, the result is a declarative sentence that is true or false. Given any formula S(x) that contains the letter x (and possibly others), Cantor's principle of abstraction asserts the existence of a set A such that, for each object x, x ∊ A if and only if S(x) holds. (Mathematicians later formulated a restricted principle of abstraction, also known as the principle of comprehension, in which self-referencing predicates, or S(A), are excluded in order to prevent certain paradoxes. See below Cardinality and transfinite numbers (set theory).) Because of the principle of extension, the set A corresponding to S(x) must be unique, and it is symbolized by {x | S(x)}, which is read “The set of all objects x such that S(x).” For instance, {x | x is blue} is the set of all blue objects. This illustrates the fact that the principle of abstraction implies the existence of sets the elements of which are all objects having a certain property. It is actually more comprehensive. For example, it asserts the existence of a set B corresponding to “Either x is an astronaut or x is a natural number.” Astronauts have no particular property in common with numbers (other than both being members of B).

Equivalent sets

      Cantorian set theory is founded on the principles of extension and abstraction, described above. To describe some results based upon these principles, the notion of equivalence of sets will be defined. The idea is that two sets are equivalent if it is possible to pair off members of the first set with members of the second, with no leftover members on either side. To capture this idea in set-theoretic terms, the set A is defined as equivalent to the set B (symbolized by A ≡ B) if and only if there exists a third set the members of which are ordered pairs such that: (1) the first member of each pair is an element of A and the second is an element of B, and (2) each member of A occurs as a first member and each member of B occurs as a second member of exactly one pair. Thus, if A and B are finite and A ≡ B, then the third set that establishes this fact provides a pairing, or matching, of the elements of A with those of B. Conversely, if it is possible to match the elements of A with those of B, then A ≡ B, because a set of pairs meeting requirements (1) and (2) can be formed—i.e., if a ∊ A is matched with b ∊ B, then the ordered pair (a, b) is one member of the set. By thus defining equivalence of sets in terms of the notion of matching, equivalence is formulated independently of finiteness. As an illustration involving infinite sets, ℕ may be taken to denote the set of natural numbers 0, 1, 2, … (some authors exclude 0 from the natural numbers). Then {(n, n²) | n ∊ ℕ} establishes the seemingly paradoxical equivalence of ℕ and the subset of ℕ formed by the squares of the natural numbers.

      As stated previously, a set B is included in, or is a subset of, a set A (symbolized by B ⊆ A) if every element of B is an element of A. So defined, a subset may possibly include all of the elements of A, so that A can be a subset of itself. Furthermore, the empty set, because it by definition has no elements that are not included in other sets, is a subset of every set.

      If every element of set B is an element of set A, but the converse is false (hence B ≠ A), then B is said to be properly included in, or is a proper subset of, A (symbolized by B ⊂ A). Thus, if A = {3, 1, 0, 4, 2}, both {0, 1, 2} and {0, 1, 2, 3, 4} are subsets of A; but {0, 1, 2, 3, 4} is not a proper subset. A finite set is nonequivalent to each of its proper subsets. This is not so, however, for infinite sets, as is illustrated with the set ℕ in the earlier example. (The equivalence of ℕ and its proper subset formed by the squares of its elements was noted by Galileo Galilei (Galileo) in 1638, who concluded that the notions of less than, equal to, and greater than did not apply to infinite sets.)

Cardinality and transfinite numbers (transfinite number)

      The application of the notion of equivalence to infinite sets was first systematically explored by Cantor. With ℕ defined as the set of natural numbers, Cantor's initial significant finding was that the set of all rational numbers is equivalent to ℕ but that the set of all real numbers is not equivalent to ℕ. The existence of nonequivalent infinite sets justified Cantor's introduction of “transfinite” cardinal numbers as measures of size for such sets. Cantor defined the cardinal of an arbitrary set A as the concept that can be abstracted from A taken together with the totality of other equivalent sets. Gottlob Frege (Frege, Gottlob), in 1884, and Bertrand Russell (Russell, Bertrand), in 1902, both mathematical logicians, defined the cardinal number of a set A somewhat more explicitly, as the set of all sets that are equivalent to A. This definition thus provides a place for cardinal numbers as objects of a universe whose only members are sets.

      The above definitions are consistent with the usage of natural numbers as cardinal numbers. Intuitively, a cardinal number, whether finite (i.e., a natural number) or transfinite (i.e., nonfinite), is a measure of the size of a set. Exactly how a cardinal number is defined is unimportant; what is important is that if and only if A ≡ B.

      To compare cardinal numbers, an ordering relation (symbolized by <) may be introduced by means of the definition if A is equivalent to a subset of B and B is equivalent to no subset of A. Clearly, this relation is irreflexive and transitive: and imply.

      When applied to natural numbers used as cardinals, the relation < (less than) coincides with the familiar ordering relation for ℕ, so that < is an extension of that relation.

      The symbol ℵ₀ (aleph-null) is standard for the cardinal number of ℕ (sets of this cardinality are called denumerable), and ℵ (aleph) is sometimes used for that of the set of real numbers. Then n < ℵ₀ for each n ∊ ℕ and ℵ₀ < ℵ.

      This, however, is not the end of the matter. If the power set of a set A—symbolized P(A)—is defined as the set of all subsets of A, then, as Cantor proved,

for every set A—a relation that is known as Cantor's theorem. It implies an unending hierarchy of transfinite cardinals:

. Cantor proved that

and suggested that there are no cardinal numbers between ℵ₀ and ℵ, a conjecture known as the continuum hypothesis.

      There is an arithmetic for cardinal numbers based on natural definitions of addition, multiplication, and exponentiation (squaring, cubing, and so on), but this arithmetic deviates from that of the natural numbers when transfinite cardinals are involved. For example, ℵ₀ + ℵ₀ = ℵ₀ (because the set of integers is equivalent to ℕ), ℵ₀ · ℵ₀ = ℵ₀ (because the set of ordered pairs of natural numbers is equivalent to ℕ), and c + ℵ₀ = c for every transfinite cardinal c (because every infinite set includes a subset equivalent to ℕ).

      The so-called Cantor paradox, discovered by Cantor himself in 1899, is the following. By the unrestricted principle of abstraction, the formula “x is a set” defines a set U; i.e., it is the set of all sets. Now P(U) is a set of sets and so P(U) is a subset of U. By the definition of < for cardinals, however, if A ⊆ B, then it is not the case that

. Hence, by substitution,

. But by Cantor's theorem,

. This is a contradiction. In 1901 Russell devised another contradiction of a less technical nature that is now known as Russell's paradox. The formula “x is a set and (x ∉ x)” defines a set R of all sets not members of themselves. Using proof by contradiction, however, it is easily shown that (1) R ∊ R. But then by the definition of R it follows that (2) (R ∉ R). Together, (1) and (2) form a contradiction.

Axiomatic set theory

      In contrast to naive set theory, the attitude adopted in an axiomatic development of set theory is that it is not necessary to know what the “things” are that are called “sets” or what the relation of membership means. Of sole concern are the properties assumed about sets and the membership relation. Thus, in an axiomatic theory of sets, set and the membership relation ∊ are undefined terms. The assumptions adopted about these notions are called the axioms (axiom) of the theory. Axiomatic set theorems are the axioms together with statements that can be deduced from the axioms using the rules of inference provided by a system of logic. Criteria for the choice of axioms include: (1) consistency—it should be impossible to derive as theorems both a statement and its negation; (2) plausibility—axioms should be in accord with intuitive beliefs about sets; and (3) richness—desirable results of Cantorian set theory can be derived as theorems.

The Zermelo-Fraenkel axioms

 The first axiomatization of set theory was given in 1908 by Ernst Zermelo, a German mathematician. From his analysis of the paradoxes described above in the section Cardinality and transfinite numbers (set theory), he concluded that they are associated with sets that are “too big,” such as the set of all sets in Cantor's paradox. Thus, the axioms that Zermelo formulated are restrictive insofar as the asserting or implying of the existence of sets is concerned. As a consequence, there is no apparent way, in his system, to derive the known contradictions from them. On the other hand, the results of classical set theory short of the paradoxes can be derived. Zermelo's axiomatic theory is here discussed in a form that incorporates modifications and improvements suggested by later mathematicians, principally Thoralf Albert Skolem, a Norwegian pioneer in metalogic, and Abraham Adolf Fraenkel, an Israeli mathematician. In the literature on set theory, it is called Zermelo-Fraenkel set theory and abbreviated ZFC (“C” because of the inclusion of the axiom of choice). See the table—> of Zermelo-Fraenkel axioms.

Schemas for generating well-formed formulas

      The ZFC “axiom of extension” conveys the idea that, as in naive set theory, a set is determined solely by its members. It should be noted that this is not merely a logically necessary property of equality but an assumption about the membership relation as well.

      The set defined by the “axiom of the empty set” is the empty (or null) set Ø.

      For an understanding of the “axiom schema of separation” considerable explanation is required. Zermelo's original system included the assumption that, if a formula S(x) is “definite” for all elements of a set A, then there exists a set the elements of which are precisely those elements x of A for which S(x) holds. This is a restricted version of the principle of abstraction, now known as the principle of comprehension, for it provides for the existence of sets corresponding to formulas. It restricts that principle, however, in two ways: (1) Instead of asserting the existence of sets unconditionally, it can be applied only in conjunction with preexisting sets, and (2) only “definite” formulas may be used. Zermelo offered only a vague description of “definite,” but clarification was given by Skolem (1922) by way of a precise definition of what will be called simply a formula of ZFC. Using tools of modern logic, the definition may be made as follows:

● I. For any variables x and y, x ∊ y and x = y are formulas (such formulas are called atomic).

● II. If S and T are formulas and x is any variable, then each of the following is a formula: If S, then T; S if and only if T; S and T; S or T; not S; for all x, S; for some x, T.

      Formulas are constructed recursively (in a finite number of systematic steps) beginning with the (atomic) formulas of (I) and proceeding via the constructions permitted in (II). “Not (x ∊ y),” for example, is a formula (which is abbreviated to x ∉ y), and “There exists an x such that for every y, y ∉ x” is a formula. A variable is free in a formula if it occurs at least once in the formula without being introduced by one of the phrases “for some x” or “for all x.” Henceforth, a formula S in which x occurs as a free variable will be called “a condition on x” and symbolized S(x). The formula “For every y, x ∊ y,” for example, is a condition on x. It is to be understood that a formula is a formal expression—i.e., a term without meaning. Indeed, a computer can be programmed to generate atomic formulas and build up from them other formulas of ever-increasing complexity using logical connectives (“not,” “and,” etc.) and operators (“for all” and “for some”). A formula acquires meaning only when an interpretation of the theory is specified; i.e., when (1) a nonempty collection (called the domain of the interpretation) is specified as the range of values of the variables (thus the term set is assigned a meaning, viz., an object in the domain), (2) the membership relation is defined for these sets, (3) the logical connectives and operators are interpreted as in everyday language, and (4) the logical relation of equality is taken to be identity among the objects in the domain.

      The phrase “a condition on x” for a formula in which x is free is merely suggestive; relative to an interpretation, such a formula does impose a condition on x. Thus, the intuitive interpretation of the “axiom schema of separation” is: given a set A and a condition on x, S(x), those elements of A for which the condition holds form a set. It provides for the existence of sets by separating off certain elements of existing sets. Calling this the axiom schema of separation is appropriate, because it is actually a schema for generating axioms—one for each choice of S(x).

Axioms for compounding sets

 Although the axiom schema of separation has a constructive quality, further means of constructing sets from existing sets must be introduced if some of the desirable features of Cantorian set theory are to be established. Three axioms in the table—>—axiom of pairing, axiom of union, and axiom of power set—are of this sort.

      By using five of the axioms (2–6), a variety of basic concepts of naive set theory (e.g., the operations of union, intersection, and Cartesian product; the notions of relation, equivalence relation, ordering relation, and function) can be defined with ZFC. Further, the standard results about these concepts that were attainable in naive set theory can be proved as theorems of ZFC.

Axioms for infinite and ordered sets

 If I is an interpretation of an axiomatic theory of sets, the sentence that results from an axiom when a meaning has been assigned to “set” and “∊,” as specified by I, is either true or false. If each axiom is true for I, then I is called a model of the theory. If the domain of a model is infinite, this fact does not imply that any object of the domain is an “infinite set.” An infinite set in the latter sense is an object d of the domain D of I for which there is an infinity of distinct objects d′ in D such that d′Ed holds (E standing for the interpretation of ∊). Though the domain of any model of the theory of which the axioms thus far discussed are axioms is clearly infinite, models in which every set is finite have been devised. For the full development of classical set theory, including the theories of real numbers and of infinite cardinal numbers, the existence of infinite sets is needed; thus the “axiom of infinity” is included. (See the table—>.)

      The existence of a unique minimal set ω having properties expressed in the axiom of infinity can be proved; its distinct members are Ø, {Ø}, {Ø, {Ø}}, {Ø, {Ø}, {Ø, {Ø}}}, … . These elements are denoted by 0, 1, 2, 3, … and are called natural numbers. Justification for this terminology rests with the fact that the Peano postulates (five axioms published in 1889 by the Italian mathematician Giuseppe Peano), which can serve as a base for arithmetic, can be proved as theorems in set theory. Thereby the way is paved for the construction within ZFC of entities that have all the expected properties of the real numbers.

      The origin of the axiom of choice was Cantor's recognition of the importance of being able to “well-order” arbitrary sets—i.e., to define an ordering relation for a given set such that each nonempty subset has a least element. The virtue of a well-ordering for a set is that it offers a means of proving that a property holds for each of its elements by a process (transfinite induction) similar to mathematical induction. Zermelo (1904) gave the first proof that any set can be well-ordered. His proof employed a set-theoretic principle that he called the “axiom of choice,” which, shortly thereafter, was shown to be equivalent to the so-called well-ordering theorem.

      Intuitively, the axiom of choice asserts the possibility of making a simultaneous choice of an element in every nonempty member of any set; this guarantee accounts for its name. The assumption is significant only when the set has infinitely many members. Zermelo was the first to state explicitly the axiom, although it had been used but essentially unnoticed earlier (see also Zorn's lemma). It soon became the subject of vigorous controversy because of its nonconstructive nature. Some mathematicians rejected it totally on this ground. Others accepted it but avoided its use whenever possible. Some changed their minds about it when its equivalence with the well-ordering theorem was proved as well as the assertion that any two cardinal numbers c and d are comparable (i.e., that exactly one of c < d, d < c, c = d holds). There are many other equivalent statements, though even today a few mathematicians feel that the use of the axiom of choice is improper. To the vast majority, however, it, or an equivalent assertion, has become an indispensable and commonplace tool. (Because of this controversy, ZFC was adopted as an acronym for the majority position with the axiom of choice and ZF for the minority position without the axiom of choice.)

Schema for transfinite induction and ordinal arithmetic

      When Zermelo's axioms were found to be inadequate for a full-blown development of transfinite induction and ordinal arithmetic, Fraenkel and Skolem independently proposed an additional axiom schema to eliminate the difficulty. As modified by John von Neumann (von Neumann, John), a Hungarian-born American mathematician, it says, intuitively, that if with each element of a set there is associated exactly one set, then the collection of the associated sets is itself a set; i.e., it offers a way to “collect” existing sets to form sets. As an illustration, each of ω, P(ω), P(P(ω)), … , formed by recursively taking power sets (set formed of all the subsets of the preceding set), is a set in the theory based on Zermelo's original eight axioms. But there appears to be no way to establish the existence of the set having all these sets as its members. However, an instance of the “axiom schema of replacement” provides for its existence.

      Intuitively, the axiom schema of replacement is the assertion that, if the domain of a function is a set, then so is its range. That this is a powerful schema (in respect to the further inferences that it yields) is suggested by the fact that the axiom schema of separation can be derived from it and that, when applied in conjunction with the axiom of power set, the axiom of pairing can be deduced.

      The axiom schema of replacement has played a significant role in developing a theory of ordinal numbers. In contrast to cardinal numbers, which serve to designate the size of a set, ordinal numbers are used to determine positions within a prescribed well-ordered sequence. Under an approach conceived by von Neumann, if A is a set, the successor A′ of A is the set obtained by adjoining A to the elements of A (A′ = A ∪ {A}). In terms of this notion the natural numbers, as defined above, are simply the succession 0, 0′, 0″, 0‴, … ; i.e., the natural numbers are the sets obtained starting with Ø and iterating the prime operation a finite number of times. The natural numbers are well-ordered by the ∊ relation, and with this ordering they constitute the finite ordinal numbers. The axiom of infinity secures the existence of the set of natural numbers, and the set ω is the first infinite ordinal. Greater ordinal numbers are obtained by iterating the prime operation beginning with ω. An instance of the axiom schema of replacement asserts that ω, ω′, ω″, … form a set. The union of this set and ω is the still greater ordinal that is denoted by ω2 (employing notation from ordinal arithmetic). A repetition of this process beginning with ω2 yields the ordinals (ω2)′, (ω2)″, … ; next after all of those of this form is ω3. In this way the sequence of ordinals ω, ω2, ω3, … is generated. An application of the axiom schema of replacement then yields the ordinal that follows all of these in the same sense in which ω follows the finite ordinals; in the notation from ordinal arithmetic, it is ω². At this point the iteration process can be repeated. In summary, the axiom schema of replacement together with the other axioms make possible the extension of the counting process as far beyond the natural numbers as one chooses.

      In the ZFC system, cardinal numbers are defined as certain ordinals. From the well-ordering theorem (a consequence of the axiom of choice), it follows that every set A is equivalent to some ordinal number. Also, the totality of ordinals equivalent to A can be shown to form a set. Then a natural choice for the cardinal number of A is the least ordinal to which A is equivalent. This is the motivation for defining a cardinal number as an ordinal that is not equivalent to any smaller ordinal. The arithmetics of both cardinal and ordinal numbers have been fully developed. That of finite cardinals and ordinals coincides with the arithmetic of the natural numbers. For infinite cardinals, the arithmetic is uninteresting since, as a consequence of the axiom of choice, both the sum and product of two such cardinals are equal to the maximum of the two. In contrast, the arithmetic of infinite ordinals is interesting and presents a wide assortment of oddities.

      In addition to the guidelines already mentioned for the choice of axioms of ZFC, another guideline is taken into account by some set theorists. For the purposes of foundational studies of mathematics (mathematics, foundations of), it is assumed that mathematics is consistent; otherwise, any foundation would fail. It may thus be reasoned that, if a precise account of the intuitive usages of sets by mathematicians is given, an adequate and correct foundation will result. Traditionally, mathematicians deal with the integers, with real numbers, and with functions. Thus, an intuitive hierarchy of sets in which these entities appear should be a model of ZFC. It is possible to construct such a hierarchy explicitly from the empty set by iterating the operations of forming power sets and unions in the following way.

      The bottom of the hierarchy is composed of the sets A₀ = Ø, A₁, … , A_n, … , in which each A_n + 1 is the power set of the preceding A_n. Then one can form the union A_ω of all sets constructed thus far. This can be followed by iterating the power set operation as before: A_ω′ is the power set of A_ω and so forth. This construction can be extended to arbitrarily high transfinite levels. There is no highest level of the hierarchy; at each level, the union of what has been constructed thus far can be taken and the power set operation applied to the elements. In general, for each ordinal number α one obtains a set A_α, each member of which is a subset of some A_β that is lower in the hierarchy. The hierarchy obtained in this way is called the iterative hierarchy. The domain of the intuitive model of ZFC is conceived as the union of all sets in the iterative hierarchy. In other words, a set is in the model if it is an element of some set A_α of the iterative hierarchy.

Axiom for eliminating infinite descending species

      From the assumptions that this system of set theory is sufficiently comprehensive for mathematics and that it is the model to be “captured” by the axioms of ZFC, it may be argued that models of axioms that differ sharply from this system should be ruled out. The discovery of such a model led to the formulation by von Neumann of axiom 10, the axiom of restriction, or foundation axiom.

      This axiom eliminates from the models of the first nine axioms those in which there exist infinite descending ∊-chains (i.e., sequences x₁, x₂, x₃, … such that x₂ ∊ x₁, x₃ ∊ x₂, …), a phenomenon that does not appear in the model based on an iterative hierarchy described above. (The existence of models having such chains was discovered by the Russian mathematician Dimitry Mirimanoff in 1917.) It also has other attractive consequences; e.g., a simpler definition of the notion of ordinal number is possible. Yet there is no unanimity among mathematicians whether there are sufficient grounds for adopting it as an additional axiom. On the one hand, the axiom is equivalent (in a theory that allows only sets) to the statement that every set appears in the iterative hierarchy informally described above—there are no other sets. So it formulates the view that this is what the universe of all sets is really like. On the other hand, there is no compelling need to rule out sets that might lie outside the hierarchy—the axiom has not been shown to have any mathematical applications.

The Neumann-Bernays-Gödel axioms

 The second axiomatization of set theory (see the table—> of Neumann-Bernays-Gödel axioms) originated with John von Neumann in the 1920s. His formulation differed considerably from ZFC because the notion of function, rather than that of set, was taken as undefined, or “primitive.” In a series of papers beginning in 1937, however, the Swiss logician Paul Bernays (Bernays, Paul Isaak), a collaborator with the German formalist David Hilbert (Hilbert, David), modified the von Neumann approach in a way that put it in much closer contact with ZFC. In 1940, the Austrian-born American logician Kurt Gödel (Gödel, Kurt), known for his undecidability proof, further simplified the theory. This axiomatic version of set theory is called NBG, after the Neumann-Bernays-Gödel axioms. As will be explained shortly, NBG is closely related to ZFC, but it allows explicit treatment of so-called classes: collections that might be too large to be sets, such as the class of all sets or the class of all ordinal numbers.

      For expository purposes it is convenient to adopt two undefined notions for NBG: class and the binary relation ∊ of membership (though, as is also true in ZFC, ∊ suffices). For the intended interpretation, variables take classes—the totalities corresponding to certain properties—as values. A class is defined to be a set if it is a member of some class; those classes that are not sets are called proper classes. Intuitively, sets are intended to be those classes that are adequate for mathematics, and proper classes are thought of as those collections that are “so big” that, if they were permitted to be sets, contradictions would follow. In NBG, the classical paradoxes are avoided by proving in each case that the collection on which the paradox is based is a proper class—i.e., is not a set.

      Comments about the axioms that follow are limited to features that distinguish them from their counterpart in ZFC. The axiom schema for class formation is presented in a form to facilitate a comparison with the axiom schema of separation of ZFC. In a detailed development of NBG, however, there appears instead a list of seven axioms (not schemas) that state that, for each of certain conditions, there exists a corresponding class of all those sets satisfying the condition. From this finite set of axioms, each an instance of the above schema, the schema (in a generalized form) can be obtained as a theorem. When obtained in this way, the axiom schema for class formation of NBG is called the class existence theorem.

      In brief, axioms 4 through 8 of NBG are axioms of set existence. The same is true of the next axiom, which for technical reasons is usually phrased in a more general form. Finally, there may appear in a formulation of NBG an analog of the last axiom of ZFC (axiom of restriction).

      A comparison of the two theories that have been formulated is in order. In contrast to the axiom schema of replacement of ZFC, the NBG version is not an axiom schema but an axiom. Thus, with the comments above about the ZFC axiom schema of separation in mind, it follows that NBG has only a finite number of axioms. On the other hand, since the axiom schema of replacement of ZFC provides an axiom for each formula, ZFC has infinitely many axioms—which is unavoidable because it is known that no finite subset yields the full system of axioms. The finiteness of the axioms for NBG makes the logical study of the system simpler. The relationship between the theories may be summarized by the statement that ZFC is essentially the part of NBG that refers only to sets. Indeed, it has been proved that every theorem of ZFC is a theorem of NBG and that any theorem of NBG that speaks only about sets is a theorem of ZFC. From this it follows that ZFC is consistent if and only if NBG is consistent.

Limitations of axiomatic set theory

      The fact that NBG avoids the classical paradoxes and that there is no apparent way to derive any one of them in ZFC does not settle the question of the consistency of either theory. One method for establishing the consistency of an axiomatic theory is to give a model—i.e., an interpretation of the undefined terms in another theory such that the axioms become theorems of the other theory. If this other theory is consistent, then that under investigation must be consistent. Such consistency proofs are thus relative: the theory for which a model is given is consistent if that from which the model is taken is consistent. The method of models, however, offers no hope for proving the consistency of an axiomatic theory of sets. In the case of set theory and, indeed, of axiomatic theories generally, the alternative is a direct approach to the problem.

      If T is the theory of which the (absolute) consistency is under investigation, this alternative means that the proposition “There is no sentence of T such that both it and its negation are theorems of T” must be proved. The mathematical theory (developed by the formalists) to cope with proofs about an axiomatic theory T is called proof theory, or metamathematics. It is premised upon the formulation of T as a formal axiomatic theory—i.e., the theory of inference (as well as T) must be axiomatized. It is then possible to present T in a purely symbolic form—i.e., as a formal language based on an alphabet the symbols of which are those for the undefined terms of T and those for the logical operators and connectives. A sentence in this language is a formula composed from the alphabet according to prescribed rules. The hope for metamathematics was that, by using only intuitively convincing, weak number-theoretic arguments (called finitary methods), unimpeachable proofs of the consistency of such theories as axiomatic set theory could be given.

      That hope suffered a severe blow in 1931 from a theorem proved by Kurt Gödel about any formal theory S that includes the usual vocabulary of elementary arithmetic. By coding the formulas of such a theory with natural numbers (now called Gödel numbers) and by talking about these numbers, Gödel was able to make the metamathematics of S become part of the arithmetic of S and hence expressible in S. The theorem in question asserts that the formula of S that expresses (via a coding) “S is consistent” in S is unprovable in S if S is consistent. Thus, if S is consistent, then the consistency of S cannot be proved within S; rather, methods beyond those that can be expressed or reflected in S must be employed. Because, in both ZFC and NBG, elementary arithmetic can be developed, Gödel's theorem applies to these two theories. Although there remains the theoretical possibility of a finitary proof of consistency that cannot be reflected in the foregoing systems of set theory, no hopeful, positive results have been obtained.

      Other theorems of Gödel when applied to ZFC (and there are corresponding results for NBG) assert that, if the system is consistent, then (1) it contains a sentence such that neither it nor its negation is provable (such a sentence is called undecidable), (2) there is no algorithm (or iterative process) for deciding whether a sentence of ZFC is a theorem, and (3) these same statements hold for any consistent theory resulting from ZFC by the adjunction of further axioms or axiom schemas. Apparently ZFC can serve as a foundation for all of present-day mathematics because every mathematical theorem can be translated into and proved within ZFC or within extensions obtained by adding suitable axioms. Thus, the existence of undecidable sentences in each such theory points out an inevitable gap between the sentences that are true in mathematics and sentences that are provable within a single axiomatic theory. The fact that there is more to conceivable mathematics than can be captured by the axiomatic approach prompted the American logician Emil Post to comment in 1944 that “mathematical thinking is, and must remain, essentially creative.”

Present status of axiomatic set theory

      The foundations of axiomatic set theory are in a state of significant change as a result of new discoveries. The situation with alternate (and conflicting) axiom systems for set theory is analogous to the 19th-century revolution in geometry that was set off by the discovery of non-Euclidean geometries (non-Euclidean geometry). It is difficult to predict the ultimate consequences of these late 20th-century findings for set theory, but already they have had profound effects on attitudes about certain axioms and have forced the realization of a continuous search for additional axioms. These discoveries have focused attention on the concept of the independence of an axiom. If T is an axiomatic theory and S is a sentence (i.e., a formula) of T that is not an axiom, and if T + S denotes the theory that results from T upon the adjunction of S to T as a further axiom, then S is said to be consistent with T if T + S is consistent and independent of T whenever both S and ∼S (the negation of S) are consistent with T. Thus, if S is independent of T, then the addition of S or ∼S to T yields a consistent theory. The role of the axiom of restriction (AR) can be clarified in terms of the notion of independence. If ZF′ denotes the theory obtained from ZF by deleting AR and either retaining or deleting the axiom of choice (AC), then it can be proved that, if ZF′ is consistent, AR is independent of ZF′.

      Of far greater significance for the foundations of set theory is the status of AC relative to the other axioms of ZF. The status in ZF of the continuum hypothesis (CH) and its extension, the generalized continuum hypothesis (GCH), are also of profound importance. In the following discussion of these questions, ZF denotes Zermelo-Fraenkel set theory without AC. The first finding was obtained by Kurt Gödel in 1939. He proved that AC and GCH are consistent relative to ZF (i.e., if ZF is consistent, then so is ZF + AC + GCH) by showing that a contradiction within ZF + AC + GCH can be transformed into a contradiction in ZF. In 1963 American mathematician Paul Cohen (Cohen, Paul Joseph) proved that (1) if ZF is consistent, then so is ZF + AC + ∼CH, and (2) if ZF is consistent, then so is ZF + ∼AC. Since in ZF + AC it can be demonstrated that GCH implies CH, Gödel's theorem together with Cohen's establishes the independence of AC and CH. For his proofs Cohen introduced a new method (called forcing) of constructing interpretations of ZF + AC. The method of forcing is applicable to many problems in set theory, and since 1963 it has been used to give independence proofs for a wide variety of highly technical propositions. Some of these results have opened new avenues for attacks on important foundational questions.

      The current unsettled state of axiomatic set theory can be sensed by the responses that have been made to the question of how to regard CH in the light of its independence from ZF + AC. Someone who believes that set theory deals only with nonexistent fictions will have no concern about the question. But for most mathematicians sets actually exist; in particular, ω and P(ω) exist (the set of the natural numbers and its power set, respectively). Further, it should be the case that every nondenumerable subset of P(ω) either is or is not equivalent to P(ω); i.e., CH either is true or is false. Followers of this faith regard the axioms of set theory as describing some well-defined reality—one in which CH must be either true or false. Thus there is the inescapable conclusion that the present axioms do not provide a complete description of that reality. A search for new axioms is in progress. One who hopes to prove CH as a theorem must look for axioms that restrict the number of sets. There seems to be little hope for this restriction, however, without changing the intuitive notion of the set. Thus the expectations favour the view that CH will be disproved. This disproof requires an axiom that guarantees the existence of more sets—e.g., of sets having cardinalities greater than those that can be proved to exist in ZF + AC. So far, none of the axioms that have been proposed that are aimed in this direction (called “generalized axioms of infinity”) serves to prove ∼CH. Although there is little supporting evidence, the optimists hope that the status of the continuum hypothesis will eventually be settled.

Robert R. Stoll Herbert Enderton

Additional Reading

I. Grattan-Guinness, The Search for Mathematical Roots, 1870–1940 (2000), is the most complete mathematical account of the development of set theory and includes an extensive bibliography. José Ferreirós, Labyrinth of Thought: A History of Set Theory and Its Role in Modern Mathematics (1999), focuses on the motivation and institutions behind the research programs in set theory between 1850 and 1940. Jean van Heijenoort (ed.), From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931 (1967, reissued 2002), has 36 of the most important papers in mathematical logic and set theory.Standard introductions for advanced undergraduate or beginning graduate-level students are Herbert B. Enderton, Elements of Set Theory (1977); and Keith J. Devlin, The Joy of Sets: Fundamentals of Contemporary Set Theory, 2nd rev. ed. (1993; originally published as Fundamentals of Contemporary Set Theory, 1979). Robert L. Vaught, Set Theory: An Introduction, 2nd ed. (1995, reissued 2001), is an undergraduate textbook that includes answers to exercises, increasing its usefulness for self-study. Paul R. Halmos, Naive Set Theory (1960, reissued 1998), is a concise overview of basic set theory ideas for nonspecialist mathematics students.Michael D. Potter, Sets: An Introduction (1990), is an axiomatic development of set theory suitable for undergraduates. Robert R. Stoll, Set Theory and Logic (1963, reissued 1979), is an informal development of ZF. Elliott Mendelson, Introduction to Mathematical Logic, 4th ed. (1997, reissued 2001), includes a formal development of NBG.Robert R. Stoll Herbert Enderton

* * *