See REFLECTION. PRINCIPLE. set theory, the study of collections, ranging from familiar examples like a set of encyclopedias or a deck of cards to mathematical examples like the set of natural numbers or the set of points on a line or the set of functions from a set A to another set B. Sets can be specified in two basic ways: by a list (e.g., {0, 2, 4, 6, 8}) and as the extension of a property (e.g., {x _ x is an even natural number less than 10}, where this is read ‘the set of all x such that x is an even natural number less than 10’). The most fundamental relation in set theory is membership, as in ‘2 is a member of the set of even natural numbers’ (in symbols: 2 1 {x _ x is an even natural number}). Membership is determinate, i.e., any candidate for membership in a given set is either in the set or not in the set, with no room for vagueness or ambiguity. A set’s identity is completely determined by its members or elements (i.e., sets are extensional rather than intensional). Thus {x _ x is human} is the same set as {x _ x is a featherless biped} because they have the same members. The smallest set possible is the empty or null set, the set with no members. (There cannot be more than one empty set, by extensionality.) It can be specified, e.g., as {x _ x & x}, but it is most often symbolized as / or { }. A set A is called a subset of a set B and B a superset of A if every member of A is also a member of B; in symbols, A 0 B. So, the set of even natural numbers is a subset of the set of all natural numbers, and any set is a superset of the empty set. The union of two sets A and B is the set whose members are the members of A and the members of B – in symbols, A 4 B % {x _ x 1 A or x 1 B} – so the union of the set of even natural numbers and the set of odd natural numbers is the set of all natural numbers. The intersection of two sets A and B is the set whose members are common to both A and B – in symbols, A 3 B % {x _ x 1 A and x 1 B} – so the intersection of the set of even natural numbers and the set of prime natural numbers is the singleton set {2}, whose only member is the number 2. Two sets whose intersection is empty are called disjoint, e.g., the set of even natural numbers and the set of odd natural numbers. Finally, the difference between a set A and a set B is the set whose members are members of A but not members of B – in symbols, A – B % {x _ x 1 A and x 2 B} – so the set of odd numbers between 5 and 20 minus the set of prime natural numbers is {9, 15}. By extensionality, the order in which the members of a set are listed is unimportant, i.e., {1, 2, 3} % {2, 3, 1}. To introduce the concept of ordering, we need the notion of the ordered pair of a and b – in symbols, (a, b) or . All that is essential to ordered pairs is that two of them are equal only when their first entries are equal and their second entries are equal. Various sets can be used to simulate this behavior, but the version most commonly used is the Kuratowski ordered pair: (a, b) is defined to be {{a}, {a, b}}. On this definition, it can indeed be proved that (a, b) % (c, d) if and only if a % c and b % d. The Cartesian product of two sets A and B is the set of all ordered pairs whose first entry is in A and whose second entry is B – in symbols, A $ B % {x _ x % (a, b) for some a 1 A and some b 1 B}. This same technique can be used to form ordered triples – (a, b, c) % ((a, b), c); ordered fourtuples – (a, b, c, d) % ((a, b, c), d); and by extension, ordered n-tuples for all finite n.
Using only these simple building blocks, (substitutes for) all the objects of classical mathematics can be constructed inside set theory. For example, a relation is defined as a set of ordered pairs – so the successor relation among natural numbers becomes {(0, 1), (1, 2), (2, 3) . . . } – and a function is a relation containing no distinct ordered pairs of the form (a, b) and (a, c) – so the successor relation is a function. The natural numbers themselves can be identified with various sequences of sets, the most common of which are finite von Neumann ordinal numbers: /, {/}, {/, {/}, {/}, {/}, {/, {/}}}, . . . . (On this definition, 0 % /, 1 % {/}, 2 % {/, {/}}, etc., each number n has n members, the successor of n is n 4 {n}, and n ‹ m if and only if n 1 m.) Addition and multiplication can be defined for these numbers, and the Peano axioms proved (from the axioms of set theory; see below). Negative, rational, real, and complex numbers, geometric spaces, and more esoteric mathematical objects can all be identified with sets, and the standard theorems about them proved. In this sense, set theory provides a foundation for mathematics.
Historically, the theory of sets arose in the late nineteenth century. In his work on the foundations of arithmetic, Frege identified the natural numbers with the extensions of certain concepts; e.g., the number two is the set of all concepts C under which two things fall – in symbols, 2 % {x _ x is a concept, and there are distinct things a and b which fall under x, and anything that falls under x is either a or b}. Cantor was led to consider complex sets of points in the pursuit of a question in the theory of trigonometric series. To describe the properties of these sets, Cantor introduced infinite ordinal numbers after the finite ordinals described above. The first of these, w, is {0, 1, 2, . . .}, now understood in von Neumann’s terms as the set of all finite ordinals. After w, the successor function yields w ! 1 % w 4 {w} % {0, 1, 2, . . . n, n + 1, . . . , w}, then w ! 2 % (w ! 1) ! 1 % {0, 1, 2, . . . , w , w ! 1}, w ! 3 % (w ! 2) ! 1 % {0, 1, 2, . . . , w, w ! 1, w ! 2}, and so on; after all these comes w ! w % {0, 1, 2, . . . , w, w ! 1, w ! 2, . . . , (w ! n), (w ! n) ! 1, . . .}, and the process begins again.
The ordinal numbers are designed to label the positions in an ordering. Consider, e.g., a reordering of the natural numbers in which the odd numbers are placed after the evens: 0, 2, 4, 6, . . . 1, 3, 5, 7, . . . . The number 4 is in the third position of this sequence, and the number 5 is in the (w + 2nd). But finite numbers also perform a cardinal function; they tell us how many so-andso’s there are. Here the infinite ordinals are less effective. The natural numbers in their usual order have the same structure as w, but when they are ordered as above, with the evens before the odds, they take on the structure of a much larger ordinal, w ! w. But the answer to the question, How many natural numbers are there? should be the same no matter how they are arranged. Thus, the transfinite ordinals do not provide a stable measure of the size of an infinite set. When are two infinite sets of the same size? On the one hand, the infinite set of even natural numbers seems clearly smaller than the set of all natural numbers; on the other hand, these two sets can be brought into one-to-one correspondence via the mapping that matches 0 to 0, 1 to 2, 2 to 4, 3 to 6, and in general, n to 2n. This puzzle had troubled mathematicians as far back as Galileo, but Cantor took the existence of a oneto-one correspondence between two sets A and B as the definition of ‘A is the same size as B’. This coincides with our usual understanding for finite sets, and it implies that the set of even natural numbers and the set of all natural numbers and w ! 1 and w! 2 and w ! w and w ! w and many more all have the same size. Such infinite sets are called countable, and the number of their elements, the first infinite cardinal number, is . 0 Cantor also showed that the set of all subsets of a set A has a size larger than A itself, so