RANDOM REALS AND ω_{1} → (ω_{1}, (α : α))^{2}

J. TATCH MOORE

Abstract. The purpose of this note will be to extend the results of J. Barnett and S. Todorčević concerning the influence MA_{ℵ_{1}} has on random graphs. I will demonstrate that if MA_{ℵ_{1}} holds then ω_{1} → (ω_{1}, (α : α))^{2} holds for every α < ω_{1} after the addition of any number of random reals.

1. Introduction

The focus of this note is to extend J. Barnett’s result in [2] that ω_{1} → (ω_{1}, (α : n))^{2} holds for all α < ω_{1} and all n < ω after the addition of any number of random reals to a model of MA_{ℵ_{1}}. Also, in [1] Barnett has shown that the stronger partition relation ω_{1} → (ω_{1}, (α : ω_{1}))^{2} holds for every α < ω_{1} after the addition of one random real to a model of MA_{ℵ_{1}}. S. Todorcevic has shown in [9, Ch. 6] that ω_{1} → (ω : ω_{1})_{2}^{2} always fails in the presence of a Sierpinski set (and in particular in models in which uncountably many random reals have been added). In light of these results it is reasonable to ask whether ω_{1} → (ω_{1}, (α : α))^{2} holds for all α < ω_{1} after the addition of an arbitrary number of random reals to a model of MA_{ℵ_{1}}. The result of this note provides a positive answer to this question.

This note is intended to be self contained, modulo the standard partition calculus notation. This can be found in Erdös, Hajnal, Maté, and Rado’s book [4] on partition calculus, which is also a good source of reading on the topic.

2. Partition Trees on Countable Ordinals

In this section I will introduce a class of objects which will prove useful in our analysis of objects in an extension of a model of MA_{ℵ_{1}} by random reals. The motivation for these definitions comes from a class of ultrafilters which were introduced and developed by A. Hajnal and R. Laver (see [3], [6]) to show that MA_{ℵ_{1}} implies ω_{1} → (ω_{1}, (α : ω_{1}))^{2} for all α < ω_{1}.

Definition 2.1. A partition tree T (on a set of ordinals) is a collection closed countable sets of ordinals such that the following conditions hold 1. T is a tree under the order of reverse inclusion.

2. If A and B are incompatible elements of T then either A < B (i.e. sup A < inf B) or B < A.

3. An element of T is a terminal node (i.e. has no successors) iff it is a singleton.

4. If A is an element of T which is not a terminal node, then A has infinitely many immediate successors, none of which contain max A.

5. If A is a nonterminal node of T then max A is the unique limit point of the collection of immediate successors of A (i.e. the minimums of the immediate successors of A forms an ω-sequence converging to max A).

6. If B, C are immediate successors of a node A in T such that max B < min C then otp B ≤ otp C.

Notation. The set of all α such that {α} is a node of T will be denoted by πT.

Notice that all partition trees are well founded (i.e. have no infinite branch) since the maximum function is a decreasing map into the ordinals along any branch of a partition tree. The definition of a partition tree is made to facilitate the definition and discussion of classes of objects, usually filters, which are associated with them.

Definition 2.2. Suppose T is a partition tree. A filter F on T is a collection of partition subtrees of T such that

1. the empty tree is not in F,

2. if F_{0} ⊆ F is finite then ∩F_{0} is in F, and

3. if S is in F and S′ is a subtree of T which contains S, then S′ is

also in F. A filter F on T is tree-like if there is an association of a filter F_{A} on the successors of A for each nonterminal A in T such that S is in F iff for every A in S, A has F_{A}-many successors in T. A tree-like filter is an ultrafilter if the filters F_{A} are all ultrafilters. A tree-like filter F is uniform if F_{A} contains the Frechet filter for every A in T.

Notice that every filter F on a partition tree T induces a filter πF on πT which is generated by {πS : S ∈ F}.

Definition 2.3. The ordertype otp(T) of a partition tree T is defined by recursion on the rank of T. If T is just a singleton, then otp(T) = 1. If {A_{n}}_{n=0}^{∞} is an increasing enumeration of the first level of T above the root of T then otp(T) = ∑_{n=0}^{∞} otp(T [A_{n}]) (where T [A] = {B ∈ T : B ⊆ A}).

It is easily checked that, if T is a partition tree otp(T) = min{otp(X) : X ∈ F} whenever F is a uniform tree-like filter on T, thus justifying the definition of otp(T). It is well known and easily verified that for every indecomposable ordinal α, there is a partition tree T such that πT ⊆ α and otp(T) = α. The following is essentially proven in [6].

Lemma 2.4 (MA_{ℵ_{1}}). If F is a uniform tree-like filter on a partition tree T and {A_{ξ} : ξ < ω_{1}} is a sequence of elements of πF then there is an uncountable B ⊆ ω_{1} such that ⋂_{ξ∈B} A_{ξ} has order type at least otp(T).

The following standard absoluteness result will be very useful in proving the main theorem. The proof is included for completeness.

Lemma 2.5. Suppose M ⊆ N are models of ZFC which contain the same ordinals. If {A_{ξ} : ξ < ω_{1}} ⊆ M is a sequence of subsets of ω_{1} and α < ω_{1} is such that there are sets A, B ⊆ ω_{1} in N with A ⊆ ⋂_{ξ∈B} A_{ξ} and otp(A) = otp(B) = α then M contains a pair of such sets which have the same properties.

Proof. Fix a bijection e : ω → α. Let (E, <) be the collection of all pairs (s, t) such that

1. s, t are injections from some set {0, …, n} into ω_{1},

2. s(i) is in A_{t(j)} for every i, j ≤ n, and

3. for every i < j ≤ n, s(i) < s(j) iff t(i) < t(j) iff e(i) < e(j) and < orders E by coordinatewise extension. Clearly an infinite branch through (E, <) gives the desired object and (E, <) is well founded in M iff it is in N.

3. The Main Result

The following theorem was proven implicitly in [7] during the course of proving the main result.

Lemma 3.1 (MA_{ℵ_{1}}). If Ġ is a name for a graph on ω_{1} then either 1. Ġ is forced to be countably chromatic or

2. for every ε < ω_{1} there are sets A, B ⊆ κ and a δ > 0 such that otp(A) ≥ ε, otp(B) = ω_{1}, A < B, and for every α ∈ A, β ∈ B

μ([[{α, β} ∈ Ġ]]) ≥ δ.

The following lemma is a modification of Theorem 4 of [8] which is useful in the setting of tree-like filters.

Lemma 3.2. Suppose that T is a partition tree, R is a measure algebra whose character is everywhere greater than #(I) for some set I, and U is a tree-like ultrafilter on T. If ḟ_{β} : πT → R is indexed by I then there is a sequence f̃_{β} : T → R indexed by I satisfying the following conditions for every β ∈ I:

1. If ξ is in πT then f̃_{β}({ξ}) = ḟ_{β}(ξ).

2. If A is in T and A is nonterminal then μ_{U_{A}}(f̃_{β}) = μ(f̃_{β}(A)).

3. For every A in T, every U in U_{A}, and every finite Γ ⊆ ω_{1}

∑_{B∈U} ∏_{β∈Γ} f̃_{β}(B) ≥ ∏_{β∈Γ} f̃_{β}(A).

Proof. This is simply a recursion carried out on the rank of T, applying the following special case of Theorem 4 of [8]:

Theorem. Suppose that R is a measure algebra whose character is everywhere greater than ω_{1}, and U is a tree-like ultrafilter on a countable set S. If ḟ_{β} : S → R is indexed by ω_{1} then there is a sequence c_{β} indexed by ω_{1} satisfying the following conditions:

1. μ_{U}(ḟ_{β}) = μ(c_{β}).

2. For every U in U and every finite Γ ⊆ ω_{1}

∑_{α∈U} ∏_{β∈Γ} ḟ_{β}(α) ≥ ∏_{β∈Γ} c_{β}.

Theorem 3.3. Suppose that V models MA _{ℵ_{1}} and {ṙ_{ξ}}_{ξ<κ} is a reals which random over V. In V[ṙ_{ξ} : ξ < κ] the partition relation ω_{1} → (ω_{1}, (α : α))^{2} holds for all α < ω_{1}.

Proof. Let α < ω_{1} be given and assume without loss of generality that α is indecomposable. Suppose that Ġ is a name for a graph on ω_{1}. By Theorem 3.1 either Ġ is forced to be countably chromatic or else there are sets A < B ⊆ ω_{1} of ordertypes α and ω_{1} respectively and ε > 0 such that for every α in A and β in B

μ([[{α, β} ∈ Ġ]]) ≥ ε.

Since the first case gives us the desired conclusion it may be assumed that we are in the second case.

Let (R, μ) be the measure algebra for introducing the reals {ṙ_{ξ} : ξ < κ}. Fix a measure algebra (S, μ) which contains R and has character everywhere greater then ℵ_{1}. Let T be a tree-like ultrafilter on A and set ḟ_{β}(α) = [[{α, β} ∈ Ġ]] for α ∈ A and β in B. Applying Lemma 3.2 fix a lifting f̃_{β} : T → S satisfying the conclusion of the lemma. Define Ṡ_{β} by

[[Ǎ ∈ Ṡ_{β}]] = f̃_{β}(A)

and Λ̇ by

[[β ∈ Λ̇]] = f̃_{β}(root(T)).

It is easy to verify that Ǔ ∪ {Ṡ_{β} : β ∈ Λ} generates a tree-like filter Ũ on T. Let c ∈ R^{+} force that Λ is uncountable. In V^{S} fix a c.c.c. partial order (P, ≤) which forces MA_{ℵ_{1}}. Applying Theorem 2.4 in the extension V^{S∗P} to {πṠ_{β} : β ∈ Λ̇}, it is possible to find sets Ȧ_{0} ⊆ Ǎ and Ḃ_{0} ⊆ Λ̇ such that otp(Ȧ_{0}) = otp(Ḃ_{0}) = α and Ȧ_{0} × Ḃ_{0} ⊆ Ġ. Now applying Theorem 2.5, the desired homogeneous set can be pulled back to V^{R}.

4. Questions

It might initially seem that there is no “reasonable” positive partition relation which lies between ω_{1} → (ω_{1}, (α : α))^{2} and ω_{1} → (ω_{1}, (α : ω_{1}))^{2}. This, however, is not the case. Let (α : β : γ) denote the class of graphs of the form (A × B) ∪ (B × C) ∪ (A × C) where A < B < C and otp(A) = α, otp(B) = β, and otp(C) = γ. It is clear that ω_{1} → (ω_{1}, (α : ω_{1}))^{2} implies that ω_{1} → (ω_{1}, (α : α : α))^{2} which in turn implies that ω_{1} → (ω_{1}, (α : α))^{2}. This leads us to the following:

Question 1. Does ω_{1} → (ω_{1}, (α : α : α))^{2} hold for any/all α ∈ [ω, ω_{1}) in an extension of a model of MA _{ℵ_{1}} by an arbitrary number of random reals?

Being even more ambitious, it is also reasonable to ask the following:

Question 2. Can ω_{1} → (ω_{1}, α)^{2} ever hold for all α < ω_{1} after adding uncountably many random reals?

It should be remarked here that it is unknown whether MA_{ℵ_{1}} implies even ω_{1} → (ω_{1}, ω^{2} + 2)^{2}. Therefore it is more natural to ask the later question under the assumption of PFA.

References

[1] J. H. Barnett. Effect of a Random Real on κ → (κ, (α : ω_{1}))^{2}. Periodica Mathematica Hungarica 30 1 (1995), pages 27-36.

[2] J. H. Barnett. Random Reals and the Relation ω_{1} → (ω_{1}, (α : n))^{2}. Periodica Mathematica Hungarica 30 3 (1995), pages 171-176.

[3] J. Baumgartner, A. Hajnal. A proof (involving Martin’s Axiom) of a partition relation. Fund. Math. 78 (1973), pages 193-203.

[4] P. Erdös, A. Hajnal, A. Maté, R. Rado. Combinatorial Set Theory: Partition Relations For Cardinals North-Holland, Amsterdam 1984.

[5] D. H. Fremlin. Measure Algebras. In Handbook of Boolean Algebras J. D. Monk, ed. North-Holland, Amsterdam 1989.

[6] R. Laver. Partition Relations For Uncountable Cardinals ≤ 2^{ℵ_{0}}. Volume II in Finite and Infinite Sets, A. Hajnal, R. Rado, Vera T. Sós eds. North-Holland pages 1029-1043.

[7] R. Laver. Random Reals and Souslin Trees Proc. Amer. Math. Soc. 100 (1987) pages 531-534.

[8] S. Todorčević. Random Set Mappings and Separability of Compacta Topology and its Applications 74 (1996) pages 265-274.

[9] S. Todorčević. Partition Problems in Topology, AMS (1989) pages 265-274.

Boise State University, Boise, Idaho 83725

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