Basis Problems in Combinatorial Set Theory

Stevo Todorcevic

1991 Mathematics Subject Classification: 04–02

An analysis of a given class S of structures in this area frequently splits into two natural parts. One part consists in recognizing the critical members of S while the other is in showing that a given list of critical members is in some sense complete. These kinds of problems tend to be interesting even in cases when elements of S do not have much structure or interest in themselves as they often appear as crucial combinatorial parts of other problems abundant in structure. A typical example of such a situation is the appearance of the Hausdorff gap (a critical substructure of the reduced power ℕ^{ℕ}/FIN; see [15]) at the crucial place in Woodin’s (consistency) proof of Kaplansky’s conjecture about automatic continuity in Banach algebras ([34]). The purpose of this paper is to explain some of these problems and resulting developments. Before we start describing specific Basis Problems some general remarks are in order. Critical objects are almost always some canonical members of S simple to describe and visualize. Sometimes, however, it may take a considerable number of years (or decades) before an old object is identified as critical, or before one finds a (simple!) definition of a new critical object. To show that a given list S_{0} of critical objects is exhaustive one needs to relate a given structure from S to one from the list S_{0}. If the structure in question is explicitly given one usually has no problems in finding the corresponding member of S_{0} and the connecting map. However, if the given structure from S is “generic”, while one may still be able to identify the member of S_{0} to which it is related, one can only hope for a “generic” connecting map. Whenever we use this approach to show that a given list S_{0} is in some sense complete, the corresponding Theorem or Conjecture will be marked by [PFA]. The readers interested in the metamathematical aspects of this approach will find a satisfactory explanation in the recent monograph of Woodin [35] where it is actually shown that there is a certain degree of uniqueness in this approach.

1 Distance Functions

It is not surprising that many critical objects in families of uncountable structures live on the domain ω_{1} of all countable ordinals as “critical” very often means “minimal” in some sense. It is rather interesting that many such critical objects can be defined on the basis of a single transformation α ↦ c_{α} which for every countable ordinal α picks a set c_{α} of smaller ordinals of minimal possible ordertype subject to the requirement that α = sup(c_{α}). This gives us a way to approach higher ordinals from below in various recursive definitions. For example, given two ordinals β > α one can step from β down towards α along the set c_{β}. More 44 S. Todorcevic precisely, one can define the step from β towards α as the minimal point ξ of c_{β} such that ξ ≥ α. Let c_{β}(α), or simply β(α), denote this ordinal. Now one can step further from β(α) towards α and get β(α)(α) (= (β(α))(α)), and so on. This leads us to the notion of a minimal walk from β to α

β > β(α) > β(α)(α) > ⋯ > β(α)(α) ⋯ (α) = α.

Let ⌈β(α)⌉ denote the weight of the step from β towards α, the cardinality of the set of all ξ ∈ c_{β} such that that ξ < α. This gives us a way to define various distances between α and β:

1. ∥αβ∥ = max{⌈β(α)⌉, ∥αβ(α)∥, ∥ξα∥ : ξ ∈ c_{β}, ξ < α},

2. ∥αβ∥_{1} = max{⌈β(α)⌉, ∥αβ(α)∥_{1}},

3. ∥αβ∥_{2} = ∥αβ(α)∥ + 1. Thus, ∥αβ∥_{2} is the number of steps in the minimal walk from β towards α, and ∥αβ∥_{1} is the maximal weight of a single step in that walk. On the other hand, ∥αβ∥ is a much finer distance function which has the following interesting subadditivity properties for every triple γ > β > α of countable ordinals:

4. ∥αγ∥ ≤ max{∥αβ∥, ∥βγ∥},

5. ∥αβ∥ ≤ max{∥αγ∥, ∥βγ∥}. Moreover, we also have the following important coherence properties for every pair β > α of countable ordinals and every integer n (see §4 below where this is used):

6. ∥ξα∥ = ∥ξβ∥ and ∥ξα∥_{1} = ∥ξβ∥_{1} for all but finitely many ξ < α.

7. ∥ξα∥ > n and ∥ξα∥_{1} > n for all but finitely many ξ < α, The minimal walk from β to α can be coded by the sequence ρ_{0}(α, β) of weights of the corresponding steps, or more precisely:

8. ρ_{0}(α, β) = ⌈β(α)⌉ ρ_{0}(α, β(α)). This leads us to another distance function whose values are countable ordinals rather than non-negative integers:

9. Δ_{0}(α, β) = min{ξ : ρ_{0}(ξ, α) ≠ ρ_{0}(ξ, β)}. Let Tr(α, β) denote the places visited during the walk from β to α i.e., the set of all ξ ≤ β for which ρ_{0}(ξ, β) is an initial segment of ρ_{0}(α, β). This leads us now to the first basic square-bracket operation on ω_{1}:

10. [αβ] = min(Tr(ξ, β) \ α) where ξ = Δ_{0}(α, β). Thus [αβ] is the member β_{i} on the path Tr(α, β) = {β = β_{0} > β_{1} > … > β_{n} = α} furthest from β subject to the requirement that there exists α = α_{0} > α_{1} > ⋯ > α_{i} such that ρ_{0}(α_{j}, α) = ρ_{0}(β_{j}, β) and c_{βj} ∩ α = c_{α_{j}} ∩ α_{i} for all j < i.

Documenta Mathematica · Extra Volume ICM 1998 · II · 43–52

Theorem 1 . [24] For every uncountable subset X of ω_{1}, the set of all ordinals of the form [αβ] for some α < β in X contains a closed and unbounded subset of ω_{1}.

This operation has been used in constructions of various mathematical objects of complex behavior such as groups, geometries, and Banach spaces ([20, 21], [7, 8]). The usefulness of [·] in these constructions is based on the fact that [·] reduces questions about uncountable subsets of ω_{1} (the subsets one usually talks about) to questions about closed and unbounded subsets of ω_{1} which are much easier to handle. Recent metamathematical results of Woodin [35] give some explanation to this phenomenon.

2 Binary relations

For a given subset A of ω_{1}, let R_{A} denote the set of all pairs (α, β) of countable ordinals such that [αβ] ∈ A. Then one can show that the family R_{A} (A ⊆ ω_{1}) of binary relations exhibits a too complex behavior if we are to choose isomorphic embeddings as connecting maps. It turns out that in this context the right choice of connecting maps is a reduction introduced long time ago by J.W. Tukey [32] for quite a different purpose. Given two binary relations R and S, we say that R is Tukey reducible to S, and write R ≤_{T} S, if there exist maps f : dom(R) → dom(S) and g : ran(S) → ran(R) such that for every r ∈ R and s ∈ S,

11. (f(r), s) ∈ S implies (r, g(s)) ∈ R.

Tukey considered this reduction only in the case of directed sets as only they are relevant to the theory of Moore–Smith convergence he was studying. The definition is, however, as meaningful in the general case (see [33] and [31] for other variations). While the square bracket operation [·] defined in the previous section can be used to show the extreme complexity also in this generality, the critical objects of the subclass of all transitive binary relations seem to remain critical also in this bigger class. Some examples of critical transitive relations are the usual well-ordering relation on ω_{1}, which we denote by ω_{1}, or the direct sum ω · ω_{1} of countably many copies of ω_{1}. The equality relation = on ω_{1} is of course the maximal binary reflexive relation on ω_{1}. Another critical structure is the family FIN_{ω_{1}} of all finite subsets of ω_{1} ordered by inclusion. That these are indeed some of the critical structures for the whole class of binary relations would follow from the positive answer to the following problem.

Conjecture 1 . [PFA] For every binary relation R on ω_{1}, either R ≤_{T} ω · ω_{1} or FIN_{ω_{1}} ≤_{T} R.

This seems to be a rather strong conjecture but it may not be so unreasonable since we were able to prove it in the case of transitive relations ([27]). An essentially equivalent Ramsey-theoretic reformulation of this conjecture has been around since the early 1970’s in various correspondences between F. Galvin, K. Kunen, R. Laver and others (see [12]): For every family G of unordered pairs of countable ordinals either there exist an uncountable subset of ω_{1} which avoids G, or else there exist uncountable subsets A and B of ω_{1} such that {α, β} ∈ G whenever α ∈ A, β ∈ B and α < β. There are a number of well-known open problems in other areas of mathematics which are awaiting the solution to this conjecture. One of them is the following duality conjecture between the closure and covering properties of subsets of an arbitrary regular topological space X (see [25] or section 5 below).

Conjecture 2 . [PFA] A family of open subsets of X contains a countable subfamily with the same union if and only if an arbitrary subset of X contains a countable subset with the same closure.

3 Transitive relations

Tukey introduced his reduction in order to illuminate the theory of Moore-Smith convergence, so he was concerned only with upwards-directed partially ordered sets. He was already able to isolate the following five directed sets as pairwise inequivalent under the equivalence relation induced by his reducibility:

1, ω, ω_{1}, ω × ω_{1} and FIN_{ω_{1}}.

It turns out that this is indeed the list of all critical directed sets on the domain ω_{1} as the following result shows.

Theorem 2 . [23][PFA] Every directed set on ω_{1} is Tukey equivalent to one of the basic five 1, ω, ω_{1}, ω × ω_{1}, FIN_{ω_{1}}.

A number of years later we were able to extend this result to arbitrary transitive relations on ω_{1}. To simplify the notation, let D_{0} = 1, D_{1} = ω, D_{2} = ω_{1}, D_{3} = ω × ω_{1} and D_{4} = FIN_{ω_{1}}, and let m · D denote the direct sum of m copies of D.

Theorem 3 . [27][PFA] Every transitive relation on ω_{1} is Tukey equivalent to one of the following where n_{i}’s are all non-negative integers:

(a) n_{0} · D_{0} ⊕ n_{1} · D_{1} ⊕ n_{2} · D_{2} ⊕ n_{3} · D_{3} ⊕ n_{4}D_{4},

(b) ω · D_{0} ⊕ n_{2} · D_{2} ⊕ n_{3} · D_{3} ⊕ n_{4} · D_{4},

(c) ω · D_{2} ⊕ n_{4} · D_{4},

(d) ω · D_{4},

(e) =.

The class of transitive relations that one can associate with the reals is considerably richer than the class of all transitive relations on the domain ω_{1} and the analogue of Theorem 3 for this domain is false. For example, Isbell [16] showed that the Banach lattice ℓ^{1} and the lattice ℕ^{ℕ} are not equivalent to either of the five basic directed sets (and moreover, not equivalent to each other). In [10], Fremlin realized that Tukey reductions (or non-reductions) between the classical objects of Real Analysis and Measure Theory are meaningful even from the point of view of these areas of mathematics. Mathematical structures that one finds in these areas are often associated with studies of certain notions of smallness, or more precisely, ideals in Boolean rings such as, for example, the power-set of the reals or the integers. Many of them can in fact be represented as analytic P-ideals on ℕ i.e., ideals of the power-set of ℕ, that are σ-directed modulo FIN, the ideal of finite subsets of ℕ, and given in some explicit way (or more precisely representable as continuous images of the irrationals when viewed as subspaces of the Cantor set 2^{ℕ}). Recently, a number of unexpected connections in this class of ideals have been discovered (see, for example, [22], [28]). One of them is the following result which shows that FIN, ℕ^{ℕ} and ℓ^{1} (all representable as analytic P -ideals on ℕ) are indeed critical members of this class.

Theorem 4 . [29] If J is an analytic P -ideal on ℕ, then either J is generated over FIN by a single subset of ℕ or else ℕ^{ℕ} ≤_{T} J ≤_{T} ℓ^{1}.

4 Linear orderings

A basis for a class X of linear orderings is any of its subclasses Y with the property that every member of X contains an isomorphic copy of a member of Y. Clearly ω_{1} and its converse ω_{1}^{∗} will be members of any basis for uncountable linear orderings so we may restrict our attention to the class R of uncountable linear orderings orthogonal to both ω_{1} and ω_{1}^{∗}. The class R itself naturally splits into the subclass S of separable orderings and its relative orthogonal A = S^{⊥} ∩ R which turns out to be nonempty. The Basis Problem for S was solved by Baumgartner [4] who has actually proved the following more precise result where S^{d} denotes the family of all L ∈ S with the property that every nontrivial interval of L has exactly ℵ_{1} many elements.

Theorem 5 . [4][PFA] Every two orderings from S^{d} are isomorphic.

The Ramsey-theoretic analysis of Baumgartner’s proof turned out to be quite rewarding. Out of a number of closely related coloring principles discovered over the years (see [1], [25]), the following asymmetric principle of open colorings turned out to be quite useful even in problems far beyond the original scope (see e.g. [25], [9]):

[OCA] For every separable metric space X and every open symmetric and irreflexive relation R on X, either X can be decomposed into countably many sets that avoid R, or else X contains an uncountable subset Y such that every two distinct members of Y are related in R. To see the relevance of OCA to the Basis Problem of S consider two uncountable separable (dense) linear orderings A and B. Let X = A × B and let R = {((a_{0}, b_{0}), (a_{1}, b_{1})) : a_{0} ≠ a_{1}, b_{0} ≠ b_{1}, (a_{0} <_{A} a_{1} ≡ b_{0} <_{B} b_{1})}. This is indeed an open relation with respect to the natural order topology on X. It is a general fact that the cartesian product of two orderings from S(∪{ω_{1}, ω_{1}^{∗}}) cannot be decomposed into countably many chains so the first alternative of OCA fails in this situation. The second alternative of OCA gives us an embedding of an uncountable subset of A into B. This shows that no two members of S are orthogonal to each other which is a half way towards the solution of the Basis Problem for separable linear orderings. The progress on the Basis Problem for the orthogonal A = (S ∪ {ω_{1}, ω_{1}^{∗}})^{⊥} has been much slower. It was initiated by the following brilliant question of R.S. Countryman [6]: Is there an uncountable linear ordering whose cartesian square is the union of countably many chains? We have already remarked that the class C of Countryman’s orderings (if nonempty) must be included in A. Note also that every C ∈ C is orthogonal to its reverse C^{∗} (which also belongs to C). Thus, unlike to the case of separable orderings, if the class C is nonempty, we cannot hope for a single-element basis in this case. In [19], Shelah established that C is indeed a nonempty class of orderings and posed the following interesting conjecture.

Conjecture 3 . [PFA] The class C is a basis for A.

This together with Baumgartner’s result about the class of separable orderings leads us to the following equivalent conjecture.

Conjecture 4 . [PFA] The class of all uncountable linear orderings has a 5element basis ω_{1}, ω_{1}^{∗}, B, C, C^{∗} where B is some uncountable set of reals and where C is any uncountable linear ordering whose cartesian square is the union of countably many chains.

While Shelah’s conjecture is still widely open one can still try to find the Ramseytheoretic principle that lies behind. This search turned out to be quite simple and (unlike the case of OCA above) the resulting coloring principle turned out to be equivalent to the statement that A has a 2-element basis. The analysis is based on a fundamental concept introduced more than 60 years ago by -D. Kurepa [17], a concept whose relevance in constructing critical uncountable structures has been realized only in recent times. This is the concept of a (special) Aronszajn tree (Atree, in short). An A-tree is simply a transformation a which to every countable ordinal ξ associates its enumeration a_{ξ} : ξ → ω (one-to-one or finite-to-one map) with the property that for a given countable ordinal α the set of restrictions {a_{ξ} ↾ α : ξ < ω_{1}} is at most countable. The set A_{a} = {a_{ξ} : ξ < ω_{1}}, ordered lexicographically, is a typical member of the class A. Clearly we can view the transformation a also as a two-place distance function a(α, β) = a_{β}(α) which makes this concept relevant in descriptions of other critical structures as well. For example, it can be seen that the distance functions ∥ · ∥, ∥ · ∥_{1} and ρ_{0} considered in the first section are all Aronszajn. However, our analysis from that section also suggests considering the notion of a coherent A-tree i.e., an A-tree a_{ξ} : ξ → ω_{1} of finite-to-one mappings which has the following property for all α < β:

12. a_{α}(ξ) = a_{β}(ξ) for all but finitely many ξ < α.

The importance of this notion can be seen from the following

Theorem 6 . [24] The cartesian square of any lexicographically ordered coherent A-tree is the union of countably many chains.

In other words, a coherent A-tree immediately gives us a critical member of the class of uncountable linear orderings. It is therefore not surprising that this notion will also give us a Ramsey-theoretic reformulation of Shelah’s Conjecture. Recall the notion of distance function Δ(α, β) = min{ξ : a_{α}(ξ) ≠ a_{β}(ξ)} that one associates to an A-tree a_{ξ} : ξ → ω of enumerations. Thus, Δ(β, γ) > Δ(α, β) reads as “β is closer to γ than to α”. So it is natural to call a binary relation R on ω_{1} an a-open relation if

13. R(α, β) and Δ(β, γ) > Δ(α, β) imply R(α, γ),

whenever α, β and γ are pairwise distinct countable ordinals. However, this is not quite analogous to the situation in the Cantor set 2^{ℕ} since it easily follows that in the present case the complement of an a-open relation on ω_{1} is also a-open.

Theorem 7 . [2][PFA] The class A of linear orderings has a 2-element basis if and only if for every a-open symmetric relation R on ω_{1} there is an uncountable subset X of ω_{1} such that X^{2}\diagonal is included either in R or in its complement.

It should be remarked that if in this Ramsey-theoretic principle we use another A-tree as a parameter which describes the notion of openness we get an equivalent formulation.

5 Topological spaces

While this is an area of considerable generality and wealth of examples there seem to be some patterns in descriptions of these examples. Pathological spaces almost always contain uncountable discrete subspace (a copy of D(ω_{1}), the discrete space on ω_{1}) and this is usually at the root of their complexity. On the other hand, spaces that do not contain D(ω_{1}) are usually obtained as mild modifications of separable metric topologies. A typical such example is the split-interval of Alexandroff and Urysohn [3] or its subspaces. It is obtained by doubling each point of the unit interval I = [0, 1], or more precisely the space I × 2 with the lexicographic order topology. Note that the split-interval is a 2−to−1-preimage of the unit interval so the two spaces share many properties in common. On the other hand, they are orthogonal to each other since clearly the split-interval contains no uncountable metrizable subspace.

Conjecture 5 . [PFA] The class of uncountable regular spaces has a 3-element basis consisting of D(ω_{1}), B and B × {0}, where B is some uncountable subset of the unit interval and where B×{0} is considered as a subspace of the split-interval.

This is a rather bold conjecture based on a question first considered by Gruenhage [14]. Note that Conjecture 2, about the equivalence of certain closure and covering properties in regular spaces considered above, is an immediate consequence of Conjecture 5. In fact, Conjecture 5 has several other weakenings which if true would still be of considerable interest. For example, if we restrict ourselves to compact spaces we get the following consequence of Conjecture 5 which is related to a problem first asked by D.H. Fremlin (see [11] or [14]).

Conjecture 6 . [PFA] Every compact space which does not contain D(ω_{1}) admits an at most 2−to−1 continuous map onto a compact metric space.

It is easily seen that this conjecture is in fact equivalent to Conjecture 5 restricted to regular spaces that can be compactified avoiding copies of D(ω_{1}). Note also that this conjecture solves the Basis Problem for compact spaces: A compact space K is either metrizable, or it contains a copy of D(ω_{1}), or an uncountable subspace of the split interval of the form B ×2. Note that from such a subspace B ×2 of K one can easily build an uncountable biorthogonal system in the Banach space C(K) of continuous real-valued functions on K i.e., a system (x_{b}, x_{b}^{∗}) (b ∈ B) of elements of C(K) × C(K)^{∗} with uniformly bounded norms such that

14. x_{b}^{∗}(x_{b}) = 1 and x_{b}^{∗}(x_{a}) = 0 whenever a ≠ b.

Another interesting consequence of Conjecture 6 is the fact that if the product of two compact spaces does not contain a copy of D(ω_{1}) then one of the factors must be metrizable.

It is interesting that the Ramsey-theoretic principles needed to solve these two conjectures are some forms of OCA discussed above in connection with the Basis Problem for separable linear orderings. This is not surprising since a separable linear ordering shows up in Conjecture 5 as a member of a basis for uncountable regular spaces. However, to solve these two conjectures one needs a much stronger form of OCA valid for a class of spaces larger than the class of separable metric spaces occurring in the original form (see [14], [25]). Lacking the methods to attack these Ramsey-theoretic problems, it is natural to try to test these two conjectures by either proving some of the consequences or by restricting ourselves to some concrete class of spaces. We have two results of this sort that show a surprising degree of accuracy in these conjectures.

Theorem 8 . [26][PFA] A compact space K is metrizable if and only if the Banach space C(K) contains no uncountable biorthogonal system.

Pointwise compact sets of Baire class-1 functions showed up perhaps for the first time in the two selection theorems of E. Helly about families of monotonic functions on the unit intervals. In more recent years the interest was renewed after Odell and Rosenthal [18] proved that a separable Banach space E contains no copy of ℓ^{1} if and only if the unit ball of E^{∗∗} with the weak* topology is such a compactum when considered as a family of functions defined on the unit ball of E^{∗}. A number of deep general results about this class of spaces were established soon afterwards by Bourgain, Fremlin, Talagrand [5] and Godefroy [13]. Since the split-interval can be represented as a compactum lying inside the first Baire class, it is natural to try to test the validity of Conjecture 6 on this class of compact spaces. The following result shows that for this class of compact spaces Conjecture 6 is indeed true even in some stronger form.

Theorem 9 . [30] Every pointwise compact subset of the first Baire class which does not contain a copy of D(ω_{1}) admits an at most 2−to−1 continuous map onto a metric compactum, and moreover, it is either metric itself or it contains a full copy of the split-interval.

Basis Problems in Combinatorial Set Theory 51

References

[1] U. Abraham, M. Rubin, and S. Shelah, On the consistency of some partition theorems for continuous colorings, Ann. Pure. Appl. Logic 29 (1985), 123–206.

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

[3] P. Alexandroff and P. Urysohn, Mémoire sur les espaces topologiques compacts, Verh. Akad. Wetensch., Amsterdam 14 (1929).

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

[5] J. Bourgain, D.H. Fremlin and M. Talagrand, Pointwise compact sets of Bairemeasurable functions, Amer. J. Math. 100 (1978), 845–886.

[6] R.S. Countryman, Spaces having a σ-monotone base, preprint 1970.

[7] P. Erdös, S. Jackson and R.D. Mauldin, On partitions of lines and spaces, Fund. Math. 145 (1994), 101–119.

[8] , On infinite partitions of lines and spaces, Fund. Math. 152 (1997), 75–95.

[9] I. Farah, Analytic quotients, submitted to Memoirs Amer. Math. Soc.

[10] D.H. Fremlin, The partially ordered sets of measure theory and Tukey’s ordering, Note di Matematica 11 (1991), 177–219.

[11] D.H. Fremlin, Problems, March 1, 1998.

[12] F. Galvin, letter of November 12, 1980.

[13] G. Godefroy, Compacts de Rosenthal, Pacific. J. Math. 91 (1980), 293–306.

[14] G. Gruenhage, Perfectly normal compacta and some partition problems, in: Open Problems in Topology (J. van Mill et al ed) Elsevier Sci. Publ. 1990.

[15] F. Hausdorff, Summen von ℵ_{1} Mengen, Fund. Math. 26 (1936), 241–255.

[16] J. R. Isbell, Seven cofinal types, J. London Math. Soc. 4 (1972), 651–654.

[17] -D. Kurepa, Ensembles linéaires et une classe de tableaux ramifiés (tableaux ramifiés de M. Aronszajn), Publ. Math. Univ. Belgrade 6 (1936), 241–255.

[18] E. Odell and H.P. Rosenthal, A double-dual characterization of separable Banach spaces containing ℓ^{1}, Israel J. Math. 20 (1975), 375–384.

[19] S. Shelah, Decomposing uncountable square into countably many chains, J.

Comb. Theory (A) 21 (1976), 110–114.

Documenta Mathematica · Extra Volume ICM 1998 · II · 43–52

[20] S. Shelah and J. Steprans, Extraspecial p-groups, Ann. Pure Appl. Logic, 34 (1987), 87–97.

[21] S. Shelah and J. Steprans, A Banach space on which there are few operators, Proc. Amer. Math. Soc., 104 (1988), 101–105.

[22] S. Solecki, Analytic ideals, Bull. Symb. Logic 2 (1996), 339–348.

[23] S. Todorcevic, Directed sets and cofinal types, Trans. Amer. Math. Soc. 290 (1985), 711–723.

[24] , Partitioning pairs of countable ordinals, Acta Mathematica, 159 (1987), 261–294.

[25] , Partition problems in topology, Amer. Math. Soc., Providence, 1989.

[26] , Irrendundant sets in Boolean algebras, Trans. Amer. Math. Soc., 339 (1993), 35–44.

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

[28] , Analytic gaps, Fund. Math. 150 (1996), 55–66.

[29] , Definable ideals and gaps in their quotients, in: Set Theory: Techniques and Applications (C.A. DiPrisco et al, eds), Kluwer Acad. Press 1997, pp. 213–226.

[30] , Compact sets of the first Baire class, preprint 1997.

[31] S. Todorcevic and J. Zapletal, On the Alaoglu–Birkhoff equivalence of posets, preprint 1997.

[32] J.W. Tukey, Convergence and uniformity in topology, Princeton Univ. Press 1940.

[33] P. Vojtáš, Galois–Tukey connections between explicit relations on classical objects of real analysis, Israel Math. Conf. Proc. vol. 6 (1993), 619–643.

[34] W.H. Woodin, Discontinuous homomorphisms of C(Ω) and Set Theory, Ph.D. Thesis, University of California, Berkeley, 1984.

[35] W.H. Woodin, The axiom of determinacy, forcing axioms and the nonstationary ideal, in preparation.

C.N.R.S.,

Université Paris VII, France.

Matematicki Institut, Beograd, Yugoslavia.

University of Toronto, Toronto, Canada.