# Set Theory

*First published Thu Jul 11, 2002*

Set Theory is the mathematical science of the infinite. It studies properties of sets, abstract objects that pervade the whole of modern mathematics. The language of set theory, in its simplicity, is sufficiently universal to formalize all mathematical concepts and thus set theory, along with Predicate Calculus, constitutes the true Foundations of Mathematics. As a mathematical theory, Set Theory possesses a rich internal structure, and its methods serve as a powerful tool for applications in many other fields of Mathematics. Set Theory, with its emphasis on consistency and independence proofs, provides a gauge for measuring the consistency strength of various mathematical statements. There are four main directions of current research in set theory, all intertwined and all aiming at the ultimate goal of the theory: to describe the structure of the mathematical universe. They are: inner models, independence proofs, large cardinals, and descriptive set theory. See the relevant sections in what follows.

- 1. The Essence of Set Theory
- 2. Origins of Set Theory
- 3. The Continuum Hypothesis
- 4. Axiomatic Set Theory
- 5. The Axiom of Choice
- 6. Inner Models
- 7. Independence Proofs
- 8. Large Cardinals
- 9. Descriptive Set Theory
- Bibliography
- Other Internet Resources
- Related Entries

## 1. The Essence of Set Theory

The objects of study of Set Theory are *sets*. As sets are
fundamental objects that can be used to define all other concepts in
mathematics, they are not defined in terms of more fundamental
concepts. Rather, sets are introduced either informally, and are
understood as something self-evident, or, as is now standard in modern
mathematics, axiomatically, and their properties are postulated by the
appropriate formal axioms.

The language of set theory is based on a single fundamental relation,
called *membership*. We say that *A* is a member of
*B* (in symbols *A*
∈ *B*),
or that the set *B* contains *A*
as its element. The understanding is that a set is determined by its
elements; in other words, two sets are deemed equal if they have
exactly the same elements. In practice, one considers sets of numbers,
sets of points, sets of functions, sets of some other sets and so
on. In theory, it is not necessary to distinguish between objects that
are members and objects that contain members -- the only objects one
needs for the theory are sets. See the supplement

Basic Set Theory

for further discussion.

Using the membership relation one can derive other concepts usually
associated with sets, such as unions and intersections of sets. For
example, a set *C* is the union of two sets *A* and
*B* if its members are exactly those objects that are either
members of *A* or members of *B*. The set *C* is
uniquely determined, because we have specified what its elements are.
There are more complicated operations on sets that can be defined in
the language of set theory (i.e. using only the relation
∈),
and we shall not
concern ourselves with those. Let us mention another operation: the
(unordered) *pair* {*A*,*B*} has as its elements
exactly the sets *A*and *B*. (If it happens that
*A*=*B*, then the “pair” has exactly one
member, and is called a *singleton* {*A*}.) By
combining the operations of union and pairing, one can produce from
any finite list of sets the set that contains these sets as members:
{*A,B,C,D,...,K,L,M*}. We also mention the *empty set*,
the set that has no elements. (The empty set is uniquely determined
by this property, as it is the only set that has no elements - this
is a consequence of the understanding that sets are determined by
their elements.)

When dealing with sets informally, such operations on sets are
self-evident; with the axiomatic approach, it is postulated that such
operations can be applied: for instance, one postulates that for any
sets *A* and *B*, the set {*A,B*} exists. In
order to endow set theory with sufficient expressive power one needs
to postulate more general construction principles than those alluded
to above. The guiding principle is that any objects that can be
singled out by means of the language can be collected into a set. For
instance, it is desirable to have the “set of all integers that
are divisible by number 3,” the “set of all straight lines
in the Euclidean plane that are parallel to a given line”, the
“set of all continuous real functions of two real variables”
etc. Thus one is tempted to postulate that given any property
*P*, there exists a set whose members are exactly all the sets
that have property *P*. As we shall see below, such an
assumption is logically inconsistent, and the accepted construction
principles are somewhat weaker than such a postulate.

One of the basic principles of set theory is the existence of an infinite set. The concept can be formulated precisely in the language of set theory, using only the membership relation, and the definition captures the accepted meaning of “infinite”. See the supplement on

Basic Set Theory

for further discussion. Using the basic construction principles, and
assuming the existence of infinite sets, one can *define*
numbers, including integers, real numbers and complex numbers, as
well as functions, functionals, geometric and topological concepts,
and all objects studied in mathematics. In this sense, set theory
serves as *Foundations of Mathematics*. The significance of
this is that all questions of provability (or unprovability) of
mathematical statements can be in principle reduced to formal
questions of formal derivability from the generally accepted axioms
of Set Theory.

While the fact that all of mathematics can be reduced to a formal system of set theory is significant, it would hardly be a justification for the study of set theory. It is the internal structure of the theory that makes it worthwhile, and it turns out that this internal structure is enormously complex and interesting. Moreover, the study of this structure leads to significant questions about the nature of the mathematical universe.

The fundamental concept in the theory of infinite sets is the
*cardinality* of a set. Two sets *A* and *B* have
the *same cardinality* if there exists a mapping from the set
*A* onto the set *B* which is *one-to-one*, that
is, it assigns each element of *A* exactly one element of
*B*. It is clear that when two sets are finite, then they have
the same cardinality if and only if they have the same number of
elements. One can extend the concept of the “number of
elements” to arbitrary, even infinite, sets. It is not apparent
at first that there might be infinite sets of different cardinalities,
but once this becomes clear, it follows quickly that the structure so
described is rich indeed.

## 2. Origins of Set Theory

The birth of Set Theory dates to 1873 when Georg Cantor proved the
uncountability of the real line. (One could even argue that the exact
birthdate is December 7, 1873, the date of Cantor's letter to
Dedekind informing him of his discovery.) Until then, no one
envisioned the possibility that infinities come in different sizes,
and moreover, mathematicians had no use for “actual
infinity.” The arguments using infinity, including the
Differential Calculus of Newton and Leibniz, do not require the use of
infinite sets, and infinity appears only as “a manner of
speaking”, to paraphrase Friedrich Gauss. The fact that the set
of all positive integers has a proper subset, like the set of squares
{1, 4, 9, 16, 25,...} of the same cardinality (using modern
terminology) was considered somewhat paradoxical (this had been
discussed at length by Galileo among others). Such apparent paradoxes
prevented Bernhard Bolzano in 1840s from developing set theory, even
though some of his ideas are precursors of Cantor's work. (It
should be mentioned that Bolzano, an accomplished mathematician
himself, coined the word *Menge* (= set) that Cantor used for
objects of his theory.)

Motivation for Cantor's discovery of Set Theory came from his
work on Fourier series (which led him to introduce *ordinal
numbers*) and on trancendental numbers. Real numbers that are
solutions of polynomial equations with integer coefficients are called
algebraic, and the search was on for numbers that are not algebraic. A
handful of these, called transcendental numbers, was discovered around
that time, and a question arose how rare such numbers are. What Cantor
did was to settle this question in an unexpected way, showing in one
fell swoop that transcendental numbers are plentiful indeed. His
famous proof went as follows: Let us call an infinite set *A*
*countable*, if its elements can be enumerated; in other words,
arranged in a sequence indexed by positive integers: *a*(1),
*a*(2), *a*(3), … , *a*(*n*),
… . Cantor observed that many infinite sets of numbers are
countable: the set of all integers, the set of all rational numbers,
and also the set of all algebraic numbers. Then he gave his ingeneous
diagonal argument that proves, by contradiction, that the set of all
real numbers is *not* countable. A consequence of this is that
there exists a multitude of transcendental numbers, even though the
proof, by contradiction, does not produce a single specific example.
See the supplement on

Basic Set Theory

for further discussion.

Cantor's discovery of uncountable sets led him to the subsequent development of ordinal and cardinal numbers, with their underlying order and arithmetic, as well as to a plethora of fundamental questions that begged to be answered (such as the Continuum Hypothesis). After Cantor, mathematics has never been the same.

## 3. The Continuum Hypothesis

As the Continuum Hypothesis has been the most famous problem in Set
Theory, let me explain what it says. The smallest infinite cardinal is
the cardinality of a countable set. The set of all integers is
countable, and so is the set of all rational numbers. On the other
hand, the set of all real numbers is uncountable, and its cardinal is
greater than the least infinite cardinal. A natural question arises:
is this cardinal (*the continuum*) the very next cardinal. In
other words, is it the case that there are no cardinals between the
countable and the continuum? As Cantor was unable to find any set of
real numbers whose cardinal lies strictly between the countable and
the continuum, he conjectured that the continuum is the next cardinal:
the Continuum Hypothesis. Cantor himself spent most of the rest of his
life trying to prove the Continuum Hypothesis and many other
mathematicians have tried too. One of these was David Hilbert, the
leading mathematician of the last decades of the 19th century. At the
World Congress of Mathematicians in Paris in 1900 Hilbert presented a
list of major unsolved problems of the time, and the Continuum
Hypothesis was the very first problem on Hilbert's list.

Despite the effort of a number of mathematicians, the problem remained unsolved until 1963, and it can be argued that in some sense the problem is still unsolved. See Section 7 on Independence Proofs.

## 4. Axiomatic Set Theory

In the years following Cantor's discoveries, development of Set
Theory proceeded with no particular concern about how exactly sets
should be defined. Cantor's informal
“definition”
was sufficient for proofs in the new theory, and the understanding was
that the theory can be formalized by rephrasing the informal definition as a
*system of axioms*. In the early 1900s it became clear
that one has to state precisely what basic assumptions are made in Set
Theory; in other words, the need has arisen to axiomatize Set
Theory. This was done by Ernst Zermelo, and the immediate reasons for
his axioms were twofold. The first one was the discovery of a paradox
in Set Theory. This paradox is referred to as *Russell's
Paradox.* Consider the “set” *S* of all sets that
are not an element of itself. If one accepts the principle that all such sets
can be collected into a set, then *S*
should be a set. It is easy to see however that this leads to a
contradiction (is the set *S* an element of itself?)

Russell's Paradox can be avoided by a careful choice of construction principles, so that one has the expressive power needed for usual mathematical arguments while preventing the existence of paradoxical sets. See the supplement on

Zermelo-Fraenkel Set Theory

for further discussion. The price one has to pay for avoiding inconsistency is that some “sets” do not exist. For instance, there exists no “universal” set (the set of all sets), no set of all cardinal numbers, etc.

The other reason for axioms was more subtle. In the course of
development of Cantor's theory of cardinal and ordinal numbers a
question was raised whether every set can be provided with a certain
structure, called *well-ordering* of the set. Zermelo proved
that indeed every set can be well-ordered, but only after he
introduced a new axiom that did not seem to follow from the other,
more self-evident, principles. His *Axiom of Choice* has become
a standard tool of modern mathematics, but not without numerous
objections of some mathematicians and discussions in both mathematical
and philosophical literature. The history of the Axiom of Choice bears
strong resemblance to that of the other notorious axiom,
Euclid's Fifth Postulate.

## 5. The Axiom of Choice

The Axiom of Choice states that for every set of mutually disjoint
nonempty sets there exists a set that has exactly one member common
with each of these sets. For instance, let *S* be a set whose
members are mutually disjoint finite sets of real numbers. We can
*choose* in each *X*
∈ *S*
the smallest number, and thus form a set that
has exactly one member in common with each
*X* ∈ *S*.
What is not self-evident is whether we can make a choice every time,
simultaneously for infinitely many sets *X*, regardless what
these abstract sets are. The Axiom of Choice, which postulates the
existence of a certain set (*the choice set*) without giving
specific instructions how to construct such a set, is of different
nature than the other axioms, which all formulate certain
construction principles for sets. It was this nonconstructive nature
of the Axiom of Choice that fed the controversy for years to come.

An interesting application of the Axiom of Choice is the
Banach-Tarski Paradox that states that the unit ball can be
partitioned into a finite number of disjoint sets which then can be
rearranged to form *two* unit balls. This is of course a
paradox only when we insist on visualizing abstract sets as something
that exists in the physical world. The sets used in the Banach-Tarski
Paradox are not physical objects, even though they do exist in the
sense that their existence is proved from the axioms of mathematics
(including the Axiom of Choice).

The legitimate question is whether the Axiom of Choice is consistent, that is whether it cannot be refuted from the other axioms. (Notice the similarity with the non Euclidean geometry.) This question was answered by Gödel, and eventually the role of the Axiom of Choice has been completely clarified. See Section 7 on Independence Proofs.

## 6. Inner Models

In the 1930s, Gödel stunned the mathematical world by discovering that mathematics is incomplete. His Incompleteness Theorem states that every axiomatic system that purports to describe mathematics as we know it must be incomplete, in the sense that one can find a true statement expressible in the system that cannot be formally proved from the axioms. In view of this result one must consider the possibility that a mathematical conjecture that resists a proof might be an example of such an unprovable statement, and Gödel immediately embarked on the project of showing that the Continuum Hypothesis might be undecidable in the axiomatic set theory.

Several years after proving the Incompleteness Theorem, Gödel proved another groundbreaking result: he showed that both the Axiom of Choice and the Continuum Hypothesis are consistent with the axioms of set theory, that is that neither can be refuted by using those axioms. This he achieved by discovering a model of set theory in which both the Axiom of Choice and the Continuum Hypothesis are true.

Gödel's model *L* of “constructible sets”
has since served as a blueprint for building so-called *inner
models*. These models form a hierarchy, corresponding to the
hierarchy of large cardinals (see
Section 8),
and provide a glimpse into the as yet hidden structure of the
mathematical universe. The advances in Inner Model Theory that have
been made in the recent past owe much to the work of Ronald Jensen
who introduced the study of the fine structure of constructible
sets.

## 7. Independence Proofs

In 1963, Paul Cohen proved independence of the Axiom of Choice and of
the Continuum Hypothesis. This he did by applying the *method of
forcing* that he invented and constructing first a model of set
theory (with the axiom of choice) in which the Continuum Hypothesis
fails, and then a model of set theory in which the Axiom of Choice
fails. Together with Gödel's models, these models show that
the Axiom of Choice can neither be proved nor refuted from the other
axioms, and that the Continuum Hypothesis can neither be proved nor
refuted from the axioms of set theory (including the Axiom of
Choice).

Cohen's method proved extremely fruitful and led first to the solution of a number of outstanding problems (Suslin's Problem, the Lebesgue measurability Problem, Borel's Conjecture, Kaplansky's Conjecture, Whitehead's Problem and so on) and soon has become one of the cornerstones of modern set theory. The technique of forcing has to date been applied by hundreds of authors of numerous articles and has enormously advanced our knowledge of Foundations of Mathematics. Along with the theory of large cardinals it is used to gauge the consistency strength of mathematical statements.

## 8. Large Cardinals

In 1930, while working on the Measure Problem, Stanislaw Ulam
discovered an important phenomenon: Assuming that a certain
mathematical statement about “small sets” (such as sets of
real numbers) is true, one can prove the existence of sets of enormous
size (*inaccessible*). This phenomenon has become more apparent
after Dana Scott's celebrated result (1961) that measurable
cardinals do not exist in *L*. Suddenly, large cardinals such
as inaccessible, measurable, supercompact etc. have become the main
focus of attention of set theorists. What emerged is a hierarchy of
properties of infinite sets, the Large Cardinal Theory, that appears
to be the basis for the structure of the set theoretical
universe. Large cardinal axioms (also referred to as axioms of
*strong infinity*) form a hierarchy whereby a stronger axiom
not only implies a weaker axiom but also proves its consistency. To
date there are scores of examples of mathematical statements whose
consistency strength can be precisely calculated in terms of the
hierarchy of large cardinals. (For instance, a negative solution of the
Singular Cardinal Problem corresponds to a large cardinal axiom
between measurabily and supercompactness.)

Since the pioneering work of Ronald Jensen, Large Cardinal Theory has been closely tied with Inner Model Theory. It turns out that for each large cardinal axiom at lower levels of the hierarchy one can find an appropriate inner model. These inner models shed additional light on the structure of the universe by employing methods of Descriptive Set Theory.

## 9. Descriptive Set Theory

Descriptive Set Theory traces its origins to the theory of
integration by Henri Lebesgue at the beginning of 20th
century. Investigations into Borel sets of real numbers led to the
theory of *projective* sets, and more generally, the theory of
definable sets of real numbers. Following Gödel's work, it
became apparent that many natural questions in Descriptive Set Theory
are undecidable in axiomatic set theory. This was further confirmed by
a proliferation of independence results following Cohen's
invention of the forcing method.

Modern Descriptive Set Theory revolves mostly around the powerful
method using infinite games. The branch of Descriptive Set Theory
known as *Determinateness*, developed by D. A. Martin, Robert
Solovay and others, brought together methods of, among others,
Recursion Theory and Large Cardinal Theory and has been very
successful in describing the structure of definable sets. More
importantly, Descriptive Set Theory provides strong evidence for the
large cardinal axioms.

## Bibliography

- Cantor, G., 1932,
*Gesammelte Abhandlungen*, Berlin: Springer-Verlag. - Ulam, S., 1930, ‘Zur Masstheorie in der allgemeinen
Mengenlehre’,
*Fund. Math.*, 16, 140-150. - Gödel, K., 1940, ‘The consistency of the axiom of choice and
the generalized continuum hypothesis’,
*Ann. Math. Studies*, 3. - Scott, D., 1961, ‘Measurable cardinals and constructible sets’,
*Bull. Acad. Pol. Sci.*, 9, 521-524. - Cohen, P., 1966,
*Set theory and the continuum hypothesis*, New York: Benjamin. - Jensen, R., 1972, ‘The fine structure of the constructible
hierarchy’,
*Ann. Math. Logic*, 4, 229-308. - Martin, D. and Steel, J., 1989, ‘A proof of projective
determinacy’,
*J. Amer. Math. Soc.*, 2, 71-125. - Hrbacek, K. and Jech, T., 1999,
*Introduction to Set Theory*, New York: Marcel Dekker, Inc.

## Other Internet Resources

- Set Theory, maintained by Jean Larson (Mathematics, University of Florida)
- Articles by J.J. O'Connor and E.F. Robertson,
in
*The MacTutor History of Mathematics*archive, (Mathematics, University of St. Andrews): - A Homepage for the Axiom of Choice, maintained by Eric Schechter (Mathematics, Vanderbilt University)
- Gödel's Incompleteness Theorem, maintained by Dale Myers (Mathematics, University of Hawaii)

[Please contact the author with suggestions.]

## Related Entries

Frege, Gottlob: logic, theorem, and foundations for arithmetic | logic: classical | proof theory | Russell's paradox