Set Theory
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 one 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.
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 N
of natural numbers and the set 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 N,
or has the same cardinality as 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.
The axioms of set theory
ZFC is an axiom system formulated in first-order logic with equality and
with only one binary relation symbol ∈
for membership. Thus, we write A∈B
to express that A
is a member of the set B
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 ∅
· 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 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 ⋃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 ∅
and such that if A∈Z,
then ⋃{A,{A}}∈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 φ
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 φ
· .
· 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 ∈-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 ∈
one normally uses for convenience other auxiliary defined symbols. For
example, A⊆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∪B,
which denotes the union of A
and B,
i.e., the set whose elements are those of A
and B;
or A∩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×B
is defined as the set of all ordered pairs (C,D)
such that C∈A
and D∈B.
Given any formula φ(x,y1,…,yn),
and sets A,B1,…,Bn,
one can form the set of all those elements of A
that satisfy the formula φ(x,B1,…,Bn).
This set is denoted by {a∈A:φ(a,B1,…,Bn)}.
In ZF one can easily prove that all these sets exist.
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 ∅
. Given an ordinal α,
its immediate successor, denoted by α+1,
is the set α∪{α}.
And given a non-empty set X
of ordinals such that for every α∈X
the successor α+1
is also in X,
one obtains the limit ordinal ⋃X.
One shows that every ordinal is (strictly) well-ordered by ∈,
i.e., it is linearly ordered by ∈
and there is no infinite ∈
-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 (ω).
In ZFC, one identifies the finite ordinals with the natural numbers. Thus, ∅=0,
{∅}=1,
{∅,{∅}}=2,
etc., hence ω
is just the set N
of natural numbers.
One can extend the operations of addition and multiplication of natural
numbers to all the ordinals. For example, the ordinal α+β
is the order-type of the well-ordering obtained by
concatenating a well-ordered set of order-type α
and a well-ordered set of order-type β.
The sequence of ordinals, well-ordered by ∈
, starts as follows
0, 1, 2,…, n
,…, ω,
ω+1,
ω+2,…,
ω+ω,…,
ω⋅n,
…, ω⋅ω,…,
ωn,
…, ωω
, …
The ordinals satisfy the principle of transfinite induction:
suppose that C
is a class of ordinals such that whenever C
contains all ordinals β
smaller than some ordinal α,
then α
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→V,
one can define a class-function F:ON→V
such that F(α)
is the value of the function G
applied to the function F
restricted to α
. 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 ω
. All the ordinals displayed above are either finite or countable. But the
set of all finite and countable ordinals is also an ordinal, called ω1,
and is not countable. Similarly, the set of all ordinals that are bijectable
with some ordinal less than or equal to ω1
is also an ordinal, called ω2,
and is not bijectable with ω1,
and so on.
Cardinals
A cardinal is an ordinal that is not bijectable with any smaller
ordinal. Thus, every finite ordinal is a cardinal, and ω
, ω1,
ω2,
etc. are also cardinals. The infinite cardinals are represented by the letter
aleph (ℵ
) of the Hebrew alphabet, and their sequence is indexed by the ordinals. It
starts like this
ℵ0
, ℵ1,
ℵ2,
…, ℵω,
ℵω+1,
…, ℵω+ω,
…, ℵω2,
…, ℵωω,
…, ℵω1,
…, ℵω2
, …
Thus, ω=ℵ0
, ω1=ℵ1,
ω2=ℵ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 κ
is called regular if it is
not the union of less than κ
smaller cardinals. Thus, ℵ0
is regular, and so are all infinite successor cardinals, such as ℵ1.
Non-regular infinite cardinals are called singular. The
first singular cardinal is ℵω,
as it is the union of countably-many smaller cardinals, namely ℵω=⋃n<ωℵn
.
The cofinality of a cardinal κ
, denoted by cf(κ)
is the smallest cardinal λ
such that κ
is the union of λ-many
smaller ordinals. Thus, cf(ℵω)=ℵ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 κ
and λ,
the sum κ+λ
is defined as the cardinality of the set consisting of the union of any two
disjoint sets, one of cardinality κ
and one of cardinality λ.
And the product κ⋅λ
is defined as the cardinality of the Cartesian product κ×λ.
The operations of sum and product of infinite cardinals are trivial, for if κ
and λ
are infinite cardinals, then κ+λ=κ⋅λ=maximum{κ,λ}
.
In contrast, cardinal exponentiation is highly non-trivial, for even the
value of the simplest non-trivial infinite exponential, namely 2ℵ0
, is not known and cannot be determined in ZFC (see below).
The cardinal κλ
is defined as the cardinality of the Cartesian product of λ
copies of κ;
equivalently, as the cardinality of the set of all functions from λ
into κ.
König’s theorem asserts that κcf(κ)>κ,
which implies that the cofinality of the cardinal 2ℵ0,
whatever that cardinal is, must be uncountable. But this is essentially all
that ZFC can prove about the value of the exponential 2ℵ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 ℵω
is a strong limit, that is, 2ℵn<ℵω,
for every n<ω,
then 2ℵω<ℵω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.
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 α
the set Vα
, given as follows:
·
V0=∅
· · Vα+1=P(Vα)
· · Vα=⋃β<αVβ
, whenever α
·
is a limit ordinal.
The Power Set axiom is used to obtain Vα+1
from Vα.
Replacement and Union allow one to form Vα
for α a
limit ordinal. Indeed, consider the function that assigns to each β<α
the set Vβ.
By Replacement, the collection of all the Vβ,
for β<α,
is a set, hence the Union axiom applied to that set yields Vα.
The axiom of Infinity is needed to prove the existence of ω
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α,
for some ordinal α.
Thus, ZF proves that the set theoretic universe, denoted by V,
is the union of all the Vα,
α
an ordinal.
The proper class V
, together with the ∈
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 important property of V
is the so-called Reflection Principle.
Namely, for each formula φ(x1,…,xn),
ZFC proves that there exists some Vα
that reflects it, that is, for every a1,…,an∈Vα
,
φ(a1,…,an)
holds in V
if and only if φ(a1,…,an)
holds in Vα
.
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α.
In particular, ZFC is not finitely axiomatizable, for otherwise ZFC would prove
that, for unboundedly many ordinals α,
Vα
is a model of ZFC, contradicting Gödel’s second incompleteness theorem
The Reflection Principle encapsulates the essence of ZF set theory, for as
shown by Levy (1960), the axioms of Extensionality, Separation, and Foundation,
together with the Reflection Principle, formulated as the axiom schema
asserting that each formula is reflected by some set that contains all elements
and all subsets of its elements (note that the Vα
are like this), is equivalent to ZF.
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 N=ω
. The set of integers Z
may be defined as the set of equivalence classes of pairs of natural numbers
under the equivalence relation (n,m)≡(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 Z
(see Enderton (1977) for details, and Levy (1979) for a different
construction). Further, one may define the rationals Q
as the set of equivalence classes of pairs (n,m)
of integers, where m≠0,
under the equivalence relation (n,m)≡(n′,m′)
if and only if n⋅m′=m⋅n′.
Again, the operations +
and ⋅
on Z
may be extended naturally to Q.
Moreover, the ordering ≤Q
on the rationals is given by: r≤Qs
if and only if there exists t∈Q
such that s=r+t.
The real numbers may be defined as Dedekind cuts of Q,
namely, a real number is given by a pair (A,B)
of non-empty disjoint sets such that A∪B=Q,
and a≤Qb
for every a∈A
and b∈B.
One can then extend again the operations of +
and ⋅
on Q,
as well as the ordering ≤Q,
to the set of real numbers 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 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
(a1,…,an)
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
((a1,…,an),b)
such that b
is the value of f
on (a1,…,am).
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∈A,
and for every a∈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 τ
on it, i.e., τ
is a subset of P(X)
containing X
and ∅
, 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.
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.
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 ∈
is interpreted as E.
Thus, if φ
is a sentence of the language of set theory and one can find a model of ZFC in
which φ
holds, then its negation ¬φ
cannot be proved in ZFC. Hence, if one can find a model of φ
and also a model of ¬φ,
then φ
is neither provable nor disprovable in ZFC, in which case we say that φ
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 φ
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 φ
is true. We shall see several examples in the next sections.
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 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.
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 Rn
and other Polish spaces
(i.e., topological spaces that are homeomorphic to a separable complete metric
space), such as the Baire space N
of all functions f:N→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 nonempty 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 Σ11
, are the continuous images of Borel sets. And the co-analytic, or Π11
, 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 R×N
to R)
and complementation, one obtains the projective sets.
The projective sets form a hierarchy of increasing complexity. For example, if A⊆R×N
is co-analytic, then the projection {x∈R:∃y∈N((x,y)∈A)}
is a projective set in the next level of complexity above the co-analytic sets.
Those sets are called Σ12,
and their complements are called Π12
.
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
R=(R,+,⋅,Z).
That is, there is a first-order formula φ(x,y1,…,yn)
in the language for the structure such that for some r1,…,rn∈R
,
A={x∈R:R⊨φ(x,r1,…,rn)}.
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, ℵ1
, is a large cardinal in the constructible universe L
namely a so-called inaccessible cardinal 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 Σ12
set that is not Lebesgue measurable and does not have the Baire property,
whereas if Martin’s axiom holds. 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 (in fact, it follows from the existence 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.
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 N
. Recall that the elements of N
are functions f:N→N,
that is, sequences of natural numbers of length ω.
The space N
is topologically equivalent (i.e., homeomorphic) to the set of irrational
points of R.
So, since we are interested in the regularity properties of subsets of R,
and since countable sets, such as the set of rationals, are negligible in terms
of those properties, we may as well work with N,
instead of R
.
Given A⊆N
, the game associated
to A,
denoted by GA,
has two players, I and II, who play alternatively ni∈N:
I plays n0,
then II plays n1,
then I plays n2,
and so on. So, at stage 2k,
player I plays n2k
and at stage 2k+1,
player II plays n2k+1
. We may visualize a run of the game as follows:
After infinitely many moves, the two players produce an infinite sequence n0,n1,n2,…
of natural numbers. Player I wins the game if the sequence
belongs to A
. Otherwise, player II wins.
The game GA
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 σ
from the set of finite sequences of natural numbers into N,
such that if the player plays according to this function, i.e., she plays σ(n0,…,n2k)
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 N
is determined if and only if the game GA
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 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 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, ADL(R),
asserts that the AD holds in L(R),
which is the least transitive class that contains all the ordinals and all the
real numbers, and satisfies the ZF axioms So, ADL(R)
implies that every set of reals that belongs to L(R)
is regular. Also, since L(R)
contains all projective sets, ADL(R)
implies PD.
The Continuum Hypothesis
The Continuum Hypothesis (CH), formulated by Cantor in 1878, asserts that
every infinite set of real numbers has cardinality either ℵ0
or the same cardinality as R.
Thus, the CH is equivalent to 2ℵ0=ℵ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 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.
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α
to obtain Vα+1,
one only takes those subsets of Lα
that are definable in Lα,
using elements of Lα
as parameters. Thus, letting PDef(X)
to denote the set of all the subsets of X
that are definable in the structure (X,∈)
by a formula of the language of set theory, using elements of X
as parameters of the definition, we let
·
L0=∅
· · Lα+1=PDef(Lα)
· · Lλ=⋃α<λLα
, whenever λ
·
is a limit ordinal.
Then L
is the union of all the Lα,
for α
an ordinal, i.e., L=⋃α∈ONLα
.
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ℵα=ℵα+1,
for every ordinal α
.
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 ∈
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 ∅.
The resulting model, L(A),
need not be however a model of the AC. One very important such model is L(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 (♢)
and square (□),
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(R)
or the inner models for large cardinals
Forcing
In 1963, twenty-five years after Gödel’s proof of the consistency of the CH
and the AC, relative to the consistency of ZF, Paul Cohen (1966) proved the
consistency of the negation of the CH, and also of the negation of the AC,
relative to the consistency of ZF. Thus, if ZF is consistent, then the CH is
undecidable in ZFC, and the AC is undecidable in ZF. To achieve this, Cohen
devised a new and extremely powerful technique, called forcing, for
expanding countable transitive models of ZF.
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 ω.
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 P(ω)
is uncountable, there are plenty of subsets of ω
that do not belong to M.
But, unfortunately, we cannot just pick any infinite subset r
of ω
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α(r),
where α 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 P
that belongs to M.
In the above example, P
would be the set of all finite increasing sequences of natural numbers, seen as
finite approximations to the infinite sequence r,
ordered by ⊆;
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 ℵ2
new subsets of ω,
so that in the generic extension the CH fails. In this case one needs to use an
appropriate partial ordering P
so that the ℵ2
of M
is not collapsed, i.e., it is the same as
the ℵ2
of the generic extension, and thus the generic extension M[G]
will satisfy the sentence that says that there are ℵ2
real numbers.
