Set Theory: Complexity, Definability, Infinity

One way to begin thinking about set theory is to forget, temporarily, about infinite cardinals, formal axioms, and the enormous universe of mathematical objects, and instead ask a much more elementary question: what does it mean to construct a mathematical object, and what resources does that construction require? Suppose we are given a finite collection of objects, say There are several things we can do with this collection. We can choose one of its elements. We can arrange its elements in some order. We can form pairs of elements, or consider functions from the collection to itself. And, perhaps most importantly, we can consider all possible ways of selecting elements from the collection. For instance, the subsets of are

Thus a set with three elements has eight subsets. More generally, a set with elements has subsets. Why does this factor of two appear? Because to specify a subset, we make one yes-or-no decision for each of the elements. A subset is therefore equivalent to a string of binary digits, or to a function The subset corresponding to consists of those elements for which . This is already a useful way to think about the power-set operation. Given a collection of objects, we are now considering all possible decisions about which objects should be selected. The resulting collection, written , is much larger than the original one.

In the finite setting, there is nothing especially mysterious about this. We can enumerate the subsets by running through all binary strings. Indeed, if we were programming a computer, we could represent each subset by an integer between and , using the binary expansion of the integer to record the membership decisions. But notice how quickly the resources required for this construction grow. If contains elements, the power set contains elements, already an enormous number. If contains a million elements, its power set is far too large to enumerate in any practical sense, even though every individual subset can still be represented by a finite binary string.

There are consequently two distinct mathematical questions here. One concerns the existence of the collection of all possible subsets. The other concerns the resources required to enumerate, describe, or compute those subsets. In finite mathematics, we can usually move between these questions without much difficulty, because everything under consideration is finite. We might need an impossibly large amount of time or memory, but there is at least a finite algorithm that would perform the enumeration.

Set theory begins to become interesting when we remove this finiteness assumption. Suppose that instead of a finite collection, we take the natural numbers We can now consider all functions Such a function is an infinite binary sequence, Equivalently, it describes a subset of the natural numbers. The familiar set of even numbers is represented by the sequence if we start indexing at zero. The set of prime numbers gives another sequence, and so does the set of positive integers occurring as denominators of convergents to some specified irrational number. But there are also binary sequences having no known pattern, no convenient mathematical description, and no algorithm that can compute their digits. In fact, there are only countably many computer programs, because each program is a finite string over a finite alphabet. Therefore there are at most countably many computable binary sequences. The collection of all binary sequences is uncountable. Thus most binary sequences are not computable. More generally, most subsets of the natural numbers cannot be individually specified by a finite description in any fixed countable mathematical language.

This is our first encounter with an important distinction: Having a mathematical object is not the same thing as possessing a finite description of it, and possessing a finite description is not the same thing as having an effective algorithm for constructing it. The axioms of set theory permit the existence of collections far larger than those that could ever be explicitly enumerated or computationally generated. To understand what this means, and why it does not immediately lead to contradictions, we need to examine the process by which the universe of sets is constructed.

Construction of the universe

There is a remarkable fact about modern mathematics: essentially all the ordinary objects we study- numbers, functions, sequences, groups, rings, fields, topological spaces, and so on, can be represented using sets. One should not necessarily interpret this as a claim that a number really is a particular set. Rather, the point is that set theory supplies a common mathematical framework in which these objects can be constructed and their properties studied. Let us see how little we need to get started.

Begin with the empty set There is a useful way to construct a successor operation on sets. Given a set , define

Applying this to the empty set gives Applying it again, The next stage is And so on. In general, the finite ordinal is represented by the set of all smaller natural numbers:

Notice how naturally order appears in this construction. We have and, more generally, whenever , Thus the ordinary order relation on natural numbers is represented by set membership. This construction is known as the von Neumann representation of ordinals. It will become especially useful when we move beyond the natural numbers, because it allows us to define infinite ordinal numbers using the same basic idea. For the moment, notice something more elementary. We began with the empty set, used the operation of forming a singleton, and took a union. These two operations were enough to generate every finite natural number. Other ordinary mathematical constructions can also be expressed using sets. For instance, an ordered pair can be represented by

This encoding has the crucial property that

Once ordered pairs are available, a function from to can be represented by a suitable subset of Equivalence relations and equivalence classes then let us construct the integers from the natural numbers, the rationals from the integers, and the real numbers from the rationals. For example, we can think of a rational number as an equivalence class of pairs with , using the relation

Nothing especially complicated is happening conceptually. We are repeatedly forming new collections out of previously available mathematical objects, and then imposing relations on those collections. The central foundational question is therefore this: Which operations on already constructed sets should be permitted, and how far can we iterate those operations? Rather than treating the axioms of set theory as an arbitrary list of logical statements, it is useful to think of them as rules specifying which set-forming operations are legitimate.

Before listing the axioms, however, let us investigate what happens when we repeatedly apply the most expansive of these operations: taking all subsets. Suppose we start with no objects at all. Let Now form all subsets of what we have:

There is only one subset of the empty set, namely the empty set itself. At the next stage,

The next stage contains four sets: In general, for the finite stages we define

Let us calculate the sizes. Writing , we have

Therefore Already The number of objects is growing at an extraordinary rate, even though we have only applied the same elementary operation a few times. But there is something much more interesting than the growth of these numbers. Every object appearing at any finite stage is itself a finite set, whose elements are finite sets, whose elements are finite sets, and so on. These are called hereditarily finite sets. A set such as is hereditarily finite, as is every finite natural number in our representation. The amount of nesting can be enormous, but it is always finite. Now imagine carrying out this construction for every natural number . We will have constructed and would like to collect everything that has appeared at some finite stage. The natural definition is

The notation represents the first infinite ordinal, which we will examine more carefully shortly. What is ? It is precisely the collection of all hereditarily finite sets. Every element of is finite, but itself is infinite. Moreover, is countable. Each is finite, and we are taking a countable union of these finite sets. One can also encode each hereditarily finite set using a finite combinatorial description and then enumerate all such descriptions. This gives us a fundamental phenomenon: An infinite object can arise as the totality of all finite constructions, even when no individual finite stage produces an infinite object. This distinction is easy to overlook because we are accustomed to writing infinite sequences and unions without asking what permits us to regard the result as one completed mathematical object. If we were working only with the finite sets, we could continue applying our finite construction rules indefinitely, in the sense that no finite stage would be the last. But that alone does not supply the infinite collection as a set. The existence of such completed infinite collections is a genuine additional principle, reflected in the axiom of infinity.

There is now another interesting observation. The natural numbers all belong to , because each is a hereditarily finite set. But the set of all natural numbers, does not belong to . It is infinite, whereas every element of is finite. It appears only at the next level:

Why? Because every natural number is an element of , so the set of all natural numbers is a subset of . At the following stage, the entire power set of the natural numbers becomes available as an element:

This is worth considering slowly. At the finite stages we could construct individual natural numbers. At we have collected all finite constructions. At the next stage we acquire infinite subsets of this countable collection, including the natural numbers as a completed set. And at the stage after that, we have the entire collection of subsets of the natural numbers as an object. Within a very small number of stages beyond the first infinite level, we have already encountered the objects underlying essentially all of ordinary real analysis. Indeed, a real number can be encoded by a subset of the natural numbers, or by an infinite binary sequence, with some care about representations. Thus the real numbers are closely connected with This is a remarkably concrete way to see how the basic mathematical universe emerges. Finite objects give us natural numbers. Sets of natural numbers give us infinite sequences and real numbers. Sets of those sets lead to collections of real numbers, spaces of functions, and increasingly complicated mathematical structures. The process does not stop there.

Rank

Before continuing the construction, it is useful to introduce a way of measuring where an object first appears. Given a set , define its rank recursively by

The rank of the empty set is zero, since the supremum of the empty collection of ordinals is zero: For a singleton, we have

More generally, the rank of a set is the smallest ordinal strictly larger than the ranks of all its elements. For the natural numbers in our representation, one finds And for the infinite ordinal ,

A general relation between rank and the cumulative hierarchy is

We can think of rank as a measure of the depth of construction of a set. This is quite different from cardinality. For instance, the singleton has only one element, but its rank is . On the other hand, is countably infinite and also has rank . More dramatically, very large sets can occur at comparatively low levels of the hierarchy, while even a singleton can have extremely high rank if its unique element is itself a high-rank object.

This is our first reason to distinguish two notions that are often conflated: Cardinality measures the number of objects in a set. Rank measures the depth of the membership structure from which that set is built. There is no reason these measurements should agree. As we move into transfinite set theory, this distinction becomes indispensable.

Let us return to the cumulative hierarchy. We have defined for finite , and then formed their union . What happens next? We can simply continue:

and so on. After infinitely many more stages we arrive at

We can continue to , , and eventually to . Then we can continue through , , and much further. What we need is a system of indices that records not only ordinary finite steps but also the stages that arise after taking limits of earlier processes. These indices are the ordinal numbers.

The general construction becomes

This is the cumulative hierarchy of sets. The universe is then described informally by

where denotes the proper class of all ordinals. One should be careful about the meaning of this formula. It is not a union indexed by some enormous set of ordinals, because there is no set of all ordinals. It is a class-sized description of the fact that every set appears at some stage. The fundamental picture is nevertheless clear. The universe is built in stages, and every set appears at some level determined by its rank. But this raises a new question. What exactly are these ordinal numbers, and why should they be the appropriate way to organize transfinite constructions?

Ordinals

We are familiar with the natural numbers as a way to count the number of steps in a finite procedure. If we perform an operation once, twice, or a hundred times, the number of iterations is a natural number. Suppose, however, that we want to describe a construction in which an object is formed from the results of all finite stages, after which the construction continues. This is what happens at . The first infinite ordinal can be represented as The next ordinal is Then And so on. The distinction between and is not one of cardinality. Both are countably infinite sets. Rather, has a final element, whereas does not. This is the first example of why ordinal arithmetic differs from ordinary arithmetic.

Consider two ordered processes. In the first, we perform one operation and then infinitely many further operations, indexed by the natural numbers. In the second, we perform infinitely many operations and then one more operation afterward. The first process has order type because adding one initial step to a countably infinite sequence does not change its order type. We can simply relabel the steps. The second process has order type The extra final step cannot be relabeled away, because has no last element. Thus ordinal addition is not commutative:

This might initially look like an arbitrary peculiarity of ordinal notation. But it is exactly what we should expect if ordinals are supposed to describe the order in which a construction takes place. The existence of a final step matters. Similarly, consider This consists of two consecutive infinite blocks. First come steps followed by another block Although the two blocks together are still countable, their order type is different from that of an ordinary natural-number sequence. Now imagine countably many such blocks. The corresponding order type is We can continue in this fashion to construct more complicated ordinals such as These are all countable ordinals.

Their significance lies not in their cardinality, but in the increasingly elaborate structures of iteration that they encode. For instance, an ordinal of the form describes a well-ordered process with one block of type , followed by three blocks of type , followed by five final steps. This leads to Cantor normal form: every nonzero ordinal can be uniquely expressed as a finite sum of decreasing powers of with positive finite coefficients. There is a natural analogy with writing an integer in base ten, except that the exponents and coefficients are used to encode well-ordered structure rather than ordinary numerical magnitude. At this point, one should avoid a possible misunderstanding. An ordinal is not necessarily a running time for an actual computer program. An ordinary Turing machine performs only finitely many steps before halting. When we speak of processes extending to or beyond, we are describing mathematical recursions with specified operations at limit stages. There are separate theories of infinitary computation that genuinely extend computational models into transfinite time. But the ordinary use of ordinals in set theory is more general: they index well-founded mathematical constructions.

Consider a tree whose nodes are all finite strictly decreasing sequences of natural numbers, together with the empty sequence , which we regard as the root. For example, are nodes of this tree. A node can be extended by appending a smaller natural number. Thus has children . There are paths of arbitrarily large finite length: we can always begin with a sufficiently large natural number. But there is no infinite path, since an infinite path would give an infinite strictly decreasing sequence of natural numbers.

Now suppose we try to establish this by repeatedly removing nodes that have no children. At the first stage, we remove all sequences ending in , since they cannot be extended. At the second stage, sequences ending in become terminal and are removed. At the third stage, those ending in disappear, and so on. In general, after stages, every nonempty sequence whose last entry is smaller than has disappeared. But what happens to the root?

The root survives every finite stage! At stage , there are still children of the root, such as . Therefore no finite number of pruning steps removes it. Now take the intersection of the trees remaining after all finite stages. Every nonempty sequence has disappeared, because its last entry is some finite number. Only the root remains:

At this stage the root finally has no children, so one additional pruning step removes it:

This explains concretely the distinction between and . The stage collects the results of all finite stages, but we may still need to perform another operation afterward.

We can measure this phenomenon using the rank of a node. Assign to each node the ordinal

Terminal nodes have rank zero. A nonempty sequence ending in has rank , while the root has rank

The key idea is that ordinals measure the depth of well-founded processes, not just the number of objects involved. More complicated trees can have ranks , or much larger countable ordinals. This is why ordinals naturally appear in termination proofs, recursion theory, and even elementary problems about integers, such as Goodstein’s theorem.

Recursion and Transfinite Induction

The reason ordinal-indexed constructions work so well is that ordinals are well-ordered. A well-ordered set is a linearly ordered set in which every nonempty subset has a least element. The natural numbers have this property. The integers do not, under their usual order, because the negative integers have no least element. All ordinals have the well-ordering property, and this permits a generalization of ordinary mathematical induction. Suppose we want to prove a property for every ordinal . It suffices to prove that whenever holds for every , then also holds. Why? Suppose there were some ordinal where the property failed. Then there would be a least ordinal where it failed. But the property would hold at every smaller ordinal, and the induction step would establish it at , a contradiction. This is transfinite induction.

A corresponding principle of transfinite recursion allows us to define an object at stage using the entire history of the construction before that stage. Symbolically, we can specify

where denotes the sequence of previously constructed objects This is much more general than an ordinary recurrence such as

In a transfinite recursion, the next object may depend on all earlier objects, and a special operation may occur at limit stages. The cumulative hierarchy is an example: at successor stages we take a power set, while at limit stages we take a union. The tree-pruning construction is another: at successor stages we remove terminal nodes, while at limit stages we take intersections. The distinction between successor and limit stages is one of the recurring organizing principles of set theory. Successor stages are where we apply a particular local operation. Limit stages are where we gather, combine, or stabilize everything constructed previously. And it is often at limit stages that qualitatively new mathematical phenomena appear.

Cardinality

We now have one way of measuring infinite objects, namely their ordinal structure or rank. But there is another, more familiar way: cardinality. Two sets have the same cardinality if there is a bijection between them. For finite sets, this reproduces ordinary counting. For infinite sets, the behavior is quite different. For example, the natural numbers and even natural numbers have the same cardinality, because is a bijection from onto the even natural numbers. Similarly, the integers are countable, as are the rational numbers. To see the countability of , note that every rational number can be represented by a pair of integers, and the collection of integer pairs is countable. For nonnegative integer pairs, a concrete enumeration is furnished by the Cantor pairing function This is a bijection between and . We can likewise enumerate all finite strings over a finite alphabet. First enumerate strings of length zero, then length one, then length two, and so on. This observation has an important consequence: there are only countably many finite mathematical descriptions in a fixed countable language. Even if those descriptions can specify extraordinarily complicated mathematical objects, there are only countably many such descriptions.

Now consider infinite binary sequences. Suppose someone claims to have enumerated all of them:

We construct a new binary sequence by changing the diagonal digits: Then differs from at coordinate . Thus cannot appear anywhere on the proposed list. We conclude that the set of all infinite binary sequences is uncountable:

This is Cantor’s diagonal argument. What makes it powerful is that it is not merely an argument about binary sequences. It is a general method of constructing an object that escapes an alleged complete classification. Given any set and any proposed surjection define

If were surjective, there would be some with . But then

a contradiction. Hence This is true for every set , finite or infinite. In particular, there cannot be a largest cardinal number. Whatever cardinality we start with, taking the power set produces a strictly larger one. This is one of the fundamental reasons the universe of sets cannot be organized around a single notion of infinity. There is an unending hierarchy of increasingly large cardinalities.

One might now imagine organizing all infinite cardinalities into an increasing list. This is what the aleph hierarchy does:

Here is the cardinality of the natural numbers, and is the least uncountable cardinal. There is, however, another natural sequence of cardinalities, obtained by repeatedly applying the power-set operation:

At limit stages we define

The first few beth numbers are

These hierarchies arise from different operations. The aleph hierarchy moves from one infinite cardinal to the next. The beth hierarchy takes the entire collection of subsets at each stage. There is no immediate reason for these two operations to produce the same result. In particular, the continuum hypothesis asserts that It asks whether taking all subsets of a countable set produces exactly the next uncountable cardinal, or whether there are intermediate cardinalities.

We know from Cantor’s theorem that But Cantor’s theorem alone gives no upper bound on where lies in the aleph hierarchy. One of the great discoveries of modern set theory is that the usual axioms do not determine the answer. Before discussing this independence phenomenon, however, there is an important point worth emphasizing: cardinal arithmetic is not completely arbitrary. Even when the axioms cannot determine an exact cardinality, they often constrain its structure.

Cofinality:

Suppose we have an increasing sequence of ordinals We can form its supremum

In this case, we say that the sequence is cofinal in . The cofinality of an ordinal measures the minimum length of an increasing sequence that approaches it without remaining bounded below it.

For instance, Likewise, because

Thus is a much more complicated ordinal than , but it can still be approached by a countable sequence. Now consider the first uncountable ordinal . Could we find a countable increasing sequence of countable ordinals whose supremum is ?

No. If for every , then each is countable. Under the axiom of choice, a countable union of countable sets is countable. Therefore the supremum of the sequence is still a countable ordinal, and cannot equal . Hence

An infinite cardinal is called regular if and singular otherwise. For example, is singular, since

Thus This distinction becomes very important in higher set theory, but it is useful already in elementary cardinal arithmetic.

Let us derive one concrete result. The cardinality of the continuum has uncountable cofinality. More precisely,

There is a particularly instructive diagonal proof of this fact. Suppose, toward a contradiction, that the space of all binary sequences can be covered by countably many sets

where each has cardinality strictly smaller than the continuum. Partition the natural numbers into countably many disjoint infinite blocks:

Each space has cardinality continuum, because is countably infinite. Now consider all the restrictions to of sequences belonging to . There are fewer than continuum-many such restrictions, because there are fewer than continuum-many members of . Therefore we can choose a binary pattern that does not occur as the restriction of any member of . Having made this choice for every , combine the patterns into one binary sequence by setting Then for every , since its restriction to was deliberately chosen to avoid all restrictions coming from . Thus belongs to none of the sets , contradicting the assumption that they cover all binary sequences. This proves the claim.

The proof is worth remembering. We have divided the coordinates into infinitely many blocks and used each block to defeat one proposed part of a covering. It is a generalized diagonal argument. In particular, the continuum cannot equal , since has countable cofinality.

Thus even though ZFC does not tell us the exact value of the continuum, it rules out some possible values. This is a good example of how infinitary combinatorics constrains cardinal arithmetic.

Axioms

We can now return to the axioms of set theory with a better sense of why they are needed. The standard foundational system is ZFC: Zermelo–Fraenkel set theory together with the axiom of choice. Rather than treating the axioms as a purely formal list, let us consider the mathematical operations they permit.

Extensionality says that two sets are equal if and only if they have the same elements:

This tells us that the identity of a set is determined entirely by its membership structure.

Pairing allows us to form from previously available objects and .

Union allows us to combine the members of a set of sets. If is a set, we can form

These are relatively modest operations. They reorganize objects already available to us.

The axiom of infinity is different. It guarantees the existence of an inductive set: a set containing and closed under the successor operation

From such a set, using separation, we obtain the smallest inductive set, which is the usual . Thus the axiom of infinity does more than permit arbitrarily large finite constructions. It guarantees a completed set containing all the finite stages.

The power-set axiom says that for every set , there exists a set consisting of all subsets of . This is a much stronger form of collection-making. It does not require that the subsets be explicitly described, computable, or previously named. For instance, the power-set axiom supplies the set even though almost all its members are noncomputable and cannot be individually described by any formula without parameters.

The separation schema allows us to filter an existing set according to a logical property. If is already a set and is a formula, then separation allows us to construct

The distinction between separation and unrestricted comprehension is crucial. Separation begins with an already existing set and selects some of its elements. It does not assert that every property defines a set consisting of all objects satisfying that property.

Why would unrestricted comprehension be dangerous? Suppose we were permitted to form

We could then ask whether . By definition,

which is impossible. This is Russell’s paradox. The lesson is that a formula describing a collection does not automatically establish that the collection is a set. The set-theoretic universe contains too many objects to be gathered into a single set of all sets. This explains why we distinguish sets from proper classes. The universe is a proper class, as is the collection of all ordinals.

Another particularly important axiom is Replacement. Suppose a formula defines a function on an existing set , assigning a unique object to each . Replacement allows us to form the set of all outputs:

At first this may sound obvious, but it has considerable consequences. Consider a construction that assigns to each natural number the corresponding level of the cumulative hierarchy: Replacement ensures that the outputs form a set

which can then be united to form . More generally, if a transfinite recursion defines an object at every stage below some ordinal , Replacement ensures that all the outputs of this set-sized recursion can be collected. This is essential because the recursive construction may generate objects of increasing rank. We need a principle ensuring that the outputs do not escape the realm of sets merely because their structural complexity increases.

Replacement thus gives ZFC much of its ability to support arbitrarily long ordinal-indexed constructions.

The axiom of Foundation, also called Regularity, says that every nonempty set contains an element such that

It rules out circular membership configurations such as and, in ZFC, infinite descending membership chains. This is the structural principle behind the rank hierarchy. Membership always moves downward in rank:

Thus the membership structure of sets is well-founded. The universe is not built out of arbitrary circular networks of objects. Every set ultimately rests on lower-rank sets, and this is why transfinite recursion on rank works.

Finally, the axiom of choice says that if we have a set-indexed family of nonempty sets then we may choose one element from every set simultaneously. That is, there exists a function such that

For finitely many sets, there is no problem. We can simply choose one element from each. For infinitely many sets, however, the existence of one global function recording all choices is a nontrivial mathematical assertion. A familiar consequence is that every vector space has a basis. The usual proof takes a maximal linearly independent set using Zorn’s lemma, which is equivalent to the axiom of choice. The interesting point is that the theorem concerns the existence of a basis, not necessarily an explicit algorithm for finding one. This is another example of why mathematical existence and effective construction must be distinguished.

There are models of set theory without Choice in which some familiar algebraic and combinatorial assertions fail. Thus Choice is not merely a convenient technical device. It changes which infinite selection principles are available in the universe.

At this point, we have interpreted several axioms as permitting particular mathematical operations. This perspective is useful, but we should also recognize its limitations. For example, the power-set axiom does not give us an actual algorithm for listing every subset of the natural numbers. Such an algorithm cannot exist, because there are uncountably many subsets and only countably many finite programs. Likewise, Replacement does not assert that every definable function is computable. A formula can define an object that is extremely difficult, or impossible, to calculate effectively. Even the constructible hierarchy, which we will encounter shortly, is not simply a hierarchy of computable sets.

A better way to interpret the resource analogy is to distinguish several kinds of mathematical resources. One is finite descriptive information: the formulas, programs, and finite strings available to specify an object. Another is computational power: whether a prescribed procedure can actually determine the object. A third is infinitary construction strength: what operations on entire infinite collections are permitted. A fourth is logical strength: what axioms are sufficient to establish the existence of the object. These notions often interact, but none can simply replace the others.

For example, the set of computable natural-number functions is countable, but deciding which programs compute total functions is itself a noncomputable problem. Likewise, an infinite tree can have a computable membership relation and possess an infinite branch, while having no computable infinite branch at all. We should therefore think of set theory as examining different forms of infinitary existence, rather than as simply extending ordinary finite computation.

Let us make this distinction more concrete. Consider the set

of all finite binary strings. A binary tree is a subset closed under taking initial segments. A branch through is an infinite binary sequence such that every finite initial segment belongs to the tree:

A classical result, König’s lemma, tells us that every infinite finitely branching tree has an infinite branch. The proof is simple. Since the root has only finitely many children, at least one child must have infinitely many descendants. Choose such a child. Repeat the argument in the infinite subtree below that child, and continue. We obtain an infinite branch. But notice exactly what the proof requires: at each stage, we must identify a child having infinitely many descendants. Suppose that membership in the tree is computable. Given a finite string , we can determine whether . Does this guarantee that the proof above can be turned into an algorithm?

No. Knowing whether a given finite string belongs to a tree does not necessarily tell us whether it has infinitely many descendants. In fact, there exist computable infinite binary trees with no computable infinite branches. This is a striking example. Every finite approximation can be inspected by a computer. The tree is known mathematically to possess an infinite branch. Yet there is no computer program that generates the bits of any complete infinite branch. One way to construct such a tree uses recursively inseparable computably enumerable sets. We impose finite requirements ensuring that an infinite branch separates two disjoint enumerably describable sets that no computable set can separate. Every finite requirement can be checked effectively, but any complete branch necessarily has noncomputable information. The lesson is that local computational access to a collection of finite possibilities need not provide the global information needed to select an infinite compatible sequence.

This naturally leads to reverse mathematics, which studies the logical principles required to prove familiar mathematical theorems. For example, weak König’s lemma is not derivable from certain weak systems of computable mathematics, even though it is straightforward to prove in ordinary ZFC. Thus the existence of an infinite path becomes a measure of the strength of the mathematical system in which we are working. We are no longer asking only whether a theorem is true. We are asking what resources are necessary to prove it.

Models

The preceding discussion suggests a more subtle question. The axioms of ZFC describe a universe of sets. But do they uniquely determine what that universe contains? To understand why the answer is no, we need to distinguish a mathematical universe from a particular model of the axioms. A model of set theory is a structure in which the axioms are interpreted and hold. For many purposes, it is especially useful to consider a transitive model . Transitivity means that whenever and , we also have . In other words, whenever a transitive model contains a set, it contains every element of that set.

Suppose is a transitive model of ZFC. Inside , the natural numbers form the usual set . The model also possesses what it regards as the power set of the natural numbers: But from the perspective of a larger universe , the model might be missing some subsets of the natural numbers. We can have

This sounds strange at first. If satisfies the power-set axiom, shouldn’t it contain all subsets of the natural numbers? It does contain all subsets that exist inside . But the larger universe may contain additional subsets that are not objects of . The same axiom can therefore hold in both universes even though they contain different collections of real numbers.

This is a fundamental point in modern set theory: The meaning of an assertion about all sets depends on the mathematical universe over which its quantifiers range. There is an analogous phenomenon in algebra. A polynomial may have no roots in a field but acquire roots in a larger field . The set-theoretic situation is more subtle, because what gets added to the larger universe may be new subsets of objects already present in the smaller one, and this can alter statements about their cardinalities.

Skolem Paradox

One of the most illuminating examples of this distinction comes from model theory. The downward Löwenheim–Skolem theorem implies that if a first-order theory in a countable language has an infinite model, then it has a countable model. Since ZFC is a first-order theory in a countable language, if ZFC is consistent, it has a countable model. But ZFC proves that uncountable sets exist. So how can a countable model of ZFC contain an uncountable set?

The resolution is that the word countable is being interpreted in two different contexts. Suppose is a countable model of ZFC. From outside , its elements can be listed as But that external enumeration is not necessarily an element of .

Inside the model, a set is countable if the model contains a suitable bijection between and the natural numbers. The model may lack such a bijection, even when one exists externally. Thus the model can correctly satisfy the statement that some of its sets are uncountable, although the model itself has only countably many elements when viewed from outside.

This phenomenon is sometimes called Skolem’s paradox, although there is no actual contradiction. It reveals something profound about cardinality. Cardinality is not merely a matter of counting elements in some informal absolute sense. It is determined through the existence of bijections, and bijections are themselves mathematical objects that a model may or may not contain. A larger universe can introduce new functions between old sets. Consequently, a set that was uncountable in a smaller model may become countable in a larger one if the larger universe adds an appropriate enumeration.

We must add one technical distinction. The Löwenheim–Skolem theorem guarantees countable models under the consistency assumption, but not necessarily countable transitive models. The existence of a countable transitive model of ZFC is a stronger metamathematical assumption. For understanding forcing, countable transitive models are often used as a particularly transparent setting, but their existence should not be silently inferred from consistency alone.

Definable Sets, Gödel’s Constructible Universe

The cumulative hierarchy uses the full power-set operation at each successor stage:

This means that every possible subset becomes available. But suppose we were more conservative. Rather than adding every subset, we add only subsets that can be defined using formulas and parameters already present at that stage. This is the basic idea behind Gödel’s constructible universe, denoted .

We begin with At the next stage, instead of taking the full power set, we take the collection of definable subsets:

At limit stages,

Here consists of subsets of definable over the structure using first-order formulas and parameters from .

The distinction is quite significant. At a countable stage, there are only countably many formulas and countably many finite tuples of parameters. Therefore there are only countably many subsets definable from those parameters. But the full power set of a countably infinite set is uncountable. So definable-subset formation can be vastly more restrictive than arbitrary power-set formation. Nevertheless, if we continue the constructible hierarchy through all ordinals, we obtain a proper class

that satisfies all the axioms of ZFC. This is a highly nontrivial theorem of Gödel. Even more strikingly, the generalized continuum hypothesis holds in :

for every ordinal . In particular,

Thus restricting the universe to constructible sets produces a coherent mathematical world with a particularly rigid cardinal structure. But one should not think of constructible sets as merely computable sets. First-order definability over an arbitrary infinite structure is not the same as effective computability. Moreover, the construction proceeds through ordinals far beyond any computable range. Constructibility is a hierarchy of iterated definability, not a finite algorithm. Still, from the resource viewpoint, the distinction between and is very suggestive. One universe permits every subset at every stage. The other admits subsets through a prescribed process of definability.

And the restriction changes what can be proved about the resulting mathematical universe.

Forcing

The constructible universe raises a natural complementary question. If we can obtain a smaller universe by restricting the permitted constructions, can we obtain a larger universe by adding new sets? Forcing is the principal technique for doing this. Let us look at a particularly concrete example.

Suppose is a countable transitive model of ZFC. We want to construct an infinite binary sequence that does not belong to . Since is countable from the outside, we could simply enumerate all its binary sequences and diagonalize against them. But forcing does something stronger: we construct a sequence that satisfies every dense requirement belonging to . This additional property will allow us to extend the entire model.

We construct through finite approximations. A condition is a finite partial function . For example, specifies three digits of our future sequence. We say if extends , so a stronger condition gives us more information. Suppose we want to ensure that the th digit is eventually determined. Consider

Whatever finite information we already have, we can extend it to decide the th digit. More generally, a collection of conditions is called dense if every condition can be strengthened to one belonging to :

We also want our new sequence to differ from every old sequence . For each such , consider

This is dense too: given any finite condition, choose a coordinate not yet specified and assign it the opposite value from . Thus meeting guarantees that our eventual sequence differs from .

Now comes the key observation. Since is countable from the outside, we can enumerate all dense subsets of our forcing notion that belong to . Write them as Starting with the empty condition, construct successively stronger conditions This is possible because each is dense. Since the conditions extend one another, their union is a consistent assignment of digits:

Because we met every , the sequence is defined at every coordinate. Because we also met every for , it differs from every old real. Therefore

But we have accomplished more than simply constructing a new real. We have met every dense requirement belonging to the original model. This is the essential property of a Cohen generic real. The corresponding generic filter allows us to construct a larger model that still satisfies ZFC. The important subtlety is that the enumeration takes place outside . Although contains each of these dense sets, it need not contain the external enumeration of all of them. Indeed, it cannot contain the resulting generic real.

Thus forcing uses a simple idea – satisfying countably many compatible, extendible requirements one at a time to construct an infinite object unavailable in the original universe. What makes this more powerful than ordinary diagonalization is that genericity lets us add the object while controlling the mathematical structure of the enlarged universe. The appropriate generic filter generated by these conditions can be used to construct a larger universe that again satisfies ZFC. There are many technical details involved in defining the extension, interpreting names for its sets, and proving the forcing theorem. But the underlying idea is already visible. We build an infinite object by specifying compatible finite approximations while meeting sufficiently many requirements from the original universe. The original model does not contain the resulting object, even though the construction is possible from a suitable external perspective. This is closely related to our earlier discussion of infinite trees. In both cases, a global infinite object is obtained by satisfying families of constraints on finite approximations.

Forcing turns this principle into a systematic way of constructing and comparing mathematical universes.

Gödel’s constructible universe gives a model of ZFC in which the continuum hypothesis holds. Cohen’s forcing method gives models of ZFC in which the continuum hypothesis fails. For instance, using suitable forcing over a model of GCH, one can construct an extension in which

Thus ZFC does not determine the exact cardinality of the continuum, assuming ZFC itself is consistent. This is a profound result, but its meaning is sometimes misunderstood. It does not say that ordinary arithmetic has become inconsistent or that mathematicians may arbitrarily choose whether any mathematical statement is true. Rather, it says that the axioms of ZFC permit more than one possible mathematical universe, and some assertions involving sufficiently rich infinite collections are sensitive to which universe is being considered.

Indeed, there are strong absoluteness results showing that many mathematical statements remain unchanged across broad classes of models. For example, transitive models of ZFC with the same natural numbers agree on all first-order arithmetic statements about those natural numbers. They agree about such assertions as Goldbach’s conjecture, whether true or false, because the underlying natural numbers and arithmetic operations are the same. But a statement involving quantification over arbitrary subsets of the natural numbers can behave differently, because two universes may possess different collections of such subsets.

This distinction between arithmetic truth and higher set-theoretic existence is one of the organizing themes of descriptive set theory and forcing. There is also a subtle distinction between ordinals and cardinals here. Forcing extensions preserve the ordinals of the ground model. They do not necessarily preserve all cardinalities. An ordinal can remain exactly the same well-ordered set while acquiring a new bijection with a smaller ordinal in the extension. Thus cardinality is sensitive to the existence of functions, whereas ordinal order type is preserved. Again, the difference between the objects and the functions available to compare the objects becomes decisive.

Large Cardinals

We have been building the cumulative hierarchy through all ordinals. But suppose we stop at some very large ordinal . Could the level already behave like a complete mathematical universe? For most ordinals, it will not satisfy all the axioms of ZFC. For instance, if we stop at a successor stage, the level need not contain the power sets of all its elements. If we stop at an ordinal of unsuitable cofinality, it may fail to be closed under set-indexed constructions required by Replacement.

This motivates the notion of an inaccessible cardinal. An uncountable cardinal is strongly inaccessible if it satisfies two conditions. First, it is regular: Second, it is a strong limit:

Let us interpret these conditions. The strong-limit condition says that taking the power set of a smaller cardinal never reaches . The regularity condition says that we cannot approach through a shorter cofinal sequence. Together, they mean that the hierarchy below has very strong closure properties. In fact, if is strongly inaccessible, then

This is an extraordinary fact. A sufficiently large cardinal is not merely a number larger than previously encountered numbers. It marks a stage of the cumulative hierarchy that can itself serve as a model of the entire theory of sets. We can see why the main closure properties should hold. If , its rank is below . Since is a limit ordinal, the power set of also appears below .

For Replacement, suppose a definable function inside assigns objects of to the elements of some set . Because is strongly inaccessible, every set belonging to has cardinality below .

The ranks of the outputs therefore form a collection of fewer than ordinals below . Regularity ensures that these ranks are bounded below . Consequently, the collection of outputs belongs to some level with , and hence belongs to . This is essentially the closure required for Replacement.

Thus inaccessible cardinals provide stages that are large enough and regular enough to support a complete internal universe of set theory. Their existence cannot be proved from ZFC if ZFC is consistent, because the existence of such a cardinal would give a model of ZFC and therefore a proof of its consistency, contradicting Gödel’s second incompleteness theorem. This gives us another notion of strength. A mathematical axiom may assert not just the existence of larger objects but the existence of objects whose structural properties are powerful enough to establish the consistency of weaker mathematical theories. This is the beginning of large cardinal theory.

Conclusion:

Let us now look back at the constructions we have developed. We began with a finite set and observed that taking all subsets can require exponentially more information. We then built the finite cumulative hierarchy and passed to the first infinite level, where all hereditarily finite objects were collected into one set. We introduced ordinals to describe the lengths of transfinite constructions, and discovered that well-founded processes can have arbitrarily complicated ordinal heights, even when their underlying objects are countable. We considered cardinality and found that taking power sets produces an inexhaustible hierarchy of larger infinities. We introduced cofinality, which measures how many approximations are required to approach a limit, and saw that this imposes meaningful restrictions on cardinal arithmetic. We interpreted the axioms of set theory as permitting different kinds of infinitary constructions, and distinguished existence, definability, and computation. Finally, we saw that the same axioms can describe different mathematical universes, that forcing can add new objects to those universes, and that certain sufficiently large cardinals give rise to entire internal models of set theory. All these ideas concern infinity, but they measure fundamentally different aspects of it.

A cardinal number measures the size of a set. An ordinal number measures a well-ordered structure and can serve as the index for a transfinite construction. The rank of a set measures its position in the cumulative hierarchy. A descriptive complexity hierarchy measures the logical operations necessary to specify an object. A computational hierarchy measures the information needed to compute an object. A model of set theory determines which sets, functions, and infinite sequences are available in a particular mathematical universe. And a consistency-strength hierarchy measures which axioms are powerful enough to justify stronger forms of mathematical existence.

These hierarchies are deeply connected, but they should not be confused. For example, a computable tree may have a noncomputable infinite branch. The tree itself is a countable mathematical object with a perfectly effective description, but its global solutions can have higher computational complexity. A countable well-founded tree may have very large countable ordinal rank. Its cardinality is small, while the transfinite complexity of its pruning process is substantial. A universe may contain every natural number but omit some subsets of the natural numbers. The natural numbers are unchanged, yet the collection of real numbers is different. A set can be uncountable in one universe and countable in another because a new bijection has become available. And a sufficiently inaccessible cardinal can mark a level of the cumulative hierarchy that satisfies the whole of ZFC, even though the cardinal itself is only one stage in a still larger ambient universe.

There is therefore no single meaningful quantity that measures how complicated an infinite mathematical object is. We must ask what aspect of the object we want to understand. How many possibilities are there? How many stages are needed to build it? How much information is required to describe it? Can it be computed? Which axioms establish its existence? Does its existence remain unchanged when we enlarge the mathematical universe? These are different questions of “complexity”, and set theory provides different tools for answering them.

I want to end with a few questions that illustrate how the preceding ideas lead naturally into deeper mathematics. First, when does finite compatibility imply an infinite solution? König’s lemma gives one answer for finitely branching trees. But there are computable trees with no computable branches, and there are higher-cardinal trees with no branches of the expected length. Understanding exactly which compactness principles are available leads to infinitary combinatorics, reverse mathematics, and large cardinals. Second, how complicated can the definition of a subset of the real numbers become? Beginning with open sets, we can apply complements and countable unions to obtain Borel sets. Iterating these operations through all countable ordinals produces a rich hierarchy. Allowing existential quantification over real numbers leads to analytic sets, whose structure is controlled by infinite trees and descriptive set-theoretic ranks. The corresponding hierarchy of definability interacts with measure theory, category, infinite games, and absoluteness.

Third, how far can computational resources be iterated? The halting problem provides information that ordinary computation cannot produce. We can iterate the Turing jump finitely many times, then through computable ordinal stages, leading to the hyperarithmetic hierarchy and the Church–Kleene ordinal . This gives a concrete way of relating transfinite recursion to computational complexity. Fourth, how do we control the effect of adding new sets? Forcing allows us to add real numbers and change the structure of the continuum. But different forcing notions preserve different properties. Some preserve cardinalities, some collapse cardinals, and some satisfy powerful preservation theorems. Understanding these phenomena requires a combination of finite combinatorics, infinite trees, elementary submodels, and carefully designed generic constructions.

Finally, what principles determine which mathematical universe should be considered? The constructible universe, forcing extensions, inner models, and large cardinal axioms offer different approaches to understanding the possible structure of the universe of sets. The resulting questions are not merely formal. They concern the relationship between mathematical objects, the language used to describe them, and the principles we accept as sufficient to establish their existence.

The most important conceptual shift, I think, is that infinity should not be viewed merely as the result of allowing a counting process to continue without end. There is a distinction between having arbitrarily large finite objects and possessing their completed infinite totality. There is another distinction between possessing an infinite set and possessing all its subsets. There is yet another distinction between having those subsets available and being able to describe or compute them. And there is a further distinction between the objects present in one mathematical universe and those present in an extension. Each of these distinctions creates new mathematical phenomena. The cumulative hierarchy gives one organizing picture: begin with nothing, construct sets out of previously available sets, take unions at limit stages, and continue through the ordinals. The hierarchy of cardinals measures how the number of available possibilities grows. Definability and computability measure which of those possibilities can be identified or produced using particular resources. Model theory and forcing reveal that different universes can contain different collections of possibilities while satisfying the same foundational axioms. In this sense, set theory is not simply the mathematics of infinite collections. It is the mathematics of what it means for an infinite object to exist, how it can be built, how complicated its construction can become, and how much of that existence is determined by the axioms we begin with. That is the perspective from which the more advanced subjects descriptive set theory, infinitary combinatorics, forcing, inner model theory, and large cardinals begin to fit together as different parts of one mathematical theory.