MathWithNaziaa : Set Theory

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:

I

 

n0

 

n2

 

n4

 

⋯

 

n2k

 

⋯

 

II

 

n1

 

n3

 

⋯

 

⋯

 

n2k+1

 

⋯

 

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.