On relatively analytic and Borel subsets

Arnold W. Miller^{1}

Abstract

Define 𝔷 to be the smallest cardinality of a function f : X → Y with X, Y ⊆ 2^{ω} such that there is no Borel function g ⊇ f. In this paper we prove that it is relatively consistent with ZFC to have 𝔟 < 𝔷 where 𝔟 is, as usual, smallest cardinality of an unbounded family in ω^{ω}. This answers a question raised by Zapletal.

We also show that it is relatively consistent with ZFC that there exists X ⊆ 2^{ω} such that the Borel order of X is bounded but there exists a relatively analytic subset of X which is not relatively coanalytic. This answers a question of Mauldin.

The following is an equivalent definition of 𝔷:

𝔷 = min{|X| : X ⊆ 2^{ω}, ∃Y ⊆ X Y is not Borel in X}

For one direction we can use for each Y ⊆ X its characteristic function f : X → 2. For the other direction use that a function is Borel iff the inverse image of each basic open set is Borel.

The following answers a question raised by Zapletal [6] see appendix A.

Theorem 1 It is relatively consistent with ZFC that 𝔟 < 𝔷.

Define p ∈ ℙ(A) for A ⊆ 2^{ω} iff p is a finite set of consistent sentences of the form:

1. “x ∈ ∩_{m<ω}U_{nm}” where x ∈ A, n ∈ ω, or

2. “x ∉ U_{nm}” where x ∈ 2^{ω}, n, m ∈ ω, or

3. “[s] ⊆ U_{nm}” where s ∈ 2^{<ω}, n, m ∈ ω.

1Thanks to University of Florida, Gainesville and to Boise State University, Idaho for their hospitality during the time this paper was written and to J.Zapletal and T.Bartoszynski for some helpful discussions.

Mathematics Subject Classification 2000: 03E35; 03E17; 03E15

By consistent we simply mean the following:

• p cannot contain both “x ∈ ∩_{m<ω}U_{nm}” and “x ∉ U_{nk}” for some x, n, k, and

• p cannot contain both “x ∉ U_{nm}” and “[x ↾ k] ⊆ U_{nm}” for some x.n, m, k.

The ordering on ℙ(A) is given by inclusion: p ≤ q iff p ⊇ q. Note that the set A enters into the picture only in sentence of type (1).

This partial order is from Miller [2] where there are versions for all countable Borel orders (this is for Σ_{3}^{0}). It can be looked on as a generalization of almost disjoint forcing of Jensen and Solovay. I learned about describing almost disjoint forcing as sets of sentences from Jack Silver.

Now suppose that G is ℙ(A)-generic over V. Define

U_{nm}^{G} = ∪{[s] : “[s] ⊆ U_{nm}” ∈ G} and W_{n}^{G} = ∩_{m<ω}U_{nm}^{G}

Lemma 2 For any x ∈ V ∩ 2^{ω}

1. x ∉ U_{nm}^{G} iff “x ∉ U_{nm}” ∈ G

2. x ∈ W_{n}^{G} iff “x ∈ ∩_{m<ω}U_{nm}” ∈ G

3. x ∈ A iff x ∈ ∪_{n<ω}W_{n}^{G}

Proof To prove (1) working in V, fix x ∈ 2^{ω} and n, m < ω. The following set is dense:

D_{x,n,m} = {p ∈ ℙ(A) : ∃k “[x ↾ k] ⊆ U_{nm}” ∈ p or “x ∉ U_{nm}” ∈ p}

To see this note that if “x ∉ U_{nm}” is not in p we can always find k large enough so that p ∪ {“[x ↾ k] ⊆ U_{nm}”} is a consistent set of sentences. Now suppose x ∈ U_{nm}^{G}, then for some k we have that “[x ↾ k] ⊆ U_{nm}” ∈ G and hence by consistency, “x ∉ U_{nm}” ∉ G. On the other hand, if “x ∉ U_{nm}” ∉ G, then since D_{x,n,m} is dense for some k we have that “[x ↾ k] ⊆ U_{nm}” ∈ G and hence x ∈ U_{nm}^{G}.

To prove (2) note that the following set is dense:

D_{x,n} = {p ∈ ℙ(A) : ∃k “x ∉ U_{nk}” ∈ p or “x ∈ ∩_{m<ω}U_{nm}” ∈ p} To see this note that if “x ∈ ∩_{m<ω}U_{nm}” ∉ p, then for large k (so that U_{nk} is not mentioned in p), the sentences p ∪ {“x ∉ U_{nk}”} are consistent.

To prove (3) note that if x ∈ A then the following is dense:

D_{x} = {p ∈ ℙ(A) : ∃n “x ∈ ∩_{m<ω}U_{nm}” ∈ p}

and we can only assert “x ∈ ∩_{m<ω}U_{nm}” for x ∈ A. QED

Note that it follows from the Lemma that A ∩ V = (∪_{n<ω}W_{n}^{G}) ∩ V and so that A is a Σ_{3}^{0} relative to the ground model reals.

Lemma 3 ℙ(A) is ccc.

Proof This is a standard Δ-systems argument. Suppose two conditions p and q agree on all sentences of the form:

“[s] ⊆ U_{nm}”

and also they agree on all sentences of the form:

“x ∈ ∩_{m<ω}U_{nm}” or “x ∉ U_{nm}”

whenever x is mentioned in both p and q. Then p ∪ q is consistent. QED

Next we must prove that ℙ(A) does not add a dominating real.

Working in V, for Y ⊆ 2^{ω} countable define p ∈ ℙ(A)_{Y} iff p ∈ ℙ(A) and

∀x, n, k (“x ∉ U_{nk}” ∈ p or “x ∈ ∩_{m<ω}U_{nm}” ∈ p) → x ∈ Y }.

Or in other words, ℙ(A)_{Y} are the conditions in ℙ(A) which only mention elements of Y.

Lemma 4 Suppose p ∈ ℙ(A) and q ∈ ℙ(A)_{Y}. Then p and q are compatible iff r and q are compatible where

r = p \ {“x ∈ ∩_{m<ω}U_{nm}” : x ∉ Y, n < ω}

Proof Incompatibility cannot arise between sentences of type (1) and (3). That is, any pair of the form:

“[s] ⊆ U_{nm}”, “x ∈ ∩_{m<ω}U_{nm}”

is consistent. It follows that the “x ∈ ∩_{m<ω}U_{nm}” ∈ p for which x ∉ Y cannot conflict with the sentences of q since by definition q cannot mention any x which is not in Y. QED

Define. T = (p, (t_{i}, n_{i}, m_{i} : i < N)) is a Y -template iff

1. p ∈ ℙ(A)_{Y}, t_{i} ∈ 2^{<ω}, n_{i}, m_{i}, N ∈ ω,

2. if “y ∈ ∩_{m<ω}U_{n_{i}m}” ∈ p, then y ∉ [t_{i}], and

3. if “[s] ⊆ U_{n_{i}m_{i}}” ∈ p, then [s] ∩ [t_{i}] = ∅.

Define. For x⃗ = (x_{i} : i < N) ∈ ∏_{i<N}[t_{i}]

p(x⃗) = p ∪ {“x_{i} ∉ U_{n_{i}m_{i}}” : i < N}

Note that by the definition of Y -template that p(x⃗) ∈ ℙ(A), i.e., is consistent, for every x⃗ ∈ ∏_{i<N}[t_{i}].

Lemma 5 Suppose that |⊢τ ∈ ω, there exists Σ ⊆ ℙ(A)_{Y} a maximal antichain deciding τ, and (p, (t_{i}, n_{i}, m_{i} : i < N)) is a Y -template. Then there exists k < ω so that for every x⃗ ∈ ∏_{i<N}[t_{i}] there exists q ∈ ℙ(A)_{Y} such that p(x⃗) ∪ q ∈ ℙ(A) and q|⊢τ < k.

Proof For q ∈ ℙ(A)_{Y} define

U_{q} = {x⃗ ∈ ∏_{i<N}[t_{i}] : p(x⃗) ∪ q ∈ ℙ(A)}

Note that U_{q} is open. To see this, suppose x⃗ ∈ U_{q} so that p(x⃗) ∪ q ∈ ℙ(A). Note that although some x_{i} might be in Y it can’t be that “x_{i} ∉ U_{n_{i}m_{i}}” ∈ p(x⃗) and “x_{i} ∈ ∩_{m<ω}U_{n_{i}m}” ∈ q, because they are compatible. Hence, there must be a sufficiently small neighborhood of x_{i} say t′_{i} = x_{i} ↾ k_{i} ⊇ t_{i} with the properties that 1. if “z ∈ ∩_{m<ω}U_{n_{i}m}” ∈ p ∪ q, then z ∉ [t′_{i}], and

2. if “[s] ⊆ U_{n_{i}m_{i}}” ∈ p ∪ q, then [s] ∩ [t′_{i}] = ∅.

Hence, x⃗ ∈ ∏_{i<N}[t′_{i}] ⊆ U_{q}.

Now since Σ ⊆ ℙ(A)_{Y} is a maximal antichain we know that

∪{U_{q} : q ∈ Σ} = ∏_{i<N}[t_{i}]

So by compactness since each U_{q} is open, there exists a finite F ⊆ Σ such that

∪{U_{q} : q ∈ F } = ∏_{i<N}[t_{i}]

and since each q ∈ Σ decides τ, the Lemma follows. QED

In order to prove the full result we must show that the iteration does not add a dominating real. To do this we prove the following stronger property (see Bartoszynski and Judah [1] definition 6.4.4):

Lemma 6 The poset ℙ(A) is really ⊑^{bounded}-good, i.e., for every name τ for an element of ω^{ω} there exists g ∈ ω^{ω} such that for any x ∈ ω^{ω} if there exists p ∈ ℙ(A) such that p|⊢∀^{∞}n x(n) < τ(n), then ∀^{∞}n x(n) < g(n).

Proof

Suppose that |⊢τ ∈ ω^{ω}. Using ccc get Y ⊆ 2^{ω} countable so that for every n < ω there exists a maximal antichain Σ ⊆ ℙ(A)_{Y} which decides τ(n). List all Y -templates as (T_{n} : n < ω). By Lemma 5 there exists g ∈ ω^{ω} with the property that for every l < ω and n < l if

T_{n} = (p, (t_{i}, n_{i}, m_{i} : i < N))

then for every x⃗ ∈ ∏_{i<N}[t_{i}] there exists q ∈ ℙ(A)_{Y} such that p(x⃗) ∪ q ∈ ℙ(A) and q|⊢τ(l) < g(l). (To get g(l) apply Lemma 5 to τ = τ(l) and each of the templates (T_{n} : n < l) and then take g(l) to be the maximum of all the k′s.)

Now suppose that p_{0}|⊢∀l > l_{0} x(l) < τ(l) and

p_{0} = p ∪ {z_{i} ∈ ∩_{m<ω}U_{n′_{i},m} : i < N′} ∪ {x_{i} ∉ U_{n_{i}m_{i}} : i < N}

where p ∈ ℙ(A)_{Y} and z_{i}, x_{i} ∉ Y.

Take t_{i} sufficiently long so that t_{i} ⊆ x_{i} and

T = (p, (t_{i}, n_{i}, m_{i} : i < N))

is a Y -template. Assume that l_{0} is sufficiently large so that T = T_{k} for some k < l_{0}. By our construction for each l > l_{0}, there exists q ∈ ℙ(A)_{Y} such that p(x⃗) ∪ q ∈ ℙ(A) and q|⊢τ(l) < g(l). But by Lemma 4 this means that p_{0} ∪ q ∈ ℙ(A) and hence x(l) < g(l). QED

The above proof is similar to that of Lemma 6.5.8 [1].

Now we prove Theorem 1. Starting with a model of CH we iterate with finite support ω_{2} times

ℙ_{α+1} = ℙ_{α}∗ ℙ^{∘} (A_{α}^{∘})

where we dovetail to list all A ⊆ 2^{ω} of size ω_{1} in the final model. Since the finite support iteration of really ⊑^{bounded}-good ccc forcing adds no dominating real (see Bartoszynski and Judah [1] Theorem 6.5.4), we have that in the resulting model 𝔟 = ω_{1}. On the other hand by Lemma 2 we have that 𝔷 = ω_{2}. QED

Define (see Zapletal [6] Appendix A)

𝔰𝔫 = min{|X| : X ⊆ T , ∀A Σ_{1}^{1} X ∩ A ≠ X ∩ W F }

where T is the set of ω-trees and W F is the set of well-founded trees. An equivalent definition is:

𝔰𝔫 = min{|X| : X ⊆ 2^{ω} ∃A Σ_{1}^{1} ∀B Π_{1}^{1} X ∩ A ≠ X ∩ B}

The equivalence is easy to show because the set of well-founded trees is a universal Π_{1}^{1} set. It is not hard to see that 𝔷 ≤ 𝔰𝔫. So we have the relative consistency of 𝔟 < 𝔰𝔫.

The following proposition is mostly due to Rothberger [5]. It implies that we must go up to at least the third level of the Borel hierarchy to get the consistency of 𝔟 < 𝔰𝔫. It shows why ℙ(A) which makes A ∩ V a Σ_{3}^{0} relative to the ground model reals cannot be improved to a forcing which makes it a relative Σ_{2}^{0}.

Proposition 7 For κ an infinite cardinal the following are equivalent:

1. 𝔟 > κ

2. For all X ⊆ 2^{ω} with |X| ≤ κ and for all Σ_{1}^{1} sets A ⊆ 2^{ω} there exists a Σ_{2}^{0} set B ⊆ 2^{ω} such that X ∩ A = X ∩ B.

3. For all X ⊆ 2^{ω} with |X| ≤ κ and for all Σ_{2}^{0} sets A ⊆ 2^{ω} there exists a Π_{2}^{0} set B ⊆ 2^{ω} such that X ∩ A = X ∩ B.

4. For all X ⊆ 2^{ω} with |X| ≤ κ and for all countable A ⊆ X there exists a Π_{2}^{0} set B ⊆ 2^{ω} such that A = X ∩ B.

Proof (2) → (3) and (3) → (4) are trivial. To see (1) → (2) let

A = {x ∈ 2^{ω} : ∃y ∈ ω^{ω} (x, y) ∈ C}

where C ⊆ 2^{ω} × ω^{ω} is closed. Suppose that A ∩ X = {x_{α} : α < κ}. Choose y_{α} ∈ ω^{ω} so that (x_{α}, y_{α}) ∈ C for each α < κ. Since 𝔟 > κ we can choose z_{n} ∈ ω^{ω} for n < ω so that for all α < κ there exists n < ω with y_{α} ≤ z_{n} (pointwise). Define

C_{n} = {(x, y) ∈ C : y ≤ z_{n}}

C_{n} is compact and therefore so is its projection:

A_{n} = {x ∈ 2^{ω} : ∃y (x, y) ∈ C_{n}}

But A ∩ X = (∪_{n<ω}A_{n}) ∩ X.

To see (4) → (1) let X ⊆ ω^{ω} with |X| = κ. Now since ω^{ω} is homeomorphic to [ω]^{ω} and [ω]^{ω} ⊆ P (ω) ≃ 2^{ω} by applying (4) we can find a Π_{2}^{0} set G ⊆ P (ω) such that

G ∩ (X ∪ [ω]^{<ω}) = [ω]^{<ω}

But note that F = P (ω) \ G is a σ-compact set which is disjoint from [ω]^{<ω}, i.e. a subset of [ω]^{ω} ≃ ω^{ω} and covers X. But is easy to show that for any σ-compact subset F of ω^{ω} there exists f ∈ ω^{ω} such that g ≤^{∗} f for all g ∈ F. QED

Remark. One way to get the consistency of 𝔟 < 𝔷 < 𝔰𝔫 is as follows: Start with a ground model of 2^{ω} = ω_{1}, 2^{ω_{1}} = ω_{2}, and 2^{ω_{2}} = ω_{17}. Do a finite support iteration of ℙ(A_{α}) for α < ω_{3}, so that for limit ordinals α we take A_{α} = A (the universal Σ_{1}^{1}-set) and for successor ordinals α we take |A_{α}| = ω_{1} as in the above proof. In the final model we will have 𝔟 = ω_{1} since it is an iteration of really ⊑^{bounded}-good ccc partial orders. Also we will have 𝔷 ≤ ω_{2} because 2^{ω_{2}} = ω_{17} and 2^{ω} = ω_{3}. We also have 𝔷 ≥ ω_{2} because of dovetailing over all A of size ω_{1}. And we will have 𝔰𝔫 = ω_{3} = 𝔠 because we have cofinally often used the universal Σ_{1}^{1}-set.

The following Theorem answers a question of Dan Mauldin (see [4] problem 7.8 and [3] p.212).

Theorem 8 It is relatively consistent with ZFC that there exist a separable metric space X such that the Borel order of X is bounded, but not every relatively analytic subset of X is Borel in X.

Proof We use almost exactly the same partial order but with one crucial difference. Instead of using arbitrary subsets A ⊆ 2^{ω} we let B ⊆ 2^{ω} be a fixed universal Π_{3}^{0} set. The partial order ℙ(B) is Borel, ccc, and adds a generic Σ_{3}^{0} set whose intersection with the ground model is the same as B’s with the ground model.

Define. A partially ordered set ℙ is very Souslin iff

1. ℙ is ccc,

2. ℙ, ≤, {(p, q) ∈ ℙ^{2} : p, q incompatible } are Σ_{1}^{1}, and

3. {Σ ∈ ℙ^{ω} : Σ enumerates a maximal antichain } is Σ_{1}^{1}.

We will need the following Lemma:

Lemma 9 (Zapletal [6] see Appendix C, Lemmas C.0.14 and C.0.17) Suppose ℙ is a very Souslin real partial order and ℙ^{ω_{2}} the countable support iteration of ℙ. Then

V^{ℙ^{ω_{2}}} ⊧ 𝔰𝔫 = ω_{1}.

Lemma 9 does not require large cardinals (LC) as many of Zapletal’s results do. It does mean that partial order ℙ(A) is not very Souslin even when A is taken to be analytic. However, if we change A to make it Borel, then it is very Souslin:

Lemma 10 For B Borel the partial order ℙ(B) is very Souslin. Proof The following sets are Borel:

1. ℙ(B)

2. {(p, q) ∈ ℙ(B) × ℙ(B) : p ⊆ q}

3. {(p, q) ∈ ℙ(B) × ℙ(B) : p and q are incompatible }

4. {(p, Y) : Y ∈ [2^{ω}]^{ω} and p ∈ ℙ(B)_{Y} }

5. {((T_{n} : n < ω), Y) : Y ∈ [2^{ω}]^{ω} and {T_{n} : n < ω} = all Y -templates }

Next we verify that being a maximal antichain in ℙ(B) is Σ_{1}^{1}. Claim. Σ ⊆ ℙ(B) is a maximal antichain iff

1. Σ is an antichain and

2. there exists Y ⊆ 2^{ω} countable and (T_{n} : n < ω) such that • Σ ⊆ ℙ(B)_{Y} and

• (T_{n} : n < ω) enumerates the set of all Y -templates and for all n if T_{n} = (p, (t_{i}, n_{i}, m_{i} : i < N)), then there exists K, (t_{i}^{j} : j < K), and (q_{j} : j < K) such that

(a) ∏_{i<N}[t_{i}] = ∪_{j<K} ∏_{i<N}[t_{i}^{j}]

(b) q_{j} ∈ Σ

(c) q_{j} ∪ p ∈ ℙ(B)

(d) “y ∈ ∩_{m<ω}U_{n_{i},m}” ∈ q_{j} → y ∉ [t_{i}^{j}]

(e) “[s] ⊆ U_{n_{i}m_{i}}” ∈ q_{j} → [t_{i}^{j}] ∩ [s] = ∅ Proof Condition (2) is just a detailed restatement of Lemma 5 and its proof. It guarantees by Lemma 4 that every p ∈ ℙ(B) is compatible with some q ∈ Σ.

This proves the claim and the lemma easily follows. QED

Hence by Zapletal’s Lemma 9 if we iterated ℙ(B) with countable support ω_{2} times then in the resulting model 𝔰𝔫 = ω_{1}. Hence there is some X ⊆ 2^{ω} of size ω_{1} with a relatively analytic set which is not relatively coanalytic. (Actually the proof of Lemma 9 shows that the ground model reals would do for such an X). But note that every Π_{3}^{0} set occurs as a cross section of our universal Π_{3}^{0}-set B and by Lemma 2 becomes Σ_{3}^{0} with respect to the ground model. Hence it is easy to see that for every X ⊆ 2^{ω} of size ω_{1} for every Σ_{3}^{0} B there exists a Π_{3}^{0} C such that X ∩ B = X ∩ C. This proves Theorem 8. QED

References

[1] Bartoszyński, Tomek; Judah, Haim; Set theory. On the structure of the real line. A K Peters, Ltd., Wellesley, MA, 1995. xii+546 pp.

[2] Miller, Arnold W.; On the length of Borel hierarchies. Ann. Math. Logic 16 (1979), no. 3, 233–267.

[3] Miller, Arnold W.; Special subsets of the real line, in Handbook of set-theoretic topology, 201–233, North-Holland, Amsterdam, 1984.

[4] Miller, Arnold W.; Some interesting problems, in Set Theory of the Reals, ed Haim Judah, Israel Mathematical Conference Proceedings, vol 6 (1993), 645-654, American Math Society, continuously updated on my home page.

[5] Rothberger, Fritz; Sur les familles indénombrables de suites de nombres naturels et les problèmes concernant la propriété C. (French) Proc. Cambridge Philos. Soc. 37, (1941). 109–126.

[6] Zapletal, Jindřich; Descriptive set theory and definable forcing. Mem. Amer. Math. Soc. 167 (2004), no. 793, viii+141 pp.

Arnold W. Miller miller@math.wisc.edu http://www.math.wisc.edu/∼miller University of Wisconsin-Madison Department of Mathematics, Van Vleck Hall 480 Lincoln Drive Madison, Wisconsin 53706-1388

Appendix

(Not intended for publication, electronic version only.)

Our first proof of 𝔟 < 𝔰𝔫 used large cardinals and the following Lemma:

Lemma 11 (Zapletal [6] Thm 5.4.12) (LC) Suppose ℙ is a real, proper, universally Baire forcing such that

V^{ℙ} ⊧ V ∩ ω^{ω}is unbounded in ≤^{∗}

Then

V^{ℙ^{ω_{2}}} ⊧ V ∩ ω^{ω}is unbounded in ≤^{∗}

where ℙ^{ω_{2}} stands for the ω_{2} iteration with countable support of ℙ.

The hypothesis (LC) stands for large cardinals, for example, unboundedly many measurable Woodin cardinals would be enough. In other words for a nice enough forcing, not adding a dominating real is preserved by the iteration. It is easy to get a two step iteration so that neither step adds a dominating real but the two steps do. For example, force ω_{1}-Cohen reals followed by the Hechler partial order of the ground model.

Fix A ⊆ 2^{ω} a universal Σ_{1}^{1} set, i.e., it is lightface Σ_{1}^{1} and every boldface Σ_{1}^{1} occurs as a cross section via some effective homeomorphism of 2^{ω} × 2^{ω} and 2^{ω}. In this case the partial order ℙ(A) is Σ_{1}^{1}, ccc, and determined by a real - so it satisfies the hypothesis of the Lemma.