there are infinite cardinals greater than F0, namely F1, F2, and so on. Unfortunately, the early set theories were prone to paradoxes. The most famous of these, Russell’s paradox, arises from consideration of the set R of all sets that are not members of themselves: is R 1 R? If it is, it isn’t, and if it isn’t, it is. The Burali-Forti paradox involves the set W of all ordinals: W itself qualifies as an ordinal, so W 1 W, i.e., W ‹ W. Similar difficulties surface with the set of all cardinal numbers and the set of all sets. At fault in all these cases is a seemingly innocuous principle of unlimited comprehension: for any property P, there is a set {x _ x has P}. Just after the turn of the century, Zermelo undertook to systematize set theory by codifying its practice in a series of axioms from which the known derivations of the paradoxes could not be carried out. He proposed the axioms of extensionality (two sets with the same members are the same); pairing (for any a and b, there is a set {a, b}); separation (for any set A and property P, there is a set {x _ x 1 A and x has P}); power set (for any set A, there is a set {x _ x0 A}); union (for any set of sets F, there is a set {x _ x 1 A for some A 1 F} – this yields A 4 B, when F % {A, B} and {A, B} comes from A and B by pairing); infinity (w exists); and choice (for any set of non-empty sets, there is a set that contains exactly one member from each). (The axiom of choice has a vast number of equivalents, including the well-ordering theorem – every set can be well-ordered – and Zorn’s lemma – if every chain in a partially ordered set has an upper bound, then the set has a maximal element.) The axiom of separation limits that of unlimited comprehension by requiring a previously given set A from which members are separated by the property P; thus troublesome sets like Russell’s that attempt to collect absolutely all things with P cannot be formed. The most controversial of Zermelo’s axioms at the time was that of choice, because it posits the existence of a choice set – a set that ‘chooses’ one from each of (possibly infinitely many) non-empty sets – without giving any rule for making the choices. For various philosophical and practical reasons, it is now accepted without much debate.
Fraenkel and Skolem later formalized the axiom of replacement (if A is a set, and every member a of A is replaced by some b, then there is a set containing all the b’s), and Skolem made both replacement and separation more precise by expressing them as schemata of first-order logic. The final axiom of the contemporary theory is foundation, which guarantees that sets are formed in a series of stages called the iterative hierarchy (begin with some non-sets, then form all possible sets of these, then form all possible sets of the things formed so far, then form all possible sets of these, and so on). This iterative picture of sets built up in stages contrasts with the older notion of the extension of a concept; these are sometimes called the mathematical and the logical notions of collection, respectively. The early controversy over the paradoxes and the axiom of choice can be traced to the lack of a clear distinction between these at the time.
Zermelo’s first five axioms (all but choice) plus foundation form a system usually called Z; ZC is Z with choice added. Z plus replacement is ZF, for Zermelo-Fraenkel, and adding choice makes ZFC, the theory of sets in most widespread use today. The consistency of ZFC cannot be proved by standard mathematical means, but decades of experience with the system and the strong intuitive picture provided by the iterative conception suggest that it is. Though ZFC is strong enough for all standard mathematics, it is not enough to answer some natural set-theoretic questions (e.g., the continuum problem). This has led to a search for new axioms, such as large cardinal assumptions, but no consensus on these additional principles has yet been reached. See also CANTOR, CLASS, CONTINUUM PROBLEM , GÖDEL’ S INCOMPLETENESS THEO — REMS , PHILOSOPHY OF MATHEMATICS , SET — THEORETIC PARADOXE. P.Mad.