Kurt G?del (1906–1978), with his work on

the constructible universe L, established

the relative consistency of the Axiom of

Choice and the Continuum Hypothesis.

More broadly, he secured the cumulative

hierarchy view of the universe of sets and ensured

the ascendancy of first-order logic as the framework

for set theory. G?del thereby transformed set theory and launched it with structured subject matter and specific methods of proof as a distinctive

field of mathematics. What follows is a survey of

prior developments in set theory and logic intended to set the stage, an account of how G?del

marshaled the ideas and constructions to formulate L and establish his results, and a description

of subsequent developments in set theory that resonated with his speculations. The survey trots out

in quick succession the groundbreaking work at the

beginning of a young subject.

Numbers, Types, and Well-Ordering

Set theory was born on that day in December 1873

when Georg Cantor (1845–1918) established that

the continuum is not countable: There is no bijection between the natural numbers

N = {0, 1, 2, 3,... } and the real numbers R, since

for any (countable) sequence of reals one can specify nested intervals so that any real in the intersection will not be in the sequence. Cantor soon investigated ways to define bijections between sets

of reals and the like. He stipulated that two sets

have the same power if there is a bijection between

them, and, implicitly at first, that one set has a

higher power than another if there is an injection

of the latter into the first but no bijection. In an

1878 publication he showed that R, the plane R × R,

and generally Rn are all of the same power, but

there were still only the two infinite powers as set

out by his 1873 proof. At the end of the publication Cantor asserted a dichotomy:

Every infinite set of real numbers either is countable or has the power of the

continuum.

This was the Continuum Hypothesis (CH) in its

nascent context, and the continuum problem, to resolve this hypothesis, would become a major motivation for Cantor’s large-scale investigations of

infinite numbers and sets.

In his Grundlagen of 1883, Cantor developed the

transfinite numbers and the key concept of wellordering. The progression of transfinite numbers

could be depicted, in his later notation, in terms

of natural extensions of arithmetical operations:

0, 1, 2, . . .ω,ω + 1,ω + 2,...ω + ω(= ω·2),

...ω·3,...ω·ω(= ω2),...ω3,...ωω,...

A relation ? is a well-ordering of a set if and only

if it is a strict linear ordering of the set such that

every nonempty subset has a ?-least element. Wellorderings carry the sense of sequential counting,

and the transfinite numbers serve as standards

for gauging well-orderings. Cantor called the set of

natural numbers N the first number class (I) and

Juliet Floyd is professor of philosophy at Boston University.

Her email address is jfloyd@bu.edu.

Akihiro Kanamori is professor of mathematics at Boston

University. His email address is aki@math.bu.edu.

418 NOTICES OF THE AMS VOLUME 53, NUMBER 4

the set of numbers whose predecessors are in bijective correspondence with (I) the second number

class (II). The infinite numbers in the above display

are all in (II). Cantor conceived of (II) as bounded

above and showed that (II) itself is not countable.

Proceeding upward, Cantor called the set of numbers whose predecessors are in bijective correspondence with (II) the third number class (III),

and so on. Cantor then propounded a basic principle in the Grundlagen:

“It is always possible to bring any welldefined set into the form of a wellordered set.”

Sets are to be well-ordered and thus to be gauged

by his numbers and number classes. With this

framework Cantor had transformed CH into the

positive assertion that (II) and R have the same

power. However, an emerging problem for Cantor

was that he could not even define a well-ordering

of R; the continuum, at the heart of mathematics,

could not be easily brought into the fold of the

transfinite numbers.

Almost two decades after his initial 1873 proof,

Cantor in 1891 came to his celebrated diagonal argument. In various guises the argument would become fundamental in mathematical logic. Cantor

himself proceeded in terms of functions, ushering

collections of arbitrary functions into mathematics, but we cast his result as is done nowadays in

terms of the power set P(x) = {y | y ? x} of a set

x. For any set x, P(x) has a higher power than x.

First, the function associating each a ∈ x with

{a} is an injection: x → P(x). Suppose now that F

is any function: x → P(x). Consider the “diagonal”

set d = {a ∈ x | a /∈ F(a)}. If d itself were a value

of F, say d = F(b), then we would have the contradiction: b ∈ d if and only if b /∈ d. Hence, F cannot

be surjective.

Cantor had been shifting his notion of set to a

level of abstraction beyond sets of real numbers

and the like; the diagonal argument can be drawn

out of the earlier argument, and the new result generalized the old since P(N) and R have the same

power. The new result showed for the first time that

there is a set of a higher power than R, e.g. P(P(N)).

Cantor’s Beitr?ge of 1895 and 1897 presented

his mature theory of the transfinite. Cantor reconstrued power as cardinal number, now an autonomous concept beyond une fa?on de parler

about bijective correspondence. He defined the addition, multiplication, and exponentiation of cardinal numbers primordially in terms of set-theoretic operations and functions. As befits the

introduction of new numbers Cantor then introduced a new notation, one using the Hebrew letter

aleph, ?. ?0 is to be the cardinal number of N and

the successive alephs

?0,?1,?2,...,?α,...

are now to be the cardinal numbers of the successive number classes from the Grundlagen and thus

to exhaust all the infinite cardinal numbers. Cantor pointed out that 2?0 is the cardinal number of

R, but frustrated in his efforts to establish CH he

did not even mention the hypothesis, which could

now have been stated as 2?0 = ?1 . Every well-ordered set has an aleph as its cardinal number, but

where is 2?0 in the aleph sequence?

CH was thus embedded in the very interstices

of the beginnings of set theory. The structures that

Cantor built, while now of great intrinsic interest,

emerged largely out of efforts to articulate and establish it. The continuum problem was made the

very first in David Hilbert’s famous list of 23 problems at the 1900 International Congress of Mathematicians; Hilbert drew out Cantor’s difficulty by

suggesting the desirability of “actually giving” a

well-ordering of R.

Bertrand Russell (1872–1970), a main architect

of the analytic tradition in philosophy, focused in

1900 on Cantor’s work. Russell was pivoting from

idealism toward a realism about propositions and

with it logicism, the thesis that mathematics can

be founded in logic. Taking a universalist approach

to logic with all-encompassing categories, Russell

took the class of all classes to have the largest cardinal number but saw that Cantor’s 1891 result

leading to higher cardinal numbers presented a

problem. Analyzing that argument, by the spring

of 1901 he came to the famous Russell’s Paradox,

a surprisingly simple counterexample to full comprehension, the assertion that for every property

A(x) the collection of objects having that property, the class {x | A(x)}, is also an object. Consider

Russell’s {x | x /∈ x}. If this were an object r , then

we would have the contradiction r ∈ r if and only

if r /∈ r. Gottlob Frege (1848-1925) was the first to

systematize quantificational logic in a formalized

language, and he aimed to establish a purely logical foundation for arithmetic. Russell famously

communicated his paradox to Frege in 1902, who

immediately saw that it revealed a contradiction

within his mature logical system.

Russell’s own reaction was to build a complex

logical structure, one used later to develop mathematics in Whitehead and Russell’s 1910-3 Principia

Mathematica. Russell’s ramified theory of types is

a scheme of logical definitions based on orders

and types indexed by the natural numbers. Russell

proceeded “intensionally”; he conceived this

scheme as a classification of propositions based on

the notion of propositional function, a notion not

reducible to membership (extensionality). Proceeding in modern fashion, we may say that the universe of the Principia consists of objects stratified

into disjoint types Tn, where T0 consists of the individuals, Tn+1 ? {Y | Y ? Tn}, and the types Tn for

n > 0 are further ramified into orders Oi

n with

APRIL 2006 NOTICES OF THE AMS 419

Tn =

i Oi

n. An object in Oi

n is to be defined either

in terms of individuals or of objects in some fixed

Oj

m for some j<i and m ≤ n, the definitions allowing for quantification only over Oj

m. This precludes Russell’s Paradox and other “vicious circles”, as objects consist only of previous objects

and are built up through definitions referring only

to previous stages. However, in this system it is impossible to quantify over all objects in a type Tn,

and this makes the formulation of numerous mathematical propositions at best cumbersome and at

worst impossible. Russell was led to introduce his

Axiom of Reducibility, which asserts that for each

object there is a predicative object consisting of exactly the same objects, where an object is predicative if its order is the least greater than that of its

constituents. This axiom reduced consideration to

individuals, predicative objects consisting of individuals, predicative objects consisting of predicative objects consisting of individuals, and so on—

the simple theory of types. In traumatic reaction to

his paradox Russell had built a complex system of

orders and types only to collapse it with his Axiom

of Reducibility, a fearful symmetry imposed by an

artful dodger.

Ernst Zermelo (1871–1953) made his major advances in set theory in the first decade of the new

century. Zermelo’s first substantial result was his

independent discovery of the argument for Russell’s

Paradox. He then established in 1904 the WellOrdering Theorem, that every set can be wellordered, assuming what he soon called the Axiom

of Choice (AC). Zermelo thereby shifted the notion

of set away from Cantor’s principle that every welldefined set is well-orderable and replaced that

principle by an explicit axiom.

In retrospect Zermelo’s argument for his WellOrdering Theorem proved to be pivotal for the development of set theory. To summarize, suppose

that x is a set to be well-ordered, and through Zermelo’s AC hypothesis assume that the power set

P(x) = {y | y ? x} has a choice function, i.e., a function γ such that for every nonempty member y of

P(x), γ(y) ∈ y. Call a subset y of x a γ-set if there

is a well-ordering R of y such that for each a ∈ y,

γ({z | zRa fails}) = a. That is, each member of y

is what γ “chooses” from what does not Rprecede it. The main observation is that γ-sets cohere in the following sense: If y is a γ-set with

well-ordering R and z is a γ-set with well-ordering

S, then y ? z and S is a prolongation of R, or vice

versa. With this, let w be the union of all the γ-sets.

Then w too is a γ-set, and by its maximality it

must be all of x, and hence x is well-ordered.

Cantor’s work had served to exacerbate a growing discord among mathematicians with respect to

two related issues: whether infinite collections can

be mathematically investigated at all, and how far

the function concept is to be extended. The

positive use of an arbitrary function operating on

arbitrary subsets of a set having been made explicit,

there was open controversy after the appearance

of Zermelo’s proof. This can be viewed as a turning point for mathematics, with the subsequent tilting toward the acceptance of AC symptomatic of

a conceptual shift.

Axiomatization

In response to his critics Zermelo published a second proof of the Well-Ordering Theorem in 1908,

and with axiomatization assuming a general

methodological role in mathematics he also published in 1908 the first full-fledged axiomatization of set theory. But as with Cantor’s work, this

was no idle structure building, but a response to

pressure for a new mathematical context. In this

case it was not for the formulation and solution of

a problem but rather to clarify a proof. Zermelo’s

motive in large part for axiomatizing set theory was

to buttress his Well-Ordering Theorem by making

explicit its underlying set existence assumptions.

To summarize Zermelo’s axioms much as they

would be presented today, there is an initial axiom

asserting that two sets are the same if they contain

the same members (Extensionality, i.e., membership

determines equality), and an axiom asserting that

there is an initial set ? having no members (Empty

Set). Then there are the generative axioms, specific

instances of comprehension: For any sets x, y,

{

x, y} = {z | z = x or z = y} is a set (Pairs),

x = {z | ?y(y ∈ x and z ∈ y)} is a set (Union),

and P(x) = {y | y ? x} is a set (Power Set). There is

an axiom asserting the existence of a particular recursively specified infinite set (Infinity). Zermelo

aptly formulated AC in terms of sets as follows: For

any set x consisting of nonempty, pairwise disjoint

sets, there is a set y such that each member of x intersects with y in exactly one element. Finally, there

is the axiom (schema) of Separation: For any set x

and “definite” property A(y), {y ∈ x | A(y)} is a set.

That is, the intersection of a set x and a class

{y | A(y)} is again a set. Zermelo saw that Separation suffices for a development of set theory

that still allows for the “l(fā)ogical” formation of sets

according to property; Russell’s Paradox is precluded since only “l(fā)ogical” subsets are to be allowed. But what exactly is a “definite” property?

This was a central vagary that would be addressed

in the subsequent formalization of Zermelo’s set

theory.

With his axioms Zermelo ushered in a new, abstract view of sets as structured solely by membership and built up iteratively according to governing

axioms, a view that would soon come to dominate.

Zermelo’s work also pioneered the reduction of

mathematical concepts and arguments to set-theoretic concepts and arguments from axioms, based

on sets doing the work of mathematical objects.

420 NOTICES OF THE AMS VOLUME 53, NUMBER 4

recursive definition along well-orderings. The proof

had an antecedent in the Zermelo 1904 proof, but

Replacement was necessary even for the very formulation, let alone the proof, of the theorem. With

the ordinals in place von Neumann completed the

incorporation of the Cantorian transfinite by defining the cardinals as the initial ordinals, those ordinals not in bijective correspondence with any of

their predecessors.

Replacement has been latterly regarded as somehow less necessary or crucial than the other axioms,

the purported effect of the axiom being only on

large-cardinality sets. Initially, Abraham Fraenkel

(1891–1965) and Thoralf Skolem (1887–1963) had

independently proposed adjoining Replacement

to ensure that E(a) = {a, P(a), P(P(a)),... } would

be a set for a, the infinite set given by Zermelo’s

Axiom of Infinity, since, as they pointed out, Zermelo’s axioms cannot establish this. However, even

E(?) cannot be proved to be a set from Zermelo’s

axioms, and if his Axiom of Infinity were reformulated to accommodate E(?), there would still be

many finite sets a such that E(a) cannot be proved

to be a set. Replacement serves to rectify the situation by admitting new infinite sets defined by “replacing” members of the one infinite set given by

the Axiom of Infinity. In any case, the full exercise

of Replacement is part and parcel of transfinite recursion, which is now used everywhere in modern

set theory, and it was von Neumann’s formal incorporation of this method into set theory, as necessitated by his proofs, that brought in Replacement.

Von Neumann (and others) also investigated the

salutary effects of restricting the universe of sets

to the well-founded sets. The well-founded sets are

the sets that belong to some “rank” Vα, these definable through transfinite recursion:

V0 = ?; Vα+1 = P(Vα); and Vδ =
{Vα | α<δ}

for limit ordinals δ.

Vω+1 contains every set consisting of natural numbers (finite ordinals), and so already at early levels

there are set counterparts to many objects in mathematics. That the universe V of all sets is the cumulative hierarchy

V =
{Vα | α is an ordinal}

is thus the assertion that every set is well-founded.

Von Neumann essentially showed that this assertion is equivalent to a simple assertion about sets,

the Axiom of Foundation: Any nonempty set x has

a member y such that x ∩ y is empty. Thus, nonempty well-founded sets have ∈-minimal members. If a set x satisfies x ∈ x, then {x} is not wellfounded; similarly, if there are x1 ∈ x2 ∈ x1 , then

{x1, x2} is not well-founded. Ordinals and sets consisting of ordinals are well-founded, and

Unlike the development of classical mathematics

from marketplace arithmetic and Greek geometry,

sets were neither laden with nor bolstered by wellworked antecedents. Zermelo axiomatization, unlike Russell’s cumbersome theory of types, provided

a simple system for the development of mathematics. Set theory would provide an underpinning

of mathematics, and Zermelo’s axioms would resonate with mathematical practice.

In the 1920s fresh initiatives structured the

loose Zermelian framework with new features and

corresponding developments in axiomatics, the

most consequential moves made by John von Neumann (1903–1957) in his dissertation, with anticipations by Dimitry Mirimanoff (1861–1945). The

transfinite numbers had been central for Cantor but

peripheral to Zermelo, and in Zermelo’s system

not even 2?0 = ?1 could be stated directly. Von

Neumann reconstrued the transfinite numbers as

bona fide sets, the ordinals, and established their

efficacy by formalizing transfinite recursion.

Ordinals manifest the idea, natural once iterative

set formation is assimilated, of taking the relation of

precedence in a well-ordering simply to be membership. A set (or class) x is transitive if and only if

whenever a ∈ b for b ∈ x, a ∈ x. A set x is a (von

Neumann) ordinal if and only if x is transitive, and

the membership relation restricted to x = {y | y ∈ x}

is a well-ordering of x. The first several ordinals are

?, {?}, {?, {?}}, {?, {?}, {?, {?}}},... , to be

taken as the natural numbers 0,1,2,3, .... The union

of these finite ordinals is an ordinal, to be taken as

ω; ω ∪ {ω} is an ordinal, to be taken as ω + 1; and

so forth. It has become customary to use the Greek

letters α, β,γ, ... to denote ordinals; the class of all

ordinals is itself well-ordered by membership, and

α<β is written for α ∈ β; and an ordinal without

an immediate predecessor is a limit ordinal. Von

Neumann established, as had Mirimanoff before him,

the key instrumental property of Cantor’s ordinal

numbers for ordinals: Every well-ordered set is

order-isomorphic to exactly one ordinal with membership. The proof was the first to make full use of

the Axiom of Replacement and thus drew that axiom into set theory.

For a set x and property A(v,w), the property is

said to be functional on x if for any a ∈ x, there is exactly one b such that A(a, b). The Axiom (schema)

of Replacement asserts: For any set x and property

A(v,w) functional on x, {b | ?a(a ∈ x and A(a, b))}

is a set.This axiom posits sets that result when members of a set are “replaced” according to a property;

a simple argument shows that Replacement subsumes Separation.

Von Neumann generally ascribed to the ordinals

the role of Cantor’s ordinal numbers, and already

to incorporate transfinite arithmetic into set theory he saw the need to establish the Transfinite Recursion Theorem, the theorem that validates

APRIL 2006 NOTICES OF THE AMS 421

well-foundedness can be viewed as a generalization

of the notion of being an ordinal that loosens the

connection with transitivity. The Axiom of Foundation eliminates pathologies like x ∈ x and

through the cumulative hierarchy rendition allows

inductive arguments to establish results about the

entire universe.

In a remarkable 1930 publication Zermelo provided his final axiomatization of set theory, one that

recast his 1908 axiomatization and incorporated

both Replacement and Foundation. He herewith

completed his transmutation of the notion of set,

his abstract, prescriptive view stabilized by further

axioms that structured the universe of sets. Replacement provided the means for transfinite recursion and induction, and Foundation made possible the application of those means to get results

about all sets. Zermelo proceeded to offer a striking, synthetic view of a procession of natural models for his axioms that would have a modern resonance and applied Replacement and Foundation

to establish isomorphism and embedding results.

Zermelo’s 1930 publication was in part a response to Skolem’s advocacy, already in 1922, of

the idea of framing Zermelo’s 1908 axioms in firstorder logic. First-order logic is the logic of formal

languages consisting of formulas built up from

specified function and relation symbols using logical connectives and first-order quantifiers ? and

?, quantifiers to be interpreted as ranging over

the elements of a domain of discourse. (Secondorder logic has quantifiers to be interpreted as

ranging over arbitrary subsets of a domain.) Skolem

had proposed formalizing Zermelo’s axioms in the

first-order language with ∈ and = as binary relation symbols. Zermelo’s definite properties would

then be those expressible in this first-order language in terms of given sets, and Separation would

become a schema of axioms, one for each first-order

formula. Analogous remarks apply to the formalization of Replacement in first-order logic. As set

theory was to develop, the formalization of Zermelo’s 1930 axiomatization in first-order logic

would become the standard axiomatization, Zermelo-Fraenkel with Choice (ZFC). The “Fraenkel”

acknowledges Fraenkel’s early suggestion of incorporating Replacement. Zermelo-Fraenkel (ZF) is

ZFC without AC.

Significantly, before this standardization both

Skolem and Zermelo raised issues about the limitations of set theory as cast in first-order logic.

Skolem had established a fundamental result for

first-order logic with the L?wenheim-Skolem Theorem: If a countable collection of first-order sentences has a model, then it has a countable model.

Having proposed framing set theory in first-order

terms, Skolem pointed out as a palliative for taking set theory as a foundation for mathematics

what has come to be called the Skolem Paradox:

Zermelo’s 1908 axioms when cast in first-order

logic become a countable collection of sentences,

and so if they have a model at all, they have a

countable model. We thus have the “paradoxical”

existence of countable models for Zermelo’s axioms

although they entail the existence of uncountable

sets. Zermelo found this antithetical and repugnant,

and proceeded in avowedly second-order terms in

his 1930 work. However, stronger currents were at

work leading inexorably to the ascendancy of firstorder logic.

Constructible Universe

Enter G?del. G?del virtually completed the mathematization of logic by submerging “metamathematical” methods into mathematics. The Completeness Theorem from his 1930 dissertation

established that logical consequence could be captured by formal proof for first-order logic and secured its key instrumental property of compactness

for building models. The main advance was of

course the direct coding, “the arithmetization of

syntax”, which together with a refined version of

Cantor’s diagonal argument led to the celebrated

1931 Incompleteness Theorem. This theorem established a fundamental distinction between what

is true about the natural numbers and what is provable and transformed a program advanced by

Hilbert in the 1920s to establish the consistency

of mathematics by finitary means. G?del’s work

showed in particular that for a (schematically definable) collection of axioms A, its consistency, that

from A one cannot prove a contradiction, has a formal counterpart in an arithmetical formula Con(A)

about natural numbers. G?del’s “second” theorem

asserts that if A is consistent and subsumes the

elementary arithmetic of the natural numbers, then

Con(A) cannot be proved from A.

G?del’s advances in set theory can be seen as

part of a steady intellectual development from his

fundamental work on incompleteness. His 1931

paper had a prescient footnote 48a:

As will be shown in Part II of this paper,

the true reason for the incompleteness

inherent in all formal systems of mathematics is that the formation of ever

higher types can be continued into the

transfinite (cf. D. Hilbert, “über das Unendliche”, Math. Ann. 95, p. 184), while

in any formal system at most countably many of them are available. For it

can be shown that the undecidable

propositions constructed here become

decidable whenever appropriate higher

types are added (for example, the type

ω to the system P [the simple theory of

types superposed on the natural numbers as individuals satisfying the Peano

422 NOTICES OF THE AMS VOLUME 53, NUMBER 4

axioms]). An analogous situation prevails for the axiom system of set theory.

G?del’s letters and lectures clarify that the addition of an infinite type ω to Russell’s theory of

types would provide a “definition for ‘truth’ ” for

the theory and hence establish hitherto unprovable

propositions like those provided by his Incompleteness Theorem. Inherent in Russell’s theory

was the indexing of types by the natural numbers,

and G?del’s citation in the footnote of Hilbert’s

1926 paper in connection with the possibility of adjoining transfinite types would bridge the past and

the future. Hilbert there had attempted a proof of

CH using transfinite indexing in his formalism,

and G?del would achieve what success is possible

in this direction. G?del never published the announced Part II, which was to have been on truth,

but his engagement with truth and its distinction

from provability could be viewed as his entrée into

full blown set theory. In a 1933 lecture G?del expounded on axiomatic set theory as a natural generalization of the simple theory of types “if certain

superfluous restrictions” are removed: One could

cumulate the types starting with individuals D0

and taking Dn+1 = Dn ∪ P(Dn), and one could extend the process into the transfinite, mindful that

for any type-theoretic system S a new proposition

(e.g., Con(S)) becomes provable if to S is adjoined

the “the next higher type and the axioms concerning it”. Thus G?del came to the cumulative hierarchy as a transfinite extension of the theory of

types that incorporates higher and higher levels of

truth.

Alfred Tarski (1902–1983) completed the mathematization of logic in the early 1930s by providing a systematic “definition of truth”, exercising

philosophers ever since. Tarski simply schematized truth by taking it to be a correspondence between formulas of a formal language and settheoretic assertions about an interpretation of the

language and by providing a recursive definition

of the satisfaction relation, that which obtains when

a formula holds in an interpretation. The eventual

effect of Tarski’s mathematical formulation of semantics would be not only to make mathematics

out of the informal notion of satisfiability, but also

to enrich ongoing mathematics with a systematic

method for forming mathematical analogues of

several intuitive semantic notions. For coming purposes, the following specifies notation and concepts:

For a first-order language, suppose that M is an

interpretation of the language (i.e., a specification

of a domain as well as interpretations of the function and relation symbols), ?(v1, v2,...,vn) is a formula of the language with the (unquantified) variables as displayed, and a1, a2,...,an are the

domain of M. Then

M |= ?[a1, a2,...,an]

asserts that the formula ? is satisfied in M according to Tarski’s recursive definition when vi is

interpreted as ai. A subset y of the domain of M

is first-order definable over M if and only if there

is a formula ψ(v0, v1, v2,...,vn) and a1, a2,...,an

in the domain of M such that

y = {z | M |= ψ[z,a1,...,an]}.

Set theory was launched on an independent

course as a distinctive field of mathematics by

G?del’s formulation of the class L of constructible

sets through which he established the relative consistency of AC and CH. He thus attended to the fundamental issues raised at the beginning of set theory by Cantor and Zermelo. In his first 1938

announcement G?del described L as a hierarchy

“which can be obtained by Russell’s ramified hierarchy of types, if extended to include transfinite

orders.” Indeed, with L G?del had refined the cumulative hierarchy of sets to a cumulative hierarchy of definable sets which is analogous to the orders of Russell’s ramified theory. G?del’s further

innovation was to continue the indexing of the hierarchy through all the ordinals. Von Neumann’s

canonical well-orderings would be the spine for a

thin hierarchy of sets, and this would be the key

to both the AC and CH results. In a 1939 note

G?del informally presented L essentially as is done

today: For any set x let def(x) denote the collection

of subsets of x first-order definable over x according to the previous definition. Then define:

L0 = ?; Lα+1 = def(Lα), Lδ =
{Lα | α<δ}

for limit ordinals δ;

and the constructible universe

L =
{Lα | α is an ordinal}.

G?del pointed out that L “can be defined and its

theory developed in the formal systems of set theory themselves.” This follows by transfinite recursion from the formalizability of def(x) in set theory, the “definability of definability”, which was

later reaffirmed by Tarski’s systematic definition

of the satisfaction relation in set-theoretic terms.

In modern parlance, an inner model is a transitive

class containing all the ordinals such that, with

membership and quantification restricted to it, the

class satisfies each axiom of ZF. G?del in effect argued in ZF to show that L is an inner model and

moreover that L satisfies AC and CH. He thus established the relative consistency Con(ZF) implies

Con(ZFC + CH).

In his 1940 monograph, based on 1938 lectures,

G?del formulated L via a transfinite recursion that

generated L set by set. His incompleteness proof

had featured “G?del numbering”, the encoding of

formulas by natural numbers, and his L recursion

APRIL 2006 NOTICES OF THE AMS 423

note. In a comment bringing out the intermixing

of types and orders, G?del pointed out that “there

are sets of lower type that can only be defined with

the help of quantifiers for sets of higher type.” For

example, constructible members of Vω+1 in the

cumulative hierarchy will first appear quite high in

the constructible Lα hierarchy; resonant with

G?del’s earlier remarks about truth, members of

Vω+1, in particular sets of natural numbers, will encode truth propositions about higher Lα’s. G?del

had given priority to the ordinals and recursively

formulated a hierarchy of orders based on definability, and the hierarchy of types was spread out

across the orders. The jumble of the Principia Mathematica had been transfigured into the constructible universe L.

G?del’s argument for CH holding in L rests, as

he himself wrote in a brief 1939 summary, on “a

generalization of Skolem’s method for constructing enumerable models”, now embodied in the

well-known Skolem Hull argument and Condensation Lemma for L. It is the first significant application of the L?wenheim-Skolem Theorem since

Skolem’s own to get his paradox. Ironically, though

Skolem sought through his paradox to discredit set

theory based on first-order logic as a foundation

for mathematics, G?del turned paradox into

method, one promoting first-order logic. G?del

showed that in L every subset of Lα belongs to

some Lβ for some β of the same power as α (so

that in L every real belongs to some Lβ for a countable β, and CH holds). In the 1939 lecture he asserted that “this fundamental theorem constitutes

the corrected core of the so-called Russellian axiom

of reducibility.” Thus, G?del established another

connection between L and Russell’s ramified theory of types. But while Russell had to postulate his

Axiom of Reducibility for his finite orders, G?del

was able to derive an analogous form for his transfinite hierarchy, one that asserts that the types are

delimited in the hierarchy of orders.

G?del brought into set theory a method of construction and argument and thereby affirmed several features of its axiomatic presentation. First,

G?del showed how first-order definability can be

used in a transfinite recursive construction to establish striking new mathematical results. This significantly contributed to a lasting ascendancy for

first-order logic which beyond its sufficiency as a

logical framework for mathematics was seen to

have considerable operational efficacy. G?del’s construction moreover buttressed the incorporation of

Replacement and Foundation into set theory. Replacement was immanent in the arbitrary extent of

the ordinals for the indexing of L and in its formal

definition via transfinite recursion. As for Foundation, underlying the construction was the wellfoundedness of sets. G?del in a footnote to his 1939

note wrote: “In order to give A [the axiom V = L,

was a veritable G?del numbering with ordinals,

one that relies on their extent as given beforehand

to generate a universe of sets. This approach may

have obfuscated the satisfaction aspects of the

construction, but on the other hand it did make

more evident other aspects: Since there is a direct,

definable well-ordering of L, choice functions

abound in L, and AC holds there. Also, L was seen

to have the important property of absoluteness

through the simple operations involved in G?del’s

recursion, one consequence of which is that for any

inner model M, the construction of L in the sense

of M again leads to the same class L. Decades later

many inner models based on first-order definability would be investigated for which absoluteness

considerations would be pivotal, and G?del had formulated the canonical inner model, rather analogous to the algebraic numbers for fields of characteristic zero.

In a 1939 lecture about L G?del described what

amounts to the Russell orders for the simple situation when the members of a countable collection

of real numbers are taken as the individuals and

new real numbers are successively defined via

quantification over previously defined real numbers, and he emphasized that the process can be

continued into the transfinite. He then observed

that this procedure can be applied to sets of real

numbers and the like, as individuals, and moreover,

that one can “intermix” the procedure for the real

numbers with the procedure for sets of real numbers “by using in the definition of a real number

quantifiers that refer to sets of real numbers, and

similarly in still more complicated ways.” G?del

called a constructible set “the most general [object]

that can at all be obtained in this way, where the

quantifiers may refer not only to sets of real numbers, but also to sets of sets of real numbers and

so on, ad transfinitum, and where the indices of iteration …can also be arbitrary transfinite ordinal

numbers.” G?del considered that although this definition of constructible set might seem at first to

be “unbearably complicated”, “the greatest generality yields, as it so often does, at the same time

the greatest simplicity.” G?del was picturing Russell’s ramified theory of types by first disassociating

the types from the orders, with the orders here

given through definability and the types represented by real numbers, sets of real numbers, and

so forth. G?del’s intermixing then amounted to a

recapturing of the complexity of Russell’s ramification, the extension of the hierarchy into the

transfinite allowing for a new simplicity.

G?del went on to describe the universe of set theory, “the objects of which set theory speaks”, as

falling into “a transfinite sequence of Russellian

[simple] types”, the cumulative hierarchy of sets.

He then formulated the constructible sets as an

analogous hierarchy, the hierarchy of his 1939

424 NOTICES OF THE AMS VOLUME 53, NUMBER 4

that the universe is L] an intuitive meaning, one has

to understand by ‘sets’ all objects obtained by

building up the simplified hierarchy of types on an

empty set of individuals (including types of arbitrary transfinite orders).” Some have been baffled

about how the cumulative hierarchy picture came

to dominate in set-theoretic practice; although

there was Mirimanoff, von Neumann, and especially Zermelo, the picture came in with G?del’s

method, the reasons being both thematic and historical: G?del’s work with L with its incisive analysis of first-order definability was readily recognized as a signal advance, while Zermelo’s 1930

paper with its second-order vagaries remained

somewhat obscure. As the construction of L was

gradually digested, the sense that it promoted of

a cumulative hierarchy reverberated to become the

basic picture of the universe of sets.

New Axioms

How G?del transformed set theory can be broadly

cast as follows: On the larger stage, from the time

of Cantor, sets began making their way into topology, algebra, and analysis so that by the time of

G?del, they were fairly entrenched in the structure

and language of mathematics. But how were sets

viewed among set theorists, those investigating

sets as such? Before G?del, the main concerns were

what sets are and how sets and their axioms can

serve as a reductive basis for mathematics. Even

today, those preoccupied with ontology, questions

of mathematical existence, focus mostly upon the

set theory of the early period. After G?del, the

main concerns became what sets do and how set

theory is to advance as an autonomous field of

mathematics. The cumulative hierarchy picture

was in place as subject matter, and the metamathematical methods of first-order logic mediated

the subject. There was a decided shift toward epistemological questions, e.g., what can be proved

about sets and on what basis.

As a pivotal figure, what was G?del’s own stance?

What he said would align him more with his predecessors, but what he did would lead to the development of methods and models. In a 1944 article on Russell’s mathematical logic, in a 1947

article on Cantor’s continuum problem (and in a

1964 revision), and in subsequent lectures and correspondence, G?del articulated his philosophy of

“conceptual realism” about mathematics. He espoused a staunchly objective “concept of set” according to which the axioms of set theory are true

and are descriptive of an objective reality schematized by the cumulative hierarchy. Be that as it

may, his actual mathematical work laid the groundwork for the development of a range of models and

axioms for set theory. Already in the early 1940s

G?del worked out for himself a possible model for

the negation of AC, and in a 1946 address he

described a new inner model, the class of ordinal

definable sets.

In his 1947 article on the continuum problem

G?del pointed out the desirability of establishing

the independence of CH, i.e., in addition to his relative consistency result, that also Con(ZF) implies

Con(ZFC + the negation of CH). However, G?del

stressed that this would not solve the problem.

The axioms of set theory do not “form a system

closed in itself”, and so the “very concept of set on

which they are based” suggests their extension by

new axioms, axioms that may decide issues like CH.

New axioms could even be entertained on the extrinsic basis of the “fruitfulness of their consequences”. G?del concluded by advancing the remarkable opinion that CH “will turn out to be

wrong” since it has as paradoxical consequences

the existence of thin, in various senses he described, sets of reals of the power of the continuum.

Later touted as his “program”, G?del’s advocacy of the search for new axioms mainly had to

do with large cardinal axioms. These postulate

structure in the higher reaches of the cumulative

hierarchy, often by positing cardinals whose properties entail their inaccessibility from below in

strong senses. Speculations about large cardinal

possibilities had occurred as far back as the time

of Zermelo’s first axiomatization of set theory.

G?del advocated their investigation, and they can

be viewed as a further manifestation of his footnote 48a idea of capturing more truth, this time by

positing strong closure points for the cumulative

hierarchy. In the early 1960s large cardinals were

vitalized by the infusion of model-theoretic methods, which established their central involvement in

embeddings of models of set theory. The subject

was then to become a mainstream of set theory

after the dramatic introduction of a new way of getting extensions of models of set theory.

Paul Cohen (1934–) in 1963 established the independence of AC from ZF and the independence

of CH from ZFC. That is, Cohen established that

Con(ZF) implies Con(ZF + the negation of AC) and

that Con(ZF) implies Con(ZFC + the negation of

CH). These results delimited ZF and ZFC in terms

of the two fundamental issues raised at the beginning of set theory. But beyond that, Cohen’s

proofs were soon to flow into method, becoming

the inaugural examples of forcing, a remarkably

general and flexible method for extending models

of set theory by adding “generic” sets. Forcing has

strong intuitive underpinnings and reinforces the

notion of set as given by the first-order ZF axioms

with conspicuous uses of Replacement and Foundation. With L analogous to the field of algebraic

numbers, forcing is analogous to making transcendental field extensions. If G?del’s construction

of L had launched set theory as a distinctive field

APRIL 2006 NOTICES OF THE AMS 425

of mathematics, then Cohen’s method of forcing

began its transformation into a modern, sophisticated one. Set theorists rushed in and were soon

establishing a cornucopia of relative consistency results, truths in a wider sense, some illuminating

problems of classical mathematics. In this sea

change the extent and breadth of the expansion of

set theory dwarfed what came before, both in terms

of the numbers of people involved and the results

established.

Already in the 1960s and into the 1970s large

cardinal postulations were charted out and elaborated, investigated because of the “fruitfulness of

their consequences” since they provided quick

proofs of various strong propositions and because

they provided the consistency strength to establish

new relative consistency results. A subtle connection quickly emerged between large cardinals and

combinatorial propositions low in the cumulative

hierarchy: Forcing showed just how relative the

Cantorian notion of cardinality is, since bijections

could be adjoined easily, often with little disturbance to the universe. In particular, large cardinals,

highly inaccessible from below, were found to satisfy substantial propositions even after they were

“collapsed” by forcing to ?1 or ?2, i.e., bijections

were adjoined to make the cardinal the first or

second uncountable cardinal. Conversely, such

propositions were found to entail large cardinal hypotheses in the clarity of an L-like inner model,

sometimes the very same initial large cardinal hypothesis. In a subtle synthesis, hypotheses of length

concerning the extent of the transfinite were correlated with hypotheses of width concerning the

fullness of power sets low in the cumulative hierarchy, sometimes the arguments providing equiconsistencies. Thus, large cardinals found not only

extrinsic but intrinsic justifications. Although their

emergence was historically contingent, large cardinals were seen to form a linear hierarchy, and

there was the growing conviction that this hierarchy provides the hierarchy of exhaustive principles

against which all possible consistency strengths can

be gauged, a kind of hierarchical completion of ZFC.

In the 1970s and 1980s possibilities for new

complementarity were explored with the development of inner model theory for large cardinals, the

investigation of minimal L-like inner models having large cardinals, models that exhibited the kind

of fine structure that G?del had first explored for

L. Also, determinacy hypotheses about sets of reals

were explored because of their fruitful consequences

in descriptive set theory, the definability theory of

the continuum. Then in a grand synthesis, certain

large cardinals were found to provide just the consistency strength to establish the consistency of

ADL(R)

, the Axiom of Determinacy holding in the

minimal inner model L(R) containing all the reals.

In a different direction, Harvey Friedman has

recently provided a variety of propositions of finite

combinatorics that are equi-consistent with the existence of large cardinals; this incisive work serves

to affirm the “necessary use” of large cardinal axioms even in finite mathematics. In set theory itself, Hugh Woodin has developed a scheme based

on a new logic in an environment of large cardinals

that argues against CH itself, and with an additional

axiom, that 2?0 = ?2 . These results serve as remarkable vindications for G?del’s original hopes

for large cardinals.

References

KURT G?DEL, [1986], Collected Works, Volume I: Publications

1929–1936, (Solomon Feferman, editor-in-chief), Oxford University Press, New York.

——— , [1990], Collected Works, Volume II: Publications

1938–1974, (Solomon Feferman, editor-in-chief), Oxford University Press, New York.

——— , [1995] Collected Works, Volume III: Unpublished Essays and Lectures, (Solomon Feferman, editor-in-chief),

Oxford University Press, New York.

[2002] THOMAS JECH, Set Theory, third millennium edition,

revised and expanded, Springer, Berlin.

[2003] AKIHIRO KANAMORI, The Higher Infinite. Large Cardinals in Set Theory from their Beginnings, second

edition, Springer-Verlag, Berlin.

[1982] GREGORY H. MOORE, Zermelo’s Axiom of Choice. Its

Origins, Development, and Influence. Springer-Verlag,

New York.