A G_{δ} IDEAL OF COMPACT SETS STRICTLY ABOVE

THE NOWHERE DENSE IDEAL IN THE TUKEY ORDER

JUSTIN TATCH MOORE AND SŁAWOMIR SOLECKI

Abstract. We prove that there is a G_{δ} σ-ideal of compact sets which is strictly above NWD in the Tukey order. Here NWD is the collection of all compact nowhere dense subsets of the Cantor set. This answers a question of Louveau and Veličković asked in [4].

1. Introduction

Given two directed partial orders (P, ≤_{P}) and (Q, ≤_{Q}), we say that P is Tukey reducible to Q, in symbols P ≤_{T} Q, if there exists a function f : P → Q such that for each q ∈ Q, {p ∈ P : f(p) ≤_{Q} q} is bounded in P. Tukey reducibility is used to compare the cofinal structure of directed partial orders. The reader is referred to the literature cited in [8] for a glimpse of the work done so far on the subject. Each directed partial order is easily seen to be Tukey bi-reducible with the ideal of its bounded subsets ordered by inclusion. Thus the study of Tukey reducibility is equivalent to the study of Tukey reducibility of ideals of sets ordered by inclusion.

In order to rule out pathologies and make the study more tractable, it is natural to impose additional structural and definability requirements on the ideals under consideration. Recently in [8] the class of basic orders was introduced as a class which both included many of the motivating examples and for which a broad theory of Tukey reduction can be developed. The class of basic orders includes two subclasses of ideals that have emerged as playing a fundamental role. They are the analytic P-ideals of subsets of ω and the analytic σ-ideals of compact sets in a fixed compact metric space. These two classes are referred to in [8], as the measure leaf and the category leaf, respectively. Within each class, one obtains a further automatic reduction in descriptive complexity: the analytic P-ideals are all F_{σδ} (i.e. Π_{3}^{0}) [6] and the analytic σ-ideals of compact sets are all G_{δ} (i.e. Π_{2}^{0}) [3].

Date: January 26, 2008.

2000 Mathematics Subject Classification. Primary: 03E04, 06A07; Secondary:

03E15, 22A26.

Key words and phrases. Ideal of compact sets, Tukey reduction.

The second author acknowledges the support of NSF grant DMS–0700841.

It was proved in [4] that the ideal

\{x ⊆ ω : ∑_{n∈x} \frac{1}{n + 1} < ∞\}

is the largest element with respect to the Tukey reduction in the measure leaf. Louveau and Veličković asked in [4] if the ideal of nowhere dense compact subsets of 2^{ω} is the largest element with respect to the Tukey reduction in the category leaf. In Theorem 3.1, we answer this question in the negative. In fact, we show that there exists a G_{δ}, σideal of compact subsets of 2^{ω} that is Tukey strictly above the nowhere dense ideal. It should be noted, however, that in [7] a condition was isolated which is fulfilled by all “naturally occurring” analytic σ-ideals of compact sets and which insures that the ideal is Tukey reducible to the nowhere dense ideal.

In this note the letters i, j, k, l, m, and n will always represent elements of the set ω of natural numbers. Hence “j < 2” should be interpreted as meaning that j comes from the set {0, 1}. We will use FF to denote the collection of all functions whose domain is a finite, non-empty subinterval of ω and whose range is contained in {0, 1}. We will use ¯0 and ¯1 to denote the constant sequences of unspecified (possibly infinite) length. If σ is in FF, [σ] will be used to denote the clopen set {x ∈ 2^{ω} : σ ⊆ x}. If X is a topological space, NWD(X) will be used to denote the collection of all closed nowhere dense subsets of X. For brevity, we will write NWD for NWD(2^{ω}).

2. The definition of ℐ_{0} and its basic properties

A G_{δ} IDEAL ABOVE NWD 3

The first examples of “exotic” G_{δ} σ-ideals of compact sets were constructed by Mátrai in [5] in order to answer a question of Kechris from [2]. The G_{δ} σ-ideal of compact sets, which will be used to prove our theorem, was defined in [7, Section 6] and was called there ℐ_{0}. We will retain this notation here. We will recall the definition of ℐ_{0} and, for completeness, re-prove that it is a G_{δ}. This proof also draws out some of the important features of the ideal. (After the present paper was completed, Mátrai showed that also his ideal from [5] does not Tukey reduce to NWD. It is not clear if it is Tukey strictly above NWD.)

In order to define the ideal ℐ_{0}, it will be useful to introduce some notation. If x is in 2^{ω} and Π is a partition of ω into finite intervals, let R(x, Π) be the set of all y in 2^{ω} such that for every i < ω there is a j < 2 such that

x ↾ Π(2i + j) = y ↾ Π(2i + j).

Here Π(i) is the element of Π with the i^{th} least minimum.

We will let ℛ denote the collection of all R(x, Π) as x and Π vary over elements of 2^{ω} and partitions consisting of finite non-empty intervals, respectively. Elements of ℛ will be referred to as test spaces. The ideal ℐ_{0} of interest to us is the collection of all compact K ⊆ 2^{ω} such that K ∩ R is nowhere dense in R for every test space R.

While ℐ_{0} is clearly co-analytic, it is not immediately apparent that ℐ_{0} is G_{δ}. If s is in FF, let ℛ_{s} denote the set of all non-empty intersections of the form R ∩ [s] such that R is in ℛ. For brevity, R ∩ [s] will be denoted by R[s]. Notice that membership to ℐ_{0} is equivalent to not containing an element of some ℛ_{s}.

If Π is a partition of ω into finitely many intervals, then we say that Π is degenerate. In this case we can still define R(x, Π) provided some extra care is taken. Let l be the number of elements of Π. If l is even, then R(x, Π) is defined as in the non degenerate case except that i < ω is replaced by i < l/2. If l = 2k + 1, then R(x, Π) is the set of all y such that if i < k, then there is a j < 2 such that

x ↾ Π(2i + j) = y ↾ Π(2i + j).

Observe that if Π consists of an odd number of intervals, then R(x, Π) is clopen and if Π consists of an even number of intervals, then R(x, Π) is the union of a clopen set and a finite set of points which are each eventually equal to x.

The reason for considering degenerate partitions is that the set of all partitions of ω into intervals is compact when equipped with its natural topology. Moreover, the map sending a pair (x, Π) to R(x, Π) is easily seen to be continuous. Since degenerate partitions give rise to sets R(x, Π) with interior, the complement of ℐ_{0} is the union of the closures of the sets ℛ_{s} as s ranges over FF. In particular, ℐ_{0} is a G_{δ} set.

The following propositions will be needed to establish that NWD is below ℐ_{0} in the Tukey order.

Proposition 2.1. If R(x_{0}, Π_{0}) ⊆ R(x_{1}, Π_{1}) are test spaces, then x_{0} = x_{1} and Π_{0} = Π_{1}.

Proof. We will first show that if R(x_{0}, Π_{0}) ⊆ R(x_{1}, Π_{1}), then Π_{0} = Π_{1}. First note that for each i there is k such that max Π_{1}(2i) = max Π_{0}(2k); otherwise it is easy to find a point in R(x_{0}, Π_{0}) which differs from x_{1} at max Π_{1}(2i) and min Π_{1}(2i+1) (and hence is not in R(x_{1}, Π_{1})). Second, for each i, Π_{1}(2i) ∪ Π_{1}(2i + 1) is intersected by at most two intervals of Π_{0}; otherwise there would be an element of R(x_{0}, Π_{0}) which differs from x_{1} at min(Π_{1}(2i)) and max(Π_{1}(2i + 1)). These two conditions together imply that Π_{0} = Π_{1}.

Now we are left to show that if R(x_{0}, Π) ⊆ R(x_{1}, Π), then x_{0} = x_{1}. Suppose that x_{0}(n) ≠ x_{1}(n) for some n and let i < ω and j < 2 be such that n is in Π(2i + j). Define y in 2^{ω} so that y(k) = x_{0}(k) if k is not in Π(2i + 1 − j) and y(k) = 1 − x_{1}(k) if k is in Π(2i + 1 − j). Notice that

y ↾ Π(2i + j) = x_{0} ↾ Π(2i + j) ≠ x_{1} ↾ Π(2i + j)
y ↾ Π(2i + 1 − j) ≠ x_{1} ↾ Π(2i + 1 − j).

Hence y is in R(x_{0}, Π) \ R(x_{1}, Π). □

Proposition 2.2. If an element of ℛ contains an element of ℛ_{s}, then the latter has non-empty interior in the former.

Proof. Suppose that R(x_{1}, Π_{1}) is an element of ℛ and R(x_{0}, Π_{0})[s] is an element of ℛ_{s} such that R(x_{0}, Π_{0})[s] ⊆ R(x_{1}, Π_{1}). Fix i_{0} and i_{1} such that

max(dom(s)) < min(Π_{0}(2i_{0})) ≤ min(Π_{1}(2i_{1})).

Set m = min(Π_{1}(2i_{1})).

We will first show that m is in an element of Π_{0} of even index. Suppose that this is not the case and let i < ω be such that m is in Π_{0}(2i + 1). If n = min(Π_{1}(2i_{1} + 1)) is in Π_{0}(2i + 1), then since dom(s) does not intersect Π_{0}(2i) (by choice of i_{0} and i_{1}), there is a y in R(x_{0}, Π_{0})∩[s] which differs from x_{1} at m and n. The point here is that we are free to put y ↾ Π_{0}(2i) = x_{0} ↾ Π_{0}(2i), leaving us uncommitted to y’s restriction to Π_{0}(2i + 1) and in particular to its values at m and n. If n is not in Π_{0}(2i + 1), then pick l > i and j such that n is in Π_{0}(2l + j). Then find a y in R(x_{0}, Π_{0}) ∩ [s] by first arranging that y agrees with x_{0} on Π_{0}(2i) and Π_{0}(2l + j). We are then free to set the values of y at m and n which are in Π_{0}(2i + 1) and Π_{0}(2l + 1 − j) to something other than x_{1}(m) and x_{1}(n).

Hence m in an element of Π_{0} of even index. Extend s to s̄ such that R(x_{0}, Π_{0}) ∩ [s̄] is non-empty and dom(s̄) = m. Observe that, for j < 2,

R_{j} = {y ∈ 2^{ω} : s̄ˆ y ∈ R(x_{j}, Π_{j})}

is a test space and that R_{0} ⊆ R_{1}. It follows from Proposition 2.1 that Π_{0} and Π_{1} define the same partition on ω \ m and that x_{0} and x_{1} agree on ω \ m. Consequently,

R(x_{0}, Π_{0}) ∩ [s̄] = R(x_{1}, Π_{1}) ∩ [s̄]

and therefore R(x_{0}, Π_{0})[s] has interior in R(x_{0}, Π_{0}).

□

3. ℐ_{0} is strictly above NWD

Theorem 3.1. The ideal ℐ_{0} is strictly above NWD in the Tukey ordering.

First we will show that NWD ≤_{T} ℐ_{0}. Let R be any test space. Since R is homeomorphic to 2^{ω}, it is sufficient to show that NWD(R) ≤_{T} ℐ_{0}. It follows immediately from Proposition 2.2, however, that NWD(R) ⊆ ℐ_{0} and that, moreover, the inclusion map is a Tukey reduction.

We will now prove the following lemma which will be used to show that ℐ_{0} is strictly above NWD in the Tukey order.

Lemma 3.2. Suppose f : 2^{ω} → NWD is Baire measurable and V_{i} (i < ω) enumerates a clopen basis for 2^{ω}. There are x in 2^{ω} and sequences ⟨m_{i} : i < ω⟩ and ⟨n_{i} : i < ω⟩ in ω such that:

(1) n_{0} = 0 and n_{i} < n_{i+1};

(2) V_{m_{i}} is a subset of V_{i} and if i < j and V_{i} = V_{j}, then V_{m_{j}} ⊆ V_{m_{i}};

(3) if y is in 2^{ω}, then either the set of i < ω such that y extends x ↾ [n_{i}, n_{i+1}) is finite or else whenever y extends x ↾ [n_{i}, n_{i+1}), then f(y) is disjoint from V_{m_{i}}.

Proof. Let f and V_{i} (i < ω) be given as in the statement of the lemma. Suppose that, for some k, we have constructed ⟨m_{i} : i < k⟩, ⟨n_{i} : i < k⟩, and x ↾ n_{k−1}. Suppose further that we have arranged that, for each i < k − 1, f^{−1}({K ∈ NWD : K ∩ V_{m_{i}} = ∅}) is comeager in [σ_{i}] where σ_{i} = x ↾ [n_{i}, n_{i+1}) and that we have fixed a decreasing sequence of open sets U_{i}^{j} ⊆ [σ_{i}] (j < ω) with U_{i}^{j} dense in σ_{i} for all j and with

⋂_{j=0}^{∞} U_{i}^{j} ⊆ f^{−1}({K ∈ NWD : K ∩ V_{m_{i}} = ∅}).

The following claim will be useful.

Claim. Suppose that for some k < ω, {σ_{i}}_{i<k} is a sequence of elements of FF and {U_{i}}_{i<k} is a sequence of open sets such that U_{i} ⊆ [σ_{i}] is dense in [σ_{i}] for each i < k. If n < ω is such that dom(σ_{i}) ⊆ n for all i, then there is a τ in FF with n = min(dom(τ)) such that [σ_{i} ∪ τ] ⊆ U_{i} for each i < k.

Proof of Claim. Let {σ_{i}}_{i<k}, {U_{i}}_{i<k}, and n be given as in the statement of the lemma. Construct τ_{ξ} (ξ ∈ 2^{n}) such that the domain of τ_{ξ} is interval, τ_{ξ} is an initial part of τ_{η} whenever ξ <_{lex} η, min(dom(τ_{ξ})) = n for all ξ in 2^{n}, and if ξ extends σ_{i} for some i < k, then [ξ ∪ τ_{ξ}] is a subset of U_{i} ∩ [ξ]. The proof is finished by setting τ equal to τ¯1. □

Returning to the proof of Lemma 3.2, the claim allows us to find a τ in FF such that min(dom(τ)) = n_{k−1} and for all i < k, [σ_{i} ∪ τ] ⊆ U_{i}^{k}. By the Baire category theorem, there is an m_{k} < ω such that V_{m_{k}} ⊆ V_{k} and

[σ ∪ τ] ∩ f^{−1}({K ∈ NWD : K ∩ V_{m_{k}} = ∅})

is non-meager where σ = ⋃_{i<k} σ_{i}. Since f is Baire measurable, we can fix n_{k} and σ_{k} : [n_{k−1}, n_{k}) → 2 such that σ_{k} extends τ and f^{−1}({K ∈ NWD : K ∩V_{m_{k}} = ∅}) is comeager in [σ ∪σ_{k}]. The recursion is finished by fixing a decreasing sequence U_{k}^{j} (j < ω) of open dense subsets of [σ ∪ σ_{k}] satisfying

⋂_{j=0}^{∞} U_{k}^{j} ⊆ f^{−1}({K ∈ NWD : K ∩ V_{m_{k}} = ∅}).

Now suppose that y is in 2^{ω} and that there are infinitely many i < ω such that σ_{i} ⊆ y. If σ_{i} ⊆ y, then we claim that y is in U_{i}^{j} for all j < ω and consequently f(y) is disjoint from V_{m_{i}}. In order to see this, let j be given. Pick a k > j such that σ_{k} ⊆ y. Then y is in U_{k} ⊆ U_{j}, as desired. □

We are now ready to finish the proof of Theorem 3.1. Suppose for contradiction that F : ℐ_{0} → NWD is a Tukey reduction. By [8, Theorem 5.3(i)], we may assume without loss of generality that F is measurable with respect to the σ-algebra generated by analytic sets. Define f : 2^{ω} → NWD by setting f(x) = F ({x}). Now, f is also measurable with respect to the σ-algebra generated by analytic sets and, therefore, it is Baire measurable. Let V_{i} (i < ω) be an enumeration of the non-empty clopen subsets of 2^{ω} such that for all i, V_{2i+1} = V_{2i}. Let x, ⟨m_{i} : i < ω⟩, and ⟨n_{i} : i < ω⟩ be given as in the conclusion of Lemma 3.2. Define

E = 2^{ω} \ ⋃_{i=0}^{∞} V_{m_{2i+1}}

and let R be the set of all y in 2^{ω} such that for every i < ω, there is a j < 2 such that

y ↾ [n_{2i+j}, n_{2i+j+1}) = x ↾ [n_{2i+j}, n_{2i+j+1}).

The set R is a test space and hence {{y} : y ∈ R} is unbounded in ℐ_{0}. On the other hand, E is nowhere dense since if U ⊆ 2^{ω} is open, there is an i < ω such that V_{i} ⊆ U and then V_{m_{2i+1}} ⊆ V_{m_{2i}} ⊆ V_{i} is disjoint from E. Also, if y is in R, then f(y) is disjoint from V_{m_{2i+1}} for any i < ω and consequently F ({y}) ⊆ E for every y in R. It follows that F^{−1}({K ∈ NWD : K ⊆ E}) is unbounded, contradicting our assumption that F was a Tukey map. The theorem is therefore proved.

Two remarks about the proof above are in order. First, Proposition 2.2 shows that whenever L is a compact set which is positive with respect to ℐ_{0}, there is a positive compact set K ⊆ L such that both ℐ_{0} ↾ K ≤_{T} NWD and NWD ≤_{T} ℐ_{0} ↾ K. This suggests the following question: If 𝒥 is a G_{δ} σ-ideal of compact sets, must every 𝒥 -positive compact set contain a 𝒥 -positive compact set K such that 𝒥 ↾ K ≤_{T} NWD? Second, in order to deny the existence of a Tukey function from ℐ_{0} to NWD, we needed to analyze its restriction to the set of all singletons of the underlying space. This occurs frequently in proofs of non-existence of Tukey functions defined on ideals of compact sets. Its first appearance we found in [1, 3M Proposition (a)].

References

[1] David H. Fremlin, The partially ordered sets of measure theory and Tukey’s ordering, Note Mat., 11:177–214, 1991.

[2] Alexander S. Kechris. Hereditary properties of the class of closed sets of uniqueness for trigonometric series. Israel J. Math., 73(2):189–198, 1987.

[3] Alexander S. Kechris, Alain Louveau, and W. Hugh Woodin. The structure of σ-ideals of compact sets. Trans. Amer. Math. Soc., 301(1):263–288, 1987.

[4] Alain Louveau and Boban Veličković. Analytic ideals and cofinal types. Ann. Pure Appl. Logic, 99(1-3):171–195, 1999.

[5] Tamas Mátrai. Kenilworth. Preprint, August 2007.

[6] Sławomir Solecki. Analytic ideals and their applications. Ann. Pure Appl. Logic, 99(1-3):51–72, 1999.

[7] Sławomir Solecki. G_{δ} ideals of compact sets. Preprint, December 2007.

[8] Sławomir Solecki and Stevo Todorcevic. Cofinal types of topological directed orders. Ann. Inst. Fourier (Grenoble), 54(6):1877–1911, 2004.

Department of Mathematics, Cornell University, Ithaca, NY 14853– 4201, USA

Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 W. Green Street, Urbana, IL 61801-2975, USA