# Set Theory

*First published Wed Oct 8, 2014*

Set theory is the mathematical theory of well-determined
collections, called *sets*, of objects that are called
*members*, or *elements*, of the set. Pure set theory
deals exclusively with sets, so the only sets under consideration are
those whose members are also sets. The theory of the
*hereditarily-finite* sets, namely those finite sets whose
elements are also finite sets, the elements of which are also finite,
and so on, is formally equivalent to arithmetic. So, the essence of
set theory is the study of infinite sets, and therefore it can be
defined as the mathematical theory of the actual—as opposed to
potential—infinite.

The notion of set is so simple that it is usually introduced informally, and regarded as self-evident. In set theory, however, as is usual in mathematics, sets are given axiomatically, so their existence and basic properties are postulated by the appropriate formal axioms. The axioms of set theory imply the existence of a set-theoretic universe so rich that all mathematical objects can be construed as sets. Also, the formal language of pure set theory allows to formalize all mathematical notions and arguments. Thus, set theory has become the standard foundation for mathematics, as every mathematical object can be viewed as a set, and every theorem of mathematics can be logically deduced in the Predicate Calculus from the axioms of set theory.

Both aspects of set theory, namely, as the mathematical science of the infinite, and as the foundation of mathematics, are of philosophical importance.

- 1. The origins
- 2. The axioms of set theory
- 3. The theory of transfinite ordinals and cardinals
- 4. The universe \(V\) of all sets
- 5. Set theory as the foundation of mathematics
- 6. The set theory of the continuum
- 7. Gödel's constructible universe
- 8. Forcing
- 9. The search for new axioms
- 10. 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 work of 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 be counted using the natural numbers. So, even though the set of natural numbers and the set of real numbers are both infinite, there are more real numbers than there are natural numbers, which opened the door to the investigation of the different sizes of infinity. See the entry on the early development of set theory for a discussion of the origin of set-theoretic ideas and their use by different mathematicians and philosophers before and around Cantor's time.

According to Cantor, two sets \(A\) and \(B\) have the same size, or
*cardinality*, 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 1878
Cantor formulated the famous *Continuum Hypothesis* (CH), which
asserts that every infinite set of real numbers is either countable,
i.e., it has the same cardinality as \(\mathbb{N}\), or has the same
cardinality as \(\mathbb{R}\). In other words, there are only two
possible sizes of infinite sets of real numbers. The CH is the most
famous problem of set theory. Cantor himself devoted much effort to
it, and so did many other leading mathematicians of the first half of
the twentieth century, such as Hilbert, who listed the CH as the first
problem in his celebrated list of 23 unsolved mathematical problems
presented in 1900 at the Second International Congress of
Mathematicians, in Paris. The attempts to prove the CH led to major
discoveries in set theory, such as the theory of constructible sets,
and the forcing technique, which showed that the CH can neither be
proved nor disproved from the usual axioms of set theory. To this day,
the CH remains open.

Early on, some inconsistencies, or paradoxes, arose from a naive
use of the notion of set; in particular, from the deceivingly natural
assumption that every property determines a set, namely the set of
objects that have the property. One example is *Russell's
Paradox*, also known to Zermelo:

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

Thus, some collections, like the collection of all sets, the
collection of all ordinals numbers, or the collection of all cardinal
numbers, are not sets. Such collections are called *proper
classes*.

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

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

## 2. The axioms of set theory

ZFC is an axiom system formulated in first-order logic with equality and 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 state below the axioms of ZFC informally.

### 2.1 The axioms of ZFC

*Extensionality*: If two sets \(A\) and \(B\) have the same elements, then they are equal.*Null Set*: There exists a set, denoted by \({\varnothing}\) and called the*empty 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 only elements. 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 the*power set*of \(A\), whose elements are all the subsets of \(A\).*Union*: For every set \(A\), there exists a set, denoted by \(\bigcup A\) and called the*union*of \(A\), whose elements are all the elements of the elements of \(A\).*Infinity:*There exists an infinite set. In particular, there exists 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 that property. A*property*is given by a formula \(\varphi\) of the first-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 given*definable function*with domain a set \(A\), there is a set whose elements are all the values of the function.Replacement is also an axiom schema, as definable functions are given by 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 axioms of Null Set and Pair follow from the other ZF axioms, so they may be omitted. Also, Replacement implies Separation.

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

*Choice:*For every set \(A\) of pairwise-disjoint non-empty sets, there exists a set that contains exactly one element from each set 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-Tarski Paradox, which says that the unit ball can be partitioned into finitely-many pieces, which can then be rearranged to form two unit balls. The objections to the axiom arise from the fact that it asserts the existence of sets that cannot be explicitly defined. But Gödel's 1938 proof of its consistency, relative to the consistency of ZF, dispelled any suspicions left about it.

The Axiom of Choice is equivalent, modulo ZF, to the
*Well-ordering Principle*, which asserts that every set can be
well-ordered, i.e., it can be linearly ordered so that every non-empty
subset has a minimal element.

Although not formally necessary, besides the symbol \(\in\) one
normally uses for convenience other auxiliary defined symbols. For
example, \(A\subseteq B\) expresses that \(A\) is a *subset* of
\(B\), i.e., every member of \(A\) is a member of \(B\). Other symbols are
used to denote sets obtained by performing basic operations, such as
\(A\cup B\), which denotes the *union* of \(A\) and \(B\), i.e., the
set whose elements are those of \(A\) and \(B\); or \(A\cap B\), which
denotes the *intersection* of \(A\) and \(B\), i.e., the set whose
elements are those common to \(A\) and \(B\). The *ordered pair*
\((A,B)\) is defined as the set \(\{ \{ A\},\{ A,B\}\}\). Thus, two
ordered pairs \((A,B)\) and \((C,D)\) are equal if and only if \(A=C\) and
\(B=D\). And the *Cartesian 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\), one can form the set of all those elements of \(A\)
that satisfy the formula \(\varphi(x,B_1,\ldots ,B_n)\). This set is
denoted by \(\{ a\in A: \varphi(a,B_1,\ldots ,B_n)\}\). In ZF one can
easily prove that all these sets exist. See the supplement 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 given
by Von Neumann in the early 1920s, the ordinal numbers, or
*ordinals*, for short, are obtained by starting with the empty
set and performing two operations: taking the immediate successor, and
passing to the limit. Thus, the first ordinal number is
\({\varnothing}\). Given an ordinal \(\alpha\), its *immediate
successor*, denoted by \(\alpha +1\), is the set \(\alpha \cup \{
\alpha \}\). And given a non-empty set \(X\) of ordinals such that for
every \(\alpha \in X\) the successor \(\alpha +1\) is also in \(X\), one
obtains the *limit ordinal* \(\bigcup X\). One shows that every
ordinal is (strictly) well-ordered by \(\in\), i.e., it is linearly
ordered by \(\in\) and there is no infinite \(\in\)-descending
sequence. Also, every well-ordered set is isomorphic to a unique
ordinal, called its *order-type*.

Note that every ordinal is the set of its predecessors. However, the class \(ON\) of all ordinals is not a set. Otherwise, \(ON\) would be an ordinal greater than all the ordinals, which is impossible. The first infinite ordinal, which is the set of all finite ordinals, is denoted by the Greek letter omega (\(\omega\)). In ZFC, one identifies the 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 of natural numbers to all the ordinals. For example, the ordinal \(\alpha +\beta\) is the order-type of the well-ordering obtained by concatenating a well-ordered set of order-type \(\alpha\) and a well-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\),…, \(n\cdot \omega\), …, \(\omega \cdot \omega\),…, \(\omega^n\), …, \(\omega^\omega\), …

The ordinals satisfy the principle of *transfinite
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
all ordinals. Using transfinite induction one can prove in ZFC (and
one needs the axiom of Replacement) the important principle of
*transfinite recursion*, which says that, given any definable
class-function \(G:V\to V\), one can define a class-function \(F:ON\to V\)
such that \(F(\alpha)\) is the value of the function \(G\) applied to the
function \(F\) restricted to \(\alpha\). One uses transfinite recursion,
for example, in order to define properly the arithmetical operations
of addition, product, and exponentiation on the ordinals.

Recall that an infinite set is *countable* 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. But the set of all finite and countable ordinals is also an
ordinal, called \(\omega_1\), and is not countable. Similarly, the set
of all ordinals that are bijectable with some ordinal less than or
equal to \(\omega_1\) is also an ordinal, called \(\omega_2\), and is not
bijectable with \(\omega_1\), and so on.

### 3.1 Cardinals

A *cardinal* is an ordinal that is not bijectable with any
smaller ordinal. Thus, every finite ordinal is a cardinal, and
\(\omega\), \(\omega_1\), \(\omega_2\), etc. are also cardinals. The
infinite cardinals are represented by the letter aleph (\(\aleph\)) of
the Hebrew alphabet, and their sequence is indexed by the ordinals. It
starts 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 a cardinal. Thus, the class of all cardinals is not a set, but a proper class.

An infinite cardinal \(\kappa\) is called *regular* if it is
not 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 called
*singular*. The first singular cardinal is \(\aleph_\omega\), as
it is the union of countably-many smaller cardinals, namely
\(\aleph_\omega =\bigcup_{n<\omega} \aleph_n\).

The *cofinality* 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 unique
cardinal, called the *cardinality* of \(A\). Given two cardinals
\(\kappa\) and \(\lambda\), the sum \(\kappa +\lambda\) is defined as the
cardinality of the set consisting of the union of any two disjoint
sets, one of cardinality \(\kappa\) and one of cardinality
\(\lambda\). And the product \(\kappa \cdot \lambda\) is defined as the
cardinality of the Cartesian product \(\kappa \times \lambda\). The
operations of sum and product of infinite cardinals are trivial, 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 even the value of the simplest non-trivial infinite exponential, namely \(2^{\aleph_0}\), is not known and cannot be determined in ZFC (see below). The cardinal \(\kappa^\lambda\) is defined as the cardinality of 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 cofinality of the cardinal \(2^{\aleph_0}\), whatever that cardinal is, must be uncountable. But this is essentially all that ZFC can prove about the value of the exponential \(2^{\aleph_0}\).

In the case of exponentiation of singular cardinals, ZFC has a lot
more 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)). The
technique developed by Shelah to prove this and similar theorems, in
ZFC, is called *pcf theory* (for *possible
cofinalities*), and has found many applications in other areas of
mathematics.

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

*A posteriori*, the ZF axioms other than
Extensionality—which needs no justification because it just
states a defining property of sets—may be justified by their use
in building the *cumulative hierarchy of sets*. Namely, in ZF
we define using transfinite recursion the class-function that assigns
to each ordinal \(\alpha\) the set \(V_\alpha\), given as follows:

\(V_0={\varnothing}\)

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

\(V_\alpha =\bigcup_{\beta <\alpha}V_\beta\), 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 assigns to each \(\beta <\alpha\) the set \(V_\beta\). By Replacement, the collection of all the \(V_\beta\), for \(\beta <\alpha\), is a set, hence the Union axiom applied to that set yields \(V_\alpha\). The axiom of Infinity is needed to prove the existence of \(\omega\) and hence of the transfinite sequence of ordinals. Finally, the axiom of Foundation is equivalent, assuming the other axioms, to the statement that every set belongs to some \(V_\alpha\), for some ordinal \(\alpha\). Thus, ZF proves that the set theoretic universe, denoted by \(V\), is the union of all the \(V_\alpha\), \(\alpha\) an ordinal.

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

One ZFC-provable important property of \(V\) is the so-called
*Reflection Principle*. Namely, for each formula
\(\varphi(x_1,\ldots ,x_n)\), ZFC proves that there exists an ordinal
\(\alpha\) such that \(V_\alpha\) reflects it, that is, 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 sentence that is true in \(V\) must be also true in some initial segment \(V_\alpha\). In particular, ZFC is not finitely axiomatizable, for otherwise ZFC would prove that, for unboundedly many ordinals \(\alpha\), \(V_\alpha\) is a model of ZFC, contradicting Gödel's second incompleteness theorem (see Section 5.2).

The Reflection Principle encapsulates the essence of ZF set theory, for it is equivalent to the axioms of Infinity plus Replacement, modulo the other ZF axioms.

## 5. Set theory as the foundation of mathematics

Every mathematical object may be viewed as a set. For example, the natural numbers are identified with the finite ordinals, so \(\mathbb{N}=\omega\). The set of integers \(\mathbb{Z}\) may be defined as the set of equivalence classes of pairs of natural numbers under the equivalence relation \((n, m)\equiv (n',m')\) if and only if \(n+m'=m+n'\). By identifying every natural number \(n\) with the equivalence class of the pair \((n,0)\), one may extend naturally the operations of sum and product of natural numbers to \(\mathbb{Z}\) (see Enderton (1977) for details, and Levy (1979) for a different construction). Further, one may define the rationals \(\mathbb{Q}\) as the set of equivalence classes of pairs \((n,m)\) of integers, where \(m\ne 0\), under the equivalence relation \((n,m)\equiv (n',m')\) if and 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 the rationals is given by: \(r \leq_{\mathbb{Q}} s\) if and only if there exists \(t\in \mathbb{Q}\) such that \(s=r+t\). The real numbers may be defined as Dedekind cuts of \(\mathbb{Q}\), namely, a real number is given by a pair \((A,B)\) of non-empty disjoint sets such that \(A\cup B=\mathbb{Q}\), and \(a\leq_{\mathbb{Q}}b\) for every \(a\in A\) and \(b\in B\). One can then extend again the operations of \(+\) and \(\cdot\) on \(\mathbb{Q}\), as well as the ordering \(\leq_{\mathbb{Q}}\), to the set of real numbers \(\mathbb{R}\).

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

Algebraic structures can also be viewed as sets, as any \(n\)-ary
relation on the elements of a set \(A\) can be viewed as a set of
\(n\)-tuples \((a_1,\ldots ,a_n)\) of elements of \(A\). And any \(n\)-ary
function \(f\) on \(A\), with values on some set \(B\), can be seen as the
set of \(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, a *group* 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
is an element of \(A\), denoted by \(-a\), such that
\(a+(-a)=(-a)+a=0\). Also, a *topological space* is just a set
\(X\) together with a topology \(\tau\) on it, i.e., \(\tau\) is a subset of
\(\mathcal{P}(X)\) containing \(X\) and \({\varnothing}\), and closed under
arbitrary unions and finite intersections. Any mathematical object
whatsoever can always be viewed as a set, or a proper class. The
properties of the object can then be expressed in the language of set
theory. Any mathematical statement can be formalized into the language
of set theory, and any mathematical theorem can be derived, using the
calculus of first-order logic, from the axioms of ZFC, or from some
extension of ZFC. It is in this sense that set theory provides a
foundation for mathematics.

The foundational role of set theory for mathematics, while significant, is by no means the only justification for its study. The ideas and techniques developed within set theory, such as infinite combinatorics, forcing, or the theory of large cardinals, have turned it into a deep and fascinating mathematical theory, worthy of study by itself, and with important applications to practically all areas of mathematics.

### 5.1 Metamathematics

The remarkable fact that virtually all of mathematics can be
formalized within ZFC, makes possible a mathematical study of
mathematics itself. Thus, any questions about the existence of some
mathematical object, or the provability of a conjecture or hypothesis
can be given a mathematically precise formulation. This makes
*metamathematics* possible, namely the mathematical study of
mathematics itself. So, the question about the provability or
unprovability of any given mathematical statement becomes a sensible
mathematical question. When faced with an open mathematical problem or
conjecture, it makes sense to ask for its provability or unprovability
in 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 implies
that ZFC is *consistent*—i.e., no contradiction can be
derived from it—if and only if it has a model. A *model*
of 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 true when
interpreted in \((M,E)\), i.e., when the variables that appear in the
axioms range over elements of \(M\), and \(\in\) is interpreted as
\(E\). Thus, if \(\varphi\) is a sentence of the language of set theory
and one can find a model of ZFC in which \(\varphi\) holds, then its
negation \(\neg \varphi\) cannot be proved in ZFC. Hence, if one can
find a model of \(\varphi\) and also a model of \(\neg \varphi\), then
\(\varphi\) is neither provable nor disprovable in ZFC, in which case we
say that \(\varphi\) is *undecidable* in, or *independent*
of, ZFC.

In 1931, Gödel announced his striking incompleteness theorems, which assert that any reasonable formal system for mathematics is necessarily incomplete. In particular, if ZFC is consistent, then there are undecidable propositions in ZFC. Moreover, Gödel's second incompleteness theorem implies that the formal (arithmetical) statement \(CON(ZFC)\), which asserts that ZFC is consistent, while true, cannot be proved in ZFC. And neither can its negation. Thus, \(CON(ZFC)\) is undecidable in ZFC.

If ZFC is consistent, then it cannot prove the existence of a model
of ZFC, for otherwise ZFC would prove its own consistency. Thus, a
proof of consistency or of undecidability of a given sentence
\(\varphi\) is always a *relative consistency* proof. That is,
one assumes that ZFC is consistent, hence it has a model, and then one
constructs another model of ZFC where the sentence \(\varphi\) is
true. We shall see several examples in the next sections.

## 6. The set theory of the continuum

From Cantor and until about 1940, set theory developed mostly
around the study of the continuum, that is, the real line
\(\mathbb{R}\). The main topic was the study of the so-called regularity
properties, as well as other structural properties, of
simply-definable sets of real numbers, an area of mathematics that is
known as *Descriptive Set Theory*.

### 6.1 Descriptive Set Theory

Descriptive Set Theory is the study of the properties and structure
of definable sets of real numbers and, more generally, of definable
subsets of \(\mathbb{R}^n\) and other *Polish spaces* (i.e.,
separable, metric, and complete), such as the *Baire space*
\(\mathcal{N}\) of all functions \(f:\mathbb{N} \to \mathbb{N}\), the
space of complex numbers, Hilbert space, and separable Banach
spaces. The simplest sets of real numbers are the basic open sets
(i.e., the open intervals with rational endpoints), and their
complements. The sets that are obtained in a countable number of steps
by starting from the basic open sets and applying the operations of
taking the complement and forming a countable union of previously
obtained sets are the *Borel sets*. All Borel sets are
*regular*, that is, they enjoy all the classical *regularity
properties*. One example of a regularity property is the
*Lebesgue measurability*: a set of reals is Lebesgue measurable
if it differs from a Borel set by a null set, namely, a set that can
be covered by sets of basic open intervals of arbitrarily-small total
length. Thus, trivially, every Borel set is Lebesgue measurable, but
sets more complicated than the Borel ones may not be. Other classical
regularity properties are the *Baire property* (a set of reals
has the Baire property if it differs from an open set by a meager set,
namely, a set that is a countable union of sets that are not dense in
any interval), and the *perfect set property* (a set of reals
has the perfect set property if it is either countable or contains a
perfect set, namely, a closed set with no isolated points). In ZFC one
can prove that there exist non-regular sets of reals, but the AC is
necessary for this (Solovay 1970).

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

Starting from the analytic (or the co-analytic) sets and applying
the operations of projection (from the product space \(\mathbb{R}\times
\mathcal{N}\) to \(\mathbb{R}\)) and complementation, one obtains the
*projective sets*. The projective sets form a hierarchy of
increasing 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 projective set in the
next level of complexity above the co-analytic sets. Those sets are
called \(\mathbf{\Sigma}^1_2\), and their complements are called
\(\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 only if 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-analytic set, is Lebesgue measurable and has the Baire property. It also proves that every analytic set has the perfect set property. But the perfect set property for co-analytic sets implies that the first uncountable cardinal, \(\aleph_1\), is a large cardinal in the constructible universe \(L\) (see Section 7), namely a so-called inaccessible cardinal (see Section 10), which implies that one cannot prove in ZFC that every co-analytic set has the perfect set property.

The theory of projective sets of complexity greater than co-analytic is completely undetermined by ZFC. For example, in \(L\) there is a \(\mathbf{\Sigma}^1_2\) set that is not Lebesgue measurable and does not have the Baire property, whereas if Martin's axiom holds (see Section 11), every such set has those regularity properties. There is, however, an axiom, called the axiom of Projective Determinacy, or PD, that is consistent with ZFC, modulo the consistency of some large cardinals, and implies that all projective sets are regular. Moreover, PD settles essentially all questions about the projective sets. See the entry on large cardinals and determinacy for further details.

### 6.2 Determinacy

A regularity property of sets that subsumes all other classical
regularity properties is that of being *determined*. For
simplicity, we shall work with the Baire space \(\mathcal{N}\). Recall
that 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 regularity properties of subsets of
\(\mathbb{R}\), and since countable sets, such as the set of rationals,
are negligible in terms of those properties, we may as well work with
\(\mathcal{N}\), instead of \(\mathbb{R}\).

Given \(A\subseteq \mathcal{N}\), the *game*
associated to \(A\), denoted by \({\mathcal G}_A\), has two players, I and
II, who play alternatively \(n_i\in \mathbb{N}\): I plays \(n_0\), then II
plays \(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:

\(\mathbf{I}\) \(n_0\) \(n_2\) \(n_4\) \(\cdots\) \(n_{2k}\) \(\cdots\) \(\mathbf{II}\) \(n_1\) \(n_3\) \(\cdots\) \(\cdots\) \(n_{2k+1}\) \(\cdots\)

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

The game \({\mathcal{G}}_A\) is *determined* if
there is a winning strategy for one of the players. A *winning
strategy* for 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 this
function, 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 other player
does.

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

One can prove in ZFC—and the use of the AC is
necessary—that there are non-determined sets. Thus, the
*Axiom of Determinacy* (AD), which asserts that all subsets of
\(\mathcal{N}\) are determined, is incompatible with the AC. But Donald
Martin proved, in ZFC, that every Borel set is determined. Further, he
showed that if there exists a large cardinal called measurable (see
Section 10), then even the analytic sets are
determined. The axiom of *Projective Determinacy* (PD) asserts
that every projective set is determined. It turns out that PD implies
that all projective sets of 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)\), which is the least transitive class that contains all the
ordinals and all the real numbers, and satisfies the ZF axioms (see
Section 7). So, \(AD^{L(\Bbb R )}\) implies that
every set of reals that belongs to \(L(\Bbb R)\) is regular. Also, since
\(L(\Bbb R)\) contains all projective sets, \(AD^{L(\Bbb R )}\) implies
PD.

### 6.3 The Continuum Hypothesis

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

Cantor proved in 1883 that closed sets of real numbers have the perfect set property, from which it follows that every uncountable closed 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 then Mikhail Suslin to all analytic sets. Thus, all analytic sets satisfy the CH. However, the efforts to prove that co-analytic sets satisfy the CH would not succeed, as this is not provable in ZFC.

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

See the entry on the continuum hypothesis for the current status of the problem, including the latest results by Woodin.

## 7. Gödel's constructible universe

Gödel's constructible universe, denoted by \(L\), is defined 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 those 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 the language of set theory, using elements of \(X\) as parameters of the definition, we let

\(L_0={\varnothing}\)

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

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

Then \(L\) is the union of all the \(L_\alpha\), for \(\alpha\) an ordinal, i.e., \(L=\bigcup_{\alpha \in ON}L_\alpha\).

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

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

The proper class \(L\), together with the \(\in\) relation restricted
to \(L\), is an *inner model* of ZFC, that is, a
*transitive* (i.e., it contains all elements of its elements)
class that contains all ordinals and satisfies all the ZFC axioms. It
is in fact the smallest inner model of ZFC, as any other inner model
contains it.

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

The theory of constructible sets owes much to the work of Ronald
Jensen. He developed the so-called *fine structure* theory of
\(L\) and isolated some combinatorial principles, such as the diamond
(\(\diamondsuit\)) and square (\(\Box\)), which can be used to carry out
complicated constructions of uncountable mathematical objects. Fine
structure theory plays also an important role in the analysis of
bigger \(L\)-like models, such as \(L(\mathbb{R})\) or the inner models
for large cardinals (see
Section 10.1).

## 8. Forcing

In 1963, twenty-five years after Gödel's proof of the
consistency of the CH, relative to the consistency of ZFC, and the
consistency of the AC from the consistency of ZF, Paul Cohen (1966)
proved the consistency of the negation of the CH, relative to the
consistency of ZFC. Thus, if ZFC is consistent, then the CH is
undecidable in ZFC. He also proved the consistency of the negation of
the AC, relative to the consistency of ZF. To achieve this, Cohen
devised a new and extremely powerful technique, called
*forcing*, for expanding transitive models of ZFC.

Since the axiom \(V=L\) implies the AC and the CH, any model of the
negation of the AC or the CH must violate \(V=L\). So, let's illustrate
the idea of forcing in the case of building a model for the negation
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 new set \(r\) so that, in the
expanded model, \(r\) will be non-constructible. Since all
hereditarily-finite sets are constructible, we aim to add an infinite
set of natural numbers. The first problem we face is that \(M\) may
contain already all subsets of \(\omega\). Fortunately, by the
Löwenheim-Skolem theorem for first-order logic, \(M\) has a
countable elementary submodel \(N\). So, since we are only 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 may assume 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 cannot just pick any infinite subset \(r\) of \(\omega\)
that does not belong to \(M\) and add it to \(M\). The reason is that \(r\)
may encode a lot of information, so that when added to \(M\), \(M\) is no
longer a model of ZFC, or it is still a model of \(V=L\). To avoid this,
one needs to pick \(r\) with great care. The idea is to pick \(r\)
*generic* over \(M\), meaning that \(r\) is built from its finite
approximations in such a way that it does not have any property that
is definable in \(M\) and can be avoided. For example, by viewing \(r\) as
an infinite sequence of natural numbers in the increasing order, the
property of \(r\) containing only finitely-many even numbers can be
avoided, because given any finite approximation to \(r\)—i.e., any
finite increasing sequence of natural numbers—one can always
extend it by adding more even numbers, so that at the end of the
construction \(r\) will contain infinitely-many even numbers; while the
property of containing the number 7 cannot be avoided, because when a
finite approximation to \(r\) contains the number 7, then it stays there
no matter how the construction of \(r\) proceeds. Since \(M\) is
countable, there are such generic \(r\). Then the expanded model \(M[r]\),
which includes \(M\) and contains the new set \(r\), is called a
*generic extension* of \(M\). Since we assumed \(M\) is a
transitive model of \(V=L\), the model \(M[r]\) is just \(L_\alpha (r)\),
where \(\alpha\) is the supremum of the ordinals of \(M\). Then one can
show, using the *forcing* relation between finite
approximations to \(r\) and formulas in the language of set theory
expanded with so-called *names* for sets in the generic
extension, that \(M[r]\) is a model of ZFC and \(r\) is not constructible
in \(M[r]\), hence the axiom of constructibility \(V=L\) fails.

In general, a forcing extension of a model \(M\) is obtained by adding to \(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 of natural numbers, seen as finite approximations to the infinite sequence \(r\), ordered by \(\subseteq\); and \(G\) would be the set of all finite initial segments of \(r\).

In the case of the consistency proof of the negation of the CH, one
starts from a model \(M\) and adds \(\aleph_2\) new subsets 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 not *collapsed*, i.e., it is the same as
the \(\aleph_2\) of the generic extension, and thus the generic
extension \(M[G]\) will satisfy the sentence that says that there are
\(\aleph_2\) real numbers.

### 8.1 Other applications of forcing

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

One important example is *Suslin's Hypothesis* (SH). Cantor
had shown that every linearly ordered set \(S\) without endpoints 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 dense subset is isomorphic
to the real line. Suslin conjectured that this is still true if one
relaxes the requirement of containing a countable dense subset to
being *ccc*, i.e., every collection of pairwise-disjoint
intervals is countable. In the early 1970s, Thomas Jech produced a
consistent counterexample using forcing, and Ronald Jensen showed that
a counterexample exists in \(L\). About the same time, Robert Solovay
and Stanley Tennenbaum (1971) developed and used for the first time
the iterated forcing technique to produce a model where the SH holds,
thus showing its independence from ZFC. In order to make sure that the
SH holds in the generic extension, one needs to destroy all
counterexamples, but by destroying one particular counterexample one
may inadvertently create new ones, and so one needs to force again and
again; in fact one needs to go on for at least \(\omega_2\)-many
steps. This is why a forcing iteration is needed.

Among other famous mathematical problems that have been shown undecidable in ZFC thanks to the forcing technique, especially using iterated forcing and sometimes combined with large cardinals, we may mention the Measure Problem and the Borel Conjecture in measure theory, Kaplansky's Conjecture on Banach algebras, and Whitehead's Problem in group theory.

## 9. The search for new axioms

As a result of 50 years of development of the forcing technique, and its applications to many open problems in mathematics, there are now literally thousands of questions, in practically all areas of mathematics, that have been shown independent of ZFC. These include almost all questions about the structure of uncountable sets. One might say that the undecidability phenomenon is pervasive, to the point that the investigation of the uncountable has been rendered nearly impossible in ZFC alone (see however Shelah (1994) for remarkable exceptions).

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

A central theme of set theory is thus the search and classification of new axioms. These fall currently into two main types: the axioms of large 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\) is a
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 new
axiom. Such a cardinal is called *weakly inaccessible*. If, in
addition \(\kappa\) is a strong limit, i.e., \(2^\lambda <\kappa\), for
every cardinal \(\lambda <\kappa\), then \(\kappa\) is called
*strongly inaccessible*. A cardinal \(\kappa\) is strongly
inaccessible if and only if it is regular and \(V_\kappa \) is a model
of ZFC. If the GCH holds, then every weakly inaccessible cardinal is
strongly inaccessible.

Large cardinals are uncountable cardinals satisfying some properties that make them very large, and whose existence cannot be proved in ZFC. The first weakly inaccessible cardinal is just the smallest of all large cardinals. Beyond inaccessible cardinals there is a rich and complex variety of large cardinals, which form a linear hierarchy in terms of consistency strength, and in many cases also in terms of outright implication. See the entry on independence and large cardinals for more details.

To formulate the next stronger large-cardinal notion, let us say
that a subset \(C\) of an infinite cardinal \(\kappa\) is *closed*
if every limit of elements of \(C\) is also in \(C\); and is
*unbounded* if for every \(\alpha <\kappa\) there exists
\(\beta\in C\) greater than \(\alpha\). For example, the set of limit
ordinals less than \(\kappa\) is closed and unbounded. Also, a subset
\(S\) of \(\kappa\) is called *stationary* if it intersects every
closed unbounded subset of \(\kappa\). If \(\kappa\) is regular and
uncountable, then the set of all ordinals less than \(\kappa\) of
cofinality \(\omega\) is an example of a stationary set. A regular
cardinal \(\kappa\) is called *Mahlo* if the set of strongly
inaccessible cardinals smaller than \(\kappa\) is stationary. Thus, the
first Mahlo cardinal is much larger 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 strong
reflection properties. Recall that the Reflection Principle
(Section 4), which is provable in ZFC, asserts
that every *true* sentence (i.e., every sentence that holds in
\(V\)) is true in some \(V_\alpha\). A strengthening of this principle to
second-order sentences yields some large cardinals. For example,
\(\kappa\) is strongly inaccessible if and only if every \(\Sigma^1_1\)
sentence (i.e., existential second-order sentence in the language of
set theory, with one additional predicate symbol) true in the
structure \((V_\kappa ,\in, A)\), for any \(A\subseteq V_\kappa\), is true
in some \((V_\alpha ,\in ,A\cap V_\alpha)\), \(\alpha <\kappa\). The
same type of reflection, but now for \(\Pi^1_1\) sentences (i.e.,
universal second-order sentences), yields a much stronger large
cardinal property of \(\kappa\), called *weak compactness*. 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 even higher-order, sentences one
obtains large cardinal notions stronger than weak compactness.

The most famous large cardinals, called *measurable*, were
discovered by Stanisław Ulam in 1930 as a result of his solution
to the Measure Problem. A (two-valued) *measure*, or
*ultrafilter*, on a cardinal \(\kappa\) is a subset \(U\) of
\(\mathcal{P}(\kappa)\) that has the following properties: (i) the
intersection of two elements of \(U\) is in \(U\); (ii) if \(X\in U\) 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\) is called
*\(\kappa\)-complete* if every intersection of less than \(\kappa\)
elements of \(U\) is also in \(U\). And a measure is called
*non-principal* if there is no \(\alpha <\kappa\) that belongs
to all elements of \(U\). A cardinal \(\kappa\) is called
*measurable* if there exists a measure on \(\kappa\) that is
\(\kappa\)-complete and non-principal.

Measurable cardinals can be characterized by elementary embeddings
of the universe \(V\) into some transitive class \(M\). That such an
embedding \(j:V\to M\) is *elementary* 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\), the sentence
\(\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 that a cardinal
\(\kappa\) is measurable if and only if there exists an elementary
embedding \(j:V\to M\), with \(M\) transitive, so that \(\kappa\) is the
first ordinal moved by \(j\), i.e., the first ordinal such that
\(j(\kappa)\ne \kappa\). We say that \(\kappa\) is the *critical
point* of \(j\), and write \(crit(j)=\kappa\). The embedding \(j\) is
definable from a \(\kappa\)-complete non-principal measure on \(\kappa\),
using the so-called *ultrapower* construction. Conversely, if
\(j:V\to M\) is an elementary 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 called
*normal*.

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

If \(\kappa\) is measurable and \(j:V\to M\) is given by the ultrapower construction, then \(V_\kappa \subseteq M\), and every sequence of length less than or equal to \(\kappa\) of elements of \(M\) belongs to \(M\). Thus, \(M\) is quite similar to \(V\), but it cannot be \(V\) itself. Indeed, a famous theorem of Kenneth Kunen shows that there cannot be any elementary embedding \(j:V\to V\), other than the trivial one, i.e., the identity. All known proofs of this result use the Axiom of Choice, and it is an outstanding important question if the axiom is necessary. Kunen's Theorem opens the door to formulating large cardinal notions stronger than measurability by requiring that \(M\) is closer to \(V\).

For example, \(\kappa\) is called *strong* 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 is
supercompactness. A cardinal \(\kappa\) is *supercompact* if for
every \(\alpha\) there exists an elementary embedding \(j:V\to M\), with
\(M\) transitive and critical point \(\kappa\), so that
\(j(\kappa)>\alpha\) and every sequence of elements of \(M\) of length
\(\alpha\) belongs to \(M\).

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

Beyond supercompact cardinals we find the *extendible*
cardinals, the *huge*, the *super huge*, etc.

Kunen's theorem about the non-existence of a non-trivial elementary embedding \(j:V\to V\) actually shows that there cannot be an 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})\to L(V_{\lambda +1})\) different from the identity.

Large cardinals form a linear hierarchy of increasing consistency strength. In fact they are the stepping stones of the interpretability hierarchy of mathematical theories. See the entry on independence and large cardinals for more details. Given any sentence \(\varphi\), exactly one the following three possibilities holds about the theory ZFC plus \(\varphi\):

ZFC plus \(\varphi\) is inconsistent.

ZFC plus \(\varphi\) is equiconsistent with ZFC.

ZFC plus \(\varphi\) is equiconsistent with ZFC plus the existence of some large cardinal.

Thus, large cardinals can be used to prove that a given sentence \(\varphi\) does not imply another sentence \(\psi\), modulo ZFC, by showing that ZFC plus \(\psi\) implies the consistency of some large cardinal, whereas ZFC plus \(\varphi\) is consistent assuming the existence of a smaller large cardinal, or just assuming the consistency of ZFC. In other words, \(\psi\) has higher consistency strength than \(\varphi\), modulo ZFC. Then, by Gödel's second 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 large cardinals exist. But everything indicates that their existence not only cannot be disproved, but in fact the assumption of their existence is a very reasonable axiom of set theory. For one thing, there is a lot of evidence for their consistency, especially for those large cardinals for which it is possible to construct an inner model.

### 10.1 Inner models of large cardinals

An *inner model* of ZFC is a transitive proper class that
contains all the ordinals and satisfies all ZFC axioms. Thus, \(L\) is
the smallest inner model, while \(V\) is the largest. Some large
cardinals, such as inaccessible, Mahlo, or weakly-compact, may exist
in \(L\). That is, if \(\kappa\) has one of these large cardinal
properties, then it also has the property in \(L\). But some large
cardinals cannot exist in \(L\). Indeed, Scott (1961) showed that if
there exists a measurable cardinal \(\kappa\), then \(V\ne L\). It is
important 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 exist
there.

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 now using \(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 is canonical, in the sense that any other normal measure witnessing the measurability of \(\kappa\) would yield the same model, and has many of the properties of \(L\). For instance, it has a projective well ordering of the reals, and it satisfies the GCH.

Building similar \(L\)-like models for stronger large cardinals, such
as strong, or Woodin, is much harder. Those models are of the form
\(L[E]\), where \(E\) is a sequence of *extenders*, each extender
being a system of measures, that encode the relevant elementary
embeddings.

The largest \(L\)-like inner models for large cardinals that have
been obtained so far can contain Woodin limits of Woodin cardinals
(Neeman 2002). However, building an \(L\)-like model for a supercompact
cardinal is still a challenge. The supercompact barrier seems to be
the crucial one, for Woodin has shown that for a kind of \(L\)-like
inner model for a supercompact cardinal, which he calls the
*Ultimate-\(L\)*, all stronger large cardinals, such as
extendible, huge, I1, etc. would also exist in the model. The
construction of Ultimate-\(L\) is still incomplete, and it is not clear
yet that it will succeed, for it rests upon some technical hypotheses
that need to be confirmed.

### 10.2 Consequences of large cardinals

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

There are infinitely many Woodin cardinals.

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

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

Another area in which large cardinals play an important role is the
exponentiation of singular cardinals. The so-called *Singular
Cardinal Hypothesis* (SCH) completely determines the behavior of
the exponentiation for singular cardinals, modulo the exponentiation
for regular cardinals. The SCH follows from the GCH, and so it holds
in \(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 for
cardinals 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 the
existence of large cardinals it is possible to build a model of ZFC
where 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 SCH holds for all cardinals smaller than \(\aleph_{\omega_1}\), then
it also holds for \(\aleph_{\omega_1}\). Moreover, if the SCH holds for
all singular cardinals of countable cofinality, then it holds for all
singular cardinals (Silver).

## 11. Forcing axioms

Forcing axioms are axioms of set theory that assert that certain
existential statements are absolute between the universe \(V\) of all
sets and its (ideal) forcing extensions, i.e., some existential
statements that hold in some forcing extensions of \(V\) are already
true in \(V\). The first forcing axiom was formulated by Donald Martin
in the wake of the Solovay-Tennenbaum proof of the consistency of
Suslin's Hypothesis, and is now known as *Martin's Axiom*
(MA). Before we state it, let us say that a *partial ordering*
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 called *compatible* if there exists \(r\in P\) such that
\(r\leq p\) and \(r\leq q\). An *antichain* of \(P\) is a subset of
\(P\) whose elements are pairwise-incompatible. A partial ordering \(P\)
is called *ccc* if every antichain of \(P\) is countable. A
non-empty subset \(G\) of \(P\) is called a *filter* 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 called
*dense* if 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 <\omega_1\}\) of dense subsets of \(P\), there exists a filter \(G\subseteq P\) that is

genericfor the set, i.e., \(G\cap D_\alpha \ne {\varnothing}\), for all \(\alpha <\omega_1\).

Martin and Solovay (1970) proved that MA is consistent with ZFC, using iterated forcing with the ccc property. At first sight, MA may not look like an axiom, namely an obvious, or at least reasonable, assertion about sets, but rather like a technical statement about ccc partial orderings. It does look more natural, however, when expressed in topological terms, for it is simply a generalization of the well-known Baire Category Theorem, which asserts that in every compact Hausdorff topological space the intersection of countably-many dense open sets is non-empty. Indeed, MA is equivalent to:

In every compact Hausdorff ccc topological space, the intersection of \(\aleph_1\)-many dense open sets is non-empty.

MA has many different equivalent formulations and has been used very successfully to settle a large number of open problems in other areas of mathematics. For example, it implies Suslin's Hypothesis and that every \(\mathbf{\Sigma}^1_2\) set of reals is Lebesgue measurable and has the Baire property. It also implies the negation of the CH and that \(2^{\aleph_0}\) is a regular cardinal, but it does not decide what cardinal it is. See Fremlin (1984) for many more consequences of MA and other equivalent formulations. In spite of this, the status of MA as an axiom of set theory is still unclear. Perhaps the most natural formulation of MA, from a foundational point of view, is in terms of reflection. Writing HC for the set of hereditarily-countable sets (i.e., countable sets whose elements are countable, the elements of which are also countable, and so on), MA is equivalent to:

For every ccc partial ordering \(P\), if an existential statement about \(HC\) holds in an (ideal) generic extension of \(V\) obtained by forcing 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 on sets in \(HC\) exists in some (ideal) generic extension 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 in terms of so-called Boolean-valued models, which provide an alternative version of forcing.

Much stronger forcing axioms than MA were introduced in the 1980s,
such as J. Baumgartner's *Proper Forcing Axiom* (PFA), and the
stronger *Martin's Maximum* (MM) of Foreman, Magidor, and
Shelah (1988), which is essentially the strongest possible forcing
axiom. Both the PFA and MM are consistent relative to the existence of
a supercompact cardinal. The PFA asserts the same as MA, but for
partial orderings that have a property weaker than the ccc, called
*properness*, introduced by Shelah. And MM asserts the same for
the wider class of partial orderings that, when forcing with them, do
not destroy stationary subsets of \(\omega_1\).

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

## Bibliography

- Bagaria, J., 2008, “Set Theory”, in
*The Princeton Companion to Mathematics*, edited by Timothy Gowers; June Barrow-Green and Imre Leader, associate editors. Princeton: Princeton University Press. - Cohen, P.J., 1966,
*Set Theory and the Continuum Hypothesis*, 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 of Set Theory and its Role in Modern Mathematics*, Second revised edition, Basel: Birkhäuser. - Foreman, M., M. Magidor, and S. Shelah, 1988, “Martin's
maximum, saturated ideals and non-regular ultrafilters”, Part I,
*Annals of Mathematics*, 127: 1–47. - Fremlin, D.H., 1984, “Consequences of Martin's Axiom”,
*Cambridge tracts in Mathematics*#84. Cambridge: Cambridge University Press. - Gödel, K., 1931, “Über formal unentscheidbare
Sä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 axiom
of choice and of the generalized continuum hypothesis”,
*Proceedings of the National Academy of Sciences, U.S.A.*24: 556–557. - –––, 1986,
*Collected Works I. Publications 1929–1936*, S. Feferman et al. (eds.), Oxford: Oxford University Press. - Hauser, K., 2006, “Gödel's program revisited, Part I:
The turn to phenomenology”,
*Bulletin of Symbolic Logic*, 12(4): 529–590. - Jech, T., 2003,
*Set theory*, 3d Edition, New York: Springer. - Jensen, R.B., 1972, “The fine structure of the constructible
hierarchy”,
*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: Springer Verlag. - Kunen, K., 1980,
*Set Theory, An Introduction to Independence Proofs*, Amsterdam: North-Holland. - Levy, A., 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 Cohen
Extensions”,
*Annals of Mathematical Logic*, 2: 143–178. - Martin, D.A. and J.R. Steel, 1989, “A proof of projective
determinacy”,
*Journal of the American Mathematical Society*, 2(1): 71–125. - Mathias, A.R.D., 2001, “Slim models of Zermelo Set
Theory”,
*Journal of Symbolic Logic*, 66: 487–496. - Neeman, I., 2002, “Inner models in the region of a Woodin
limit of Woodin cardinals”,
*Annals of Pure and Applied Logic*, 116: 67–155. - Scott, D., 1961, “Measurable cardinals and constructible
sets”,
*Bulletin de l'Académie Polonaise des Sciences. Série des Sciences Mathématiques, Astronomiques et Physiques*, 9: 521–524. - Shelah, S., 1994, “Cardinal Arithmetic”,
*Oxford Logic Guides*, 29, New York: The Clarendon Press, Oxford University Press. - –––, 1998,
*Proper and improper forcing*, 2nd Edition, New York: Springer-Verlag. - Shelah, S. and W.H. Woodin, 1990, “Large cardinals imply
that every reasonably definable set of reals is Lebesgue
measurable”,
*Israel Journal of Mathematics*, 70(3): 381–394. - Solovay, R., 1970, “A model of set theory in which every set
of reals is Lebesgue measurable”,
*Annals of Mathematics*, 92: 1–56. - Solovay, R. and S. Tennenbaum, 1971, “Iterated Cohen
extensions and Souslin's problem”,
*Annals of Mathematics (2)*, 94: 201–245. - Todorcevic, S., 1989, “Partition Problems in
Topology”,
*Contemporary Mathematics*, Volume 84. American Mathematical Society. - Ulam, S., 1930, ‘Zur Masstheorie in der allgemeinen
Mengenlehre’,
*Fundamenta Mathematicae*, 16: 140–150. - Woodin, W.H., 1999,
*The Axiom of Determinacy, Forcing Axioms, and the Nonstationary Ideal*,*De Gruyter Series in Logic and Its Applications*1, Berlin-New York: Walter de Gruyter. - –––, 2001, “The Continuum Hypothesis, Part
I”,
*Notices of the AMS*, 48(6): 567–576, and “The Continuum Hypothesis, Part II”,*Notices of the AMS*48(7): 681–690. - Zeman, M., 2001,
*Inner Models and Large Cardinals*,*De Gruyter Series in Logic and Its Applications*5, Berlin-New York: Walter de Gruyter. - Zermelo, E., 1908, “Untersuchungen über die Grundlagen
der Mengenlehre, I”,
*Mathematische Annalen*65: 261–281. Reprinted in Zermelo 2010: 189–228, with a facing-page English translation, and an Introduction by Ulrich Felgner (2010). English translation also in van Heijenoort 1967: 201–215.

## Academic Tools

How to cite this entry. Preview the PDF version of this entry at the Friends of the SEP Society. Look up this entry topic at the Indiana Philosophy Ontology Project (InPhO). Enhanced bibliography for this entry at PhilPapers, with links to its database.

## Other Internet Resources

- Jech, Thomas, “Set Theory”,
*The Stanford Encyclopedia 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 the*Stanford Encyclopedia of Philosophy*— see the version history.] - Cantor's Attic, a website built by by Joel David Hamkins and Victoria Gitman, but community maintained.