|
Set theory is a branch of mathematics and computer science created principally by the German mathematician Georg Cantor
at the end of the 19th century. Initially controversial, set theory has
come to play the role of a foundational theory
in modern mathematics, in the sense of a theory invoked to justify assumptions made in mathematics concerning the existence of
mathematical objects (such as numbers or functions) and their properties. Formal versions of set theory also have a foundational
role to play as specifying a theoretical ideal of mathematical
rigor in proofs. At the same time the basic concepts of set theory are used throughout mathematics, the subject is pursued in
its own right as a speciality by a comparatively small group of mathematicians and logicians. It should be mentioned that there are also mathematicians using and promoting different approaches to the
foundations of mathematics.
The basic concepts of set theory are set and membership. A set is thought of as any
collection of objects, called the members (or elements) of the set. In mathematics, the members of sets are any
mathematical objects, and in particular can themselves be sets. Thus one speaks of the set N of natural numbers {0,1,2,3,4,...}, the set of real numbers, and the set of functions from the natural numbers to the natural numbers; but also, for example, of the set
{0,2,N} which has as members the numbers 0 and 2 and the set N.
Initially, what is now known as "naive" or "intuitive" set theory was developed. (See Naive set theory). As it turned out, assuming that one could perform any operations on sets without
restriction led to paradoxes such as Russell's paradox. To address these problems, set theory had to be re-constructed, this time using an
axiomatic approach.
The origins of rigorous set theory
The important idea of Cantor's, which got set theory going as a new field of study, was to define two sets A and
B to have the same number of members (the same cardinality)
when there is a way of pairing off members of A exhaustively with members of B. Then the set N
of natural numbers has the same cardinality as the set Q of rational numbers (they are both said to be countably
infinite), even though N is a proper subset of
Q. On the other hand, the set R of real numbers does not have the same cardinality as
N or Q, but a larger one (it is said to be uncountable). Cantor gave two proofs that R is not countable, and the second of these, using
what is known as the diagonal construction,
has been extraordinarily influential and has had manifold applications in logic and mathematics.
Cantor went right ahead and constructed infinite hierarchies of infinite sets, the ordinal and cardinal numbers. This was controversial in
his day, with the opposition led by the finitist Leopold Kronecker, but there is no significant disagreement among mathematicians today that Cantor
had the right idea.
Cantor's development of set theory was still "naïve" in the sense that he didn't have a precise axiomatization in mind. In retrospect, we can say that Cantor was tacitly using the axiom of extensionality, the axiom of infinity, and the axiom schema of (unrestricted) comprehension. However, the last of these leads directly
to Russell's paradox, by constructing the set
S := {A : A is not in A} of all sets that don't belong to themselves. (If
S belongs to itself, then it does not, giving a contradiction,
so S must not belong to itself. But then S must belong to itself, giving a final and absolute contradiction.)
Therefore, set theorists were forced to abandon either classical
logic or unrestricted comprehension, and the latter was far more reasonable to most. (Although intuitionism had a significant following, the paradox still goes through with intuitionistic logic. There is no paradox in Brazilian logic, but that was almost completely unknown at the time.)
In order to avoid this and similar paradoxes, Ernst Zermelo put forth
a system of axioms for set theory in 1908. He
included in this system the axiom of choice, a truly controversial
axiom that he needed to prove the well ordering theorem.
This system was later refined by Adolf Fraenkel and Thoralf Skolem, giving the axioms used today.
Axioms for set theory
The axioms for set theory now most often studied and used, although put in their final form by Skolem, are called the Zermelo-Fraenkel set theory (ZF). Actually, this term
usually excludes the axiom of choice, which was once more controversial than it is today. When this axiom is included, the
resulting system is called ZFC.
An important feature of ZFC is that every object that it deals with is a set. In particular, every element of a set is itself
a set. Other familiar mathematical objects, such as numbers, must be subsequently defined in terms of sets.
The ten axioms of ZFC are listed below. (Strictly speaking, the axioms of ZFC are just strings of logical symbols. What
follows should therefore be viewed only as an attempt to express the intended meaning of these axioms in English. Moreover, the
axiom of separation, along with the axiom of replacement, is actually an infinite schema of axioms, one for each formula.) Each
axiom has further information in its own article.
- Axiom of extensionality: Two sets are the same if
and only if they have the same elements.
- Axiom of empty set: There is a set with no elements. We
will use {} to denote this empty set.
- Axiom of pairing: If x, y are sets, then so
is {x,y}, a set containing x and y as its only elements.
- Axiom of union: For any set x, there is a set y
such that the elements of y are precisely the elements of the elements of x.
- Axiom of infinity: There exists a set x such that {}
is in x and whenever y is in x, so is the union y U {y}.
- Axiom of separation (or subset axiom): Given any set and
any proposition P(x), there is a subset of the original set containing precisely those elements x for which
P(x) holds.
- Axiom of replacement: Given any set and any mapping, formally defined as a proposition P(x,y)
where P(x,y) and P(x,z) implies y = z, there is a set containing precisely
the images of the original set's elements.
- Axiom of power set: Every set has a power set. That is, for any set x there exists a set y, such that the
elements of y are precisely the subsets of x.
- Axiom of regularity (or axiom of foundation): Every
non-empty set x contains some element y such that x and y are disjoint sets.
- Axiom of choice: (Zermelo's version) Given a set x of
mutually disjoint nonempty sets, there is a set y (a choice set for x) containing exactly one element
from each member of x.
The axioms of choice and regularity are still controversial today among a minority of mathematicians.
Independence in set theory
Many important statements are independent of ZFC. The independence is usually proved by forcing, that is it is shown that
every countable transitive model of ZFC (plus, occasionally, large cardinal axioms) can be expanded to satisfy the statement in
question, and (through a different expansion) its negation. An independence proof by forcing automatically proves independence
from arithmetical statements, other concrete statements, and large cardinal axioms. Some statements independent of ZFC can be
proven to hold in particular inner models, such as in the constructible universe. However, some statements that are true about constructible sets are
disproved by large cardinal axioms.
Here are some statements whose independence is provable by forcing:
Note: The Diamond Principle implies the Continuum Hypothesis and the negation of the Suslin Hypothesis.
The constructible universe satisfies the Generalized Continuum Hypothesis, the Diamond Principle, and the Kurepa Hypothesis.
Set theory foundations for mathematics
It is often asserted that axiomatic set theory is an adequate foundation for current mathematical practice, in the sense that in principle all proofs produced by the
mathematical community could be written formally in set theory terms. It is also generally believed that no serious advantage
would come from doing that, in almost all cases: the axiomatic foundations normally used are sufficiently closely aligned to the
underlying set theory, that full axiomatic translation yields only a little extra, compared to argument in the usual, traditional
informal style. One area where a gap can appear between practice and easy formalisation is in category theory, where for example a concept like 'the category of all categories' requires more
careful set-theoretic handling.
Objections to set theory
Since its inception, there have been some mathematicians who have objected to using set theory as a foundation for
mathematics, claiming that it is just a game which includes elements of fantasy. Notably, Henri Poincaré said "set theory is a disease from which mathematics will one day recover", [note that this
quote is part of the folklore of mathematics, but it's hard to find the original
quote] and Errett Bishop dismissed set theory as God's mathematics, which
we should leave for God to do.
The most frequent objection to set theory is based on the constructivist view that, loosely, mathematics has something to do
with computation. See mathematical
constructivism. On the other hand this is not really an objection to axiomatic set theory, as a formal theory. It is a comment on the naive
set theory that is being formalised, and its admission of non-computational elements.
See also
External link
For information on the history of the notation see
|