IDEALS INDUCED BY TSIRELSON SUBMEASURES

ILIJAS FARAH

Abstract. We use Tsirelson’s Banach space ([2]) to define an F_{σ} P-ideal which refutes a conjecture of Mazur and Kechris (see [12, 9, 8]).

1. Introduction

By the dichotomy results of Silver and Harrington–Kechris–Louveau (see [10, 8]), the Borel-cardinality of quotients over Borel equivalence relations on Polish spaces is well-understood below P(ℕ)/Fin. This can not be said for the next level of this ordering, even if we restrict our attention to Borel-cardinalities of quotients P(ℕ)/I over Borel ideals I. The two natural ‘successors’ of Fin are the Fubini ideals on ℕ^{2}: Fin × ∅ (also called I_{1}) consisting of all sets with only finitely many nonempty vertical sections, and ∅ × Fin (also called I_{3} and Fin^{ω}) consisting of all sets all of whose vertical sections are finite. By results of Solecki ([17]), quotients over these two ideals are the critical points for quotients over Borel ideals which are not Pideals and for Borel P-ideals which are not F_{σ}, respectively (I is a P-ideal if it is σ-directed under the inclusion modulo finite). In [9], Kechris posed the following trichotomy conjecture for Borel ideals I such that P(ℕ)/I ≰_{B} P(ℕ)/Fin: at least one of P(ℕ^{2})/Fin×∅, P(ℕ^{2})/∅×Fin, and P(ℕ)/I_{1/n} is ≤_{B} P(ℕ)/I (the summable ideal I_{1/n} is defined below). By the above results of Solecki, this is equivalent to an earlier dichotomy conjecture of Mazur ([12]): If I is an F_{σ} ideal such that P(ℕ)/I ≰_{B} P(ℕ)/Fin, then either P(ℕ^{2})/Fin × ∅ or P(ℕ)/I_{1/n} is ≤_{B} P(ℕ)/I.

Consider an ordering on Borel ideals simpler than ≤_{B}:

I ≤_{RB}^{+} J if there is A ⊆ ℕ and h: A → ℕ such that B ∈ I iff h^{−1}(B) ∈ J.

If A = ℕ, then we write I ≤_{RB} J. Clearly I ≤_{RB}^{+} J implies P(ℕ)/I ≤_{B} P(ℕ)/J, as the mapping A ↦ h^{−1}(A) verifies. It is rather surprising that the converse is often true; for example, the above Solecki’s dichotomy results are proved for the ≤_{RB}-ordering (see also Lemma 2.1 below).

Any I serving as a counterexample to the Kechris–Mazur conjecture, or KMC, would have to be an F_{σ} P-ideal. Until recently, the only known F_{σ} P-ideals were the summable ideals, that is, ones of the form

I_{f} = {A : ν_{f}(A) < ∞} = {A : lim_{n}(ν_{f}(A \ n)) = 0}

Date: November 25, 1998.

1991 Mathematics Subject Classification. 04A15, 46B.

I would like to thank S. Todorcevic for giving me several useful suggestions while I was working on this problem, to K. Mazur who has noticed quite a few inaccuracies in the original version of this paper, and to an anonymous referee whose remarks have considerably simplified the presentation, in particular in §6.

Supported by NSERC of Canada.

where ν_{f}(A) = ∑_{n∈A} f(n) for some f: ℕ → ℝ^{+}. These ideals can not serve as a counterexample to the Kechris–Mazur’s conjecture, since we have either I_{f} ≤_{RB}^{+} Fin or I_{1/n} ≤_{RB}^{+} I_{f} (note that this is false for the ≤_{RB} ordering, and this is why we introduce ≤_{RB}^{+}). By [17, Theorem 3.3] (see also [11, Lemma 1.2]), all F_{σ} P-ideals are of the form

I = {A : ϕ(A) < ∞} = {A : lim_{i} ϕ(A \ i) = 0}

for some lower semicontinuous submeasure ϕ, i.e. mapping such that ϕ(A) ≤ ϕ(A ∪ B) ≤ ϕ(A) + ϕ(B), ϕ(∅) = 0 and lim_{i} ϕ_{i}(A ∩ i) = ϕ(A) for all A, B. The first non-summable F_{σ} P-ideals were discovered in [4] (see also [3]). All these ideals were of the form

I_{{ϕ_{n}}} = {A : ∑_{i} ϕ_{i}(A) < ∞},

where for some sequence {n_{i}} each ϕ_{i} is a submeasure on the interval [n_{i}, n_{i+1}). But such ideals satisfy the KMC since if lim_{i} sup_{j} ϕ_{i}({j}) = 0 (and this can be assumed without a loss of generality by going to a positive set) then there are s_{i} and m_{i} such that

ϕ_{k}(s_{i}) \begin{cases}≈ 1/i, & k = m_{i} \\ = 0, & otherwise, \end{cases}

so that the map collapsing s_{i} to i witnesses I_{1/n} ≤_{RB}^{+} I_{{ϕ_{i}}}. An F_{σ} P-ideal which is not of the form I_{{ϕ_{i}}} was later found by Solecki ([16]), who has also proved that this ideal is of the form I_{{ϕ_{i}}} when restricted to a positive set, so it is again ≥_{RB}^{+} I_{1/n}. Another class of F_{σ} P-ideals, suggested by Kechris, are ideals of the form

I = \{A : \sqrt[p]{∑_{i} ϕ_{i}(A))^{p}} < ∞\}

for a sequence of submeasures ϕ_{i} as before and p > 1, but these again do not serve as a counterexample to KMC, for the same reason as I_{{ϕ_{i}}}. (However, using methods and results of [7] it can be proved that the Borel-cardinalities of these quotients are different for different p’s.)

The new F_{σ} P-ideal which we define here is extracted from Tsirelson space, an infinite-dimensional Banach spaces which does not contain a copy of c_{0} or any ℓ_{p} (see [2]). The study of this space has played a prominent role in the recent striking developments in the theory of infinite-dimensional Banach spaces (see [6], [13, page 956]). It is likely that other Banach spaces will give rise to interesting examples of analytic P-ideals (see [5]).

After the completion of this paper, we have learned that our main result, Theorem 3.1, was independently proved by B. Velickovic ([19]).

The paper is organized as follows. In §2 we prove that P(ℕ)/I_{1/n} ≤_{B} P(ℕ)/I is equivalent to I_{1/n} ≤_{RB}^{+} I. In §3 we introduce the ideals T_{fh}. In §§4–6 various properties of these ideals are proved, and in §7 we conclude the proof that P(ℕ)/T_{fh} serves as a counterexample to the Kechris–Mazur conjecture.

A word on notation: If s, t are finite sets of integers and n is an integer, by s < t we will denote the fact that max s < min t, and by n < s (n > s) the fact that n < min s (n > max s, respectively).

The results of this note were presented at the XI Latinamerican Logic Symposium in Merida, Venezuela, in July 1998.

2. The first reduction

A quotient P(ℕ)/I has the smaller Borel-cardinality than the quotient P(ℕ)/J (in symbols P(ℕ)/I ≤_{B} P(ℕ)/J) if there is a Borel mapping F: P(ℕ) → P(ℕ) such that XΔY ∈ I iff F (X)ΔF (Y) ∈ J.

In the following lemma it is proved that the KMC is equivalent to its apparently stronger version, appearing in [4], which states: For every analytic ideal I such that I ≰_{RB} Fin one of Fin × ∅, ∅ × Fin or I_{1/n} is ≤_{RB} I ↾ A for some I-positive A. (It is well-known that P(ℕ)/I ≤_{B} P(ℕ)/Fin is equivalent to I ≤_{RB} Fin.)

Lemma 2.1. If J is an analytic P-ideal such that P(ℕ)/I_{1/n} ≤_{B} P(ℕ)/J, then I_{1/n} ≤_{RB}^{+} J. Moreover, there are w_{1} < w_{2} < w_{3} < … in Fin such that the map collapsing w_{i} to i witnesses this.

Proof By [17], we can fix a lower semicontinuous submeasure ϕ such that J = {A : lim_{i} ϕ(A \ i) = 0}. Let F: P(ℕ) → P(ℕ) be a Borel reduction. By a standard use of stabilizers, similar to one below, we can assume that F is continuous (see also [18]). Find integers 1 = a_{1} < b_{1} < a_{2} < b_{2} < …, s_{i} ⊆ [b_{i}, a_{i+1}) and k_{i} ∈ (b_{i}, a_{i+1}) so that for all i, all u, v ⊆ b_{i}, and all X, Y ⊆ [a_{i+1}, ∞):

1. a_{i} > 2^{i}, b_{i} > 2a_{i},

2. (F (u ∪ s_{i} ∪ X)ΔF (u ∪ s_{i} ∪ Y)) ∩ k_{i} = ∅,

3. ϕ((F (u ∪ s_{i} ∪ X)ΔF (v ∪ s_{i} ∪ X)) \ k_{i}) ≤ 2^{−i}. The method for construction of these sequences is standard, dating back to [15] and [18]: Assume that a_{i}, b_{i} (i ≤ n) and s_{j}, k_{j} (j ≤ n−1) as above have been chosen, but there are no s_{n}, k_{n} and a_{n+1} satisfying the requirements. The condition 1 is easy to satisfy and since F is continuous, 2 will be satisfied for every choice of s_{n}, a large enough k_{n} and a large enough a_{n+1}. Therefore we can construct a sequence b_{n} < t_{1} < l_{1} < t_{2} < l_{2} < … so that l_{i} ∈ ℕ, t_{i} ∈ Fin, and for all i there are u_{i}, v_{i} ⊆ a_{n} such that

ϕ((F (u_{i} ∪ ⋃_{j=1}^{i} t_{j} ∪ t_{i+1})ΔF (u_{i} ∪ ⋃_{j=1}^{i} t_{j} ∪ t_{i+1})) \ l_{i}) > 2^{−n}.

Pick u, v such that ⟨u, v⟩ = ⟨u_{i}, v_{i}⟩ infinitely often. Then F (u ∪ ⋃_{i} t_{i})ΔF (v ∪ ⋃_{i} t_{i}) is not in J —a contradiction.

Assume a_{n}, b_{n}, s_{n} and k_{n} are chosen to satisfy the above conditions. By 1, ν_{1/n}([a_{i}, b_{i}]) ≥ 1/n and there is u_{i} ⊆ (a_{i}, b_{i}) such that |ν_{1/n}(u_{i}) − 1/i| ≤ 2^{−i} for every i. Let C = ⋃_{i} s_{i} and define F_{1} : P (⋃_{i}[a_{i}, b_{i})) → P(ℕ) by

F_{1}(B) = F (B ∪ C)ΔF (C).

Then F_{1}(∅) = ∅ and for X, Y ⊆ ⋃_{i}[a_{i}, b_{i}) we have (X ∪C)Δ(Y ∪C) = XΔY ∈ I_{1/n} iff F_{1}(X)ΔF_{1}(Y) = F (X ∪ C)ΔF (Y ∪ C) ∈ J. Note that by 2–3 for all i, all u, v ⊆ ⋃_{i≤m}[a_{i}, b_{i}), and all X, Y ⊆ ⋃_{i≥m+1}[a_{i}, b_{i}) we have:

4. (F_{1}(u ∪ X)ΔF_{1}(u ∪ Y)) ∩ k_{m} = ∅,

5. ϕ((F_{1}(u ∪ X)ΔF_{1}(v ∪ X)) \ k_{m}) ≤ 2^{−m}. Let w_{i} = F_{1}(u_{i}) ∩ [k_{i−1}, k_{i}). Then a map collapsing w_{i} to i witnesses I_{1/n} ≤_{RB}^{+} J. This follows by the following computations (assume m ∈ A and let u_{X} = ⋃_{i∈X} u_{i}):

t_{m} = (F_{1}(u_{A})Δw_{A}) ∩ [k_{m−1}, k_{m})
⊆ (F_{1}(u_{A})ΔF_{1}(u_{A\m})) ∪ (F_{1}(u_{A\m})ΔF_{1}(u_{m}))) ∩ [k_{m−1}, k_{m})

(since w_{A} ∩ [k_{m−1}, k_{m}) = w_{m})

⊆ ((F_{1}(u_{A})ΔF_{1}(u_{A\m})) \ a_{m}) ∪ (F_{1}(u_{A\m})ΔF_{1}(u_{m}))) ∩ k_{m}

(by 4. and 5., since u_{A}Δu_{A\m} ⊆ ⋃_{i=1}^{m−1}[a_{i}, b_{i}) and u_{A\m}Δu_{m} ⊆ ⋃_{i=m+1}^{∞}[a_{i}, b_{i})) = (F_{1}(u_{A})ΔF_{1}(u_{A\m})) \ a_{m},

and therefore ϕ(t_{m}) ≤ 2^{−m+1}, if m ∈ A. An analogous computation shows that ϕ(t_{m}) ≤ 2^{−m+1} also in the case when m ∉ A, and therefore we have

F_{1}(u_{A})Δw_{A} ⊆ ⋃_{m} t_{m} ∪ [1, k_{1}) ∈ J .

To prove the moreover part, that we can assume that w_{1} < w_{2} …, find 1 < n_{1} < m_{1} < n_{2} < m_{2} < … so that n_{i} > 2^{i}, ν_{1/n}([n_{i}, m_{i}]) − 1/i| ≤ 2^{−i}, and

max ⋃_{j∈[n_{i},m_{i}]} w_{j} < min ⋃_{j∈[n_{i+1},m_{i+1}]} w_{j}.

Then sets w′_{i} = ⋃_{j∈[n_{i},m_{i}]} w_{j} are as required.

Let us digress a little and note that ∅ × Fin also shares the nice property of I_{1/n} from Lemma 2.1, as its proof readily shows.

Lemma 2.2. If J is an analytic P-ideal such that P(ℕ^{2})/∅ × Fin ≤_{B} P(ℕ)/J, then ∅ × Fin ≤_{RB}^{+} J ↾ A for some A ∈ J^{+}.

It would be interesting to find more ideals with this property shared by I_{1/n} and ∅ × Fin, since it considerably simplifies some questions about the Borel-cardinality of their quotients. Let us note that a pathological F_{σδ} P-ideal J constructed in [3, §6] does not have this property. Namely, by a result of M.R. Oliver ([14]), E_{J} is Borel-reducible to E_{Z_{0}}, the equivalence relation induced by the density zero ideal. But the ideal Z_{0} is nonpathological (see [3]), and therefore by [3, Proposition 6.5] J ≤_{RB}^{+} Z_{0} would imply that J is nonpathological as well.

3. Tsirelson submeasures and ideals

Assume that {x_{n}} is an unconditional basic sequence in a Banach space X such that lim_{n} ∥ ∑_{i=1}^{n} x_{i}∥ = ∞. Then

J = {A : ∥ ∑_{n∈A} x_{n}∥ < ∞}

is an analytic P-ideal, which we call a generalized summable ideal. Many analytic P-ideals are of this form, and ideals T_{fh} defined below are obtained in this way from the Tsirelson space, a Banach space which does not include a copy of c_{0} or any ℓ_{p} (see [2]).

For sets A, B ⊆ ℕ by AB we shall often denote their intersection, A ∩ B. Fix functions f: ℕ → ℝ and an increasing h: ℕ → ℕ. A tuple

⟨k, E_{1}, … E_{m)}⟩

is h-admissible if k ∈ ℕ, E_{i} ∈ Fin for all i, k < E_{1} < E_{2} < ⋯ < E_{m)}, and m ≤ h(k). We shall denote pairs ⟨k, E_{1}, …, E_{m}⟩ by ⟨k, E⃗⟩ and write m = |E⃗|, so that the necessary condition for the admissibility is |E⃗| ≤ h(k). Let A_{h} be the set of all h-admissible tuples. Define a sequence of Tsirelson submeasures τ_{n} = τ_{f,h,n} (n ∈ ℕ ∪ {∞}) as follows:

τ_{f,h,0}(A) = sup_{n∈A} f(n)

τ_{f,h,n}^{k}(A) = sup_{⟨k,E⃗⟩∈A_{h}} ∑_{i=1}^{|E⃗|} τ_{f,h,n}(E_{i}A),

τ_{f,h,n+1}(A) = max\{τ_{f,h,n}(A), \frac{1}{2} sup_{k} τ_{f,h,n}^{k}(A)\},
τ_{f,h,∞}(A) = sup_{n} τ_{f,h,n}(A) = lim_{n} τ_{f,h,n}(A).

We shall always omit ∞ in subscripts, so that τ_{f,h} stands for τ_{f,h,∞} and τ_{f,h}^{k} stands for τ_{f,h,∞}^{k}. Similarly, when f, h are clear from the context we shall write τ_{n} instead of τ_{f,h,n}, τ^{k} instead of τ_{f,h}^{k}, and so on. The submeasure τ = τ_{f,h} defines a Tsirelson ideal, T_{fh}, on ℕ by:

T_{fh} = Exh(τ) = {A : lim_{i} τ(A \ i) = 0}.

We shall always assume that f: ℕ → ℝ^{+}, lim_{i} f(i) = 0, and h is strictly increasing, unless otherwise specified.

Theorem 3.1. Assume f, h are as above. Then P(ℕ)/I_{1/n} ≰_{B} P(ℕ)/T_{fh} and T_{fh} is an F_{σ} P-ideal.

The proof of Theorem 3.1 occupies the rest of this note.

Lemma 3.2. Assume f, h are as above. Then

1. Either τ(A) = sup_{i∈A} f(i) or τ(A) = \frac{1}{2} sup_{k} τ^{k}(A).

2. All τ_{n} and τ are lower semicontinuous submeasures.

3. τ(A) < ∞ if and only if lim_{n} τ(A \ n) = 0.

4. τ_{m+1}(A) < ∞ if and only if lim_{n} τ_{m}(A \ n) = 0.

5. T_{fh} = {A : τ(A) < ∞} and therefore it is an F_{σ} P-ideal.

Proof To prove 1, note that if τ(A) > sup_{i∈A} f(i) then we have

τ(A) = sup_{n} (\frac{1}{2} sup_{k} τ_{n}^{k}(A)) = \frac{1}{2} sup_{k} τ^{k}(A).

Statement 2 is obvious from the definition. In 3 only the direct implication requires a proof. Assume that lim_{n} τ(A \ n) ≠ 0; then we can find ε > 0 and finite sets w_{1} < w_{2} < … included in A such that τ(w_{n}) ≥ ε for all n. Fix p ∈ ℕ and find n̄ such that

min(wn̄) > 2p.

Then A_{0} = ⋃_{i=n̄}^{n̄+2p} w_{i} ⊆ A and by 1 we get

τ(A_{0}) ≥ \frac{1}{2} ∑_{i=n̄}^{n̄+2p} τ(w_{i}) ≥ p · ε.

Since p was arbitrary, we have τ(A) = ∞ as required.

The proof of 4 is analogous to that of 3, and 5 follows immediately from 3.

We shall concentrate on the ideal T_{fh}, but we note that the ideals

T_{f,h,n} = Exh(τ_{n}) = {A : lim_{i} τ_{n}(A \ i) = 0}, n ∈ ℕ,

can turn out to be interesting in their own right. All these are P-ideals which are not F_{σ} (assuming they are proper ideals, of course), since a mapping witnessing ∅ × Fin ≤_{RB} T_{f,h,n} can be easily obtained from an (n − 1)-good sequence (see §6).

4. Properties of Tsirelson submeasures

In this section we compute several lemmas which will be used in proof of Theorem 3.1. First we give a transparent description of how τ_{n} is computed in Lemma 4.2 below. By ℕ^{<ℕ} we denote the set of all finite sequences of integers, and consider it as a tree under the ordering of end-extension. A set T ⊆ ℕ^{<ℕ} is a tree if it is closed under taking initial segments of its elements. Note that the height of T is equal to the maximal length of its element. By ⟨⟩ we denote the empty sequence in ℕ^{<ℕ}, and tˆ i is the sequence obtained by concatenating t with ⟨i⟩. An end-node of T is any t ∈ T such that tˆ i ∉ T for all i. (Note that end-nodes of T do not necessarily belong to its top level.)

Definition 4.1. A family ⟨E_{t} : t ∈ T ⟩ is an h-tree if T ⊆ ℕ^{<ℕ} is a finitely branching finite tree, sets E_{t} are finite, and for all t ∈ T, if tˆ 1, …, tˆ l are the immediate successors of t in T then

1. E_{tˆ 1} < E_{tˆ 2} < ⋯ < E_{tˆ l} and E_{t} = ⋃_{i=1}^{l} E_{tˆ l},

2. l ≤ h(min E_{tˆ 1}), i.e. ⟨min E_{tˆ 1}, E_{tˆ 1}, …, E_{tˆ l}⟩ is h-admissible, and

3. if t is an end-node of T, then E_{t} is a singleton. The height of ⟨E_{t} : t ∈ T ⟩ is the height of T. Note that every i ∈ E_{⟨⟩} defines the unique branch,

B_{i} = {t ∈ T : i ∈ E_{t}},

of T. The length, |B_{i}|, of this branch is equal to the length of its last node. A function g: ℕ → {0, 1, …, n, ∞} is an (h, n)-weight assignment if there is an h-tree ⟨E_{t} : t ∈ T ⟩ of height at most n such that

4. E_{⟨⟩} = {i : g(i) ≠ ∞},

5. g(i) = |B_{i}| for each i ∈ E_{⟨⟩}.

Lemma 4.2. Assume that h: ℕ → ℕ is strictly increasing. Then for every s we have

τ_{n}(s) = sup_{g} ∑_{i∈s} 2^{−g(i)}f(i),

where the supremum is taken over all (h, n)-weight assignments g.

Proof Note that every branching of an h-tree corresponds to an application of a step in the recursive definition of τ_{n+1}, and that the nodes of height k come with the weight equal to 2^{−k} because of the k-fold multiplication with 1/2. Conditions 3. and 5. correspond to τ_{0}(A) = sup_{i∈A} f(i). Therefore, the Lemma is proved by a straightforward induction on n.

Lemma 4.3. If f, h are as in Lemma 4.2, n ∈ ℕ and s is finite, then there is an s′ ⊆ s such that τ_{n}(s′) = τ_{n}(s) and τ(s′) ≤ 3τ_{n}(s′)/2.

Proof Since s is finite, the supremum appearing in Lemma 4.2 is attained for some (h, n)-weight assignment g; let s′ = {i : g(i) ≠ ∞}∩s. It suffices to prove that τ_{m}(s′) ≤ 3τ_{n}(s′)/2 for every m. Fix m, let g_{m} be some (h, m)-weight assignment, and let X = {i ∈ s′ : g_{m}(i) > g(i)} and Y = {i ∈ s′ : g_{m}(i) ≤ g(i)}. We claim that (†) ∑_{i∈Y} 2^{−g_{m}(i)}f(i) ≤ τ_{n}(s′). To verify this, by Lemma 4.2 it suffices to show that the map g′ defined by

g′(i) = \begin{cases}g_{m}(i), & if g_{m}(i) ≤ g(i), \\ ∞, & if g_{m}(i) > g(i) or g_{m}(i) = ∞, \end{cases}

is an (h, n)-weight assignment. To see this, let ⟨E_{t} : t ∈ T ⟩ be an h-tree of height m witnessing that g_{m} is an (h, m)-weight assignment. Then for T′ = {t ∈ T : |t| ≤ n} the family ⟨E_{t} ∩ {i : g′(i) ≠ ∞} : t ∈ T′⟩ is an h-tree (this follows immediately from the definitions). Since g is an (h, n)-weight assignment, this tree is of height at most n and it witnesses that g′_{m} is an (h, n)-weight assignment.

Therefore (†) is true and since X ⊆ s′ we have

τ_{m}(s′) = ∑_{i∈X} 2^{−g_{m}(i)}f(i) + ∑_{i∈Y} 2^{−g_{m}(i)}f(i)

≤ \frac{1}{2} ∑_{i∈X} 2^{−g(i)}f(i) + τ_{n}(s′) ≤ \frac{1}{2}τ_{n}(s′) + τ_{n}(s′).

Since m was arbitrary and τ(s′) = sup_{m} τ_{m}(s′), this concludes the proof.

Lemma 4.4. Assume lim_{n} f(n) = 0 and h: ℕ → ℕ is strictly increasing. Then for all s and n we have ν_{f}(s) ≥ 2^{n+1}(τ_{n+1}(s) − τ_{n}(s)).

Proof Fix an ε > 0. Let g be an (h, n + 1)-weight assignment such that

∑_{i∈s} 2^{−g(i)}f(i) ≥ τ_{n+1}(s) + ε,

as given by Lemma 4.2. Let s_{0} = {i ∈ s : g(i) ≤ n}. Then by a weight assignment argument identical to that in the proof of Lemma 4.3 we have τ_{n}(s) ≥ τ_{n}(s_{0}) ≥ ∑_{i∈s_{0}} 2^{−g(i)}f(i), and therefore

2^{−(n+1)}ν_{f}(s) ≥ 2^{−(n+1)} ∑_{i∈s\s_{0}} f(i)

≥ ∑_{i∈s} 2^{−g(i)}f(i) − ∑_{i∈s_{0}} 2^{−g(i)}f(i) ≥ τ_{n+1}(s) − τ_{n}(s) + ε.

Since ε > 0 was arbitrary, this concludes the proof.

Recall that if {w_{i}} is a sequence of sets and A ⊆ ℕ, then we write w_{A} = ⋃_{i∈A} w_{i}. The following lemma will be very useful (recall the definition of τ_{n}^{k} from §3).

Lemma 4.5. Assume f, h are as in Lemma 4.2, w_{1} < w_{2} < … is a sequence of finite sets, and δ > 0. If for all i we have

1. τ_{n}(w_{i}) < δ/2 and

2. τ_{n−1}^{max(w_{i})}(w_{[i+1,∞)}) < δ (taking max(w_{0}) = 1), then for every A ⊆ ⋃_{i} w_{i} we have τ_{n}(A) < δ.

Proof If τ_{n}(A) = τ_{n−1}(A), the conclusion follows from 2. above.

Claim 4.6. Under the above assumptions, if A ⊆ ⋃_{i} w_{i} and τ_{n}(A) > τ_{n−1}(A), then

τ_{n}(A) ≤ sup_{i} (τ_{n}(w_{i}) + \frac{1}{2}τ_{n−1}^{max w_{i}} (⋃_{j=i+1}^{∞} w_{j})) .

Proof Fix ε > 0. By the assumption, we have τ_{n}(A) ≤ \frac{1}{2} ∑_{j=1}^{m} τ_{n−1}(E_{j}A) + ε

for some m ≤ h(k) and k < E_{1} < ⋯ < E_{m}. Let i be the minimal such that k ≤ max w_{i}. If max E_{l} ≤ max w_{i} for all l = 1, …, h(k), then τ_{n}(A) ≤ τ_{n}(w_{i}) + ε, and there is nothing to prove. Let l be the minimal such that max E_{l} > max w_{i}. Then

τ_{n}(A) ≤ \frac{1}{2} ∑_{j=1}^{l−1} τ_{n−1}(E_{j}A) + τ_{n−1}(E_{l}A) + \frac{1}{2} ∑_{j=l}^{m} τ_{n−1}(E_{j}A) + ε

≤ \frac{1}{2} ∑_{j=1}^{l−1} τ_{n−1}(E_{j}A) + τ_{n−1}(E_{l}(Aw_{i})) +

τ_{n−1}(E_{l}(A \ w_{i})) + \frac{1}{2} ∑_{j=l}^{m} τ_{n−1}(E_{j}A) + ε

≤ τ_{n}(w_{i}) + \frac{1}{2}τ_{n−1}^{k}(⋃_{p=i+1}^{∞} w_{p}) + ε.

Since k ≤ max w_{i} and ε > 0 was arbitrarily small, this completes the proof.

Lemma 4.5 follows immediately by the Claim.

5. The second reduction

The main result of this section is Proposition 5.3, essentially saying that if I ≤_{RB} T_{fh} then I is of the form T_{f′,h′} for some f′, h′ (possibly with lim_{i} f′(i) ≠ 0). It is essentially due to Casazza, Johnson and Tzafriri (see [1] and [2, Proposition I.12 and Lemmas II.1 and II.3]) who used the case when h is the identity function to prove that every infinite-dimensional subspace of the Tsirelson space includes a copy of a Tsirelson space. We reproduce the proof from [1] for the convenience of the reader.

Lemma 5.1. Assume f: ℕ → ℝ is nonnegative and h: ℕ → ℕ is strictly increasing, and let h^{+}(n) = h(n + h(n)). Then for every A and n we have

τ_{f,h,n}(A) ≤ τ_{f,h^{+},n}(A) ≤ 3τ_{f,h,n}(A).

Proof The left-hand side inequality is obvious, since h^{+} ≥ h. We prove the following strengthening of the right-hand side inequality by induction:

(*) For all A and n there are sets F_{1} < F_{2} < F_{3} such that

τ_{f,h^{+},n}(A) ≤ ∑_{j=1}^{3} τ_{f,h,n}(F_{j}A).

The case when n = 0 is trivial, so let us assume the lemma is proved for some n and prove it for n + 1. If τ_{f,h^{+},n+1}(A) = τ_{f,h^{+},n}(A), then there is nothing to prove, so we can assume

τ_{f,h^{+},n+1}(A) = \frac{1}{2} ∑_{l=1}^{h^{+}(k)} τ_{f,h^{+},n}(E_{l}A),  for some h^{+}-admissible ⟨k, E⃗⟩,

≤ \frac{1}{2} ∑_{l=1}^{h^{+}(k)} ∑_{j=1}^{3} τ_{f,h,n}(F_{lj}E_{l}A), for some F_{l1} < F_{l2} < F_{l3}.

We can assume F_{lj}E_{l} = F_{lj} for all l, j. For G_{3(l−1)+j} = F_{lj} we have G_{1} < G_{2} < ⋯ < G_{3h^{+}(k)}. We can assume all G_{l}’s are nonempty, possibly by eliminating the empty ones from the sequence. Let k^{∗} = k + h(k) (so that h^{+}(k) = h(k^{∗})) and

F_{1} = ⋃_{l=1}^{h(k)} G_{l},  F_{2} = ⋃_{l=h(k)+1}^{h(k)+h(k^{∗})} G_{l}, and F_{3} = ⋃_{l=h(k)+h(k^{∗})+1}^{3h^{+}(k)} G_{l}.

Then ⟨k, G_{1}, …, G_{h(k)}⟩ is h-admissible, so we have

τ_{f,h,n+1}(F_{1}A) ≥ \frac{1}{2} ∑_{l=1}^{h(k)} τ_{f,h,n}(G_{l}A).

Note that, since each G_{l} is nonempty, we have min(G_{h(k)+1}) ≥ min G_{1} +h(k) ≥ k^{∗}, and therefore the tuple associated with F_{2} is h-admissible and we have

τ_{f,h,n+1}(F_{2}A) ≥ \frac{1}{2} ∑_{l=h(k)+1}^{h(k^{∗})} τ_{f,h,n}(G_{l}A).

Like before, min G_{h(k)+h(k^{∗})+1} ≥ k^{∗} + h(k^{∗}). Since k ≤ h(k) and h(2k) ≤ h(k^{∗}), we have (note that h(i) + j ≤ h(i + j), since h is strictly increasing):

3h^{+}(k) ≤ h(k^{∗}) + 2h(k^{∗}) ≤ h(k^{∗}) + h(k^{∗} + h(k^{∗}))

and 3h^{+}(k)−h(k^{∗}) ≤ h(k^{∗} +h(k^{∗})), so the tuple associated with F_{3} is h-admissible, and we have

τ_{f,h^{+},n+1}(A) ≤ \frac{1}{2} ∑_{l=1}^{3h(2k))} τ_{f,h,n}(G_{l}A) ≤ ∑_{j=1}^{3} τ_{f,h,n+1}(F_{j}A),

completing the inductive proof.

Lemma 5.2. Assume f, h are as in Lemma 5.1 and that w_{1} < w_{2} < … are finite sets. Let f′(i) = τ_{f,h}(w_{i}), h′(i) = h(min w_{i}), and h′′(i) = h(max w_{i}). Then for all A ⊆ ℕ we have

τ_{f′,h′}(A) ≤ τ_{f,h}(w_{A}) ≤ 6τ_{f′,h′′}(A).

Proof We first prove the left-hand side inequality, by proving (*) τ_{f′,h′,n}(A) ≤ τ_{f,h}(w_{A}) using the induction on n. Since τ_{f′,h′}(A) = lim_{n} τ_{f′,h′,n}(A), this will suffice. In the case when n = 0 for some i ∈ A we have τ_{f′,h′,0}(A) = τ_{f,h}(w_{i}) ≤ τ_{f,h}(⋃_{j∈A} w_{j}).

Now assume (*) is true for n. If τ_{f′,h′,n+1}(A) = τ_{f′,h′,n}(A), there is nothing to prove. So we can assume

τ_{f′,h′,n+1}(A) = \frac{1}{2} ∑_{j=1}^{h′(k)} τ_{f′,h′,n}(E_{j}A), for some h-admissible ⟨k, E⃗⟩.

(Assuming that |E⃗| = h′(k) is clearly not a loss of generality.) Since h′ is increasing, we can assume k = min E_{1}, and therefore h′(min E_{1}) = h(min w_{k})). Let E′_{j} = ⋃_{j∈E_{i}} w_{j}. Then ⟨min w_{k}, E′_{1}, …, E′_{h′(k)}⟩ is h-admissible, by the inductive assumption we have

\frac{1}{2} ∑_{j=1}^{h′(k)} τ_{f′,h′,n}(E_{j}A) ≤ \frac{1}{2} ∑_{j=1}^{h(min w(k))} τ_{f,h}(E′_{j}w_{A}) ≤ τ_{f,h}(w_{A}),

and this ends the verification of the left-hand side inequality.

Now we prove the right-hand side inequality. Let h^{∗}(i) = 2h′′(i). Since 2h′′(i) ≤ h′′(i + h′′(i)), Lemma 5.1 implies τ_{f′,h^{∗},n} ≤ 3τ_{f′h′′,n} for all n, and therefore it suffices to prove

τ_{f,h,n}(w_{A}) ≤ 2 · τ_{f′,h^{∗},n}(A)

using the induction on n. When n = 0 for some i ∈ A we have

τ_{f,h,0}(w_{A}) = τ_{f,h,0}(w_{i}) ≤ τ_{f,h}(w_{i}) = τ_{f′,h′′,0}(i) ≤ 2 · τ_{f′,h^{∗},0}(A).

Now we assume the lemma is true for n and prove it for n+1. Again we can assume that τ_{f,h,n+1}(w_{A}) > τ_{f,h,n}(w_{A}), therefore for some h-admissible ⟨k, E⃗⟩ (without a loss of generality, we can assume that k = min E_{1} and |E⃗| = h(k)) we have

τ_{f,h,n+1}(w_{A}) = \frac{1}{2} ∑_{l=1}^{h(k)} τ_{f,h,n}(E_{l}w_{A}).

We can assume w_{A} ⊆ ⋃_{l=1}^{h(k)} E_{l}. Let E_{l}^{−} = {i : min(w_{i}) ∈ E_{l}} and E_{l}^{+} = {i : max(w_{i}) ∈ E_{l}}. Then by the inductive assumption

\frac{1}{2} ∑_{l=1}^{h(k)} τ_{f,h,n}(E_{l}w_{A}) ≤ \frac{1}{2} ∑_{l=1}^{h(k)} 2τ_{f,h,n}(E_{l}^{+}A) + \frac{1}{2} ∑_{l=1}^{h(k)} 2τ_{f,h,n}(E_{l}^{−}A)

≤ \frac{1}{2} ∑_{l=1}^{h(k)} 2τ_{f′,h^{∗},n}(E_{l}^{+}A) + \frac{1}{2} ∑_{l=1}^{h(k)} 2τ_{f′,h^{∗},n}(E_{l}^{−}A)

If j = min(⋃_{l=1}^{h(k)}(E_{l}^{+} ∪ E_{l}^{−})), then h′′(j) = h(max w_{j}) ≥ h(min E_{1}) = h(k), also h^{∗}(j) = 2h′′(j) ≥ 2h(k), so that ⟨j, E⃗^{∗}⟩ (where E⃗^{∗} is the increasing enumeration of ⋃_{l=1}^{h(k)}(E_{l}^{−} ∪ E_{l}^{+})) is h^{∗}-admissible, so that the right-hand side is equal to at most 2τ_{f′,h^{∗},n+1}(A). As pointed out earlier, this concludes the proof since τ_{f′,h^{∗},n+1} ≤ τ_{f′,h′′,n+1} for all n.

We are now prepared for the main result of this section.

Proposition 5.3. Assume f: ℕ → ℝ is nonnegative h: ℕ → ℕ is strictly increasing. If w_{1} < w_{2} < … are finite sets, then for f′(i) = τ_{f,h}(w_{i}) and h′(i) = h(min w_{i}) we have T_{f′,h′} = {A : w_{A} ∈ T_{fh}}.

Proof Let h′′(i) = max(w_{i}) and (h′)^{+}(i) = h′(i + h′(i)). Since h′′ ≤ (h′)^{+}, Lemmas 5.1 and 5.2 imply that for every A we have

τ_{f′h′}(A) ≤ τ_{f,h}(w_{A}) ≤ 6τ_{f′h′′}(A) ≤ 6τ_{f′(h′)^{+}}(A) ≤ 18τ_{f′h′}(A),

thus τ_{f,h}(w_{A}) = ∞ if and only if τ_{f′h′}(A) = ∞, and the two ideals coincide.

6. Good sequences

An important part of the proof of Theorem 3.1 is in proving its weaker version:

Proposition 6.1. If h is strictly increasing, the ideals T_{fh} and I_{1/n} are different.

Proof Assume the contrary, that T_{fh} = I_{1/n}. Note that we can assume lim_{i} f(i) = 0, for otherwise there would be an infinite set A none of whose infinite subsets is in T_{fh}, but there is no such set for I_{1/n}.

Claim 6.2. There is a sequence t_{1} < t_{2} < … and N ∈ ℕ such that a) ν_{f} ≤ Nν_{1/n} on ⋃_{i} t_{i}, and

b) inf_{i}(τ_{1}(t_{i})) > 0.

Proof Let I_{m} = [m, m+h(m)) and note that τ(I_{m}) = τ_{1}(I_{m})/2 = ν_{f}(I_{m})/2. We shall prove that there is an N ∈ ℕ such that if t_{m}^{0} = {k ∈ I_{m} : k·f(k) < N}, then all but finitely many t_{m}^{0} satisfy ν_{1/n}(t_{m}^{0}) ≥ (ln 2)/2. If can find such a sequence, then we can take t_{i} to be its subsequence satisfying t_{1} < t_{2} < …, and a) will be satisfied. To assure b), note that lim inf_{i} ν_{f}(t_{i}) > 0, since otherwise there would be an infinite C ⊆ ℕ such that Y = ⋃_{i∈C} t_{i} satisfies ν_{f}(Y) < ∞, but then Y ∈ T_{fh} \ I_{1/n}, contradicting our assumptions. Therefore we can find a subsequence of t_{i} which satisfies inf_{i} ν_{f}(t_{i}) > 0, and since t_{i} ⊆ [m_{i}, m_{i} +h(m_{i})) for some m_{i}, this implies b).

Assume that N as above does not exist. Then we can find {m(N)}_{N=1}^{∞} satisfying 1. ν_{1/n}{k ∈ I_{m(N)} : k · f(k) < 2^{N}} < (ln 2)/2,

2. k > 2^{N} for all k ∈ I_{m(N)}, f(k) < 2^{−N}, and

3. intervals I_{m(N)} are pairwise disjoint. Since ν_{1/n}(I_{m}) ≥ ln(m + h(m)) − ln(m) ≥ ln 2 for all m, by 1. we have

ν_{1/n}\{k ∈ I_{m(N)} : k · f(k) ≥ 2^{N}\} > \frac{ln 2}{2}.

Let s_{N} ⊆ I_{m(N)} be such that

4. k · f(k) ≥ 2^{N} for all k ∈ s_{N}, and

5. |ν_{1/n}(s_{N}) − 2^{−N+1}| < 2^{−N}. (Note that 5. can be assured by using 2.) Then we have

τ(s_{N}) = \frac{ν_{f}(s_{N})}{2} ≥ 2^{N}ν_{1/n}(s_{N}) ≥ 2^{N} · 2^{−N} = 1

therefore ⋃_{N} s_{N} ∈ I_{1/n} \ T_{fh}, contradicting our assumption and completing the proof.

We will use {t_{i}} given by Claim 6.2 to find {w_{j}} such that for all j

6. w_{1} < w_{2} < … are included in ⋃_{i} t_{i},

7. τ_{j+1}(w_{j}) ≥ 2^{−j+1}, and

8. τ_{j}(w_{j}) ≤ 2^{−j}.

Assume {w_{j}} satisfy 6–8 above, and find v_{j} ⊆ w_{j} such that τ(v_{j}) ≤ 3τ_{j+1}(w_{j})/2 and τ_{j+1}(v_{j}) = τ_{j+1}(w_{j}). Therefore τ(v_{j}) < 2^{−j+2} and by Lemma 4.4 we have ν_{f}(v_{j}) ≥ 2^{j+1}(2^{−j+1} − 2^{−j}) = 2. Note that τ ≤ ν_{f} and ν_{f} ≤ Nν_{1/n} on the set X = ⋃_{j} v_{j} ⊆ ⋃ t_{i}, and therefore lim_{n} τ(X \ n) < ∞ and lim_{n} ν_{f}(X \ n) = ∞. This implies X ∈ T_{fh} \ I_{f} ⊆ T_{fh} \ I_{1/n}, contradicting our assumptions.

Therefore it will suffice to find {w_{i}} satisfying 6–8 above. We shall do this by using the following notion (recall that u_{A} = ⋃_{i∈A} u_{i}).

Definition 6.3. A sequence u_{1} < u_{2} < … of finite sets is m-good for f, h (or simply m-good if f, h are clear from the context) if there exists a δ > 0 such that:

i) the set {τ_{m}(u_{i}) : i ∈ ℕ} is dense in [0, δ], and ii) lim_{i} τ_{m−1}(u_{[i,∞)}) = 0.

Lemma 6.4. Assume lim_{n} f(n) = 0 and h is strictly increasing. If a sequence {u_{i}} is m-good and a, ε > 0, then there is a finite v ⊆ ⋃_{i} u_{i} satisfying |τ_{m+1}(v) − a| < ε and τ_{m}(v) < ε.

Proof We can assume that ε < δ, where δ is as in the definition of good sequence. By going to a subsequence we can also assume that for all i we have

(*) τ_{m−1}^{max u_{i}}(u_{[i+1,∞)}) < ε (taking max(u_{0}) = 1).

The set A = {i : τ_{m}(u_{i}) < ε/2} is infinite and lim sup_{k∈A} τ_{m}(u_{k}) = ε/2 (because the sequence {u_{i}} is m-good and the corresponding δ is bigger than ε/2). By 4. of Lemma 3.2 we have τ_{m+1}(u_{A}) = ∞. Therefore we can find v ⊆ u_{A} such that τ_{m+1}(v) ≥ a, τ_{m+1}(v′) < a for every v′ ⊊ v, and f(j) < ε for every j ∈ v. Then by the subadditivity of τ_{m+1} we have |τ_{m+1}(v) − a| = τ_{m+1}(v) − a < ε. By Lemma 4.5 (applied with δ = ε) we have τ_{m}(v) < ε, therefore v is as required.

Lemma 6.5. Assume lim_{n} f(n) = 0 and h is strictly increasing. Then for every m-good sequence {u_{i}} there is an m+1-good sequence {v_{i}} such that ⋃_{i} v_{i} ⊆ ⋃_{i} u_{i}.

Proof Let q_{i} (i ∈ ℕ) be an enumeration of all rationals in the interval (0, 1). By using Lemma 6.4, we can recursively find v_{1} < v_{2} < … included in ⋃_{i} u_{i} and such that |τ_{m+1}(v_{i}) − q_{i}| < 2^{−i} and τ_{m}(v_{i}) < 2^{−i}. Then for every i we have τ_{m}(v_{[i,∞)}) < 2^{−i+1}, therefore the sequence v_{i} is m + 1-good.

Let t_{i} be as in Claim 6.2, and let ε = inf_{i} τ_{1}(t_{i}) > 0. Since lim_{n} f(n) = 0, we can find u_{i} ⊆ t_{i} (i ∈ ℕ) so that {τ_{1}(u_{i}) : i ∈ ℕ} is dense in [0, ε]. Since the condition lim_{i} τ_{0}(u_{i}) = 0 reduces to our assumption that lim_{k} f(k) = 0, this sequence is 1good. Therefore the sequence w_{i} as in 6–8 can now be constructed recursively by using Lemma 6.5 and Lemma 6.4. As explained before, this implies that that two ideals differ and concludes the proof.

The above proof gives the following proposition of independent interest (see the proof of [5, Proposition 3.6]).

Proposition 6.6. If lim_{n} f(n) = 0, h: ℕ → ℕ is strictly increasing and

lim inf_{n} ν_{f}([n, n + h(n)) > 0,

then for every m ≥ 1 there is an m-good sequence.

7. Proof of Theorem 3.1

The ideal T_{fh} is, by 5 of Lemma 3.2, an F_{σ} P-ideal. Therefore it remains to prove that P(ℕ)/I_{1/n} ≰_{B} P(ℕ)/T_{fh}. By Lemma 2.1, it will suffice to prove that there is no sequence of finite sets w_{1} < w_{2} < … such that for all A ⊆ ℕ we have (*) A ∈ I_{1/n} if and only if ⋃_{i∈A} w_{i} ∈ T_{fh}. Assume that such a sequence exists. By Proposition 5.3, for some strictly increasing h′ and f′(n) = τ_{f,h}(w_{n}) the ideals I_{1/n} and T_{f′,h′} coincide, but this contradicts Proposition 6.1 and completes the proof.

References

[1] P.G. Casazza, W.B. Johnson, and L. Tzafriri. On Tsirelson’s space. Israel J. Math., 47:81–98, 1984.

[2] P.G. Casazza and T.J. Shura. Tsirelson’s space. Lecture Notes in Mathematics 1363. Springer, 1980.

[3] I. Farah. Analytic quotients. to appear.

[4] I. Farah. Analytic ideals and their quotients. PhD thesis, University of Toronto, 1997.

[5] I. Farah. Basis problem for turbulent actions. preprint, 1998.

[6] W.T. Gowers. Recent results in the theory of infinite-dimensional Banach spaces. In Proceedings of the International Congress of Mathematicians, Zürich 1994, pages 932–942.

[7] G. Hjorth. Actions by classical Banach spaces. preprint, 1996.

[8] G. Hjorth and A.S. Kechris. New dichotomies for Borel equivalence relations. Bull. Symb. Logic, 3:329–346, 1997.

[9] A.S. Kechris. Rigidity properties of Borel ideals on the integers. In 8th Prague topological symposium on general topology and its relations to modern analysis and algebra, 1996, volume 85 of Topology and its applications, pages 195–205, 1998.

[10] A. Louveau. On the size of quotients by definable equivalence relations. In Proceedings of the International Congress of Mathematicians, Zürich 1994, pages 269–276.

[11] K. Mazur. F_{σ}-ideals and ω_{1}ω_{1}^{∗}-gaps in the Boolean algebra P(ω)/I. Fund. Math., 138:103– 111, 1991.

[12] K. Mazur. Towards the dichotomy for F_{σ}-ideals. preprint, 1996.

[13] E. Odell and T. Schlumprecht. Distortion and stabilized structure in Banach spaces; New geometric phenomena for Banach and Hilbert spaces. In Proceedings of the International Congress of Mathematicians, Zürich 1994, pages 955–965.

[14] M.R. Oliver. Borel upper bounds for the Louveau–Velickovic and Mazur towers. preprint, 1998.

[15] S. Shelah. Proper Forcing. Lecture Notes in Mathematics 940. Springer, 1982.

[16] S. Solecki. personal communication. 1997.

[17] S. Solecki. Analytic ideals. Bull. Symb. Logic, 2:339–348, 1996.

[18] B. Velickovic. Definable automorphisms of P(ω)/Fin. Proc. Amer. Math. Soc., 96:130–135, 1986.

[19] B. Velickovic. A note on Tsirelson type ideals. Fund. Math., this issue, 1998.

York University, North York, Canada M3J 1P3

E-mail address: ifarah@mathstat.yorku.ca