WEAK DIAMOND AND OPEN COLORINGS

JUSTIN TATCH MOORE

Abstract. The purpose of this article is to prove the relative consistency of certain statements about open colorings with 2^{ℵ_{0}} < 2^{ℵ_{1}}. In particular both OCA and the statement that every 1-1 function of size ℵ_{1} is σ-monotonic are consistent with 2^{ℵ_{0}} < 2^{ℵ_{1}}. As a corollary we have that 2^{ℵ_{0}} < 2^{ℵ_{1}} does not admit a ℙ_{max} variation (in the presence of an inaccessible cardinal).

The open coloring axiom, OCA, is a Ramsey theoretic statement relating to the real numbers. Since its introduction in [17] it has found a wealth of applications to problems closely related to the real line (see [5], [7], [13], [17], [19], and [20]). Frequently, applications of OCA require an application of MA_{ℵ_{1}} to complete the argument (see, e.g., [7], [20]). Farah gave some explanation of this phenomenon through the following theorem.

Theorem 0.1. [6] OCA is relatively consistent with (1) 𝔱 = ℵ_{1}.

(2) There are no Q-sets.

(3) There are two ℵ_{1} dense sets of reals which are not order isomorphic.

Since items 1-3 are all consequences of weak diamond (an equivalent of 2^{ℵ_{0}} < 2^{ℵ_{1}} — see [4]) this suggests the question of whether OCA is relatively consistent with weak diamond. In this paper I will show that this is indeed the case. I will also show the relative consistency of weak diamond with “Every partial 1-1 function f ⊆ ℝ^{2} of size ℵ_{1} is the union of countably many monotonic functions.” An application of the later result is that there is no ℙ_{max} variation for weak diamond (see [21] for a discussion of ℙ_{max} models and their variants). In particular there are two consequences of the bounded form of PFA which jointly imply 2^{ℵ_{0}} = 2^{ℵ_{1}} but which are each relatively consistent with 2^{ℵ_{0}} < 2^{ℵ_{1}} (one of them modulo an inaccessible cardinal).

I would like to thank Ilijas Farah and Paul Larson for reading drafts of this paper and offering a number of useful suggestions.

The research for this paper was supported by EPSRC grant GR/M71121 during my stay at the University of East Anglia.

1. Weak diamond and the open coloring axiom

In this section I will prove that the open coloring axiom of [17] is relatively consistent with 2^{ℵ_{0}} < 2^{ℵ_{1}}. Recall that the open coloring axiom is the following assertion:

OCA: If X is a separable metric space and G ⊆ [X]^{2} is open then either

(1) there is a decomposition of X into countably many pieces X_{i} such that [X_{i}]^{2} ∩ G is empty for all i or

(2) there is an uncountable H ⊆ X such that [H]^{2} ⊆ G. Here [X]^{2} is the set of unordered pairs of distinct elements of X and open subsets of [X]^{2} are those induced by symmetric open subsets of X^{2}.

Definition 1.1. If G ⊆ [X]^{2} is an open graph then let H(X, G) be the partial order of all finite complete subgraphs of (X, G) ordered by reverse inclusion. Let H^{ω}(X, G) be the finite support product of ω many copies of H(X, G).

We will need the following lemma which is a corollary of the proof of Theorem 4.4 in [17].

Lemma 1.2. Let G ⊆ [ω^{ω}]^{2} be an open graph. There is a countably closed forcing P_{G} which introduces a set Ẋ ⊆ ω^{ω} such that

(1) if Y ⊆ ω^{ω} is in the ground model and induces an uncountably chromatic subgraph of G then Y̌ ∩ Ẋ is forced to be uncountable and

(2) H^{ω}(Ẋ, G) is forced to satisfy the countable chain condition.

Proof. If U ⊆ (ω^{ω})^{n} is open and p ∈ (ω^{ω})^{n} set

U_{p} = {q ∈ U : ∀i < n{q(i), p(i)} ∈ G}.

If f : (ω^{ω})^{n} → ω^{ω} is a partial function with domain A then let

ω_{f}^{∗}(p) = ⋂\{\overline{f′′(U_{p} ∩ A)} : p ∈ U and U is open\}

Let P_{G} be all triples of countable sequences ⟨T_{ξ} : ξ < α⟩, ⟨g_{ξ} : ξ < α⟩, and ⟨x_{ξ} : ξ < α⟩ of closed subgraphs of G, countable partial functions from (ω^{ω})^{n} to ω^{ω}, and elements of ω^{ω} respectively which satisfy

(1) [T_{ξ}]^{2} ∩ G is empty,

(2) if ξ < η < α then x_{η} is not in T_{ξ}, and

(3) if ξ < η < α, the domain of g_{ξ} is contained in (ω^{ω})^{n}, p is an n-tuple of distinct elements of {x_{γ} : γ < η}, and ω_{g_{ξ}}^{∗}(p) is an empty subgraph of G then x_{η} is not in ω_{g_{ξ}}^{∗}(p).

Set Ẋ to be the elements of the generic sequence ⟨x_{ξ} : ξ < ω_{1}⟩. The first conclusion of our theorem follows from genericity. Also note that the generic sequences ⟨T_{ξ} : ξ < ω_{1}⟩ and ⟨g_{ξ} : ξ < ω_{1}⟩ enumerate the closed subgraphs of G satisfying (1) above and the countable partial functions in V^{P_{G}}. The proof of Theorem 4.4 now yields that H^{ω}(Ẋ, G) satisfies the c.c.c.. ^{1} □

Theorem 1.3. OCA is relatively consistent with weak diamond.

Proof. Start with a ground model V satisfying CH together with ℵ_{2} < 2^{ℵ_{1}}. Construct a countable support iteration of length ω_{2} of partial orders of size ℵ_{1} as follows. At stage α < ω_{2} we have a book-keeping device which gives us a Q_{α} name Ġ_{α} for an open graph. Define

Q_{α+1} = Q_{α} ∗ PĠ_{α} ∗ H^{ω}(Ẋ_{α}, Ġ_{α}).

The book-keeping is done in such a way that every Q_{ω_{2}} name for an open graph Ġ appears as Ġ_{α} for stationarity many α < ω_{2} (see [15]).

Since properness is preserved by countable support iterations, Q_{ω_{2}} is proper. Moreover, since Q_{α} has size ℵ_{1} for all α, Q_{ω_{2}} satisfies the ℵ_{2}-c.c.. It follows immediately that V^{Q_{ω_{2}}} satisfies 2^{ℵ_{0}} = ℵ_{2} < 2^{ℵ_{1}}.

To see that Q_{ω_{2}} forces OCA, let (Ẏ , Ġ) be a Q_{ω_{2}} name for an open graph which is not countably chromatic. Since Q_{ω_{2}} has the ℵ_{2}-c.c. there is a closed unbounded set C ⊆ ω_{2} such that for every δ in C, Ġ is a Q_{δ} name and (Ẏ ↾ Q_{δ}, Ġ) is a Q_{δ} name for an open graph which is not countably chromatic. Thus for some δ in C, Ġ = Ġ_{δ}. Now Ẋ_{δ} is forced to have an uncountable intersection with Ẏ and since H^{ω}(Ẋ_{δ}, Ġ_{δ}) decomposes (Ẋ_{δ}, Ġ) into countably many complete subgraphs, it also must introduce an uncountable Ḣ ⊆ Ẏ such that [Ḣ]^{2} ⊆ Ġ. □

2. Weak diamond and σ-monotonic functions

The purpose of this section is to demonstrate that it is relatively consistent with weak diamond that all 1-1 functions f ⊆ ℝ^{2} of size ℵ_{1} can be decomposed into countably many monotonic functions.

Lemma 2.1. Suppose that there is a cofinal subset of (ω_{1}^{ω_{1}}, <) of size ℵ_{2} and that the continuum is ℵ_{2}. There is a sequence g⃗ = ⟨g_{ξ} : ξ < ω_{2}⟩ of functions from ℝ to ℝ such that if f is a partial function from ℝ to ℝ of size ℵ_{1} then f can be covered by countably many functions from the sequence g⃗.

1Theorem 4.4 is cast in the language of closed set mappings. To see the translation to open colorings, see Theorems 8.0 and 8.1 of [17].

Proof. It will be easiest to index g⃗ by the set ω_{2} ×ω_{2} ×ω. Let ℝ = {x_{ξ} : ξ < ω_{2}} be a fixed enumeration and for δ < ω_{2} set X_{δ} = {x_{ξ} : ξ < δ}. Fix δ < ω_{2}. I will first show that there is a sequence Γ_{δ,ξ} (ξ < ω_{2}) of subsets of X_{δ}^{2} such that

(1) for all ξ < ω_{2} and all x in X_{δ} there are only countably many y such that (x, y) is in Γ_{δ,ξ} and

(2) if f : X_{δ} → X_{δ} then there is a ξ < ω_{2} such that f ⊆ Γ_{δ,ξ}. Fix a cofinal sequence h_{γ} (γ < ω_{2}) in (ω_{1}^{ω_{1}}, <) and set

Γ_{γ} = {(x_{ξ}, x_{η}) : η < h_{γ}(ξ)}.

If f ⊆ X^{2} is a function, let h(ξ) be the index of f(x_{ξ}) (h(ξ) = 0 if f(x_{ξ}) is not defined). Clearly if h_{γ} dominates h, then f ⊆ Γ_{γ}.

Notice that condition (1) implies that each of the sets Γ_{δ,ξ} can be covered by countably many functions g_{δ,ξ,n} (n < ω) from ℝ to ℝ. By property (2),

g⃗ = ⟨g_{δ,ξ,n} : (δ, ξ, n) ∈ ω_{2} × ω_{2} × ω⟩

has the desired covering property. □

Theorem 2.2. It is relatively consistent with weak diamond that every partial 1-1 function f from ℝ to ℝ of size ℵ_{1} can be decomposed into countably many monotonic functions.

Remark 2.3. A similar result is proven in Section 7 of [1] and similar techniques are employed there (this was brought to my attention during the final revision of this paper). We will need Theorem 2.2, however, for the application in the next section.

Proof. First notice that the sequence g⃗ of Lemma 2.1 can be chosen in such a way that if f is 1-1 then it can be covered by countably many 1-1 elements of g⃗. To see this take the original sequence together with all functions of the form

{(x, y) : (x, y) ∈ g_{ξ} and (y, x) ∈ g_{η}}.

It is easily verified that countable unions of these functions cover all partial 1-1 functions of size ℵ_{1}.

Start with a ground model which satisfies CH, ℵ_{2} < 2^{ℵ_{1}}, and “There is a cofinal subset of (ω_{1}^{ω_{1}}, <) of size ℵ_{2}.” We will now build a c.c.c. partial order Q of size ℵ_{2} such that in V^{Q} all 1-1 functions f ⊆ ℝ^{2} of size ℵ_{1} can be decomposed into countably many monotonic functions. In V^{Q} the continuum will be ℵ_{2} and there will be a cofinal subset of (ω_{1}^{ω_{1}}, <) of size ℵ_{2} and hence Lemma 2.1 will apply. Using the same book-keeping technique as in [15], build Q as an iteration of partial orders of size ℵ_{1} in such a way that the functions in the sequence g⃗ given by Lemma 2.1 can all be decomposed into countably many monotonic functions in V^{Q}. The following lemma takes care of individual stages of the iteration.

Lemma 2.4. [2] (CH) If f is a 1-1 function from ℝ to ℝ then there is a c.c.c. forcing P of size ℵ_{1} such that forcing with P introduces a decomposition of f into countably many monotonic functions.

□

3. An application to ℙ_{max} theory.

In this section I will show that there is no ℙ_{max} variation conditioned to the sentence “2^{ℵ_{0}} < 2^{ℵ_{1}}.” This will be done by showing that there are two Π_{2} sentences for the structure (H(ω_{2}), ∈) each of which can individually be forced hold together with 2^{ℵ_{0}} < 2^{ℵ_{1}} over any ground model^{2} but which jointly imply 2^{ℵ_{0}} = 2^{ℵ_{1}}.

The first sentence is the following assertion due to Baumgartner [3]:

ψ_{A}: For every tree T of size ℵ_{1} with countable levels there is a map f : T → ℕ such that for all s, t, u with f(s) = f(t) = f(u), s < t, u implies t and u are comparable.

This statement can readily be seen to be equivalent to the assertion that all Aronszajn trees are special and that there are no Kurepa trees (see [3]). It is known that this statement can be forced together with CH (and hence 2^{ℵ_{0}} < 2^{ℵ_{1}}) over any model in which there is an inaccessible cardinal (see chapter V section 8 in [14]).

The second sentence is

ψ_{B}: If f ⊆ ℝ^{2} is a 1-1 function of size ℵ_{1} then f can be covered

by countably many monotonic functions. The fact that ψ_{A} ∧ ψ_{B} implies 2^{ℵ_{0}} = 2^{ℵ_{1}} is a consequence of the next theorem.

Theorem 3.1. (ψ_{B}) There is a sequence T_{ξ} (ξ < 2^{ℵ_{0}}) of subtrees of 2^{<ω_{1}}, each with countable levels, such that every element of 2^{ω_{1}} is a branch through some T_{ξ}.

Proof. Fix a sequence x_{α} (α < ω_{1}) of distinct elements of ℝ and a sequence of bijections H_{α} : 2^{α} ↔ ℝ for each α < ω_{1}. Also fix an enumeration f⃗_{ξ} (ξ < 2^{ℵ_{0}}) of all objects f⃗ such that

(1) f⃗ is a countable sequence of monotonic functions,

(2) the domain of each element of f⃗ is a Borel subset of ℝ, and (3) the domains of the elements of f⃗ cover X = {x_{α} : α < ω_{1}}.

2In one case an inaccessible cardinal is needed in the ground model.

For each ξ < 2^{ℵ_{0}}, let T_{ξ} be the collection of all t in 2^{<ω_{1}} such that if α ≤ |t|, there is a member of the sequence f⃗_{ξ} which sends x_{α} to H_{α}(t ↾ α). Clearly T_{ξ} is a downwards closed subtree of 2^{<ω_{1}} and, since f⃗_{ξ} is countable, T_{ξ} has countable levels. It suffices to show that every element of 2^{ω_{1}} is a branch though some T_{ξ}. To this end, fix z in 2^{ω_{1}} and define f : X → 2^{ω} by setting f(x_{α}) = H_{α}(z ↾ α). Now, by ψ_{B}, it is possible to find a ξ < 2^{ℵ_{0}} such that the members of the sequence f⃗_{ξ} cover f. It is now easy to see that z is a branch through T_{ξ}. □

Remark 3.2. It is perhaps worth mentioning the following result due to Baumgartner (see Theorem 3.5.11 of [9]): Assuming PFA, after forcing with any measure algebra ψ_{A} holds. The analysis of random graphs under MA_{ℵ_{1}} has been one of the main techniques used to produce models of 2^{ℵ_{0}} < 2^{ℵ_{1}} in which certain consequences of MA_{ℵ_{1}} hold. Thus the method of analyzing random graphs (see, e.g., [12], [18]) and techniques presented in Section 2 take a fundamentally different approaches to maximizing consequences of forcing axioms in the context of 2^{ℵ_{0}} < 2^{ℵ_{1}}.

4. Closing remarks and questions

The real motivation behind the results of this paper is the program of studying which Π_{2} sentences for (H(ω_{2}), ∈) are compatible with weak diamond. Set-theoretic topologists are often interested in questions of this sort, particularly in the context of studying the structure of normal and hereditarily normal spaces (see [8], [16]). For example

Question 4.1. Is weak diamond compatible with the statement that every c.c.c. partial order satisfies Knaster’s condition?

Here Knaster’s condition is the statement that ever uncountable family contains an uncountable linked subcollection. The papers [6], [10], and [11] provide some answers to problems of this nature but with weak diamond replaced by some of its useful consequences.

Todorčević has shown (unpublished) that if 𝔭 > ω_{1} then the open coloring axiom of [1] (which I will denote OCA_{[ARS]} — see [1] for a definition) is equivalent to the statement that every 1-1 function f ⊆ ℝ^{2} is the union of countably many monotonic functions. The following question, however, remains open.

Question 4.2. Is OCA_{[ARS]} relatively consistent with 2^{ℵ_{0}} < 2^{ℵ_{1}}?

Finally, the fact that ψ_{A} is not only consistent with weak diamond but with CH as well suggests the following question (for undefined terms, see chapter 10 of [21]; compare to question 2 on page 906 of [21]).

Question 4.3. (LC)^{3} Are there two Π_{2} sentences for the structure (H(ω_{2}), ∈) which can individually be forced to hold together with CH over any ground model but which jointly imply 2^{ℵ_{0}} = 2^{ℵ_{1}}?

References

[1] U. Abraham, M. Rubin, and 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.

[2] U. Avraham and S. Shelah. Martin’s Axiom does not imply that every two ℵ_{1}-dense sets of reals are isomorphic. Israel J. Math., 38(1–2):161–176, 1981.

[3] J. Baumgartner. Applications of the proper forcing axiom. In K. Kunen and J. Vaughan, editors, Handbook of Set-Theoretic Topology. North-Holland, 1984.

[4] K. Devlin and S. Shelah. A weak version of ♢ which follows from 2^{ℵ_{0}} < 2^{ℵ_{1}}. Israel Journal of Math, 29(2–3):239–247, 1978.

[5] A. Dow and K. P. Hart. The measure algebra does not always embed. Fund. Math., 163(2):163–176, 2000.

[6] I. Farah. OCA and towers in P(ℕ)/fin. Comment. Math. Univ. Carolin., 37(4):861–866, 1996.

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

[8] G. Gruenhage and P. Nyikos. Normality in X^{2} for compact X. Trans. Amer. Math. Soc., 340(2):563–586, 1993.

[9] J. Hirschorn. Cohen and random reals. PhD thesis, University of Toronto, 2000.

[10] P. Larson and S. Todorčević. Chain conditions in maximal models. Fund. Math., 168(1):77–104, 2001.

[11] P. Larson and S. Todorčević. Katětov’s problem. Trans. Amer. Math. Soc., 354:1783–1792, 2002.

[12] J. T. Moore. Ramsey theory on sets of real numbers. PhD thesis, University of Toronto, 2000.

[13] J. T. Moore. Open colorings, the continuum and the second uncountable cardinal. Proc. Amer. Math. Soc., to appear.

[14] S. Shelah. Proper and improper forcing. Springer-Verlag, Berlin, second edition, 1998.

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

[16] F. Tall. Tall’s problems. In J. van Mill and G. M. Reed, editors, Open problems in topology, pages 21–35. North-Holland, 1990.

[17] S. Todorčević. Partition Problems In Topology. Amer. Math. Soc., 1989.

[18] S. Todorčević. Random set mappings and separability of compacta. Topology and its Applications, 74:265–274, 1996.

3Here LC means under suitable large cardinal assumptions.

[19] B. Veličković. Applications of the open coloring axiom. In H. Judah, W. Just, and H. Woodin, editors, Set theory of the continuum, volume 26 of Mathematical Sciences Research Institute Publications, pages 137–154. Springer-Verlag, 1992. Berkeley, California, Oct. 16–20, 1989.

[20] B. Veličković. OCA and automorphisms of P(ω)/fin. Topology Appl., 49(1):1– 13, 1993.

[21] W. H. Woodin. The Axiom of Determinacy, Forcing Axioms, and the Nonstationary Ideal. Logic and its Applications. de Gruyter, 1999.

Department of Mathematics, Boise State University, Boise, Idaho 83725i

E-mail address: justin@math.boisestate.edu