Open colorings, the continuum and the second uncountable cardinal ^{∗}

Justin Tatch Moore

June 15, 2002

Abstract

The purpose of this article is to analyze the cardinality of the continuum using Ramsey theoretic statements about open colorings or “open coloring axioms.” In particular I will show that the conjunction of two well known axioms, OCA_{[ARS]} and OCA_{[T]}, implies that the size of the continuum is ℵ_{2}.

Our focus in this paper will be the following two open coloring axioms ^{1} and their influence on the size of the continuum.

OCA_{[ARS]} If X is a separable metric space of size ℵ_{1} and c : [X]^{2} → {1, …, n} is a continuous map then there is a decomposition of X into countably many pieces X_{i} (i ∈ ℕ) such that c is constant on [X_{i}]^{2} for all i ∈ ℕ.

OCA_{[T]} If X is a separable metric space and G ⊆ [X]^{2} is open then either G is countably chromatic (there is a decomposition of X into countably many pieces X_{i} such that [X_{i}]^{2} ∩ G is empty for all i) or there is an uncountable H ⊆ X such that [H]^{2} ⊆ G.

∗The research for this paper was supported by EPSRC grant GR/M71121 during my stay at the University of East Anglia. I would also like to acknowledge the support I received from the Institut Mittag-Leffler during my visit there.

1The subscripts [ARS] and [T] refer to [1] and [11] where these axioms originally appeared. In the current literature OCA has come to mean OCA_{[T]}.

Here [X]^{2} is the set of unordered pairs of distinct elements of X. A set G ⊆ [X]^{2} is open if for every {x, y} in G there are disjoint neighborhoods U ∋ x and V ∋ y such that {{x′, y′} : x′ ∈ U, y′ ∈ V } is contained in G. One defines continuity in a similar way for functions of the form c : [X]^{2} → {1, …, n}.

What I will demonstrate through the course of this note is that the conjunction of these two axioms implies that there are exactly ℵ_{2} real numbers. The proof is divided into four parts, each contributing a section to the paper along with some review and concluding remarks. The first section recalls some of the basic properties of the partial order (ℕ^{ℕ}, <^{∗}) of eventual dominance. Section 2 gives some of the flavor of the proof from [11] that OCA_{[T]} implies that the minimum size of an unbounded subset of (ℕ^{ℕ}, <^{∗}) is equal to ℵ_{2}. Section 3 introduces the alternation map and its properties. This map is then used in Section 4 to code reals inside of certain unbounded subsets of (ℕ^{ℕ}, <^{∗}) in the presence of OCA_{[T]}. Section 5 shows that OCA_{[ARS]} prevents too many reals from being coded inside of any subset of ℕ^{ℕ} of size ℵ_{1}. The final section closes with some questions and comments.

None of the mathematics in this paper should be beyond the understanding of someone able to make sense of the statement of the main theorem. Those familiar with the order (ℕ^{ℕ}, <^{∗}) should feel free to skip the first section. Those familiar with OCA_{[T]} may wish to skip directly to Section 3. Readers interested in further reading on 2^{ℵ_{0}} and ℵ_{2} are referred to [3],[8],[9], [12], and [13].

I would like to thank Stevo Todorčević for giving me Theorem 2.1 as an exercise back in 1997 during our first evening in a coffee shop. He also offered some useful suggestions on the presentation of the material in Section 2.

1 The partial order (ℕ^{ℕ}, <^{∗})

Our discussion in this paper will frequently focus around the topological space ℕ^{ℕ} of all sequences of natural numbers. This is a complete separable metric space when equipped with the product topology. Basic open sets in this context take the form

[u] = {x ∈ ℕ^{ℕ} : x extends u}

where u is a finite sequence of natural numbers. The complete metric is given by d(x, y) = 2^{−Δ(x,y)} where

Δ(x, y) = min{n : x(n) ≠ y(n)}.

We will also be interested in ℕ^{ℕ} as a partially ordered set under the order <^{∗} of eventual dominance:

x <^{∗} y iff x(n) < y(n) for all but finitely many n.

The partial order (ℕ^{ℕ}, <^{∗}) has a rich structure and frequently shows up in mathematical problems, particularly those close to analysis, set theory, and general topology. The following observations are well known and easily proven.

Fact 1.1. (ℕ^{ℕ}, <^{∗}) is countably directed (every countable subset has an upper bound).

Fact 1.2. If X is an unbounded and countably directed subset of (ℕ^{ℕ}, <^{∗}) then whenever X is decomposed into countably many sets X_{n} (n ∈ ℕ), there is an n such that X_{n} is unbounded and countably directed.

In light of Fact 1.1 and the trivial observation that ℕ^{ℕ} is unbounded in (ℕ^{ℕ}, <^{∗}) it makes sense to define the following cardinal.

Definition 1.3. The unbounding number 𝔟 is the minimum size of an unbounded subset of (ℕ^{ℕ}, <^{∗}).

This cardinal is therefore somewhere between ℵ_{1} and 2^{ℵ_{0}}. It turns out to have some rather surprising combinatorial properties (see [11, §1]). The following fact is well known and easily verified.

Fact 1.4. There is an unbounded chain in (ℕ^{ℕ}, <^{∗}) of order type 𝔟. In particular there is an unbounded and countably directed subset of (ℕ^{ℕ}, <^{∗}) of size 𝔟.

The next observation is behind much of the combinatorics associated with unboundedness in (ℕ^{ℕ}, <^{∗}).

Fact 1.5. Suppose X ⊆ ℕ^{ℕ} is nonempty and has the property that every neighborhood of X is unbounded. For every basic open set [u], if [u] ∩ X is nonempty, then there is a v extending u such that [vˆ i] ∩ X is nonempty for infinitely many i.

Notice that since the union of countably many bounded sets is bounded (by Fact 1.1), if X is an unbounded subset of (ℕ^{ℕ}, <^{∗}) then it contains a nonempty set X′ such that every neighborhood of X′ is unbounded.

2 ℵ_{2} and the unbounding number

This section will review the following result and give a sketch of its proof.

Theorem 2.1. [11] OCA _{[T]} implies that 𝔟 is ℵ_{2}.

This result breaks into two parts, one showing 𝔟 is at least ℵ_{2} and the later showing that it is at most ℵ_{2}. Proving that 𝔟 is at least ℵ_{2} under OCA_{[T]} was done originally via the oscillation map (see [11]). It was this proof that lead me to the discovery of the alternation map (which is essentially a continuous version of the oscillation map) and to the coding technique which will be presented in the later sections. An interested reader is encouraged to deduce this portion of the Theorem 2.1 from the properties of the alternation map given below.

The half of Theorem 2.1 which deals with the inequality 𝔟 ≤ ℵ_{2} makes crucial use of the following well studied notion.

Definition 2.2. If κ and λ are cardinals then a (κ, λ^{∗}) gap in (ℕ^{ℕ}, <^{∗}) is a pair of sequences a_{ξ} (ξ < κ) and b_{η} (η < λ) in ℕ^{ℕ} such that

a_{ξ} <^{∗} a_{ξ′} <^{∗} b_{η′} <^{∗} b_{η}

for all ξ < ξ′ < κ and η < η′ < λ but for which there is no single c in ℕ^{ℕ} such that a_{ξ} <^{∗} c <^{∗} b_{η} for all ξ < κ and η < λ.

Long ago Hausdorff made the following important connection between gaps and unbounded chains in (ℕ^{ℕ}, <^{∗}).

Theorem 2.3. [4] If κ is a regular cardinal, then there is an unbounded chain in (ℕ^{ℕ}, <^{∗}) of order type κ iff there is a (κ, ω^{∗}) gap in (ℕ^{ℕ}, <^{∗}).

Hausdorff also discovered another type of gap — the (ω_{1}, ω_{1}^{∗}) gap. Rather remarkably, this is the best that one can do without using extra assumptions.

Theorem 2.4. [11] Under OCA _{[T]} all gaps in (ℕ^{ℕ}, <^{∗}) are of the form (ω_{1}, ω_{1}^{∗}), (κ, ω^{∗}), or (ω^{∗}, κ) for some cardinal κ.

Also quite striking is the following fact which now completes the proof of Theorem 2.1. An interested reader is encouraged to supply its proof via Theorem 2.3.

Lemma 2.5. [11] If every subset of ℕ^{ℕ} of size at most ℵ_{2} is bounded, then there is an (ω_{2}, κ^{∗}) gap in (ℕ^{ℕ}, <^{∗}) for some regular uncountable cardinal κ.

3 The alternation map

For technical reasons we will now restrict our discussion to the suborder (ℕ^{↑ℕ}, <^{∗}) of strictly increasing sequences of natural numbers. Since ℕ^{↑ℕ} is both cofinal in and order isomorphic to (ℕ^{ℕ}, <^{∗}) this is really not a loss of generality. The following notion will be central to our discussion in this section.

Definition 3.1. Suppose that S is a subset of ℕ. Two sequences x and y in ℕ^{↑ℕ} are said to alternate on S if x(n) ≠ y(n) for all n in S and for every pair of consecutive elements m and n of S, x(m) < y(m) iff x(n) > y(n).

Notice that this notion also makes sense if x and y are only partial functions whose domains include S.

Now suppose that x and y are two distinct elements of ℕ^{↑ℕ} and that x is lexicographically less than y. Define a set S(x, y) ⊆ ℕ by recursion. The first element of S(x, y) is Δ(x, y). Given the 2n^{th} element k of S(x, y) define the next two elements to be y(k) and x(y(k)). So the elements of S(x, y) are

Δ(x, y), y(Δ(x, y)), x(y(Δ(x, y))), y(x(y(Δ(x, y)))), …

If x and y are only partial functions, repeat this procedure so long as the elements generated remain in the domains of both x and y. Since x and y are strictly increasing, the elements of S being defined are getting successively larger and larger. If i is an integer and S(x, y) has an i^{th} element (starting with i = 0), then we will occasionally find it convenient to denote it as S(x, y)(i).

Notice that the map S : [ℕ^{↑ℕ}]^{2} → P(ℕ) is continuous since to determine a finite amount of information about S(x, y) one needs only a finite amount of information about x and y. Given S(x, y), alt(x, y) is defined to be the cardinality of the largest initial segment of S(x, y) on which x and y alternate minus one. Thus alt : [ℕ^{↑ℕ}]^{2} → ℕ ∪ {∞} is also a continuous map, where ℕ ∪ {∞} is the one point compactification of ℕ. Notice that the alternation map is finite on all pairs which are comparable in (ℕ^{↑ℕ}, <^{∗}).

The following theorem shows that the alternation map exhibits a behavior similar to that of the more well known oscillation map of Todorčević (see, e.g., [11]). It has essentially appeared in [5] and chapter 4 of [6]. A proof has been included for completeness.

Theorem 3.2. If X is an unbounded and countably directed in (ℕ^{↑ℕ}, <^{∗}) then there is an n such that for every k there is a pair x, y in X with Δ(x, y) = n and alt(x, y) = k.

Proof. Let X be given and choose a countable dense subset D of X. Since (X, <^{∗}) is countably directed, there is an a in X which is an upper bound for D. Now consider the set of all {y ∈ X : a <^{∗} y}. Since X is directed and unbounded, this set is also unbounded. It is therefore possible by Fact 1.2 to find an n and a subcollection Y of this set such that every neighborhood of Y is unbounded and a(i) < y(i) for every y in Y and i ≥ m.

Now choose a sequence u_{k} (i ∈ ℕ) such that for all k

1. u_{k} is a finite sequence of natural numbers such that [u_{k}ˆ i] ∩ Y is nonempty for infinitely many i,

2. u_{k} is an initial segment of u_{k+2},

3. Δ(u_{k}, u_{k+1}) = |u_{0}| > m,

4. |u_{k}| < S(u_{k+1}, u_{k+2})(k) < |u_{k+1}|, and

5. u_{k+2}(n_{k}) < u_{k+1}(n_{k}) where n_{k} = S(u_{k+1}, u_{k+2})(k).

The recursion is easily carried out using Fact 1.5. Notice that u_{2k+1} <_{lex} u_{2k+2} follows from 2, 3, and 5. Also, by 2 and 3, S(u_{k+1}, u_{k+2})(i) is a fixed integer n_{i} which does not depend on k provided that i ≤ k. By 5 u_{k} and u_{k+1} alternate on S(u_{k}, u_{k+1}) = {n_{0}, …, n_{k−1}} (S(u_{0}, u_{1}) is empty).

Now let d_{k} be in [u_{k+1}] ∩ D and fix an m_{k} such that d_{k}(i) < a(i) for all i > m_{k}. Choose y_{k} in [u_{k}] ∩ Y such that y_{k}(|u_{k}|) > a(m_{k}). Note that y_{k} dominates d_{k} on the interval [|u_{k}|, m_{k}] by monotonicity and y_{k} dominates d_{k} [m_{k}, ∞) since m_{k} > m. It follows that Δ(d_{k}, y_{k}) = n_{0} and that {n_{0}, …, n_{k}} are the first k + 1 elements of S(d_{k}, y_{k}). Note that y_{k}(n_{k}) > d_{k}(n_{k}) and that the next element of S(d_{k}, y_{k}) is greater than |u_{k}| and hence y_{k} dominates d_{k} at this place as well. Hence by our observations above {n_{0}, …, n_{k}} is exactly the largest initial segment of S(d_{k}, y_{k}) on which d_{k} and y_{k} alternate, making alt(d_{k}, y_{k}) = k.

4 Continuously coding a real number

In this section we will see how to code countable binary sequences into subsets of ℕ^{ℕ}. Since the real numbers have the same size as {0, 1}^{ℕ} this can be considered as a means for coding reals. To facilitate the coding that we are about to define, it is useful if we change the map alt to a map t which takes values which are finite binary sequences rather than natural numbers. To this end let φ(k, n) be the unique binary sequence t of length n such that

k ≡ ∑_{i=0}^{n−1} t(i)2^{i} mod 2^{n}.

It is easily seen that φ(·, n) maps onto the binary sequences of length n. If x, y are in ℕ^{↑ℕ} and alt(x, y) is finite, define

t(x, y) = φ(alt(x, y), Δ(x, y)).

Notice that, since it is a composition of continuous functions, t is continuous on its domain. Its domain is the preimage of ℕ under the alternation map and is therefore an open set. Similarly t is defined on all pairs x and y which are comparable in (ℕ^{↑ℕ}, <^{∗}). Theorem 3.2 immediately gives the following result.

Theorem 4.1. If X is unbounded and countably directed in (ℕ^{↑ℕ}, <^{∗}) and r is in {0, 1}^{ℕ} then there is a pair x, y in X such that t(x, y) is defined and is an initial segment of r.

Now we are ready to define what it means for a set H ⊆ ℕ^{↑ℕ} to code an element r of {0, 1}^{ℕ}.

Definition 4.2. If H ⊆ ℕ^{↑ℕ} is uncountable, t is defined on [H]^{2}, and the image of [H]^{2} under t contains no two incompatible elements then H is said to be a code. If r is the unique element of {0, 1}^{ℕ} such that t(x, y) is an initial segment of r for all x, y in H then we will say that r is coded by H.

Remark 4.3. Notice that the map Δ is unbounded on the pairs of any uncountable set X. This implies that no set can be a code for two distinct r and r′ in {0, 1}^{ℕ}.

Theorem 4.4. (OCA _{[T]}) If X ⊆ ℕ^{↑ℕ} is unbounded and countably directed then for every r in {0, 1}^{ℕ} there is an H ⊆ X which codes it.

Proof. Define G_{r} ⊆ [X]^{2} by putting {x, y} in G_{r} iff t(x, y) is defined and is an initial segment of r. Since t is continuous and has an open domain, G_{r} is open. By Fact 1.2 and Theorem 4.1, G_{r} isn’t countably chromatic. Applying OCA_{[T]}, there is an uncountable H ⊆ X such that [H]^{2} ⊆ G_{r} which, by definition, is a code for r.

5 Sealing codes

In this section we finish the proof of the main result by showing that under OCA_{[ARS]} any chain in (ℕ^{↑ℕ}, <^{∗}) of size ℵ_{2} can contain codes for at most ℵ_{2} reals.

Theorem 5.1. (OCA _{[ARS]}) Suppose that X_{0} ⊆ ℕ^{↑ℕ} has size ℵ_{1} and t is defined on [X_{0}]^{2}. There is a disjoint family A_{r} (r ∈ {0, 1}^{ℕ}) of (possibly empty) subsets of X_{0} such that if H ⊆ X_{0} is a code for r then H \ A_{r} is at most countable. In particular at most ℵ_{1} many different elements of {0, 1}^{ℕ} have codes contained in X_{0}.

Proof. Define t_{n} : [X_{0}]^{2} → {0, 1}^{≤n} for each n by setting t_{n}(x, y) to be the restriction of t(x, y) to its first n entries (set t_{n}(x, y) = t(x, y) if Δ(x, y) ≤ n). Note that t_{n} is also continuous for each n and has finite range. Construct a family {A_{s}} indexed by the finite binary sequences with the following properties:

1. For each n the collection {A_{s} : s ∈ {0, 1}^{n}} is a partition of X_{0} into disjoint sets.

2. Each A_{s} can be decomposed into countably many sets A_{s,i} such that t_{|s|} is constantly s on [A_{s,i}]^{2} for all i.

Let n be fixed and apply OCA_{[ARS]} to t_{n} : [X_{0}]^{2} → {0, 1}^{≤n} to get countably many sets Y_{i} such that t_{n} is constant on [Y_{i}]^{2} for all i. Notice we may assume that, for each i, if x ≠ y are in Y_{i} then Δ(x, y) > n. It follows that for every i there is an s in {0, 1}^{n} such that t is constantly s on [Y_{i}]^{2} (possibly for trivial reasons). The sets A_{s} (s ∈ {0, 1}^{n}) are now constructed so that they are pairwise disjoint and each A_{s} is contained in union of all Y_{i} such that t_{n} is constantly s on [Y_{i}]^{2}. It should be clear that these sets satisfy properties 1 and 2 above.

If r is in {0, 1}^{ℕ} set A_{r} = ⋂_{n=0}^{∞} A_{r↾n}. By property 1 A_{r} and A_{r′} are disjoint for distinct r and r′ in {0, 1}^{ℕ}. Now observe that, by property 2, if s ∈ {0, 1}^{n} is different than r ↾ n then H ∩A_{s} is countable since t′′_{n}[H]^{2} ⊆ {⟨⟩, …, r ↾ n}. Applying property 1 again, H \ A_{r↾n} is countable for all n and hence H \ A_{r} is countable.

6 Closing remarks

I will now close this paper by mentioning the following two open problems.

Question 6.1. Does OCA_{[ARS]} imply 2^{ℵ_{0}} is ℵ_{2}?

Question 6.2. Does OCA_{[T]} imply 2^{ℵ_{0}} is ℵ_{2}?

Both of these questions are interesting for different reasons and, in spite of their similar appearance, seem to be quite different in nature. Question 6.1 is a special case of the more well known open problem of whether the Bounded Proper Forcing Axiom implies 2^{ℵ_{0}} = ℵ_{2} (see [10] for more information on bounded forcing axioms). Question 6.2 has been pursued since OCA_{[T]} was introduced. Interest in it stems both from the wide variety of applications which this axiom has seen (see, e.g., [2], [11, §8]) and from the fact that it is consistent with an effective form of the Continuum Hypothesis in the absence of the Axiom of Choice (see [7]). I. Farah has shown in an unpublished note that it is consistent that OCA_{[T]} holds for graphs of size ℵ_{1} and 2^{ℵ_{0}} > ℵ_{2} but it is known that this restricted form of the axiom is much weaker than OCA_{[T]} (see [10]). Both questions are also interesting if they are supplemented with MA_{ℵ_{1}}, an axiom often used in conjunction with these axioms.

Any complete resolution to these questions would be of great interest. If either question has a positive answer (particularly in the case of Question 6.1) this would seem to require a new method for proving that 2^{ℵ_{0}} is ℵ_{2}. On the other hand, if both questions have a negative answer, this would give two Ramsey theoretic statements which are individually consistent with 2^{ℵ_{0}} > ℵ_{2} but which jointly imply 2^{ℵ_{0}} = ℵ_{2}. Situations of this kind (and lack thereof) have recently received a great deal of attention — see [13].

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 (1985) 123-206.

[2] I. Farah. Analytic Quotients. Memoirs of the AMS 148 702 (2000).

[3] M. Foreman, M. Magidor, S. Shelah. Martin’s Maximum, Saturated Ideals, and Nonregular Ultrafilters. I. Ann. of Math. 127 1 (1988) 1-47.

[4] F. Hausdorff. Die Graduierung nach dem Endverlauf. Abhandlun. König. Sächsis. Gesellsch. Wissenschaften, Math.-Phys. Kl. 31 (1909) 296-334.

[5] J. T. Moore. Continuous Colorings Associated With Certain Characteristics of the Continuum. Discrete Math. 214 (2000) 263-273.

[6] J. T. Moore. Topics in Ramsey Theory on Sets of Real Numbers. Ph.D. Thesis. University of Toronto (2000).

[7] C. Di Prisco, S. Todorčević. Perfect Set Properties in L(ℝ)[U]. Adv. Math. 139 2 (1998) 240-259.

[8] S. Todorčević. Comparing the Continuum With the First Two Uncountable Cardinals, in Logic and Scientific Methods (M. L. Dalla, et al, eds.). Kluwer Acad. Publ. (1997) 145-155.

[9] S. Todorčević. Conjectures of Chang and Rado and Cardinal Arithmetic, in Finite and Infinite Sets in Combinatorics (N. W. Sauer et al., eds), Kluwer Acad. Publ. (1993) 385-398.

[10] S. Todorčević. Localized reflection and fragments of PFA . DIMACS Ser. Discrete Math. Theoret. Comput. Sci. (to appear).

[11] S. Todorčević. Partition Problems In Topology. American Math. Soc., Providence (1989).

[12] B. Veličković. Forcing Axioms and Stationary Sets. Adv. Math. 94 (1992) 256-284.

[13] W. H. Woodin. The Axiom of Determinacy, Forcing Axioms, and the Nonstationary Ideal. de Gruyter Series in Logic and its Applications (1999).