Uncountable Random Graphs

Justin Tatch Moore April 8, 1999

Definitions

Definition. A measure algebra is a complete Boolean algebra R together with a measure μ : R → [0, 1]:

1. μ(a) = 0 iff a = 0,

2. μ(1) = 1, and

3. μ(∑_{n=0}^{∞} a_{n}) = ∑_{n=0}^{∞} μ(a_{n}) whenever a_{i} · a_{j} = 0 for all i ≠ j.

Definition. If (R, μ) is a measure algebra and V is a set, then a random graph Ġ is a map Ġ : [V]^{2} → R ([V]^{2} is the set of all ordered pairs of members of V).

Unless otherwise stated, (R, μ) will always represent an arbitrary measure algebra.

History and Motivations

The interest, in this area of combinatorics, is to prove Ramsey theoretic statements for random graphs from the assumption of Ramsey theoretic axioms such as MA_{κ}. This can be interpreted as proving that certain consequences of MA_{κ} also hold in forcing extensions of models of MA_{κ} by measure algebras. The R-names for the relevant objects are often either random graphs or similar objects.

This is the best that can be hoped for since axioms such as the Continuum Hypothesis and ♢ can be used to prove rather strong negative combinatorial statements such as ω_{1} ↛ (ω_{1}, (ω : 2))^{2} and the existence of Souslin trees.

Definitions And Notation

Partition Calculus:

Definition. If κ, α, β are order types then κ → (α, β)^{2} stands for “For every G ⊆ [κ]^{2} either there is a set A ⊆ κ of order type α such that [A]^{2} ∩ G is empty or else there is a B ⊆ κ of order type β such that [B]^{2} ⊆ G.”

There are many variations on this theme. For instance if (ξ : η) were written in place of β then the second option would read “there are A, B ⊆ κ of ordertypes ξ and η respectively such that sup A < min B and A × B ⊆ G.”

Definition. A tree (T, <) is a partially ordered set such that for every t in T, < well orders the set {s ∈ T : s < t}. The height of an element t of T is the ordertype of {s ∈ T : s < t}. The collection of all elements of a tree T of a fixed height α is called the α^{th} level of T.

A κ tree is a tree whose elements have height less than κ and such that every level has size strictly less than κ. If a κ tree has no cofinal branch then it is an Aronszajn tree. If κ is not specified then it is ω_{1} by default.

Theorem 1 (Laver). If V models MA_{κ} then in V^{R} every κ tree either has an uncountable branch or else can be decomposed into countably many antichains.

This was generalized to the following result.

Theorem 2 (Todorcevic). If MA_{κ} holds in V then SM_{κ} holds in V^{R}: If F : κ → [κ]^{ω} satisfies α ∉ F (α) for all α < κ then either

1. there exist X_{n} ⊆ κ (n ∈ ℕ) with ⋃_{n=1}^{∞} X_{n} = κ and X_{n} ∩ (∪F′′X_{n}) = ∅ (n ∈ ℕ) or else

2. there is an uncountable A ⊆ κ such that for every finite G ⊆ A, {β < κ : G ⊆ F (β)} is uncountable.

Contrasting the Cohen Model:

(R, μ) is an arbitrary measure algebra and C is the countable Cohen algebra.

Theorem 3 (Shelah). In V^{C} there is a Souslin tree (an Aronszajn tree with no uncountable antichain).

Theorem 4 (Laver). [MA_{ℵ_{1}}] In V^{R} all Aronszajn trees are special (can be decomposed into countably many antichains).

Theorem 5 (Todorcevic). In V^{C} the negative partition relation ω_{1} ↛ (ω_{1}, (ω : 2))^{2} holds.

Theorem 6 (JTM). [MA_{ℵ_{1}}] In V^{R} the positive partition relation ω_{1} → (ω_{1}, (α : α))^{2} holds for all α < ω_{1}.

Theorem 7 (Todorcevic). In V^{C} there is a c.c.c. destructible (ω_{1}, ω_{1}^{∗})-gap.

New Motivations:

Often metamathematical facts about the combinatorics of V^{R} can be translated into mathematical facts about “random” objects, such as graphs and set mappings, which are of independent interest (this is less the case for the Cohen algebra).

Theorem 8 (Todorcevic). [MA_{κ}] If Ḟ : κ × κ → R is such that for every β < κ the collection {α < κ : Ḟ(α, β) ≠ 0} is countable then either

1. there are Ẋ_{n} : κ → R (n ∈ ℕ) such that for all α ≠ β < κ and m < ω

∞ ; ∑ ; n=1 Ẋ_{n}(α) = 1,

Ḟ(β, α) · Ẋ_{m}(α) · Ẋ_{n}(β) = 0

2. or else there is an Ȧ : κ → R with uncountable support such that for every finite G ⊆ κ and every co-countable C ⊆ κ

_{α∈C}^{∑} _{β∈G}^{∏} Ḟ(α, β) ≥ _{β∈G}^{∏} Ȧ(β).

This formulation answered problem DV on D. Fremlin’s list of problems.

Tools

Now it is perhaps worth while to mention some of the tools involved in the previous results.

Theorem 9. Suppose (S, μ) is a measure algebra, R complete atomless subalgebras of S, and A is a subset of S such that the character of R is everywhere greater than the cardinality of A. There is a measure preserving map h : A → R such that h(a) ≤ b whenever a is in A, b ∈ R and a ≤ b.

This is frequently useful when (S, μ) is the completion of an ultrapower of R and A is a list of (equivalence classes of) R-names for subsets of I.

The above theorem was essentially proven by S. Todorcevic when he demonstrated the following (which is a corollary of the above).

Theorem 10 (Todorcevic). Suppose I and J are sets, U is an ultrafilter on I and (R, μ) is a measure algebra whose character is everywhere greater than #(I ×J). If [f_{ξ}] (ξ ∈ J) is a sequence of elements of (R^{I}/U, μ_{U}) then there is a sequence c_{ξ} (ξ ∈ J) of elements of R such that

1. μ(c_{ξ}) = μ_{U}([f_{ξ}]) for all ξ ∈ J and

2. For every finite J_{0} ⊆ J

_{U∈U}^{∏} _{i∈U}^{∑} _{ξ∈J_{0}}^{∏} f_{ξ}(i) ≥ _{ξ∈J_{0}}^{∏} c_{ξ}.

The following is closely related to the previous theorem and is often how it is applied.

Theorem 11 (Todorcevic). [MA_{ℵ_{1}}] If U is an ultrafilter on I, Ẋ_{ξ} (ξ < ω_{1}) is a collection of R-names for subsets of I such that for some δ > 0

μ(Ẋ_{ξ}(i)) ≥ δ

for all ξ < ω_{1} and i in I then there is a name Ũ for a filter and a condition c in R^{+} such that c forces Ũ contains U and Ẋ_{ξ} for uncountably many ξ < ω_{1}.

It should be noted that this theorem applies to all ultrafilters U in V even though all applications to date require only that this theorem is true for some uniform (or nonprinciple) ultrafilter U.

The Role Of Martin’s Axiom:

Theorem 12 (Laver). [MA_{ℵ_{1}}] If Ġ : [ω_{1}]^{2} → R is a random graph on ω_{1} then either

1. there exist Ẋ_{n} : ω_{1} → R (n ∈ ℕ) such that for all α < β < κ and m < ω

∞ ; ∑ ; n=1 Ẋ_{n}(α) = 1,

Ġ(α, β) · Ẋ_{m}(α) · Ẋ_{m}(β) = 0

2. there exists a δ > 0 and a sequence {F_{ξ} : ξ < ω_{1}} of disjoint finite subsets of ω_{1} such that for every ξ ≠ η < ω_{1}

μ(∑{Ġ(α, β) : (α, β) ∈ F_{ξ} × F_{η}}) ≥ δ.

Forcing and Absoluteness:

Theorem 13. If G is a graph a vertex set κ and there is a forcing notion which introduces a homogeneous subset of G of the form [A]^{2} or A × B for countable A and B then such a homogeneous set already exists for G.

Of course the exact form of the homogeneous set is not crucial. What is important is the countability condition and some assurance that the homogeneous set is of some “reasonable” form.

Techniques

The best way to demonstrate the power of tools is to put them to use. I will now do this by demonstrating how to prove using MA_{ℵ_{1}} that ω_{1} → (ω_{1}, (ω : α))^{2} holds in V^{R}.

To this end, let Ġ : [ω_{1}]^{2} → R be a random graph on ω_{1} and α < ω_{1} be given. By Theorem 12, if Ġ is not forced to be countably chromatic then there is a sequence {F_{ξ} : ξ < ω_{1}} of disjoint finite sets and a δ > 0 such that for every ξ ≠ η < ω_{1} there are ξ̄ in F_{ξ} and η̄ in F_{η} such that μ(Ġ(ξ̄, η̄)) ≥ δ.

By working a little, it is possible to find a pair A, B ⊆ ω_{1} such that

1. A is infinite,

2. B is uncountable,

3. sup A < min B, and

4. for all ξ ∈ A and η ∈ B μ(Ġ(ξ, η)) ≥ δ.

For each η in B, define K̇_{η} to be a R-name for a subset of A such that

[[ξ ∈ K̇_{η}]]= Ġ(ξ, η).

Let U be an arbitrary nonprinciple ultrafilter on A.

By Theorem 11 it is possible to pick c ∈ R^{+} , Ũ, and Ḃ^{∗} such that c forces that Ḃ^{∗} an uncountable subset of B and Ũ is a filter on A extending U an containing K̇_{η} for every η in Ḃ^{∗}.

In V^{R_{c}}, let Ṗ be a name for a partial order which forces an infinite set Ȧ_{1} ⊆ A such that for every β in Ḃ^{∗} all but finitely many members of Ȧ^{∗} are contained in K̇_{β} (R_{c} denotes the restriction of R to the positive element c).

In V^{R_{c}∗P} it is possible to find a pair Ȧ_{α}, Ḃ_{α} such that Ȧ_{α} is infinite and contained in K̇_{η} for every η ∈ Ḃ_{α} and the order type of Ḃ_{α} is α. This means exactly that Ȧ_{α} × Ḃ_{α} ⊆ Ġ. By absoluteness such a homogeneous set is forced by c to exist in V^{R}.

Applications to Topology ^{∗}

The inequality 2^{ℵ_{0}} < 2^{ℵ_{1}} turns out to be of great importance to topologists who study questions which involve normality. It is quite often useful to know when consequences of MA_{ℵ_{1}} are consistent with this hypothesis. Since measure algebras such as the Haar algebra of character ℶ_{ω_{1}} force the inequality 2^{ℵ_{0}} < 2^{ℵ_{1}}, the theory of uncountable random graphs has applications in the study of normality in topological spaces. Random graphs also seem to be useful in answering questions of the form “what impact do certain assertions about topological spaces have on the size of the continuum.”

∗All spaces are assumed to be T_{3}

Souslin Trees and Lines:

Question (Souslin,1920). If L is a linearly orderable connected compactum which satisfies the countable chain condition, must L be homeomorphic to the unit interval [0, 1]?

It is well known among set theoretic topologists that the answer to this question is undecidable and is in fact equivalent to the nonexistence of Souslin trees (MA_{ℵ_{1}} implies that such objects do not exist). Laver’s result shows that the answer to the above question is yes in V^{R} if V models MA_{ℵ_{1}}.

S and L Spaces: The connection between the properties of

1. being hereditarily separable,

2. being hereditarily Lindelöf, and

3. not containing an uncountable discrete subspace

turns out to be quite closely related graphs on ω_{1}.

Definition. X is an S space if it is hereditarily Separable but not hereditarily Lindelöf. X is an L space if it is hereditarily Lindelöf (every open cover has a countable subcover) but not hereditarily separable.

Definition. A topology τ on ω_{1} is said to be left separated if all initial intervals are closed in τ. Similarly τ is right separated if all final intervals are closed in τ.

Canonical examples of S (L) spaces are topologies on ω_{1} which are right (left) separated but contain no uncountable left (right) separated subspaces. It is well known that spaces of this type form a basis for all S and L spaces (that is to say that all S and L spaces contain a subspace of this type).

Compact L Spaces:

Souslin Lines are in fact canonical examples of compact L spaces. SM_{ℵ_{1}} was invented to, among other things, destroy compact L spaces and allow the continuum to have arbitrary size greater than ℵ_{1} of uncountable cofinality.

Theorem 14 (Todorcevic). [SM_{ℵ_{1}}] If X is a compact topological space and X contains an L space then X also contains an uncountable discrete subset.

Conjecture (Todorcevic). If V is a model of MA_{ℵ_{1}} then there are no compact S spaces in V^{R}.

S Spaces With Additional Properties:

It is consistent with ZFC that no S spaces exist. This, however, is a rather strong assertion. A general theme in topology is to ask what axioms place what restrictions on the properties of S spaces. One example of such a property is that of being extremely disconnected (i.e. the closure of every open set is open).

Theorem 15 (Szymanski). [MA_{ℵ_{1}}] There are no extremely disconnected S spaces.

Szymanski did not use full MA_{ℵ_{1}} but rather the following combinatorial statement known as Wage’s Lemma which was shown to be a consequence of MA_{ℵ_{1}} by M. Wage.

WL. If A is a collection of countable subsets of ω_{1} of size ω_{1} then there is an uncountable X ⊆ ω_{1} which has finite intersection with every element of A.

There is also a random analog.

Theorem 16 (JTM). If V models MA_{ℵ_{1}} then V^{R} models Wage’s Lemma.

Problems and Conjectures

Compact S Spaces:

Question (Todorcevic). Is there a compact S space in V^{R}?

This originated from a much older problem.

Question (Katetov). Is it consistent that if X is a compact space and every subspace of X^{2} is normal then X is metrizable?

Katetov showed that if X is compact and every subspace of X^{3} is normal then X is metrizable, making this a natural question to ask. If V is a model of MA_{ℵ_{1}} then the only possible counterexample to Katetov’s problem in V^{R} is a space X whose square is a compact S space (Nyikos, Gruenhage, Todorcevic).

Partition Calculus:

Question. If MA_{ℵ_{1}} holds in V, must

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

hold in V^{R} for every α < ω_{1}?

A positive answer is known for this question if (R, μ) is a separable measure algebra. In fact Barnett has shown that if (R, μ) is separable and V models MA_{ℵ_{1}} then V^{R} models

ω_{1} → (ω_{1}, (α : ω_{1}))^{2}.

Conjecture (Baumgartner, Hajnal). If MA_{ℵ_{1}} holds in V then V^{R} models ω_{1} → (ω_{1}, α)^{2} for all α < ω_{1}.

This is open even for the trivial measure algebra. It is probably more reasonable to assume PFA in the ground model (since, unlike MA_{ℵ_{1}}, PFA is known to imply ω_{1} → (ω_{1}, α)^{2} for all α < ω_{1}).