Proceedings of the International Congress of Mathematicians Hyderabad, India, 2010

The Proper Forcing Axiom

Justin Tatch Moore

This article is dedicated to Stephanie Rihm Moore.

The author’s preparation of this article and his travel to the 2010 meeting of the International Congress of Mathematicians was supported by NSF grant DMS– 0757507. I would like to thank Ilijas Farah, Stevo Todorcevic, and James West for reading preliminary drafts of this article and offering suggestions.

Abstract. The Proper Forcing Axiom is a powerful extension of the Baire Category Theorem which has proved highly effective in settling mathematical statements which are independent of ZFC. In contrast to the Continuum Hypothesis, it eliminates a large number of the pathological constructions which can be carried out using additional axioms of set theory.

Mathematics Subject Classification (2000). Primary 03E57; Secondary 03E75.

Keywords. Forcing axiom, Martin’s Axiom, OCA, Open Coloring Axiom, PID, P-ideal Dichotomy, proper forcing, PFA

1. Introduction

Forcing is a general method introduced by Cohen and further developed by Solovay for generating new generic objects. While the initial motivation was to generate a counterexample to the Continuum Hypothesis, more sophisticated forcing notions can be used both to generate morphisms between structures and also obstructions to morphisms between structures.

Forcing axioms assert that the universe of all sets has some strong degree of closure under the formation of such generic objects by forcings which are sufficiently non pathological. Since forcings can in general add generic bijections between countable and uncountable sets, non pathological should include preserves uncountablity at a minimum. The exact quantification of non pathological yields the different strengths of the forcings axioms. The first and among the weakest of these axioms is Martin’s Axiom which was abstracted by Martin from Solovay and Tennenbaum’s proof of the independence of Souslin’s Hypothesis [59]. Progressively stronger axioms were formulated and proved consistent as advances were made in set theory in the 1970s. The culmination of this progression was [22], where the strongest forcing axiom was isolated.

Forcing axioms have proved very effective in classifying and developing the theory of objects of an uncountable or non separable nature. More generally they serve to reduce the complexity of set-theoretic difficulties to a level more approachable by the non specialist. The central goal in this area is to establish the consistency of a structure theory for uncountable sets while at the same time working within a single axiomatic framework.

In this article, I will focus attention on the Proper Forcing Axiom (PFA):

If Q is a proper forcing and 𝒜 is a collection of maximal antichains in Q with |𝒜 | ≤ ℵ_{1}, then there is a filter G ⊆ Q which meets each element of 𝒜.

This axiom was formulated and proved consistent relative to the existence of a supercompact cardinal by Baumgartner using Shelah’s Proper Forcing Iteration Lemma. The details of the formulation of this axiom need not concern us at the moment (see Section 5 below). I will begin by mentioning two applications of PFA.

Theorem 1.1. [7] Assume PFA. Every two ℵ_{1}-dense sets of reals are isomorphic.

Theorem 1.2. [57] Assume PFA. If Φ is an automorphism of the Boolean algebra 𝒫(ℕ)/Fin, then Φ is induced by a function ϕ : ℕ → ℕ.

The role of PFA in these two theorems is quite different. In the first case, PFA is used to build isomorphisms between ℵ_{1}-dense sets of reals (here a linear order is κ-dense if each of its proper intervals is of cardinality κ). The procedure for doing this can be viewed as a higher cardinal analog of Cantor’s back-and-forth argument which is used to establish that any two ℵ_{0}-dense linear orders are isomorphic. As we will see in Section 3.1, however, the situation is fundamentally more complicated than in the countable case since there are many non isomorphic ℵ_{1}-dense linear orders.

In the second theorem, PFA is used to build an obstruction to any non trivial automorphism of 𝒫(ℕ)/Fin. This grew out of Shelah’s seminal result in which he established the consistency of the conclusion of Theorem 1.2 [56, Ch. IV]. The difference between Theorems 1.2 and 1.1 is that one can generically introduce new elements to the quotient 𝒫(ℕ)/Fin. This can moreover be done in such a way that it may be impossible to extend the function Φ to these new generic elements of the domain.

In both of the above theorems, there is a strong contrast with the influence of the Continuum Hypothesis (CH). CH implies that there are 2^{2^{ℵ_{0}}} isomorphism types of ℵ_{1}-dense sets of reals [14] and 2^{2^{ℵ_{0}}} automorphisms of 𝒫(ℕ)/Fin [52] (notice that there are only 2^{ℵ_{0}} functions from ϕ : ℕ → ℕ). This is in fact a common theme in the study of forcing axioms.

I will finish the introduction by saying that there was a great temptation to title this article Martin’s Maximum. Martin’s Maximum (MM) is a natural strengthening of PFA in which proper is replaced by preserves stationary subsets of ω_{1}. This is the broadest class of forcings for which a forcing axiom is consistent. This axiom was proved consistent relative to the existence of a supercompact cardinal in [22].

I have chosen to focus on PFA instead for a number of reasons. First, when applying forcing axioms to problems arising outside of set theory, experience has shown that PFA is nearly if not always sufficient for applications. Second, we have a better (although still limited) understanding of how to apply the PFA. (Of course this is an equally strong argument for why we need to develop the theory of MM more completely and understand its advantages over PFA.)

Finally, and most importantly, a wealth of new mathematical ideas and proofs have come out of reducing the hypothesis of MM in existing theorems to that of PFA. In every instance in which this has been possible, there have been significant advances in set theory of independent interest. For example the technical accomplishments of [45] led to the solution of the basis problem for the uncountable linear orders in [46] soon after. Thus while MM is trivially sufficient to derive any consequence of PFA, working within the more limited framework of PFA has led to the discovery of new consequences of MM and new consistency results.

The reader is referred to [22] for the development of MM and to [9, pp. 57–60] for a concise account of the typical consequences of MM which do not follow from PFA. An additional noteworthy example can be found in [31]. Finally, the reader is referred to [87] for a somewhat different axiomatic framework due to Woodin for achieving some of the same end goals. It should be noted that reconciling this alternate framework with MM (or even PFA) is a major open problem in set theory.

This article is organized as follows. After reviewing some notation, I will present a case study of how PFA was used to give a complete classification of a certain class of linear orderings known as Aronszajn lines. After that, I will present two combinatorial consequences of PFA and illustrate how they can be applied through several different examples. These principles both have a diverse array of consequences and at the same time are simple enough in their formulation so as to be usable by a non specialist. In Section 5, I will formulate PFA and illustrate Todorcevic’s method of building proper forcings. I will utilize the combinatorial principles from the previous section as examples to illustrate this technique. Section 6 presents some examples of how PFA has been successfully used to solve problems arising outside of set theory. The role of the equality 2^{ℵ_{0}} = ℵ_{2}, which follows from PFA, will be discussed in Section 7. Section 8 will give some examples of how the mathematics developed in the study of PFA has been used to prove theorems in ZFC. I will close the article with some open problems.

With the possible exception of Section 5, I have made an effort to keep the article accessible to a general audience with a casual interest in the material. Needless to say, details are kept to a minimum and the reader is encouraged to consult the many references contained throughout the article. In a number of places I have presented examples and stated lemmas simply to hint at the mathematics which is being omitted due to the nature of the article. It is my hope that the curious reader will take a pen and paper and try to fill in some of the details or else use this as an impetus to head to the library and consult some of the many references.

2. Notation and background

The reader with a general interest in set theory should consult [32]. Further information on linear orders, trees, and coherent sequences can be found in [67] and [79], respectively. Information on large cardinals and the determinacy of games can be found in [29]. Further information on descriptive set theory can be found in [30].

For the most part I will follow the conventions of [32]. ℕ = ω will be taken to include 0. An ordinal is a set α linearly ordered by ∈ such that if β is in α, then β ⊆ α. Thus an ordinal is the set of its predecessors. In particular ω_{1}, which is the first uncountable ordinal, is the set of all countable ordinals. A cardinal is the least ordinal of its cardinality. While ℵ_{α} is a synonym for ω_{α}, the former is generally used to measure cardinality while the latter is generally used to measure length and when there is a need to refer to the set itself. Lower case Greek letters will be used to denote ordinals, with κ, λ, μ, and θ denoting cardinals.

If X is a set, then [X]^{k} denotes all subsets of X of cardinality k. In particular, [X]^{2} is the set of all unordered pairs of elements of X. A graph is a pair (G, X) where X is a set and G ⊆ [X]^{2} (X is the vertex set and G is the edge set).

A tree is a partial order (T, ≤) in which the predecessors of each element of T are well ordered by <. The ordertype of the set of strict predecessors of a t in T is the height of t; the collection of all elements of T of a fixed height is a level of T. All trees will also be assumed to be Hausdorff : if s and t have limit height and the same sets of predecessors, then they are equal. In particular, trees are equipped with a well defined meet operation ∧ : T × T → T. A subset of a tree is an antichain if it consists of pairwise incomparable elements (in the setting of trees this coincides with the notion of antichain in Section 5 below).

Generally a superscript of ∗ on a relation symbol is taken to mean “with only a finite number of exceptions” (in a context in which this makes sense). In particular, A ⊆^{∗} B means that A \ B is finite.

An ideal ℐ on a set S is a subset of 𝒫(S) which is closed under subsets and finite unions. To avoid trivialities, all ideals in this article will be assumed to contain all of the finite subsets of the underlying set. Fin is the ideal of all finite subsets of ℕ. Fin × ∅ is the collection of all subsets of ℕ × ℕ in which all but finitely many vertical sections are empty. ∅ × Fin is the collection of all subsets of ℕ × ℕ in which all vertical sections are finite. An ideal ℐ is a P-ideal if (ℐ , ⊆^{∗}) is countably directed (i.e. every countable subset has an upper bound). ∅ × Fin is a P-ideal; Fin × ∅ is not. If ℐ is a collection of subsets of S, then ℐ^{⊥} is the ideal of all subsets of S which have finite intersections with all elements of ℐ. Observe that (∅ × Fin)^{⊥} = Fin × ∅ and (Fin × ∅)^{⊥} = ∅ × Fin.

Throughout this article, all topological spaces are assumed to be T_{3}. When discussing Banach spaces, basis will always refer to a Schauder basis. A Polish space is a separable, completely metrizable topological space. A subset of a Polish space is analytic if it is the continuous image of a Borel set in a Polish space. The σ-algebra generated by the analytic sets will be denoted by 𝒞.

3. Classification and ℵ_{1}

3.1. The basis problem for uncountable linear orders: a case

study. In order to illustrate the influence of PFA and how it plays a role in classification problems for uncountable structures, I will begin with an example of a recent success in this area. Consider the following problem.

Problem 3.1. Do the uncountable linear orders have a finite basis?

That is, is there a finite set of uncountable linear orders such that every other contains an isomorphic copy of one from this finite set?

Observe that any such basis must contain a set of reals of minimum possible cardinality — namely ℵ_{1}. The following theorem, which actually predates PFA, shows that under PFA a single set of reals of cardinality ℵ_{1} is sufficient to form a basis for the uncountable separable linear orders.

Theorem 3.2. [7] Assume PFA. Every two ℵ_{1}-dense sets of reals are isomorphic. In particular any set of reals of cardinality ℵ_{1} embeds into any other.

This is in stark contrast to the situation under CH.

Theorem 3.3. [14] If X ⊆ ℝ with |X| = |ℝ|, then there is a Y ⊆ X with |Y | = |X| such that no two distinct subsets of Y of cardinality |ℝ| are isomorphic. In particular if |ℝ| = ℵ_{1}, then there is no basis for the uncountable suborders of ℝ of cardinality less than |𝒫(ℝ)|.

In fact this is part of general phenomenon: it is typically not possible to classify arbitrary structures of cardinality 2^{ℵ_{0}}. (This statement is not meant to be applied to objects such as manifolds which, while of cardinality 2^{ℵ_{0}}, are really coded by a countable — or even finite — mathematical structure.)

How does one reconcile Theorems 3.2 and 3.3? Baumgartner’s result actually shows that given any model of ZFC, it is possible to go into a forcing extension in which uncountability is preserved and every two ℵ_{1}-dense sets of reals are isomorphic. In particular, two ℵ_{1}-dense sets of reals which may not have been isomorphic are made isomorphic by Baumgartner’s forcing. Thus while CH implies that there are many non-isomorphic ℵ_{1}-dense sets of reals, the reason for this is simply that there is an inadequate number of embeddings between such orders, rather than some intrinsic property of the sets of reals which prevents them from being isomorphic.

Now we return to our basis problem. Since ω_{1} can not be embedded into ℝ and since ω_{1} is isomorphic to each of its uncountable suborders, any basis for the uncountable linear orders must also contain ω_{1} and −ω_{1}. The following classical construction of Aronszajn and Kurepa shows that any basis for the uncountable linear orders must have at least four elements (see [67, 5.15] for a historical discussion).

Theorem 3.4. There is an uncountable linear order which does not contain an uncountable separable suborder and does not contain ω_{1} or −ω_{1}.

Such linear orders are commonly known as Aronszajn lines or A-lines. Regardless of the value of 2^{ℵ_{0}}, A-lines necessarily have cardinality ℵ_{1}. Like uncountable suborders of ℝ, every A-line contains an ℵ_{1}-dense suborder. Following Theorem 3.2, there was an effort to prove an analogous result for the class of A-lines. It turned out that the answer to this pursuit lay in the following question of R. Countryman.

Question 3.5. Does there exist an uncountable linear order C such that C × C, equipped with the coordinatewise partial order, is the union of countably many chains?

Such linear orders are known as Countryman lines or C-lines. Clearly every uncountable suborder of a C-line is a C-line. It was observed by Galvin that such linear orders are necessarily Aronszajn. Their most remarkable property is that if C is a C-line, then no uncountable linear order can be embedded into both C and −C. Indeed, if f : L → C and g : L → −C were to witness such embeddings, then the range of f × g, regarded as a subset of C × C, would be the graph of a strictly decreasing function. As such a graph can intersect every chain in C × C in at most a singleton, L must be countable. Thus, unlike the situation with uncountable suborders of ℝ under CH, there is a fundamental obstruction preventing an embedding of C into −C if C is a C-line. The following theorem of Shelah, therefore, ruled out an analog of Baumgartner’s result for ℵ_{1}-dense A-lines.

Theorem 3.6. [55] There is a Countryman line.

It was in this paper that precursors of Problem 3.1 began to be considered. Shelah made two conjectures at the end of [55]:

1. It is consistent that every two Countryman lines contain uncountable suborders which are either isomorphic or reverse isomorphic.

2. (PFA) It is consistent that every Aronszajn lines contains a Countryman suborder.

Shelah’s construction led Todorcevic to prove the following theorem, indicating that such linear orders occur quite naturally.

Theorem 3.7. [69] If e_{β} (β < ω_{1}) is a coherent sequence such that for each β, e_{β} is a finite-to-one function from β into ω, then the lexicographical order on the sequence is a Countryman line.

Here a sequence e_{β} (β < ω_{1}) with e_{β} : β → ω is coherent if whenever β < γ, e_{β} =^{∗} e_{γ} ↾ β. Given such a sequence, we can also form an Aronszajn tree T = {e_{β} ↾ α : α ≤ β < ω_{1}}. Here an Aronszajn tree (or A-tree) is an uncountable tree in which all levels and chains are countable. An A-tree which is the set of restrictions of a coherent sequence is said to be coherent.

Before proceeding, I will mention the method from [69] for explicitly constructing such a coherent sequence. Let ⟨C_{α} : α < ω_{1}⟩ be a sequence such that C_{α+1} = {α} and if α is a limit ordinal then C_{α} is a cofinal subset of α isomorphic to ω. Such a sequence is known as a C-sequence. Given a C-sequence, there is a canonical “walk” between any two ordinals α < β in ω_{1}:

β_{i} = \begin{cases}β & if i = 0 \\ min(C_{β_{i−1}} \ α) & if i > 0 and β_{i−1} > α \end{cases}

The walk starts at β and stops once α is reached at some stage l (l is always finite since otherwise we would have defined an infinite descending sequence of ordinals). Such walks have a number of associated statistics:

ϱ_{0}(α, β) = ⟨|C_{β_{i}} ∩ α| : i < l⟩
ϱ_{1}(α, β) = max ϱ_{0}(α, β)
ϱ_{2}(α, β) = l = |ϱ_{0}(α, β)|

If we set e_{β}(α) = ϱ_{1}(α, β), then this defines a coherent sequence satisfying the hypothesis of Theorem 3.7. In fact if we define (for i = 0, 1, 2)

C(ϱ_{i}) = ({ϱ_{i}(·, β) : β < ω_{1}}, ≤_{lex})
T (ρ_{i}) = ({ϱ_{i}(·, β) ↾ α : α ≤ β < ω_{1}}, ⊆)

then C(ϱ_{i}) is a C-line and T (ϱ_{i}) is an A-tree. Not only does the above construction yield an informative example of a C-line and an A-tree, it is the simplest instance of a widely adaptable technique of Todorcevic for building combinatorial objects both at the level of ℵ_{1} and on higher cardinals. A modern account of this can be found in [79].

Again we return to our analysis of Problem 3.1. The following theorem of Todorcevic shows that, under PFA, C-lines are indeed canonical objects.

Theorem 3.8. (see [48]) Assume MA_{ℵ_{1}}. If C and C′ are Countryman lines which are ℵ_{1}-dense and non stationary, then either C ≃ C′ or −C ≃ C′.

Here an A-line A is non stationary if A = ⋃ 𝒞 where 𝒞 ⊆ [A]^{ω} is a ⊆-chain which is closed under countable unions and is such that if X is in 𝒞, then the convex components of A \ X contain no first or last elements. It is routine to show that every A-line contains an ℵ_{1}-dense non stationary suborder. On the other hand, there are 2^{ℵ_{1}} isomorphism types of ℵ_{1}-dense C-lines [71].

The following theorem reduced Problem 3.1 to a purely Ramsey theoretic statement about A-trees.

Theorem 3.9. [1] (see [79, §4.4] for a proof) Assume PFA. The following are equivalent:

1. Every Aronszajn line has a Countryman suborder;

2. For every Aronszajn tree T and every partition T = K_{0} ∪ K_{1}, there is an uncountable antichain A ⊆ T and an i < 2 such that s ∧ t is in K_{i} for all s ≠ t in A.

3. For some Aronszajn tree T, if T = K_{0} ∪ K_{1} then there is an uncountable antichain A ⊆ T and an i < 2 such that s ∧ t is in K_{i} for all s ≠ t in A.

Progress on Problem 3.1 then stopped until [64], where a number of additional properties of A-trees were discovered, assuming PFA.

Theorem 3.10. [64] Assume MA_{ℵ_{1}}. If T is a coherent Aronszajn tree, then

𝒰 (T) = {K ⊆ ω_{1} : ∃A ∈ 𝒜 (T)(∧(A) ⊆ K)}

is an ultrafilter, where 𝒜 is the collection of all uncountable antichains of T and ∧(A) = {s ∧ t : s ≠ t ∈ A}.

Theorem 3.11. [64] If S ≤ T denotes the existence of a strictly increasing map from S into T, then the class of all Aronszajn trees contains a ≤-antichain of cardinality 2^{ℵ_{1}} and an infinite <-descending chain.

Theorem 3.12. [64] Assume PFA. The coherent Aronszajn trees are linearly ordered by ≤ without a first or last element. Furthermore S ≤ T holds if and only if there is an increasing function f : ω_{1} → ω_{1} such that

U ∈ 𝒰 (T) if and only if f^{−1}(U) ∈ 𝒰 (S)

(i.e. βf(𝒰 (S)) = 𝒰 (T)).

Finally, the following theorem was proved, thus solving Problem 3.1. This was accomplished by proving that PFA implies (3) of Theorem 3.9.

Theorem 3.13. [46] Assume PFA. Every Aronszajn line contains a Countryman suborder.

Corollary 3.14. Assume PFA. If X ⊆ ℝ has cardinality ℵ_{1} and C is a Countryman line, then X, ω_{1}, −ω_{1}, C, and −C form a basis for the uncountable linear orders.

In the wake of Theorem 3.13, two additional results were obtained which completely clarified our understanding of the A-lines assuming PFA.

Theorem 3.15. [48] If C is a Countryman line, then the direct limit η_{C} of the alternating lexicographic products C × (−C) × ⋯ × (−C) is universal for the class of Aronszajn lines.

Theorem 3.16. [42] The Aronszajn lines are well quasi-ordered by embeddability: if A_{i} (i ∈ ℕ) are Aronszajn lines, then there are i < j such that A_{i} embeds into A_{j}.

These results draw a strong analogy between the A-lines and the countable linear orderings: C and −C play the roles of ℕ and −ℕ and η_{C} plays the role of ℚ. Theorem 3.15 is analogous to Cantor’s theorem that all countable dense linear orders are isomorphic; Theorem 3.16 should be compared to the following theorem of Laver.

Theorem 3.17. [34] The countable linear orders are well quasi-ordered by embeddability.

3.2. The Ramsey Theory of ω_{1}. The study of the Ramsey theory of ω_{1} has played a central role in the development of PFA (see, e.g., [70]). It was noticed early on by Sierpinski that the analog of Ramsey’s theorem for ω_{1} is false.

Theorem 3.18. [58] There is a partition [ω_{1}]^{2} = K_{0} ∪ K_{1} such that if X ⊆ ω_{1} is uncountable, [X]^{2} ∩ K_{i} ≠ ∅ for each i < 2.

This was strengthened considerably by Todorcevic, using the method of minimal walks discussed above.

Theorem 3.19. [69] There is a partition [ω_{1}]^{2} = ⋃_{ξ<ω_{1}} K_{ξ} such that if X ⊆ ω_{1} is uncountable, then [X]^{2} ∩ K_{ξ} ≠ ∅ for each ξ < ω_{1}.

Still, many problems in set theory boil down to Ramsey theoretic statements about ω_{1} for restricted classes of partitions or where weaker notions of homogeneity are required. Theorem 3.9 is a typical instance of this. Another important example is the reformulations of the S and L space problems in terms of Ramsey theoretic statements [51]. These problems were eventually solved with different outcomes.

Theorem 3.20. [65] [70] Assume PFA. Every non Lindelöf space contains an uncountable discrete subspace.

Theorem 3.21. [47] There is a non separable space without an uncountable discrete subspace. Moreover, there is no basis for the uncountable topological spaces of cardinality less than ℵ_{2}.

I will finish the section by mentioning another classification result under PFA which is closely aligned with the study of the Ramsey theory of ω_{1}.

Theorem 3.22. [68] Assume PFA. Every directed system of cardinality at most ℵ_{1} is cofinally equivalent to one of the following: 1, ω, ω_{1}, ω × ω_{1}, [ω_{1}]^{<ω}.

This classification was extended to the transitive relations on ω_{1} in [73]. It is interesting to note that it is unknown whether a similar classification of relations on ω_{2} is possible under any axiomatic assumptions. Such a classification would require that 2^{ℵ_{0}} > ℵ_{2} and in particular that PFA fails (see [68]).

4. Combinatorial Principles

While direct applications of PFA require specialized knowledge of set theory, there are an increasing number of combinatorial principles that follow from PFA which are at the same time powerful and approachable by the non specialist. Both applying these principles and isolating new and useful ones is an important theme in set theoretic research (it should be stressed that one must always hold utility as paramount here).

Two prominent examples are the P-Ideal Dichotomy [76] and Todorcevic’s formulation of the Open Coloring Axiom [70]:

PID: If X is a set and ℐ ⊆ [X]^{ω} is a P-ideal, then either

1. there is an uncountable Z ⊆ X such that [Z]^{ω} ⊆ ℐ or

2. X can be covered by countably many sets in ℐ^{⊥}.

OCA: If G is a graph on a separable metric space X whose edge set is topologically open, then either

1. there is an uncountable H ⊆ X such that [H]^{2} ⊆ G (i.e. G contains an uncountable complete subgraph) or

2. X can be covered by countably many sets Y such that [Y]^{2} ∩G = ∅ (i.e. G is countably chromatic).

I will now present a number of typical examples of graphs and ideals to which these principles can be applied.

Example 4.1. [2] Let G be the graph on ℝ^{2} consisting of all edges {(x, y), (x′, y′)} such that x < x′ and y < y′. Observe that G is open. If X is a complete subgraph of G, then X is the graph of a partial strictly increasing function from ℝ to ℝ. If A and B are uncountable subsets of ℝ, then the subgraph of G induced by A × B is never countably chromatic and therefore OCA implies that there is an uncountable partial increasing function from A to B.

Example 4.2. [70] Recall that if f and g are in ℕ^{ℕ}, then f <^{∗} g means that f(i) < g(i) for all but finitely many i. It is well known that this is a countably directed partial order. If f ≠ g are in ℕ^{ℕ}, define {f, g} ∈ G if there are i and j such that f(i) < g(i) and f(j) > g(j). This defines an open graph. Subsets E ⊆ ℕ^{ℕ} such that [E]^{2} ∩ G = ∅ are quite sparse. For example such an E can not contain an uncountable <^{∗}-well ordered set.

In [70, 0.7] it is shown that if X ⊆ ℕ^{ℕ} is unbounded and countably <^{∗}-directed, then there are f ≠ g in X such that f ≤ g (i.e. {f, g} is not in G). This can be used to argue that OCA implies every subset of ℕ^{ℕ} of cardinality ℵ_{1} is <^{∗}-bounded. This is among the simplest applications of the phenomenon of oscillation which is explored further in [44], [70] and in different contexts in [47], [79].

Example 4.3. Let σℚ denote the collection of all subsets of ℚ which are well ordered in the usual order on ℚ. σℚ is a tree with the order defined by a ≤ b if a is an initial part of b. This is a separable metric space with the topology inherited from 𝒫(ℚ). Let G denote the set of all pairs {a, b} which are comparable in the tree order on σℚ. This is a closed graph on σℚ. Observe that if H ⊆ σℚ is a complete subgraph, then ∪H is in σℚ and every element of H is an initial part of ∪H. In particular, G has no uncountable complete subgraphs. On the other hand, if E ⊆ σℚ satisfies that [E]^{2} ∩ G is empty, then E is an antichain. Since σℚ is not a countable union of antichains [33], this example shows that the asymmetry in the statement of OCA is necessary, even for graphs on vertex sets which are nicely definable. By contrast, it is a ZFC theorem that the conclusion of OCA holds for every open graph on an analytic subset of a Polish space [21]. Furthermore, OCA holds for open graphs on projective sets as well under appropriate large cardinal assumptions.

For the next two examples, suppose that 𝒥 is a P-ideal on a set S and ϕ_{J} (J ∈ 𝒥) is a collection of functions such that ϕ_{J} is a function from J into some countable set C and whenever J and J′ are in 𝒥

{s ∈ J ∩ J′ : ϕ_{J}(s) ≠ ϕ_{J′}(s)}

is finite. Such a family of functions is said to be coherent. A coherent family of functions is trivial if there is a single Φ : S → C such that {s ∈ J : ϕ_{J}(s) ≠ Φ(s)} is finite for all J in 𝒥.

Example 4.4. [70, 8.7] If S is countable, then define a graph G on the set of pairs of elements of 𝒥 by {J, J′} ∈ G if and only if there is an s in J ∩ J′ such that ϕ_{J}(s) ≠ ϕ_{J′}(s). If we topologize 𝒥 by identifying it with the subspace {(J, ϕ_{J}) : J ∈ 𝒥 } of 𝒫(S) × 𝒫(S × S), then G is an open graph in a separable metric topology. If G is countably chromatic, then the coherent family is trivial. If ℋ ⊆ ℐ is uncountable and satisfies that [ℋ ]^{2} ⊆ G, then ℋ is unbounded in (𝒥 , ⊆^{∗}). Notice that any such ℋ contains such a subset of cardinality ℵ_{1} and therefore this alternative of OCA implies that (𝒥 , ⊆^{∗}) contains an unbounded subset of cardinality ℵ_{1}. Such an ℋ is quite closely related to the obstruction to non trivial automorphisms of 𝒫(ℕ)/Fin mentioned in the introduction.

An important instance of this example is when S = ℕ × ℕ and 𝒥 = ∅ × Fin. If every subset of (ℕ^{ℕ}, <^{∗}) of cardinality ℵ_{1} is bounded (this is a consequence of OCA), then every uncountable ℋ ⊆ 𝒥 contains an uncountable ℋ ′ whose union is in 𝒥. Thus OCA implies every coherent family indexed by ∅ × Fin is trivial.

Remark 4.5. In [38] it is shown that the triviality of coherent families of functions indexed by ∅ × Fin has an influence on the computation of the strong homology of certain locally compact subspaces of ℝ^{n}. Specifically, non-trivial coherent families indexed by ∅ × Fin coincide with the 1-cocycles in a certain cochain complex. This is used to show that, assuming CH, strong homology is not additive [38]. In [13] it is pointed out that PFA can be used rule out such 1-cocycles.

The existence of non-trivial n-cocyles in this cochain complex for any n, however, implies that strong homology fails to be additive [38, Theorem 8]. Unlike with 1-cocycles, very little is known what hypotheses entail the non existence of ncocycles beyond Goblot’s Vanishing Theorem (see [38]). For instance it is entirely possible that it is a theorem of ZFC that either 1-cocycles or 2-cocycles exist in this cochain complex. Additionally, while it is known that there are no 𝒞 -measurable 1-cocycles in this cochain complex, it is unclear whether the same can be said for n-cocycles for n > 1.

The body of work surveyed in [37, Ch. 11–14] has not yet been developed from a set-theoretic perspective (although see [62], [63], [74]). Recasting this material in set-theoretic language and developing it to the level of [79] would likely be a rewarding endeavor.

Example 4.6. [76] Given a coherent family ϕ_{J} (J ∈ 𝒥) of functions mapping into {0, 1}, we can define ℐ to be the collection of all countable I ⊆ 𝒥 such that for some J in 𝒥,

{J′ ∈ I : |{s ∈ J ∩ J′ : ϕ_{J}(s) = 0 ∧ ϕ_{J′}(s) = 1}| ≤ n}

is finite for each n in ℕ. If ℋ ⊆ 𝒥 is uncountable and satisfies that [ℋ ]^{ω} ⊆ ℐ, then ℋ is unbounded in (𝒥 , ⊆^{∗}). As noted above, this implies that (𝒥 , ⊆^{∗}) contains an unbounded subset of cardinality ℵ_{1}. If 𝒥 is a countable union of sets in ℐ^{⊥}, then the coherent sequence is trivial.

Example 4.7. [3] Suppose that T is an ω_{1}-tree (i.e. an uncountable tree in which every level is countable). Define ℐ to be the collection of all countable subsets I of T such that if t is in T, then {s ∈ I : s ≤ t} is finite. The assumption that the levels of T are countable implies that ℐ is a P-ideal. If Z ⊆ T is uncountable and [Z]^{ω} ⊆ ℐ, then it follows that Z contains an uncountable antichain. If T = ⋃_{n} S_{n} where S_{n} is in ℐ^{⊥}, then it follows that T is a countable union of chains. Since neither of these alternatives is compatible with T being a Souslin tree, PID implies Souslin’s Hypothesis.

Example 4.8. [76] Recall that if κ is a regular cardinal, then □(κ) is the assertion that there is a sequence ⟨C_{α} : α < κ⟩ with the following properties:

1. C_{α} ⊆ α is closed and unbounded for each α < κ and C_{α+1} = {α};

2. if α is a limit point of C_{β}, then C_{α} = C_{β} ∩ α;

3. there is no closed unbounded C ⊆ κ such that for every limit point α of C, C_{α} = C ∩ α.

As in Section 3.1, we can define ϱ_{2} : [κ]^{2} → ω using a □(κ)-sequence: ϱ_{2}(α, β) is the length of the walk from β down to α. If β < κ and n ∈ ω, set

K_{β,n} = {α < β : ϱ_{2}(α, β) ≤ n}.

One can argue that if ℐ is the collection of all countable I which have finite intersection with every K_{β,n}, then ℐ is a P-ideal which does not satisfy either alternative of PID. In fact, κ is not the union of countably many sets in ℐ^{⊥}, even though each β < κ has this property (as witnessed by {K_{β,n}}_{n}). The failure of □(κ) for all κ is known to have considerable large cardinal strength (see [53]).

In fact the properties of the family 𝒦 = {K_{β,n} : (β < κ^{+}) ∧ (n < ω)} which violate PID can be abstracted so as to be applied to more general situations. For instance this argument can be adapted to prove that PID implies that 2^{μ} = μ^{+} whenever μ is a singular strong limit cardinal [84].

5. Proper forcings and how to construct them

We will now turn to the task of formulating PFA. Recall that a forcing is a partial order Q with a greatest element. Elements of a forcing are generally referred to as conditions and q ≤ p is generally taken to mean q is an extension of p. Two conditions are compatible if they have a common extension and incompatible otherwise. A filter is a collection of conditions which is upward closed and downward directed.

An antichain is a collection of pairwise incompatible conditions. A forcing Q is c.c.c. if every antichain is countable.

A completely general example of a forcing is the collection of non empty open sets in a compact topological space, with U ≤ V defined to mean that \overline{U} ⊆ V. In this setting, points correspond to maximal filters and antichains are families of pairwise disjoint open sets. If U is dense and open in a topological space, then U is the union of a maximal antichain 𝒜 of open sets V such that V ≤ U. This allows one to translate forcing axioms into statements about Baire category.

Now we turn to formulating properness, which is a weakening of being c.c.c.. Unless specified otherwise, θ will always be used to denote a regular uncountable cardinal. Recall that H(θ) is the collection of all sets of hereditary cardinality at most θ. In this case (H(θ), ∈) satisfies all of the axioms of ZFC except possibly the powerset axiom. M ⊆ H(θ) is an elementary submodel of H(θ) if whenever ϕ(x_{1}, …, x_{n}) is a formula in the language of set theory and a_{1}, …, a_{n} are in M, (M, ∈) satisfies ϕ(a_{1}, …, a_{n}) if and only if (H(θ), ∈) satisfies ϕ(a_{1}, …, a_{n}).

If Q is a forcing, then a suitable model for Q is a countable elementary submodel of H(θ) for some θ such that 𝒫(Q) is in M. If M is a suitable model for Q, then a condition in q is (M, Q)-generic if whenever A ⊆ Q is a maximal antichain which is in M, every extension of q is compatible with an element of A ∩ M. Finally, Q is proper if whenever M is a suitable model for Q, every condition in Q ∩ M has an (M, Q)-generic extension. We are now in a position to understand the formulation of PFA given in the introduction:

If Q is a proper forcing and 𝒜 is a collection of maximal antichains in Q with |𝒜 | ≤ ℵ_{1}, then there is a filter G ⊆ Q such that G ∩ A ≠ ∅ for every A in 𝒜.

Thus PFA is just the statement obtained by replacing “c.c.c.” by “proper” in the formulation of MA_{ℵ_{1}}. It is not difficult to verify that in fact every c.c.c. forcing is proper and hence that PFA implies MA_{ℵ_{1}}. While proper forcings necessarily preserve uncountability, they may collapse cardinals above ℵ_{1}. To a large extent, this is where PFA derives its additional strength.

In situations where there is a need to apply PFA directly, Todorcevic has developed a general approach for building proper forcings to accomplish a given task such as introducing an uncountable complete subgraph to a given graph or an embedding between two structures. This method was introduced in [66] and further detailed in [70] and [73]. Typically the conditions in the forcing Q consist of pairs q = (X_{q}, 𝒩_{q}) where X_{q} is a finite approximation of the desired object and 𝒩_{q} is a finite ∈-chain of elementary substructures of some (H(θ), ∈) for θ suitably large. In all cases, there are additional requirements placed on the pairs which are specific to the application at hand. One verifies properness by proving that if M is a suitable model for Q and M ∩ H(θ) is in 𝒩_{q}, then q is (M, Q)-generic. In situations in which this construction results in a proper forcing, the forcing Q can usually be regarded as a two step iteration of a forcing which collapses |H(θ)| to ℵ_{1} by covering it with an ∈-chain of countable substructures, followed by a c.c.c. forcing of finite approximations to the desired object.

I will illustrate this method of construction by defining forcings which can be used to show that PFA implies OCA and PID. These examples are relatively simple in terms of the interaction between the finite working part and the chain of models. Still, they contain all of the important features of other examples built using these methods.

5.1. The OCA forcing. Let G be a fixed open graph on a separable metric space X and let ℰ denote the collection of all E ⊆ X such that [E]^{2} ∩ G = ∅. Define Q_{G} to be the collection of all pairs q = (H_{q}, 𝒩_{q}) such that:

1. H_{q} ⊆ X is finite and [H_{q}]^{2} ⊆ G;

2. 𝒩_{q} is a finite ∈-chain of countable elementary submodels of H(2^{ℵ_{0}}^{+}), each containing X and G;

3. if x ≠ y are in H_{q}, then there is an N in 𝒩_{q} such that |N ∩ {x, y}| = 1 (i.e. 𝒩_{q} separates H_{q});

4. if N is in 𝒩_{q} and x is in H_{q} \ N, then x is not in E for any E in ℰ ∩ N.

The order on Q_{G} is defined by q ≤ p if H_{p} ⊆ H_{q} and 𝒩_{p} ⊆ 𝒩_{q}.

The following is the key lemma in establishing the properness of this forcing.

Lemma 5.1. Suppose that N_{i} (i < k) is a finite ∈-chain of suitable models for X and G and that x is an element of X^{k} such that if i < k, then x_{i} is not an element of any E in ℰ ∩ N_{i} and x_{i} is in N_{i+1} if i < k. If D ⊆ X^{k} is an element of N_{0} which has x as an accumulation point, then there is an open U ⊆ X in N_{0} satisfying:

• x(k − 1) ∉ \overline{U} and \{x(k − 1), y\} is in G whenever y is in U;

• {y ↾ k − 1 : (y ∈ D) ∧ (y(k − 1) ∈ U)} accumulates to x ↾ k − 1.

5.2. The PID forcing. We will now turn to a class of forcings which can be used to force instances of PID. Suppose that ℐ is a P-ideal on a set S. Let θ be sufficiently large such that ℐ is in H(θ) and for each countable N ≺ H(θ), let I_{N} be an element of ℐ such that I ⊆^{∗} I_{N} whenever I is in ℐ ∩ N (this is possible since N is countable and ℐ is a P-ideal). Define Q_{ℐ} to be the collection of all pairs q = (Z_{q}, 𝒩_{q}) such that:

1. Z_{q} ⊆ S is finite;

2. 𝒩_{q} is a finite ∈-chain of suitable models for ℐ which separates Z_{q};

3. if N is in 𝒩_{q} and x is in Z_{q} \ N, then x is not in J for any J in ℐ^{⊥} ∩ N.

The order on Q_{ℐ} is slightly more complicated than in the case of Q_{G}. Define q ≤ p if Z_{p} ⊆ Z_{q}, 𝒩_{p} ⊆ 𝒩_{q}, and whenever N is in 𝒩_{p}

N ∩ (Z_{q} \ Z_{p}) ⊆ I_{N}.

This last condition ensures that if G ⊆ Q_{ℐ} is a filter, then every countable subset of ⋃_{q∈G} Z_{q} is in ℐ.

The following is the key combinatorial lemma which is used in the proof that Q_{ℐ} is proper (see [73, 7.8]).

Lemma 5.2. Suppose that 𝒥 is a σ-ideal on a set S, N_{i} (i < k) is a finite ∈- chain of suitable models for 𝒥, and x is in S^{k} such that x_{i} is not in any element of 𝒥 ∩ N_{i} and x_{i} is in N_{i+1} if i < k − 1. If D ⊆ S^{k} is in N_{0} and contains x, then there is a T ⊆ D in N_{0} which contains x and is 𝒥^{+}-splitting:

{x ∈ S : ∃t ∈ T ((u ↾ i)ˆ x ⊆ t)}

is not in 𝒥 whenever u is in T and i < k.

6. Some applications of PFA

I will now mention some applications PFA. The focus will be on applications outside of set theory and on those which are more recent. Two other applications of note are Shelah’s solution to Whitehead’s Problem [54] (which required only MA_{ℵ_{1}}) and Woodin’s resolution of Kaplanski’s Conjecture concerning automatic continuity of homomorphisms of C([0, 1]) into commutative Banach algebras [86]. In addition, an extensive list of applications of MA_{ℵ_{1}} can be found in [23].

6.1. Automorphisms of the Calkin algebra. Let H be a separable

infinite dimensional Hilbert space and let ℬ(H) and 𝒦 (H) be the bounded and compact operators on H, respectively. The Calkin algebra is the quotient 𝒞 (H) = ℬ(H)/𝒦 (H), regarded as a C^{∗}-algebra.

Every unitary operator in 𝒞 (H) gives rise to an automorphism of 𝒞 (H) via conjugation; such automorphisms are said to be inner. In [11], Brown, Douglas, and Filmore asked whether there are any other automorphisms of 𝒞 (H). This turns out to be independent of ZFC:

Theorem 6.1. [50] Assume CH. There is an outer automorphism of 𝒞 (H).

Theorem 6.2. [16] Assume OCA. Every automorphism of 𝒞 (H) is inner.

At the core of Farah’s proof of Theorem 6.2 is the construction and the analysis of coherent families of unitaries which are derived from a given automorphism of 𝒞 (H). Such families are analogs of the coherent families of functions from Example 4.4.

Theorem 6.2 is a new direction in a natural progression of theorems concerning automorphisms and homomorphisms of quotient structures which began with Shelah’s work on the automorphism group of 𝒫(ℕ)/Fin in [56, IV]. The reader is referred to [17], [18] for a detailed account of the work in this area prior to [16]. Also Farah, Weaver, and others have recently begun an investigation into how PFA and other set theoretic methods can be applied to operator algebras; see [20], [85].

6.2. Bases in quotients of Banach spaces. The following problem in

Banach space theory has its roots in Banach’s original monograph [6] (the problem appears explicitly only sometime later; see, e.g., [49]).

Problem 6.3. Does every infinite dimensional Banach space have an infinite dimensional quotient with a basis?

Johnson and Rosenthal proved that the answer to this problem is positive in the class of separable Banach spaces [28]. Whether it is true in general has become known as the Separable Quotient Problem (so called because it is equivalent to asking whether every infinite dimensional Banach space has an infinite dimensional separable quotient). In fact, the proof of [28] yields the following stronger result.

Theorem 6.4. Assume that every subset of ℕ^{ℕ} of cardinality at most θ is <^{∗}- bounded. Every Banach space of density at most θ has an infinite dimensional quotient with a basis.

In this vein it is also natural to ask whether a non separable Banach space has a non separable quotient with a basis. This question was addressed in part by the following result.

Theorem 6.5. [78] Assume MA_{ℵ_{1}} and PID. Every Banach space of density ℵ_{1} has a quotient with a basis of length ω_{1}.

6.3. Von Neumann’s problem on the existence of strictly pos-

itive measures. Given a complete Boolean algebra ℬ, it is natural to ask under what circumstances ℬ admits a strictly positive probability measure. Two necessary requirements are that ℬ be c.c.c. and that it be weakly distributive. Von Neumann asked whether these conditions are also sufficient.

Problem 6.6. [43, Problem 163] Does every complete Boolean algebra which is c.c.c. and weakly distributive necessarily support a strictly positive measure?

A positive answer implies Souslin’s Hypothesis and therefore is not provable in ZFC [36]. Maharam divided von Neumann’s problem into two complementary problems.

Problem 6.7. [36] Does every weakly distributive c.c.c. complete Boolean algebra support a strictly positive continuous submeasure?

Problem 6.8. [36] Does every complete Boolean algebra equipped with a strictly positive continuous submeasure admit a strictly positive measure?

This division was significant in part because it was possible to show that, unlike Souslin’s Hypothesis, the answer to Problem 6.8 could not be changed by forcing and therefore was unlikely to be independent of ZFC. This is analogous to the division of Theorem 1.2 discussed in Section 8 below.

Recently two results completely resolved the situation.

Theorem 6.9. [5] Assume PID. If ℬ is a complete Boolean algebra which is c.c.c. and weakly distributive, then ℬ supports a strictly positive continuous submeasure.

Theorem 6.10. [61] There is a complete Boolean algebra supporting a strictly positive continuous submeasure which does not support a measure.

This application of PFA also demonstrates the merits of its large cardinal strength. While the conclusion of Theorem 6.9 does not apparently have any relationship to large cardinals, it was demonstrated after the fact that the conclusion of Theorem 6.9 does entail the existence of an inner model which satisfies a large cardinal hypothesis.

Theorem 6.11. [19] Assume that if ℬ is a complete Boolean algebra which is c.c.c. and weakly distributive, then ℬ supports a strictly positive continuous submeasure. Then there is an inner model with a measurable cardinal κ such that o(κ) = κ^{++}.

6.4. The determinacy of Gale-Stewart games. An application of

PFA of a rather different nature is derived entirely through its consistency strength. Recall that in a Gale-Stewart game, two players play natural numbers alternately, resulting in an infinite sequence n_{i} (i < ∞) of elements of ℕ. The winner of the game is determined based on whether the resulting sequence is in a predetermined set Γ ⊆ ℕ^{ℕ}. The principle question, in this level of abstraction, is under what circumstances such a game is determined — i.e. when does one of the two players have a strategy to win the game? The Axiom of Choice implies that there are sets Γ ⊆ ℕ^{ℕ} which specify undetermined games. On the other hand, by a classical theorem of Gale and Stewart, closed games are determined.

The interest in such games arises from the fact that the regularity properties of subsets of ℝ^{n} — such as Lebesgue measurability and the Baire Property — can be reformulated in terms of the determinacy of games (see [30, §20-21]). The assertion that the conclusion of OCA holds for open graphs on a given set of reals X can also be regarded as a regularity property of X and has a corresponding game associated to it [21]. In fact the determinacy of games for a point class has come to be regarded as the ultimate form of a regularity property. The first major success in understanding which games could be determined was the following result.

Theorem 6.12. [39] Assume there is a measurable cardinal. Then every analytic game is determined.

With a considerably more complicated proof, it was possible to prove Borel determinacy within ZFC.

Theorem 6.13. [40] Every Borel game is determined.

Unlike Borel games, however, the determinacy of analytic games does require a large cardinal assumption (see [29, §31]).

While there are natural examples of definable subsets of Polish spaces which are not Borel (see [8]), all simply definable sets tend to be projective. Here the projective sets in a Polish space X are the smallest algebra of subsets of X which contain the open sets and which is closed under continuous images. In a major breakthrough, Martin and Steel were able to prove projective determinacy from what turned out to be an optimal large cardinal hypothesis.

Theorem 6.14. [41] If there are infinitely many Woodin cardinals, then all projective games are determined.

While PFA does not imply the existence of large cardinals, it does entail the existence of inner models which satisfy substantial large cardinal hypotheses. This allowed for the proof of the following result.

Theorem 6.15. [60] Assume PFA. The inner model L(ℝ) satisfies that all sets Γ ⊆ ℕ^{ℕ} are determined. In particular, all projective sets are Lebesgue measurable and have the Baire Property.

7. The role of 2^{ℵ_{0}} = ℵ_{2}

One of the important early results on PFA was that it implies 2^{ℵ_{0}} = ℵ_{2} [9] [82]. This is significant in part because it provides a natural limitation to the number of maximal antichains one can expect to meet in a proper forcing.^{1} Since then a number of different proofs have been given that PFA implies 2^{ℵ_{0}} = ℵ_{2} [12] [44] [45]. In each case new ideas where required which were of independent interest. The most significant example of this is the isolation of the principle MRP in [45] which in turn played a key role in the solution of the basis problem for the uncountable linear orders [46] and which has since found other applications [12] [83].

What is clear from experience is that in order to prove structural results at the level of ℵ_{1}, one must deal with combinatorics similar to that involved in proofs that 2^{ℵ_{0}} = ℵ_{2}. What is less clear is to what extent this connection can be made more explicit.

Problem 7.1. Is there a consistent classification of structures of cardinality ℵ_{1} which implies 2^{ℵ_{0}} = ℵ_{2}?

The classification of A-lines presented in Section 3.1 provides an intriguing test question. It is also an open problem whether the combinatorial principles presented in Section 4 already entail that 2^{ℵ_{0}} ≤ ℵ_{2}. (While OCA implies 𝔟 = ℵ_{2}, it is known that PID is consistent with CH, relative to the existence of a supercompact cardinal [76].)

Problem 7.2. Does OCA imply 2^{ℵ_{0}} = ℵ_{2}?

Problem 7.3. Does PID imply 2^{ℵ_{0}} ≤ ℵ_{2}?

Both OCA and PID can be used to classify gaps and therefore do imply that 𝔟 ≤ ℵ_{2}. Recall that a pair of sequences f_{ξ} (ξ < κ), g_{η} (η < λ) form a (κ, λ^{∗})-gap in ℕ^{ℕ}/Fin if:

• whenever ξ < ξ′ < κ and η < η′ < λ, then f_{ξ} <^{∗} f_{ξ′} <^{∗} g_{η′} <^{∗} g_{η} and • there does not exist an h in ℕ^{ℕ} such that if ξ < κ and η < λ, then f_{ξ} <^{∗}

1It was known before the proof that PFA implies 2^{ℵ_{0}} = ℵ_{2} that ℵ_{1} can not be replaced by ℵ_{2} in the formulation of PFA. It had also already been known that the stronger MM implies 2^{ℵ_{0}} = ℵ_{2} [22].

h <^{∗} g_{η}.

Theorem 7.4. [27] There is an (ω_{1}, ω_{1}^{∗})-gap.

Theorem 7.5. [27] The following are equivalent for a regular cardinal κ:

• There is a (κ, ω^{∗})-gap.

• There is an (ω, κ^{∗})-gap.

• There is an unbounded chain in (ℕ^{ℕ}, <^{∗}) of ordertype κ.

Theorem 7.6. [70] [76] Assume either OCA or PID. If κ and λ are regular cardinals and there is a (κ, λ^{∗})-gap, then either κ = ω, λ = ω, or κ = λ = ω_{1}. In particular, 𝔟 ≤ ℵ_{2}.

In [44], it was shown that the conjunction of OCA and the initial formulation of OCA presented in [2] does imply 2^{ℵ_{0}} = ℵ_{2}.

8. The role of PFA in proving theorems in ZFC

One of the remarkable features of the study of forcing axioms and their consequences is that one often obtains ZFC theorems of independent interest as byproducts. One instance of this is the following result which is implicit Shelah’s original proof of the consistency of the conclusion of Theorem 1.2 [56, IV], but which was first made explicit in [81].

Theorem 8.1. If Φ is an automorphism of 𝒫(ℕ)/Fin, then either Φ is induced by a map ϕ : ℕ → ℕ or else Φ does not have a 𝒞 -measurable lifting.

We also have the following analogous result for the Calkin algebra.

Theorem 8.2. [16] If Φ is an automorphism of 𝒞 (H), then either Φ is inner or else Φ does not have a 𝒞 -measurable lifting.

This is part of a more general phenomenon: one can show in ZFC that certain objects or morphisms must fail to have nice regularity properties and PFA can then be used to build regularity properties into such objects or morphisms. For instance, Theorem 1.2 can be viewed as the combination of Theorem 8.1 above and the following theorem.

Theorem 8.3. Assume PFA. If Φ is an automorphism of 𝒫(ℕ)/Fin, then Φ has a 𝒞 -measurable lifting.

The reader is referred to [18] for a detailed discussion of this phenomenon in quotients.

The following Analytic Gap Theorem was directly inspired by the influence of OCA on gaps in ℕ^{ℕ}/Fin and also closely parallels the formulation of PID. It says that the pair 𝒜 = ∅ × Fin, ℬ = Fin × ∅ is essentially the only analytic gap occurring in 𝒫(ℕ)/Fin.

Theorem 8.4. [72] Suppose that 𝒜 ⊆ 𝒫(ℕ) is analytic and closed under taking subsets. If ℬ ⊆ 𝒜^{⊥} then either there is a countable 𝒜_{0} ⊆ ℬ^{⊥} such that every element of 𝒜 is contained in an element of 𝒜_{0}, or else there is tree T ⊆ ℕ^{<ω} such that

1. if t is in T, then {i ∈ ℕ : tˆ i ∈ T } is an infinite element of ℬ and

2. every branch through T is an element of 𝒜.

Remark 8.5. While there are many similarities between 𝒫(ℕ)/Fin and 𝒞 (H), there are important differences as well. For instance recent work of Zamora-Aviles [88] shows that there are analytic gaps in 𝒞 (H) in which both sides are countably directed (in an appropriate analog of ⊆^{∗}).

One application of this theorem is the following result concerning the metrizability of separable Fréchet groups.

Theorem 8.6. [80] Suppose that G is a countable topological group which is Fréchet. If the topology on G is analytic as a subset of 𝒫(G), then G is metrizable.

The Ramsey theoretic approach to applications of set theory which developed simultaneously with the theory of PFA also played a role in the results of [75].

Theorem 8.7. [75] Suppose that K is a compact subset of the Baire class 1 functions on a Polish space X. The following are true:

1. K contains a dense metrizable subspace. In particular if K satisfies the countable chain condition, then it is separable.

2. If K does not contain an uncountable discrete subspace, then K admits an at most 2-to-1 map onto a compact metric space.

3. If K is non metrizable, then either K contains an uncountable discrete subspace or else K contains a homeomorphic copy of [0, 1] × {0, 1} with the interval topology.

4. If K is separable and x is a point in K, then either x has a countable neighborhood base or else there is a discrete subset of K of cardinality 2^{ℵ_{0}} which has x as its unique accumulation point.

The Analytic Gap Theorem is especially important in the proof of 4, where it is used to bring the Ramsey theory of perfect sets of reals into this context. This has been further exploited in the following result which solves a special case of the separable quotient problem.

Theorem 8.8. [4] If X is an infinite dimensional Banach space, then X^{∗} has an infinite dimensional separable quotient.

In some cases, whether these results can be generalized to arbitrary compact spaces in the presence of PFA remains open (see [25] for a survey of related problems, including Problem 9.6 below).

Problem 8.9. [24] Assume PFA. If K is compact and does not contain an uncountable discrete subspace, must K admit an at most 2-to-1 map onto a metric space?

Finally, I will mention the following effective analog of Theorem 6.9 above.

Theorem 8.10. [77] If a complete Boolean algebra satisfies the σ-bounded chain condition and is weakly distributive, then it supports a strictly positive continuous submeasure.

9. Open problems

In closing, I have collected a number of open problems. When possible I have included a reference to either recent progress or a survey of the problem.

Problem 9.1. (Efimov [15]; see [26]) Is it consistent that every infinite compact space contains either a convergent sequence or a copy of βℕ? Does this follow from PFA?

Problem 9.2. (Todorcevic; see [18]) Assume PFA. If ℐ and 𝒥 are analytic ideals on ℕ such that 𝒫(ℕ)/ℐ ≃ 𝒫(ℕ)/𝒥, must the isomorphism be induced by a map ϕ : ℕ → ℕ?

Problem 9.3. (Todorcevic; see [44]) Does either OCA or PID imply 2^{ℵ_{0}} ≤ ℵ_{2}?

Problem 9.4. (Moore [48]) Suppose the following are true: (a) every two ℵ_{1}- dense non-stationary Countryman lines are isomorphic or reverse isomorphic, (b) every Aronszajn line can be embedded into η_{C}, and (c) the Aronszajn lines are well quasi-ordered. Does it follow that 2^{ℵ_{0}} = ℵ_{2}?

Problem 9.5. (see [25] [35]) Assume PFA. If a compact convex set does not contain an uncountable discrete subspace, must it be metrizable?

Problem 9.6. (Gruenhage [24]; see [25]) Assume PFA. Do the uncountable first countable spaces have a three element basis consisting of a set of reals of cardinality ℵ_{1} with the separable metric, the Sorgenfrey, and the discrete topologies?

Problem 9.7. [49] Does every infinite dimensional Banach space have an infinite dimensional quotient with a basis?

Problem 9.8. (Todorcevic [73]) Is there a consistent classification of the cofinal types of directed sets of cardinality at most ℵ_{2} which is comparable to the classification of directed sets of cardinality at most ℵ_{1} given in [68]?

Problem 9.9. (see [13] [38] [37]) Is it consistent that strong homology is additive?

References

[1] U. Abraham, S. Shelah. Isomorphism types of Aronszajn trees. Israel J. Math., 50(1-2):75–113, 1985.

[2] U. Abraham, M. Rubin, S. Shelah. On the consistency of some partition theorems for continuous colorings, and the structure of ℵ_{1}-dense real order types. Ann. Pure Appl. Logic, 29(2):123–206, 1985.

[3] U. Abraham, S. Todorcevic. Partition properties of ω_{1} compatible with CH. Fund. Math., 152(2):165–181, 1997.

[4] S. A. Argyros, P. Dodos, V. Kanellopoulos. Unconditional families in Banach spaces. Math. Ann., 341(1):15–38, 2008.

[5] B. Balcar, T. Jech,, T. Pazák. Complete CCC Boolean algebras, the order sequential topology, and a problem of von Neumann. Bull. London Math. Soc., 37(6):885–898, 2005.

[6] S. Banach. Théorie des Opérations Linéaires. Warszawa, 1932.

[7] J. E. Baumgartner. All ℵ_{1}-dense sets of reals can be isomorphic. Fund. Math., 79(2):101–106, 1973.

[8] H. Becker. Descriptive set-theoretic phenomena in analysis and topology. In Set theory of the continuum (Berkeley, CA, 1989), volume 26 of Math. Sci. Res. Inst. Publ., pages 1–25. Springer, New York, 1992.

[9] M. Bekkali. Topics in Set Theory. Springer-Verlag, Berlin, 1991. Lebesgue measurability, large cardinals, forcing axioms, ρ-functions, Notes on lectures by Stevo Todorčević.

[10] M. Bell, J. Ginsburg, S. Todorcevic. Countable spread of expY and λY. Topology Appl., 14(1):1–12, 1982.

[11] L. G. Brown, R. G. Douglas, P. A. Fillmore. Extensions of C^{∗}-algebras and Khomology. Ann. of Math. (2), 105(2):265–324, 1977.

[12] A. E. Caicedo, B. Veličković. The bounded proper forcing axiom and well orderings of the reals. Mathematical Research Letters, 13(3):393–408, 2006.

[13] A. Dow, P. Simon, J. E. Vaughan. Strong homology and the proper forcing axiom. Proc. Amer. Math. Soc., 106(3):821–828, 1989.

[14] B. Dushnik, E. W. Miller. Concerning similarity transformations of linearly ordered sets. Bull. Amer. Math. Soc., 46:322–326, 1940.

[15] B. Efimov. The imbedding of the Stone-Čech compactifications of discrete spaces into bicompacta. Dokl. Akad. Nauk SSSR, 189:244–246, 1969.

[16] I. Farah. All automorphisms of the Calkin algebra are inner. ArXiv preprint 0705.3085v9 (9/29/2009).

[17] —. Analytic quotients: theory of liftings for quotients over analytic ideals on the integers. Mem. Amer. Math. Soc., 148(702), 2000.

[18] —. Rigidity conjectures. In Logic Colloquium 2000, volume 19 of Lect. Notes Log., pages 252–271. Assoc. Symbol. Logic, Urbana, IL, 2005.

[19] I. Farah, B. Veličković. von Neumann’s problem and large cardinals. Bull. London Math. Soc., 38(6):907–912, 2006.

[20] I. Farah, E. Wofesy. Set theory and operator algebras. Lecture notes from Appalacian Set Theory Workshop, Feb. 2008.

[21] Q. Feng. Homogeneity for open partitions of pairs of reals. Trans. Amer. Math. Soc., 339(2):659–684, 1993.

[22] M. Foreman, M. Magidor, S. Shelah. Martin’s Maximum, saturated ideals, and nonregular ultrafilters. I. Ann. of Math. (2), 127(1):1–47, 1988.

[23] D. H. Fremlin. Consequences Of Martin’s Axiom. Cambridge University Press, 1984.

[24] G. Gruenhage. Perfectly normal compacta, cosmic spaces, and some partition problems. In Open Problems in Topology, pages 85–95. North-Holland, Amsterdam, 1990.

[25] G. Gruenhage, J. Tatch Moore. Perfect compacta and basis problems in topology. In Elliott Pearl, editor, Open Problems in Topology II. Elsevier, 2007.

[26] K. P. Hart. Efimov’s problem. In Elliott Pearl, editor, Open Problems in Topology II. Elsevier, 2007.

[27] F. Hausdorff. Die graduierung nach dem endverlauf. Abhandlun. König. Sc̈hsis. Gessellsch. Wissenschaften, Math.-Phys. Kl., pages 296–334, 1909.

[28] W. B. Johnson, H. P. Rosenthal. On ω^{∗}-basic sequences and their applications to the study of Banach spaces. Studia Math., 43:77–92, 1972.

[29] A. Kanamori. The Higher Infinite. Springer Monographs in Mathematics. Springer-Verlag, Berlin, second edition, 2003. Large cardinals in set theory from their beginnings.

[30] A. S. Kechris. Classical Descriptive Set Theory, volume 156 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995.

[31] B. König, Y. Yoshinobu. Kurepa trees and Namba forcing. preprint, 2005.

[32] K. Kunen. An Introduction to Independence Proofs, volume 102 of Studies in Logic and the Foundations of Mathematics. North-Holland, 1983.

[33] Dj. Kurepa. Sur les fonctins réels dans la famille des ensembles bien ordonnés de nombres rationells. Bull. Int. Acad. Yougoslave, 4:35–42, 1954.

[34] R. Laver. On Fraïssé’s order type conjecture. Ann. of Math. (2), 93:89–111, 1971.

[35] J. Lopez-Abad, S. Todorcevic. Generic Banach spaces and generic simplices. preprint 3/2010.

[36] D. Maharam. An algebraic characterization of measure algebras. Ann. of Math. (2), 48:154–167, 1947.

[37] S. Mardešić. Strong shape and homology. Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2000.

[38] S. Mardešić, A. V. Prasolov. Strong homology is not additive. Trans. Amer. Math. Soc., 307(2):725–744, 1988.

[39] D. A. Martin. Measurable cardinals and analytic games. Fund. Math., 66:287–291, 1969/1970.

[40] —. Borel determinacy. Ann. of Math. (2), 102(2):363–371, 1975.

[41] D. A. Martin, J. R. Steel. A proof of projective determinacy. J. Amer. Math. Soc., 2(1):71–125, 1989.

[42] C. Martinez. It is consistent that the Aronszajn lines are well quasi-ordered. preprint, [43] D. Mauldin, editor. The Scottish Book. Birkhäuser, 1981.

[44] J. Tatch Moore. Open colorings, the continuum and the second uncountable cardinal. Proc. Amer. Math. Soc., 130(9):2753–2759, 2002.

[45] —. Set mapping reflection. J. Math. Log., 5(1):87–97, 2005.

[46] —. A five element basis for the uncountable linear orders. Ann. of Math. (2), 163(2):669–688, 2006.

[47] —. A solution to the L space problem. Jour. Amer. Math. Soc., 19(3):717–736, 2006.

[48] —. A universal Aronszajn line. Math. Res. Lett., 16(1):121–131, 2009.

[49] A. Pełczyński. Some problems on bases in Banach and Fréchet spaces. Israel J. Math., 2:132–138, 1964.

[50] N. C. Phillips, N. Weaver. The Calkin algebra has outer automorphisms. Duke Math. J., 139(1):185–202, 2007.

[51] J. Roitman. A reformulation of S and L. Proc. Amer. Math. Soc., 69(2):344–348, 1978.

[52] W. Rudin. Homogeneity problems in the theory of Čech compactifications. Duke Math. J., 23:409–419, 1956.

[53] E. Schimmerling, M. Zeman. Square in core models. Bull. Symbolic Logic, 7(3):305– 314, 2001.

[54] S. Shelah. Infinite abelian groups, Whitehead problem and some constructions. Israel J. Math., 18:243–256, 1974.

[55] —. Decomposing uncountable squares to countably many chains. J. Combinatorial Theory Ser. A, 21(1):110–114, 1976.

[56] —. Proper forcing, volume 940 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1982.

[57] S. Shelah, J. Steprāns. PFA implies all automorphisms are trivial. Proc. Amer. Math. Soc., 104(4):1220–1225, 1988.

[58] W. Sierpiński. Sur un problème de la thèorie des relations. Ann. Scuola Norm. Sup. Pisa, 2(2), 1933.

[59] R. Solovay, S. Tennenbaum. Iterated Cohen extensions and Souslin’s problem. Ann. of Math., 94:201–245, 1971.

[60] J. R. Steel. PFA implies AD^{L(ℝ)}. J. Symbolic Logic, 70(4):1255–1296, 2005.

[61] M. Talagrand. Maharam’s problem. Ann. of Math. (2), 168(3):981–1009, 2008.

[62] D. Talayco. Applications of cohomology to set theory. I. Hausdorff gaps. Ann. Pure Appl. Logic, 71(1):69–106, 1995.

[63] D. Talayco. Applications of cohomology to set theory. II. Todorčević trees. Ann. Pure Appl. Logic, 77(3):279–299, 1996.

[64] S. Todorcevic. Lipschitz maps on trees. J. Inst. Math. Jussieu, 6(3):527–556, 2007.

[65] —. Forcing positive partition relations. Trans. Amer. Math. Soc., 280(2):703–720, 1983.

[66] —. A note on the proper forcing axiom. In Axiomatic set theory (Boulder, Colo., 1983), volume 31 of Contemp. Math., pages 209–218. Amer. Math. Soc., Providence, RI, 1984.

[67] —. Trees and linearly ordered sets. In Handbook of set-theoretic topology, pages 235–293. North-Holland, Amsterdam, 1984.

[68] —. Directed sets and cofinal types. Trans. Amer. Math. Soc., 209:711–723, 1985.

[69] —. Partitioning pairs of countable ordinals. Acta Math., 159(3–4):261–294, 1987.

[70] —. Partition Problems In Topology. Amer. Math. Soc., 1989.

[71] —. Aronszajn orderings. Publ. Inst. Math. (Beograd) (N.S.), 57(71):29–46, 1995. D̄uro Kurepa memorial volume.

[72] —. Analytic gaps. Fund. Math., 150(1):55–66, 1996.

[73] —. A classification of transitive relations on ω_{1}. Proc. London Math. Soc. (3), 73(3):501–533, 1996.

[74] —. The first derived limit and compactly F_{σ} sets. J. Math. Soc. Japan, 50(4):831– 836, 1998.

[75] —. Compact subsets of the first Baire class. J. Amer. Math. Soc., 12(4):1179–1212, 1999.

[76] —. A dichotomy for P-ideals of countable sets. Fund. Math., 166(3):251–267, 2000.

[77] —. A problem of von Neumann and Maharam about algebras supporting continuous submeasures. Fund. Math., 183(2):169–183, 2004.

[78] —. Biorthogonal systems and quotient spaces via Baire category methods. Math. Ann., 335(3):687–715, 2006.

[79] —. Walks on ordinals and their characteristics, volume 263 of Progress in Mathematics. Birkhäuser, 2007.

[80] S. Todorcevic, C. Uzcátegui. Analytic k-spaces. Topology Appl., 146/147:511–526, 2005.

[81] B. Veličković. Definable automorphisms of 𝒫(ω)/fin. Proc. Amer. Math. Soc., 96(1):130–135, 1986.

[82] —. Forcing axioms and stationary sets. Adv. Math., 94(2):256–284, 1992.

[83] M. Viale. The proper forcing axiom and the singular cardinal hypothesis. Jour. Symb. Logic, 71(2):473–479, 2006.

[84] —. A family of covering properties. Math. Res. Lett., 15(2):221–238, 2008.

[85] N. Weaver. Set theory and C^{∗}-algebras. Bull. Symbolic Logic, 13(1):1–20, 2007.

[86] W. H. Woodin. Discontinuous homorphisms of C(ω) and set theory. PhD thesis, University of California at Berkeley, 1984.

[87] —. The Axiom of Determinacy, Forcing Axioms, and the Nonstationary Ideal. Logic and its Applications. de Gruyter, 1999.

[88] B. Zamora-Aviles. The structure of order ideals and gaps in the Calkin algebra. PhD thesis, York University, 2009.

Department of Mathematics Cornell University Ithaca, NY 14853–4201 USA E-mail: justin@math.cornell.edu