LEBESGUE’S DENSITY THEOREM AND DEFINABLE SELECTORS FOR IDEALS

SANDRA MÜLLER, PHILIPP SCHLICHT, DAVID SCHRITTESSER, AND THILO WEINERT

Abstract. We introduce a notion of density point and prove results analogous to Lebesgue’s density theorem for various well-known ideals on Cantor space and Baire space. In fact, we isolate a class of ideals for which our results hold. As a contrasting result of independent interest, we show that there is no reasonably definable selector that chooses representatives for the equivalence relation on the Borel sets of having countable symmetric difference. In other words, there is no notion of density which makes the ideal of countable sets satisfy an analogue to the density theorem.

1. Introduction

1.1. Lebesgue’s Density Theorem. We write Meas 𝔛, μ for the collection of measurable subsets of a measure space 𝔛, μ and A _{μ} B to mean that two subsets A and B of 𝔛 are equal up to a null set, i.e., μ AΔB 0. Suppose 𝔛, d, μ is a metric measure space, by which we mean a metric space 𝔛, d equipped with the completion μ of a Borel measure on 𝔛. For A Meas 𝔛, μ ,

d_{A}^{μ} x lim inf_{ϵ 0} \frac{μ A B_{d} ϵ, x}{μ B_{d} ϵ, x}

is called the density of x in A, and

D_{μ} A x 𝔛 d_{A}^{μ} x 1

is called the set of density 1 points (or just density points) of A.

Now take 𝔛 to be Cantor space ^{ω}2, consisting of infinite binary sequences with the natural ultrametric d x, y \frac{1}{2^{n}}, where n is least such that x n y n , and let μ be the coin-tossing measure on ^{ω}2, i.e., the resulting product measure where 0 and 1 are assigned weight \frac{1}{2}. This is also known as the Bernoulli measure, uniform measure, or Lebesgue measure on ^{ω}2. The following result is known as Lebesgue’s Density Theorem (for Cantor space).^{1}

Theorem 1.1. For any A, B Meas ^{ω}2, μ (A) A _{μ} B D_{μ} A D_{μ} B , and (B) D_{μ} A _{μ} A.

For more on descriptive set theoretical aspects of Theorem 1.1 see [AC13, ACC15, AC18]; for a proof see [AC13] or [Mil08, Proposition 2.10] for ultrametric spaces. We give a different (finitized) proof just after Theorem 3.4 below.

When μ is a measure on a set 𝔛, the collection I_{μ} of its null sets is a typical example of a σ-ideal on 𝔛. By this we mean a collection I of subsets of 𝔛 which is closed under taking subsets and countable unions. We shall also assume that ideals are proper, i.e., that 𝔛 I.

Theorem 1.1 is not merely a result about a particular measure on ^{ω}2 but rather a statement about I_{μ}, its null-ideal: For it can be shown that D_{μ} A D_{μ^{}}A if I_{μ} I_{μ^{}}(for any two Borel measures μ, μ^{}on ^{ω}2).^{2} This motivates the main question which we answer in this paper. To state it, let for any Polish space 𝔛 (i.e., every completely metrizable separable space) Borel 𝔛 denote the collection of its Borel sets (the smallest collection containing the open sets which is closed under countable unions and taking complements).

Date: November 16, 2018.

2010 Mathematics Subject Classification. 03E15, 28A05.

Key words and phrases. Density points, ideals, selectors, forcing.

1This theorem is more usually stated for 𝔛 ℝ^{n} and μ λ^{n}, the n-dimensional Lebesgue measure. We concentrate on Cantor space since it is a more familiar setting for tree ideals (see below).

Question 1.2. Let I be a σ-ideal on a Polish space 𝔛. Can one define a set of density points D_{I} A for each A Borel X (or perhaps even for A from a larger collection) so that the analogue of Theorem 1.1 holds?

Of course we want the assignment A D_{I} A be to definable to rule out using the Axiom of Choice to select D_{I} A . An instance where the answer to Question 1.2 is positive is given by the following fact:

Fact 1.3. Suppose I is the collection of null sets of the completion ν of a Borel probability measure on a Polish space (or even a standard Borel space) 𝔛. Then there is a function D_{I} : Meas 𝔛, ν Borel 𝔛 so that the analogues of (A) and (B) in Theorem 1.1 hold.

The reason is that there is a Borel isomorphism ϕ of ^{ω}2, μ with 𝔛, ν so that images of sets in I_{μ} exactly the sets in I_{ν} [Kec95, 17.39]. Thus the map D_{I} is moreover induced by a Borel function on codes of analytic sets (see [Kec73]).

Question 1.2 also has a positive answer for the meager ideal, i.e., the smallest σ-ideal containing all closed nowhere dense sets (closed sets with empty interior): In this case let D_{I} A O O open, A O comeager in O for any set A with the Baire property (i.e., any set which has meager symmetric difference with some Borel set).^{3}

1.2. Strongly linked tree ideals. We answer Question 1.2 by utilizing the connection between σ-ideals and forcing.^{4} For any ideal I on a Polish space 𝔛, Borel 𝔛 I is a preorder (i.e., a transitive binary relation, a.k.a. a forcing or forcing notion) under . For all ideals of practical relevance, the structure of I can be recovered from a particularly nice dense subset^{5} of this preorder, consisting of perfect sets (closed sets without isolated points). Conversely, to any preorder ℙ P, with P P 𝔛 there is a standard way to construct a σ-ideal I_{ℙ} and a collection of ℙ-measurable sets Meas 𝔛, ℙ . We give a detailed review of this construction in Section 4.

We shall mostly restrict our attention to spaces of the form ^{ω}X, where X 2 or X ω, with the product topology—i.e., Cantor space and Baire space.^{6} Recall that C ^{ω}X is closed if and only if it is the branch set T of a subtree T of ^{ω} X (this is arguably the main reason for working in these spaces).

A tree forcing is a preorder ℙ, where ℙ is a collection of perfect subtrees of ^{ω} X, corresponding to perfect subsets of ^{ω}X.^{7} A tree σ-ideal is simply an ideal of the form I_{ℙ} where ℙ, is a tree forcing.

Tree σ-ideals are ubiquitous and relevant in many areas of mathematics, and to our knowledge every practically relevant ideal on a Polish space is of this form. Examples include: the null ideal of a Borel probability measure, the meager ideal on any non-meager Polish space, the K_{σ} sets, i.e., the ideal generated by the compact sets, on any Polish space which is not itself K_{σ}, or the nowhere Ramsey sets on ω ^{ω}, whose associated notion of measurability, the Ramsey property, is of immense importance in areas as diverse as combinatorics and functional analysis. (The associated forcings are of course Random, Cohen, Miller, and Mathias forcing, respectively.) For further examples see Section 6.

2On the other hand, Theorem 1.1 depends strongly on the metric. See [Mat95], [KRS16, Example 5.6], [ACC13], and [KRS16, Lemma 2.3].

3For a different definition of density point which generalizes the classical notion and at the same time is meaningful for the meager ideal, see [PWBW85] (we discuss this in Section 5.3).

4This connection has been explored also in [GRSS95, Zap08, Ike10, BKW18, SS18, KSZ13].

5For a given preorder ℙ, _{ℙ} , a set D ℙ is dense in ℙ if for any p ℙ there is d D with d _{ℙ} p.

6Note that if I is a σ-ideal on an arbitrary Polish space 𝔛 then there is D I such that 𝔛 D is homeomorphic to ^{ω}ω so this is not a serious restriction.

7We omit for the sake of this introduction two minor technical requirements; see Section 4.1 for the precise definition.

In Section 4.5 we shall show an analogue of Lebesgue’s Density Theorem for the class of strongly linked tree ideals which we now define. Towards this, let us use the following notation: When T is a subtree of ^{ω} X, write stem_{T} (called the stem of T) for the longest s ^{ω} X such that T N_{s}. Recall here that the product topology on ^{ω}X has the basic open sets N_{s} x ^{ω}X s x for s ^{ω} X, where means initial segment.

Definition 1.4. A collection ℙ of subtrees of ^{ω} X is called strongly linked if whenever T, T^{}ℙ and stem_{T} and stem_{T^{}}are comparable under , then T and T^{}are compatible, i.e., there is S ℙ with S T T^{}. A strongly linked tree ideal is an ideal of the form I_{ℙ} where ℙ is a strongly linked tree forcing.

To state our first main result, we write A _{I} B to mean that AΔB I for A, B P ^{ω}X .

Theorem 1.5. Let I be a strongly linked tree ideal, i.e., let I I_{ℙ} where ℙ is a strongly linked tree forcing. For A Meas ^{ω}X, ℙ define the set of I-shift density points (or short, just I-density points) of A as follows:

D_{I} A x ^{ω}X n ω m n T ℙ stem_{T} x n T A I .  (1)

Then the analogue of Theorem 1.1 holds, i.e., for any A, B Meas ^{ω}X, ℙ (A) A _{I} B D_{I} A D_{I} B , and (B) D_{I} A _{I} A.

Intuitively, as we shall see, x D_{I} A means that for every sufficiently small neighborhood N_{s} of x, A N_{s} is “very large” in some sense. We show in Section 4.6 that D_{I} also is reasonable in terms of complexity: When ℙ is analytic the map D_{I} : Meas ^{ω}X, ℙ Borel is induced by a map from Borel codes to Borel codes which is absolutely Δ_{2}^{1} and hence universally Baire measurable.

It follows immediately from Theorem 1.5 that D_{I} is a useful notion of density point for the ideals associated to Cohen forcing, Hechler forcing, eventually different forcing, Laver forcing with a filter, and Mathias forcing with a shift invariant filter (cf. Section 6). Although one can define D_{I} as in (1) for arbitrary tree ideals, we verify in Section 5.1 that Theorem 1.5 fails for ℙ equal to Sacks, Miller, Mathias, Laver, or Silver forcing.

While the null ideal is not a strongly linked tree ideal (see Remark 4.16) our methods also yield a variant of density point for the null ideal. Namely, when I I_{μ} is the ideal of null sets with respect to the Lebesgue measure μ on ^{ω}2 and ℙ is Random forcing (see Definition 6.1(a) or Example 4.1) let

D_{I} A x ^{ω}X n ω m n T ℙ

\frac{μ T N_{x n}}{μ N_{x n}} \frac{1}{2} T A I_{μ} . (2)

We show in Section 3 that D_{I} A _{μ} A for any A Meas ^{ω}2, μ .

It is also interesting and not hard to characterize the class of strongly linked tree ideals without any reference to forcing. For this, write I^{}for P ^{ω}X I, i.e., for the co-ideal associated to an ideal I on ^{ω}X and write A _{I} B to mean A B I.

Fact 1.6. A σ-ideal I on ^{ω}X is a strongly linked tree ideal if and only if

(1) There is a collection C of non-empty perfect subsets of ^{ω}X such that for any A Borel ^{ω}X , A I^{}if and only if there is C C such that C _{I} A.

(2) C is shift-invariant (or strongly arboreal) in the following sense: For all C C and all s ^{ω} X either C N_{s} or C N_{s} C.

(3) C is strongly linked: For any C_{0}, C_{1} C either there is C_{2} C with C_{2} C_{0} C_{1}

or there is s ^{ω}X and i 0, 1 such that C_{i} N_{s} and N_{s} C_{1 i} .

The reason is that ℙ C, is isomorphic to a tree forcing by (2), and using (1) and (3) one can show that I I_{ℙ} (this uses only that ℙ has the ccc; see Section 4).

1.3. No selector for the ideal of countable sets. Finally, we show that Question 1.2 does not have a positive answer in general; in fact we show that for the simplest σ-ideal, it is not possible to define a reasonable notion of density point. First, given a tree ideal I I_{ℙ} consider the equivalence relation _{I} on Meas ^{ω}X, ℙ , and note that (A) and (B) in Theorem 1.1 mean precisely that D_{I} gives one and the same representative on each equivalence class. Such a map is said to lift a selector for _{I}.

Let I be the ideal of countable sets and consider the equivalence relation on Borel ^{ω}X given by A _{I} B (i.e., AΔB is countable). We show the following result in Section 5.2:

Theorem 1.7. There is no map D: Borel ^{ω}X Borel ^{ω}X which lifts a selector for the equivalence relation _{I} on Borel ^{ω}X such that D is induced by a Baire measurable map on the set of Borel codes.

Thus under the Axiom of (Projective) Determinacy there is no (projective) such map. We also show in Theorem 5.9 that it is consistent with ZF that there is no definable map lifting a selector (if ZF is consistent), and that there is no such map in Solovay’s model.

The aim of these results is to find dividing lines between tree ideals with and without a good notion of “density point”. They show that in all analyzed cases of tree forcings ℙ the following three conditions (a)-(c) are equivalent. Moreover for any ℙ which is a strongly linked tree forcing or equal to Random or Sacks forcing, all four conditions (a)-(d) are equivalent.

(a) ℙ is σ-linked.

(b) ℙ satisfies the countable chain condition (ccc).

(c) With D_{I_{ℙ}} as in Definition 2.3 below, D_{I_{ℙ}} A _{I_{ℙ}} A for each Borel set A ^{ω}X. In other words I_{ℙ} has the density property with respect to D_{I_{ℙ}} in the sense of Definition 2.1 below.

(d) There is a simply definable map which lifts to a selector for _{I_{ℙ}}.

Whether (d) holds for other well-known forcings is an important question left open in this paper (see Section 7)

1.4. Structure of the paper. We introduce density points for ideals in Section 2 and study them for the null ideal in Section 3. We further show in Section 3.1 that one can effectively construct density points of a closed set from weights on the basic open sets. We introduce tree ideals and some of their properties in Sections 4.1 to 4.3. For instance, we show that for any tree forcing ℙ with the ω_{1}-covering property, all Borel sets are ℙmeasurable. This improves a result of Ikegami. We then prove the density property for strongly linked tree ideals in Sections 4.4 and 4.5. In Section 4.6, we determine a bound on the complexity of density operators for a large class of ccc forcings and show that they are universally Baire measurable. Section 5.1 contains counterexamples for the remaining tree forcings listed in Section 6. In Section 5.2, we prove that there is no simply definable selector for the ideal of countable sets. This is extended to a version for projective selectors from PD. Moreover, we show that it is consistent with ZF that there is no selector at all for the ideal of countable sets. Section 6 contains a list of the tree forcings we consider in this article. We end with some open questions in Section 7.

1.5. Acknowledgments. The first-listed author, formerly known as Sandra Uhlenbrock, was partially supported by FWF grant number P28157 and the second-listed author by a Marie Skłodowska-Curie Individual Fellowship with number 794020. Moreover, these two authors wish to thank the Erwin Schrödinger International Institute for Mathematics and Physics (ESI), Vienna for support during the workshop “Current Trends in Descriptive Set Theory” in December 2016. The third-listed author thankfully acknowledges support through DNRF Niels Bohr Professorship of Lars Hesselholt as well as FWF grant number F29999. The last-listed author thanks the FWF for supporting him through the grants numbered I3081 and Y1012-N35.

We would like to thank Alessandro Andretta, Martin Goldstern, Daisuke Ikegami and Luca Motto Ros for discussions, and Jindra Zapletal for suggesting to study eventually different forcing.

2. Density points for tree ideals

In this section we introduce some notation and define our notion of density point for tree ideals in a way that allows us to treat both, D_{I} as defined in (1) for strongly linked tree ideals and D_{I_{μ}}, our variant of density point for the null ideal from (2) simultaneously.

Recall that we write X 2 or X ω. We consider subtrees T of ^{ω} X and write

T x ^{ω}X n ω x n T

for the set of branches through T. A tree T is perfect if it has no end nodes and some splitting node above each node. Let

T s t X^{ω} s^{⌢}t T
s^{⌢}T s^{⌢}t t T
T_{u} t T u t t u

for s ^{ω} X and u T. Let further

σ_{s}: ^{ω} X ^{ω} X, σ_{s} x s^{⌢}x
denote the shift by s ^{ω} X. Thus σ_{s}^{1} T  T s  t s^{⌢}t T . For s, t X^{ω} , we

write s t if s is an initial segment of t. Recall that the stem stem_{T} of a tree T is the longest s T such that s t or t s for all nodes t T. The set of splitting nodes of T (those with at least two direct successors in T) is denoted split_{T}. Moreover, let s t denote the longest common initial segment of s and t.

If I is an ideal on ^{ω}X and A and B are subsets of ^{ω}X, recall that we write A _{I} B for A△B I. We also write A _{I} B for A B I and A _{I} B for A B I. An ideal on ωX is called shift invariant if it is closed under pointwise images and preimages of σ_{t} for all t ^{ω} X. For an ideal I, a set is called I-positive if it is not in I; recall that the set of I-positive sets (the co-ideal of I) is denoted I^{}.

The central notion for this article is the density property:

Definition 2.1. If I is an ideal and D is a map from the collection of Borel subsets of ^{ω}X to P ^{ω}X , we say that the density property holds (with respect to D and I) if D A _{I} A for all A.

Ideally, we would like to define a notion of density points relative to an arbitrary shift invariant ideal I on ^{ω}X. For our definition we find it necessary to fix a collection L_{I} of sets which we consider “large”; but for strongly linked ideals and for the null ideal there is a natural choice of L_{I}—namely when I I_{μ}, L_{I} is defined as the set of perfect sets of measure at least \frac{1}{2} and when I I_{ℙ} and ℙ is strongly linked, L_{I} is defined to be the set T ℙ stem_{T} .

Since we want to speak about arbitrary tree ideals in some of our results below, we make the following convention.

Convention 2.2. Let I be a tree ideal, and fix ℙ such that I I_{ℙ}. If I I_{μ} we shall assume that ℙ is Random forcing, i.e. the collection of trees T ^{ω} 2 such that for all s T, μ T N_{s} 0; further, we let

L_{I} T T ℙ, μ T \frac{1}{2} .

If ℙ is any other tree forcing then we let

L_{I} T T ℙ, stem_{T} .

We say that elements of L_{I} are large with respect to I.

Definition 2.3. Suppose that A is a subset of ^{ω}X.

(a) An element x of ^{ω}X is an I-shift density point of A if there is some n_{x} such that for

all B L_{I} and n n_{x}

σ_{x n} B A I.

(b) D_{I} A denotes the set of I-shift density points of A. We further say that an ideal I satisfies the I-shift density property if D_{I} A △A I for all Borel sets A.

For simplicity, we sometimes just write I-density point and I-density property. It is clear that by Convention 2.2, Definition 2.3 just repeats the defintion of D_{I} given in (1) for strongly linked tree ideals as well as the one in (2) for the null ideal. Note that D_{I} A is Σ_{2}^{0} for any subset A of ^{ω}X. To see this, let

S s ^{ω} X B L_{I} σ_{s} B A I

and observe that x D_{I} A m n m x n S; thus D_{I} A is Σ_{2}^{0} S .

Finally, note that in those cases where we verify the I-shift density property we obtain that D_{I} A △A I for all A Meas ℙ,^{ω}X , not just for Borel A (since in all these cases ℙ is ccc; cf. Remark 4.19).

Remark 2.4. Definition 2.3 can be rephrased in the following fashion. We call a subset A^{}of ^{ω}X I-full if for all B L_{I}, the set B A^{}is I-positive (this is analogous to the definition of stationary sets from club sets). Then x is a density point of A if and only if A x n σ_{x n}^{1} A is eventually I-full as n increases.

Remark 2.5. We notice that definition 2.3 can also be rephrased via the following notion of convergence. We say that a sequence f⃗ f_{n} n ω of functions f_{n}: ^{ω}X ℝ converges in I to a function f: ^{ω}X ℝ if the following condition holds:^{8} For all ϵ 0, there is some n_{0} such that for all B L_{I} and n n_{0},

B x ^{ω}X f_{n} x f x ϵ I.

By shift invariance, the condition σ_{x n} B A I in Definition 2.3 (a) is equivalent to B σ_{x n}^{1} A I. Moreover, B σ_{x n}^{1} A B x ^{ω}X 1_{σ_{x n}^{1} A} x 1 ϵ for any ϵ with 0 ϵ 1. Therefore x is an I-shift density point of A if and only if the functions 1_{σ_{x n}^{1} A} converge in I to the constant function with value 1.

3. The null ideal

In this section, we outline the situation in the special case of the σ-ideal on^{ω}2 of Lebesgue null sets to illustrate some ideas used in this paper.

Let μ denote the Lebesgue measure on ^{ω}2, i.e., the measure generated by the assignment μ N_{t} 2^{n} for any t ^{n}2. Recall that we write I_{μ} for the σ-ideal of μ-null sets. The next lemma implies that the I_{μ}-shift density property holds.

Lemma 3.1. Let A be a Borel subset of ^{ω}2.

8Compare this with convergence in measure in Lemma 5.10.

(1) If d_{A}^{μ} x 1 and ϵ 0, then there is some n_{x,ϵ} such that for all n n_{x,ϵ} and all Borel sets B with μ B ϵ, μ σ_{x n} B A 0.

(2) If d_{A}^{μ} x 0 and ϵ 0, then there is a Borel set B with

n σ_{x n} B A

and μ B 1 ϵ.

Proof. For the first claim, note that there is some n_{x,ϵ} with \frac{μ A N_{x n}}{μ N_{x n}} 1 ϵ for all n n_{x,ϵ}, since

d_{A}^{μ} x lim inf_{n} \frac{μ A N_{x n}}{μ N_{x n}} 1.

If B is any I_{μ}-positive Borel set of size at least ϵ, then μ σ_{x n} B A 0 for all n n_{x,ϵ}. For the second claim, let ϵ⃗ ϵ_{i} i ω be a sequence in ℝ^{}with _{i} ϵ_{i} ϵ. Since

d_{A}^{μ} x lim inf_{n} \frac{μ A N_{x n}}{μ N_{x n}} 0,

there is a strictly increasing sequence n⃗ n_{i} i ω with \frac{μ A N_{x n_{i}}}{μ N_{x n_{i}}} ϵ_{i} for all i ω.

Let B_{i} σ_{x n_{i}}^{1} A for i ω and B _{i ω} B_{i}. Then

μ B _{i} μ B_{i}  _{i} \frac{μ A N_{x n_{i}}}{μ N_{x n_{i}}}  _{i} ϵ_{i} ϵ.

Let C be an I_{μ}-positive set with μ C 1 ϵ that is disjoint from B. Then C B_{i} for all i ω. Since B_{i} σ_{x n_{i}}^{1} A , it follows that σ_{x n_{i}} C A σ_{x n_{i}} C σ_{x n_{i}} B_{i} σ_{x n_{i}} C B_{i} . □

For ϵ \frac{1}{2}, we obtain that d_{A}^{μ} x 1 implies that x is an I_{μ}-shift density point and d_{A}^{μ} x 0 implies that this fails. This yields the following corollary (by Theorem 1.1).

Corollary 3.2. For every measurable A ^{ω}2, D_{I} A _{μ} D_{μ} A . In particular, the I_{μ}-shift density property holds.

We shall give a proof of Lebesgue’s Density Theorem below in Section 3.1 making our proof of the I_{μ}-shift density property completely self-contained (cf. also Section 4.5).

In the next lemma, we give two examples which show that if d_{A}^{μ} x 0, 1 , then x can but does not have to be an I_{μ}-shift density point of A.

Lemma 3.3. Each of the following statements is satisfied by some Borel subset A of ^{ω}2 and some x ^{ω}2 with d_{A}^{μ} x 0, 1 .

(a) x is an I_{μ}-shift density point of A.

(b) x is not an I_{μ}-shift density point of A.

Proof. Let A 0^{n}^{⌢}1^{3}^{⌢}x ^{ω}2 n ω, x ^{ω}2 and B its complement.

For (a) note that d_{B}^{μ} 0^{ω} 0, 1 since \frac{μ B N_{0^{n}}}{μ N_{0^{n}}} \frac{3}{4} for all n ω. Thus μ σ_{0^{n}} C B 0 for any Borel set C with μ C \frac{1}{2}. So 0^{ω} is an I_{μ}-shift density point of B.

For (b) we have d_{A}^{μ} 0^{ω} 1 d_{B}^{μ} 0^{ω} 0, 1 . Since μ B \frac{1}{2} and σ_{0^{n}} B A for all n ω, 0^{ω} is not an I_{μ}-shift density point of A. □

3.1. An explicit construction of density points. In this section, we show how to explicitly construct density points of a closed set C of positive measure. In fact, there is an algorithm that takes as input a list of data from C and outputs a perfect tree (level by level) all of whose branches are density points. By choosing e.g. the leftmost branch, we can approximate a single density point with arbitrary precision.

The data consists of a tree T with weights w_{t} \frac{μ T N_{t}}{μ N_{t}} 0 for all t T; we call this a weighted tree. The input has the form of a Turing program with an oracle that can decide whether t T and approximate w_{t} with any given precision ϵ ℚ 0, 1 .

Theorem 3.4. There is an algorithm that computes from any weighted tree T and any q ℚ 0, 1 a subtree S of T such that S consists of Lebesgue density points of T and μ S 1 q μ T .

Note that for all strongly linked collections of trees ℙ (see Definition 4.15) listed in Section 6 and all T ℙ, S T already satisfies the conditions in the previous theorem. For these forcings, any T ℙ has the property that for all x T , there are infinitely many n ω such that there is some S T with x S and stem_{S} x n. Hence all elements of T are density points of T by the proof of Lemma 4.17 below.

Theorem 3.4 will follow from the next lemmas. To state them, we fix the following notation: Let C T , L_{t,i} Lev_{t i} T_{t} be the level of T_{t} at height t i and write

w_{t,i} \frac{L_{t,i}}{2^{i}} μ N_{t} ^{1} \frac{L_{t,i}}{2^{t i}}

for all t 2^{ω} and i ω. This is the relative size of levels of T above t. The next result shows that these values converge to the relative measure at t.

Lemma 3.5. lim_{i} w_{t,i} w_{t} for all t 2^{ω} .

Proof. We have w_{t} lim_{i} w_{t,i}, since C N_{t} _{u L_{t,i}} N_{u} and hence w_{t} w_{t,i} for all i ω. To prove that lim_{i} w_{t,i} w_{t}, suppose that ϵ 0 is given. Let U be an open set with C N_{t} U and μ U μ C N_{t} ϵ μ N_{t} . By compactness of C, we can assume that U is a finite union of basic open sets. We can thus write U _{j n} N_{s_{j}} for some s⃗ s_{j} j n that consists of pairwise incompatible sequences s_{j} of the same length t i. Since C N_{t} U, we have

w_{t,i} μ N_{t} ^{1} \frac{L_{t,i}}{2^{t i}} \frac{μ _{j n} N_{s_{j}}}{μ N_{t}} \frac{μ U}{μ N_{t}}.

Hence w_{t,i} w_{t} \frac{μ U μ C N_{t}}{μ N_{t}} ϵ by the previous inequality and the definition of w_{t}. □

For any t 2^{ω} and i ω, let

r_{t,i} inf c 0, 1 \frac{u L_{t,i} w_{u} c}{L_{t,i}} c

denote the ratio of nodes on level t i above t with large weight.

Lemma 3.6. lim inf_{i} r_{t,i} 1 for all t 2^{ω} .

Proof. Let b w_{t} and assume that c 0, 1 is given. Since b bc b 1 c c, there is some ϵ 0 with b b ϵ c b ϵ 1 c c. By Lemma 3.5, we can take i ω to be sufficiently large such that w_{t,i} b ϵ. Moreover, let α denote the fraction of nodes u L_{t,i} with weight w_{u} c. Then

b w_{t} 2^{i} _{u L_{t,i}} w_{u} w_{t,i}α w_{t,i} 1 α c.

We claim that α c. Otherwise α c and b w_{t,i}α w_{t,i} 1 α c w_{t,i}c w_{t,i} 1 c c. Since w_{t,i} b ϵ, we obtain b b ϵ c b ϵ 1 c c, contradicting the definition of ϵ. □

We need the following notion to ensure that weights converge to 1 along branches of the tree constructed below. We say that v t is t, a -good if w_{u} a for all u with t u v; otherwise it is called t, a -bad. Let

s_{t,a,i} \frac{u L_{t,i} u is t, a -good}{L_{t,i}}

denote the fraction of t, a -good nodes on level t i above t.

We fix a computable function f: ℚ 0, 1 ℚ 0, 1 such that \frac{1 b}{b b a} \frac{1 a}{a} holds for all a, b ℚ 0, 1 with b f a .

Lemma 3.7. If a ℚ 0, 1 and w_{t} b f a , then lim inf_{i} s_{t,a,i} a.

Proof. Since b f a , there is some c 0, 1 with 1 b \frac{1 a}{a} b b a c. Let i be sufficiently large such that the fraction of v L_{t,i} with w_{v} c is at least b by Lemma 3.6. Then the fraction of nodes v L_{t,i} with w_{v} c is at most 1 b and their number at most 2^{i}w_{t,i} 1 b .

Let A the set of t, a -bad nodes in L_{t,i}, U _{v A} N_{v} and α \frac{A}{L_{t,i}}. We aim to show that α 1 a. The number of t, a -bad nodes in L_{t,i} is 2^{i}w_{t,i}α. Since all of these except at most 2^{i}w_{t,i} 1 b have weight at least c, we have

2^{t i}μ C U _{v A} w_{v} 2^{i}w_{t,i}α 2^{i}w_{t,i} 1 b c.

Claim. 1 b \frac{1 a}{a} w_{t,i} α 1 b c.

Proof. For each v A, take some u_{v} with t u_{v} v and w_{u_{v}} a by the definition of t, a -bad. In particular \frac{1 w_{uv}}{w_{uv}} \frac{1 a}{a} .

Let B u_{v} v A and B^{}the set of -minimal elements of B. For each v A and u u_{v}

μ N_{u} C 2^{u} 1 w_{u} 2^{u}w_{u} \frac{1 a}{a} \frac{1 a}{a} μ C N_{u} .

Since the sets N_{u} for u B^{}are pairwise disjoint, the previous inequality implies

μ U C _{u B^{}}μ N_{u} C \frac{1 a}{a} _{u B^{}}μ C N_{u} \frac{1 a}{a} μ C U .

By this inequality and the one before the claim, we have μ N_{t} C μ U C \frac{1 a}{a} μ C U 2^{t} \frac{1 a}{a} w_{t,i}α w_{t,i} 1 b c. Since \frac{μ N_{t} C}{2^{t}} \frac{μ N_{t} C}{μ N_{t}} 1 w_{t} 1 b and μ N_{t} 2^{t}, the claim follows. □

It is sufficient to show that α 1 a. Otherwise by the previous claim and since b w_{t} w_{t,i}

1 b \frac{1 a}{a} w_{t,i} α 1 b c

\frac{1 a}{a} w_{t,i} 1 a 1 b c

\frac{1 a}{a} w_{t,i} b a c

\frac{1 a}{a} b b a c.

But this contradicts the choice of c. □

Proof of Theorem 3.4. Let a⃗ a_{i} i ω be a computable sequence in ℚ 0, 1 with i ω a_{i}^{2} 1 q. Using Lemmas 3.6 and 3.7, we will inductively construct a strictly increasing sequence n⃗ n_{i} i ω and sets S_{i} Lev_{n_{i}} T with n_{0} 0 and S_{0} by induction on i ω. The sets S_{i} are compatible levels of a tree in the sense that each t S_{i} has an extension u S_{i 1} and conversely, each u S_{i 1} extends some t S_{i}. We further let T^{i} t T u S_{i} t u u t denote the subtree of T induced by S_{i}.

We will maintain during the induction that (a) u is t, a_{i} -good for all t S_{i 1} and u S_{i 2} and (b) \frac{μ T^{i 1}}{μ T^{i}} a_{i}^{2}.

Description. This describes the construction. We simultaneously construct auxiliary numbers a_{i}^{}, a_{i}^{}, b_{i} ℚ and j_{i} ω with a_{i} a_{i}^{}a_{i}^{}b_{i} 1 and b_{i} f a_{i}^{}for all i 1. It is not hard to see that all steps are effective.

Let n_{0} 0 and S_{0} Lev_{n_{0}} T Lev_{0} T .

For i 1, we first choose some a_{1}^{}ℚ with a_{1} a_{1}^{}1 and b_{1} ℚ 0, 1 with b_{1} f a_{1}^{}. By Lemma 3.6 applied to t , there is some j_{1} with r_{,j_{1}} b_{1}. Let n_{1} j_{1} and S_{1} a subset of Lev_{n_{1}} T with w_{u} b_{1} for all u S_{1} and \frac{S_{1}}{Lev_{n_{1}} T} b_{1}. We can further

take b_{1} to be sufficiently large such that \frac{μ T^{1}}{μ T^{0}} a_{0}^{2} by r_{,j_{1}} b_{1} and the definition of r_{,j_{1}} .

Fix i 1 and assume that step i is completed. First take some a_{i 1}^{}, a_{i 1}^{}ℚ with a_{i 1} a_{i 1}^{}a_{i 1}^{}1 and 1 a_{i 1}^{}a_{i}^{}a_{i}. Let b_{i 1} ℚ 0, 1 with b_{i 1} f a_{i 1}^{}, a_{i 1}^{}, a_{i}. By Lemma 3.6, there is some j_{i 1} such that r_{t,j_{i 1}} b_{i 1} for all t S_{i}. Since b_{i} f a_{i}^{} by the inductive hypothesis and a_{i}^{}a_{i}^{}, we can take j_{i 1} to satisfy s_{t,a_{i}^{},j_{i 1}} a_{i}^{}for all t S_{i} by Lemma 3.7. Let n_{i 1} n_{i} j_{i 1} . By definition of j_{i 1} , there is a subset S_{i 1} of Lev_{n_{i 1}} T such that for all u S_{i 1} , we have w_{u} b_{i 1} , there is a (unique) t S_{i} with

t u, u is t, a_{i}^{}-good and \frac{L_{t,j_{i 1}} S_{i 1}}{L_{t,j_{i 1}}} 1 a_{i}^{}1 b_{i 1} .

Verification. We show that the algorithm computes the required tree. Clearly condition (a) is maintained in the construction. The next claim shows (b).

Claim. \frac{μ T^{i 1}}{μ T^{i}} a_{i}^{2} for all i ω.

Proof. This is clear for i 0. Let i 1 and fix any t S_{i}. Since a_{i 1}^{}b_{i 1} and by the

definition of S_{i 1} , we have \frac{L_{t,j_{i 1}} S_{i 1}}{L_{t,j_{i 1}}} 1 a_{i}^{}1 b_{i 1} 1 a_{i}^{}1 a_{i 1}^{}1 a_{i}.

Hence \frac{L_{t,j_{i 1}} S_{i 1}}{L_{t,j_{i 1}}} a_{i}.

Since each u S_{i 1} has weight at least b_{i 1} , we have c : \frac{μ T^{i 1} N_{t}}{μ T^{i} N_{t}} c^{}: a_{i}b_{i 1} .

By the definition of T^{i 1} from S_{i 1} , d : \frac{μ T^{i} N_{t} T^{i 1}}{μ T^{i} N_{t}} d^{}: 1 a_{i}. Moreover

c d 1. Since c c^{}, \frac{c d^{}}{c} 1 \frac{d^{}}{c} 1 \frac{d^{}}{c^{}}\frac{c^{}d^{}}{c^{}}. Since d d^{}and by the last

inequality \frac{c}{c d}  \frac{c}{c d^{}}\frac{c^{}}{c^{}d^{}}. Therefore c \frac{c}{c d}  \frac{c^{}}{c^{}d^{}}\frac{a_{i}b_{i 1}}{a_{i}b_{i 1} 1 a_{i}} a_{i}b_{i 1} a_{i}^{2}.

Since this inequality holds for all t S_{i}, we have \frac{μ T^{i 1}}{μ T^{i}} a_{i}^{2}. □

To see that conditions (a) and (b) are sufficient, let S be the unique perfect subtree of ^{ω} 2 with Lev_{n_{i}} S S_{i} for all i ω. This tree can be computed level by level via the algorithm above. We have lim_{i} a_{i} 1 by the definition of a⃗. Thus (a) implies that all elements of S are density points of T . Moreover, μ S inf_{i ω} μ T^{i}

i ω a_{i}^{2}μ T  1 q μ T by (b) as required.  □

The previous result also provides a different (finitized) proof of Lebesgue’s density theorem for the uniform measure on Cantor space, since any Borel set can be approximated in measure by closed subsets. To see this, note that trivially D A D ^{ω}X A for any subset A of ^{ω}X. Thus it is sufficient to show that for any Borel set A and any ϵ 0, there is a closed subset C of A with μ A C ϵ consisting of density points of A; the density property for A follows by applying this property to both A and its complement. To see that this property holds, take a closed subset B of A with μ A B \frac{ϵ}{2}. By Theorem 3.4, there is a closed subset C of B with μ B C \frac{ϵ}{2} that consists of density points of B and therefore also of A. Since μ A C ϵ, C is as required.

Note that the algorithm also produces lower bounds for weights along branches of S.

4. Tree ideals

In this section, we study ideals induced by collections of trees. We introduce the class of strongly linked tree ideals which includes various well-known ones and show that the density property holds for this class.

4.1. What is a tree ideal? A tree ideal on ^{ω}X is induced by a collection ℙ of perfect subtrees of ^{ω} X that contains ^{ω} X and T_{s} for all T ℙ and s T (we say that ℙ is shift invariant, or following [Ike10], strongly arboreal). We will always assume this condition for any collection of trees.

Any such collection of trees carries the partial order S T : S T S T . Such partial orders are also called tree forcings;^{9} some well-known examples are listed in Section 6. For instance, the null ideal is induced by the collection of Random trees, given as follows:

Example 4.1. A subtree T of ^{ω} 2 is Random if μ T_{s} 0 for all s T with stem_{T} s.

We next associate an ideal to any collection of trees as in [Ike10, Definition 2.6]. The underlying idea is based on the special case that the sets T for T ℙ form a base for a topology. In this case, ℙ is called topological and its topology is denoted τ_{ℙ}. For instance, the collection of Hechler trees (see Definition 6.1 (e)) is topological. In fact, all tree forcings of the kind studied in Section 4.5 below have this property.^{10}

Usually, one defines nowhere dense sets relative to a given topology, or equivalently, to a base of that topology. Moreover, meager sets are defined as countable unions of these sets. In the next definition, these notions are generalized by replacing a base by an arbitrary collection of trees.

Definition 4.2. [Ike10, Definition 2.6] Let ℙ be a collection of trees.

(a) A set A is ℙ-nowhere dense if for all T ℙ there is some S T with S A . Moreover, N_{ℙ} is the ideal of ℙ-nowhere dense sets.

(b) I_{ℙ} is the σ-ideal of ℙ-meager sets generated by N_{ℙ}.

Tree ideals are those of the form I_{ℙ} for a collection ℙ of trees.^{11} This presentation allows for uniform proofs of results for various ideals. Many well-known ideals are of this form; for instance, for Cohen forcing^{12} τ_{ℙ} is the standard topology, so N_{ℙ} is the collection of nowhere dense sets and I_{ℙ} that of meager sets. For Random forcing, N_{ℙ} and I_{ℙ} equal the σ-ideal of null sets. Sacks forcing is the collection of all perfect trees; here both ideals equal the Marczewski ideal (see [Szp35, 3.1]). Its restriction to Borel sets equals the ideal of countable sets by the perfect set property for Borel sets. For Mathias forcing, τ_{ℙ} is the Ellentuck topology, and N_{ℙ} and I_{ℙ} are equal to the ideal of nowhere Ramsey sets (see [BKW18]). The ideal associated to Silver forcing consists of the completely doughnut null sets (see [Hal03]).

4.2. Measurability for tree ideals. Let ℙ be a collection of trees. The next definition introduces a form of indivisibility^{13} of ℙ with respect to A: If T ℙ and T is split into two pieces by forming intersections with A and its complement, then at least one of these pieces contains a set of the form S for some S ℙ, up to some ℙ-meager set.

Definition 4.3. [Ike10, Definition 2.8]^{14} A subset A of ^{ω}X is called ℙ-measurable if for every T ℙ, there is some S T with at least one of the properties (a) S _{I_{ℙ}} A and (b) S _{I_{ℙ}} A.

Note that the properties (a) and (b) are mutually exclusive (see Lemma 4.10 below). The main motivation for introducing this notion is the fact that it formalizes various well-

known properties. For instance, we will see in Lemma 4.8 that ℙ-measurability for Random forcing means Lebesgue measurability. For Sacks forcing it is equivalent to the Bernstein property for collections of sets closed under continuous preimages and intersections with closed sets [BL99, Lemma 2.1]. Moreover, for Mathias forcing it is equivalent to being completely Ramsey.

9These forcings, but without the condition that ^{ω}X is in ℙ, are called strongly arboreal in [Ike10, Definition 2.4].

10Topological does not imply the density property. For instance, assuming CH one can construct a dense topological (shift-invariant) subforcing of Sacks forcing, while we show in Propostion 5.1 and Theorem 5.5 that the density property fails for the ideal associated to Sacks forcing.

11In [BL99, Section 2] and various other papers, tree ideals mean the ideals N_{ℙ} instead of I_{ℙ}.

12See Section 6 for this and the following forcings.

13See e.g. [LNVTPS09] for the concept of indivisibility in combinatorics.

14This is a modification of a definiton in [BHL05, Section 0].

Our next goal is to show that for a very large class of forcings, all Borel sets are ℙmeasurable. This will be important in the proofs of the following sections.

[Ike10, Lemma 3.5] shows that for proper tree forcings ℙ, all Borel sets are ℙ-measurable.^{15} We will show a slightly more general version of this result. To state this, recall that a forcing ℙ has the ω_{1}-covering property if for any ℙ-generic filter G over V, any countable set X of ordinals in V G is covered by a set in Y V that is countable in V. For instance, this statement holds for all proper and thus for all Axiom A forcings.^{16} In particular, it holds for all forcings considered in this paper.

We will need the following characterization of the ω_{1}-covering property. Here we will write D^{∥p} q D p ∥ q if D ℙ and p ℙ, where p ∥ q denotes that there is an r ℙ such that r p and r q.

Lemma 4.4. The following conditions are equivalent for any forcing ℙ:

(a) ℙ has the ω_{1}-covering property.

(b) For any condition p ℙ and any sequence D⃗ D_{n} n ω of antichains in ℙ, there is some q p such that for any n ω, the set D_{n}^{∥q} is countable.

Proof. We first assume (a). Let p ℙ and let D⃗ D_{n} n ω be as in (b). Take a ℙ-generic filter G over V. Moreover, let f n be an element of D_{n} G for each n ω. By the ω_{1}-covering property, there is a countable subset C V of ℙ such that f n C for all n ω. Let f be a name for f such that q p forces f n Č for all n ω. It follows that D_{n}^{∥q} C, since for any ℙ-generic filter H over V that contains both q and r we have

r { \atop f^{H}} n C.

For the converse implication, assume (b) and suppose that G is ℙ-generic over V and C is a countable set of ordinals in V G . Moreover, let f be an enumeration of C and f a name with { \atop f^{G}} f. Then there is a condition p G which forces that f: ω Ord is a function. For each n ω, let D_{n} be a maximal antichain of conditions deciding f n . By our assumption, there are densely many conditions q p as in (b). Hence there is some q G as in (b). Since D_{n}^{∥q} is countable for all n ω, C_{n} α r f n α for some r q, q^{}for a q^{}D_{n}^{∥q} is countable and hence C _{n ω} C_{n} is a countable cover of ran f . □

To show that all Borel sets are ℙ-measurable if ℙ has the ω_{1}-covering property, we need the next two easy lemmas. We will use the following notation. If A is a subset of ^{ω}X, let ℙ_{A} T ℙ T _{I_{ℙ}} A . We further say that a subset of ℙ is A-good if it is contained in ℙ_{A} ℙ_{A} ℙ_{^{ω}X A}.

Lemma 4.5. A subset A of ^{ω}X is ℙ-measurable if and only if there is an A-good maximal antichain in ℙ.

Proof. If A is ℙ-measurable, then ℙ_{A} is a dense subset of ℙ. Then there is a maximal antichain in ℙ contained in ℙ_{A} and hence an A-good maximal antichain. Conversely, if D is a maximal A-good antichain in ℙ and S ℙ, let T D^{∥S} and R S, T. Then R _{I_{ℙ}} A or R _{I_{ℙ}} ^{ω}X A. □

If D ℙ, write ^{}D _{T D} T .

Lemma 4.6. If D is a maximal antichain in ℙ and T ℙ, then T ^{}D^{∥T} N_{ℙ}.

Proof. Let S ℙ, R D^{∥S} and Q R, S. If Q T, then there is some P Q with

P  T  by the closure property of ℙ defined in the beginning of Section 4.1. If
Q ∥ T, let P Q, T. Since P D^{∥T}, P is disjoint from T  ^{}D^{∥T}, as required.  □

The next result shows that Borel sets are ℙ-measurable in all relevant cases.

15The proof of this and several other results in [Ike10] can also be done from the weaker assumption that ℙ has the ω_{1}-covering property. We give a more direct proof.

16See [Jec03, Definition 31.10].

Lemma 4.7. If ℙ has the ω_{1}-covering property, then the ℙ-measurable sets form a σ-algebra. In particular, all Borel sets are ℙ-measurable.

Proof. For the first claim, it suffices to show that the class of ℙ-measurable sets is closed under forming countable unions. To this end, let A⃗ A_{n} n ω be a sequence of ℙ-measurable subsets of ^{ω}X. Furthermore, let D_{n} be an A_{n}-good maximal antichain for each n ω by Lemma 4.5. We will show that A _{n ω} A_{n} is ℙ-measurable.

Fix any T ℙ. Since ℙ has the ω_{1}-covering property, there is some S T such that the sets E_{n} D_{n}^{∥S} are countable for all n ω by Lemma 4.4. First assume that for some n ω, there is a tree R E_{n} with R _{I_{ℙ}} A_{n}. Then there is some Q S with Q _{I_{ℙ}} A_{n} A as required. So we can assume that the previous assumption fails. We claim that then S _{I_{ℙ}} A. It suffices to show that S A_{n} I_{ℙ} for each n ω, since I_{ℙ} is a σ-ideal. To see this, note that R A_{n} I_{ℙ} for all R E_{n} by our case assumption. Hence ^{}E_{n} A_{n} I_{ℙ}. Moreover, S ^{}E_{n} N_{ℙ} by Lemma 4.6 and therefore S A_{n} I_{ℙ}.

Since it easy to see that closed sets are ℙ-measurable, it follows that all Borel sets are ℙ-measurable. □

Next is the observation that ℙ-measurability for Random forcing means Lebesgue measurability. We recall the argument from [Ike10] for the benefit of the reader.

Lemma 4.8. [Ike10, Proposition 2.9] If ℙ is a ccc tree forcing and A is any subset of ^{ω}X, then the following conditions are equivalent.

(a) A is ℙ-measurable.

(b) There is a Borel set B with A△B I_{ℙ}.

Proof. If A is ℙ-measurable, then ℙ_{A} is dense in ℙ. Let D ℙ_{A} be a maximal antichain in ℙ. Since D is countable, the sets B_{0} ^{}D ℙ_{A} _{I_{ℙ}} A and B_{1} ^{}D ℙ_{A} _{I_{ℙ}} ^{ω}X A are Borel. Since D is maximal, ^{ω}X ^{}D N_{ℙ} by Lemma 4.6. Thus A△B_{0} I_{ℙ}.

The reverse implication follows from the fact that all Borel sets are ℙ-measurable by Lemma 4.7. □

4.3. Positive Borel sets. The following characterization of positive Borel sets via trees will be important below. It uses an auxiliary ideal from [Ike10].

Definition 4.9. [Ike10, Definitions 2.11] A I_{ℙ}^{}if for all T ℙ, there is some S T with S A I_{ℙ}.

It is clear that I_{ℙ} I_{ℙ}^{}, but it is open whether equality holds for all proper tree forcings.^{17} Note that equality holds for ccc forcings. To see this, assume that A I_{ℙ}^{}. Then ℙ_{^{ω}X A} (as defined before Lemma 4.5) is dense in ℙ and therefore contains a (countable) maximal antichain D. We have A ^{}D I_{ℙ}. Since ^{ω}X ^{}D N_{ℙ} by Lemma 4.6, we have A I_{ℙ}. Moreover, equality holds for fusion forcings (then in fact N_{ℙ} I_{ℙ}) ^{18} and for topological tree forcings as in the proof of [FKK16, Lemma 3.8].

The next lemma characterizes I_{ℙ}^{}-positive sets.

Lemma 4.10. Suppose that ℙ is a tree forcing.

(1) For any T ℙ, T I_{ℙ}^{}.

(2) A ℙ-measurable subset A of ^{ω}X is I_{ℙ}^{}-positive if and only if there is some T ℙ with T _{I_{ℙ}^{}}A.

17To our knowledge, every known proper tree forcing satisfies either the ccc or fusion and thus equality holds.

18For a tree forcing ℙ, we define fusion as the existence of a sequence _{ n} n ω of partial orders on ℙ with _{0} which satisfy the following conditions:

(a) (decreasing) If S _{n} T and m n, then S _{m} T.

(b) (limit) If T⃗ T_{n} n ω is a sequence in ℙ with T_{n 1} _{n} T_{n} for all n ω, then there is some

S ℙ with S _{n} T_{n} for all n ω.

(c) (covering) If T ℙ, n ω and D is dense below T, then there is some S _{n} T with S ^{}D.

Proof. We show the first claim. If T I_{ℙ}^{}, then S I_{ℙ} for some S T. Let A⃗ A_{n} n ω be a sequence of sets in N_{ℙ} with S _{n ω} A_{n}. We can then recursively construct a sequence S⃗ S_{n} n ω in ℙ such that S_{0} S, S_{n 1} S_{n}, S_{n} A_{n} for all n ω and the sequence s⃗ stem_{S_{n}} n ω of stems is strictly increasing. Then x _{n ω} stem_{S_{n}} _{n ω} S_{n} . Since S_{n} A_{n} for all n ω and S _{n ω} A_{n}, we have x S . But this contradicts the fact that x S .

We now show the second claim. By the first part, it is sufficient to take any ℙ-measurable I_{ℙ}^{}-positive set A and find some S ℙ with S _{I_{ℙ}^{}}A. Assume that there is no such tree. Since A is ℙ-measurable, we have that for any T ℙ there is some S T with S _{I_{ℙ}} A. Hence A I_{ℙ}^{}by the definition of I_{ℙ}^{}. □

For ideals I of the form I_{ℙ}^{}such that ℙ has the ω_{1}-covering property, the definition of Ishift density points (Definition 2.3) of a Borel set A can now be formulated in the following way: An element x of ^{ω}X is an I-shift density point of A if there is some n_{x} such that for all B L_{I} and n n_{x}, there is some T ℙ with

T _{I} σ_{x n} B A.

Note that it is easy to see that ℙ-measurability remains equivalent if I_{ℙ} is replaced with I_{ℙ}^{}. Moreover, the ideals N_{ℙ}, I_{ℙ} and I_{ℙ}^{}remain the same if ℙ is replaced by a dense subset by the next remark.

Remark 4.11. ℙ is dense in ℚ if for every T ℙ, there is some S T in ℚ. We define ℙ and ℚ to be mutually dense if ℙ is dense in ℚ and conversely.

We claim that N_{ℙ} N_{ℚ}, I_{ℙ} I_{ℚ} and I_{ℙ}^{}I_{ℚ}^{}if ℙ and ℚ are mutually dense. To see that N_{ℙ} N_{ℚ}, take any A N_{ℙ} and T ℚ. As ℙ is dense in ℚ, there is some T^{}T in ℙ. Since A N_{ℙ}, there is some S T^{}in ℙ with S A . As ℚ is dense in ℙ, there is some S^{}S with S^{}ℚ such that S^{}A S A . Thus N_{ℙ} N_{ℚ} and I_{ℙ} I_{ℚ}. A similar argument shows I_{ℙ}^{}I_{ℚ}^{}.

Conversely, any two collections of trees ℙ and ℚ with the ω_{1}-covering property and I_{ℙ}^{}I_{ℚ}^{}are mutually dense by Lemmas 4.7 and 4.10.

4.4. An equivalence to the density property. Let I be an ideal on ^{ω}X. We say that a function D: Borel ^{ω}X Borel ^{ω}X is lifted from Borel ^{ω}X I if for any A, B Borel ^{ω}X , A _{I} B D A D B .

For instance, D_{I} as introduced in Definition 2.3 is lifted from Borel ^{ω}X I if I is shift invariant (see p. 5). Then in fact A _{I} B D_{I} A D_{I} B by the definition of D_{I}.

The I-density property for D means that D A _{I} A for all Borel sets A. We now give a useful condition for proving this for specific ideals. To state this condition, we say that D is I-compatible if A _{I} B D A _{I} D B and A _{I} B D A _{I} D B for all Borel sets A and B. We further say that D is I-positive if D A A is I-positive for all I-positive Borel sets A.

Proposition 4.12. If D: Borel ^{ω}X Borel ^{ω}X is a function that is lifted from Borel ^{ω}X I, then the following statements are equivalent.

(a) D is I-compatible and I-positive.

(b) D has the I-density property.

Proof. It is clear that the I-density property implies that D is I-positive and I-compatible. To see that these conditions imply the density property, take any Borel set A. We aim to show that D A _{I} A.

We first show that B_{0} A D A is in I. Towards a contradiction, assume that B_{0} is Ipositive. Then D B_{0} D A is also I-positive, since it contains D B_{0} B_{0} as a subset, and the latter is I-positive since D is I-positive. On the other hand, we have D B_{0} D A I since B_{0} A and D is I-compatible, contradiction.

It remains to show that B_{1} D A A is in I. Assume that B_{1} is I-positive, so that in particular D A is I-positive. The set C D B_{1} B_{1} is I-positive, since D is I-positive.

We thus obtain C _{I} D A , as C D B_{1} and we have D B_{1} _{I} D A since B_{1} _{I} A (in fact B_{1} and A are disjoint) and D is I-compatible. However, this contradicts the fact that C is I-positive and C B_{1} D A . □

4.5. Strongly linked collections of trees have the density property. To obtain the density property for D_{I_{ℙ}}, we will make two modest assumptions on ℙ. Let K_{I} denote a fixed subset of ℙ coding L_{I} (from Convention 2.2) in the sense that L_{I} T T K_{I} .

Definition 4.13. A collection ℙ of trees has the stem property if for all T ℙ and I_{ℙ}^{}-almost all x T , there are infinitely many n ω such that there is some S T with x S and S x n K_{I}.

The condition is trivially true for all x T when K_{I} T ℙ stem_{T} and we only introduce it to deal with the case of Random forcing. For Random forcing, we let K_{I} T ℙ μ T \frac{1}{2} . Then the stem property follows from Theorem 3.4 or Lebesgue’s density theorem.

The next lemma shows that D_{I} is I-compatible for I I_{ℙ}^{}provided that D_{I} is I-positive and ℙ has the stem property.

Lemma 4.14. Assume that ℙ is a collection of trees with the stem property, all Borel sets are ℙ-measurable, I I_{ℙ}^{}and D_{I} T I for all T ℙ. Then D_{I} A D_{I} B _{I} D_{I} A B for all Borel sets A, B.

Proof. It is easy to see that D_{I} A B D_{I} A D_{I} B , so suppose towards a contradiction that there are Borel sets A, B with C D_{I} A D_{I} B D_{I} A B I. Since C is Borel (it is a Boolean combination of Σ_{2}^{0} sets) and hence ℙ-measurable, by Lemma 4.10 there is some S_{0} ℙ with S_{0} _{I} C.

Since S_{0} _{I} D_{I} A we can pick x S_{0} D_{I} A witnessing the stem property for S_{0}. Let n_{x} ω witness that x D_{I} A . By the choice of x, there is some m n_{x} and S_{1} S_{0} with S_{1} x m K_{I}. Since m n_{x}, S_{1} A I. By Lemma 4.10, there is some S_{2} ℙ with S_{2} _{I} S_{1} A.

Thus S_{2} _{I} C D_{I} B . Repeating the previous argument with A replaced by B yields some S_{3} ℙ with S_{3} _{I} S_{2} B.

Since S_{3} _{I} A B, we have D_{I} S_{3} D_{I} A B , Note that D_{I} S_{3} S_{3} S_{0} . As D_{I} S_{3} I by our assumption, this contradicts the fact that S_{0} was chosen so that S_{0} D_{I} A B I. □

To obtain I-positivity we assume the following property.

Definition 4.15. A collection of trees ℙ is called strongly linked if any S, T ℙ with stem_{S} stem_{T} and stem_{T} S are compatible in ℙ.

This condition holds for all ccc tree forcings that we study except Random forcing. For instance for Hechler forcing, eventually different forcing, Laver forcing 𝕃_{F} with a filter and Mathias forcing ℝ_{F} with a shift invariant filter. Clearly the condition implies that ℙ is σ-linked and ccc.

Remark 4.16. Random forcing doesn’t have a strongly linked dense subset. To see this, assume that 𝔹^{}is strongly linked and dense in 𝔹. Let S 𝔹^{}and t S with stem_{S} t and \frac{μ S N_{t}}{μ N_{t}} 1. For example, such a t S exists if S is nowhere dense. Let further

A N_{t} S . Since \frac{μ A N_{t}}{μ N_{t}} 0, there is some T 𝔹 with T A and t stem_{T}. Since 𝔹^{}is dense in 𝔹, we can assume that T 𝔹^{}. Then stem_{S} stem_{T}, but S and T are incompatible.

Lemma 4.17. Assume that ℙ is a strongly linked tree forcing—whence by Convention 2.2 L_{I} T ℙ stem_{T} . Moreover assume that I I_{ℙ}^{}. Then D_{I} is I-positive. In fact for any T ℙ, all x T are I-density points of T .

Proof. Let x T be given. Then there is some m ω such that letting T^{}T_{x m}, stem_{T^{}}x m. It is sufficient to show that x is an I-density point of T . To see this, suppose that S ℙ is such that stem_{S} x n for some n m. Since the stems of S and T^{}are compatible, stem_{S} T^{}, and ℙ is strongly linked, S and T^{}are compatible. Then S T^{}and thus also S T are I-positive sets as required. □

This implies a version of Lebesgue’s density theorem.

Corollary 4.18. I_{ℙ}^{}has the density property for any strongly linked tree forcing with the stem property. In particular, I_{ℙ} has the density property for Cohen forcing ℂ, Hechler forcing ℍ, eventually different forcing 𝔼, Laver forcing 𝕃_{F} with a filter and Mathias forcing ℝ_{F} with a shift invariant filter.

For Random forcing, the I_{μ}-density property follows from Lemma 3.1 and Lebesgue’s density theorem. An alternative proof (which does not appeal to Lebesgue’s density theorem) is now obtained via Lemma 3.1, Theorem 3.4 and Proposition 4.12.

Note that if ℙ is topological and I_{ℙ} has the density property, then one can describe D_{I_{ℙ}} A as follows using τ_{ℙ}. First note that I_{ℙ} I_{ℙ}^{}by the proof of [FKK16, Lemma 3.8]. Moreover, for any Borel set A there is some τ_{ℙ}-open set U with A△U τ_{ℙ}-meager by the τ_{ℙ}-Baire property. Since I_{ℙ} equals the set of τ_{ℙ}-meager sets, D_{I_{ℙ}} A is almost equal to a τ_{ℙ}-open set. However, note that even for ccc collections it is not clear how to find such a set in a simply definable way.

We conclude this section with some observations about other variants of the Definition 2.3 of density points and the density property.

Remark 4.19. If ℙ is ccc and the density property holds for all Borel sets, then it already holds for all ℙ-measurable sets. This is the case because any ℙ-measurable set equals A△B for some Borel set A and some B I_{ℙ} by the ccc and Lemma 4.8.

Remark 4.20. (a) If we let L_{I} I^{}be the I-positive sets for Hechler forcing ℍ and I I_{ℍ}, then the density property fails. To see this, let T be the Hechler tree with empty stem given by the constant function with value 1. With this variant T does not satisfy the density property, since no x T is an I-shift density point of T , as witnessed by N_{0} L_{I}.

(b) If n_{0} depends on B L_{I} in Definition 2.3, then the density property fails for I_{ℍ} as well. To see this, let x be the function with x n n 1 for all n ω and let T_{,x} be the tree with empty stem given by x. Let further A _{t ^{ω} ω} T_{t^{⌢} t ,t^{⌢} t ^{⌢}0^{}}; this contains all y ^{ω}ω with y n n for some n ω. It is sufficient to show T_{,x} D A A by Lemma 4.10.

It is easy to see that T_{,x} A , since any y T_{,x} satisfies y n n 1 for all n ω.

We now claim that y D A for all y ω^{ω}. So take any I_{ℍ}-positive Borel set B. It is sufficient to assume that B T_{s,u} for some s ^{ω} ω and u ^{ω}ω by Lemma 4.10. Then for any n u s ), σ_{y n}^{1} T_{s,u} s A y n ^{⌢} T_{s,u} s A contains T_{t,t^{⌢}v} for t y n^{⌢} n and v ^{ω}ω with v i u s i 1 for all i ω. Hence it is I_{ℍ}-positive and thus y is a density point of A.

4.6. Complexity of the density operator. In this section, we give an upper bound for the complexity of the operator D_{I} for relevant cases of tree ideals I of the form I_{ℙ}. K_{I} is fixed as in the previous section.

A definable forcing ℙ is called absolutely ccc if the ccc holds in all generic extensions. A Δ_{2}^{1} predicate is absolutely Δ_{2}^{1} if its Σ_{2}^{1} and Π_{2}^{1} definitions are equivalent in all generic extensions.

Lemma 4.21. Suppose that I I_{ℙ}, where ℙ, _{ℙ} and _{ℙ} are Σ_{1}^{1}, K_{I} is a Σ_{1}^{1} subset of ℙ and ℙ is absolutely ccc. Then

D_{I} : Borel ^{ω}X Borel ^{ω}X

is induced by an absolutely Δ_{2}^{1} function from Borel codes to Borel codes.

Proof. Let B denote the Π_{1}^{1} set of Borel codes and B_{x} the set coded by a Borel code x. Let φ x denote the Π_{2}^{1} formula x B & T K_{I} B_{x} T I. Let ψ x denote the Σ_{2}^{1} statement: x B and there is some m ω and a sequence T⃗ T_{i} i m from ℙ with i m T_{i} _{I} B_{x} and T L_{I} i m T ∥_{ℙ} T_{i}.

Claim. x φ x ψ x .

Proof. If φ x holds, inductively define an antichain T⃗ T_{ξ} ξ θ from ℙ with T_{ξ} _{I_{ℙ}} B_{x} for all ξ θ. Suppose that T⃗^{α} T_{ξ} ξ α is already defined. If there is T L_{I} which is incompatible with each element of T⃗^{α}, we may find T_{α} ℙ with T_{α} T and T_{α} B_{x} since Φ x holds. We can thus extend the antichain by adding T_{α}. By the ccc we must reach some θ ω_{1} such that each T L_{I} is compatible to an element of T⃗ T_{ξ} ξ θ . Enumerate T⃗ in order type m ω to obtain a witness to ψ x .

If conversely ψ x holds, then for any T K_{I} we may find some i ω with T_{i} ∥ T and T_{i} _{I} B_{x}, so one can infer B_{x} T I from Lemma 4.10. Thus φ x holds. □

We now check that φ x is a Π_{2}^{1} and ψ x a Σ_{2}^{1} formula. First note that the statement B_{x} N_{ℙ} is Σ_{2}^{1}, since this holds if and only if there is a (countable) maximal antichain S⃗ S_{i} i m in ℙ with B_{x} _{i m} S_{i} . Since I I_{ℙ} is the σ-ideal generated by N_{ℙ}, the statements B_{x} I and T _{I} B_{x} are Σ_{2}^{1} as well. The claim follows.

Since ℙ is absolutely ccc, the argument above shows that x Φ x Ψ x is absolute to generic extensions. Given a Borel code x, we can thus determine S_{x} s ^{ω} X T K_{I} σ_{s} T B_{x} I in an absolutely Δ_{2}^{1} fashion. From this, we can compute a Borel code for D_{I} B_{x} . □

We want to point out that the previous lemma remains true with virtually the same proof if we replace absolutely ccc and absolutely Δ_{2}^{1} by provably ccc and provably Δ_{2}^{1}.

We now show that for all strongly linked tree forcings listed in Section 6, the density operator D_{I_{ℙ}} is induced by a universally Baire measurable function.

Recall that a forcing is called Suslin if ℙ, _{ℙ} and _{ℙ} are Σ_{1}^{1}. Also recall that a subset A of ^{ω}ω is called universally Baire if for any topological space Y and any continuous function f: Y ^{ω}ω, f^{1} A has the property of Baire. A function f: A B between subsets of ^{ω}ω is called universally Baire measurable if f^{1} U is universally Baire for every relatively open subset U of B. Note that all universally Baire sets have the Baire property, are Lebesgue measurable and Ramsey [FMW92, Theorem 2.2].

Proposition 4.22. For any strongly linked Suslin tree forcing ℙ, D_{I_{ℙ}} is induced by a universally Baire function.

Proof. If ℙ is strongly linked, then S ∥ T if and only if stem_{S} and stem_{T} are compatible, so ℙ is arithmetical and hence Σ_{1}^{1}. Moreover, the fact that a Suslin tree forcing is strongly linked is Π_{2}^{1} and hence absolute. Thus D_{I_{ℙ}} is induced by an absolutely Δ_{2}^{1} function on the Borel codes by Lemma 4.21. Any such function is universally Baire measurable by [FMW92, Theorem 2.1]. □

5. Ideals without density

In this section, we study various counterexamples to density properties.

5.1. Counterexamples. We first give counterexamples to the density property in Definition 2.3 for several non-ccc tree forcings.

Proposition 5.1. Let ℝ, 𝕍, 𝕊 denote Mathias, Silver and Sacks forcing. Then I_{ℝ}, I_{𝕍} and I_{𝕊} do not have the shift density property.

Proof. To see that I_{ℝ} does not have the I_{ℝ}-shift density property, let A f ^{ω}2 f 2n 1 1 for all n ω . Note that A S for some S ℝ and hence A I_{ℝ}. We aim to show that no x A is an I_{ℝ}-density point of A, i.e. A D_{ℝ} A . Then in particular A△D_{ℝ} A A D_{ℝ} A I_{ℝ}.

Let x A be arbitrary and let T ℝ be a perfect tree such that split T 2ℕ and t^{⌢}i^{⌢}j T iff j 0 for all t split T and i, j 0, 1 . In particular stem_{T} . Let n_{0} ω be arbitrary and let n n_{0} be even. Then f_{x n} T A and thus x is not an I_{ℝ}-density point of A.

As ℝ 𝕍 𝕊, the claim also holds for I_{𝕍} and I_{𝕊}. □

The following is a similar counterexample for Laver and Miller forcing.

Proposition 5.2. Let 𝕃, 𝕄 denote Laver and Miller forcing. Then I_{𝕃} and I_{𝕄} do not have the shift density property.

Proof. Let A f ω^{ω} f n is even for all n ω . Then A S for some S 𝕃 so in particular A I_{𝕃}. We aim to show that no x A is an I_{𝕃}-density point of A, i.e. A D_{𝕃} A . As above this implies A△D_{𝕃} A I_{𝕃}.

Let x A be arbitrary and let T 𝕃 be a perfect tree such that stem_{T} and T g ω^{ω} g n is odd for all n ω . Let n_{0} ω be arbitrary and let n n_{0}. Then f_{x n} T A and thus x is not an I_{𝕃}-density point of A.

Since 𝕃 𝕄, the claim for I_{𝕄} follows. □

5.2. Selectors modulo countable. We now study the ideal I of countable sets. In contrast to the previous results, we will show that there is no Baire measurable selector with Borel values for the equivalence relation of having countable symmetric difference on the set of Borel subsets. This implies that the density property fails for I for any reasonable notion of density points.

To state the result formally, we need the following notions. A selector for an equivalence relation E^{}is a function that chooses an element from each equivalence class. We generalize this notion by replacing equality with a subequivalence relation E of E^{}.

Definition 5.3. Suppose that E E^{}are equivalence relations on a set Y and X Y. A selector for E^{}E on X is an E^{}, E -homomorphism X Y that uniformizes E^{}.

Equivalently, the induced map on Y E is a selector for the equivalence relation on Y E induced by E^{}.

In the following, E will be equality of decoded sets, E^{}the equivalence relation of having countable symmetric difference, X the set of F_{σ}-codes and Y the set of Borel codes.

More precisely, Λ_{F_{σ}} denotes the set of F_{σ}-codes (sequences T⃗ T_{n} n ω where T_{n} is a subtree of 2^{ω} for each n), Λ the set of Borel codes and B_{x} the Borel set coded by x Λ. We can assume that Λ_{F_{σ}} Λ. Let E_{}denote the equivalence relation on Λ of equality of decoded sets, i.e. x, y E_{}B_{x} B_{y}. Let further x, y E_{I} B_{x}△B_{y} I for x, y Λ.

Definition 5.4. A selector for I with Borel values is a selector for E_{I} E_{}on Λ_{F_{σ}}.

The motivation for this definition is as follows. Consider any notion of density points for I with Borel values, i.e. such that for any Borel set A the set of density points of A is Borel. If the density property holds for this notion, then it induces a selector for I on the set of Borel codes.

The restriction to F_{σ}-codes is purely for the technical reason that it is already sufficient to show that no such selectors exist.

Theorem 5.5. There is no Baire measurable selector for I with Borel values.

Note that this result is analogous to the fact that E_{0} does no have a Baire measurable selector. The proof for E_{0} is a short argument, see for example [Hjo10, Example 1.6.2].

The idea of the proof is to add an F_{σ} set B_{C} _{n ω} T_{n} by forcing over a countable elementary submodel M of H_{ω_{1}}. One then shows that the properties of a selector are not satisfied on the E_{I}-equivalence class of B_{C}. The trees T_{n} will be added by the following forcing 𝕋. The conditions in 𝕋 are finite subtrees t of 2^{ω} , ordered by end extension. Moreover, we let T denote a name for the generic tree G that is added by a 𝕋-generic filter G. Note that 𝕋 is equivalent to Cohen forcing, since it is countable and non-atomic. We include a proof of the following well-known fact for the reader’s convenience.

Lemma 5.6. Assume that G is 𝕋-generic over V. Then in any further generic extension, any two branches in { \atop T^{G}} are mutually Cohen generic over V.

Proof. Assume that ℚ is a 𝕋-name for a forcing and 1_{𝕋 ℚ} forces that σ and τ are distinct branches in T. Let further D be a dense subset of Add ω, 1 ^{2} and

E p, q 𝕋 ℚ u, v D p, q _{𝕋 ℚ} u σ & v τ .

It is sufficient to show that E is a dense subset of 𝕋 ℚ. To this end, assume that a condition p, q 𝕋 ℚ is given. By extending it, we can assume that p, q _{𝕋 ℚ} u σ & v τ for two incompatible u, v 2^{ω} . We first add all direct successors to end nodes of p to add another splitting level. It is easy to see that one can successively extend each pair of new end nodes to an element of D to obtain a condition r _{𝕋} p with r, q in E. □

Proof of Theorem 5.5. Suppose that there is a selector F on Λ_{F_{σ}} as in the statement of the theorem. Since F is Baire measurable, there is a comeager G_{δ} subset A of Λ_{F_{σ}} such that F A is continuous. Let x_{A} be a real that codes this restriction. Moreover, let M H_{ω_{1}} be countable with x_{A} M.

The following items are defined in M. Let 𝕋^{ω} denote the finite support product of ω copies of 𝕋, T⃗ { \atop T_{n}} n ω a sequence of 𝕋^{ω}-names for the generic trees and C a 𝕋^{ω}-name for the canonical F_{σ}-code for _{n ω} { \atop T_{n}} . Let further F be a 𝕋^{ω}-name for the continuous function coded by x_{A}. Then { \atop F^{g}} x F x for all x A M g and 𝕋^{ω}-generic filters g over M in V.

Claim. 1 _{𝕋^{ω}}^{M} { \atop T_{n}} B_{F C} for all n ω.

Proof. Assume towards a contradiction that p _{𝕋^{ω}}^{M} { \atop T_{n}} B_{F C} for some p 𝕋^{ω} and some n ω. Since A is comeager, there is a 𝕋^{ω}-generic filter g over M with p g and { \atop C^{g}} A.

Then { \atop F^{g}} { \atop C^{g}} F { \atop C^{g}} and B_{{ \atop F^{g}} { \atop C^{g}}} B_{F { \atop C^{g}}}. We have M g { \atop T_{n}^{g}} B_{{ \atop F^{g}} { \atop C^{g}}} and

hence { \atop T_{n}^{g}} B_{F { \atop C^{g}}} { \atop T_{n}^{g}} B_{{ \atop F^{g}} { \atop C^{g}}} by Π_{1}^{1}-absoluteness between M g and V. But this contradicts the assumption that F is a selector. □

By the maximum principle, there is a 𝕋^{ω}-name σ M for an element of { \atop T_{0}} B_{F C}. We now proceed as follows. We first rearrange a given 𝕋^{ω} Add ω, 1 -generic extension

M g h of M as a 𝕋^{ω} Add ω, 1 -generic extension M G H such that σ^{G} is equal to the Cohen real given by h and { \atop C^{G}} and { \atop C^{g}} are in the same E_{}-equivalence class. We then use this to show that B_{F { \atop C^{g}}} B{ \atop C^{g}} contains all Cohen reals in V over M g and hence is uncountable. But this contradicts the fact that F is a selector for E_{I}.

To this end, we will use the following forcings. Let 𝕋_{σ} be the forcing that consists of all conditions p, s , where p 𝕋 and s is a maximal branch in p such that q p q s σ. It is ordered by pointwise extension. Moreover, let ℙ_{σ} be the finite support product of 𝕋_{σ} and ω copies of 𝕋. Since 𝕋^{ω} is separative, its Boolean completion exists and ℙ_{σ} is a dense subset. We will also need the following forcing 𝕋_{}, which adds a 𝕋-generic tree and simultaneously shoots a branch through it. The conditions in 𝕋_{}are pairs p, s , where p 𝕋 and s is a maximal branch in p.

Now let ℙ_{}denote the finite support product of 𝕋_{}and ω copies of 𝕋. Let τ be a name for the branch added by 𝕋_{}. In the following claims, we will translate values of σ (when forcing with ℙ_{σ}) to those of τ (when forcing with 𝕋_{}) and conversely. Note that the sets of values of σ and of τ are not necessarily equal, since σ could for instance be the leftmost branch of { \atop T_{0}} and is then different from τ. However, we can translate values of τ to those of σ if they are compatible with the information forced about σ. Therefore, we need to introduce the following notation. For any p 𝕋^{ω}, let σ_{p} denote the unique maximal sequence w 2^{ω} with p _{𝕋^{ω}} w σ and T_{σ} σ_{p} p 𝕋^{ω} the set of possible initial segments of σ, as decided by conditions in 𝕋^{ω}. Moreover, let U_{σ} denote the set of w 2^{ω} such that T_{σ} is dense above w.

Claim. U_{σ} is a nonempty open subset of 2^{ω} .

Proof. It is clear that U_{σ} is open. To see that it is nonempty, assume towards a contradiction that T_{σ} is nowhere dense. For every u 2^{ω} , let v v_{u} be an extension of u such that C_{v} w 2^{ω} v w is disjoint from T_{σ}. Then D _{u 2^{ω}} C_{v_{u}} is an open dense subset of Cohen forcing. Since σ is a name for a Cohen real, it follows that for any Cohen generic g over M, there is some u with v_{u} σ^{g}. But this contradicts the fact that σ^{g} T_{σ} . □

Claim. (a) Every 𝕋^{ω} Add ω, 1 -generic extension M G H is equal to a ℙ_{}Add ω, 1 -

generic extension M g h with σ^{G} τ^{g} and B{ \atop C^{G}} B{ \atop C^{g}}.

(b) Every ℙ_{}Add ω, 1 -generic extension M g h with τ^{g} n U_{σ} for some n ω is equal to a 𝕋^{ω} Add ω, 1 -generic extension M G H with σ^{G} τ^{g} and B{ \atop C^{G}} B{ \atop C^{g}}.

Proof. To prove the first claim, we will define a projection from a dense subset D_{σ} of ℙ_{σ} Add ω, 1 to ℙ_{}Add ω, 1 . We refer to [Cum10, Definition 5.2] for the definition of projections. To define D_{σ}, we associate to each p⃗, q ℙ_{σ} Add ω, 1 with p⃗ p_{0}, s_{}, p_{1}, …, p_{k} a strictly increasing sequence of indices which single out certain trees p_{i} for 1 i k. Let s_{i} stem_{p_{i}} for all i k. If u, v are incompatible elements of 2^{ω} , we will also write dir u, v for the unique node below v that is a direct successor of u v.

A sequence n⃗ n_{i} i l is called a gluing sequence for p⃗, q if the following conditions hold. The first value n_{0} is least such that q 2n_{0} 1, s_{n_{0}} is incompatible with s_{}and dir s_{}, s_{n_{0}} p_{0}. Moreover, for all i l the value n_{i 1} is least with n_{i 1} n_{i}, q 2n_{i 1} 1, s_{n_{i 1}} is incompatible with s_{}, dir s_{}, s_{n_{i 1}} p_{0} and s_{n_{i 1}} s_{}is a proper end extension of s_{n_{i}} s_{}. For every condition p⃗, q ℙ_{σ} Add ω, 1 , there is a unique maximal gluing sequence we denote by n⃗ n⃗_{p⃗,q} n_{i} i n_{p⃗,q} . We define p⃗, q D_{σ} to hold if n_{l} k max dom q for l n_{p⃗,q}.

We now define a projection π: D_{σ} ℙ_{}Add ω, 1 that glues these trees to p_{0}. We define π p⃗, q for p⃗ p_{0}, s_{}, p_{1}, …, p_{k} as follows. Let J J_{p⃗,q} 0 n_{i} i n_{p⃗,q} and let m⃗ m⃗_{p⃗,q} m_{i} i m_{p⃗,q} be the order preserving enumeration of k 1 J. Now let π p⃗, q t⃗, u where t⃗ t_{0}, t_{}, t_{1}, …, t_{m} , t_{0} _{i J} p_{n_{i}}, t_{i 1} p_{m_{i}} for i m_{p⃗,q} and u the sequence of odd digits of q.

Subclaim. π is a projection.

Proof. It is clear that π is a homomorphism. To see that π is a projection, suppose that

π p⃗, q  t⃗, u , v⃗  v_{0}, v_{}, v_{1}, …, v_{l}  t⃗ t_{0}, t_{}, t_{1}, …, t_{k} and w u. We need to
find some a⃗, b  p⃗, q with π a⃗, b  v⃗, w . Let m⃗ m⃗_{p⃗,q}, n⃗ n⃗_{p⃗,q} and J J_{p⃗,q} be

as above. Let end p_{i} denote the set of all elements of 2^{ω} that are compatible with some maximal node in p_{i}. In other words, end p_{i} is the union of all end extensions of p_{i}.

We now define a_{i} for i l. Let a_{0} r v_{0} t_{}r r v_{}and note that a_{0}, v_{}is a condition in 𝕋_{σ}. If 1 i k and i J, we let a_{i} v_{0} end p_{i} . If 1 i k and i J, then i m_{j} for some j m_{p⃗,q} and we let a_{i} v_{m_{j}}. Let further a_{i} v_{i J 1} if k i l. Moreover, let j be the number of direct successors in v_{0} of nodes strictly below v_{}at or above t_{}that are incompatible with v_{}. The subtrees of v_{0} through each of these stems are missing in t_{0} and we add them as a_{i} for l i l j. Let a⃗ a_{0}, s_{}, a_{1}, …, a_{l j} . We can further assume that j w q by extending v_{0}, v_{}. We finally extend q to b by adding j even digits with value 1, w q odd digits of w above q and j w q arbitrary odd digits.

Since n_{i} k max dom q for i n_{p⃗,q} by the definition of D_{σ}, the choice of a_{0}, a_{i} for l i l j and b implies that the first coordinate of π a⃗, b is equal to v_{0}, v_{}. Hence π a⃗, b v⃗, w as required. □

Since π is a projection, there is a ℙ_{}-generic filter g over M in M G H with σ^{G} τ^{g} and B{ \atop C^{G}} B{ \atop C^{g}}. It is clear that M g M G H because of the second coordinate of the projection. Hence the quotient forcing for M g in M G H is non-atomic. Since 𝕋^{ω} Add ω, 1 is countable, the quotient forcing has a dense subset that is isomorphic to Cohen forcing. This shows (a).

We now complete the proof of the claim by showing (b). Note that for any 𝕋_{}Add ω, 1 - generic filter g h over M, the quotient forcing for τ^{g} in 𝕋_{}Add ω, 1 is countable and non-atomic, therefore it has a dense subset that is isomorphic to Cohen forcing. Assuming that the claim fails, there is some r U_{σ} that forces as a Cohen condition that in any further Cohen extension, the required rearrangement doesn’t exist. In other words, for every 𝕋_{}Add ω, 1 -generic extension M g h with τ^{h} n r for n r , there is no such rearrangement. Since r U_{σ}, T_{σ} is dense above r and hence there is some p T_{σ} with σ_{p} r. Now let G H be 𝕋^{ω} Add ω, 1 -generic over M with p G. Then M G H can be rearranged as M g h with σ^{G} τ^{h} and B{ \atop C^{G}} B{ \atop C^{g}} by the first claim. Hence τ^{h} n σ^{G} n r, but this contradicts the choice of r. □

Let θ be a 𝕋^{ω} Add ω, 1 -name for the Cohen real in the second coordinate.

Claim. (a) Every 𝕋^{ω} Add ω, 1 -generic extension M G H is equal to a ℙ_{}Add ω, 1 -

generic extension M g h with θ^{H} τ^{g} and B{ \atop C^{g}} B{ \atop C^{G}} θ^{H} .

(b) Every ℙ_{}Add ω, 1 -generic extension M g h is equal to a 𝕋^{ω} Add ω, 1 -generic extension M G H with θ^{H} τ^{g} and B{ \atop C^{g}} B{ \atop C^{G}} θ^{H} .

Proof. To prove the claim, we will define a projection ρ: D ℙ_{}Add ω, 1 , where D is a dense subset of 𝕋^{ω} Add ω, 1 . We first define D as follows. Suppose that p⃗, q 𝕋^{ω} Add ω, 1 and supp p⃗ dom q 0, k for some k 1. Let p⃗ p_{i} i k and s_{i} stem_{p_{i}} for i k. Note that if all nodes in p_{i} are compatible, then s_{i} p_{i}. We associate a splitting sequence n⃗ n⃗_{p⃗,q} n_{i} i n to p⃗, q as follows. Let n_{0} be least such that s_{n_{0}} is incompatible with q and s_{n_{0}} q . If n_{i} is already defined, let n_{i 1} be least such that s_{n_{i 1}} is incompatible with q, n_{i 1} n_{i} and s_{n_{i 1}} q is a proper end extension of s_{n_{i}} q. There is a unique maximal splitting sequence n⃗ n⃗_{p⃗,q} n_{i} i n_{p⃗,q} . We now let p⃗, q D if n_{p⃗,q} k, i.e. p_{k} appears in the splitting sequence.

The projection constructs a tree from the splitting sequence. Given any p⃗, q D, we now define ρ p⃗, q t⃗, u with t⃗ t_{0}, t_{}, t_{1}, …, t_{l} . Let t_{0} _{i k} p_{n_{i}} q j j q and t_{}q. If m⃗ m⃗_{p⃗,q} m_{i} i m_{p⃗,q} is the order preserving enumeration of 0, k n_{i} i n_{p⃗,q} , let t_{j 1} p_{m_{j}} for j m_{p⃗,q}. Since s_{n_{k}} is incompatible with q, t_{0}, t_{} is a condition in 𝕋_{}and hence ρ p, q 𝕋_{}Add ω, 1 . Moreover, let u i 0 if m_{i} is even and u i 1 if it is odd for all i m_{p⃗,q}.

Subclaim. ρ is a projection.

Proof. It is clear that ρ is a homomorphism. To see that ρ is a projection, suppose that

ρ p⃗, q  t⃗, u with t⃗  t_{0}, t_{}, t_{1}, …, t_{l} , v⃗  v_{0}, v_{}, v_{1}, …, v_{m}  t⃗ and w u. We
will find some a⃗, b  p⃗, q with ρ a⃗, b v⃗, w and start with defining a⃗. Let a_{m_{i}} v_{i}

for 1 i m_{p⃗,q} and a_{n_{i}} v_{0} end p_{n_{i}} for i k. It remains to define a_{i} for i k. To this end, consider the set K of all nodes in v_{0} that are direct successors of nodes in t_{}, v_{}r 2^{ω} t_{}r v_{}, but incompatible with v_{}. Note that K contains at most one node of each length. Let r⃗ r_{i} i j enumerate the elements of K in the order of increasing length. We define a_{k i 1} v_{0} end r_{i} for i j. We can assume that dom w dom u j by extending v_{0}, v_{}. Using this, we add the trees v_{i} for k i k j to a⃗ in this order and for each of them, we first add a tree to the splitting sequence to adjust the parity, if necessary. We thus obtain b v_{}and an extension a⃗ of the previously defined values with a⃗, b p⃗, q and ρ a⃗, b v⃗, w . □

The (a) and (b) in the last claim about rearranging M G H as M g h and conversely now follow similarly as in the proof of the previous claim. □

Finally, there is a 𝕋^{ω}-generic filter g over M in V with C { \atop C^{g}} A, since A is comeager. We pick some p U_{σ} and let h be any Cohen generic filter over M g in V with p h and let x h. Since x is a Cohen real over M g , it is easy to see by a density argument that x B_{C}. Since p U_{σ}, the previous two claims show that we can rearrange M g h as a 𝕋^{ω} Add ω, 1 -generic extension M G H with σ^{G} x. We have σ^{G} B_{F C} by the choice of σ and Borel absoluteness between M G and V. Thus B_{F C} B_{C} contains every Cohen real over M g in V and hence it is uncountable by Lemma 5.6. But this contradicts the assumption that F is a selector. □

The next results use the following principle. Let internal projective Cohen absoluteness (IA_{proj}^{ℂ}) denote the statement that H_{ω_{1}}^{M g} H_{ω_{1}} holds for all sufficiently large regular cardinals θ, countable elementary submodels M H_{θ} and Cohen generic filters g over M in V.

We will only need the first part of the next lemma; the second part is an easy observation. Recall that PD denotes the axiom of projective determinacy.^{19}

Lemma 5.7. (1) PD implies IA_{proj}^{ℂ}.

(2) If IA_{proj}^{ℂ} holds, then all projective set have the property of Baire.

Proof. (1) Take a Σ_{2n}^{1}-universal Σ_{2n}^{1} subset A_{n} of ^{ω}2 ^{2} for each n 1. If the Σ_{2n}^{1}-formula φ_{n} x, y defining A_{n} is chosen in a reasonable way, then for any Σ_{2n}^{1}-formula ψ x with (hidden) real parameters, there is some y_{ψ} ^{ω}2 with x ψ x φ_{n} x, y_{ψ} . Moreover, this holds in all transitive models of ZFC^{}and the map ψ y_{ψ} is absolute between such models. We assume that in any transitive model of ZFC^{}, A_{n} denotes the set defined by φ_{n} x, y .

Let M H_{θ} be a countable elementary submodel for some large enough regular cardinal θ. By [Mos09, Corollary 6C.4] and PD, there is a Σ_{2n}^{1}-scale σ_{n} _{n}^{m} m ω on A_{n} for each n 1. Let r_{n}^{m} x denote the rank of x A_{n} with respect to _{n}^{m}. Moreover, recall that the tree of the scale σ_{n} is defined as^{20}

T_{σ_{n}}  x m, r_{n}^{0} x , ..., r_{n}^{m 1} x  x A_{n}, m ω

and p T_{σ_{n}} A_{n}. Since ZFC^{}PD is sufficient to prove the existence of such scales, let T_{σ_{n}} denote the tree defined via φ_{n} x, y in any transitive model of this theory containing P ω as an element. Let g V be Cohen generic over M.

Claim. M g A_{n} p T_{σ_{n}} .

Proof. p T_{σ_{n}} has a projective definition via the above definitions of T_{σ_{n}} and A_{n}. Thus the claim holds by 1-step projective Cohen absoluteness in M [Woo82, Lemma 2]. □

Claim. T_{σ_{n}}^{M} T_{σ_{n}}^{M g}.

Proof. By PD any projective pre-wellorder E is thin, i.e. there is no perfect set of reals that are pairwise inequivalent with respect to E. By 1-step projective Cohen absoluteness [Woo82, Lemma 2], [Sch14, Lemma 3.18] and PD, Cohen forcing does not add new equivalence classes to E. Equality now follows from [Sch14, Theorem 5.15]. The inclusion T_{σ}^{M} T_{σ}^{M g} holds since the rank function r_{n} is upwards absolute from M to M g by the previous statement for E _{n}. The converse inclusion is proved in [Sch14, Claim 5.16] from PD. □

19See [Jec03, Chapter 33].

20The tree of a scale is defined in the discussion before [Mos09, Theorem 8G.10].

We now show that IA_{proj}^{ℂ} holds. Assume that ψ x is a Σ_{2n}^{1}-formula and x M g . Note that the equivalences ψ x φ_{n} x, y_{ψ} x, y_{ψ} A_{n} x, y_{ψ} p T_{σ_{n}} hold in V and in M g by the first claim. It remains to show that M g x, y_{ψ} p T_{σ_{n}} if and only if x, y_{ψ} p T_{σ_{n}} holds in V.

We claim that T_{σ_{n}}^{M g} T_{σ_{n}} M g . To see this, note that T_{σ_{n}}^{M} T_{σ_{n}} M since M H_{θ}. Using the second claim and the fact that Ord^{M} Ord^{M g}, we obtain T_{σ_{n}}^{M g} T_{σ_{n}}^{M} T_{σ_{n}} M T_{σ_{n}} M g . By absoluteness of wellfoundedness, we have M g x, y_{ψ} p T_{σ_{n}} x, y_{ψ} p T_{σ_{n}}^{M g} x, y_{ψ} p T_{σ_{n}} .

(2) Since M is countable, the set of Cohen reals over M in V is comeager. Therefore, this claim holds by the argument for the Baire property in Solovay’s model. □

The above argument for the non-existence of a selector with Borel values can now be used for the following results. We fix codes for Σ_{n}^{1} sets via Σ_{n}^{1}-universal Σ_{n}^{1} sets.

Theorem 5.8. Assuming IA_{proj}^{ℂ}, there is no Baire measurable selector for I with projective values.

Proof. This is proved similarly to Theorem 5.5. We only indicate the two necessary changes. In the proof of the first claim, IA_{proj}^{ℂ} implies that the (projective) statement { \atop T_{n}^{g}} B_{F { \atop C^{g}}} { \atop T_{n}^{g}} B_{{ \atop F^{g}} { \atop C^{g}}} is absolute between M g and V. The second change is at the very end of the proof. Here projective absoluteness between M g h and V by IA_{proj}^{ℂ} guarantees that x σ^{G} B_{F { \atop C^{g}}} and thus B_{F { \atop C^{g}}} B{ \atop C^{g}} contains every Cohen real over M g in V. As before, this contradicts Lemma 5.6 and the fact that F is a selector for I. □

Note that by Lemma 5.7, PD is sufficient for the previous result. Thus PD implies that there is no projective selector for I. Note that some assumption beyond ZFC is necessary to prove this statement. For instance, in L there are projective selectors for all projectively coded ideals I, since there is a projective, in fact a Σ_{2}^{1}, wellorder of the reals.

The previous arguments can also be used to show that it is consistent with ZF that there is no selector at all for I.

Suppose that κ is an uncountable cardinal and G is a ℙ-generic filter over V for ℙ Add κ, 1 or ℙ Col ω, κ . We call V^{}_{α κ} V G α a symmetric extension for ℙ. Note that V^{}HOD_{V^{}}^{V G} by homogeneity and for cardinals κ of uncountable cofinality, ℝ^{V^{}}ℝ^{V G}.

Theorem 5.9. There are no selectors for I in the following models of ZF.

(a) Symmetric extensions V^{}for Add ω, κ and Col ω, κ , where κ is any uncountable cardinal.

(b) Solovay’s model.

(c) L ℝ assuming AD^{L ℝ}.

Proof. The proof of the first claim is similar to that of to Theorem 5.5.

Suppose that F is a selector for I in V^{}. It is definable from an element x_{0} of V G α for some α κ. We can further assume that x_{0} V. Hence F is continuous on the set of Cohen reals over V in V^{}; let F be a name for this function.

We follow the proof of Theorem 5.5 but work with V instead of M. The first claim in the proof of Theorem 5.5 is replaced by the following claim.

We will write V^{}for a ℙ-name for V^{}to keep the notation simple.

Claim. 1 _{𝕋^{ω} ℙ}^{V} V^{}{ \atop T_{n}} B_{F C} for all n ω.

Proof. Assume towards a contradiction that p, q _{𝕋^{ω} ℙ}^{V} V^{}{ \atop T_{n}} B_{F C} for some p 𝕋^{ω}, q ℙ and n ω. We can assume q 1 by homogeneity. Let g h be a 𝕋^{ω} ℙ-generic filter over V with p g whose symmetric model is V^{}. Then { \atop T_{n}^{g}} B_{F { \atop C^{g}}} { \atop T_{n}^{g}} B_{{ \atop F^{g}} { \atop C^{g}}} . But this contradicts the assumption that F is a selector with respect to I. □

There is a 𝕋^{ω}-name σ in V that is forced to be an element of { \atop T_{n}} B_{F C} V^{}by the previous claim. The next steps of the proof are as before.

In the end of the proof, we rearrange V g h as a 𝕋^{ω} Add ω, 1 -generic extension V G H with σ^{G} x as before. Then σ^{G} B_{F { \atop C^{g}}} by the choice of σ. Thus B_{F { \atop C^{g}}} B{ \atop C^{g}} contains every Cohen real over V g in V^{}. Since there are uncountably many Cohen reals over V g in V^{}, this contradicts the assumption that F is a selector.

The second claim holds since Solovay’s model is obtained via a symmetric extension for Col ω, κ . Note that this model is also a Add ω, ω_{1} -generic extension of an intermediate model.

The last claim follows from [SS06, Theorem 0.1] and the first claim. By this theorem and AD^{L ℝ}, L ℝ ^{V} L ℝ ^{V^{}}for some symmetric extension V^{}for Col ω, κ for some κ over some ground model N which is an inner model of some generic extension of V. □

5.3. Density points via convergence. In this section we discuss the notion of density point introduced in [PWBW85]. We show that this notion does not satisfy the analogue of Lebesgue’s Density Theorem for any of the tree forcings listed in the next section except Cohen and Random forcing.

Lebesgue’s density theorem was generalized to the σ-ideals of meager sets on Polish metric spaces in [PWBW85, Theorem 2]. To this end, a notion of density points for ideals was introduced. This notion is based on the following measure theoretic lemma.

Lemma 5.10. Suppose that X, d, μ is a metric measure space, f is a Borel-measurable function and f⃗ f_{n} n ω is a sequence of Borel-measurable functions from X, d to ℝ. The following statements are equivalent.

(a) f_{n} f converges in measure, i.e. for all ϵ 0 we have

lim_{n} μ x X f_{n} x f x ϵ 0.

(b) Every subsequence of f⃗ has a further subsequence that converges pointwise μ-almost everywhere.

Condition (b) is suitable for generalizations to other ideals, since it only mentions the ideal of null sets, but not the measure itself.

Definition 5.11. Let I be a σ-ideal on ^{ω}X and A ^{ω}X.

(1) For each n ω let f_{n} be the characteristic function of σ_{x n}^{1} A N_{x n} . Define x to be an I-convergence density point of A if every subsequence of f_{n} _{n ω} has a further subsequence which converges I-almost everywhere to the constant function ωX 1 (i.e., converges everywhere on a set A such that ^{ω}X A I).

(2) By the I-convergence density property we mean the statement that for every B Borel ^{ω}X it holds that BΔB^{}I where B^{}is the set of I-convergence density points of B.

We first consider tree forcings on ^{ω}ω. For s ^{ω} ω and f_{0}, …, f_{m} ^{ω}ω, let

T_{s,f_{0},...,f_{m}} t C_{s} i m n s t n f_{i} n

(cf. Definition 6.1 (f) below) and let f ^{ω}ω denote the constant function with value 0.

Lemma 5.12. If N_{0} and T_{,f} are I-positive, then the I-convergence density property fails. In particular, this holds for I_{ℍ}, I_{𝔼}, I_{𝕄} and I_{𝕃_{A}} if A contains all cofinite sets.

Proof. We claim that no x ^{ω}ω is an I-convergence density point of T_{,f} . We have σ_{t}^{1} T_{,f} T_{,f} if t T_{,f} and σ_{t}^{1} T_{,f} otherwise. Hence σ_{t}^{1} T_{,f} N_{0} for all t ^{ω} ω. Thus x is not an I-convergence density point of T_{,f} . □

We now turn to tree forcings on ^{ω}2. For s 2^{ω} and N ω ^{ω} let

T_{s,N} t ^{ω} 2 t C_{s} & n t n 1 n N

(cf. Definition 6.1 (h) below).

Lemma 5.13. Suppose that N_{1} and T_{,N} are I-positive for some infinite set N. Then the I-convergence density property fails. In particular, this holds for ℝ_{A} and 𝕍_{A} for any subset A of P ω that contains at least one infinite set.

Proof. It is sufficient to show that no x T_{,N} is an I-convergence density point of T_{,N} . We have σ_{x n}^{1} T_{,N} N_{1} for all n N. Since N_{1} is I-positive, any infinite strictly increasing sequence in N witnesses that x is not an I-convergence density point. □

The next lemma takes care of the remaining tree forcings.

Lemma 5.14. Suppose that I is an ideal on ^{ω}2 with I_{𝕊} I I_{ℝ}. Then the I-convergence density property fails.

Proof. Let

T t 2^{ω} i ω t i 1 j ω i 2^{j} 1 .

It is sufficient to show that no x ^{ω}2 is an I-convergence density point of T . Otherwise there is a strictly increasing sequence n⃗ n_{i} i ω such that

A y ^{ω}2 i j i y σ_{x n_{j}}^{1} T

is co-countable. Let

A_{i,j} σ_{x n_{i}}^{1} T σ_{x n_{j}}^{1} T

for i j in ω. Since A _{i,j ω, i j} A_{i,j} is uncountable, A_{i,j} is uncountable for some i j. Let a _{lex} b _{lex} c be elements of A_{i,j}. We denote the longest common initial segment of d, e 2^{ω} by d e. We can assume without loss of generality that a b s, a c b c t and s t. Then s and t are splitting nodes in σ_{x n_{i}}^{1} T and σ_{x n_{j}}^{1} T . Hence s n_{i}, s n_{j}, t n_{i}, t n_{j} are of the form 2^{k} 1. Since s t, n_{j} n_{i} can be written in the form 2^{k} 2^{l} in two different ways. But this contradicts the easy fact that k, l are uniquely determined by 2^{k} 2^{l}. □

Let ℙ_{E_{0}} denote E_{0}-forcing [Zap08, Section 4.7.1] and 𝕎 an appropriate representation of Willowtree forcing [Bre95, Section 1.1]. Since ℝ 𝕍 𝕎 ℙ_{E_{0}} 𝕊, the previous result holds for the ideals I_{ℙ} associated to these forcings as well.

6. A list of tree forcings

We review definitions of some tree forcings for the reader’s convenience. If N ω and m ω, we write m N m n n N . Moreover, a subset A of P ω is called shift invariant if N A m N A for all m ω.

Definition 6.1. Assume that A is a subset of P ω .

(a) Random forcing is the collection of perfect subtrees T of ^{ω} 2 with μ T_{s} 0 for all s T with stem_{T} s.

(b) Cohen forcing ℂ is collection of cones C_{s} t ^{ω} ω s t or t s for s ^{ω} ω.

(c) Sacks forcing 𝕊 is the collection of all perfect subtrees of 2^{ω} .

(d) Miller forcing 𝕄 is the collection of superperfect subtrees T of ^{ω} ω. This means that above every node in T there is some infinitely splitting node t in T, i.e. t has infinitely many direct successors.

(e) Hechler forcing ℍ is the collection of trees

T_{s,f} t C_{s} n s t n f n

for s ^{ω} ω and f ^{ω}ω.

(f) Eventually different forcing 𝔼 is the collection of trees

T_{s,f_{0},...,f_{m}} t C_{s} i m n s t n f_{i} n

for s ^{ω} ω and f_{0}, …, f_{m} ^{ω}ω.

(g) A-Laver forcing 𝕃_{A} is the collection of subtrees T of ^{ω} ω such that for every t T with stem_{T} t, the set succ_{T} t of direct successors of t in T is an element of A. Laver forcing is 𝕃_{F} for the Fréchet filter F of cofinite sets.

(h) A-Mathias forcing ℝ_{A} is the collection of trees

T_{s,N} t ^{ω} 2 t C_{s} & n t n 1 n N

for s 2^{ω} and N A. Mathias forcing ℝ is ℝ_{A} for A ω ^{ω}.

(i) A-Silver forcing 𝕍_{A} is the collection of trees

T_{f} t ^{ω} 2 n dom t dom f f n t n ,

where dom f ω N for some N A. Silver forcing 𝕍 is 𝕍_{A} for A ω ^{ω}.

All of these satisfy the above condition for collections of trees ℙ that T_{s} ℙ for all T ℙ and s T. Moreover, Random forcing, Cohen forcing, Sacks forcing, Hechler forcing, eventually different forcing, and A-Laver forcing are shift invariant in the sense that for all T and s 2^{ω} , T ℙ σ_{s} T ℙ. If A is shift invariant, then ℝ_{A} and 𝕍_{A} are also shift invariant.

Note that Cohen forcing, Hechler forcing, eventually different forcing, Laver forcing, and Silver forcing are topological, while Random forcing, Sacks forcing, and Miller forcing are not.

7. Open problems

We end with some open questions. The main one asks about equivalence of the properties discussed in the introduction.

Question 7.1. Are the shift density property, the existence of a simply definable selector and the ccc equivalent for all simply definable σ-ideals?

For more examples of ideals, see [Zap08]. We further suggest to study the relationship between the shift density property and the condition that the collection of Borel sets modulo I carries a natural Polish metric. For the previous question, we suggest to generalize the proof idea of Theorem 5.5 to other non-ccc ideals such as the K_{σ}-ideal.

Question 7.2. Is there a Baire measurable selector with Borel values for the K_{σ}-ideal?

Lemma 4.7 showed that the ℙ-measurable sets form a σ-ideal if ℙ has the ω_{1}-covering property. If this assumption can be omitted, this would in particular imply a positive answer to the next question.

Question 7.3. Are all Borel sets ℙ-measurable for all tree forcings ℙ?

Note that any counterexample ℙ collapses ω_{1} if we assume CH; then ℙ preserves ω_{1} if and only if it has the ω_{1}-covering property by a similar argument as in the proof of Lemma 4.4.

The last question is about the notion of generic absoluteness introduced in Section 5.2. Lemma 5.7 shows that this follows from PD. Our results leave the consistency strength of this statement open.

Question 7.4. Does IA_{proj}^{ℂ} imply that 0^{#} exists?

References

[AC13] Alessandro Andretta and Riccardo Camerlo. The descriptive set theory of the Lebesgue density theorem. Adv. Math., 234:1–42, 2013.

[AC18] Alessandro Andretta and Riccardo Camerlo. Analytic sets of reals and the density function in the cantor space. To appear in the European Journal of Mathematics, arXiv preprint arXiv:1705.02285, 2018.

[ACC13] Alessandro Andretta, Riccardo Camerlo, and Camillo Costantini. The density point property. Slides of a talk given by Alessandro Andretta at the 4th European Set Theory Conference, Mon St. Benet, Catalunya, 2013.

[ACC15] Alessandro Andretta, Riccardo Camerlo, and Camillo Costantini. Lebesgue density and exceptional points. arXiv preprint arXiv:1510.04193, 2015.

[BHL05] Jörg Brendle, Lorenz Halbeisen, and Benedikt Löwe. Silver measurability and its relation to other regularity properties. Math. Proc. Cambridge Philos. Soc., 138(1):135–149, 2005.

[BJ95] Tomek Bartoszyński and Haim Judah. Set theory. A K Peters, Ltd., Wellesley, MA, 1995. On the structure of the real line.

[BKW18] Jörg Brendle, Yurii Khomskii, and Wolfgang Wohofsky. Cofinalities of Marczewski-like ideals. Preprint, 2018.

[BL99] Jörg Brendle and Benedikt Löwe. Solovay-type characterizations for forcing-algebras. The Journal of Symbolic Logic, 64(3):1307–1323, 1999.

[Bre95] Jörg Brendle. Strolling through paradise. Fund. Math., 148(1):1–25, 1995.

[Cum10] James Cummings. Iterated forcing and elementary embeddings. In Handbook of set theory. Vols. 1, 2, 3, pages 775–883. Springer, Dordrecht, 2010.

[FKK16] Sy Friedman, Yurii Khomskii, and Vadim Kulikov. Regularity properties on the generalized reals. Ann. Pure Appl. Logic, 167(4):408–430, 2016.

[FMW92] Qi Feng, Menachem Magidor, and Hugh Woodin. Universally Baire sets of reals. In Set theory of the continuum (Berkeley, CA, 1989), volume 26 of Math. Sci. Res. Inst. Publ., pages 203– 242. Springer, New York, 1992.

[GRSS95] Martin Goldstern, Miroslav Repickỳ, Saharon Shelah, and Otmar Spinas. On tree ideals. Proceedings of the American Mathematical Society, 123(5):1573–1581, 1995.

[Hal03] Lorenz Halbeisen. Making doughnuts of cohen reals. Mathematical Logic Quarterly: Mathematical Logic Quarterly, 49(2):173–178, 2003.

[Hjo10] Greg Hjorth. Borel equivalence relations. In Handbook of set theory. Vols. 1, 2, 3, pages 297–332. Springer, Dordrecht, 2010.

[Ike10] Daisuke Ikegami. Forcing absoluteness and regularity properties. Ann. Pure Appl. Logic, 161(7):879–894, 2010.

[Jec03] Thomas Jech. Set theory. Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2003. The third millennium edition, revised and expanded.

[JR95] Haim Judah and Miroslav Repický. No random reals in countable support iterations. Israel J. Math., 92(1-3):349–359, 1995.

[Kan09] Akihiro Kanamori. The higher infinite. Springer Monographs in Mathematics. Springer-Verlag, Berlin, second edition, 2009. Large cardinals in set theory from their beginnings, Paperback reprint of the 2003 edition.

[Kec95] A. Kechris. Classical Descriptive Set Theory, volume 156 of Graduate Texts in Mathematics. Springer-Verlag New York, 1995.

[Kec73] Alexander S. Kechris. Measure and category in effective descriptive set theory. Ann. Math. Logic, 5:337–384, 1972/73.

[KPW08] Piotr Kalemba, Szymon Plewik, and Anna Wojciechowska. On the ideal v^{0} . Cent. Eur. J. Math., 6(2):218–227, 2008.

[KRS16] Antti Käenmäki, Tapio Rajala, and Ville Suomala. Local homogeneity and dimensions of measures. Ann. Sc. Norm. Super. Pisa Cl. Sci. (5), 16(4):1315–1351, 2016.

[KSZ13] Vladimir Kanovei, Marcin Sabok, and Jindřich Zapletal. Canonical Ramsey theory on Polish spaces, volume 202. Cambridge University Press, 2013.

[LNVTPS09] Claude Laflamme, Lionel Nguyen Van Thé, Maurice Pouzet, and Norbert Sauer. Partitions and indivisibility properties of countable dimensional vector spaces. arXiv preprint arXiv:0907.3771, 2009.

[Mat95] Pertti Mattila. Geometry of sets and measures in Euclidean spaces, fractals and rectifiability, volume 44 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 7:11, 1995.

[Mil08] Benjamin D. Miller. The existence of quasi-invariant measures of a given cocycle, I: Atomless, ergodic sigma-finite measures. Ergodic Theory and Dynamical Systems, 28(5):1599–1613, 2008.

[Mos09] Yiannis N. Moschovakis. Descriptive set theory, volume 155 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, second edition, 2009.

[PWBW85] Wiesława Poreda, Elżbieta Wagner-Bojakowska, and Władysław Wilczyński. A category analogue of the density topology. Fundamenta Mathematicae, 125:167–173, 1985.

[Sch14] Philipp Schlicht. Thin equivalence relations and inner models. Ann. Pure Appl. Logic, 165(10):1577–1625, 2014.

[Sik48] Roman Sikorski. On the representation of Boolean algebras as fields of sets. Fund. Math., 35:247–258, 1948.

[SS06] Ralf Schindler and John Steel. The strength of AD. Unpublished note, available at https://ivv5hpp.uni-muenster.de/u/rds/, 2006.

[SS18] Saharon Shelah and Otmar Spinas. Different cofinalities of tree ideals. Preprint, 2018.

[Szp35] Edward Szpilrajn. Sur une classe de fonctions de m. sierpiński et la classe correspondante d’ensembles. Fundamenta Mathematicae, 24(1):17–34, 1935.

[Woo82] W. Hugh Woodin. On the consistency strength of projective uniformization. In Proceedings of the Herbrand symposium (Marseilles, 1981), volume 107 of Stud. Logic Found. Math., pages 365–384. North-Holland, Amsterdam, 1982.

[Zap04] Jindřich Zapletal. Descriptive set theory and definable forcing. Mem. Amer. Math. Soc., 167(793), 2004.

[Zap08] Jindřich Zapletal. Forcing idealized, volume 174 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2008.

Sandra Müller, Kurt Gödel Research Center, Fakultät für Mathematik, Universität Wien, Währinger Straße 25, 1090 Wien, Austria

   Email address: mueller.sandra@univie.ac.at

Philipp Schlicht, School of Mathematics, University of Bristol, University Walk, Bristol, BS8 1TW, UK

   Email address: philipp.schlicht@bristol.ac.uk

David Schrittesser, Kurt Gödel Research Center, Fakultät für Mathematik, Universität Wien, Währinger Straße 25, 1090 Wien, Austria

   Email address: david.schrittesser@univie.ac.at

Thilo Weinert, Kurt Gödel Research Center, Fakultät für Mathematik, Universität Wien, Währinger Straße 25, 1090 Wien, Austria

   Email address: thilo.weinert@univie.ac.at