m522
⚠️EXPERIMENTAL WORK IN PROGRESS⚠️

Contents

 Introduction

This course is about set theory, and its use in the study of the real line. By way of motivation, consider the question of measuring the size of a given set of real numbers. The word "size" can mean many different things, depending on the context. To see what I mean, consider these three important examples.

In this course we will ask the natural question: How do these three kinds of size compare with one another? In answering this question, we will discover numerous relationships between measure and category, with the diagram of these relationships revealing a beautiful structure.

Our investigation of measure and category will lead us to a number of statements that are independent of the axioms of set theory. This means that such statements cannot be proved true or false using the usual axioms of set theory. The most central example of such a statement is the continuum hypothesis (CH), which asserts that the set of all real numbers has cardinality equal to the first uncountable cardinal number. Cantor initially posed this problem in 1878. In 1940 Gödel showed the axioms of set theory can't disprove CH, and in 1965 Cohen finally showed that the axioms of set theory can't prove CH.

In his proof of the latter half of the independence of CH, Cohen developed a tool for building models of set theory called forcing. Far from being an isolated application, since then forcing has become a standard tool for establishing independence results. We will develop the machinery of forcing and give a number of such applications.

With the tool of forcing in hand, we will return to the notions of measure and category. We will find that there are numerous cardinal numbers surrounding the zero length sets and the meager sets whose values, like the size of the set of all real numbers, are also independent of the axioms of set theory.

 Category and measure
The real number system Definition 1

The real number system is a complete ordered field. That is, it is a set together with distinguished elements , operations and an ordering satisfying the following rules:

  • It is a field: it satisfies the associative, commutative, and distributive laws, is the additive identity and is the multiplicative identity;
  • It is an ordered field: is a strict total order, implies , and if is positive then implies ;
  • It is complete: if has an upper bound, then it has a least upper bound (supremum).
 Remark 1

It is not difficult to prove that any two complete ordered fields are isomorphic to each other, so it makes sense to define the real number system as the unique such object.

 Remark 2

The above definition of the real number system is an abstract, axiomatic definition. That is, it tells you how real numbers behave, but it leaves it up to your imagination what a real number really is. In fact, we have some choice in this matter. For example we can view the real numbers as decimal strings or binary strings. For our set-theoretic purposes, all that matters is that we give one construction of the real numbers that works.

The first to give an explicit and rigorous construction of the real number system was Dedekind, who did so in the 19th century. Here is how his construction worked. First we will take the construction of the rational number system for granted. It is simply the set of fractions whose numerator is an integer and whose denominator is a nonzero natural number.

The key insight is to realize that each real number has a cut in the rational numbers associated with it: the set of rational numbers that are strictly less than . This association should be bijective: If the least upper bound property is true, then any such cut gives rise to a real number as the supremum of the cut. And if two real numbers are different, then they should give rise to different cuts.

So all we have to do to define real numbers was to define cuts. To avoid circularity, we should axiomatize cuts without referring to real numbers at all. A cut in the rational numbers is a subset satisfying three properties:

To complete the construction one must say how the operations and relation can be defined just in terms of cuts, and then prove that they satisfy the axioms of a complete ordered field. For example, one defines to be the supremum of the set , and one defines if and only if and . We omit the details of verifying that these definitions work.

Remark 3

It is interesting to compare Dedekind's construction with the modern decimal number construction (which we omit). The decimal number construction is practical for calculations, but has some oddities. For example some numbers have two decimal representations, like and . Also we made an arbitrary decision to use decimal expansions as opposed to any other base. Dedekind's construction is beautiful because it is completely uniform and does not involve any arbitrary decisions.

 Definition 2

A set of real numbers is said to be countable if its elements can be enumerated using natural number indices. In other words, is countable if there exists a sequence such that .

Note that this definition implies that finite sets are countable. If we wish to emphasize that a particular countable set is infinite, we will use the term countably infinite. A set that is not countable is called uncountable. We now give Cantor's famous proof of the fact that the set of all real numbers is uncountable. The argument goes by contradiction and uses a recursive construction to reach a contradiction one step at a time. Such arguments are often called "diagonal", for reasons we shall see later on.

Theorem 1 Cantor The set of all real numbers is uncountable. Proof.

Suppose towards a contradiction that the set of all real numbers is countable. Then there exists a sequence such that . Our strategy will be to inductively construct a decreasing sequence of closed intervals such that for all , . Then if lies in the intersection of these intervals, cannot be equal to for any , a contradiction.

The construction itself is straightforward. For the base case let be any interval which omits . For the inductive step, if has been defined, let be any subinterval of which omits .

We can now find a point in the intersection of the using the completeness property. First observe that since for all , the set of left endpoints is bounded above by any and all of the right endpoints . By the completeness property, the set of left endpoints has a least upper bound . Since is an upper bound for , we have for all . Since is the least possible upper bound for , we have for all . Therefore we have for all .

Since lies in for all , and since we chose in such a way that it omits , we know that for all . This contradicts the hypothesis that , and concludes the proof.

This argument appears in one form or another numerous times throughout elementary analysis and set theory. We shall next see it in the proof of the Baire category theorem.

Exercise 1

With the definition of for Dedekind cuts, show that addition is commutative and associative.

 Exercise 2

Define multiplication for Dedekind cuts, and show that it agrees with multiplication for rational numbers. [Hint: consider four cases when are negative or nonnegative.]

 Exercise 3

Let be a set of real numbers containing a positive-length interval. Show that is uncountable.

 Notes 1

Although the material in this section is standard and can be located in most any analysis book, an excellent introduction is Understanding Analysis by Stephen Abbott. For the completeness axiom see Abbott, Section 1.3. For Cantor's theorem see Abbott, Section 1.4. For Dedekind cuts see Abbott, Section 8.4.
Baire category theory Definition 1

A set of real numbers is said to be nowhere dense if every positive-length interval contains a positive-length interval such that is disjoint from .

 Example 1

Any finite subset of is nowhere dense. The set is nowhere dense. In fact, any discrete set is nowhere dense (here, is discrete if every point of is isolated). The set of rational numbers whose numerator is and whose denominator is a power of is not nowhere dense, because such a number can be found in every positive-length subinterval of .

Note that nowhere dense sets need not be countable. The classical Cantor middle thirds set is an archetypal example of a nowhere dense set. Recall that the Cantor set is defined as follows. Begin with the set . Let be the set with its open middle third removed. Let be the set with the open middle third removed from each component of . Refer to fig-cantor-set$ for a picture of these first few sets. Recursively, let be constructed from by removing the open middle third from each component of . Finally the Cantor set is defined to be . We will see in a later section that the Cantor set is uncountable.

Proposition 1

The Cantor set is nowhere dense.

 Proof.

First compute that the sum of the lengths of all of those middle thirds removed in the construction of the cantor set is exactly (Exercise 1). It follows from this that does not contain any positive-length intervals. Now if is any positive-length interval, then must contain a point . Now note that is closed because it is an intersection of closed sets, and hence is open. Thus there is an open interval centered at such that . Shrinking the radius of if necessary, we can suppose that . This shows that is nowhere dense.

The terminology "nowhere dense" may sound strange at first, but it is justified by the following fact.

Proposition 2

Let be a set of real numbers. The following are equivalent:

  1. is nowhere dense;
  2. (the topological closure of ) has no interior;
  3. for every nonempty open set , we have that is not dense in .

The proof is requested in Exercise 2.

Theorem 1

The class of nowhere dense sets is closed under the operations of subset, union, and closure.

 Proof.

Preservation to subsets is immediate from the definition.

For preservation to unions, suppose that are nowhere dense and let be a positive-length interval. Since is nowhere dense, there is a positive-length interval . Since is nowhere dense there is a further positive-length interval . It follows that

This establishes that is again nowhere dense.

Preservation to closures is immediate from condition (b) of Proposition 2, but we can also give a direct argument. Let be nowhere dense and let be a given positive-length interval. Since is nowhere dense there is a positive-length interval such that . Removing endpoints if necessary, we may suppose that is open. It follows that (recall that since is the intersection of all closed sets containing , we have that is the union of all open sets disjoint from ). This shows that is nowhere dense.

 Remark 1

It is easy to see that the class of nowhere dense sets is not preserved to infinite unions, even countably infinite ones. For example, the set of rational numbers is countable, and therefore it is a countable unions of singletons: . Each singleton is clearly nowhere dense, so is a countable union of nowhere dense sets, but is dense.

 Definition 2

A set of real numbers is called meager if it is a union of countably many nowhere dense sets. A set is called comeager if is meager.

In principal it is possible that this notion is completely moot in the sense that maybe every set of real numbers is meager according to this definition. The Baire category theorem says that this is not the case. In fact, we will soon see that meager sets are rather paltry as the name implies.

Theorem 2 Baire category theorem

The set of all real numbers is nonmeager. In fact, if is a positive-length interval then is nonmeager.

 Proof.

The proof is very similar to Cantor's proof of Theorem 1. Let be a positive-length interval and suppose towards a contradiction that is meager. Then there exists a sequence of nowhere dense sets such that . We will inductively construct a decreasing sequence of closed subintervals such that for all , .

The induction is again straightforward. First apply the definition of being nowhere dense to obtain . Inductively apply the definition of being nowhere dense to to obtain . (Each time we may shrink the newly obtained interval slightly to suppose that it is closed.)

We can now argue just as in the proof of Theorem 1 that there exists a point . It follows that , which contradicts the assumption that , and completes the proof.

 Remark 2

Baire category theory gets its name from the above theorem, and the fact that meager sets used to be called "first category". Nonmeager sets used to be called "second category".

 Theorem 3

The class of meager sets is closed under the operations of subset and countable union.

We remark that the meager property is not necessarily preserved to the closure. In fact is meager if and only if is nowhere dense.

As a consequence of the Baire category theorem, for any set it is possible to assign one of three distinct "sizes":

We should verify that no set of numbers can be both meager and comeager. Indeed, suppose that both and were meager. Then by Theorem 3 their union would be meager, contradicting the Baire category theorem.

We should also verify that there exists sets of numbers that are neither meager nor comeager. Indeed, if is any bounded positive-length interval then by the Baire category theorem is nonmeager, and since also contains a bounded interval, is also non-comeager.

Exercise 1

Compute the sum of the lengths of all of the intervals removed from in the construction of the Cantor set. What if some other fraction is removed at each stage?

 Exercise 2

Prove Proposition 2.

 Exercise 3

We have observed that unlike the nowhere dense property, the meager property is not necessarily preserved to the closure. Prove that if is meager, then was nowhere dense to begin with.

 Notes 1

For more on the Cantor set see Abbott, Section 3.1. For the Baire category theorem see Abbott, Section 3.5. For Baire category theory generally see Oxtoby, Chapter 1.
Lebesgue measure theory

Classical measure theory aims to try to extend the length function on intervals to be defined on more complicated sets. For example, if a given set is a finite or even countable union of intervals, then it is appropriate to take the sum of the lengths of the components. But what about more unwieldy sets like the Cantor set? This was known as the measure problem: to construct a measurement function , defined on sets of real numbers and valued in , satisfying:

  1. agrees with length: if is an interval then
  2. translation invariance: for all sets and real numbers
  3. countably additivity: if is a sequence pairwise disjoint sets then

Perhaps surprisingly, the conditions (a)--(c) are mutually contradictory and so no such measurement function exists! Here is Vitali's simple example of a contradiction arising from these requirements. Regard as an additive subgroup of and consider the cosets of , that is, sets of the form . Let be a set of coset representatives, that is, contains exactly one element from each of the cosets. (It is always possible to choose a coset representative in because is dense.)

Then the translations for form a countable sequence of pairwise disjoint sets that cover all of . In fact, if we let then the translations for already cover all of . We can then infer from (a) and (c) that lies between and . But on the other hand, by (b) and (c) we have that

This is a contradiction because an infinite sum of a single constant value can be equal only to either or , and so cannot lie between and .

Remark 1

We observe that the axiom of choice was explicitly used in Vitali's construction of the set above. In fact, it is known that the use of the axiom of choice is necessary to build a counterexample.

The contradiction described above is typically resolved not by dropping one of the conditions (a)--(c), but rather by dropping the requirement that is defined on all sets of real numbers. The justification for this decision is that sets like the constructed above should be regarded as pathological, and we don't usually need to measure them in applications.

Let us naïvely begin to construct a measure that is at least defined on reasonable sets. First, condition (a) implies we should let for any interval . Next, if is a union of disjoint intervals , then condition (c) implies we should let . Third, if is an intersection of sets where is defined and finite, then it is natural to define . We now observe that all three of the above simple cases fit into the rule given by the following key formula:

The next result states that this rule for defining actually works for all sets that are reasonably constructible. Recall that a Borel set is one that can be constructed by beginning with the intervals and then executing countably many countable unions or intersections.

Theorem 1 Carathéodory's extension theorem

The measure defined in Equation~ satisfies conditions (a) and (b), and additionally satisfies condition (c) when applied to Borel sets.

 Proof of conditions (a) and (b) only

For condition (a), let be an interval. It is clear that , since itself is an interval covering . For the other direction, we will show that implies . Then taking the infemum over all such coverings this allows us to conclude that .

Let us first handle the case when is closed and bounded, and all of the are open intervals . Then since is compact, is covered by just finitely many of the , without loss of generality we may assume they are indexed . Now after further renaming or removing intervals from the list, we may suppose that covers the left endpoint of , each covers the right endpoint of , and covers the right endpoint of . We can now compute that

If is not necessarily closed and the are not necessarily open, then we look instead at and . Then the cover all but a countable subset of , so for any we can find additional open intervals with covering these missing points. Now the previous argument shows that . Using the geometric series formula we obtain . Letting we have the desired result.

Finally if is not bounded, we let be a sequence of bounded subintervals of such that . The above result implies that , and letting we once again achieve the desired result. This concludes the proof of condition (a).

Condition (b) follows directly from the fact that the length function is translation invariant, and the definition of depends only on .

For the proof that satisfies condition (c), we refer the reader to any standard measure theory text.

From now on we will ignore the full power of measure theory to assign a real number measure to any Borel set, and focus only on the specific value zero. Sets whose measure is zero are called null sets, and for convenience we extract the definition of null set from the above definition of arbitrary measure.

Definition 1

A set of real numbers is null if for all there exists a sequence of intervals such that and .

 Example 1

The Cantor set is null. Indeed, we have already computed that the sum of the lengths of all intervals removed from in the construction of is equal to . Since has measure , it follows from additivity that must have measure .

The notion of null set bears many similarities with the notion of meager set. As was the case with meager sets, the notion of a null set allows us to assign to any given set one of three simple "sizes": null, conull, or nonnull and non-conull. Moreover, null sets satisfy an analog of the Baire category theorem and the preservation properties of meager sets.

Corollary 1

The set of all real numbers is not null. In fact, if is any positive-length interval then is not null.

 Corollary 2

The class of null sets is closed under the operations of subset and countable union.

Corollary 1 is immediate from condition (a) of Theorem 1. Corollary 2 is immediate from condition (c) of Theorem 1.

Exercise 1

Prove that condition (c) of a measure implies monotonicity: if then .

Exercise 2

Prove that condition (c) of a measure implies continuity from above: if is a decreasing sequence of sets, is finite, and , then .

 Exercise 3

Give a proof directly from Definition 1 that the Cantor set is null.

 Exercise 4

Give a proof directly from Definition Definition 1 that the class of null sets is closed under countable union.

 Notes 1

Our presentation of Vitali's construction follows Folland, Section 1.1. Our proof of Theorem 1, part (a) follows Oxtoby, Chapter 1. For a proof of part (c), see Folland, Section 1.4.
Sets, orderings, and cardinality

So far we have seen sets that are finite, countable, and uncountable. If a set is finite, then there is a natural number that tells us exactly how many elements has. If is countable, we understand that it has exactly as many elements as there are natural numbers. But if is uncountable, is that all that needs be said or is there some kind of number that tells us just how uncountable it is?

In this section we discuss the notion of "cardinality" of a set , which replaces the notion of "number of elements" in the case when is infinite. Notationally, we write for the cardinality of . As we shall see, when is finite will be a natural number. When is countable will take the value (called aleph zero, or aleph nought). And when is uncountable will take one of the values and so forth.

In the next section we will describe exactly what the 's are. But first it turns out that we can give many of the most important facts about cardinality without ever defining the cardinal numbers precisely.

Definition 1

Let and be sets. We say that if there is a bijective function , we say that if there is an injective function , and we say that if and also .

 Remark 1

In the above definition, we managed to define all of the comparisons between cardinals without ever defining the cardinal itself. For most practical purposes, this definition is sufficient.

Our first result confirms that there are many different uncountable cardinalities. Recall that if is a set, then the power set of , denoted , is the set of all subsets of .

Theorem 1 Cantor

If is any set, then .

 Proof.

It is clear that , since the map is an injection from into .

To see that there is no bijection between and , let be any function. Then build the set of all elements such that . We claim that is not in the range of , and therefore that is not a bijection.

To see this, suppose towards a contradiction that there exists such that . Then by the definition of , we have that iff . And since we can write this as iff , which is a clear contradiction.

 Remark 2

The classical argument above is given the name "diagonal" because of the key formula in the proof: . The idea is that if you were to shade the set of pairs such that that , then the set would be built by taking the unshaded elements of the diagonal of the plane.

 Definition 2

Let be a set (or class).

  • A partial ordering of is a binary relation satisfying: (reflexive) ; (antisymmetric) ; (transitive) .
  • A total ordering of is a partial ordering such that for all either or .
  • A well-ordering of is a total ordering such that every subset has a -least element .
 Remark 3

The well-order property may seem obscure at first, but finding a least element is precisely what is needed in induction arguments. It is what allows us to say "otherwise, let be the least counterexample".

In the next few results, we essentially show that the cardinals are well-ordered by . Note that reflexivity holds because the identity function is an injection from into itself, and transitivity holds because the composition of two injections is an injection. The following result establishes antisymmetry.

Theorem 2 Cantor--Schröder--Bernstein

If there are injections and then there is a bijection .

Proof.

Replacing with , we may suppose that that . Then we have

Now can be written as the union of the successive differences of these sets, together with the intersection of them all:

Meanwhile, gives bijections

It follows that the map

is a bijection from to .

 Remark 4

This result also gives a simple recipe for checking whether two sets have the same cardinality. For example, to show that there is a bijection between and it is much easier to construct two injections than a single bijection.

The next result shows that the cardinalities are totally ordered. In the proof we will need Zorn's lemma: If is a partially ordered set such that every totally ordered subset has an upper bound, then has at least one maximal element. Zorn's lemma is used perennially in analysis, and it is a consequence of the axiom of choice.

Theorem 3

If are sets then either there is an injective function from to or an injective function from to .

 Proof.

Consider the family of all injective functions whose domain is a subset of and whose range is a subset of . Then is partially ordered by extension of functions, and it is easy to check that this ordering satisfies the hypothesis of Zorn's lemma. Thus there is a maximal element , and since it is maximal either the domain of is all of or the range of is all of . In the first case is an injection from to , and in the second case is an injection from to .

Finally we show that the cardinals are well-ordered. One technicality arises here that did not in the last four properties. To check that the cardinals are well-ordered, we should check that any collection of sets has a minimal element, and that collection need not itself be a set. (Remember: the set of all sets isn't a set!)

Theorem 4

Let be a class of sets. Then there exists that injects into all other sets .

 Proof.

We argue very similarly to Theorem 3, but in order to apply Zorn's lemma we must first suppose that really is a set. Fix any element and let

This time is partially ordered by coordinatewise extension of functions. By Zorn's lemma there is a maximal element , and since it is maximal either the domain is all of or the range of one of the functions is all of . In the first case is an injection from to for all . In the second case, fix such that . Then for any , the composition is an injection from to , so is as desired.

In the general case when is a class, we can reduce to the set case as follows. Fix an element and let denote the collection of subsets of that are in bijection with some element of . Since is a set, we can find which injects into all elements of . It follows that injects into all other elements of too. Indeed if and does not inject into , then by Theorem 3, injects into . It follows that is in bijection with a subset of and hence injects into after all.

Although we still can't be fully rigorous about the meaning of the symbols , the well-ordering property helps justify the use of these symbols. Essentially is the least cardinality greater than , is the least cardinality greater than , and so forth. In the next section, we will make this fully precise.

Exercise 1

Show that there is a bijection between and .

 Exercise 2

Which of the following categories satisfy the analog of the Cantor--Schr\"oder--Bernstein theorem? (That is, monomorphisms implies isomorphism .) linear orders with order-preserving maps; groups with group homomorphisms; topological spaces with continuous maps; topological spaces with piecewise continuous maps.

 Exercise 3

We used the well-ordering principle together with Cantor's theorem to argue that there are uncountable ordinals. Here is another way: show that the set of isomorphism equivalence classes of well-orderings of is itself naturally well-ordered, and that this well-ordering is uncountable.

 Notes 1

Our proof of Theorem 4 follows and extends the proof given in Chaim Samuel Hönig, Proof of the well-ordering of cardinal numbers. For a more detailed proof of Theorem 2, see Kunen (Foundations), Section I.10.
Ordinal numbers and cardinal numbers

Ordinal numbers play a central role in set theory, including both cardinality theory and forcing. While cardinal numbers are needed to measure the size of an infinite set, ordinal numbers are needed to measure the length of an infinite well-ordered set. The ordinals can be used to extend the notion of counting into the infinite, and also to give a formal definition of the cardinals described in the previous section.

The initial goal in defining the ordinals is to provide a collection of well-ordered sets such that for any given well-ordered set there is one and only one ordinal such that is isomorphic to . For finite well-ordered sets, we can write such a definition explicitly:

This construction can be summed up in one recurrence: . The first infinite ordinal, called or , is simply the union of all the finite ordinals. The process can then continue; the successor of is the ordinal .

Intuitively, infinite ordinals are all constructed in this fashion. If is any ordinal then its successor is , and after infinitely many such steps we take a union. Unfortunately this prescription is not rigorous because it is circular; we cannot make a definition like . Instead we have the following more technical characterization.

Definition 1

A set is an ordinal if it satisfies the properties:

  • is well-ordered by the relation (or more precisely by the relation defined as -or-equal);
  • is transitive: if then .
 Remark 1

The first condition ensures that the ordinals are in fact well-ordered; the order relation is simply the most convenient one available in set theory. The second condition ensures that the ordinals have no "gaps"; for instance the set is well-ordered but not an ordinal.

The following fundamental facts about ordinals together imply that Definition 1 achieves our initial goals in defining the ordinals.

Theorem 1
  • The class of all ordinals is itself transitive and well-ordered by .
  • If is a well-ordered set then there exists a unique ordinal such that is isomorphic to .\qed

An ordinal is said to be successor ordinal if it is of the form for some ordinal . Otherwise is said to be limit ordinal. The first part of Theorem 1 allows us to show that successor and limit are appropriate names.

Proposition 1

If then is the least ordinal greater than . If is a limit ordinal then is the union of the ordinals that came before it.

 Proof.

It is easy to check is indeed an ordinal (it is transitive and well-ordered by ). Since the ordinals are well-ordered we may let be the least ordinal greater than ; we want to show that . If this were not the case, then by totality we would either have or . In the first case either or , which contradicts that is greater than . The second case contradicts that is the least such.

Next let be a limit ordinal, and let be the union of all . Since is transitive we easily have that . On the other hand if then by the previous paragraph and since is limit we must have . Thus and it follows that .

As we have hinted, although ordinals naturally measure the length of well-orderings, they can also be used to measure size . Recall that the axiom of choice implies the well-ordering principle, which states that any set admits a well-ordering . Combining this with Theorem 1, it follows that any set is in bijection with at least one ordinal. Different well-orderings of can lead to different ordinals, so we make the following definition.

Definition 2

If is any set, then is the least ordinal such that is in bijection with .

Thus a cardinal is a special type of ordinal. Most ordinals will not be cardinals, since for instance if is in bijection with then clearly it is also in bijection with . We give names to the ordinals which are cardinals: The first infinite cardinal is , the first uncountable cardinal is , the next least cardinal is , and so forth.

The pattern continues transfinitely as well, with defined for every ordinal . Officially, these higher cardinals are defined using transfinite recursion. Just as natural numbers are used to index traditional recursion, ordinals are used to index transfinite recursion. While ordinary recursion requires a special "base" case at , transfinite recursion requires a "limit" case at each limit ordinal.

Definition 3

The first infinite cardinal is . If is defined then is the least ordinal that is not in bijection with . If is a limit ordinal and has been defined for , then .

 Exercise 1

Show that if is an infinite cardinal, then is a limit ordinal.

 Exercise 2

Use Zorn's lemma to prove the well-ordering principle.

 Exercise 3

If is an infinite set, show that is equal to for some .

 Notes 1

This material on ordinals and cardinals can be found in any introductory set theory textbook. For ordinals, see for instance Section 1.7 of Devlin's The joy of sets. For cardinals, see Section 3.6 of the same text.
The topology of Cantor and Baire space

If is a countable set then denotes the space of all sequences with values in , that is, functions from to . We can endow with a topology by regarding as discrete, as a product of countably many copies of , and using the product topology. Officially a basic set in the product topology has the form

where are distinct and are open. However in our case we can make two simplifications: since is countable we can replace with , and since is discrete we can suppose the are singletons. Putting this all together, we obtain a basis consisting of all

where is an element of for any .

The two most important examples of sequence spaces are the Cantor space and the Baire space .

Proposition 1

The Cantor space is homeomorphic to the Cantor middle thirds set. The Baire space is homeomorphic to the set of irrational real numbers.

 Proof.

We give the proof in the case of the Cantor space, and a brief hint in the case of the Baire space.

The Cantor middle thirds set has a natural description in terms of ternary expansions. If then lies in the Cantor set if and only if it has a ternary expansion that does not contain the digit . Thus there is a simple bijection given by replacing the 's in with 's:

The map is continuous: if then there exists such that if we round down at its th digit then it is still and if we round it up at its th digit then it is still . It follows that if , then we have . Finally recall that a continuous bijection between compact spaces is always ahomeomorphism.

For the Baire space, it is common to use the values of as the entries in a continued fraction:

With some elementary number theory, it is possible to verify that this map is a bijection onto the set of irrational numbers, and even a homeomorphism.

This result also implies that admits a complete metric, because the Cantor set is a closed and hence complete subspace of . In fact, any sequence space is completely metrizable. For an example of a complete metric, given such that , let be the least natural number such that and set .

Proposition 2

The metric on defined above is complete.

 Proof.

Let be a Cauchy sequence in . We can inductively construct an increasing sequence of indices such that for all and we have . In other words for the all agree, for the all agree, etc. Thus we may define an element by letting this agreed upon value. Now it is easy to check that .

 Remark 1

While the metric on defined above is fairly natural, it is not canonical. For example, any reordering would give rise to a different compatible metric.

We now discuss a variety of topological properties in the context of sequence space. The closed sets, nowhere dense sets, and compact sets all have special descriptions in sequence space.

To begin, let denote the set of finite sequences of elements of . This set is partially ordered by the subset relation, but we emplay special terminology in this case. If we say that is an initial segment of or alternatively that is an extension of . We use the same terminology if , , and : is a finite initial segment of , or is an infinite extension of .

A subset is said to be a tree if it is closed downward, that is, closed under initial segments. An element is said to be a branch through if all of its finite initial segments lie in . We denote by the subset of consisting of all branches through .

Proposition 3

A subset is closed if and only if there exists a tree such that .

 Proof.

Given any set , we let be the tree consisting of all such that (that is, all initial segments of elements of ). We will show that the set of all branches through the tree is precisely the closure of , which implies the desired result. For this, note that lies in the closure of if and only if every open neighborhood of of meets . This is equivalent to the statement that for every initial segment , . Finally, this is equivalent to the statement that is a branch through .

In previous sections we have defined nowhere dense subsets of in terms of intervals. In fact we can define nowhere dense subsets of any topological space in terms of open sets: is nowhere dense in if every open set has an open subset disjoint from . This definition can even be made with basic open sets in place of open sets. Thus we have the following characterization.

Proposition 4

is nowhere dense if and only if for every there exists such that and is disjoint from .

Meager sets are now defined in the same way as before: is meager if it is the union of countably many nowhere dense sets. Our proof of the Baire category theorem for the real numbers naturally extends to arbitrary complete metric spaces.

Theorem 1 Baire category theorem

If is a complete metric space then is not meager. Moreover if is a nonempty open subset of then is not meager.\qed

In particular the notions of meager and comeager sets make perfect sense in both and . The proof of this general Baire category theorem is nearly identical to the proof of Theorem 2 with closed intervals replaced by closures of basic open sets . The completeness of is used to verify there is a point .

Exercise 1

Check that the topology on with basis consisting of all is really the same as the product topology.

 Exercise 2

Give an example of an open subset of which is not closed.

 Exercise 3

Show that the sequence space is homeomorphic to the cartesian product with itself .

 Notes 1

For introductory material on the combinatorics and topology of sequence space, see Kechris, Sections 2A and 2B. For another proof that the Baire space is homeomorphic to the irrationals, see Section 1 of Miller, Descriptive set theory and forcing.
Cardinal characteristics
-compactness in Baire space

As we have discussed in the introduction, the exact cardinal value of the size of the set of all real numbers is independent of the axioms of set theory. That is, if we write then we know for some , but we do not know which one. Here stands for continuum. Since is also equal to the cardinality of Cantor space, it is also often denoted . In this section we discuss several cardinal values other than that arise from the special topology of the Baire space .

We have measured the size of sets of real numbers using cardinality, category, and measure. We now introduce a fourth notion in the Baire space. A set is said to be -compact if it is the union of countably many compact sets.

Like the meager and null sets, the class of -compact sets is closed under countable unions. While the class of -compact sets is not closed under subsets, if one wishes they can simply consider instead the class of subsets of -compact sets instead. In a moment we shall show that the whole Baire space is not -compact, so that -compactness really is a good notion of a small set.

Remark 1

Among the spaces we've explored so far, the notion of -compactness only works in the Baire space. That's because both and both have the property that the whole space is -compact: is the union of closed bounded intervals, and is itself compact.

We now introduce for the first time the process of associating cardinal characteristics to a class of sets. First we denote by the class of all sets such that is a subset of some -compact set.

Definition 1
  • The cardinal is the least cardinality of any set which is not .
  • The cardinal is the least cardinality of any family of subsets of whose union covers all of .

Our next result will generalize Cantor's theorem by showing that the cardinals and are uncountable lower bounds for the value of the continuum. First we need the following characterizations of compact sets in Baire space.

Lemma 1

A subset is compact if and only if it is a closed subset of some product of bounded intervals .

 Proof.

We will use the fact that a countable product of finite metric is compact (this follows from Tychonoff's theorem, but it's easy to check directly too). Since a closed subspace of a compact metric space is again compact, it follows that any closed subset of a product is compact. For the converse suppose that is compact, and suppose towards a contradiction that is not contained in a product of bounded intervals. Then there exists some coordinate such that contains a sequence of elements with . Then clearly does not have any convergent subsequence, contradicting that was compact.

 Theorem 1

We have and .

 Proof.

It is clear that because every countable set is , being the union of its points. To see that it is enough to show that itself is not -compact. So suppose towards a contradiction that where each is compact. Then by the Baire category theorem, at least one of the must have a nonempty interior, say . But is not contained in a product of bounded intervals, so by Lemma 1 this contradicts that is compact.

To show that , suppose a countable family of -compact sets covered all of . Then a countable family of compact sets would also cover all of , again contradicting that is not -compact. Finally it is clear that , since the whole space is the union of its points and .

In fact we'll see shortly that .

Remark 2 It follows from the proof of Theorem 1 that every set in is meager. Indeed, compact sets are closed, and moreover since they are bounded they cannot contain any basic open sets . It follows that compact sets are nowhere dense, and hence -compact sets are meager. This in turn implies the Baire category property for -compact sets: is not -compact and any basic open neighborhood is not -compact.

We now work establish a key relationship between the cardinals and , and the combinatorics of the Baire space. To begin, we can partially order Baire space by iff for all , we have . We also have the more versatile eventual domination order: if almost everywher, that is, there is some such that for all we have . Of course eventual domination is not a partial order because only implies that and agree almost everywhere, which we denote by .

Definition 2
  • A subset is said to be a dominating family if for all there exists such that . The dominating number , is the smallest cardinality of any dominating family.
  • A subset is said to be an unbounded family if there is no single such that for all . The unbounding number is the smallest cardinality of any unbounded family.

The following result records the relationship between these two cardinal values.

Proposition 1

We have .

 Proof.

We begin by showing that is uncountable. For this, it is enough to show that every countable family is bounded by some . So let be a countable family and enumerate its elements . To construct the bound , we use a diagonalization process similar to the proof of Cantor's theorem. More specifically, we define so that it dominates :

Then for each we have for all , and therefore , as desired.

To show that , it is enough to show that every dominating family is unbounded. Let us establish the contrapositive: if is bounded, say by , then every satisfies . Letting , it follows that every satisfies , and hence that is not a dominating family.

Finally, since is itself a dominating family, and .

We are now ready to state the connection between sets and the eventual domination ordering.

Theorem 2

We have and .

 Proof.

Let us say that a family is -bounded if there is an such that for all , and that is -bounded if there is an such that for all . Then it is clear from Lemma 1 that a family is -bounded if and only if is contained in a compact set. To establish the first equality in the theorem, it suffices to show that a family is -bounded if and only if is contained in a -compact set.

For this, suppose that is -bounded by . Let enumerate all finite modifications of , so that for all there is some such that . It follows that is contained in the -compact set of functions that are -bounded by some . Conversely, suppose that , where each is compact. Then for each there exists some such that is -bounded by . Since , there exists such that for all . It follows that is -bounded by .

The second equality is similar. If is a dominating family then consider the collection of all for a finite modification of an element of . This latter collection is a family of compact sets that covers all of . Conversely if is a family of compact subsets of that covers all of , then each is -bounded by some . It follows that the collection of all is a dominating family.

 Exercise 1

Prove directly that a countable product of finite metric spaces is compact.

 Exercise 2

Find an example of a meager subset of which is not .

 Exercise 3

Consider the space with the product topology. Is it -compact?

 Notes 1

The conection between and the domination relation is presented in Section 2 of Blass, Combinatorial cardinal characteristics of the continuum.
Ideals and their cardinals

Let be any one of the three spaces , , or . An ideal on is a subset which is closed under subsets and (finite) unions. We think of an ideal as any collection of sets that captures some quality of smallness in subsets of . Of course, the whole space should not be small, so we are only interested in proper ideals, i.e.\ those do not contain .

An ideal is called a -ideal if it is additionally closed under countable unions. In the past several sections, we have discussed three key notions of smallness and each one is a -ideal.

As was the case with , we can associate cardinal characteristics to any ideal. We will consider four key characteristics.

Definition 1

Let be an ideal of subsets of a set , such that contains all singletons of .

  • The additivity of , , is the smallest number of sets in whose union is not in .
  • The uniformity of , , is the smallest cardinality of any subset of that is not in .
  • The covering number of , , is the smallest number of sets in whose union covers all of .
  • The cofinality of , , is the smallest cardinality of any subset such that every element of is a subset of an element of .
 Remark 1

The cofinality of an ideal is the least number of sets you need to generate the ideal by closing under subsets. More precisely, a subset is called a basis for if every element of is a subset of some element of . Thus the cofinality of is the least cardinality of a basis for .

As was the case with the cardinals we introduced in the previous section, assuming is reasonable, all four of the cardinals characteristics associated with provides an uncountable lower bound for the value of the continuum.

Lemma 1

Suppose that is a proper -ideal, contains the singletons, and that has a basis consisting of Borel sets. Then each of the four cardinals above is uncountable and bounded above by .

 Proof.

The additivity of is uncountable simply because is a -ideal. In the next lemma we will show that if is a proper -ideal containing the singletons, then the additivity of is a lower bound for all four cardinal characteristics of , and hence all four are uncountable.

Next, it is easy to verify that for any proper -ideal containing the singletons, the additivity, uniformity, and covering number of are bounded above by . If additionally has a basis consisting of Borel sets, then since there are only many Borel sets, we have that the cofinality of is bounded above by too.

All three of the -ideals we have introduced have a basis of Borel sets. For this is clear because -compact sets are Borel. For any meager set is contained in a countable union of closed nowhere dense sets, which are Borel. Finally for , note that if is null then for all there is a Borel set such that and . It follows that is contained in the Borel null set .

Remark 2

There can exist proper -ideals containing the singletons that don't have a basis of size . For example, it is consistent that the ideal of strongly null sets has while . [ref]

We next establish the basic relationships between the four cardinal characteristics associated with .

Lemma 2

Suppose that is a proper -ideal and that contains the singletons. Then we have the inequalities , and also .

 Proof.

For the inequality , we will show that for every set not in , we can find a family of the same (or lower) cardinality such that . This is easy: if , then the family consisting of all such that has the same cardinality as and satisfies .

The proofs of each of the next three inequalities follows the same form: given a set indicated by the right-hand side, find a set of the same or lower cardinality indicated by the left-hand side. So to show , let be a basis for . For each set choose an element and let . Then has the same or lower cardinality as , and we claim that . Indeed if then we would have for some , contradicting that .

For the inequality , if satisfies , then itself satisfies .

For the inequality , again suppose that is a basis for . Since contains the singletons, it follows that itself covers .

The conclusions of the two lemmas are summarized in fig:ideal$

The relationships between the cardinal characteristics of , assuming satisfies the hypotheses of the two lemmas. In the figure, the arrow represents the inequality .

In the previous section we introduced , but we dealt only with the characteristics and . We conclude this section by giving the values of and as well.

Proposition 1

We have and .

 Proof.

We have already shown that . For the reverse inequality, first recall from Theorem 2 that a subset of is unbounded if and only if it is not . Now suppose that is a family of subsets of such that is not . For each let be a bound for . Then is an unbounded family: Indeed, otherwise the set of things bounded by some would be bounded and hence so would . This shows that .

The second equality is similar and left as Exercise 1.

 Exercise 1

Show that .

 Exercise 2

Let be the ideal of all countable subsets of . What are the values of the four cardinal characteristics of ?

 Notes 1

We have finally entered into the material covered in the book Bartoszyński--Judah, Set theory: on the structure of the real line. The basic properties of -ideals and their cardinals begins in Section 1.3.
Cichoń's diagram

So far we have seen many similarities between the various size notions that we have discussed. The classes of meager sets and null sets are both ideals, both proper, both closed under countable unions, and so on. In this section we further investigate how far this comparison extends, and in the process we reveal a deep and intricate connection between measure and category.

To begin, it is natural to ask whether the meager and null sets are truly different notions. The following result shows that they are very different indeed: it is possible to be small according to either notion, and at the same time, large according to the other.

Proposition 1

There exists a null comeager set. There exists a meager conull set.

 Proof.

The key is that we can construct dense open sets of arbitrarily small measure. That is, for each we will construct a dense open set such that . Assuming we have done so, we let . Clearly the set is null. To see that it is comeager note that for all , we have that is closed and nowhere dense. Thus is meager.

To construct the set , let be an enumeration of the rational numbers, and for each let be the open interval centered at of length . We then let . Clearly is dense and open, and .

Finally, since is null and comeager, we clearly have that is meager and conull.

Although this result shows that category and measure are very different in terms of which sets they deem small, it also provides a certain symmetry between the two notions. The next result breaks this symmetry, and in its place provides an intricate structure of relationships between category and measure. This result is what we came all this way to see.

Theorem 1

The cardinal characteristics defined in the previous sections exhibit the pattern of inequalities known as Cichoń's diagram, which is depicted in fig:cichon$.

Cichoń's diagram of cardinal characteristics. Here as usual the arrow represents the inequality .
Remark 1

In Cichoń's diagram, the symbol can stand for the meager ideal on any one of the spaces , , or . Indeed, we have already seen in Proposition 1 that and can be made homeomorphic after removing a countable subset of each. In Exercise 1, we show that the same is true of and .

Similarly, the symbol can stand for the null ideal on either or ; see Exercise 2. In fact, it is possible to define a natural measure on , and then can stand for the null ideal on too. [ref]

 Remark 2 Theorem 1 doesn't rule out the possibility that all or some of the cardinals in Cichoń's diagram are equal to each other. And this is indeed possible: if CH is true then and so all twelve of the cardinals are identical. So to truly break the symmetry between category and measure, we need some way to show that it is possible for these cardinals to be different. For that we will need the method of forcing, which will be the focus of the second half of the course.

For the rest of this section as well as the next few, we take up the proof of Theorem 1. We have already established seven out of the fifteen inequalities depicted: follows from Proposition 1. The two bounds and follow from Lemma 1. And four more of the inequalities are special cases of Lemma 2.

We conclude this section with proofs of four more fairly easy inequaleties. The remaining four turn out to be be slightly more difficult. In the next section we will present a handy but abstract tool that will reduce our workload to just two more inequalities. The final two will be proved in the following two sections.

Lemma 1

We have , and .

 Proof.

For the first inequality, recall our observation in Remark 2 that , so any nonmeager subset of is certainly not . But we also know that every non- set is unbounded. It follows that every nonmeager subset of is unbounded, which implies .

The second inequality again uses the fact that , and we leave it as Exercise 3.

 Lemma 2

We have , and .

 Proof.

For the first inequality, we must show that given a nonmeager set , we can find a family of null sets of smaller or equal size such that . For this, we let be the null comeager set constructed in Proposition 1, and consider the family of null sets .

To see that , suppose towards a contradiction that this is not the case. Then there exists such that for all . It follows that for all , or in other words that is disjoint from . But is comeager, so this would imply that is meager, which is a contradiction.

The proof of the second inequality is identical but with the terms meager and null exchanged. This time let be nonmeager, and let be meager conull. Then the same argument shows that the family defined above covers , since otherwise there would be a translate of which is null.

 Exercise 1

Show that there is a homeomorphism between co-countable subsets of and .

 Exercise 2

For a basic open set of , let . Then extends to a measure on the Borel sets of (take this for granted). Show that there is a measure-preserving bijection between co-countable subsets of and .

 Exercise 3

Show that .
Ideals and duality

At this point one might have observed that many of the proofs of inequalities between cardinal characteristics have come in pairs. This phenomenon is easy to spot in Lemma 1 Lemma 2, but if one examines the proof it is even present in Lemma 2. It turns out that there is a category-theoretic duality lurking behind all of these pairings. (Here we mean category as in objects and morphisms, not as in Baire's theorem.)

Definition 1

Let be a relation and (that is, the domain of is and the codomain of is ).

  • A subfamily is an -dominating family if for every there exists such that .
  • The dominating number of is the minimum cardinality of an -dominating family.

It is clear that the dominating number is the dominating number of the relation . But it is also easy to check that the unbounding number can be expressed as the dominating number of the relation . Moreover, if is an ideal then all four of the cardinal characteristics of can be expressed as dominating numbers.

Proposition 1

Let be an ideal on . Then we have:

  • is the dominating number of the subset relation on (meaning .
  • is the dominating number of the relation on .
  • is the dominating number of the relation on .
  • is the dominating number of the relation on .
 Proof.

It is straightforward to see the characterizations of and . The characterizations of and both use the downward closure property: lies in if and only if is a subset of an element of .

It is worth observing that the four cardinals come in two dual pairs. Here, if is a relation, then the dual of is its negated transpose . That is, the dual of satisfies iff . Thus we see that and arise from dual relations, as do and . Before we can exploit this duality, we need to describe the morphisms on the category of binary relations.

Definition 2

Let and be relations, and to avoid excessive notation, write and for the demain and codomain of , and similarly for . A morphism from to is a pair of maps

such that the following holds

for all and .

The definition in a sense implies that the following diagram ``commutes.'' Of course, the and edges symbolize relations, not functions, so this is only a partial analogy.

⇡⇡

In any case, the definition of a morphism is custom-designed to give us the following two key properties.

Proposition 2
  • If is a morphism from to , then .
  • If is a morphism from to , then is a morphism from to . Hence in this case we also have .
 Proof.

For the first statement, it is enough to show that if is an -dominating family, then the image is an -dominating family. Indeed, the image has the same or smaller cardinality than . To check this we simply chase the diagram: since is -dominating, for any there exists such that . Since is a morphism, it follows that . This confirms that is an -dominating family.

For the second statement, just take the contrapositive of the morphism property, , to arrive at the property required of a morphism from to .

For each of the inequalities between cardinal characteristics that we have seen, it is possible to extract a morphism hiding in the proof.

Example 1

In Lemma 2, where we showed that , we could have used the morphism from relation on to the relation on given by the maps

Indeed, it is trivial to see that . The fact that can be taken to be the identity reflects the fact that if is a basis for then the very same is also a covering family.

Moreover, if we exchange the roles of and we obtain a morphism from to . This morphism lies behind the inequality . Indeed, this inequality was proved by sending any to the family of all for .

 Example 2

In Lemma 2, where we showed that , we could have used the following morphism from the relation on to the relation on . Again we let be a fixed null comeager set.

To check that it is a morphism, implies , which in turn implies that , as required. Recall that the function featured prominently in our original proof: for each we formed the family of translates .

Once again, if we exchange the roles of and we obtain a morphism witnessing the inequality . Recall that this proof was the same, but using translates of the comeager null set . The minus sign in has no effect on the argument.

Beyond these two examples, we see that each arrow in Cichoń's diagram (Theorem 1) is potentially dual to the arrow that is positioned diametrically opposite to it. Assuming there is a morphism behind the proof of one of the inequalities, then the other inequality follows automatically from Proposition 2.

Remark 1

True inequalities between cardinal characteristics are not always witnessed by morphisms. For example, it is true that , but it is consistent that the dual inequality fails. [ref]

Exercise 1 Find a morphism behind the proof of the inequality (Lemma 2). Check that it is dual to a morphism behind the inequality . Exercise 2 Find a morphism behind the proof of the inequality (Lemma 1). Check that it is dual to a morphism behind the inequality . Notes 1

The category-theoretic presentation of relations, morphisms, and duality follows Section 4 of Blass.
Category and difference sets

In this section we will prove two of the four inequalities remaining in Theorem 1. We prove and (actually thanks to duality only one proof is needed). Recall that is the dominating number of the relation on , while is the dominating number of the relation on meager sets. Although the two relations don't seem directly comparable, we now introduce some technology to understand their relationship more clearly. An interval partition is a partition of into finite nonempty intervals . We always assume that the is adjacent to , and hence also that they are enumerated in increasing order.

Definition 1

If and is an interval partition, we say strongly differs from on if for all but finitely many we have .

If is fixed and is an interval partition, we define the set to be the set of all such that strongly differs from on .

Proposition 1

A subset is meager if and only if there is some and interval partition such that .

 Proof.

First suppose that , we will show is meager. For this, let

Thus , and it is clear that contains no interior. Moreover is a countable intersection of boolean combinations of basic open sets, and hence is closed. Thus we have shown that is meager.

Conversely suppose where each is nowhere dense, and suppose without loss of generality that for all . We will define an interval partition and an element recursively. To begin, since isn't dense there exists such that . We let and .

Now suppose that and have been constructed for and let be the initial segment built so far. Since is nowhere dense, by Proposition 4 we can find an extension of such that . But we can do even better: we can find an extension of such that even if only agrees with on , then we still have .

Such a is built in many steps: Let enumerate all elements of whose domain is exactly . Repeatedly using that is nowhere dense, we can find a sequence of successive extensions such that . We then let and . This concludes the construction of and .

To see that , observe that whenever we have . In other words, whenever we have that differs from on . Since the are increasing, any lies in all but finitely many of the . Thus we can conclude that any strongly differs from on .

The result implies that the collection of sets forms a basis for the meager ideal on Cantor space. This basis is particularly useful because it is easy to see when one set of the form is a subset of another.

Proposition 2

If and are interval partitions, then we have if and only if for all but finitely many there exists such that and .

The proof is elementary (though slightly technical), and we leave it for Exercise 1. Proposition 2 provides characterization of as the dominating number of a simple combinatorial relation on pairs . The cardinals and can be characterized by a similar combinatorial relation just on interval partitions. First, if and are interval partitions, we write if for all but finitely many there exists such that .

Proposition 3

There is a morphism from to , and there is a morphism from to . Hence is equal to the dominating number of the relation on interval partitions, and is the dominating number of the relation on interval partitions.

 Proof.

We first construct a morphism from to . Given any interval partition we define the element by the right endpoint of the interval after the one containing . Moreover for any function define an interval partition consisting of intervals such that .

Now, if , we must verify that . Indeed, given any we may find such that . Then if is large enough, since we know there exists an interval such that . Then by definition of we have . And by definition of we have . Hence , as desired.

The morphism from to is the same, but with the roles of and reversed. We leave it to the reader to check that this is indeed the case.

 Lemma 1

We have and .

 Proof.

We prove the second inequality by finding a morphism from the relation on to the relation on interval partitions. We therefore obtain the first inequality as a consequence of duality. For this it is enough to consider the relation just on the basis of meager sets of the form . We let:

Then by Proposition 2, in particular implies that , and hence , as desired.

We conclude this section with a further result that gives much more information about the relationship between and the other cardinals.

Theorem 1

We have .

 Proof.

We have already shown that and . Hence it remains only to show that . For this we must show that if is a family of meager subsets of such that then is meager. Without loss of generality, we can suppose that consists of closed nowhere dense sets.

We begin by finding a countable dense subset disjoint from . Indeed, since we have that . In fact for any basic open set we must have that does not cover , since otherwise we could use Exercise 2 to find a countable family of translates of which covers all oof . This shows is co-dense, and therefore we can find as required.

Now enumerate . Then for each and , since is nowhere dense, we can find a finite initial segment such that is disjoint from . Since , the family of functions is bounded by a single function . Finally we use this to define the set:

Then is a countable intersection of dense open sets, and hence it is comeager. Moreover since for all we have , we have that is disjoint from . We can thus conclude that is meager, as desired.

 Remark 1

Although the last result does not apparently involve a morphism, it is true that an analogous argument shows the dual fact that . This three-term duality is also part of an abstract morphism-like framework, which we omit. [ref]

 Exercise 1

Prove Proposition 2.

 Exercise 2

Let and . Show that there exists a homeomorphism such that iff .
Bartoszyński's theorem

In this section we complete the proof of the two inequalities remaining in Cichoń's diagram: and . By duality, the two inequalities are really one that was discovered independently by Bartoszyński and Raisonnier--Stern. The proof we give is mostly due to Bartoszyński, and is markedly more difficult than our previous results. In fact I will need your help proving two of the preparatory facts (see the exercises).

We begin by introducing a new relation that sits between and . A slalom is a sequence of subsets such that . We write for the set of slaloms. An element is said to ski through , which we denote by , if for almost every we have .

Lemma 1

There is a morphism from the relation on null subsets of to the relation on .

Before the proof, we will need the following fact about null sets, which we leave for Exercise 1.

Proposition 1

If is a null set, then there exists a closed subset with the property that whenever we have is nonnull.

 Proof of Lemma 1

We must define and such that for all and null sets we have implies .

To define , we start with a sequence of open subsets such that , and given we let

Then it is clear that is a null set. For technical reasons later on, we will need to assume that the sets are mutually independent events (the measure of the intersection is the product of the measures). It is not difficult to write down such explicitly.

Before defining , given a null set let us preview what properties we will need of the slalom . So suppose that is given and . Let be chosen as in Proposition 1, so that we have . Since is complete and the sets are open, the Baire category theorem implies that at least one of them is non-dense in . Thus there is a basic open set such that and eventually we have . We will define the slalom so that for large enough, it includes all such . This will guarantee that as required.

As a first approximation to this, whenever we begin by letting

and otherwise we simply let . We now have two issues to deal with:

  • We need a single slalom that handles all at once.
  • The don't necessarily satisfy ; we need .

Tackling the second issue first, we will show that the sets are not too large. More specifically we claim that the sum converges. Indeed, by the independence of the sets we have

By our choice of , the left-hand side is positive. Hence the right-hand side is positive too and taking a logarithm we obtain

From the Taylor series expansion we always have , and the claim now follows.

To deal with the first issue we construct a single slalom such that for all we eventually have . To do this fix an enumeration of the elements of . By the convergence shown in the previous paragraph we can find such that for all we have . We then let . Then clearly

Thus is a slalom, and this completes the construction of .

To quickly recapitulate why this works, again suppose that . By the above reasoning we can find such that and for almost all , . Thus for large enough we have both and . It follows that .

 Remark 1

Although we don't need it, there is also a morphism the other way, that is, from to the relation on . Thus the ski-through relation on slaloms can be used to give a complete combinatorial characterization of both and .

 Lemma 2

There is a morphism from the relation on to the relation on meager subsets of .

This time we will need a topological fact before the proof, and once again we leave it for Exercise 2.

Proposition 2

Given and an open subset , there is a countable family of open subsets of with the properties:

  • Whenever we have ;
  • Every nowhere dense set is disjoint from some set in .
 Proof of Lemma 2

We must define and such that whenever we have .

To construct , first let be an enumeration of , and for each apply Proposition 2 to to obtain a family . Now if is a slalom we let

Then by the first property of the , for all we have that is a nonempty subset of . It follows that each set is dense and open, and hence that is meager.

To define , let be a meager subset of and write as an increasing union of nowhere dense sets . By the second property of the , for all there exists such that . We let this value .

Finally let and be given and suppose that . Then for large enough we have that contains an element with . Thus for large enough we have that is disjoint from . It follows that , and hence as desired.

 Corollary 1

We have and .

This concludes the proof of Bartoszyński's theorem, as well as Theorem 1.

Exercise 1

Prove Proposition 1. [Hint: First show that there exists a closed subset which is nonnull. Let be the union of all basic open sets such that , and show that . Finally let , and show that has the desired properties.]

 Exercise 2

Prove Proposition 2. [Hint: Wlog itself, and wlog we can replace with . Let be an open basis, and show that is as desired. If has been defined, enumerate it as . For each consider all the clopen sets with the property:

  • for all , if then we have .

Then let be the collection of for all and with this property. Now verify that any nowhere dense set is disjoint from an element of and that the intersection of any elements of is nonempty. It may help to start with the special case .]

Notes 1

The presentation of the proof of Bartoszyński's theorem was largely taken from Sections 522K--522P of Fremlin, Measure theory. A similar proof can also be found in Bartoszyński's handbook article, Invariants of measure and category.

Le tour de forcing
The idea of forcing

In this part, we will assume familiarity with the notions of statement, theory, and model. As a reminder, a formula is simply a mathematical assertion that can be expressed using the ordinary logical symbols (and, or, not, quantifiers, variables) and non-logical symbols (in our case, , , , etc). A sentence is a formula in which every variable is quantified, and a theory is a collection of sentences. If is a theory, then a model of is a set, together with interpretations of the non-logical symbols of , in which all the sentences in hold true.

We are interested in the theory ZFC, which consists of the standard axioms for set theory, that govern how the relation behaves. G\"odel's incompleteness theorem implies that for some sentences , the models of ZFC do not all agree about whether is true or false. A theorem is a sentence that holds true in every model of ZFC. A sentence is independent of ZFC if it holds true in some models, and false in others. One example that we have mentioned already is CH, the sentence which says that .

Forcing is a method of adding new sets to a given model of ZFC, to obtain a larger model of ZFC. By carefully choosing how we add the new sets, we may be able to force a given statement to hold true in . For example if , it is possible to add a new element that is a bound for , even if was unbounded to begin with. This is a powerful move, and when iterated it can have an effect on the value of the cardinal .

But forcing cannot do just anything. For a very simple example, if , then will remain nonempty after forcing. There is some element and this element will remain in forever. More generally, we will see that a wide variety of statements are absolute, meaning that their truth value cannot be changed by forcing. The Riemann hypothesis is an example of such a statement.

The concept of absoluteness highlights the distinction between ordinals and cardinals. Recall that an ordinal is a set which is transitive and well-ordered by the relation. Both of these properties are absolute, and therefore forcing can never add or change ordinals. On the other hand, is defined to be the least ordinal that cannot be mapped injectively into . So is equal to some ordinal , but this ordinal value can be raised by a forcing which adds a new injection from to .

The situtation is even more fluid with an indirectly-defined cardinal such as . Recall that is the unique cardinal number that is in bijection with . This value can be raised by a forcing which adds at least many new subsets of . The value can also be shrunk by a forcing which adds a new bijection between and the old (while still preserving ). Roughly speaking, this is how we will establish the independence of the continuum hypothesis.

For the rest of this section we introduce the basic combinatorial objects used in forcing. The main object is very simple: a forcing notion is simply a partial order with a maximum element (also written ). When we force with , we add a new subset of to the universe. We think of the elements of as imposing conditions on the new set to be added. If we say that is stronger than if ; lower elements hold more information.

When we force with , the partial order can give fine control over the new subset that we add.

Definition 1

A subset is a filter if it satisfies the two properties:

  • upwards closed: if and then .
  • downwards directed: if then there exists such that .

Elements are said to be compatible if there exists such that . Thus a filter is simply a set of pairwise compatible elements, closed upwards for convenience.

Example 1

Let be a tree. Then can be made into a notion of forcing by turning it upside-down, that is, setting if and only if . Since is a tree, this partial ordering has a maximal element the empty sequence.

In an upside-down tree such as , the only way for two elements to be compatible is to actually be comparable, that is, or . Thus if is a filter, then the elements of actually form a path through .

We encourage the reader to note the distinction between the two words comparable and compatible: pairwise comparable sets form a chain while pairwise compatible sets form a filter. Compatibility is what is needed in direct limit constructions. In a tree, the two concepts end up the same.

Definition 2

A subset is dense if for all there exists such that .

The use of the word ``dense'' here may seem in conflict with the use of the word in topology, but the two can be connected. If is a partial order then it has a topology with a basis consisting of the downward cones . A subset is dense if and only if it is dense in this topology.

We think of the dense subsets of as omnipresent---almost every element of lies below some element of . When we force with we add a filter that is generic in the sense that it meets these dense subsets of . The more dense sets that we demand that meets, the stronger a condition this imposes on .

For example, if just countably many dense sets are given, then we will see in the next section that there is always a filter that meets them all. On the other extreme, we could say that a filter is fully generic if it meets every dense set of , but the next result shows that this is too strong.

Proposition 1

Suppose that for every , there exist incompatible elements . Then does not have a fully generic filter.

 Proof.

It is enough to show that if is a filter then its complement is dense. For this, let be arbitrary and by the hypothesis on let be incompatible elements such that . Since is a filter, it cannot contain both and . Thus contains at least one of them, and this shows is dense.

A partial order satisfying the hypothesis of the proposition is called atomless. The condition ensures that forcing with is nontrivial. Once we acknowledge that fully generic filters do not exist in the given universe of set theory, we arrive at the following definition.

Definition 3

If is a model of set theory and , we say that is -generic if for every such that is dense, we have .

When we make forcing rigorous, we will show that under appropriate hypotheses, a -generic filter can be found outside of . We will then let be the smallest model containing both and , and call this the forcing extension with respect to the notion .

Example 2

Returning to the example of the forcing notion with the upside-down ordering, we have already said that a filter is actually a path through . If is -generic, then much more can be said of this path. First of all, consider the sets

Clearly is dense, since any can be extended to an element with length at least (recall we are using the upside-down ordering). It follows that meets for all , and hence that is an infinite path. Second, if is -generic then we have already seen that . Thus the union is an element of that wasn't there before, that is, is a new element of the Baire space! We can do the same with and Cantor space.

This example brings us back to our discussion of forcing CH to be false in a forcing extension. We have just seen how to add one new element to ; if we were to repeat the process we can add many new elements to .

Martin's axiom

We will make the ideas of the previous section more rigorous shortly. But before going into the technical details of this, we will introduce the combinatorics of forcing using forcing itself as a black box. Specifically, we will appeal to a statement called Martin's axiom, which roughly speaking says that the current universe of set theory already contains many highly generic filters . The consistency of MA is itself proved using forcing, but we shall take this for granted for now. This will allow us to explore the effects of forcing using a number of partial orders without ever leaving .

There is unfortunately one major limitation on the variety of partial orders we will be able to explore using Martin's axiom. A subset is said to be an antichain if for all we have and are not compatible. Thus if is an antichain, a filter can only choose at most one of the elements of .

Definition 1

A partial order is said to be ccc (or satisfy the countable chain condition if every antichain is countable.

In some sense the ccc imposes a limitation on the number of different filters that may be added when forcing with . The partial order considered in the previous section is obviously ccc because it is countable. However, there are many examples of ccc partial orders which are not countable.

Example 1

Consider the partial order consisting of all nonempty open subsets of , with the ordering iff . Then is ccc: indeed, two sets are incompatible in this ordering if and only if they are disjoint. Thus an antichain is a family of pairwise disjoint open sets, and since is separable, such a family must be countable.

 Example 2

Consider the partial order with the usual upside-down tree ordering. Then this is not ccc. Indeed, the set of sequences of length is an uncountable antichain in .

Definition 2

Martin's axiom (or just MA) is the statement: For every ccc partial order and every family of fewer than continuum many dense subsets of there exists an -generic filter .

We sometimes consider the refinements of MA defined as follows. The axiom MA is the same statement as MA, with replaced by .

Proposition 1

MA is true. Thus if CH holds, then MA is true.

 Proof.

Let be any partial order and let be a countable family of dense subsets of . Fix , and inductively let be an element of . Then the set is downwards directed, and hence closing it upwards generates a filter which meets each of the .

In fact, in this proof we did not even need to be ccc. The next result states that MA is also consistent with a larger continuum. For now we take this fact for granted and use it to derive several applications, as an introduction to the combinatorics of forcing.

Theorem 1

There is a model of set theory which satisfies both MA and CH.

We say that a set of axioms is consistent, or consistent with ZFC, if there is a model of ZFC which satisfying those axioms. Thus the above result can be rephrased: MA+CH is consistent.

The axiom MA packages a great deal of forcing into one universe . When MA is true, it is as if somebody has already performed forcing with all of the ccc partial orders. In fact later we shall see that the consistency of MA can be established by repeatedly applying the forcing construction.

Proposition 2

In the definition of MA, we cannot in general drop the condition that the family of dense sets have size less than continuum.

 Proof.

We again go to our favorite partial ordering with the upside-down order. This time, for each we consider the set

It is easy to see that is dense: any sequence can be extended to a sequence that disagrees with . Now if MA were to hold with respect to families of dense sets of size continuum, then there would be a filter that meets for every . It follows from this that the function is an element of which disagrees with every , a contradiction.

 Proposition 3

In the definition of MA, we cannot in general drop the condition that is ccc.

 Proof.

This time we let use the partial order with the upside-down order. We have already seen that is not ccc. Now for each we consider the set

Then is dense: any can be extended to include in its range. Now if MA were to hold with respect to this partial order, then there would be a filter that meets for all . It follows from this that there is an onto function from to , a contradiction.

We close this section with a result showing the effect of MA on properties of the continuum. Recall that the Baire category theorem states that the set of all real numbers is not meager, that is, is uncountable. It turns out that MA implies is as large is possible.

Theorem 2

MA implies that the Baire category theorem holds for unions of length less than , that is, .

 Proof.

Let be a family of nowhere dense subsets of of cardinality less than continuum. We will construct such that . Let be the partial order consisting of all bounded, positive-length intervals in , ordered by iff . Then is easily seen to be ccc by the same argument as in Example 1. For each , we consider the set

Then is dense for any : since is nowhere dense, for any positive-length interval there is a positive length such that . We may then shrink further to suppose that .

Now by MA, we can find a filter such that meets for every . Then the sets for have the finite intersection property, and it follows from the completeness of that there is a point . Then if , since we can find a positive-length interval such that and . That is, we have and , and so . We conclude that is not an element of , as desired.

Martin's axiom and Cichoń's diagram

We have seen the effect of MA on properties of the continuum. We now explore the effect of MA on further cardinal characteristics found in Cichoń's diagram. We begin by showing that MA makes large. Although this already follows from Theorem 2 together with all we have proved about Cichoń's diagram, here we give a direct proof.

Theorem 1

Assuming MA, we have .

 Proof.

Suppose towards a contradiction that , and fix a dominating family . Let be the partial order with the upside-down ordering. For each we consider the family sets

Observe that is dense for all and : if we can easily find and find such that . Thus by MA we can find a filter which meets for all and . Letting , it is clear that is not dominated by for any , contradicting that is a dominating family.

The content of the above proof is that if is fully generic for , then in none of the elements in the Baire space of dominate . It falls short, however, of showing that actually dominates every element in the Baire space of . With a slightly more specialized partial order, this can be achieved as well.

Given a family , the Hechler forcing with respect to is the partial order consisting of elements where and is finite. We partially order by if the conditions hold:

If is an element of a Hechler forcing, then as usual the left coordinate , called the stem, is a finite approximation for a new element of Baire space. The new coordinate can be thought of as a set of promises, which ensures that stronger conditions will dominate the elements of .

Hechler forcing is always ccc, because incompatible conditions cannot have the same stem , and there are only countably many possible stems .

Theorem 2

Assuming MA, we have .

 Proof.

Suppose towards a contradiction that is an unbounded family of size , and let be the Hechler forcing . We now consider two families of dense sets. First, for each we consider the set

To see that is dense, let be a given element of . If then we extend the stem to a sequence defined by for all such that . Then clearly and .

Next, for each we consider the set

Then is again dense, since given we have (Observe that the promises are trivially satisfied since we have not lengthened the stem!)

Now by MA we cand find a filter that meets for all and for all . We then let

be the element of the Baire space determined by . Given and we first find an element , and then letting we find an element . Since is a filter we can find which is stronger than both. Then by the definition of the ordering on , there is some such that and hence . Since and were arbitrary, it follows that for all , contradicting that is unbounded.

We close this section by finding the effect of MA on the cardinal . As we will see, MA once again implies that this cardinal has its maximum value of . By the inequalities shown in Theorem 1 and especially Bartoszyński's theorem, this implies that assuming MA, all the cardinal characteristics in Cichoń\'s diagram have the value . At face value, this obviates the last three results which showed that individual characteristics are equal to . But those arguments were more direct, and moreover introduced us to several forcings which will remain important outside of the MA context.

Theorem 3

Assuming MA, we have . In particular, all the cardinal characteristics in Cichoń's diagram (except possibly for ) have the same value.

For this proof, we once again introduce a new and special notion of forcing. The amoeba partial ordering with parameter consists of all open subsets such that . The ordering on is defined by iff . Thus the elements of are inner approximations to an open set of measure .

Lemma 1

For any , the amoeba partial ordering is ccc.

 Proof.

Given an uncountable family we must show that at least two elements are compatible, that is, . We first give ourselves a little wiggle room as follows: since is uncountable and there are only countably many values of , by the pigeon-hole principle we can find a fixed and an uncountable subset such that for all we have .

Now for each we can find an open set which is a finite union of intervals with rational endpoints and such that . Once again, since there are only countably many possible sets , we can find a fixed set and an uncountable such that for every .

We claim that any two elements are compatible. Indeed, we compute:

Thus we can conclude that is not an antichain, as desired.

We are now prepared to prove Theorem 3.

Proof of Theorem 3

Given a family of fewer than continuum many null sets, we wish to show that is again null. For this, it is sufficient to show that for any we have is contained in an open set of measure .

For this, let be given and let be the corresponding amoeba forcing. For each we consider the set

To see that is dense, let be a given open set with . Since is null we can find an open set such that and . Then and , and so is stronger than and . (Kunen says: The amoeba reached out a pseudopod to engulf the morsel of food .)

Now by MA there is a filter such that meets for all . Letting be the open set determined by , we clearly have that . To conclude, we claim that . For this, since is second countable we can find countably many elements such that . Since measure is continuous from below (similar to Exercise 2) for all there exists some such that . Since is downwards-directed we inductively have , which implies that . It follows that , and since was arbitrary we have , as desired.

 Exercise 1

Suppose that is an almost disjoint family of infinite subsets of : for all we have that is finite. Show that if then there exists a single infinite set such that is finite for all . [Hint: consider the forcing consisting of pairs where is a finite subset of , is a finite subset of , and iff , , and whenever we have .]
The machinery of forcing

So far we have seen forcing only in the context of appeals to Martin's axiom, which gives us highly generic filters in a single model of set theory. When we actually do forcing, we wish to find a fully generic filter , even though we know this must lie outside of . But what does it mean that a set lies outside of the universe of sets? In fact, to find ``new'' sets we will really assume that is a countable, transitive model of ZFC. In other words is a countable set lying in some larger universe , it is closed downwards under , and the structure satisfies all of the axioms of set theory.

The mild assumption that there is such a turns out to be very powerful. First of all, if is countable then given a partial order we can easily find a filter that meets all the dense subsets of that actually lie in . After all there are just countably many sets in and therefore just countably many dense subsets of in . Hence we can use the argument of Proposition 1 to diagonalize and obtain a -generic filter .

Second of all, if is transitive then we can use the machinery of absoluteness to reason about the basic properties of and its forcing extensions . Recall that a formula in the language of set theory is if all of its quantifiers are bounded, that is, of the form or else . We will use the well-known fact that if is a formula with parameters in a transitive set , then is true if and only if holds in .

So just how mild is the assumption that there is a countable transitive model of ZFC? Unfortunatley it is not a totally nontrivial one. The countability isn't the problem; recall that by the L\"owenheim--Skolem theorem if there is an infinite model of a theory then there is a countable one. Rather, the problem is assuming there is a model of ZFC at all. Indeed this is equivalent to assuming that ZFC is consistent, that is, ZFC does not entail any contradictions. But we know from G\"odel's incompleteness theorem that it is not possible to establish the consistency of ZFC using ZFC alone.

It is possible to work around this technicality by supposing only that satisfies a large but finite subsystem of ZFC. By the reflection theorem, it is possible to obtain transitive set models of such a subsystem, and it is not difficult to use such a model to get a countable transitive one. However, for simplicity we will simply assume for the rest of this section that is a countable, transitive model of all of ZFC.

The first problem we have to deal with when introducing forcing is that if one is working in , then since is not available it is difficult to refer to elements of (and hence difficult to prove facts about them). Instead we have the following notion of a name of a ``potential'' element in .

Definition 1

If is a partial order, then a set is called a -name for an element of the forcing extension by if consists of elements where is a **-name and .

Like sets themselves, the definition is recursive. To explain it briefly, we can think of an ordinary set as a wellfounded tree with at the root, the elements of on the first level, the elements of elements of on the second level, and so on. A -name is similar, except the nodes of the tree are also -names, and each node is labelled with an element of .

What are the labels there for? In a moment we will show how to evaluate names to yield an element of the extension . When is an element of , we will think of the label as the ``probability'' that will be included as an element of . If is high in the ordering on then is more likely to be included; if it is low then is less likely to be included. Specifically, we include just those whose label lies in the generic filter .

Definition 2

Let be a partial order in and be a filter. If is a -name, then the evaluation of via , denoted , is defined recursively by

We then define the forcing extension of corresponding to by

The definitions of -name and the evaluation are heavily recursive, but one should expect this from such a general set-theoretic construction. It is an amazing fact that such a short construction actually works, and it will take us some time to prove everything we need.

Lemma 1

If is a partial order and is a filter, then we have and . Moreover, if is any other transitive model of ZFC with these two properties, then .

Proof.

To prove the statements, we need only write down explicit -names for the objects in question. First recall that we are always assuming has a maximum element . Thus if we can write the recursive definition

The idea here is to take the tree of and label each node with a . To see that , suppose inductively that for all . Then since always lies in , the definition implies that .

To see that we construct a single name

Then by the previous paragraph, we have that , as desired.

Finally, if is a model of ZFC which contains as a submodel and as an element, we must check that contains for all names . For this, can simply evaluate as in its definition, and will be correct in this evaluation because the definition of is and hence absolute to transitive models. [ref]

Names of the form for are called check names. For convenience we will sometimes identify with its check name. The name is called the canonical name for the generic, and we observe that it does not depend on at all. Still, when a filter is given we may again identify with this name.

We next show that forcing doesn't enlarge very much.

Lemma 2

If is a partial order in the countable transitive model and is a filter, then is countable and moreover and contain the same ordinals.

 Proof.

It is clear that is countable from its definition; each element of is determined by a name which lies in .

For the statement about ordinals, first recall that the property of being an ordinal is absolute to transitive models. Now suppose that is an ordinal of and let be a name such that . Note that when we construct from we essentially throw stuff away, and so is in a sense more complicated than . We can make this precise using the notion of a rank: for any set we can define the -rank . Then it is easy to see inductively that . In our case, and the rank of an ordinal is always . We conclude that , and since rank is an absolute notion and is transitive, we have .

The most important fact about the forcing extensionn is that if is a model of ZFC, then so is . We will give just a partial proof of this fact, beginning with the following easier axioms.

Lemma 3

If is a partial order in and is a filter, then the extension satisfies the axioms of extensionality, infinity, foundation, pairing, and union.

 Proof.

Every set satisfies the axiom of foundation. Since is tansitive and infinite, it must contain and therefore satisfies the axiom of infinity. To show satisfies extensionality, it is enough to show that is a transitive set. For this, let is an arbitrary element of and . Then by definition of , we have for some . In particular, .

The pairing and union axioms are existence axioms, which means we must devise names for the two constructions. First suppose and let denote the name . Then it is immediate to see that . Next suppose , and define the name:

Then since includes names for all conceivable elements of elements of , we have that . (To hit exactly we can either refine this argument or appeal to the comprehension axiom after we have proved it.)

 Exercise 1

In many cases it is more convenient to use instead of itself. Write down a name such that whenever is a filter and .
The forcing language and forcing theorems

We have been able to establish a number of facts about the forcing extension using elementary manipulations of the definition of -name. For more complex axioms and properties of , we will need a way to decide whether a given sentence holds in . But just as the value of a name depends on the filter , the truth value of a given sentence may depend on the filter , just as the set value of a name depends on .

For example to prove the comprehension axiom, we need to build a name for the set . But from within , it is not immediately clear how to tell for which elements the property will be true in . We will need the following.

Definition 1

Let be a partial order.

  • The forcing language for consists of the usual logical symbols, , and the -names as constant symbols.
  • If is a sentence of the forcing language for , we say satisfies if, after replaceing the names in replaced by their values , it is true in .
  • If and is a sentence of the forcing language for , then we say forces , written , if implies satisfies .
 Example 1

Anything that we know for sure about will be forced by the element . So for instance since we have proved that satisfies the axiom of pairing, we can say ``the axiom of pairing''.

For a less trivial example, if we have already seen that adding a generic filter adds a new element of Baire space . Moreover a simple dense set argument shows that will be surjective onto . Thus we can say `` is a surjective function from .'' (Recall that we cannot use the symbol , so we instead use , which is the canonical name for .)

On the other hand, different generic filters will yield different specific values for . Thus does not force any interesting properties of , other than that it is some natural number. But suppose that is a finite sequence with . Then if is a generic filter, then implies . In other words we have ``''. (From now on, we will often neglect the checkmarks on simple things like natural numbers.)

The following three results are the fundamental tools used in the development of the theory of forcing. Essentially all further facts about forcing will be derived from these properties of the forcing machinery.

Theorem 1 The forcing theorems
  1. Definability theorem: The relation is definable in .
  2. Forcing theorem: If is a sentence of the forcing language satisfies , then there exists such that .
  3. If is a model of ZFC then is a model of ZFC.
 Remark 1

The exact sense in which is ``definable'' is somewhat technical. Specifically, we mean that for each formula in the language of set theory, the relation on tuples defined by is definable.

Let us first see the power of forcing theorems (a) and (b) to establish forcing theorem (c). Recall that the comprehension axiom states that if is a formula, then for all sets we have that is a set.

For the first time, we will use the dot notation for names for elements . That is, rather than letting be a name such that , we will let denote a name such that . This saves on the total number of distinct letters that we have to use. A good rule of thumb is this: whenever we write a specific name for an unknown set we use greek letters, and whenever we write an unknown name for a specific set we use dot notation.

Theorem 2

Assume the definability and forcing theorems are true. Then satisfies the comprehension axiom.

 Proof.

If and are as above, we need to cook up a name for the set . For this, let be names for respectively, and let

\[ \rho=\set{(\pi,p)\mid\pi\in\dom\dot a,\;p\in\mathbb P,\;p\forces\pi\in\sigma,\text{ and }p\forces\phi(\pi,\dot b)}\text{.}

\]

Here we are using the definability theorem even to know that lies in . To see that , first suppose that . Then there is such that and . By definition of , it follows that in we have both and . In other words, in we have both and , and therefore .

Conversely if then satisfies the sentences of the forcing language and . By the forcing theorem there exist such that and . Letting be such that we clearly have and also .

We omit the proofs of the remaining axioms: replacement, power set, and choice. All three are also existence axioms, and they can once again be proved by inventing clever names. In each case, the names are defined using the forcing relation.

We conclude this section with several elementary but frequently used properties of the forcing relation. These properties will also be used to guide the proof of the forcing theorems in the next section.

Lemma 1

If and then .

 Proof.

This is a straightforward consequence of the fact that if and , then since is closed upwards we have .

 Lemma 2

An element if and only if for all we have .

 Proof.

First suppose that and let . Then by Lemma 1 we have . Now we cannot have , since in that case if is a -generic filter with we would have that satisfies both and .

For the converse we proceed by contrapositive and suppose that . Then there is a -generic filter with such that satisfies . By the forcing theorem, there is such that . Letting be such that we have too, as desired.

 Lemma 3

If then there is a name and some such that .

 Proof.

Fix a -generic filter with . Then satisfies , and hence there is a name such that satisfies . By the forcing theorem there is such that . Letting be such that , we have that is as desired.
The proof of the forcing theorems

Recall that our definition of the relation cannot be carried out within . In this section we give a definition of a variant of the relation, denoted , which can be carried out entirely within . The definition of is inspired by the properties of the true relation that follow from the forcing theorem.

Definition 1

We first define for atomic and neg-atomic formulas by recursion on the complexity of the names .

Clause (3) above is also used in the formation of compound formulas.

Several remarks are in order. First, one should take a moment to confirm the definition isn't circular. For example is defined in terms of equality, which after negating is defined in terms of , which after negating is defined in terms of . The key thing to notice is that when we encounter for the second time, we have names of lower complexity than before. Since the class of names is well-founded, the recursion is well-defined.

Second, while the clauses in Definition 1 are inspired by properties of , they are actually somewhat oversimplified. For example, comparing clause (5) with Lemma 3 we see that clause (5) does not reflect the general case. It turns out that is nearly but not fully equivalent to ; this will still be enough to complete our proof.

We now turn to the proof of the forcing theorems, which will unfold over the next several lemmas. The first of these states that the analog of Lemma 1 holds for .

Lemma 1

If and then .

 Proof.

We prove this by induction on the complexity of the formula . For example, let us check that the induction passes through the first clause of Definition 1. Suppose are names and that the lemma holds for the sentence whenever . Then if , there is such that and . If also , then clearly also and by inductive hypothesis . Hence , as desired. The verification of the remaining four clauses is similar, and we leave them for Exercise 1.

The centerpiece of the proof is the following result, which shows that the analog of the forcing theorem (Theorem 1(b)) holds for . The proof is mostly a straightforward induction similar to the proof of the previous lemma.

Lemma 2

If is a sentence of the forcing language, then satisfies if and only if there is such that .

 Proof.

Once again we prove this by induction on the complexity of . To check that the induction passes through the first clause of Definition 1, suppose that are names and that the lemma holds for the sentence whenever . We must show that the lemma holds for the sentence . For this, first suppose that and . Then by Definition 1 there exists such that and . Clearly satisfies , and by the inductive hypothesis also satisfies . It follows that satisfies .

Conversely, suppose that satisfies . Then there must be some such that satisfies . By the inductive hypothesis, there exists such that . Since is downwards-directed we can find such that . Then by Lemma 1, , and so by Definition 1 we have .

The verification that the induction goes through the second, fourth, and fifth clauses of Definition 1 is similar and we leave them for Exercise 2.

Finally, we verify that the induction passes through the third clause of Definition 1. So suppose the lemma is true for , and let us show it holds for . For this, first suppose that there is such that . Then for all we have . It follows from Lemma 1 that for all we have . By inductive hypothesis, we must have that does not satisfy , and hence satisfies .

Conversely suppose that satisfies . Then does not satisfy , so by inductive hypothesis, for all we have . We now consider the set

Then is dense: given any , if then itself lies in . Otherwise , so by Definition 1 there is such that . Thus in this case , and we have verified is dense. Finally, since is -generic there exists . Since we know , we must have instead that , as desired.

We observe that the key use of the genericity of is in the above very clever verification that the induction goes through the third clause of Definition 1.

Now we can establish the definability theorem for as follows.

Lemma 3

For all we have if and only if . In particular, the forcing relation is definable in .

 Proof.

First suppose that , and let be a -generic filter with . Then by Lemma 2 we have satisfies , and hence satisfies . This shows that .

Conversely, suppose that . By Definition 1, to show it is equivalent to show that for all there exists such that . So let be given, and let be a -generic filter such that . The since we have satisfies . By Lemma 2 there exists such that . Finally we may let with , and by Lemma 1 we have that too, as desired.

Finally we can conclude that the forcing theorem holds for the true forcing relation as well. This completes our proof of the forcing theorems!

Lemma 4

If satisfies then there is such that .

 Proof.

If satisfies , then satisfies . Hence by Lemma 2 there exists such that , and by Lemma 3 this implies .

Exercise 1

Complete the proof of Lemma 1 by checking that for each of clauses 2--5 of Definition 1, if the lemma holds for the sentence on the right-hand side of the , then the lemma holds for the sentence on the left-hand side.

 Exercise 2

Prove that the induction of Lemma 2 goes through the second, fourth, and fifth clauses of Definition 1.

 Notes 1

This version of the proof of the forcing and definability theorems was largely drawn from handwritten notes, written by Spencer Unger during a forcing course given by Richard Laver. A proof can also be found in [REF Kunen, Section IV.2].
Forcing and cardinal characteristics
Cohen forcing and the continuum

We are now ready to use forcing, and our first big target will be to establish the consistency of CH.

Definition 1

For any cardinals , we define the set to be the family of all functions , where is a finite subset of . We partially order by function extension: if and only if .

Just as the forcing uses finite approximations to add a new function , the forcing uses finite approximations to add a new function . Forcing of this type is often called Cohen forcing, since Cohen essentially used this partial order in his original presentation of forcing. In this section we only have need for , which as we shall show, not only adds a new function from , but also adds lots of new functions from .

Lemma 1

Forcing with the partial order adds many (distinct) elements to .

 Proof.

Let be a -generic filter, and let . Now, for any limit ordinal we let be the function defined by . It is clear that there are many of these functions. We claim that if then . Indeed, consider the set

Then is dense: indeed, given , since is finite we can find such that neither nor lies in the domain of . Then if we let be an extension of such that , we clearly have .

Now since is -generic, there exists . Then there exists such that . Since it follows that and therefore that , as desired.

Thus if we force with , then in we can say for certain that . However before we can say for sure that satisfies CH, we need to be very careful about the cardinal value of . As we saw in Definition 1, it is possible for forcing to collapse cardinals. Even if in we started with being the seventeenth uncountable cardinal, in it could be that is just a countable ordinal! This is where the ccc property comes to our rescue, as we shall now see see see.

Theorem 1

If is ccc, then preserves cardinals. That is, if in we have , then in we have too.

The key reason for this is the following property of ccc partial orders, which allows us to predict function values in a forcing extension with a countable degree of accuracy.

Lemma 2

Let be a ccc partial order, and a -generic filter, and suppose that . If and , then there is such that and for all we have is countable and .

 Proof.

Let denote a name for , so that by the forcing theorem there exists such that . Define

To see that , note that if then by the forcing lemma there is some such that . Using the downwards-directed property of we can assume that , and hence obtain that .

To see that is countable, for each select a particular such that . We claim that if then is incompatible with . Otherwise, we would be able to find with . Letting be a -generic filter with , then in we would have both and , a contradiction. Thus the set of for forms an antichain, and so by the ccc property we must have that is countable.

Proof of Theorem 1

Let be a cardinal in , and first assume that is a successor cardinal . Suppose towards a contradiction that in there is a cardinal and an onto function . By the previous lemma, in there is a function such that is countable for all and . But now in we can use together with a bijection between and to obtain an onto function , contradicting that is a cardinal in .

Finally if is a limit cardinal , then is the limit of the successor cardinals . Since we have just shown that successor cardinals are preserved, remains a limit of cardinals in . Since a limit of cardinals is a cardinal, is a cardinal in .

 Remark 1

In fact, something stronger is true: forcing with a ccc partial order preserves not only cardinals but also cofinalities. Roughly, this means that if is an ordinal in , then cannot have a shorter unbounded sequence in than does.

Proposition 1

The partial order is ccc.

A family of sets is called a delta system if there exists a set such that for every we have . The set is called the root of the delta system.

Lemma 3 Delta system lemma

Let be any cardinal, and let be an uncountable family of finite subsets of . Then there exists an uncountable subset which forms a delta system.

 Proof.

Since there are only countably many possible values of for , by the pigeon-hole principle we can replace with an uncountable subset of it such that some fixed value for all .

Now we use induction on . If , then forms a delta system automatically. Next suppose that the claim is true for families of sets of size . First consider the case that there is some which lies in uncountably many of the . Then by the inductive hypothesis we can find a delta system contained in . It follows that the family is a delta system too.

Second consider the case that every , is contained in just countably many of the . Then we can inductively find an uncountable subfamily that is pairwise disjoint, and hence a delta system with trivial root. Indeed, if countably many pairwise disjoint sets have been found so far, then all the ordinals in are still only contained in countably many of the . This means that we can find an disjoint from them all, and completes the proof of the claim.

 Proof of Proposition 1

It suffices to show that any uncountable contains two compatible elements. In fact we will show that it contains uncountably many pairwise compatible elements. For this we first consider the corresponding family of domains . Then is an uncountable family of finite subsets of . Thus by Lemma 3, we can find an uncountable subset which forms a delta system with some root .

Now, let be the subset of consisting of functions such that . These functions may disagree on , but they can never disagree elsewhere. Since there are only countably many possibilities for , by the pigeon-hole principle we can replace with an uncountable subset of it such that some fixed function for all . It follows from this that every pair of elements of is compatible.
More tricks with the continuum

Since ccc forcing preserves cardinals, if satisfies CH then it is not possible to force CH using ccc forcing. Indeed, since forcing only adds sets (and never takes them away), the only way to lower the cardinality of the continuum is to collapse cardinals.

Definition 1

For any cardinals we define the set to be the family of all functions , where is a countable subset of . We partially order by iff .

Like its sibling , forcing with adds a new function . But as we'll see, it does it in a different way. For example, we showed that is ccc, but it is easy to see that is not ccc. For another thing, adds many new elements to , but if is uncountable adds no new elements to .

Theorem 1

Let and let be a -generic filter. Then satisfies CH.

In a moment we will prove that forcing with adds a surjection from onto . However, once again we have to be careful: we have to check that the of is the same as the of . In fact this will be true when forcing with any partial ordering satisfying the following simple property.

Definition 2

A partial order is countably closed if for every sequence of elements such that for all , there exists such that for all .

It is clear that whenever is uncountable, is an example of a countably closed partial order.

Lemma 1

If is countably closed, then forcing with does not add new elements of . Moreover forcing with does not collapse .

 Proof.

Let be an element of in , and let be a name for . We will show that in fact lies in . To begin, by the forcing theorem we can find some such that . Now, since has some value in , there is some such that satisfies . Hence we can find and such that . Moreover since is downwards directed, we can suppose without loss of generality that .

Repeating this argument inductivley, we can find and such that . Moreover we can assume that for all . Since is countably closed, there exists such that for all . Then for all , which means that ``knows'' every value of . It follows that is definable in by if and only if .

To see that does not collapse , let denote the ordinal such that in we have , and suppose towards a contradiction that in we have that is countable. Then in there is a surjective function . Note that in the argument of the previous paragraph we only needed that the domain of was and the codomain of was a set in . Hence we can use the same reasoning to conclude that is definable in , contradicting that is uncountable in .

 Proof of Theorem 1

By Lemma 1, the notions of and are identical in and . Thus in the rest of this argument we need not distinguish in which model they are computed.

To begin, it is clear that is a new function from . Now for each consider the set

Then is dense: indeed, if is element of then we can find some such that , and define an extension such that .

It follows that has the property: for every there exists such that for all we have . In other words, every element of the Baire space is coded in the values of . Since there are only many possible functions coded in this way, we have .

We now return to the argument of the previous section. Recall that we showed forcing with results in the continuum having value . With a slightly more careful argument, we can actually show that in fact the continuum has size exactly .

Theorem 2

Suppose that in , CH is true and is an uncountable cardinal such that . Let and let be a -generic filter. Then in , we have .

Proof.

We have already shown that in we have . To show that , it suffices to show that in there are at most many subsets of . To this end, we claim that every subset of in has a nice name, that is, a name of the form

where for each , is an antichain of .

Admitting this claim, since is ccc, we know that each antichain is countable. It follows that there are only many possibilities for the name , and hence only many possibilities for the set . Since we have assumed that , this completes the proof.

To establish the claim, let be a subset of and let be a name for . By the forcing theorem there is some such that . Now consider the sets

Using Zorn's Lemma, we can find a maximal antichain . We will show that the corresponding nice name is a name for .

First, it is clear that , since if then and hence satisfies . Conversely, suppose that satisfies and let be such that . As usual since is downwards directed we can suppose that . We now consider the set

Then is dense: given any , if is incompatible with , then itself lies in . Otherwise is compatible with and hence there is . Then lies in the set , and since is a maximal antichain in , we must have that is compatible with some . Hence we can find , and then .

Finally, since is generic, there is some and an element with . Since is closed upwards, too, and since we have . This shows that , as desired.

 Remark 1

If satisfies we say that has uncountable cofinality. For example, any successor cardinal has uncountable cofinality. K\"onig's theorem states that always has uncountable cofinality. Thus Theorem 2 implies that K\"onig's theorem is sharp.

 Exercise 1

Kunen, exercise IV.7.10.
Cohen forcing and the domination order

In the previous sections we studied the effect of the forcing on the value of the continuum . For the next two sections, we generalize our previous results by exploring the effect of forcing with on the values of the other cardinal characteristics in Cichoń's diagram. In this section, we consider just the cardinals associtaed with the domination order , namely and .

Before we study the effect of the -sized Cohen forcing , we first examine the effect of the countable Cohen forcing . The key result is the following lemma, which showcases the narrow window that Cohen forcing occupies with respect to the domination order .

Lemma 1

Let , and let be a -generic filter. Then we have:

  • If , then is not -dominated by any element of .
  • If , then not every element of is -dominated by .
 Proof.

The proof of the first statement is a simple density argument, which we leave for Exercise 1.

For the second statement, let and let be a -name for . We wish to define a function which is not dominated by . For this, since is countable, we can enumerate . For each , we then define the approximation to given by

(If the above maximum is undefined, then set by default.) We now diagonalize against these approximations to to define a function such that for all . Specifically we let

and observe that lies in by the definability theorem. We claim that this is in fact not dominated by .

For this, if we have then we can find such that for all we have . By the forcing theorem, we can find such that . But now if we choose any , then by definition of we have , and by definition of we have . This is a contradiction!

In order to use the above result about to establish properties of the full forcing , we need the following fact which essentially says that the full forcing can be factored into smaller pieces.

Lemma 2

Let and let be a -generic filter for . Suppose that , and set and ; likewise set and . Then is -generic for , is -generic for , and .

 Proof.

It is straightforward to verify that and are filters. Moreover, since and are defined from , and can be recovered from and , it follows easily that .

To show that is -generic for , let be a dense subset of . Letting

it is trivial to see that is dense in . Since is -generic for , there exists an element . Then , and since is closed upwards, we have too. Thus , as desired.

To show that is -generic for is analogous but slightly trickier. For this, let be a dense subset of , and let be a -name for . Using the forcing theorem, we can find such that `` is dense in ''. Let

We claim that is dense in . Indeed, let be an arbitrary element of , where and . If then we are done, so suppose instead that . Since is dense in , there exists such that . Then by the forcing theorem there exists such that . Letting , we have that , as desired.

Now, since is -generic for , there exists an element . Then , and by definition of we have that too. Thus again we have , as desired.

We are now ready to state the effect of forcing with on the cardinals and .

Theorem 1

Suppose that in , CH is true and is an uncountable cardinal such that . Let and be a -generic filter. Then in , we have and .

 Proof.

We first show that . Recall that we already know that . Now suppose, towards a contradiction, that . That is, in there exists a dominating family such that . We claim that there is some such that and is added by the forcing .

To establish the claim, we first code as a subset of by enumerating and letting

Now let be a nice name for (see the proof of Theorem 2), and note that since is ccc there are at most many elements of mentioned in . Each of these many elements of in turn has just finitely many ordinals in its domain. Letting be the union of all these domains, we have that is a -name and hence is added by the forcing .

We now reach a contradiction as follows. Let , , , and . Then the dominating family lies in . But forcing with over adds the generic element to the Baire space. Applying Lemma 1 to the ground model , we see that is not dominated by any element of , a contradiction.

We now turn to the proof that . Since the Baire space of the ground model, , is itself a family of size , it suffices to show that remains unbounded in . So suppose to the contrary that some is a bound for .

We first show that we can suppose is added by a countable fragment of the forcing . For this, let be a nice name for . Then once again since is ccc, mentions just countably many elements of and these elements each use just finitely many elements of the domain . Hence there exists a countable subset such that is already added by the partial order .

Now, since , by Lemma 1 we have that does not dominate the Baire space of . This is a contradiction!

 Exercise 1

Show that if and is -generic, then is not dominated by any element of the Baire space of .

 Exercise 2

Kunen, exercise IV.4.11.
Cohen forcing and Cichoń's diagram

In the previous section we began to study the effect of Cohen forcing on the values of the cardinals in Cichoń's diagram. In this section we complete this study by establishing the following result.

Theorem 1

Suppose that in , CH is true and is an uncountable cardinal with . Then forcing with results in all cardinals in the left half of Cichoń's diagram equal to , and all cardinals in the right half of Cichoń's diagram equal to (see fig:cichon-cohen$).
Values of the cardinal characteristics in Cichoń's diagram after Cohen forcing. Refer to fig:cichon$ for the template of cardinal characteristics.

The key to the proof of this theorem is to establish the analogs of the statements in Lemma 1. For the statements we need our combinatorial characterization of meager sets by difference sets. Recall from Proposition 1 that a subset is meager if and only if is contained in some set of the form . Here, is a partition of into intervals, , and denotes the set of all which differ from on almost every interval of .

Lemma 1

Let , and let be a -generic filter. Then we have:

  • If , then does not lie in any set of the form where .
  • If , then not every element of lies in .

In other words, the first statement says that the generic does not lie in in any meager set coded in , and the second statement says that the Baire space of the ground model remains nonmeager after the forcing.

Proof. The proofs of the two statements can be viewed as slight improvements to the arguments of Lemma 1. For the first statement, let be an interval partition and , with . For each let

Then it is easy to see that is dense: given one can choose large enough so that , and then extend to as required. It follows that has the property that for all there exists such that . This means precisely that does not lie in .

For the second statement, let be an interval partition and , with both . Let and be -names for and respectively. We will recursively construct an element which does not lie in .

To do this, first enumerate the set of pairs as . We will construct as the union of approximations as follows. Assuming has already been defined, choose large enough that . Using Lemma 3 we can find and a fixed sequence such that . We now define to be an extension of such that too.

Finally, we let and claim that . To see this, suppose towards a contradiction that . Then by the forcing theorem we could find and such that . But now if is such that , then by construction there exists and such that . This is a contradiction, since is an extension of that forces something contrary to !

We are now ready to complete the proof of Theorem 1. Referring to the ZFC-provable inequalities of fig:cichon$, to establish this result it suffices to prove that just the following two equalities in .

Theorem 2 Under the hypotheses of Theorem 1, in we have and . Proof.

Once again, the proofs of these two statements are similar to the arguments of Theorem 1.

We first show that . So suppose, towards a contradiction, that . That is, in there exists a family of meager subsets of such that and . Note that we can suppose without loss of generality that every element of is of the form .

We again claim that there is some such that and is added by the forcing . To see this, observe that an interval partition can be coded by its sequence of endpoints, and hence can be coded as a subset of . Thus we can use a nice name argument as in the proof of Theorem 1 to find as required.

Now let , , , and . Then the covering family lies in . But now by Lemma 1, does not lie in any set of the form of , a contradiction.

To show that , it suffices to show that itself remains nonmeager in . So suppose to the contrary that is meager in . Then there exist some such that .

Using a nice name argument, we can as usual suppose that the countable objects and are added by a countable fragment of the forcing . But now is becomes meager after forcing with , contradicting Lemma 1.
Random forcing

The previous section provided one possible picture of Cichoń's diagram after forcing: the left half of the diagram is small, the right half large. It turns out that many other configurations can be achieved with more creative forcing partial orders. In this section we begin to explore the effect of random forcing which, as we will see, does for measure what Cohen forcing did for category.

The random forcing partial order can be defined on any of the spaces , , or , but in order to generalize it later we will define it on Cantor space . Recall that we use the ``coin-tossing'' measure on , which is defined analogously to the Lebesgue measure of Equation~ but with the length replaced by the probability . Thus we have

As usual, the function has the properties of a measure on a class of sets containing all Borel sets. The null ideal on consists of those for which .

Definition 1

The random forcing partial order consists of equivalence classes of nonnull (Borel) subsets . Here, two subsets and are called equivalent iff the symmetric difference is null. The set is partially ordered by iff is null.

The random forcing partial order is also a Boolean algebra, which means that we can take pairwise joins (unions), meets (intersections), and complements. Although we will not develop the theory here, it turns out that any partial order is forcing equivalent to a Boolean algebra. For example, Cohen forcing is equivalent to the partial order consisting of equivalence classes of nonmeager subsets of , where sets are equivalent if their symmetric difference is meager.

Like Cohen forcing, if is a -generic filter for random forcing then there is a corresponding generic element . In order to define , first observe that for each the elements for form a maximal antichain of . It follows that for each , there is exactly one with . We may then let

This is well-defined since the elements of are pairwise compatible.

Just as the Cohen generic real lies in every comeager set coded in the ground model, this generic is ``random'' in the sense that it lies in every conull set coded in the ground model. Before showing this, we should say precisely what we mean by this coding. While it is possible to code arbitrary Borel sets, for simplicity we will state the result only for sets.

Recall that a subset of is called if it is a countable intersection of open sets. Thus any set can be expressed as , and we say that the sequence is a code for . If is a forcing extension of and is a set of coded by , then we let be the set in with the same code.

Lemma 1

Let , let be -generic, and the corresponding generic element of . Suppose is a set of , and let be the interpretation of in . Then if is conull then lies in , and if is null then lies in the complement of .

 Proof.

First suppose that is open, that is, has the form , and assume that is conull. Then the set

is dense: any nonnull has nonnull intersection with some and therefore is an element of which lies in . Since is generic, there is some such that lies in . By definition of , it follows that and therefore .

Now suppose that is , so has the form , and that is conull. Then each of the sets is conull too. By the previous argument, lies in for all . Thus , as desired.

Finally if is null then has the form and is conull. By a similar dense set argument, one of the sets must satisfy . Thus for this we have that for all , and hence . Therefore we have that for some , , in other words, .

As we mentioned, this result can be stated for Borel sets as well; one simply uses induction to reach sets with more complex codes. Meanwhile it follows from Lemma 1 that the random real is new. Indeed, if is any element of the ground model , then is a conull set (in fact it is open). Thus lies in this set (interpreted in , and in particular .

Just as Cohen forcing has a -sized version , random forcing has a -length version . Like the -sized Cohen forcing, the -sized random forcing adds many new elements to Cantor space and therefore pushes the value of the continuum up to .

To make the definition of precise, we recall that the product topology on has a basis consisting of the sets , where is a function from a finite subset of to . The measure on is again defined by assigning to each the measure and extending it as before.

Theorem 1

Suppose that in , CH is true and is an uncountable cardinal such that . Let and let be a -generic filter. Then in , we have .

 Proof.

We first claim that is ccc, and hence remains a cardinal in . To see this, first note that two elements of are incompatible if and only if is null. Thus it suffices to show that if is a family pairwise disjoint, nonnull subsets of , then is countable. For this, since the full space has measure , for each there can be just finitely many elements of of measure . It follows that there can be just countably many elements of in total, and so is ccc.

Next, we claim that adds many distinct elements to . First, by the definition given above in the case of , we can use to define a corresponding function . We then define a family of many elements of by letting for every limit ordinal . Then the are pairwise distinct because this happens with probability one. More percisely, for any distinct limit ordinals let

Then is and null. To see that it is null, note that is the intersection of the independent events

Since each of these events has probability , we have and so is null. It now follows from Lemma 1 that lies in the complement of (interpreted in ) and therefore that .

We can now conclude that in we have . Finally by the nice name argument of Theorem 2, it is also easy to argue that .

Exercise 1

Show that the random forcing partial order, together with , forms a complete Boolean algebra. Here, a Boolean algebra is complete if every subset has a least upper bound.
Random forcing and Cichoń's diagram

So far we have seen only similarities between the effects of Cohen and random forcing. In this section we investigate the effect of random forcing on Cichoń's diagram, and in the process we'll see that the two forcing notions are not the same. In fact the effect random forcing on the characteristics of . is analogous to the effect of Cohen forcing on the characteristics of

Theorem 1

Suppose that in , CH is true and is an uncountable cardinal. Then forcing with results in all cardinals in the bottom two lines of Cichoń's diagram equal to and all cadrinals in the top line of Cichoń's diagram equal to (see fig:cichon-random$).
Values of the cardinal characteristics in Cichoń's diagram after random forcing. Refer to fig:cichon$ for the template of cardinal characteristics.

We begin by addressing the effect of random forcing on the domination order. The following result shows that a much stronger property holds than in the case of Cohen forcing; compare it with Lemma 1.

Lemma 1

Let and let be a -generic filter. Then in we have that for all there exists such that .

 Proof.

It suffices to define a function in with the property that for every there exists such that . Indeed, if this is the case then the set of such is dense, and so there is such a in . Then by the forcing theorem we will have that satisfies .

For each fixed , we define as follows. For each , let be such that . If there is no such , simply let . Then the collection of is pairwise incompatible, or in terms of representing sets, pairwise disjoint. Letting , choose to be large enough so that the measure of is at least .

Now clearly . Therefore, if then as desired. However, we must check that is not null, and this follows from our choice of the :

It follows that , and this completes the proof.

We can use this result directly to compute the values of and in the random forcing extension.

Theorem 2

Suppose that in , CH is true and is an uncountable cardinal. Let and let be a -generic filter. Then in , we have .

 Proof.

By the previous lemma, the ground model is a dominating family of size in .

We now continue the proof of Theorem`Theorem 1. Referring to the known inequalities in Theorem 1, it remains only to show the following two equalities.

Theorem 3

Under the hypotheses of Theorem 1, in we have and .

Before the proof, we need a factorization lemma to take the place of Lemma 2. The following result is similar, but with one important difference. Whereas in Lemma 2 the two factors and were defined in , this time the second factor must be defined in the extension after the forcing with .

Lemma 2

Let , and let be -generic. Let , , and . Now in define and . Then is -generic for , is -generic for , and .

We omit the proof [temporarily]. [We also need the definition of , see Kunen V.4.30.]

Proof of Theorem 3

The proofs are analogous to the proofs of the two equalities in Theorem 2. To show that , assume to the contrary that . Then there exists a cardinal and a family of null sets such that and .

Since every null set is contained in a null set, we can suppose that every element of is a set. Thus every has a code, which is a countable collection binary sequences on a finite subset of . Using a now-familiar nice name argument, we can find a set with such that if and is as above, then the codes for all elements of appear in .

But now, the forcing adds a random real . By Lemma 1 we know that does not lie in any null set coded in . This contradicts that is a covering family in .

To see that , one can argue that the ground model reals form a nonnull set in the forcing extension. Alternatively we may let be the sequence of random reals added by the forcing, and show that the set is nonnull in .

For this, suppose to the contrary that is null. Then there is some null set such that . Once again using a nice name argument, we can find a countable set such that if and is as above, then appears in .

Finally, since is uncountable we can find some element which is not added by , and instead added over by the forcing . Once again using Lemma 1, since is a null set in we have that lies in the complement of . In particular, doesn't lie in , a contradiction.

 Notes 1

Some of the results of this section are proved in Kunen, Section IV.7. Others appear as exercises in Section V.4. The ideas of the proofs are also summarized in Blass, Subsection 11.4.
Hechler forcing and Cichoń's diagram

Values of the cardinal characteristics in Cichoń's diagram after Hechler forcing. Refer to fig:cichon$ for the template of cardinal characteristics.