On Silver’s Remark on the Ramseyness of Σ_{1}^{1} and Σ_{2}^{1}

{岩田竜之 \atop 学籍番号 31960105-6}

Abstract

Our topic in this paper is subsets of reals (⊆ ^{ω}2) and their Ramseyness.

Erdös and Rado [1, Example 1, p. 434] showed the existence of non-Ramsey subsets using the Axiom of Choice (AC). Mathias [4] showed that the use of AC is essential. It is natural to ask how complex subsets must be to be Ramsey.

ω2 is a complete Polish space. Therefore we can develop descriptive set theory and can consider projective and analytical hierarchies.

Galvin and Prikry [3] showed that every Borel subset is Ramsey.

J. Silver [2] proved that every Σ_{1}^{1} subset of reals is Ramsey and that if there is a measurable cardinal then every Σ_{2}^{1} subset of reals is also Ramsey. In his proof Silver used the forcing notion making MA(ω_{1}). He remarked that instead of this forcing we can use a less complicated forcing notion.

In this paper we give the definitions of these concepts and a more detailed proof of Silver’s remark.

In the case of Σ_{1}^{1} our theorem is the same as Silver’s result but our proof is a little different. Next we show that every provably Δ_{2}^{1} subset is completely Ramsey by a similar proof. Finally, in the case of Σ_{2}^{1}, the simplicity of our forcing notion enables us to find the weakest cardinality hypothesis. The last two results extend Silver’s results. Throughout these three theorems we do not use AC, so they are completely within ZF.

1 Notation and Definition

ZF denotes Zermelo-Fraenkel set theory without the Axiom of Choice. The Axiom of Choice is referred to as AC. ZFC means ZF+AC. We assume ZF for the ambient theory if not specified otherwise.

ω is the set of natural numbers and is the least infinite ordinal. ω_{1} is the set of at most countable ordinals and is the least uncountable ordinal. 0 denotes the empty set.

For sets X and Y, P(X) is the power set of X and ^{Y} X is the set of functions from Y into X. When Y is a natural number n, ^{n}X is identified with n-tuples of elements from X. If X is a set of ordinals, [X]^{ω} denotes the set of subsets of X whose order type is ω. Similarly, [X]^{<ω} denotes the set of subsets of X whose order type is finite. For example, P(ω) is the disjoint union of [ω]^{<ω} and [ω]^{ω}.

ω2 = ^{ω}{0, 1} is identified with P(ω) through the characteristic function. Inclusion symbols ⊆’s are used in this sense. We will study a property of subsets of reals (X ⊆ ^{ω}2).

ω2 can be regarded as the topological product space of ω-many discrete spaces {0, 1}. Open sets in this topology are generated from {x|n ∈ x}_{n∈ω} and {x|n ∉ x}_{n∈ω} by finite intersection and arbitrary union. Throughout this paper, we fix this topology of ^{ω}2.

As our topology of ^{ω}2 makes a perfect Polish space we can develop descriptive set theory. First we define the analytical hierarchy. For this we consider a second-order arithmetic

structure

A(a) = ⟨ω,^{ω}2, ∈, +, ×, exp, <, 0, 1, a⟩,

where a ∈ ^{ω}2 is thought of as an interpretation of a predicate over ω, exp(x, y) is x^{y} and second-order equality “=^{2}” is not allowed. Quantifiers bounded in ω are abbreviated to quantifiers with a superscript “0”, and in ^{ω}2 with a superscript “1”. For example, “∃^{1}y” means “∃y ∈ ^{ω}2”.

Definable subsets of ^{r}ω × ^{k}(^{ω}2) in this structure are classified by the difficulty of the formula defining them.

A ⊆ ^{r}ω ×^{k}(^{ω}2) is Δ_{0}^{0} in a iff A is definable in A(a) by a formula whose only quantifiers are bounded, i.e., (∃^{0}n < t) or (∀^{0}n < t), where t is a term representing numbers.

A ⊆ ^{r}ω ×^{k}(^{ω}2) is arithmetical in a iff A is definable in A(a) by a formula whose only quantifiers are all numerical, i.e., ∃^{0} or ∀^{0}. To a formula defining arithmetical relation, replacement and contraction of quantifiers are applied based on the following equivalences:

(∀^{0}p < q)∃^{0}mR(p, q, m, w) iff ∃^{0}m(∀^{0}p < q)R(p, q, (m)_{p}, w)
∃^{0}m∃^{0}pR(p, m, w) iff ∃^{0}mR((m)_{0}, (m)_{1}, w) ,

where (m)_{i} denotes the i-th element of a finite sequence of natural numbers which is coded by m in the usual Δ_{0}^{0} manner. Through these transformations every arithmetical relation A ⊆ ^{r}ω ×^{k}(^{ω}2) is either of the following:

A ∈ Σ_{n}^{0}(a) iff ∀w (w ∈ A ↔ ∃^{0}m_{1}∀^{0}m_{2} … Qm_{n}R(w, m_{1}, m_{2},…, m_{n})) ,

A ∈ Π_{n}^{0}(a) iff ∀w (w ∈ A ↔ ∀^{0}m_{1}∃^{0}m_{2} … Qm_{n}R(w, m_{1}, m_{2},…, m_{n}))

for some R ⊆ ^{r+n}ω ×^{k}(^{ω}2) Δ_{0}^{0} in a, where quantifiers bounding m_{1},…, m_{n} are alternating between ∃^{0} and ∀^{0}. Δ_{n}^{0}(a) denotes Σ_{n}^{0}(a) ∩ Π_{n}^{0}(a).

It can be easily shown that

Σ_{n}^{0}(a) ∪ Π_{n}^{0}(a) ⊂ Δ_{n+1}^{0}(a) = Σ_{n+1}^{0}(a) ∩ Π_{n+1}^{0}(a) , for n > 0.

We call this classification the arithmetical hierarchy.

We can check that A is recursive in a iff A ∈ Σ_{1}^{0}(a) ∩ Π_{1}^{0}(a) = Δ_{1}^{0}(a).

A ⊆ ^{r}ω × ^{k}(^{ω}2) is analytical in a iff A is definable in A(a) by a formula without any restriction of quantifiers. Through some transformations, every analytical relation A ⊆ ^{r}ω × ^{k}(^{ω}2) is either of the following: (These transformations are not easy since we cannot use even the countable axiom of choice.)

A ∈ Σ_{n}^{1}(a) iff ∀w (w ∈ A ↔ ∃^{1}x_{1}∀^{1}x_{2} … Qx_{n}R(w, x_{1}, x_{2},…, x_{n})) ,
A ∈ Π_{n}^{1}(a) iff ∀w (w ∈ A ↔ ∀^{1}x_{1}∃^{1}x_{2} … Qx_{n}R(w, x_{1}, x_{2},…, x_{n}))

for some R ⊆ ^{r}ω × ^{k+n}(^{ω}2) arithmetical in a, where quantifiers bounding x_{1},…, x_{n} are alternating between ∃^{1} and ∀^{1}. Δ_{n}^{1}(a) denotes Σ_{n}^{1}(a) ∩ Π_{n}^{1}(a).

It can be easily shown that

Σ_{n}^{1}(a) ∪ Π_{n}^{1}(a) ⊂ Δ_{n+1}^{1}(a) = Σ_{n+1}^{1}(a) ∩ Π_{n+1}^{1}(a) , for n > 0.

We call this classification the analytical hierarchy.

Throughout these arithmetical and analytical notations, if a = 0 then “(0)” is suppressed. Next we define the projective hierarchy. While this is usually defined using the open sets

of the topology of the space and the projection, here we adopt the following properties as their definitions. For n > 0 and A ⊆ ^{r}ω ×^{k}(^{ω}2),

A ∈ Σ_{n}^{1} iff A is Σ_{n}^{1}(a) for some a ∈ ^{ω}2 ,
A ∈ Π_{n}^{1} iff A is Π_{n}^{1}(a) for some a ∈ ^{ω}2 ,
A ∈ Δ_{n}^{1} iff A is Δ_{n}^{1}(a) for some a ∈ ^{ω}2 .

It is easily shown that

Σ_{n}^{1} ∪ Π_{n}^{1} ⊂ Δ_{n+1}^{1} = Σ_{n+1}^{1} ∩ Π_{n+1}^{1} , for n > 0.

We present the following proposition:

Proposition 1 For a ∈ ^{ω}2, n > 0, R ⊆ ^{r}ω × ^{k}(^{ω}2) is Σ_{n}^{0}(a) iff there is a Σ_{n}^{0} S ⊆ rω ×^{k+1}(^{ω}2) such that ∀w(R(w) ↔ S(w, a)). Analogous statements hold for Π_{n}^{0}, Σ_{n}^{1}, and Π_{n}^{1}.

Note that the analogous statements for Δ_{n}^{0} and Δ_{n}^{1} do not hold.

Now we have defined hierarchies of subsets of reals in terms of descriptive set theory. From here we define a property of subsets of reals, Ramseyness. If A is a subset of ^{ω}2,

S ∈ [ω]^{ω} is said to be homogeneous for A when [S]^{ω} ⊆ A or [S]^{ω} ∩ A = 0. When A has some homogeneous set S, A is said to be Ramsey. A is completely Ramsey iff f^{−1}(A) is Ramsey for every continuous function f : ^{ω}2 → ^{ω}2. Obviously if A is completely Ramsey then A is Ramsey, since the identity function is continuous! This complete Ramseyness is by Galvin-Prikry [3].

We freely use the technical terms and notations of forcing. In particular, for any p.o. set P and any condition p, q ∈ P and formula φ,

p ||−_{P} φ iff p forces φ in a forcing by P ,
p ||_{P} φ iff p ||−_{P} φ or p ||−_{P} ¬φ ,
p ≤_{P} q iff p extends or is a stronger condition than q .

The subscripts P are suppressed when clear from the context.

Next we define the Mathias forcing and closed intervals. The Mathias forcing p.o. set is

P_{M} =^{def} {⟨s, S⟩ ∈ [ω]^{<ω} × [ω]^{ω} | max s < min S}

ordered by:

⟨s, S⟩ ≤_{P_{M}} ⟨t, T ⟩ ⇔^{def} t ⊆ s ∧ S ∪ (s \ t) ⊆ T .

For ⟨s, S⟩ ∈ P_{M}, the corresponding closed interval is

[s, S] =^{def} {X ∈ [ω]^{ω} | s ⊆ X ⊆ s ∪ S} .

Actually [s, S] is closed in [ω]^{ω} in the sense of relative topology. For ⟨s, S⟩ ∈ P_{M} and A ⊆ ^{ω}2 we borrow terms of forcing, which we define as follows:

⟨s, S⟩ forces A (⟨s, S⟩ ||−^{R} A) ⇔^{def} [s, S] ⊆ A ,
⟨s, S⟩ decides A (⟨s, S⟩ ||^{R} A) ⇔^{def} ⟨s, S⟩ ||−^{R} A ∨ ⟨s, S⟩ ||−^{R} (^{ω}2 \ A) .

The superscripts R are from “in the real world” and these symbols must be distinguished from the ordinary forcing notions ||− and || . It is easy to check that

A is Ramsey iff ∃S ∈ [ω]^{ω}(⟨0, S⟩ ||^{R} A)

and that if A is completely Ramsey then

∀⟨s, S⟩ ∈ P_{M}∃⟨s, S′⟩ ∈ P_{M} [⟨s, S′⟩ ≤ ⟨s, S⟩ ∧ ⟨s, S′⟩ ||^{R} A] .

For the latter, note that if e(n) denotes the n-th least member of S then f : X ↦ s∪e“X is continuous. In fact, this latter property is the definition of complete Ramseyness adopted by Silver [2]. Our definition is strictly stronger than this property in the following sense: Suppose there is a non-Ramsey set, say A. Define a continuous injection f : ^{ω}2 → ^{ω}2 by

f(X) = ⋃_{n∈X}{2n, 2n + 1} .

Then f“A satisfies the above property, as ⟨s, S ∩ {2n}_{n∈ω}⟩ or ⟨s, S ∩ {2n + 1}_{n∈ω}⟩ decides (^{ω}2\f“A). On the other hand, this is not completely Ramsey in our sense, as f^{−1}(f“A) = A is not Ramsey.

Under AC, we can prove the existence of non-Ramsey sets.

Proposition 2 If AC holds, there exists a non-Ramsey set. Moreover if ^{ω}2 ⊆ L, then this set can be taken to be Δ_{2}^{1}.

Proof of Proposition: If AC holds, there is a well-ordering ≺ of ^{ω}2. Here we define

A =^{def} {X ∈ [ω]^{ω} | ∀^{1}Y (Y ∈ [X]^{ω} → Y ⊀ X)} .

There is no homogeneous Z ∈ [ω]^{ω} for A: First the ≺-least element of [Z]^{ω} is always in A, thus [Z]^{ω} ∩ A ≠ 0. But if [Z]^{ω} were to be a subset of A, the existence of a sequence of distinct infinite sets

Z_{0} ⊂ Z_{1} ⊂ ⋯ ⊂ Z

would give us a descending chain of ≺, which contradicts the well-orderedness of ≺.

Next if ^{ω}2 ⊆ L, the above well-ordering is taken to be the L-order <_{L}. This order is Δ_{2}^{1}. Thus the above definition of A tells us that A is Π_{2}^{1}. Moreover using

IS_{L}(x, y) ↔ {(x)_{i} | i ∈ ω} = {z ∈ ^{ω}2 | z <_{L} y} ,

which is Σ_{2}^{1} (see [5] for more), A is reformulated as

A = {X ∈ [ω]^{ω} | ∃^{1}Y [IS_{L}(Y, X) ∧ ∀^{0}i((Y)_{i} ∉ [X]^{ω})]} ,

which is Σ_{2}^{1}. □

In this proposition, the use of AC is essential. Mathias [4] showed that the following theorem holds.

Proposition 3 If ZF+“there is an inaccessible cardinal” is consistent, then ZF+“all subsets of reals are Ramsey” is consistent.

On the other hand we can prove the Ramseyness of sets in the projective low hierarchy. Silver [2] showed that 1. Every Σ_{1}^{1} subset of ^{ω}2 is Ramsey,

2. If there is a measurable cardinal, then every Σ_{2}^{1} subset of ^{ω}2 is Ramsey.

In his paper he suggested the possibility of the use of a less complicated forcing notion than his, and his proof used freely but not essentially the axiom of choice.

Our aim in this paper is showing in ZF that:

1. Every Σ_{1}^{1} subset of ^{ω}2 is completely Ramsey,

2. Every provably Δ_{2}^{1} subset of ^{ω}2 is completely Ramsey,

3. For a ⊆ ω, if ω_{1}^{L[a]} < ω_{1} then every Σ_{2}^{1}(a) subset of ^{ω}2 is Ramsey.

The first result is exactly the same as Silver’s except that the proof does not require AC.

2 Preliminary for Descriptive Set Theory

We give here some properties in descriptive set theory needed in the following sections.

Arithmetical and analytical hierarchies for Baire space ^{ω}ω are defined similarly to those of ^{ω}2 by the structure

A′(a) = ⟨ω,^{ω}ω, ap, +, ×, exp, <, 0, 1, a⟩.

First we mention a correlation between ^{ω}ω and ^{ω}2. These spaces are complete Polish spaces, so they are known to be Borel isomorphic in a general context. But in fact this isomorphism can be given explicitly.

Lemma 1 There is an isomorphism π : ^{ω}ω → ^{ω}2 such that n ∈ π(x) and π^{−1}(y)(m) = n are both Δ_{3}^{0} in ^{ω}ω and ^{ω}2 respectively.

This isomorphism can be made from two injections

f : ^{ω}ω ∋ x ↦ 0^{x(0)}1^{x(1)}0^{x(2)}1^{x(3)} ⋯ ∈ ^{ω}2 , and
g : ^{ω}2 ∋ y ↦ y ∈ ^{ω}ω

by using Schroeder-Bernstein’s method. It is long but straightforward to check that this isomorphism is written by a bi-Δ_{3}^{0} relation.

The following lemmata are frequently used in the proof of our main theorems. These are proved as usual in the effective context of ^{ω}ω, and are derived in our space ^{ω}2 through the above isomorphism. They do not require AC. Refer to [5] for proofs.

Lemma 2 If A is Δ_{1}^{1} then A is Borel.

Lemma 3 There is a theorem σ_{1} of ZF such that for any transitive (set or class) ∈-model M of σ_{1}, every Σ_{1}^{1} relation is absolute for M.

Lemma 4 (Shoenfield) There is a theorem σ_{2} of ZF such that for any transitive (set or class) ∈-models M of σ_{2} with ω_{1}^{V} ⊆ M, every Σ_{2}^{1} relation is absolute for M.

Here the class M versions of these theorems are theorem schemata. But even in this case, σ_{1} or σ_{2} is a single theorem, so models have only to satisfy a fragment of ZF in each case.

The proofs of these might seem to use the regularity of ω_{1}. But, in fact, we can rewrite the proofs using only the lack of mapping from countable objects onto ω_{1}.

Lemma 5 Every Σ_{1}^{1} set is the canonical union of ℵ_{1} Borel increasing sets. More formally, for every Σ_{1}^{1} formula φ(w) with only free variables w ∈ ^{k}(^{ω}2), there are Π_{1}^{1} formulae θ_{φ}(w, z) and χ_{φ}(w, z) such that

1. If z codes some countable ordinal, then ∀^{1}w (θ_{φ}(w, z) ↔ ¬χ_{φ}(w, z)).

2. If z does not code any countable ordinal, then ∀^{1}w (¬θ_{φ}(w, z) ∧ ¬χ_{φ}(w, z)).

3. If z_{α}, z_{β} codes α, β and α ≤ β, then ∀^{1}w (θ_{φ}(w, z_{α}) → θ_{φ}(w, z_{β})).

4. φ(w) iff ∃^{1}zθ_{φ}(w, z).

This lemma is an effective version of the usual ℵ_{1}-Borel lemma, and in fact is a single theorem of ZF through the Gödelization of formulae. Using this lemma, we can split Σ_{1}^{1} set into ℵ_{1} Borel sets: Let Σ_{1}^{1}(a) set

A = {x ∈ ^{ω}2 | φ(x, a)} .

By taking α = β in condition 3, we can define for α < ω_{1},

A_{α} = {x ∈ ^{ω}2 | for some and any z coding α, θ_{φ}(x, a, z)} .

These sets are Borel by condition 1. By condition 3,

α ≤ β ⟶ A_{α} ⊆ A_{β} .

Finally, by condition 4,

A = ⋃_{α<ω_{1}} A_{α} .

Moreover this splitting lemma holds for Σ_{2}^{1}; Lemma 6 Every Σ_{2}^{1} set is the canonical union of ℵ_{1} Borel increasing sets. More formally, for every Σ_{2}^{1} formula φ(w) with only free variables w ∈ ^{k}(^{ω}2), there are Π_{1}^{1} formulae θ_{φ}(w, z) and χ_{φ}(w, z) such that

1. If z codes some countable ordinal, then ∀^{1}w (θ_{φ}(w, z) ↔ ¬χ_{φ}(w, z)).

2. If z does not code any countable ordinal, then ∀^{1}w (¬θ_{φ}(w, z) ∧ ¬χ_{φ}(w, z)).

3. If z_{α}, z_{β} codes α, β and α ≤ β, then ∀^{1}w (θ_{φ}(w, z_{α}) → θ_{φ}(w, z_{β})).

4. φ(w) iff ∃^{1}zθ_{φ}(w, z).

3 On Σ_{1}^{1} sets

We use the following theorem as a basis. A proof which uses a very weak version of the axiom of choice is found in [3].

Theorem 1 (Galvin-Prikry) (AC) Every Borel set of ^{ω}2 is completely Ramsey.

Now we show the following theorem with a different proof from Silver’s original proof in [2].

Theorem 2 (Silver) Every Σ_{1}^{1} set of ^{ω}2 is completely Ramsey.

Proof : First we have only to show that every Σ_{1}^{1} set of ^{ω}2 is Ramsey. For if A is Σ_{1}^{1} and f : ^{ω}2 → ^{ω}2 is continuous then f^{−1}(A) is Σ_{1}^{1}, too.

Given a Σ_{1}^{1}(a) set A^{V} = {x | φ(x, a)}, we shall show that this A^{V} is Ramsey. The superscript V suggests that this set is defined in V from φ.

Let θ_{φ} and χ_{φ} be as in the splitting lemma (Lemma 5). Then we can define for α < ω_{1},

A_{α}^{V} = {x | for some (any) z coding α, θ_{φ}(x, a, z)} .

And we know A^{V} = ⋃_{α<ω_{1}^{V}} A_{α}^{V}.

Now suppose N is a countable transitive model of a fragment of ZF+AC sufficiently large for this proof with a ∈ N.

We argue in N from here. A^{N} and A_{α}^{N} for α < ω_{1}^{N} are defined from φ, θ_{φ} and a in N, too. N can be assumed to satisfy the splitting lemma, so that A^{N} = ⋃_{α<ω_{1}^{N}} A_{α}^{N} and each A_{α}^{N} is Borel. Moreover N can be assumed to satisfy Theorem 1, so N thinks each A_{α}^{N} is completely Ramsey (here we need that N satisfies at least a weak version of AC).

Claim 2.1 There is F ⊆ [ω]^{ω} such that 1. |F| ≤ ω_{1}^{N} ,

2. E, E′ ∈ F ⟶ E ∩ E′ ∈ F ,

3. |ω \ E| < ω ⟶ E ∈ F,

4. ∀α < ω_{1}∀s ∈ [ω]^{<ω}∃U ∈ F [⟨s, U⟩ ||^{R} A_{α}^{N}] .

Proof of Claim: Fix a sequence ⟨α_{β}, s_{β}⟩_{β<ω_{1}} enumerating ω_{1} × [ω]^{<ω}. Recursively on β we construct a sequence ⟨E_{β}⟩_{β<ω_{1}} such that

1. n < ω, {β_{1},… β_{n}} ⊂ ω_{1} ⟶ |E_{β_{1}} ∩… ∩ E_{β_{n}}| = ω ,

2. β < ω_{1} ⟶ ⟨s_{β}, E_{β}⟩ ||^{R} A_{α_{β}}^{N}.

Assume that we have constructed ⟨E_{η}⟩_{η<β}. As this is countable and satisfies the first condition in the recursion hypothesis, there is X ∈ [ω]^{ω} such that ∀η < β (|X \ E_{η}| < ω). Since A_{α_{β}}^{N} is completely Ramsey, there is E_{β} ∈ [X \ ∪s_{β}]^{ω} such that ⟨s_{β}, E_{β}⟩ ||^{R} A_{α_{β}}^{N}. Here we again need N ⊧ AC. That ⟨E_{η}⟩_{η<β+1} satisfies the above conditions is easily checked. F is generated from the E_{β}’s and cofinite subsets of ω by finite intersections. □

Now we are on the point of defining our key forcing notion.

P_{F} =^{def} {⟨s, U⟩ ∈ P_{M} | U ∈ F}

ordered by ≤_{P_{M}}.

Claim 2.2 P_{F} has the c.c.c.

Proof of Claim: Let ⟨s_{β}, U_{β}⟩_{β<ω_{1}} ⊆ P_{F}. Since |[ω]^{<ω}| = ω, we have β_{0} and β_{1} such that s_{β_{0}} = s_{β_{1}}. Then by condition 2 in Claim 2.1, ⟨s_{β_{0}}, U_{β_{0}} ∩ U_{β_{1}}⟩ ∈ P_{F} and is a common extension of ⟨s_{β_{0}}, U_{β_{0}}⟩ and ⟨s_{β_{1}}, U_{β_{1}}⟩. □

Define

for α < ω_{1}, D_{α} =^{def} {⟨s, U⟩ ∈ P_{F} | ∀t ⊆ s (⟨t, U⟩ ||^{R} A_{α}^{N})} ,
for n < ω, \overline{D_{n}} =^{def} \{⟨s, U⟩ ∈ P_{F} | s ⊈ n\} .

Claim 2.3 Each D_{α} is dense.

Proof of Claim: Fix α < ω_{1} and ⟨s, U⟩ ∈ P_{F}. Enumerate P(s) as {t_{i}}_{i<n} with n < ω. By condition 4 in Claim 2.1, for each i < n, there is U_{i} ∈ F such that ⟨t_{i}, U_{i}⟩ ||^{R} A_{α}^{N}. Using condition 2 in Claim 2.1 n-times, Ũ =^{def} U ∩ ⋂_{i<n} U_{i} is in F. Then ⟨s, U⟩ ≥ ⟨s, Ũ⟩ ∈ D_{α}. □ Claim 2.4 Each \overline{D_{n}} is dense.

Proof of Claim: Fix n < ω and ⟨s, U⟩ ∈ P_{F}. Let m be the least member of U \ n. Then ⟨s, U⟩ ≥ ⟨s ∪ \{m\}, U \ (m + 1)⟩ ∈ \overline{D_{n}}. □

Now we step out from N to the universe V. Since |N| ≤ ω, we have in V a P_{F}-generic G over N. We can make N[G] satisfy arbitrarily large finite fragments of ZFC by means of making the grand model N satisfy some large fragment. And since N ⊧ P_{F} has the c.c.c., ω_{1}^{N} = ω_{1}^{N[G]}.

We argue in N[G] from here. We define from φ, θ_{φ} and a, A^{N[G]} and A_{α}^{N[G]} for α < ω_{1}^{N[G]} in N[G]. Again, we can assume N[G] knows (Lemma 5)

A^{N[G]} = ⋃_{α<ω_{1}^{N[G]}} A_{α}^{N[G]} .

Let X be ⋃\{s | ⟨s, U⟩ ∈ G\}. It is easily checked that X ∈ [ω]^{ω} follows from G ∩ \overline{D_{n}} ≠ 0 for all n. And for all ⟨s, U⟩ ∈ G, X ∈ [s, U].

Claim 2.5 ∀α < ω_{1}^{N[G]} ( A_{α}^{N[G]} ∩ [X]^{ω} is open in [X]^{ω} ).

Proof of Claim: Fix α < ω_{1}^{N[G]} = ω_{1}^{N}, and a real c_{α} ∈ N coding α. As D_{α} is dense, there is ⟨s, U⟩ ∈ G ∩ D_{α}. Then X ∈ [s, U]. By the definition of D_{α}, for each t ⊆ s,

N ⊧ ⟨t, U⟩ ||^{R} A_{α}^{N} .

(Here note that this is A_{α}^{N}, not A_{α}^{N[G]} yet.) But by the definition of A_{α}^{N}, this is written more verbosely by,

N ⊧ ∀z ∈ [t, U] θ_{φ}(z, a, c_{α})
∨ N ⊧ ∀z ∈ [t, U] χ_{φ}(z, a, c_{α}) .

Here “z ∈ [t, U]” is arithmetical, θ_{φ} and χ_{φ} are Π_{1}^{1}. So the whole statements “∀z ∈ [t, U] …” are both Π_{1}^{1}. Since N and N[G] are models of a sufficiently large fragment of ZF, we may assume that these relations are absolute for N and N[G] (Lemma 3). Hence

N[G] ⊧ ∀z ∈ [t, U] θ_{φ}(z, a, c_{α})
∨ N[G] ⊧ ∀z ∈ [t, U] χ_{φ}(z, a, c_{α}) ,

that is,

⟨t, U⟩ ||^{R} A_{α}^{N[G]} .

For any Y ∈ [X]^{ω}, Y ∈ [Y ∩ s, X \ s] ⊆ [Y ∩ s, U], so Y ∈ A_{α}^{N[G]} iff ⟨Y ∩ s, U⟩ ||−^{R} A_{α}^{N[G]}. This implies

A_{α}^{N[G]} ∩ [X]^{ω} = ⋃{[t, X \ s] | t ⊆ s ∧ ⟨t, U⟩ ||−^{R} A_{α}^{N[G]}} ,

and this is a (finite) union of open sets in [X]^{ω}. □

Hence A^{N[G]} ∩ [X]^{ω} = ⋃_{α<ω_{1}}(A_{α}^{N[G]} ∩ [X]^{ω}) is open in [X]^{ω}. Moreover as the space ^{ω}2 satisfies the second countability axiom (in fact its basic open sets are countable), so does the subspace [X]^{ω}. Thus there exists γ < ω_{1}^{N[G]} such that

A_{γ}^{N[G]} ∩ [X]^{ω} = ⋃_{α<γ}(A_{α}^{N[G]} ∩ [X]^{ω}) = ⋃_{α<ω_{1}}(A_{α}^{N[G]} ∩ [X]^{ω}) = A^{N[G]} ∩ [X]^{ω} .

We fix this γ.

Claim 2.6 There is Y ∈ [X]^{ω} such that ⟨0, Y ⟩ ||^{R} A^{N[G]}.

Proof of Claim: As A^{N[G]} ∩ [X]^{ω} is open in [X]^{ω}, there is an open set O ⊆ ^{ω}2 such that O ∩ [X]^{ω} = A^{N[G]} ∩ [X]^{ω}. We can assume that N[G] knows that the open set O is completely Ramsey (Theorem 1). Now we have Y ∈ [X]^{ω} such that ⟨0, Y ⟩ ||^{R} O, but this implies ⟨0, Y ⟩ ||^{R} A^{N[G]}. □

Here we already know that N[G] thinks A^{N[G]} is Ramsey. We shall show this situation also holds in V by absoluteness.

Now we step out from N[G] to V. And we consider two cases.

Case 1 : N[G] ⊧ ⟨0, Y ⟩ ||−^{R} (^{ω}2 \ A^{N[G]}) .

This means

N[G] ⊧ ∀z ∈ [Y]^{ω} ¬φ(z, a) ,

but this is a Π_{1}^{1} statement on Y and a. We can assume that Π_{1}^{1} statements are absolute for N[G] and V, so

V ⊧ ∀z ∈ [Y]^{ω} ¬φ(z, a) .

Thus ⟨0, Y ⟩ ||−^{R} (^{ω}2 \ A^{V}).

Case 2 : N[G] ⊧ ⟨0, Y ⟩ ||−^{R} A^{N[G]} .

If we were to follow the same transformation as Case 1, we would have a Π_{2}^{1} statement, which is not necessarily absolute for our countable model N[G]. So we use the above γ here. In fact,

N[G] ⊧ ⟨0, Y ⟩ ||−^{R} A_{γ}^{N[G]} .

Using c_{γ} ∈ N[G] coding γ, this is written as

N[G] ⊧ ∀z ∈ [Y]^{ω} θ_{φ}(z, a, c_{γ}) .

This is a Π_{1}^{1} statement about Y, a and c_{γ}. This can be assumed to be absolute for N[G] and V, thus

V ⊧ ∀z ∈ [Y]^{ω} θ_{φ}(z, a, c_{γ}) .

This means ⟨0, Y ⟩ ||−^{R} A_{γ}^{V}, and this clearly implies

⟨0, Y ⟩ ||−^{R} A^{V} .

In each case, ⟨0, Y ⟩ forces the same in N[G] and V, and the theorem is proved. □

The main difference between Silver’s proof [2] and ours is as follows: Silver brought a forcing which makes N[G] ⊧ MA(ω_{1}), where MA(ω_{1}) means that for every c.c.c. p.o. set and for every sequence of dense subsets whose length is at most ω_{1}, there exists a “generic” filter which intersects all dense sets in the sequence. And in N[G] he constructed our P_{F} and directly got a “generic” object using MA(ω_{1}). Since the cardinality of the family of dense subsets we want to make this “generic” subset intersect is ω_{1}, MA(ω_{1}) suffices. His proof is mainly in N[G], so does not need any argument about absoluteness for N and N[G].

On the other hand, we can use Mathias forcing P_{M} instead of P_{F}. Then we owe the preservation of ω_{1} to Mathias [4, 4.10].

But the simplicity of our forcing will allow us to get some refinement in the case of Σ_{2}^{1}.

4 On provably Δ_{2}^{1} sets

In this section, we get the Ramseyness of a little wider class than the previous section. We first define the class of provably Δ_{2}^{1} sets.

Definition 1 For a ∈ ^{ω}2 and A ⊆ ^{ω}2, A is (ZF-)provably Δ_{2}^{1}(a) iff there exist a Σ_{2}^{1} formula φ(x, w) and a Π_{2}^{1} formula ψ(x, w) such that:

• x ∈ A iff φ(x, a) iff ψ(x, a) ,

• ZF ⊢ ∀^{1}x, w [φ(x, w) ↔ ψ(x, w)] .

A is provably Δ_{2}^{1} iff for some a ∈ ^{ω}2, A is provably Δ_{2}^{1}(a).

Provably Δ_{2}^{1} sets are also Δ_{2}^{1}, but the converse is false. The next lemma tells us that the theory used for the equivalence may be somewhat ambiguous.

Lemma 7 A is ZFC-provably Δ_{2}^{1}(a) iff A is ZF-provably Δ_{2}^{1}(a). In fact, for any Σ_{2}^{1} φ and Π_{2}^{1} ψ,

ZFC ⊢ ∀^{1}x, w [φ(x, w) ↔ ψ(x, w)]
iff ZF ⊢ ∀^{1}x, w [φ(x, w) ↔ ψ(x, w)] .

Proof : Suppose ZFC ⊢ ∀^{1}x, w [φ(x, w) ↔ ψ(x, w)], φ is Σ_{2}^{1} and ψ is Π_{2}^{1}. It is enough to show that ZF implies the same theorem. “∀^{1}x, w (L[x, w] ⊧ σ_{2})” and “∀^{1}x, w (ω_{1}^{V} ⊆ L[x, w])” are theorems of ZF, where σ_{2} is as in Lemma 4. So by this theorem—in fact by one theorem in the schema,

ZF ⊢ ∀^{1}x, w (φ(x, w) ↔ L[x, w] ⊧ φ(x, w)) .

Similarly,

ZF ⊢ ∀^{1}x, w (ψ(x, w) ↔ L[x, w] ⊧ ψ(x, w)) .

And since “L[x, w] satisfies a fragment of ZFC sufficient for a proof of ∀^{1}x, w [φ(x, w) ↔ ψ(x, w)]” is a theorem of ZF, thus

ZF ⊢ ∀^{1}x, w (L[x, w] ⊧ φ(x, w) ↔ L[x, w] ⊧ ψ(x, w)) .

These equivalences establish our goal. □

Note that “ZFC” is replaced by “ZF+∃^{1}x(V = L[x])”, but not by “ZF+V = L”.

Theorem 3 Every provably Δ_{2}^{1} sets of ^{ω}2 is completely Ramsey.

Proof : The outline of the proof is the same as the case of Σ_{1}^{1}. We need to treat each absoluteness carefully because hierarchies are raised now.

We have only to show Ramseyness again. For if A is provably Δ_{2}^{1} and f : ^{ω}2 → ^{ω}2 is continuous then f^{−1}(A) is provably Δ_{2}^{1}.

Now we fix a ∈ ^{ω}2, and a provably Δ_{2}^{1}(a) set

{x | φ(x, a)} = A^{V} = ^{ω}2 \ B^{V} = {x | ¬ψ(x, a)} ,

where φ and ψ are Σ_{2}^{1}. These are canonically divided into ℵ_{1} Borel sets.

A^{V} = ⋃_{α<ω_{1}^{V}} A_{α}^{V}
B^{V} = ⋃_{α<ω_{1}^{V}} B_{α}^{V} ,

where A_{α}^{V} , B_{α}^{V} are defined from θ_{φ}, θ_{ψ} and a. We want to show this A^{V} is Ramsey.

Again we begin our argument in N which is a countable transitive model of a fragment of ZF+AC sufficiently large for this proof with a ∈ N. We define (in N) A^{N}, B^{N}, A_{α}^{N}, B_{α}^{N} for α < ω_{1}^{N} using the same φ, ψ, θ_{φ}, θ_{ψ} and a. N can be assumed to know that the splitting of Σ_{2}^{1}’s (Lemma 6) and that A is provably Δ_{2}^{1}(a):

A^{N} = ⋃_{α<ω_{1}^{N}} A_{α}^{N} = ^{ω}2 \ B^{N} = ^{ω}2 \ ⋃_{α<ω_{1}^{N}} B_{α}^{N} .

Moreover N can be assumed to think each A_{α}^{N}, B_{α}^{N} is Borel and so completely Ramsey (Theorem 1).

We construct F, P_{F}, D_{α} and \overline{D_{n}} similarly to the previous section but with another property of F:

5. ∀α < ω_{1}∀s ∈ [ω]^{<ω}∃U ∈ F [⟨s, U⟩ ||^{R} B_{α}^{N}] .

The construction is straightforward. We can check that P_{F} has the c.c.c. and that D_{α} and \overline{D_{n}} are dense.

Next we step out to V and get a P_{F}-generic G over N. From now on we argue in N[G], which is a model of an arbitrarily large fragment of ZF+AC. Since N ⊧ P_{F} has the c.c.c., ω_{1}^{N} = ω_{1}^{N[G]}.

Now in N[G], we define A^{N[G]}, B^{N[G]}, A_{α}^{N[G]}, and B_{α}^{N[G]} for α < ω_{1}^{N[G]} by the same formulae φ, ψ, θ_{φ}, θ_{ψ} and a. Here again N[G] can be assumed to know

A^{N[G]} = ⋃_{α<ω_{1}^{N[G]}} A_{α}^{N[G]} = ^{ω}2 \ B^{N[G]} = ^{ω}2 \ ⋃_{α<ω_{1}^{N[G]}} B_{α}^{N[G]} .

Let X be ⋃\{s | ⟨s, U⟩ ∈ G\}. Then X ∈ [ω]^{ω} by the density of \overline{D_{n}}.

The following claim is shown by the same proof as before.

Claim 3.1 ∀α < ω_{1} (A_{α}^{N[G]} ∩ [X]^{ω} and B_{α}^{N[G]} ∩ [X]^{ω} are open in [X]^{ω}).

Again, A^{N[G]}∩[X]^{ω} = ⋃_{α<ω_{1}^{N[G]}}(A_{α}^{N[G]}∩[X]^{ω}) and B^{N[G]}∩[X]^{ω} = ⋃_{α<ω_{1}^{N[G]}}(B_{α}^{N[G]}∩[X]^{ω}) are

open (in fact clopen) in [X]^{ω}, and by the second countability axiom there exists γ < ω_{1}^{N[G]} such that

A^{N[G]} ∩ [X]^{ω} = A_{γ}^{N[G]} ∩ [X]^{ω} = [X]^{ω} \ B^{N[G]} = [X]^{ω} \ B_{γ}^{N[G]} .

We fix this γ and a real c_{γ} coding γ. Because A^{N[G]} is open in [X]^{ω} and N[G] thinks open sets are completely Ramsey (Theorem 1), there is Y ∈ [X]^{ω} such that ⟨0, Y ⟩ ||^{R} A^{N[G]}.

Now we step out from N[G] to V. And we consider two cases.

Case 1 : N[G] ⊧ ⟨0, Y ⟩ ||−^{R} A^{N[G]} .

In fact,

N[G] ⊧ ⟨0, Y ⟩ ||−^{R} A_{γ}^{N[G]} ,

that is,

N[G] ⊧ ∀z ∈ [Y]^{ω} θ_{φ}(z, a, c_{γ}) .

This statement is Π_{1}^{1} as before, so this is assumed to be absolute for N[G] and V, thus

V ⊧ ∀z ∈ [Y]^{ω} θ_{φ}(z, a, c_{γ}) .

This means ⟨0, Y ⟩ ||−^{R} A_{γ}^{V} and implies

⟨0, Y ⟩ ||−^{R} A^{V} .

Case 2 : N[G] ⊧ ⟨0, Y ⟩ ||−^{R} (^{ω}2 \ A^{N[G]}) .

This case is similar to the previous case, using B_{γ}.

The rest is the same as the previous section. □

5 On Σ_{2}^{1} sets

We go on to Σ_{2}^{1} sets. Unlike before, we cannot prove the Ramseyness of Σ_{2}^{1} sets from ZF alone because if ^{ω}2 ⊆ L then there exists a Δ_{2}^{1} set which is not Ramsey. Hence by our second result (Theorem 3), this set is also a counterexample of Δ_{2}^{1} and not provably Δ_{2}^{1}. So we need some additional assumption which implies ^{ω}2 ⊈ L at least.

Silver in [2] started from the existence of a measurable cardinal, and essentially used the assumption that for each a ⊆ ω, ω_{1}^{V} is inaccessible in L[a]. He showed this assumption implies that all Σ_{2}^{1} sets are Ramsey.

We use our forcing and make this theorem effective and somewhat refined.

Theorem 4 For a ∈ ^{ω}2, if ω_{1}^{L[a]} < ω_{1} then every Σ_{2}^{1}(a) subset of ^{ω}2 is Ramsey.

Proof : Because of the effectiveness of our statement, we cannot establish complete Ramseyness. (If A is Σ_{2}^{1}(a) and f is a continuous mapping coded by a real z_{f}, f^{−1}(A) would be Σ_{2}^{1}(a, z_{f}).)

Given a Σ_{2}^{1}(a) set A^{V} = {x | φ(x, a)} with a Σ_{2}^{1} formula φ, using Lemma 6, we define

A_{α}^{V} = {x | for some (any) z coding α, θ_{φ}(x, a, z)} .

We know A^{V} = ⋃_{α<ω_{1}} A_{α}^{V}. We shall show that this A^{V} is Ramsey.

We start from L[a], which is the class of constructible sets from a, as a ground model. In L[a] the whole ZFC holds. From now on we argue in L[a]. L[a] knows Σ_{2}^{1} can be split into ℵ_{1} Borel sets (Lemma 6). We can define A^{L[a]} and A_{α}^{L[a]}’s by the same formulae φ, θ_{φ}, and a as in V. We know

A^{L[a]} = ⋃_{α<ω_{1}^{L[a]}} A_{α}^{L[a]} .

L[a] knows that each A_{α}^{L[a]} is Borel and hence is completely Ramsey (by Theorem 1). This implies the same Claim as Claim 2.1, and we have F, c.c.c. P_{F}, and dense subsets D_{α}, \overline{D_{n}}.

Now again we step out from L[a] to the universe V. Can we find a P_{F}-generic G over L[a]? G must touch all dense subsets of P_{F} in L[a]. But as L[a] satisfies AC, we have only to make G touch all maximal antichains of P_{F} in L[a]. Moreover as L[a] ⊧ P_{F} has the c.c.c., the cardinality of each maximal antichain is at most countable in L[a]. And L[a] knows |P_{F}| ≤ ω_{1}^{L[G]} and the continuum hypothesis 2^{ω} = ω_{1}. Consequently,

|{D ∈ L[a] | D is maximal antichain in P_{F}}| ≤ |(^{ω}P_{F})^{L[a]}| ≤ (ω_{1}^{ω})^{L[a]} ≤ (ω_{1})^{L[a]} < ω_{1}^{V} .

This tells us that we have a P_{F}-generic G over L[a] in V. Again since L[a] ⊧ P_{F} has the c.c.c., ω_{1}^{L[a]} = ω_{1}^{L[a][G]}.

We argue in L[a][G] from here. L[a][G] knows that A^{L[a][G]} is the union of A_{α}^{L[a][G]}’s and that these are well-defined. Let X be ⋃{s | ⟨s, U⟩ ∈ G}. Note that for all ⟨s, U⟩ ∈ G, X ∈ [s, U]. Since \overline{D_{n}} is dense, X ∈ [ω]^{ω}.

Claim 4.1 ∀α < ω_{1} (A_{α}^{L[a][G]} ∩ [X]^{ω} is open in [X]^{ω} ).

The proof of this claim is exactly as before. Hence A^{L[a][G]}∩[X]^{ω} = ⋃_{α<ω_{1}^{L[a][G]}}(A_{α}^{L[a][G]}∩[X]^{ω})

is open in [X]^{ω}. And again by the second countability axiom there exists γ < ω_{1}^{L[a][G]} such that

A_{γ}^{L[a][G]} ∩ [X]^{ω} = ⋃_{α<γ}(A_{α}^{L[a][G]} ∩ [X]^{ω}) = ⋃_{α<ω_{1}^{L[a][G]}}(A_{α}^{L[a][G]} ∩ [X]^{ω}) = A^{L[a][G]} ∩ [X]^{ω} .

We fix this γ and a real c_{γ} coding this.

A^{L[a][G]} is open in [X]^{ω} implies that there is Y ∈ [X]^{ω} such that ⟨0, Y ⟩ ||^{R} A^{L[a][G]}.

Now we step out from L[a][G] to V. We consider two cases here, too.

Case 1 : L[a][G] ⊧ ⟨0, Y ⟩ ||−^{R} (^{ω}2 \ A^{L[a][G]})

This means

L[a][G] ⊧ ∀z ∈ [Y]^{ω} ¬φ(z, a) ,

but this is a Π_{2}^{1} statement about Y and a and by Shoenfield’s Σ_{2}^{1} absoluteness theorem (Lemma 4) this statement is absolute for L[a][G] and V, so

V ⊧ ∀z ∈ [Y]^{ω} ¬φ(z, a) .

Thus ⟨0, Y ⟩ ||−^{R} (^{ω}2 \ A^{V}).

Case 2 : L[a][G] ⊧ ⟨0, Y ⟩ ||−^{R} A^{L[a][G]}

Using the above γ,

L[a][G] ⊧ ⟨0, Y ⟩ ||−^{R} A_{γ}^{L[a][G]} .

This means

L[a][G] ⊧ ∀z ∈ [Y]^{ω} θ_{φ}(z, a, c_{γ}) .

This is a Π_{1}^{1} statement about Y, a and c_{γ}, so this is absolute for L[a][G] and V,

V ⊧ ∀z ∈ [Y]^{ω} θ_{φ}(z, a, c_{γ}) ,

and this implies ⟨0, Y ⟩ ||−^{R} A^{V}.

In each case, ⟨0, Y ⟩ ||^{R} A^{V}, and the theorem is proved. □

Remark: If we use a forcing making MA(ω_{1}) as Silver did, then this forcing notion has the c.c.c. and is of cardinality ω_{2}. Thus in L[a] the number of all maximal antichains is ω_{2}. We would need the assumption that ω_{2}^{L[a]} < ω_{1}.

If we used Mathias forcing P_{M}, then since P_{M} does not satisfy the c.c.c., we would need ω_{2}^{L[a]} < ω_{1} again.

We also have a corollary which is related to a large cardinal hypothesis.

Corollary 5 (Silver) If ∀a (ω_{1}^{L[a]} < ω_{1}) then every Σ_{2}^{1} set of ^{ω}2 is completely Ramsey.

Proof of Corollary: Suppose A is Σ_{2}^{1}(a) and f : ^{ω}2 → ^{ω}2 is continuous. f can be coded by one real, say z_{f}. Then f^{−1}(A) is Σ_{2}^{1}(a, z_{f}). So our theorem tells us f^{−1}(A) is Ramsey. This shows that A is completely Ramsey. □

The converse of our third theorem (Theorem 4) is false: From Silver’s lemma ([2, p. 61 LEMMA]) we know

MA(ω_{1}) ⟶ “all Σ_{2}^{1} sets are Ramsey” ,

so the right statement is equiconsistent with ZF. But it is easily checked that

∀^{1}a (ω_{1}^{L[a]} < ω_{1}^{V}) ⟶ ∀^{1}a (ω_{1}^{V} is inaccessible in L[a]) ,

which is consistency-wise stronger than ZF.

This result is optimal in the sense of height in the projective hierarchy: If V = L[μ] holds, in other words if the universe is the canonical inner model for measurability, then there is a Δ_{3}^{1} well-ordering of ^{ω}2, so there is a Δ_{3}^{1} non-Ramsey set ([5, 20.18, 20.20]). But this hypothesis implies that ∀^{1}a (ω_{1}^{L[a]} < ω_{1}).

References

[1] P. Erdös and R. Rado, Combinatorial theorems on classifications of subsets of a given set, Proceedings of the London Mathematical Society, vol. 2 (1952), pp. 417–439.

[2] J. H. Silver, Every analytic set is Ramsey, Journal of Symbolic Logic, vol. 35 (1970), pp. 60–64.

[3] F. Galvin and K. Prikry, Borel sets and Ramsey’s theorem, Journal of Symbolic Logic, vol. 38 (1973), pp. 193–198.

[4] A. R. D. Mathias, Happy families, Annals of Mathematical Logic, vol. 12 (1977), pp. 59– 111.

[5] A. Kanamori, The Higher Infinite, Springer, Berlin, 1994.