Set theory is the mathematical theory of well-determined collections,calledsets, of objects that are calledmembers, orelements, of the set. Pure set theory deals exclusively withsets, so the only sets under consideration are those whose members arealso sets. The theory of thehereditarily-finite sets, namelythose finite sets whose elements are also finite sets, the elements ofwhich are also finite, and so on, is formally equivalent toarithmetic. So, the essence of set theory is the study of infinitesets, and therefore it can be defined as the mathematical theory ofthe actual—as opposed to potential—infinite.

The notion of set is so simple that it is usually introducedinformally, and regarded as self-evident. In set theory, however, asis usual in mathematics, sets are given axiomatically, so theirexistence and basic properties are postulated by the appropriateformal axioms. The axioms of set theory imply the existence of aset-theoretic universe so rich that all mathematical objects can beconstrued as sets. Also, the formal language of pure set theory allowsone to formalize all mathematical notions and arguments. Thus, settheory has become the standard foundation for mathematics, as everymathematical object can be viewed as a set, and every theorem ofmathematics can be logically deduced in the Predicate Calculus fromthe axioms of set theory.

Both aspects of set theory, namely, as the mathematical science of theinfinite, and as the foundation of mathematics, are of philosophicalimportance.

• 1. The origins
• 2. The axioms of set theory
  • 2.1 The axioms of ZFC
• 3. The theory of transfinite ordinals and cardinals
  • 3.1 Cardinals
• 4. The universe \(V\) of all sets
• 5. Set theory as the foundation of mathematics
  • 5.1 Metamathematics
  • 5.2 The incompleteness phenomenon
• 6. The set theory of the continuum
  • 6.1 Descriptive Set Theory
  • 6.2 Determinacy
  • 6.3 The Continuum Hypothesis
• 7. Gödel’s constructible universe
• 8. Forcing
  • 8.1 Other applications of forcing
• 9. The search for new axioms
• 10. Large cardinals
  • 10.1 Inner models of large cardinals
  • 10.2 Consequences of large cardinals
• 11. Forcing axioms
• Bibliography
• Academic Tools
• Other Internet Resources
• Related Entries

1. The origins

Set theory, as a separate mathematical discipline, begins in the workof Georg Cantor. One might say that set theory was born in late 1873,when he made the amazing discovery that the linear continuum, that is,the real line, is not countable, meaning that its points cannot becounted using the natural numbers. So, even though the set of naturalnumbers and the set of real numbers are both infinite, there are morereal numbers than there are natural numbers, which opened the door tothe investigation of the different sizes of infinity. See the entry ontheearly development of set theory for a discussion of the origin of set-theoretic ideas and their useby different mathematicians and philosophers before and aroundCantor’s time.

According to Cantor, two sets \(A\) and \(B\) have the same size, orcardinality, if they are bijectable, i.e., the elements of\(A\) can be put in a one-to-one correspondence with the elements of\(B\). Thus, the set \(\mathbb{N}\) of natural numbers and the set\(\mathbb{R}\) of real numbers have different cardinalities. In 1878Cantor formulated the famousContinuum Hypothesis (CH), whichasserts that every infinite set of real numbers is either countable,i.e., it has the same cardinality as \(\mathbb{N}\), or has the samecardinality as \(\mathbb{R}\). In other words, there are only twopossible sizes of infinite sets of real numbers. The CH is the mostfamous problem of set theory. Cantor himself devoted much effort toit, and so did many other leading mathematicians of the first half ofthe twentieth century, such as Hilbert, who listed the CH as the firstproblem in his celebrated list of 10 (later expanded to 23 in thepublished version) unsolved mathematical problems presented in 1900 atthe Second International Congress of Mathematicians, in Paris. Theattempts to prove the CH led to major discoveries in set theory, suchas the theory of constructible sets, and the forcing technique, whichshowed that the CH can neither be proved nor disproved from the usualaxioms of set theory. To this day, the CH remains open.

Early on, some inconsistencies, or paradoxes, arose from a naive useof the notion of set; in particular, from the deceivingly naturalassumption that every property determines a set, namely the set ofobjects that have the property. One example isRussell’sParadox, also known to Zermelo:

consider the property of sets of not being members of themselves. Ifthe property determines a set, call it \(A\), then \(A\) is a memberof itself if and only if \(A\) is not a member of itself.

Thus, some collections, like the collection of all sets, thecollection of all ordinals numbers, or the collection of all cardinalnumbers, are not sets. Such collections are calledproperclasses.

In order to avoid the paradoxes and put it on a firm footing, settheory had to be axiomatized. The first axiomatization was due toZermelo (1908) and it came as a result of the need to spell out thebasic set-theoretic principles underlying his proof of Cantor’sWell-Ordering Principle. Zermelo’s axiomatization avoidsRussell’s Paradox by means of the Separation axiom, which isformulated as quantifying over properties of sets, and thus it is asecond-order statement. Further work by Skolem and Fraenkel led to theformalization of the Separation axiom in terms of formulas offirst-order, instead of the informal notion of property, as well as tothe introduction of the axiom of Replacement, which is also formulatedas an axiom schema for first-order formulas (see next section). Theaxiom of Replacement is needed for a proper development of the theoryof transfinite ordinals and cardinals, using transfinite recursion(seeSection 3). It is also needed to prove the existence of such simple sets as theset of hereditarily finite sets, i.e., those finite sets whoseelements are finite, the elements of which are also finite, and so on;or to prove basic set-theoretic facts such as that every set iscontained in a transitive set, i.e., a set that contains all elementsof its elements (see Mathias 2001 for the weaknesses of Zermelo settheory). A further addition, by von Neumann, of the axiom ofFoundation, led to the standard axiom system of set theory, known asthe Zermelo-Fraenkel axioms plus the Axiom of Choice, or ZFC.

Other axiomatizations of set theory, such as those of vonNeumann-Bernays-Gödel (NBG), or Morse-Kelley (MK), allow also fora formal treatment of proper classes.

2. The axioms of set theory

ZFC is an axiom system formulated in first-order logic with equalityand with only one binary relation symbol \(\in\) for membership. Thus,we write \(A\in B\) to express that \(A\) is a member of the set\(B\). See the

Supplement on Basic Set Theory

for further details. See also the

Supplement on Zermelo-Fraenkel Set Theory

for a formalized version of the axioms and further comments. We statebelow the axioms of ZFC informally.

2.1 The axioms of ZFC

• Extensionality: If two sets \(A\) and \(B\) have the sameelements, then they are equal.

• Null Set: There exists a set, denoted by \({\varnothing}\)and called theempty set, which has no elements.

• Pair: Given any sets \(A\) and \(B\), there exists a set,denoted by \(\{ A,B\}\), which contains \(A\) and \(B\) as its onlyelements. In particular, there exists the set \(\{ A\}\) which has\(A\) as its only element.

• Power Set: For every set \(A\) there exists a set, denoted by\(\mathcal{P}(A)\) and called thepower set of \(A\), whoseelements are all the subsets of \(A\).

• Union: For every set \(A\), there exists a set, denoted by\(\bigcup A\) and called theunion of \(A\), whose elementsare all the elements of the elements of \(A\).

• Infinity: There exists an infinite set. In particular, thereexists a set \(Z\) that contains \({\varnothing}\) and such that if\(A\in Z\), then \(\bigcup\{ A, \{ A\}\}\in Z\).

• Separation: For every set \(A\) and every given property,there is a set containing exactly the elements of \(A\) that have thatproperty. Aproperty is given by a formula \(\varphi\) of thefirst-order language of set theory.

  Thus, Separation is not a single axiom but an axiom schema, that is,an infinite list of axioms, one for each formula \(\varphi\).

• Replacement: For every givendefinable function withdomain a set \(A\), there is a set whose elements are all the valuesof the function.

  Replacement is also an axiom schema, as definable functions are givenby formulas.

• Foundation: Every non-empty set \(A\) contains an\(\in\)-minimal element, that is, an element such that no element of\(A\) belongs to it.

These are the axioms of Zermelo-Fraenkel set theory, or ZF. The axiomsof Null Set and Pair follow from the other ZF axioms, so they may beomitted. Also, Replacement implies Separation.

Finally, there is the Axiom of Choice (AC):

• Choice: For every set \(A\) of pairwise-disjoint non-emptysets, there exists a set that contains exactly one element from eachset in \(A\).

The AC was, for a long time, a controversial axiom. On the one hand,it is very useful and of wide use in mathematics. On the other hand,it has rather unintuitive consequences, such as the Banach-TarskiParadox, which says that the unit ball can be partitioned intofinitely-many pieces, which can then be rearranged to form two unitballs. The objections to the axiom arise from the fact that it assertsthe existence of sets that cannot be explicitly defined. ButGödel’s 1938 proof of its consistency, relative to theconsistency of ZF, dispelled any suspicions left about it.

The Axiom of Choice is equivalent, modulo ZF, to theWell-orderingPrinciple, which asserts that every set can be well-ordered,i.e., it can be linearly ordered so that every non-empty subset has aminimal element.

Although not formally necessary, besides the symbol \(\in\) onenormally uses for convenience other auxiliary defined symbols. Forexample, \(A\subseteq B\) expresses that \(A\) is asubset of\(B\), i.e., every member of \(A\) is a member of \(B\). Other symbolsare used to denote sets obtained by performing basic operations, suchas \(A\cup B\), which denotes theunion of \(A\) and \(B\),i.e., the set whose elements are those of \(A\) and \(B\); or \(A\capB\), which denotes theintersection of \(A\) and \(B\), i.e.,the set whose elements are those common to \(A\) and \(B\). Theordered pair \((A,B)\) is defined as the set \(\{ \{ A\},\{A,B\}\}\). Thus, two ordered pairs \((A,B)\) and \((C,D)\) are equalif and only if \(A=C\) and \(B=D\). And theCartesian product\(A\times B\) is defined as the set of all ordered pairs \((C,D)\)such that \(C\in A\) and \(D\in B\). Given any formula\(\varphi(x,y_1,\ldots ,y_n)\), and sets \(A,B_1,\ldots ,B_n\), by theaxiom of Separation one can form the set of all those elements of\(A\) that satisfy the formula \(\varphi(x,B_1,\ldots ,B_n)\). Thisset is denoted by \(\{ a\in A: \varphi(a,B_1,\ldots ,B_n)\}\). In ZFone can easily prove that all these sets exist. See theSupplement on Basic Set Theory for further discussion.

3. The theory of transfinite ordinals and cardinals

In ZFC one can develop the Cantorian theory of transfinite (i.e.,infinite) ordinal and cardinal numbers. Following the definition givenby Von Neumann in the early 1920s, the ordinal numbers, orordinals, for short, are obtained by starting with the emptyset and performing two operations: taking the immediate successor, andpassing to the limit. Thus, the first ordinal number is\({\varnothing}\). Given an ordinal \(\alpha\), itsimmediatesuccessor, denoted by \(\alpha +1\), is the set \(\alpha \cup \{\alpha \}\). And given a non-empty set \(X\) of ordinals such that forevery \(\alpha \in X\) the successor \(\alpha +1\) is also in \(X\),one obtains thelimit ordinal \(\bigcup X\). One shows thatevery ordinal is (strictly) well-ordered by \(\in\), i.e., it islinearly ordered by \(\in\) and there is no infinite\(\in\)-descending sequence. Also, every well-ordered set isisomorphic to a unique ordinal, called itsorder-type.

Note that every ordinal is the set of its predecessors. However, theclass \(ON\) of all ordinals is not a set. Otherwise, \(ON\) would bean ordinal greater than all the ordinals, which is impossible. Thefirst infinite ordinal, which is the set of all finite ordinals, isdenoted by the Greek letter omega (\(\omega\)). In ZFC, one identifiesthe finite ordinals with the natural numbers. Thus,\({\varnothing}=0\), \(\{ {\varnothing}\}=1\), \(\{ {\varnothing}, \{{\varnothing}\}\}=2\), etc., hence \(\omega\) is just the set\(\mathbb{N}\) of natural numbers.

One can extend the operations of addition and multiplication ofnatural numbers to all the ordinals. For example, the ordinal \(\alpha+\beta\) is the order-type of the well-ordering obtained byconcatenating a well-ordered set of order-type \(\alpha\) and awell-ordered set of order-type \(\beta\). The sequence of ordinals,well-ordered by \(\in\), starts as follows

0, 1, 2,…, \(n\),…, \(\omega\), \(\omega+1\),\(\omega+2\),…, \(\omega +\omega\),…, \(\omega \cdotn\), …, \(\omega \cdot \omega\),…, \(\omega^n\),…, \(\omega^\omega\), …

The ordinals satisfy the principle oftransfinite induction:suppose that \(C\) is a class of ordinals such that whenever \(C\)contains all ordinals \(\beta\) smaller than some ordinal \(\alpha\),then \(\alpha\) is also in \(C\). Then the class \(C\) contains allordinals. Using transfinite induction one can prove in ZFC (and oneneeds the axiom of Replacement) the important principle oftransfinite recursion, which says that, given any definableclass-function \(G\) (namely a definable operation that takes any set\(x\) to a set \(G(x)\)), one can define a class-function \(F\) withdomain the class \(ON\) of ordinals, such that \(F(\alpha)\) is thevalue of the function \(G\) applied to the function \(F\) restrictedto \(\alpha\). One uses transfinite recursion, for example, in orderto define properly the arithmetical operations of addition, product,and exponentiation on the ordinals.

Recall that an infinite set iscountable if it is bijectable,i.e., it can be put into a one-to-one correspondence, with \(\omega\).All the ordinals displayed above are either finite or countable. Butthe set of all finite and countable ordinals is also an ordinal,called \(\omega_1\), and is not countable. Similarly, the set of allordinals that are bijectable with some ordinal less than or equal to\(\omega_1\) is also an ordinal, called \(\omega_2\), and is notbijectable with \(\omega_1\), and so on.

3.1 Cardinals

Acardinal is an ordinal that is not bijectable with anysmaller ordinal. Thus, every finite ordinal is a cardinal, and\(\omega\), \(\omega_1\), \(\omega_2\), etc. are also cardinals. Theinfinite cardinals are represented by the letter aleph (\(\aleph\)) ofthe Hebrew alphabet, and their sequence is indexed by the ordinals. Itstarts like this

\(\aleph_0\), \(\aleph_1\), \(\aleph_2\), …, \(\aleph_\omega\),\(\aleph_{\omega +1}\), …, \(\aleph_{\omega +\omega}\),…, \(\aleph_{\omega^2}\), …, \(\aleph_{\omega^\omega}\),…, \(\aleph_{\omega_1}\), …, \(\aleph_{\omega_2}\),…

Thus, \(\omega=\aleph_0\), \(\omega_1=\aleph_1\),\(\omega_2=\aleph_2\), etc. For every cardinal there is a bigger one,and the limit of an increasing sequence of cardinals is also acardinal. Thus, the class of all cardinals is not a set, but a properclass.

An infinite cardinal \(\kappa\) is calledregular if it isnot the union of less than \(\kappa\) smaller cardinals. Thus,\(\aleph_0\) is regular, and so are all infinite successor cardinals,such as \(\aleph_1\). Non-regular infinite cardinals are calledsingular. The first singular cardinal is \(\aleph_\omega\),as it is the union of countably-many smaller cardinals, namely\(\aleph_\omega =\bigcup \{\aleph_n : n<\omega\} \).

Thecofinality of a cardinal \(\kappa\), denoted by\(cf(\kappa)\) is the smallest cardinal \(\lambda\) such that\(\kappa\) is the union of \(\lambda\)-many smaller ordinals. Thus,\(cf(\aleph_\omega)=\aleph_0\).

By the AC (in the form of the Well-Ordering Principle), every set\(A\) can be well-ordered, hence it is bijectable with a uniquecardinal, called thecardinality of \(A\). Given twocardinals \(\kappa\) and \(\lambda\), the sum \(\kappa +\lambda\) isdefined as the cardinality of the set consisting of the union of anytwo disjoint sets, one of cardinality \(\kappa\) and one ofcardinality \(\lambda\). And the product \(\kappa \cdot \lambda\) isdefined as the cardinality of the Cartesian product \(\kappa \times\lambda\). The operations of sum and product of infinite cardinals aretrivial, for if \(\kappa\) and \(\lambda\) are infinite cardinals,then \(\kappa +\lambda =\kappa \cdot \lambda = maximum \{ \kappa,\lambda\}\).

In contrast, cardinal exponentiation is highly non-trivial, for eventhe value of the simplest non-trivial infinite exponential, namely\(2^{\aleph_0}\), is not known and cannot be determined in ZFC (seebelow). The cardinal \(\kappa^\lambda\) is defined as the cardinalityof the Cartesian product of \(\lambda\) copies of \(\kappa\);equivalently, as the cardinality of the set of all functions from\(\lambda\) into \(\kappa\). König’s theorem asserts that\(\kappa^{cf(\kappa)}>\kappa\), which implies that the cofinalityof the cardinal \(2^{\aleph_0}\), whatever that cardinal is, must beuncountable. But this is essentially all that ZFC can prove about thevalue of the exponential \(2^{\aleph_0}\).

In the case of exponentiation of singular cardinals, ZFC has a lotmore to say. In 1989, Shelah proved the remarkable result that if\(\aleph_\omega\) is a strong limit, that is,\(2^{\aleph_n}<\aleph_\omega\), for every \(n<\omega\), then\(2^{\aleph_\omega}<\aleph_{\omega_4}\) (see Shelah (1994)). Thetechnique developed by Shelah to prove this and similar theorems, inZFC, is calledpcf theory (forpossiblecofinalities), and has found many applications in other areas ofmathematics.

4. The universe \(V\) of all sets

A posteriori, the ZF axioms other thanExtensionality—which needs no justification because it juststates a defining property of sets—may be justified by their usein building thecumulative hierarchy of sets. Namely, in ZFwe define using transfinite recursion the class-function that assignsto each ordinal \(\alpha\) the set \(V_\alpha\), given as follows:

• \(V_0={\varnothing}\)

• \(V_{\alpha +1}=\mathcal{P}(V_\alpha)\)

• \(V_\alpha =\bigcup \{ V_\beta : \beta <\alpha \}\), whenever\(\alpha\) is a limit ordinal.

The Power Set axiom is used to obtain \(V_{\alpha +1}\) from\(V_\alpha\). Replacement and Union allow one to form \(V_\alpha\) for\(\alpha\) a limit ordinal. Indeed, consider the function that assignsto each \(\beta <\alpha\) the set \(V_\beta\). By Replacement, thecollection of all the \(V_\beta\), for \(\beta <\alpha\), is a set,hence the Union axiom applied to that set yields \(V_\alpha\). Theaxiom of Infinity is needed to prove the existence of \(\omega\) andhence of the transfinite sequence of ordinals. Finally, the axiom ofFoundation is equivalent, assuming the other axioms, to the statementthat every set belongs to some \(V_\alpha\), for some ordinal\(\alpha\). Thus, ZF proves that the set theoretic universe, denotedby \(V\), is the union of all the \(V_\alpha\), \(\alpha\) anordinal.

The proper class \(V\), together with the \(\in\) relation, satisfiesall the ZFC axioms, and is thus a model of ZFC. It is the intendedmodel of ZFC, and one may think of ZFC as providing a description of\(V\), a description however that is highly incomplete, as we shallsee below.

One important property of \(V\) is the so-calledReflectionPrinciple. Namely, for each formula \(\varphi(x_1,\ldots ,x_n)\),ZFC proves that there exists some \(V_\alpha\) that reflects it, thatis, for every \(a_1,\ldots,a_n\in V_\alpha\),

\(\varphi(a_1,\ldots ,a_n)\) holds in \(V\) if and only if\(\varphi(a_1,\ldots,a_n)\) holds in \(V_\alpha\).

Thus, \(V\) cannot be characterized by any sentence, as any sentencethat is true in \(V\) must be also true in some initial segment\(V_\alpha\). In particular, ZFC is not finitely axiomatizable, forotherwise ZFC would prove that, for unboundedly many ordinals\(\alpha\), \(V_\alpha\) is a model of ZFC, contradictingGödel’s second incompleteness theorem (seeSection 5.2).

The Reflection Principle encapsulates the essence of ZF set theory,for as shown by Levy (1960), the axioms of Extensionality, Separation,and Foundation, together with the Reflection Principle, formulated asthe axiom schema asserting that each formula is reflected by some setthat contains all elements and all subsets of its elements (note thatthe \(V_\alpha\) are like this), is equivalent to ZF.

5. Set theory as the foundation of mathematics

Every mathematical object may be viewed as a set. For example, thenatural numbers are identified with the finite ordinals, so\(\mathbb{N}=\omega\). The set of integers \(\mathbb{Z}\) may bedefined as the set of equivalence classes of pairs of natural numbersunder the equivalence relation \((n, m)\equiv (n',m')\) if and only if\(n+m'=m+n'\). By identifying every natural number \(n\) with theequivalence class of the pair \((n,0)\), one may extend naturally theoperations of sum and product of natural numbers to \(\mathbb{Z}\)(see Enderton (1977) for details, and Levy (1979) for a differentconstruction). Further, one may define the rationals \(\mathbb{Q}\) asthe set of equivalence classes of pairs \((n,m)\) of integers, where\(m\ne 0\), under the equivalence relation \((n,m)\equiv (n',m')\) ifand only if \(n\cdot m'=m\cdot n'\). Again, the operations \(+\) and\(\cdot\) on \(\mathbb{Z}\) may be extended naturally to\(\mathbb{Q}\). Moreover, the ordering \(\leq_{\mathbb{Q}}\) on therationals is given by: \(r \leq_{\mathbb{Q}} s\) if and only if thereexists \(t\in \mathbb{Q}\) such that \(s=r+t\). The real numbers maybe defined as Dedekind cuts of \(\mathbb{Q}\), namely, a real numberis given by a pair \((A,B)\) of non-empty disjoint sets such that\(A\cup B=\mathbb{Q}\), \(A\) has no greatest element, and \(a\lt_{\mathbb{Q}} b\) for every \(a\in A\) and \(b\in B\). One can thenextend again the operations of \(+\) and \(\cdot\) on \(\mathbb{Q}\),as well as the ordering \(\leq_{\mathbb{Q}}\), to the set of realnumbers \(\mathbb{R}\).

Let us emphasize that it is not claimed that, e.g., real numbersare Dedekind cuts of rationals, as they could also be definedusing Cauchy sequences, or in other different ways. What is important,from a foundational point of view, is that the set-theoretic versionof \(\mathbb{R}\), together with the usual algebraic operations,satisfies the categorical axioms that the real numbers satisfy, namelythose of a complete ordered field. The metaphysical question of whatthe real numbers really are is irrelevant here.

Algebraic structures can also be viewed as sets, as any \(n\)-aryrelation on the elements of a set \(A\) can be viewed as a set ofordered \(n\)-tuples \((a_1,\ldots ,a_n)\) of elements of \(A\). Andany \(n\)-ary function \(f\) on \(A\), with values on some set \(B\),can be seen as the set of ordered \(n+1\)-tuples \(((a_1,\ldots,a_n),b)\) such that \(b\) is the value of \(f\) on \((a_1,\ldots,a_m)\). Thus, for example, agroup is just a triple \((A, +,0)\), where \(A\) is a non-empty set, \(+\) is a binary function on\(A\) that is associative, \(0\) is an element of \(A\) such that\(a+0=0+a=a\), for all \(a\in A\), and for every \(a\in A\) there isan element of \(A\), denoted by \(-a\), such that \(a+(-a)=(-a)+a=0\).Also, atopological space is just a set \(X\) together with atopology \(\tau\) on it, i.e., \(\tau\) is a subset of\(\mathcal{P}(X)\) containing \(X\) and \({\varnothing}\), and closedunder arbitrary unions and finite intersections. Any mathematicalobject whatsoever can always be viewed as a set, or a proper class.The properties of the object can then be expressed in the language ofset theory. Any mathematical statement can be formalized into thelanguage of set theory, and any mathematical theorem can be derived,using the calculus of first-order logic, from the axioms of ZFC, orfrom some extension of ZFC. It is in this sense that set theoryprovides a foundation for mathematics.

The foundational role of set theory for mathematics, whilesignificant, is by no means the only justification for its study. Theideas and techniques developed within set theory, such as infinitecombinatorics, forcing, or the theory of large cardinals, have turnedit into a deep and fascinating mathematical theory, worthy of study byitself, and with important applications to practically all areas ofmathematics.

5.1 Metamathematics

The remarkable fact that virtually all of mathematics can beformalized within ZFC, makes possible a mathematical study ofmathematics itself. Thus, any questions about the existence of somemathematical object, or the provability of a conjecture or hypothesiscan be given a mathematically precise formulation. This makesmetamathematics possible, namely the mathematical study ofmathematics itself. So, the question about the provability orunprovability of any given mathematical statement becomes a sensiblemathematical question. When faced with an open mathematical problem orconjecture, it makes sense to ask for its provability or unprovabilityin the ZFC formal system. Unfortunately, the answer may be neither,because ZFC, if consistent, is incomplete.

5.2 The incompleteness phenomenon

Gödel’s completeness theorem for first-order logic impliesthat ZFC isconsistent—i.e., no contradiction can bederived from it—if and only if it has a model. Amodelof ZFC is a pair \((M,E)\), where \(M\) is a non-empty set and \(E\)is a binary relation on \(M\) such that all the axioms of ZFC are truewhen interpreted in \((M,E)\), i.e., when the variables that appear inthe axioms range over elements of \(M\), and \(\in\) is interpreted as\(E\). Thus, if \(\varphi\) is a sentence of the language of settheory and one can find a model of ZFC in which \(\varphi\) holds,then its negation \(\neg \varphi\) cannot be proved in ZFC. Hence, ifone can find a model of \(\varphi\) and also a model of \(\neg\varphi\), then \(\varphi\) is neither provable nor disprovable inZFC, in which case we say that \(\varphi\) isundecidable in,orindependent of, ZFC.

In 1931, Gödel announced his striking incompleteness theorems,which assert that any reasonable formal system for mathematics isnecessarily incomplete. In particular, if ZFC is consistent, thenthere are propositions in the language of set theory that areundecidable in ZFC. Moreover, Gödel’s second incompletenesstheorem implies that the formal (arithmetical) statement \(CON(ZFC)\),which asserts that ZFC is consistent, while true, cannot be proved inZFC. And neither can its negation. Thus, \(CON(ZFC)\) is undecidablein ZFC.

If ZFC is consistent, then it cannot prove the existence of a model ofZFC, for otherwise ZFC would prove its own consistency. Thus, a proofof consistency or of undecidability of a given sentence \(\varphi\) isalways arelative consistency proof. That is, one assumesthat ZFC is consistent, hence it has a model, and then one constructsanother model of ZFC where the sentence \(\varphi\) is true. We shallsee several examples in the next sections.

6. The set theory of the continuum

From Cantor and until about 1940, set theory developed mostly aroundthe study of the continuum, that is, the real line \(\mathbb{R}\). Themain topic was the study of the so-called regularity properties, aswell as other structural properties, of simply-definable sets of realnumbers, an area of mathematics that is known asDescriptive SetTheory.

6.1 Descriptive Set Theory

Descriptive Set Theory is the study of the properties and structure ofdefinable sets of real numbers and, more generally, of definablesubsets of \(\mathbb{R}^n\) and otherPolish spaces (i.e.,topological spaces that are homeomorphic to a separable completemetric space), such as theBaire space \(\mathcal{N}\) of allfunctions \(f:\mathbb{N} \to \mathbb{N}\), the space of complexnumbers, Hilbert space, and separable Banach spaces. The simplest setsof real numbers are the basic open sets (i.e., the open intervals withrational endpoints), and their complements. The sets that are obtainedin a countable number of steps by starting from the basic open setsand applying the operations of taking the complement and forming acountable union of previously obtained sets are theBorelsets. All Borel sets areregular, that is, they enjoyall the classicalregularity properties. One example of aregularity property is theLebesgue measurability: a set ofreals is Lebesgue measurable if it differs from a Borel set by a nullset, namely, a set that can be covered by sets of basic open intervalsof arbitrarily-small total length. Thus, trivially, every Borel set isLebesgue measurable, but sets more complicated than the Borel ones maynot be. Other classical regularity properties are theBaireproperty (a set of reals has the Baire property if it differsfrom an open set by a meager set, namely, a set that is a countableunion of sets that are not dense in any interval), and theperfectset property (a set of reals has the perfect set property if itis either countable or contains a perfect set, namely, a nonemptyclosed set with no isolated points). In ZFC one can prove that thereexist non-regular sets of reals, but the AC is necessary for this(Solovay 1970).

Theanalytic sets, also called \(\mathbf{\Sigma}^1_1\), arethe continuous images of Borel sets. And theco-analytic, or\(\mathbf{\Pi}^1_1\), sets are the complements of analytic sets.

Starting from the analytic (or the co-analytic) sets and applying theoperations of projection (from the product space \(\mathbb{R}\times\mathcal{N}\) to \(\mathbb{R}\)) and complementation, one obtains theprojective sets. The projective sets form a hierarchy ofincreasing complexity. For example, if \(A\subseteq \mathbb{R}\times\mathcal{N}\) is co-analytic, then the projection \(\{ x\in\mathbb{R}: \exists y\in \mathcal{N}((x,y)\in A)\}\) is a projectiveset in the next level of complexity above the co-analytic sets. Thosesets are called \(\mathbf{\Sigma}^1_2\), and their complements arecalled \(\mathbf{\Pi}^1_2\).

The projective sets come up very naturally in mathematical practice,for it turns out that a set \(A\) of reals is projective if and onlyif it is definable in the structure

\[\mathcal{R}=(\mathbb{R}, +,\cdot ,\mathbb{Z}).\]

That is, there is a first-order formula \(\varphi ( x, y_1,\ldots,y_n)\) in the language for the structure such that for some\(r_1,\ldots ,r_n\in \mathbb{R}\),

\[A=\{ x\in \mathbb{R}: \mathcal{R}\models \varphi(x,r_1,\ldots,r_n)\}.\]

ZFC proves that every analytic set, and therefore every co-analyticset, is Lebesgue measurable and has the Baire property. It also provesthat every analytic set has the perfect set property. But the perfectset property for co-analytic sets implies that the first uncountablecardinal, \(\aleph_1\), is a large cardinal in the constructibleuniverse \(L\) (seeSection 7), namely a so-called inaccessible cardinal (seeSection 10), which implies that one cannot prove in ZFC that every co-analytic sethas the perfect set property.

The theory of projective sets of complexity greater than co-analyticis completely undetermined by ZFC. For example, in \(L\) there is a\(\mathbf{\Sigma}^1_2\) set that is not Lebesgue measurable and doesnot have the Baire property, whereas if Martin’s axiom holds(seeSection 11), every such set has those regularity properties. There is, however, anaxiom, called the axiom of Projective Determinacy, or PD, that isconsistent with ZFC, modulo the consistency of some large cardinals(in fact, it follows from the existence of some large cardinals), andimplies that all projective sets are regular. Moreover, PD settlesessentially all questions about the projective sets. See the entry onlarge cardinals and determinacy for further details.

6.2 Determinacy

A regularity property of sets that subsumes all other classicalregularity properties is that of beingdetermined. Forsimplicity, we shall work with the Baire space \(\mathcal{N}\). Recallthat the elements of \(\mathcal{N}\) are functions \(f:\mathbb{N} \to\mathbb{N}\), that is, sequences of natural numbers of length\(\omega\). The space \(\mathcal{N}\) is topologically equivalent(i.e., homeomorphic) to the set of irrational points of\(\mathbb{R}\). So, since we are interested in the regularityproperties of subsets of \(\mathbb{R}\), and since countable sets,such as the set of rationals, are negligible in terms of thoseproperties, we may as well work with \(\mathcal{N}\), instead of\(\mathbb{R}\).

Given \(A\subseteq \mathcal{N}\), thegame associated to\(A\), denoted by \({\mathcal G}_A\), has two players, I and II, whoplay alternatively \(n_i\in \mathbb{N}\): I plays \(n_0\), then IIplays \(n_1\), then I plays \(n_2\), and so on. So, at stage \(2k\),player I plays \(n_{2k}\) and at stage \(2k+1\), player II plays\(n_{2k+1} \). We may visualize a run of the game as follows:

After infinitely many moves, the two players produce an infinitesequence \(n_0, n_1,n_2,\ldots\) of natural numbers. Player I wins thegame if the sequence belongs to \(A\). Otherwise, player II wins.

The game \({\mathcal{G}}_A\) isdetermined if there is awinning strategy for one of the players. Awinning strategyfor one of the players, say for player II, is a function \(\sigma\)from the set of finite sequences of natural numbers into\(\mathbb{N}\), such that if the player plays according to thisfunction, i.e., she plays \(\sigma (n_0,\ldots ,n_{2k})\) at the\(k\)-th turn, she will always win the game, no matter what the otherplayer does.

We say that a subset \(A\) of \(\mathcal{N}\) isdeterminedif and only if the game \({\mathcal{G}}_A\) is determined.

One can prove in ZFC—and the use of the AC isnecessary—that there are non-determined sets. Thus, theAxiom of Determinacy (AD), which asserts that all subsets of\(\mathcal{N}\) are determined, is incompatible with the AC. ButDonald Martin proved, in ZFC, that every Borel set is determined.Further, he showed that if there exists a large cardinal calledmeasurable (seeSection 10), then even the analytic sets are determined. The axiom ofProjective Determinacy (PD) asserts that every projective setis determined. It turns out that PD implies that all projective setsof reals are regular, and Woodin has shown that, in a certain sense,PD settles essentially all questions about the projective sets.Moreover, PD seems to be necessary for this. Another axiom,\(AD^{L(\Bbb R )}\), asserts that the AD holds in \(L(\Bbb R)\), whichis the least transitive class that contains all the ordinals and allthe real numbers, and satisfies the ZF axioms (seeSection 7). So, \(AD^{L(\Bbb R )}\) implies that every set of reals that belongsto \(L(\Bbb R)\) is regular. Also, since \(L(\Bbb R)\) contains allprojective sets, \(AD^{L(\Bbb R )}\) implies PD.

6.3 The Continuum Hypothesis

The Continuum Hypothesis (CH), formulated by Cantor in 1878, assertsthat every infinite set of real numbers has cardinality either\(\aleph_0\) or the same cardinality as \(\mathbb{R}\). Thus, the CHis equivalent to \(2^{\aleph_0}=\aleph_1\).

Cantor proved in 1883 that closed sets of real numbers have theperfect set property, from which it follows that every uncountableclosed set of real numbers has the same cardinality as \(\mathbb{R}\).Thus, the CH holds for closed sets. More than thirty years later,Pavel Aleksandrov extended the result to all Borel sets, and thenMikhail Suslin to all analytic sets. Thus, all analytic sets satisfythe CH. However, the efforts to prove that co-analytic sets satisfythe CH would not succeed, as this is not provable in ZFC.

In 1938 Gödel proved the consistency of the CH with ZFC. Assumingthat ZF is consistent, he built a model of ZFC, known as theconstructible universe, in which the CH holds. Thus, theproof shows that if ZF is consistent, then so is ZF together with theAC and the CH. Hence, assuming ZF is consistent, the AC cannot bedisproved in ZF and the CH cannot be disproved in ZFC.

See the entry on thecontinuum hypothesis for the current status of the problem.

7. Gödel’s constructible universe

Gödel’s constructible universe, denoted by \(L\), isdefined by transfinite recursion on the ordinals, similarly as \(V\),but at successor steps, instead of taking the power set of\(V_\alpha\) to obtain \(V_{\alpha +1}\), one only takes the set ofthose subsets of \(L_\alpha\) that are definable in \(L_\alpha\),using elements of \(L_\alpha\) as parameters. Thus, letting\(\mathcal{P}^{Def}(X)\) to denote the set of all the subsets of \(X\)that are definable in the structure \((X,\in )\) by a formula of thelanguage of set theory, using elements of \(X\) as parameters of thedefinition, we let

• \(L_0={\varnothing}\)

• \(L_{\alpha +1}=\mathcal{P}^{Def}(L_\alpha)\)

• \(L_\lambda =\bigcup \{L_\alpha :\alpha <\lambda\}\), whenever\(\lambda\) is a limit ordinal.

Then \(L\) is the union of all the \(L_\alpha\), for \(\alpha\) anordinal.

Gödel showed that \(L\) satisfies all the ZFC axioms, and alsothe CH. In fact, it satisfies theGeneralized ContinuumHypothesis (GCH), namely \(2^{\aleph_\alpha}=\aleph_{\alpha+1}\), for every ordinal \(\alpha\).

The statement \(V=L\), called theaxiom of constructibility,asserts that every set belongs to \(L\). It holds in \(L\), hence itis consistent with ZFC, and implies both the AC and the GCH.

The proper class \(L\), together with the \(\in\) relation restrictedto \(L\), is aninner model of ZFC, that is, atransitive (i.e., it contains all elements of its elements)class that contains all ordinals and satisfies all the ZFC axioms. Itis in fact the smallest inner model of ZFC, as any other inner modelcontains it.

More generally, given any set \(A\), one can build the smallesttransitive model of ZF that contains \(A\) and all the ordinals in asimilar manner as \(L\), but now starting with the transitive closureof \(\{A \}\), i.e., the smallest transitive set that contains \(A\),instead of \({\varnothing}\). The resulting model, \(L(A)\), need notbe however a model of the AC. One very important such model is\(L(\mathbb{R})\), the smallest transitive model of ZF that containsall the ordinals and all the real numbers.

The theory of constructible sets owes much to the work of RonaldJensen. He developed the so-calledfine structure theory of\(L\) and isolated some combinatorial principles, such as the diamond(\(\diamondsuit\)) and square (\(\Box\)), which can be used to carryout complicated constructions of uncountable mathematical objects.Fine structure theory plays also an important role in the analysis ofbigger \(L\)-like models, such as \(L(\mathbb{R})\) or the innermodels for large cardinals (seeSection 10.1).

8. Forcing

In 1963, twenty-five years after Gödel’s proof of theconsistency of the CH and the AC, relative to the consistency of ZF,Paul Cohen (1966) proved the consistency of the negation of the CH,and also of the negation of the AC, relative to the consistency of ZF.Thus, if ZF is consistent, then the CH is undecidable in ZFC, and theAC is undecidable in ZF. To achieve this, Cohen devised a new andextremely powerful technique, calledforcing, for expandingcountable transitive models of ZF, or of ZFC.

Since the axiom \(V=L\) implies the AC and the CH, any model of thenegation of the AC or the CH must violate \(V=L\). So, let’sillustrate the idea of forcing in the case of building a model for thenegation of \(V=L\). We start with a transitive model \(M\) of ZFC,which we may assume, without loss of generality, to be a model of\(V=L\). To violate \(V=L\) we need to expand \(M\) by adding a newset \(r\) so that, in the expanded model, \(r\) will benon-constructible. Since all hereditarily-finite sets areconstructible, we aim to add an infinite set of natural numbers. Thefirst problem we face is that \(M\) may contain already all subsets of\(\omega\). Fortunately, by the Löwenheim-Skolem theorem forfirst-order logic, \(M\) has an elementary submodel which isisomorphic to a countable transitive model \(N\). So, since we areonly interested in the statements that hold in \(M\), and not in \(M\)itself, we may as well work with \(N\) instead of \(M\), and so we mayassume that \(M\) itself is countable. Then, since\(\mathcal{P}(\omega)\) is uncountable, there are plenty of subsets of\(\omega\) that do not belong to \(M\). But, unfortunately, we cannotjust pick any infinite subset \(r\) of \(\omega\) that does not belongto \(M\) and add it to \(M\). The reason is that \(r\) may encode alot of information, so that when added to \(M\), \(M\) is no longer amodel of ZF, or it is still a model of \(V=L\). To avoid this, oneneeds to pick \(r\) with great care. The idea is to pick \(r\)generic over \(M\), meaning that \(r\) is built from itsfinite approximations in such a way that it does not have any propertythat is definable in \(M\) and can be avoided. For example, by viewing\(r\) as an infinite sequence of natural numbers in the increasingorder, the property of \(r\) containing only finitely-many evennumbers can be avoided, because given any finite approximation to\(r\)—i.e., any finite increasing sequence of naturalnumbers—one can always extend it by adding more even numbers, sothat at the end of the construction \(r\) will contain infinitely-manyeven numbers; while the property of containing the number 7 cannot beavoided, because when a finite approximation to \(r\) contains thenumber 7, then it stays there no matter how the construction of \(r\)proceeds. Since \(M\) is countable, there are such generic \(r\). Thenthe expanded model \(M[r]\), which includes \(M\) and contains the newset \(r\), is called ageneric extension of \(M\). Since weassumed \(M\) is a transitive model of \(V=L\), the model \(M[r]\) isjust \(L_\alpha (r)\), where \(\alpha\) is the supremum of theordinals of \(M\). Then one can show, using theforcingrelation between finite approximations to \(r\) and formulas in thelanguage of set theory expanded with so-callednames for setsin the generic extension, that \(M[r]\) is a model of ZFC and \(r\) isnot constructible in \(M[r]\), hence the axiom of constructibility\(V=L\) fails.

In general, a forcing extension of a model \(M\) is obtained by addingto \(M\) a generic subset \(G\) of some partially ordered set\(\mathbb{P}\) that belongs to \(M\). In the above example,\(\mathbb{P}\) would be the set of all finite increasing sequences ofnatural numbers, seen as finite approximations to the infinitesequence \(r\), ordered by \(\subseteq\); and \(G\) would be the setof all finite initial segments of \(r\).

In the case of the consistency proof of the negation of the CH, onestarts from a model \(M\) of ZFC, as before, and adds \(\aleph_2\) newsubsets of \(\omega\), so that in the generic extension the CH fails.In this case one needs to use an appropriate partial ordering\(\mathbb{P}\) so that the \(\aleph_2\) of \(M\) is notcollapsed, i.e., it is the same as the \(\aleph_2\) of thegeneric extension, and thus the generic extension \(M[G]\) willsatisfy the sentence that says that there are \(\aleph_2\) realnumbers.

8.1 Other applications of forcing

Besides the CH, many other mathematical conjectures and problems aboutthe continuum, and other infinite mathematical objects, have beenshown undecidable in ZFC using the forcing technique.

One important example isSuslin’s Hypothesis (SH).Cantor had shown that every linearly ordered set \(S\) withoutendpoints that is dense (i.e., between any two different elements of\(S\) there is another one), complete (i.e., every subset of \(S\)that is bounded above has a supremum), and with a countable densesubset is isomorphic to the real line. Suslin conjectured that this isstill true if one relaxes the requirement of containing a countabledense subset to beingccc, i.e., every collection ofpairwise-disjoint intervals is countable. In the early 1970s, ThomasJech produced a consistent counterexample using forcing, and RonaldJensen showed that a counterexample exists in \(L\). About the sametime, Robert Solovay and Stanley Tennenbaum (1971) developed and usedfor the first time the iterated forcing technique to produce a modelwhere the SH holds, thus showing its independence from ZFC. In orderto make sure that the SH holds in the generic extension, one needs todestroy all counterexamples, but by destroying one particularcounterexample one may inadvertently create new ones, and so one needsto force again and again; in fact one needs to go on for at least\(\omega_2\)-many steps. This is why a forcing iteration isneeded.

Among other famous mathematical problems that have been shownundecidable in ZFC thanks to the forcing technique, especially usingiterated forcing and sometimes combined with large cardinals, we maymention the Measure Problem and the Borel Conjecture in measuretheory, Kaplansky’s Conjecture on Banach algebras, andWhitehead’s Problem in group theory.

9. The search for new axioms

As a result of 60 years of development of the forcing technique, andits applications to many open problems in mathematics, there are nowliterally hundreds of problems and questions, in practically all areasof mathematics, that have been shown independent of ZFC. These includealmost all important questions about the structure of uncountablesets. One might say that the undecidability phenomenon is pervasive,to the point that the investigation of the uncountable has beenrendered nearly impossible in ZFC alone (see however Shelah (1994) forremarkable exceptions).

This prompts the question about the truth-value of the statements thatare undecided by ZFC. Should one be content with them beingundecidable? Does it make sense at all to ask for their truth-value?There are several possible reactions to this. One is theskeptic’s position: the statements that are undecidable in ZFChave no definite answer; and they may even be inherently vague.Another, the common one among mathematicians, is Gödel’sposition: the undecidability only shows that the ZFC system is tooweak to answer those questions, and therefore one should search fornew axioms that once added to ZFC would answer them. The search fornew axioms has been known asGödel’s Program. SeeHauser (2006) for a thorough philosophical discussion of the Program,and also the entry onlarge cardinals and determinacy for philosophical considerations on the justification of new axiomsfor set theory.

A central theme of set theory is thus the search and classification ofnew axioms. These fall currently into two main types: the axioms oflarge cardinals and the forcing axioms.

10. Large cardinals

One cannot prove in ZFC that there exists a regular limit cardinal\(\kappa\), for if \(\kappa\) is such a cardinal, then \(L_\kappa\) isa model of ZFC, and so ZFC would prove its own consistency,contradicting Gödel’s second incompleteness theorem. Thus,the existence of a regular limit cardinal must be postulated as a newaxiom. Such a cardinal is calledweakly inaccessible. If, inaddition \(\kappa\) is a strong limit, i.e., \(2^\lambda <\kappa\),for every cardinal \(\lambda <\kappa\), then \(\kappa\) is calledstrongly inaccessible. A cardinal \(\kappa\) is stronglyinaccessible if and only if it is regular and \(V_\kappa \) is a modelof ZFC. If the GCH holds, then every weakly inaccessible cardinal isstrongly inaccessible.

Large cardinals are uncountable cardinals satisfying some propertiesthat make them very large, and whose existence cannot be proved inZFC. The first weakly inaccessible cardinal is just the smallest ofall large cardinals. Beyond inaccessible cardinals there is a rich andcomplex variety of large cardinals, which form a linear hierarchy interms of consistency strength, and in many cases also in terms ofoutright implication. See the entry onindependence and large cardinals for more details.

To formulate the next stronger large-cardinal notion, let us say thata subset \(C\) of an infinite cardinal \(\kappa\) isclosedif every limit of elements of \(C\) which is less than \(\kappa\) isalso in \(C\); and isunbounded if for every \(\alpha<\kappa\) there exists \(\beta\in C\) greater than \(\alpha\). Forexample, the set of limit ordinals less than \(\kappa\) is closed andunbounded. Also, a subset \(S\) of \(\kappa\) is calledstationary if it intersects every closed unbounded subset of\(\kappa\). If \(\kappa\) is regular and uncountable, then the set ofall ordinals less than \(\kappa\) of cofinality \(\omega\) is anexample of a stationary set. A regular cardinal \(\kappa\) is calledMahlo if the set of strongly inaccessible cardinals smallerthan \(\kappa\) is stationary. Thus, the first Mahlo cardinal is muchlarger than the first strongly inaccessible cardinal, as there are\(\kappa\)-many strongly inaccessible cardinals smaller than\(\kappa\).

Much stronger large cardinal notions arise from considering strongreflection properties. Recall that the Reflection Principle (Section 4), which is provable in ZFC, asserts that everytrue sentence(i.e., every sentence that holds in \(V\)) is true in some\(V_\alpha\). A strengthening of this principle to second-ordersentences yields some large cardinals. For example, \(\kappa\) isstrongly inaccessible if and only if every \(\Sigma^1_1\) sentence(i.e., existential second-order sentence in the language of settheory, with one additional predicate symbol) true in any structure ofthe form \((V_\kappa ,\in, A)\), where \(A\subseteq V_\kappa\), istrue in some \((V_\alpha ,\in ,A\cap V_\alpha)\), with \(\alpha<\kappa\). The same type of reflection, but now for \(\Pi^1_1\)sentences (i.e., universal second-order sentences), yields a muchstronger large cardinal property of \(\kappa\), calledweakcompactness. Every weakly compact cardinal \(\kappa\) is Mahlo,and the set of Mahlo cardinals smaller than \(\kappa\) is stationary.By allowing reflection for more complex second-order, or evenhigher-order, sentences one obtains large cardinal notions strongerthan weak compactness.

The most famous large cardinals, calledmeasurable, werediscovered by Stanisław Ulam in 1930 as a result of his solutionto the Measure Problem. A (two-valued)measure, orultrafilter, on a cardinal \(\kappa\) is a subset \(U\) of\(\mathcal{P}(\kappa)\) that has the following properties: (i) theintersection of any two elements of \(U\) is in \(U\); (ii) if \(X\inU\) and \(Y\) is a subset of \(\kappa\) such that \(X\subseteq Y\),then \(Y\in U\); and (iii) for every \(X\subseteq\kappa\), either\(X\in U\) or \(\kappa -X\in U\), but not both. A measure \(U\) iscalled\(\kappa\)-complete if every intersection of less than\(\kappa\) elements of \(U\) is also in \(U\). And a measure is callednon-principal if there is no \(\alpha <\kappa\) thatbelongs to all elements of \(U\). A cardinal \(\kappa\) is calledmeasurable if there exists a measure on \(\kappa\) that is\(\kappa\)-complete and non-principal.

Measurable cardinals can be characterized by elementary embeddings ofthe universe \(V\) into some transitive class \(M\). That such anembedding \(j:V\to M\) iselementary means that \(j\)preserves truth, i.e., for every formula \(\varphi (x_1,\ldots ,x_n)\)of the language of set theory, and every \(a_1,\ldots ,a_n\), thesentence \(\varphi (a_1,\ldots ,a_n)\) holds in \(V\) if and only if\(\varphi (j(a_1),\ldots ,j(a_n))\) holds in \(M\). It turns out thata cardinal \(\kappa\) is measurable if and only if there exists anelementary embedding \(j:V\to M\), with \(M\) transitive, so that\(\kappa\) is the first ordinal moved by \(j\), i.e., the firstordinal such that \(j(\kappa)\ne \kappa\). We say that \(\kappa\) isthecritical point of \(j\), and write \(crit(j)=\kappa\).The embedding \(j\) is definable from a \(\kappa\)-completenon-principal measure on \(\kappa\), using the so-calledultrapower construction. Conversely, if \(j:V\to M\) is anelementary embedding, with \(M\) transitive and \(\kappa=crit(j)\),then the set \(U=\{ X\subseteq \kappa:\kappa\in j(X)\}\) is a\(\kappa\)-complete non-principal ultrafilter on \(\kappa\). A measure\(U\) obtained in this way from \(j\) is callednormal.

Every measurable cardinal \(\kappa\) is weakly compact, and there aremany weakly compact cardinals smaller than \(\kappa\). In fact, below\(\kappa\) there are many cardinals that aretotallyindescribable, i.e., they reflect all sentences, of anycomplexity, and in any higher-order language.

If \(\kappa\) is measurable and \(j:V\to M\) is given by theultrapower construction, then \(V_\kappa \subseteq M\), and everysequence of length less than or equal to \(\kappa\) of elements of\(M\) belongs to \(M\). Thus, \(M\) is quite similar to \(V\), but itcannot be \(V\) itself. Indeed, a famous theorem of Kenneth Kunenshows that there cannot be any elementary embedding \(j:V\to V\),other than the trivial one, i.e., the identity. All known proofs ofthis result use the Axiom of Choice, and it is an outstandingimportant question if the axiom is necessary. Kunen’s Theoremopens the door to formulating large cardinal notions stronger thanmeasurability by requiring that \(M\) is closer to \(V\).

For example, \(\kappa\) is calledstrong if for every ordinal\(\alpha\) there exists an elementary embedding \(j:V\to M\), for some\(M\) transitive, such that \(\kappa =crit(j)\) and \(V_\alpha\subseteq M\).

Another important, and much stronger large cardinal notion issupercompactness. A cardinal \(\kappa\) issupercompact iffor every \(\alpha\) there exists an elementary embedding \(j:V\toM\), with \(M\) transitive and critical point \(\kappa\), so that\(j(\kappa)>\alpha\) and every sequence of elements of \(M\) oflength \(\alpha\) belongs to \(M\).

Woodin cardinals fall between strong and supercompact. Everysupercompact cardinal is Woodin, and if \(\delta\) is Woodin, then\(V_\delta\) is a model of ZFC in which there is a proper class ofstrong cardinals. Thus, while a Woodin cardinal \(\delta\) need not beitself very strong—the first one is not even weaklycompact—it implies the existence of many large cardinals in\(V_\delta\).

Beyond supercompact cardinals we find theextendiblecardinals, thehuge, thesuper huge, etc.

Kunen’s theorem about the non-existence of a non-trivialelementary embedding \(j:V\to V\) actually shows that there cannot bean elementary embedding \(j:V_{\lambda +2}\to V_{\lambda +2}\)different from the identity, for any \(\lambda\).

The strongest large cardinal notions not known to be inconsistent,modulo ZFC, are the following:

• There exists an elementary embedding \(j:V_{\lambda +1}\to V_{\lambda+1}\) different from the identity.

• There exists an elementary embedding \(j:L(V_{\lambda +1})\toL(V_{\lambda +1})\) different from the identity.

Large cardinals form a linear hierarchy of increasing consistencystrength. In fact they are the stepping stones of the interpretabilityhierarchy of mathematical theories. See the entry onindependence and large cardinals for more details. Typically, given any sentence \(\varphi\) of thelanguage of set theory, exactly one the following three possibilitiesholds about the theory ZFC plus \(\varphi\):

• ZFC plus \(\varphi\) is inconsistent.

• ZFC plus \(\varphi\) is equiconsistent with ZFC (i.e., ZFC isconsistent if and only if so is ZFC plus \(\varphi\)).

• ZFC plus \(\varphi\) is equiconsistent with ZFC plus the existence ofsome large cardinal.

Thus, large cardinals can be used to prove that a given sentence\(\varphi\) does not imply another sentence \(\psi\), modulo ZFC, byshowing that ZFC plus \(\psi\) implies the consistency of some largecardinal, whereas ZFC plus \(\varphi\) is consistent assuming theexistence of a smaller large cardinal, or just assuming theconsistency of ZFC. In other words, \(\psi\) has higher consistencystrength than \(\varphi\), modulo ZFC. Then, by Gödel’ssecond incompleteness theorem, ZFC plus \(\varphi\) cannot prove\(\psi\), assuming ZFC plus \(\varphi\) is consistent.

As we already pointed out, one cannot prove in ZFC that largecardinals exist. But everything indicates that their existence notonly cannot be disproved, but in fact the assumption of theirexistence is a very reasonable axiom of set theory. For one thing,there is a lot of evidence for their consistency, especially for thoselarge cardinals for which it is possible to construct a canonicalinner model.

10.1 Inner models of large cardinals

Aninner model of ZFC is a transitive proper class thatcontains all the ordinals and satisfies all ZFC axioms. Thus, \(L\) isthe smallest inner model, while \(V\) is the largest. Some largecardinals, such as inaccessible, Mahlo, or weakly-compact, may existin \(L\). That is, if \(\kappa\) has one of these large cardinalproperties, then it also has the property in \(L\). But some largecardinals cannot exist in \(L\). Indeed, Scott (1961) showed that ifthere exists a measurable cardinal \(\kappa\), then \(V\ne L\). It isimportant to notice that \(\kappa\) does belong to \(L\), since \(L\)contains all ordinals, but it is not measurable in \(L\) because a\(\kappa\)-complete non-principal measure on \(\kappa\) cannot existthere.

If \(\kappa\) is a measurable cardinal, then one can construct an\(L\)-like model in which \(\kappa\) is measurable by taking a\(\kappa\)-complete non-principal and normal measure \(U\) on\(\kappa\), and proceeding as in the definition of \(L\), but nowusing \(U\) as an additional predicate. The resulting model, called\(L[U]\), is an inner model of ZFC in which \(\kappa\) is measurable,and in fact \(\kappa\) is the only measurable cardinal. The model iscanonical, in the sense that any other normal measure witnessing themeasurability of \(\kappa\) would yield the same model, and has manyof the properties of \(L\). For instance, it has a projective wellordering of the reals, and it satisfies the GCH.

Building similar \(L\)-like models for stronger large cardinals, suchas strong, or Woodin, is much harder. Those models are of the form\(L[E]\), where \(E\) is a sequence ofextenders, eachextender being a coherent system of measures, that encode the relevantelementary embeddings.

The largest \(L\)-like inner models for large cardinals that have beenobtained so far can contain Woodin cardinals that are limits of Woodincardinals (Neeman 2002). However, building an \(L\)-like model for asupercompact cardinal is still a challenge. The supercompact barrierseems to be the crucial one, for Woodin has shown that for a naturalkind of inner model for a supercompact cardinal \(\kappa\), which hecalls aweak extender model for the supercompactness of \( \kappa\), all stronger large cardinals greater than \(\kappa\) that mayexist in \(V\), such as extendible, huge, etc. would also exist in themodel.

10.2 Consequences of large cardinals

The existence of large cardinals has dramatic consequences, even forsimply-definable small sets, like the projective sets of real numbers.For example, Solovay (1970) proved, assuming that there exists ameasurable cardinal, that all \(\mathbf{\Sigma}^1_2\) sets of realsare Lebesgue measurable and have the Baire property, which cannot beproved in ZFC alone. And Shelah and Woodin (1990) showed that theexistence of a proper class of Woodin cardinals implies that thetheory of \(L(\mathbb{R})\), even with real numbers as parameters,cannot be changed by forcing, which implies that all sets of realnumbers that belong to \(L(\mathbb{R})\) are regular. Further, under aweaker large-cardinal hypothesis, namely the existence of infinitelymany Woodin cardinals, Martin and Steel (1989) proved that everyprojective set of real numbers is determined, i.e., the axiom of PDholds, hence all projective sets are regular. Moreover, Woodin showedthat the existence of infinitely many Woodin cardinals, plus ameasurable cardinal above all of them, implies that every set of realsin \(L(\mathbb{R})\) is determined, i.e., the axiom\(AD^{L(\mathbb{R})}\) holds, hence all sets of real numbers thatbelong to \(L(\mathbb{R})\), and therefore all projective sets, areregular. He also showed that Woodin cardinals provide the optimallarge cardinal assumptions by proving that the following twostatements:

1. There are infinitely many Woodin cardinals.

2. \(AD^{L({\Bbb R})}\).

are equiconsistent, i.e., ZFC plus 1 is consistent if and only if ZFCplus 2 is consistent. See the entry onlarge cardinals and determinacy for more details and related results.

Another area in which large cardinals play an important role is theexponentiation of singular cardinals. The so-calledSingularCardinal Hypothesis (SCH) completely determines the behavior ofthe exponentiation for singular cardinals, modulo the exponentiationfor regular cardinals. The SCH follows from the GCH, and so it holdsin \(L\). A consequence of the SCH is that if\(2^{\aleph_n}<\aleph_\omega\), for all finite \(n\), then\(2^{\aleph_{\omega}}=\aleph_{\omega +1}\). Thus, if the GCH holds forcardinals smaller than \(\aleph_\omega\), then it also holds at\(\aleph_\omega\). The SCH holds above the first supercompact cardinal(Solovay). But Magidor (1977) showed that, remarkably, assuming theexistence of large cardinals it is possible to build a model of ZFCwhere the GCH first fails at \(\aleph_\omega\), hence the SCH fails.Large cardinals stronger than measurable are actually needed for this.In contrast, however, ZFC alone suffices to prove that if the SCHholds for all cardinals smaller than \(\aleph_{\omega_1}\), then italso holds for \(\aleph_{\omega_1}\). Moreover, if the SCH holds forall singular cardinals of countable cofinality, then it holds for allsingular cardinals (Silver).

11. Forcing axioms

Forcing axioms are axioms of set theory that assert that certainexistential statements are absolute between the universe \(V\) of allsets and its (ideal) forcing extensions, i.e., some existentialstatements that hold in some forcing extensions of \(V\) are alreadytrue in \(V\). The first forcing axiom was formulated by Donald Martinin the wake of the Solovay-Tennenbaum proof of the consistency ofSuslin’s Hypothesis, and is now known asMartin’sAxiom (MA). Before we state it, let us say that apartialordering is a non-empty set \(P\) together with a binary relation\(\leq\) on \(P\) that is reflexive and transitive. Two elements,\(p\) and \(q\), of \(P\) are calledcompatible if thereexists \(r\in P\) such that \(r\leq p\) and \(r\leq q\). Anantichain of \(P\) is a subset of \(P\) whose elements arepairwise-incompatible. A partial ordering \(P\) is calledcccif every antichain of \(P\) is countable. A non-empty subset \(G\) of\(P\) is called afilter if (i) every two elements of \(G\)are compatible, and (ii) if \(p\in G\) and \(p\leq q\), then also\(q\in G\). Finally, a subset \(D\) of \(P\) is calleddenseif for every \(p\in P\) there is \(q\in D\) such that \(q\leq p\).

MA asserts the following:

For every ccc partial ordering \(P\) and every set \(\{ D_\alpha:\alpha <\kappa \}\), where \(\kappa \lt 2^{\aleph_0}\), of densesubsets of \(P\), there exists a filter \(G\subseteq P\) that isgeneric for the set, i.e., \(G\cap D_\alpha \ne{\varnothing}\), for all \(\alpha <\kappa\).

Since MA follows easily from the CH, MA is only of interest if the CHfails. Martin and Solovay (1970) proved that MA plus the negation ofthe CH is consistent with ZFC, using iterated forcing with the cccproperty. At first sight, MA may not look like an axiom, namely anobvious, or at least reasonable, assertion about sets, but rather likea technical statement about ccc partial orderings. It does look morenatural, however, when expressed in topological terms, for it issimply a generalization of the well-known Baire Category Theorem,which asserts that in every compact Hausdorff topological space theintersection of countably-many dense open sets is non-empty. Indeed,MA is equivalent to:

In every compact Hausdorff ccc topological space, the intersection ofless than \(2^{\aleph_0}\)-many dense open sets is non-empty.

MA has many different equivalent formulations and has been used verysuccessfully to settle a large number of open problems in other areasof mathematics. For example, MA plus the negation of the CH impliesSuslin’s Hypothesis and that every \(\mathbf{\Sigma}^1_2\) setof reals is Lebesgue measurable and has the Baire property. It alsoimplies that \(2^{\aleph_0}\) is a regular cardinal, but it does notdecide what cardinal it is. See Fremlin (1984) for many moreconsequences of MA and other equivalent formulations. In spite ofthis, the status of MA as an axiom of set theory is still unclear.Perhaps the most natural formulation of MA, from a foundational pointof view, is in terms ofgeneric absoluteness. Namely, MA isequivalent to the following:

For every ccc partial ordering \(P\), if an existential statement,containing subsets of some cardinal less than \(2^{\aleph_0}\) asparameters, holds in an (ideal) generic extension of \(V\) obtained byforcing with \(P\), then the statement is true, i.e., it holds in\(V\). In other words, if a set having a property that depends only onbounded subsets of \( 2^{\aleph_0}\) exists in some (ideal) genericextension of \(V\) obtained by forcing with a ccc partial ordering,then a set with that property already exists in \(V\).

The notion of ideal generic extension of \(V\) can be made precise interms of so-called Boolean-valued models, which provide an alternativeversion of forcing.

Much stronger forcing axioms than MA (for \(\omega_1\)) wereintroduced in the 1980s, such as J. Baumgartner’sProperForcing Axiom (PFA), and the strongerMartin’sMaximum (MM) of Foreman, Magidor, and Shelah (1988). Both the PFAand MM are consistent relative to the existence of a supercompactcardinal. The PFA asserts the same as MA, but for partial orderingsthat have a property weaker than the ccc, calledproperness,introduced by Shelah. And MM asserts the same for the wider class ofpartial orderings that, when forcing with them, do not destroystationary subsets of \(\omega_1\).

Strong forcing axioms, such as the PFA and MM imply that allprojective sets of reals are determined (PD), and have many otherstrong consequences in infinite combinatorics. Notably, they implythat the cardinality of the continuum is \(\aleph_2\).

A different forcing axiom is Woodin’s Axiom \((\ast)\), whichresulted from his analysis of \(\mathbb{P}_{{\rm max}}\) forcingextensions over models of AD. Even though a stronger form of MM knownas \({\rm MM}^{++}\) and Axiom \((\ast)\) have similar and very richconsequences, both their motivation and their formulation are verydifferent, to the point that they were seen as competing axioms. Theirconnection was far from being clear, until Asperó and Schindler(2021) showed that, in the presence of large cardinals, Axiom\((\ast)\) is equivalent to a bounded form of \({\rm MM}^{++}\), andtherefore to a natural generic absoluteness principle.

Bibliography

• Asperó, D. and Schindler, R. D., 2021,“Martin’s Maximum\(^{++}\) implies Woodin’s Axiom\((\ast)\)”,Annals of Mathematics, 193(3):793–835.
• Bagaria, J., 2008, “Set Theory”, inThe PrincetonCompanion to Mathematics, edited by Timothy Gowers; JuneBarrow-Green and Imre Leader, associate editors. Princeton: PrincetonUniversity Press.
• Cohen, P.J., 1966,Set Theory and the ContinuumHypothesis, New York: W. A. Benjamin, Inc.
• Enderton, H.B., 1977,Elements of Set Theory, New York:Academic Press.
• Ferreirós, J., 2007,Labyrinth of Thought: A History ofSet Theory and its Role in Modern Mathematics, Second revisededition, Basel: Birkhäuser.
• Foreman, M., Magidor, M., and Shelah, S., 1988,“Martin’s maximum, saturated ideals and non-regularultrafilters”, Part I,Annals of Mathematics, 127:1–47.
• Fremlin, D.H., 1984, “Consequences of Martin’sAxiom”,Cambridge tracts in Mathematics #84. Cambridge:Cambridge University Press.
• Gödel, K., 1931, “Über formal unentscheidbareSätze der Principia Mathematica und verwandter Systeme I,”Monatshefte für Mathematik Physik, 38: 173–198.English translation in Gödel 1986, 144–195.
• –––, 1938, “The consistency of the axiomof choice and of the generalized continuum hypothesis”,Proceedings of the National Academy of Sciences, U.S.A. 24:556–557.
• –––, 1986,Collected Works I. Publications1929–1936, S. Feferman et al. (eds.), Oxford: OxfordUniversity Press.
• Hauser, K., 2006, “Gödel’s program revisited,Part I: The turn to phenomenology”,Bulletin of SymbolicLogic, 12(4): 529–590.
• Jech, T., 2003,Set theory, 3d Edition, New York:Springer.
• Jensen, R.B., 1972, “The fine structure of the constructiblehierarchy”,Annals of Mathematical Logic, 4(3):229–308.
• Kanamori, A., 2003,The Higher Infinite, Second Edition.Springer Monographs in Mathematics, New York: Springer.
• Kechris, A.S., 1995,Classical Descriptive Set Theory,Graduate Texts in Mathematics, New York: SpringerVerlag.
• Kunen, K., 1980,Set Theory, An Introduction to IndependenceProofs, Amsterdam: North-Holland.
• Levy, A., 1960, “Axiom schemata of strong infinity inaxiomatic set theory”,Pacific Journal of Mathematics,10: 223–238.
• –––, 1979,Basic Set Theory, New York:Springer.
• Magidor, M., 1977, “On the singular cardinals problem,II”,Annals of Mathematics, 106: 514–547.
• Martin, D.A. and R. Solovay, 1970, “Internal CohenExtensions”,Annals of Mathematical Logic, 2:143–178.
• Martin, D.A. and J.R. Steel, 1989, “A proof of projectivedeterminacy”,Journal of the American MathematicalSociety, 2(1): 71–125.
• Mathias, A.R.D., 2001, “Slim models of Zermelo SetTheory”,Journal of Symbolic Logic, 66:487–496.
• Neeman, I., 2002, “Inner models in the region of a Woodinlimit of Woodin cardinals”,Annals of Pure and AppliedLogic, 116: 67–155.
• Scott, D., 1961, “Measurable cardinals and constructiblesets”,Bulletin de l’Académie Polonaise desSciences. Série des Sciences Mathématiques,Astronomiques et Physiques, 9: 521–524.
• Shelah, S., 1994, “Cardinal Arithmetic”,OxfordLogic Guides, 29, New York: The Clarendon Press, OxfordUniversity Press.
• –––, 1998,Proper and improper forcing,2nd Edition, New York: Springer-Verlag.
• Shelah, S. and W.H. Woodin, 1990, “Large cardinals implythat every reasonably definable set of reals is Lebesguemeasurable”,Israel Journal of Mathematics, 70(3):381–394.
• Solovay, R., 1970, “A model of set theory in which every setof reals is Lebesgue measurable”,Annals ofMathematics, 92: 1–56.
• Solovay, R. and S. Tennenbaum, 1971, “Iterated Cohenextensions and Souslin’s problem”,Annals ofMathematics (2), 94: 201–245.
• Todorcevic, S., 1989, “Partition Problems inTopology”,Contemporary Mathematics, Volume 84.American Mathematical Society.
• Ulam, S., 1930, ‘Zur Masstheorie in der allgemeinenMengenlehre’,Fundamenta Mathematicae, 16:140–150.
• Woodin, W.H., 1999,The Axiom of Determinacy, Forcing Axioms,and the Nonstationary Ideal,De Gruyter Series in Logic andIts Applications 1, Berlin-New York: Walter de Gruyter.
• –––, 2001, “The Continuum Hypothesis, PartI”,Notices of the AMS, 48(6): 567–576, and“The Continuum Hypothesis, Part II”,Notices of theAMS 48(7): 681–690.
• Zeman, M., 2001,Inner Models and Large Cardinals,DeGruyter Series in Logic and Its Applications 5, Berlin-New York:Walter de Gruyter.
• Zermelo, E., 1908, “Untersuchungen über die Grundlagender Mengenlehre, I”,Mathematische Annalen 65:261–281.Reprinted in Zermelo2010: 189–228, with a facing-page English translation, and anIntroduction by Ulrich Felgner (2010). English translation also in vanHeijenoort 1967: 201–215.

Academic Tools

	How to cite this entry.
	Preview the PDF version of this entry at theFriends of the SEP Society.
	Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO).
	Enhanced bibliography for this entryatPhilPapers, with links to its database.

Other Internet Resources

• Jech, Thomas, “Set Theory”,The StanfordEncyclopedia of Philosophy (Fall 2014 Edition), Edward N. Zalta(ed.), URL = <https://plato.stanford.edu/archives/fall2014/entries/set-theory/>. [This was the previous entry on set theory in theStanfordEncyclopedia of Philosophy — see theversion history.]

Related Entries

set theory: continuum hypothesis |set theory: early development |set theory: independence and large cardinals |set theory: large cardinals and determinacy