SOME REMARKS ON THE OPEN COLORING AXIOM

JUSTIN TATCH MOORE

Abstract. This note contains two results relating to the problem of whether the Open Coloring Axiom implies that the continuum is ℵ_{2}. It also establishes that Farah’s OCA_{∞} is equivalent to OCA.

1. Introduction

The Open Coloring Axiom (OCA) is the assertion that every open graph on a separable metric space is either countably chromatic or else has an uncountable complete subgraph. Here a graph is open if the adjacency relation on the vertex set is topologically open. OCA is a consequence of the Proper Forcing Axiom (PFA) [11] and has been useful in a broad spectrum of applications, especially when combined with Martin’s Axiom [3], [4], [6], [7], [10], [11], [13], [14].

This form of OCA is due to Todorcevic [11] and was inspired by similar principles (one bearing the same name) introduced and studied by Abraham, Rubin, and Shelah in [1]. All of those consequences except the one also denoted OCA follow from Todorcevic’s formulation of OCA. In what follows, we will denote the original OCA of [1] by OCA_{[ARS]}.

Soon after Todorcevic introduced OCA, he proved that it implies 𝔟 = ℵ_{2} and asked if it implies 𝔠 = ℵ_{2} [11]. This question was made more intriguing by the following result.

Theorem 1. [8] The conjunction of OCA_{[ARS]} and OCA implies that 𝔠 = ℵ_{2}.

Recently Gilton and Neeman have announced that OCA_{[ARS]} does not imply 𝔠 = ℵ_{2}. One purpose of this note is to present two results which relate to the problem of whether OCA implies 𝔠 = ℵ_{2}. The first is stated as follows.

Theorem 2. If OCA holds and Q is a c.c.c. forcing which adds a new real then OCA fails in any forcing extension by Q which does not add a dominating real.

Theorem 2 gives some explanation to the general observation that it is very difficult (if not impossible) to add any reals and preserve OCA.

In order to understand and motivate the second result, we need to recall the basic structure of the proof of Theorem 1. Central to the argument is the notion of a code for a real r. A code for r is an uncountable clique for a certain open graph G_{r} on ω^{ω}. In [8] it is shown that OCA implies that if X ⊆ ω^{ω} is an unbounded <^{∗}- chain consisting of increasing functions, then each real has a code which is a subset of X. It is then shown that OCA_{[ARS]} implies that any X_{0} ⊆ ω^{ω} of cardinality ℵ_{1} can contain codes for at most ℵ_{1} many reals. The next result shows that this consequence of OCA_{[ARS]} is not a consequence of OCA.

Theorem 3. OCA is consistent with the existence of a set X_{0} ⊆ ω^{ω} of size ℵ_{1} which contains codes for ℵ_{2} reals.

The final section of the paper answers a question of Ilijas Farah. In [5], he introduced a formal strengthening of OCA in [5] which he denoted OCA_{∞}. This strengthening also follows from PFA and has been used in some applications of PFA where OCA a priori wasn’t quite sufficient to carry out the proof. It turns out, however, that OCA_{∞} is equivalent to OCA.

Theorem 4. Assume OCA. Whenever X is a separable metric space and ⟨G_{n} | n ∈ ω⟩ is a decreasing sequence of open subsets of [X]^{2} then either:

(1) there is a decomposition X = ⋃_{n∈ω} X_{n} where G_{n} ∩ [X_{n}]^{2} = ∅ for each n ∈ ω or

(2) There is an uncountable partial injection f : 2^{ω} → X such that if a ≠ b are in the domain of f, then {f(a), f(b)} ∈ G_{Δ(a,b)}.

The conclusion of Theorem 4 is in fact a formal strengthening of OCA_{∞} already considered in [5].

2. Notation and preliminaries

While an attempt has been made to keep this paper self contained, the reader is encouraged to have some familiarity with [8] as much of the motivation for the results in this paper stem from it. We will now fix some notation and recall some definitions. If x, y ∈ ω^{ω} are distinct, define Δ(x, y) to be the minimum n such that x(n) ≠ y(n). The function 2^{−Δ(x,y)} defines a separable metric topology on ω^{ω} which is compatible with the product topology. We will also equip ω^{ω} with the partial order of eventual dominance: x <^{∗} y if x(n) < y(n) for all but finitely many n. We will identify [ω^{ω}]^{2} — the collection of all unordered pairs from ω^{ω} — with the collection of ordered pairs (x, y) ∈ (ω^{ω})^{2} such that x <_{lex} y. When we refer to the topology on [ω^{ω}]^{2}, we will be referring to the subspace topology inherited from (ω^{ω})^{2}. Occasionally we will need to replace ω^{ω} with ω^{↑ω}, the collection of all strictly increasing functions from ω to ω. Recall that 𝔟, the unbounding number, is the smallest cardinality of a <^{∗}-unbounded subset of ω^{ω}.

We will need the map t from [8] and the notion of a code as presented there. To liberate the variable t we will use τ to denote this map. All that we will need from τ is that it satisfies the following conditions:

(1) τ is continuous and the domain of τ is an open subset of [ω^{↑ω}]^{2};

(2) if x <^{∗} y then {x, y} is in the domain of τ;

(3) for all {x, y} in the domain of τ, τ(x, y) is a binary sequence of length Δ(x, y).

(4) If r is in 2^{ω} and X ⊆ ω^{↑ω} is unbounded and countably directed with respect to <^{∗} then there is a {x, y} ∈ [X]^{2} ∩ dom(τ) such that τ(x, y) is an initial part of r.

Define G_{r} to be the collection of all pairs {x, y} such that τ(x, y) is defined and is an initial part of r. A set H ⊆ ω^{↑ω} is said to be a code for an element r of 2^{ω} if H is uncountable and [H]^{2} ⊆ G_{r}.

If G is an open graph on X, we will let H(G, X) denote the collection of all finite cliques viewed as a forcing, with the order of reverse containment. We will need the following consequence of the proof of Theorem 4.4 of [11].

Lemma 1 (CH). Let (G, X) be an open graph on a separable metric space X and let ⟨M_{α} | α ∈ ω_{1}⟩ be a continuous ∈-increasing sequence of elementary submodels of H(ℵ_{2}), each with (G, X) as an element. If Y is separated by M⃗ then H(G, Y) is c.c.c. in all its finite powers.

Here M⃗ separates Y if for all x ≠ y in Y there is an α ∈ ω_{1} such that exactly one of x, y is in M_{α}.

3. OCA and c.c.c. forcing extensions

In this section we will give a proof of Theorem 2. Let P be a c.c.c. partial order and let G ⊆ P be V -generic such that V [G] does not contain a dominating real. Let t ∈ 2^{ω} be in V [G] but not in V. By assumption, ω^{↑ω} ∩ V is unbounded in V [G]. Since P is c.c.c., every countable subset of ω^{↑ω} ∩ V in V [G] is contained in a countable set in V and hence ω^{↑ω} ∩ V is countably directed in V [G]. By the properties of τ, the restriction of G_{r} to ω^{↑ω} is not countably chromatic and hence there is a code H ⊆ ω^{↑ω} ∩ V for t. Now return to V and let X be the collection of all x in ω^{↑ω} such that there is a p in P which forces x̌ to be in Ḣ.

Now define a graph G^{∗} on X × 2^{ω} by putting {(x, r), (y, s)} in G^{∗} if and only if x ≠ y and τ(x, y) is an initial part of either r or s. To prove the theorem, it suffices to show that G^{∗} is not countably chromatic and yet does not contain an uncountable clique.

To see that G^{∗} is not countably chromatic, suppose for contradiction that it is and let X × 2^{ω} ⊆ ⋃_{n∈ω} Γ_{n} where Γ_{n} is closed and G^{∗} independent for each n. For each x in X, define

Γ_{n}(x) := {r ∈ 2^{ω} | (x, r) ∈ Γ_{n}}

and for each r in 2^{ω} define

Γ_{n}^{−1}(r) := {x ∈ X | (x, r) ∈ Γ_{n}}.

Observe that for all x in X, {Γ_{n}(x) | n ∈ ω} is a cover of 2^{ω}. Hence X×2^{ω} ⊆ ⋃{Γ_{n} | n ∈ ω} holds in any forcing extension by Shoenfield’s absoluteness theorem. On the other hand, if r is in 2^{ω}, {Γ_{n}^{−1}(r) | n ∈ ω} is a cover of X by G_{r}-independent sets. Hence X cannot contains a code for any r in any generic extension, a contradiction.

Now suppose that G^{∗} contains an uncountable clique Ω ⊆ X × 2^{ω}. Notice that since Ω is in V and t is not, there is an n ∈ ω such that for some uncountable Ω′ ⊆ Ω, if (x, r) is in Ω′ then Δ(r, t) ≤ n and if (x, r), (y, s) are in Ω′ then Δ(x, y) > n. Define

Y := {y ∈ X | ∃r ∈ 2^{ω}((y, r) ∈ Ω′)}.

Then Y is uncountable but cannot have an uncountable intersection with H. This is a contraction: since P is c.c.c., there must be a p ∈ P which forces that Y̌ ∩ Ḣ is uncountable. It follows that G^{∗} does not have an uncountable clique, completing the proof of Theorem 2.

4. OCA and small sets which contain many codes

The purpose of this section is to prove Theorem 3. Before we begin we will need some definitions. If X⃗ = ⟨x_{ξ} | ξ ∈ ω_{1}⟩ is a sequence of distinct elements of ω^{↑ω} and G is an open graph on the range of X then G is NS-Luzin if whenever E ⊆ ω_{1} indexes a G-independent set, E is nonstationary. We will use X to denote the range of X⃗. If u is a finite binary sequence, define G_{u} to consist of all {x, y} ∈ [ω^{↑ω}]^{2} such that u is an initial part of τ(x, y).

The essence of our proof of Theorem 3 is contained in the following lemmas.

Lemma 2 (CH). If ⟨(G_{i}, X⃗_{i}) | i ∈ ω⟩ is a sequence of NS-Luzin open graphs and (G_{∗}, Y) is an open graph such that (G_{∗}, Y) is not countably chromatic then there is a c.c.c. forcing which introduces an uncountable clique to (G_{∗}, Y) and preserves the NS-Luzin property of (G_{i}, X⃗_{i}) for all i ∈ ω.

Lemma 3. If G is an NS-Luzin graph and ⟨P_{α} | α ∈ δ⟩ is a directed system of c.c.c. forcings such that for all α ∈ δ, 1 ∥ _{P_{α}} Ǧ is NS-Luzin, then the direct limit forces that Ǧ is NS-Luzin.

Lemma 4. If X⃗ := ⟨x_{ξ} | ξ ∈ ω_{1}⟩ is a sequence of distinct elements of ω^{↑ω} such that for every finite binary sequence u, G_{u} is NS-Luzin when restricted to X, then (Gċ, X⃗) is NS-Luzin for any Cohen real ċ.

Before we prove the Lemmas, we first see how to deduce Theorem 3. Let V be a model of CH + ♢(S_{1}^{2}). Observe that if X⃗ = ⟨x_{ξ} | ξ ∈ ω_{1}⟩ is an unbounded chain in ω^{↑ω} in V then G_{u} is NS-Luzin for all finite binary u. Now iterate c.c.c. forcings using finite support using ♢(S_{1}^{2}) as a bookkeeping device as in the standard consistency proof of OCA, all the time using Lemma 2 to generate the necessary partial orders which preserve that G_{u} is NS-Luzin for each u in 2^{<ω}. By Lemma 3 this is preserved by all initial stages of the iteration. Since Cohen reals are added cofinally often by the support of the iteration, there will be ℵ_{2} reals r in the final model such that (G_{r}, X) is NS-Luzin. By OCA such graphs must have an uncountable clique. We will now turn to the proofs of the lemmas.

Proof of Lemma 2. Let ⟨(G_{i}, X⃗_{i}) | i ∈ ω⟩ and (G_{∗}, Y) be given and let x_{i,α} denote the α^{th} entry of X⃗_{i}. Consider the graphs ⟨(G_{i}, X_{i}) | i ∈ ω⟩ and (G_{∗}, Y) as a single graph which is the disjoint union of these graphs. Let ⟨M_{α} | α ∈ ω_{1}⟩ be a continuous ∈-chain of countable elementary submodels of H(ℵ_{2}) which contains all of these objects. Let C be the closed unbounded set of all α ∈ ω_{1} such that α = M_{α} ∩ ω_{1}. For each α in C, let y_{α} be any element of Y which is in Y ∩(M_{α+2}\M_{α+1}) and define Y′ := {y_{α} | α ∈ C}. For each i ∈ ω, the set Z := {x_{i,α} | α ∈ C}∪Y′ is still separated by M⃗ and therefore H(G_{i} ˙∪G_{∗}, Z) is c.c.c. in all its finite powers. Notice that this implies that H(G_{∗}, Y′) does not introduce any uncountable G_{i}-independent subset of {x_{i,α} | α ∈ C} since otherwise this would give an uncountable antichain in

H(G_{i}, {x_{α} | α ∈ C}) × H(G_{∗}, Y′) ⊆ H(G_{i} ∪ G_{∗}, Z)^{2}.

This finishes the proof. □

Proof of Lemma 3. Suppose that G is a graph on {x_{ξ} | ξ ∈ ω_{1}} and that Ṡ is a P_{δ}-name for a stationary subset of ω_{1} where P_{δ} is the direct limit of the system ⟨P_{α} | α ∈ δ⟩. If δ has countable cofinality then let δ := sup_{n} δ_{n} and Ṡ_{n} be the P_{δ_{n}}-name which is the restriction of Ṡ — an element of P_{δ_{n}}-forces ξ is in Ṡ_{n} if its image in P_{δ} forces that ξ is in Ṡ. Let p ∈ P_{δ} be arbitrary. Since p forces that Ṡ is the union of Ṡ_{n}, there is an n and q ∈ P_{δ_{n}} such that q ≤ p and q ∥ _{P_{δn}} Ṡ_{n} is stationary. By assumption q ∥ _{P_{δn}} {x_{ξ} | ξ ∈ Ṡ_{n}} is not G-independent. Thus q ∥ _{P_{δ}}{x_{ξ} | ξ ∈ Ṡ} is not G-independent. Since p was arbitrary, this is forced by every condition in P_{δ}.

Now suppose that δ has uncountable cofinality. Suppose that Ė is a P_{δ}-name for a subset of ω_{1} such that {x_{ξ} | ξ ∈ Ė} is forced by p ∈ P_{δ} to be G-independent. We need to show that p forces that Ė is nonstationary. Since the closure of a G-independent set is independent, we may assume that {x_{ξ} | ξ ∈ Ė} is relatively closed in {x_{ξ} | ξ ∈ ω_{1}}. Now, since P_{δ} is a direct limit of c.c.c. partial orders and δ has uncountable cofinality, any relatively closed set added by P_{δ} is added by some P_{α} for α ∈ δ. Hence there is an α ∈ δ and a P_{α}-name Ḟ such that p ∥ _{P_{δ}} Ḟ = Ė. Now applying the hypothesis, we see that Ė is forced by p to be nonstationary. □

Proof of Lemma 4. Suppose that p ∈ 2^{<ω} is a condition in Cohen forcing and Ṡ is a name such that p forces Ṡ is a stationary subset of ω_{1}. We need to find an extension q of p and α ≠ β such that q forces that α̌, β̌ ∈ Ṡ and {x̌_{α}, x̌_{β}} is in Gċ.

Find an extension p′ of p such that S′ := {α ∈ ω_{1} | p′ ∥ α ∈ Ṡ} is stationary. Since G_{p′} is NS-Luzin, there is a pair α ≠ β in S′ such that τ(x_{α}, x_{β}) extends p′. Finally, extend p′ to q := τ(x_{α}, x_{β}). Now q forces that τ(x_{α}, x_{β}) is an initial part of ċ and hence that {x̌_{α}, x̌_{β}} is in Gċ. □

5. OCA implies OCA_{∞}

We will now prove Theorem 4. Let ⟨(G_{n}, X) | n ∈ ω⟩ be given as in the statement of Theorem 4 and define an open graph G on 2^{ω} × X by {(a, x), (b, y)} ∈ G if and only if a ≠ b, x ≠ y, and {x, y} ∈ G_{Δ(a,b)}. Notice that G is open: if {(a, x), (b, y)} is in G, then there are disjoint open neighborhoods U and V about (a, x) and (b, y) respectively so that if (a′, x′) ∈ U and (b′, y′) ∈ V then Δ(a′, b′) = Δ(a, b) and {x′, y′} ∈ G_{Δ(a,b)} = G_{Δ(a′,b′)}. Next observe that if f ⊆ 2^{ω} × X is an uncountable complete subgraph of G, then f satisfies the second alternative of the lemma.

Now suppose that 2^{ω} × X = ⋃_{n∈ω} E_{n}. Since the closure of a G_{n}-independent set is G_{n}-independent, we may assume that each E_{n} is closed in 2^{ω} × X. For each x ∈ X, 2^{ω} × {x} ⊆ ⋃_{n∈ω} E_{n}. Hence by the Baire Category Theorem, it is possible to pick n_{x} ∈ ω and t_{x} ∈ 2^{<ω} for each x ∈ X such that [t_{x}] × {x} ⊆ E_{n_{x}}. If (n, t) ∈ ω × 2^{<ω}, define X_{n,t} to be the set of all x such that n_{x} = n and t_{x} = t.

Claim. For each n and t, X_{n,t} is G_{|t|}-independent.

Proof. Let x ≠ y be in X_{n,t} and fix a ∈ [t^{⌢}0] and b ∈ [t^{⌢}1]. We have that Δ(a, b) = |t| and {(x, a), (y, b)} ⊆ E_{n}. Since E_{n} is G-independent, {x, y} ∉ G_{Δ(a,b)} = G_{|t|}. □

Finally let ⟨X_{n} | n ∈ ω⟩ be any enumeration of {X_{n,t} | n ∈ ω and t ∈ 2^{<ω}} such that if X_{k} = X_{n,t}, then k ≥ |t|. Since G_{m+1} ⊆ G_{m} for all m, any G_{m}- independent set is G_{k} independent for all k > m. It follows that the decomposition X = ⋃_{k∈ω} X_{k} satisfies the first alternative of the lemma.

6. Open questions

We will conclude with a list of some open questions.

Question 1. Assume OCA. If Q is a c.c.c. poset which adds a new real, does Q force that OCA fails?

Question 2. Is it possible to force OCA together with 𝔠 > ℵ_{2} with a c.c.c. poset starting from some model of CH?

Question 3. Does OCA imply that cov(ℳ) ≤ ℵ_{2}?

The existing techniques for building posets for forcing instances of OCA all involve using finite conditions. Such posets seem likely to add Cohen reals (although this is not well understood — it is not known if OCA implies cov(ℳ) > ℵ_{1}), suggesting that if we force OCA using known techniques, cov(ℳ) = 𝔠 should hold in the generic extension. On the other hand, if OCA holds, there will be a transitive set M of cardinality ℵ_{2} such that (M, ∈) satisfies OCA and a suitable fragment of ZFC and such that M ∩ ω^{ω} is <^{∗}-unbounded. If cov(M) > ℵ_{2}, then there will be a Cohen real c over M and c will have a code H which is a subset of M ∩ ω^{↑ω}. This seems implausible.

References

[1] 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.

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

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

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

[5] I. Farah. Cauchy nets and open colorings. Publ. Inst. Math. (Beograd) (N.S.), 64(78):146– 152, 1998. 50th anniversary of the Mathematical Institute, Serbian Academy of Sciences and Arts (Belgrade, 1996).

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

[7] . All automorphisms of the Calkin algebra are inner. Ann. of Math. (2), 173(2):619– 661, 2011.

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

[9] Stevo Todorcevic. Comparing the continuum with the first two uncountable cardinals. In Logic and scientific methods (Florence, 1995), pages 145–155. Kluwer Acad. Publ., Dordrecht, 1997.

[10] . Embeddability of K × C into X. Bull. Cl. Sci. Math. Nat. Sci. Math., (22):27–35, 1997.

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

[12] . PFA and the continuum. Preprint August 1987.

[13] . A proof of Nogura’s conjecture. Proc. Amer. Math. Soc., 131(12):3919–3923, 2003.

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