Luzin and anti-Luzin almost disjoint families

Judith Roitman^{1} and Lajos Soukup^{2}

University of Kansas, Mathematical Institute of the Hungarian Academy of Science

November, 1997

Abstract. Under MA_{ω_{1}} every uncountable almost disjoint family is either anti-Luzin or has an uncountable Luzin subfamily. This fails under CH. Related properties are also investigated.

0. Introduction

This paper looks at two combinatorial properties of almost disjoint families, Luzin and anti-Luzin, along with some variants.

Let A be an uncountable almost disjoint family on a countable set W.

Definition 0.1. A is Luzin iff there is an enumeration A = {a_{α} : α < ω_{1}} such that for all w ∈ [W]^{<ω}, α < ω_{1}, {β < α : a_{α} ∩ a_{β} ⊂ w} is finite.

Definition 0.2. A is anti-Luzin iff ∀B ∈ [A]^{ω_{1}}∃C, D ∈ [B]^{ω_{1}} ⋃ C ∩ ⋃ D is finite.

The notion of “Luzin” is somewhat standard. The notion of “anti-Luzin” is new. Luzin almost disjoint families are an analogue of Hausdorff gaps: they exist (via

a diagonal construction) in ZFC, and because of the finitary nature of the definition the property of “Luzin” is upwards absolute. Perhaps because of this similarity, they have been called Luzin gaps.

Anti-Luzin families also exist in ZFC, as canonical objects: any uncountable set of branches of a countable tree T is an anti-Luzin family on T.

Luzin and anti-Luzin families are hereditary in the following sense: uncountable subfamilies of Luzin (respectively anti-Luzin) almost disjoint families are Luzin (respectively anti-Luzin).

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 54G20, 03E35, 04A20, 06E99.

Key words and phrases. Luzin, almost disjoint family.

1 Partially supported by the University of Kansas General Research Fund grant # 3058

2 Supported by the Hungarian National Foundation for Scientific Research grant # 16391

Definition 0.3. A is near-Luzin iff ∀C, D ∈ [A]^{ω_{1}} ⋃ C ∩ ⋃ D is infinite.

We will rely heavily on the following obvious statement: A is anti-Luzin iff it has no uncountable near-Luzin subfamily.

Near-Luzin first appeared in [HJ], where it was called ω_{1}-full: near-Luzin families give rise to compact Hausdorff spaces in which the intersection of any two uncountable open sets is non-empty.

Claim 0.4. If A is Luzin then it is near-Luzin.

Proof. Fix an arbitrary enumeration {a_{α} : α < ω_{1}} of A. Suppose A is not near-Luzin. Then there are uncountable C, D ⊂ A with ⋃ C ∩ ⋃ D = w finite. So for each c ∈ C, d ∈ D, c ∩ d ⊂ w. There is α with a_{α} ∈ C, {a_{β} ∈ D : β < α} infinite. So A is not Luzin.

Corollary 0.5. An anti-Luzin family is not Luzin.

While superficially corollary 0.5 does not reverse (a disjoint union of a Luzin and an anti-Luzin family is neither Luzin nor anti-Luzin), does it reverse in any deep sense? In particular, must any uncountable almost disjoint family which does not embed one embed the other? The answer is yes and no.

Theorem 0.6. Assume MA_{ω_{1}}. Every uncountable almost disjoint family is either anti-Luzin or contains an uncountable Luzin subfamily.

Theorem 0.7. Assume |^{•}. There is an uncountable almost disjoint family which contains no uncountable anti-Luzin and no uncountable Luzin subfamilies.

Here |^{•} is the following weakening of CH: There is a family S ⊂ [ω_{1}]^{ω} of size ω_{1} so that every uncountable subset of ω_{1} contains a set in S.

Theorem 0.6 says that under MA_{ω_{1}}, almost disjoint families have a lot of structure. Theorem 0.7 says that under |^{•} they don’t. This used to be what one would expect, but recent work on iterating totally proper forcing while preserving CH has changed our expectations. In particular, Abraham and Todorcevic showed the consistency of “CH + all (ω_{1}, ω_{1})-gaps contain an uncountable Hausdorff sub-gap.” If Luzin almost disjoint families were combinatorially similar to Hausdorff gaps the conclusion of theorem 0.6 would also be consistent with CH. Thus theorem 0.7 destroys the parallel between Luzin almost disjoint families and Hausdorff gaps.

In section 1 we prove theorem 0.6, in section 2 we prove theorem 0.7, in the rest of the paper we explore some of the fine combinatorial structure of these notions.

Conventions. In this paper almost disjoint families are collections of infinite sets whose pairwise intersections are finite; the superscript “^{∗}” means “mod finite; ” all trees grow upward; and properties are listed consecutively no matter what theorem, lemma, or definition they occur in, so if there is a reference to property 17 the reader can easily find it.

Acknowledgment. We would like to express our thanks to the referees for his (her) numerous valuable suggestions and comments.

1. Proof of Theorem 0.6

Assume MA_{ω_{1}}. Let A = {a_{α} : α < ω_{1}} be an almost disjoint family which is not anti-Luzin. By moving to a possibly smaller subfamily, we may assume A is near-Luzin.

Let ℙ be the set [ω_{1}]^{<ω} under the following partial order:

p ≤ q iff p ⊃ q and ∀α ∈ p \ q∀β ∈ q if α < β then a_{α} ∩ a_{β} ⊄ k_{q}

where k_{q} = max ⋃{a_{α} ∩ a_{β} : {α, β} ∈ [q]^{2}}.

Remark 1.1. If β > sup p then p ∪ {β} ≤ p.

A quick ad hoc definition: for s, t ⊂ ON, s ≪ t iff sup s < inf t.

Remark 1.2. If r, s, t are disjoint, r ≪ s ∪ t, p = r ∪ s, q = r ∪ t and k_{p} = k_{q} = k, then p, q are compatible iff for all α ∈ s, β ∈ t a_{α} ∩ a_{β} ⊄ k.

By remark 1.1, enough sets are dense so that if ℙ is ccc then, by MA_{ω_{1}}, there is a generic filter G so that {a_{α} : α ∈ ⋃ G} is Luzin. Remark 1.2 will be used to show ccc.

Lemma 1.3. Suppose n, k ∈ ω and suppose E ∈ [[ω_{1}]^{n}]^{ω_{1}} is pairwise disjoint. Then there are s ≠ t ∈ E with a_{α} ∩ a_{β} ⊄ k for all α ∈ s, β ∈ t.

To prove lemma 1.3 we need

Sublemma 1.3.1. If S, T are uncountable disjoint subsets of ω_{1} and k < ω then there are S′ ∈ [S]^{ω_{1}} T′ ∈ [T]^{ω_{1}} and k′ > k with k′ ∈ a_{α} ∩ a_{β} for all α ∈ S′, β ∈ T′.

Proof of sublemma 1.3.1. Otherwise for all k′ > k either S(k′) = {α ∈ S : k′ ∈ a_{α}} is countable or T (k′) = {α ∈ T : k′ ∈ a_{α}} is countable. Let S′′ = S \⋃{S(k′) : k′ > k and S(k′) is countable}. Let T′′ = T \ ⋃{T (k′) : k′ > k and T (k′) is countable}. S′′ and T′′ are uncountable and ⋃_{α∈S′′}(a_{α} \ k) ∩ ⋃_{β∈T′′}(a_{β} \ k) = ∅, contradicting our hypothesis on A.

Proof of lemma 1.3. For s ∈ E we write s = {α(s, i) : i < n} Let {(i_{m}, j_{m}) : m < n^{2}} enumerate n × n. Using lemma 1.3.1 iteratively, at each stage m we have uncountable disjoint subsets of E, E(m), F (m), with E(m) ⊃ E(m + 1), F (m) ⊃ F (m + 1), and k_{m} > k with k_{m} ∈ a_{α(s,i_{m})} ∩ a_{α(t,j_{m})} for all s ∈ E(m), t ∈ F (m). But then for α ∈ s ∈ E(n^{2} − 1), β ∈ t ∈ F (n^{2} − 1), a_{α} ∩ a_{β} ⊄ k.

Lemma 1.4. ℙ is ccc.

Proof. Given an uncountable subset F of ℙ we may without loss of generality assume that for some n, F ⊂ [ω_{1}]^{n}; F is a Δ-system with root r so that each p ∈ F has the form r ∪ s_{p}; there is some k with ∀p ∈ F k = k_{p}; and E = {s_{p} : p ∈ F } is well-ordered by ≪. By the lemma there are p ≠ q ∈ F so that for all α ∈ s_{p}, β ∈ s_{q}, a_{α} ∩ a_{β} ⊄ k. By remark 1.2, p, q are compatible.

2. Proof of Theorem 0.7

In this section we prove theorem 0.7. In the next section we will give a stronger version, but the combinatorics are sufficiently complicated that it makes sense to give the weaker proof first and then show how to improve it.

Let {S_{α} : α < ω_{1}} be a |^{•}-sequence, i.e. each S_{α} ⊂ α and every uncountable X ⊂ ω_{1} contains some S_{α}.

The family A = {f_{α} : α < ω_{1}} will be a subset of ℘(ω × ω), where each f_{α} is a function from ω to ω.

We require:

1. if α ≠ γ then {i : f_{α}(i) = f_{γ}(i)} is finite

2. if β ≤ α then f_{α} ∩ ⋃_{γ∈S_{β}} f_{γ} is infinite
3. if β ≤ α then ∃n {γ ∈ S_{β} : f_{α} ∩ f_{γ} ⊂ n × n} is infinite.

Property 1 makes A almost disjoint and property 2 makes it near-Luzin (hence prevents an uncountable anti-Luzin subfamily). Finally, property 3 prevents an uncountable Luzin subfamily. Indeed, let {f_{α_{ν}} : ν < ω_{1}} be an enumeration of an uncountable subfamily of A. Pick β < ω_{1} with S_{β} ⊂ {α_{ν} : ν < ω_{1}}. Let I = {ν : α_{ν} ∈ S_{β}} and fix μ < ω_{1} such that α_{μ} ≥ β and μ > sup I. Then, by 3, there is m ∈ ω such that {ν < μ : f_{α_{ν}} ∩ f_{α_{μ}} ⊂ m × m} is infinite, which contradicts the requirement formulated in definition 0.1. So {f_{α_{ν}} : ν < ω_{1}} is not Luzin.

Some preliminaries:

Definition 2.1. A set F ⊂ ω × ω is fat iff lim sup_{n} |π_{n}F | = ω, where π_{n}F = {j : (n, j) ∈ F }.

Notice that if ∃U a finite family of functions with F ⊂^{∗} ⋃ U then F is not fat, and that fat sets are infinite.

Lemma 2.2. If C is an infinite almost disjoint family of functions from ω to ω, then ⋃ C is fat.

Proof. Fix m < ω. Let G ∈ [C]^{m+1}. There is r so that if f ≠ g ∈ G then f|` [r, ω) ∩ g|` [r, ω) = ∅. So m < lim sup_{n}|π_{n} ⋃ G|.

Definition 2.3. Let C be a countable almost disjoint collection of functions from ω to ω. A finite partial function σ from ω to ω is C-free iff ∃^{∞}g ∈ C g ∩ σ = ∅.

Lemma 2.4. Let C be a countable collection of functions from ω to ω. There is a function s : ω → ω + 1 so that if σ is a finite partial function from ω to ω with σ(i) ≠ s(i) for all i ∈ dom σ, then σ is C-free.

Such an s is called C-tight.

Proof. Consider C as a subset of the compact space (ω + 1)^{ω}. Let s be an accumulation point of C in (ω + 1)^{ω}. If σ is a finite partial function from ω to ω with s ∩ σ = ∅ then s ∉ {f : f ∩ σ ≠ ∅} which is closed, so C \ {f : f ∩ σ ≠ ∅} is infinite.

The construction is a straightforward induction, given the following

Lemma 2.5. Let C be a countable almost disjoint collection of functions from ω to ω, let C_{n} ⊂ C for each n < ω, and let F_{n} be fat for each n < ω. Then there is a function f : ω → ω so

4. {f} ∪ C is almost disjoint

5. for each n, f ∩ F_{n} is infinite

6. ∀n∃m_{n} {g ∈ C_{n} : f ∩ g ⊂ m_{n} × {f(i) : i < m_{n}}} is infinite.

The family {f_{α} : α < ω_{1}} will be constructed recursively in ω_{1} steps. Assume that {f_{α} : α < β} is already constructed. Fix an enumeration {β_{n} : n < ω} of β.

Let C = {f_{α} : α < β}, C_{n} = {f_{α} : α ∈ S_{β_{n}}} and F_{n} = ∪C_{n}. Now we can apply lemma 2.5 to get f_{β} as f.

In the next section, we will need to deal with many more fat sets, which is why 2.5 is stated in its current generality.

Proof of lemma 2.5. Let C = {g_{i} : i < ω}.

At stage j we construct a finite set U_{j} (“U” is short for “used up”) of functions in C where U_{j−1} ⊂ U_{j}; we define m_{j} ≥ j, and define f on (m_{j−1}, m_{j}].

So suppose we are at stage j. We know m_{k} for each k < j, f|` m_{j−1} + 1, U_{j−1}, and, for each k < j, we have an C_{k}-tight s_{k}. Our induction hypothesis is that

∀k < j, f|` (m_{k−1}, m_{j−1}] ∩ s_{k}|` (m_{k−1}, m_{j−1}] = ∅.

Let s_{j} be C_{j}-tight.

Since F_{k} is fat, ∀k ≤ j there is some r_{k,j} > m_{j−1} with each r_{k,j} < r_{k+1,j}, and some (r_{k,j}, t_{k,j}) ∈ F_{k} \ ⋃ U_{j−1}. Let m_{j} = r_{j,j}. Let r_{−1,j} = m_{j−1}.

For k ≤ j, let f(r_{k,j}) = t_{k,j}. (This is towards property 5.)

For i ∈ (r_{−1,j}, r_{j,j}) with ∀k i ≠ r_{k,j}, let f(i) be any m ∉ {g(i) : i ∈ U_{j−1}} ∪ {s_{k}(i) : k ≤ j}. (This is towards properties 4 and 6.)

For each k ≤ j

f|` (m_{k−1}, m_{j}] ∩ s_{k}|` (m_{k−1}, m_{j}] = ∅

so f|` (m_{k−1}, m_{j}] is C_{k}-free, for each k ≤ j. Hence, for each k ≤ j there is g_{k,j} ∈ C_{k} \ U_{j−1} with

g_{k,j} ∩ f|` (m_{k−1}, m_{j}] = ∅.

Let

U_{j} = U_{j−1} ∪ {g_{k,j} : k ≤ j} ∪ {g_{j}}.

Property 4 is satisfied: If n ≤ j and i ∈ (m_{j−1}, m_{j}] then g_{n}(i) ≠ f(i), so

f ∩ g_{n} ⊂ m_{n} × {f(i) : i < m_{n}}.

Property 5 is satisfied:

∀j ≥ n f(r_{n,j}) = t_{n,j}

and

(r_{n,j}, t_{n,j}) ∈ F_{n}

so f ∩ F_{n} is infinite.

Property 6 is satisfied: If j ≥ n then

f|` (m_{n−1}, m_{j}] ∩ g_{n,j} = ∅

so

g_{n,j} ∩ f ⊂ m_{n} × {f(i) : i < m_{n}}.

3. A strengthening of theorem 0.7

In this section we strengthen theorem 0.7.

Definition 3.1. An uncountable almost disjoint family A is strongly near-Luzin iff, for every C_{0}, ...C_{n} ∈ [A]^{ω_{1}}, ⋂_{i≤n} ⋃ C_{i} is infinite.

Strongly near-Luzin families appear in [JN], where they are called strong Luzin families. They cannot exist under MA + ¬ CH. The following theorem shows that they need not be Luzin.

Theorem 3.2. Assume |^{•}. There is an uncountable almost disjoint family which is strongly near-Luzin, but has no uncountable Luzin subfamilies.

The proof is somewhat like that of theorem 0.7, but the combinatorics are more complicated, so complicated that we will invoke elementary submodels to avoid stating them explicitly.

So let {S_{α} : α < ω_{1}} be a |^{•}-sequence.

We begin by strengthening property 2 to

7. If β_{0}, ...β_{n} < α and each sup S_{β_{i}}∪(β_{i}+1) < inf S_{β_{i+1}} then f_{α}∩⋂_{i≤n} ⋃_{γ∈S_{β_{i}}} f_{γ} is infinite.

We will be done if the sequence of f_{α}’s satisfies properties 1, 7, and 3. Indeed, as we have seen in the proof of theorem 0.7, property 3 implies that A does not contain an uncountable Luzin subfamily. Property 1 yields that A is almost disjoint. So we need to show that if property 7 holds then A is strongly near Luzin. So let n ∈ ω and I_{0}, …, I_{n−1} ∈ [ω_{1}]^{ω_{1}}. Since {S_{α} : α < ω_{1}} is a |^{•}-sequence we can find β_{0} < β_{1} < ⋯ < β_{n−1} ∈ ω_{1} such that S_{β_{i}} ⊂ I_{i} and sup S_{β_{i−1}} ∪ (β_{i−1} + 1) < min S_{β_{i}}. Then, by property 7, ⋂_{i<n} ⋃{f_{γ} : γ ∈ I_{i}} ⊃ ⋂_{i<n} ⋃{f_{γ} : γ ∈ S_{β_{i}}} is infinite, which was to be proved.

In applying 2.5 in the previous section we had the luxury of knowing that each ⋃ C_{n} was fat. But an intersection of fat sets need not be fat. So we must ensure that the following property holds:

8. If β_{0}, ...β_{n} < α and each sup S_{β_{i}} ∪(β_{i} +1) < inf S_{β_{i+1}}, then ⋂_{i≤n} ⋃_{γ∈S_{β_{i}}} f_{γ} is fat.

Property 8 allows us to construct a family in which property 7 holds. How will we build a family in which property 8 holds?

Definition 3.4. For F ⊂ ω × ω and E ∈ [ω]^{ω} let π_{E}F = F ∩ (E × ω).

To get property 8 to hold, we need to start with enough fat C’s, then have enough E’s so that the resulting π_{E}C’s are fat, iterate the process... Rather then try to define the precise combinatorics of “enough”, we take advantage of elementary submodels which provide all the fat sets we need.

Along with constructing our sequence of functions f_{α}, then, we will construct a sequence of large enough countable elementary submodels {N_{α} : α < ω_{1}} where

{9. each f_{α}, S_{α}, \{N_{β} : β ≤ α\} ∈ N_{α+1}, \{N_{β} : β < α\} ⊂ N_{α}, and \{S_{α} : α < \atop ω_{1}\} ∈ N_{0}.}

Further requirements are:

1. if α ≠ γ then {i : f_{α}(i) = f_{γ}(i)} is finite

10. If C ∈ N_{α} is fat, and E = {n : (n, f_{α}(n)) ∈ C} then π_{E}C is fat.
11. If C ∈ N_{α} is fat, then f_{α} ∩ C is infinite.
12. If S ∈ N_{α} ∩ [α]^{ω} then ∃m {γ ∈ S : f_{γ} ∩ f_{α} ⊂ m × m} is infinite.

Note that property 11 follows from property 10.

As before, property 1 gives us {f_{α} : α < ω_{1}} almost disjoint. It remains to show that properties 10 and 11 imply property 8 (which implies property 7, which implies strongly near-Luzin), and property 12 implies there are no uncountable Luzin subfamilies.

Lemma 3.5. Suppose A = {f_{α} : α < ω_{1}}, {N_{α} : α < ω_{1}} satisfy 1, 9, 10, 11 and 12. Then

(a) A satisfies property 8.

(b) A is has no uncountable Luzin subfamily.

Proof of 3.5 (a). We show by induction on n that if β_{0} < ...β_{n} and each sup S_{β_{i}} < inf S_{β_{i+1}} then ⋂_{i≤n} ⋃_{γ∈S_{β_{i}}} f_{γ} is fat. So suppose β_{0}, ...β_{n}, each sup S_{β_{i}} < inf S_{β_{i+1}}, and C = ⋂_{i<n} ⋃_{γ∈S_{β_{i}}} f_{γ} is fat. Let α < inf S_{β_{n}} with β_{n−1} ∈ N_{α}. Then C ∈ N_{α}. Let {γ_{j} : j < ω} ⊂ S_{β_{n}} with each γ_{j} < γ_{j+1}. Define {E_{j} : j < ω}, {C_{j} : j < ω} as follows: E_{0} = {k : (k, f_{γ_{0}}(k)) ∈ C}, C_{0} = π_{E_{0}}C, E_{j+1} = {k : (k, f_{γ_{j+1}}(k)) ∈ C_{j}}, C_{j+1} = π_{E_{j+1}}C_{j}. By property 9, each C_{j}, E_{j} ∈ N_{β_{j+1}}. By property 10, each C_{j} is fat.

But then, by property 11, each C_{j} ∩ f_{γ_{j}} is infinite, so by A almost disjoint and C_{j} ⊃ C_{j+1}, C ∩ ⋃{f_{γ_{j}} : j < ω} is fat.

Proof of 3.5 (b). Given an uncountable subfamily B of A and an enumeration B = {g_{α} : α < ω_{1}}, where g_{α} = f_{ϕ(α)}, there are α ≤ β < ω_{1} so that S_{α} ⊂ ranϕ ∩ β and ϕ′′β = ranϕ ∩ β. Let δ = ϕ(β) ≥ β. Note that α ∈ N_{α} ⊂ N_{β} ⊂ N_{δ}, so, by property 12, ∃m {γ ∈ S_{α} : f_{γ} ∩ f_{δ} ⊂ m × m} is infinite. Since g_{β} = f_{δ} and ϕ^{−1}S_{α} ⊂ β it follows that B is not Luzin.

Now notice that the construction used in the proof of 2.5 easily adapts to a construction of a family satisfying properties 1, 9, 11, and 12. To get property 10, r_{k,j} is required to satisfy

|π_{r_{k,j}}C_{k}| > j,

which can be done because C_{k} is fat.

4. Trees and anti-Luzin families

The canonical example of an anti-Luzin family is a set of branches of a countable perfect tree, i.e. a countable tree such that there are two incomparable nodes above every node. What about the reverse? Must every anti-Luzin family look like the branches of a tree?

Definition 4.1. An uncountable almost disjoint family A is a tree family iff there is a tree ordering T = (⋃ A, ≺) so that for every a ∈ A there is a branch b of T with a =^{∗} b.

We will show that under CH + ∃ a Suslin line there is an anti-Luzin family which contains no uncountable tree families.

Question 4.2. Is there (under ZFC alone) an anti-Luzin family which contains no uncountable tree families?

While we don’t know the answer to question 4.2, we have a related MA + ¬-CH result.

Definition 4.3. An almost disjoint family A is a hidden tree family iff for some infinite T ⊂ ⋃ A the set {a ∩ T : a ∈ A} is a tree family.

Hidden tree families need not be anti-Luzin. For example, let A = {a_{α} : α < ω_{1}} be a tree family on the set of even integers, and let B = {b_{α} : α < ω_{1}} be Luzin on the set of odd integers. Then {a_{α} ∪ b_{α} : α < ω_{1}} is both Luzin and a hidden tree family.

In fact, under MA + ¬CH all uncountable almost disjoint families of size < 2^{ω} are hidden tree families.

Theorem 4.4. Assume MA(pre-caliber ω_{1}). Then every uncountable almost disjoint family of size < 2^{ω} on ω is a hidden tree family.

Proof of theorem.

We define p ∈ ℙ: p = (T_{p}, ≺_{p}, A_{p}, h_{p}) where T_{p} ∈ [ω]^{<ω}, (T_{p}, ≺_{p}) is a finite tree,

A_{p} ⊂ A is finite,
h_{p} : A_{p} → ω is a function,
each (a \ h_{p}(a)) ∩ T_{p} is linearly ordered by ≺_{p},
∀a ∈ A_{p} ∀n ∈ a ∩ (T_{p} \ h_{p}(a)) ∀k ∈ T_{p} \ h_{p}(a) if k ≺_{p} n then k ∈ a.

We define p ≤ q iff

(a) (T_{q}, ≺_{q}) is an initial subtree of (T_{p}, ≺_{p}),

(b) A_{q} ⊂ A_{p},

(c) h_{q} ⊂ h_{p}, ℙ is easily seen to have pre-caliber ω_{1}.

Subclaim 4.4.1. For each a ∈ A, the set

D_{a} = {p ∈ ℙ : a ∈ A_{p}}

is dense in ℙ.

Proof. Assume that a ∉ A_{p}. Let q = (T_{p}, ≺_{p}, A_{p} ∪ {a}, h_{p} ∪ (a, n)), where n > max T_{p}. Then q ∈ ℙ because a ∩ (T_{p} \ h_{p}(a)) = ∅. The relation q ≤ p is clear. □

Subclaim 4.4.2. For each n ∈ ω and a ∈ A

D_{a,n} = {p ∈ ℙ : a ∈ A_{p} and a ∩ (T_{p} \ n) ≠ ∅}

is dense in ℙ.

Proof. Let p ∈ ℙ. By subclaim 4.4.1 we can assume that a ∈ A_{p}. Let

k ∈ a \ ⋃(A_{p} \ {a}) \ max{T_{p} ∪ n + 1}.

Let q = (T_{p}∪{k}, ≺_{q}, A_{p}, h_{p}), where ≺_{p}⊂≺_{q} and ℓ ≺_{q} k for each ℓ ∈ a∩(T_{p}\h_{p}(a)). Since k ∉ a′ for a′ ∈ A_{p} \ {a} and a ∩ (T_{p} \ h_{p}(A) is linearly ordered by ≺_{p} we have that q ∈ ℙ and clearly q ≤ p. □

Let

D = {D_{a,n} : a ∈ A, n ∈ ω}.

By MA(σ-centered) we have an D-generic filter G. Then

T = (T, ≺) = ( ⋃_{p∈G} T_{p}, ⋃_{p∈G} ≺_{p})

witnesses that A is a hidden tree family: taking h = ⋃_{p∈G} h_{p} we have that (T ∩ a) \ h(a) is a tail of a branch of T .

In contrast we get under CH + ∃ a Suslin line an anti-Luzin family which has no uncountable hidden tree families. In fact we get something stronger.

Definition 4.5. An uncountable almost disjoint family A is a weak tree family iff there is a tree ordering T = (⋃ A, ≺) and a 1-1 function ϕ : A → Br(T) (here Br(T) is the set of branches of T) where range ϕ is pairwise disjoint, and each a ⊂^{∗} ϕ(a).

A is a hidden weak tree family iff, for some T, {a ∩ T : a ∈ A} is a weak tree family.

Weak tree families appeared in [V] where they are called neat families. Velickovic proved the following result (lemma 2.3): Assume MA_{ℵ_{1}}. If A ⊂ [ω]^{ω} is an almost disjoint family then there is an uncountable family B ⊂ A and a partition b = b_{0}∪b_{1} for each b ∈ B such that B_{i} = {b_{i} : b ∈ B} is a weak tree family for i ∈ 2.

Remark. One can consider the following weakening of the notion of weak tree families. An uncountable almost disjoint family A is a very weak tree family iff there are a tree ordering T = (⋃ A, ≺) and a function ϕ : A → [Br(T)]^{<ω} such that the range ϕ is pairwise disjoint and each a ⊂^{∗} ⋃ ϕ(a). A is a hidden very weak tree family iff, for some T, {a ∩ T : a ∈ A} is a very weak tree family.

However, as it was observed by the referee, a hidden very weak tree family can be split into countably many hidden tree families: for every element x of A fix a node of the tree such that above this node x is covered by a single branch, and spit A accordingly.

Theorem 4.6. Assume CH + ∃ a Suslin line. Then there is an uncountable anti-Luzin almost disjoint family which contains no uncountable hidden weak tree families.

First, a quick lemma.

Lemma 4.7. Let T^{∗} be Aronszajn, B an uncountable set of branches of T^{∗} so that no two elements of B have the same order type. Then there are incompatible elements s, t ∈ T^{∗} so that {b ∈ B : s ∈ b} and {b ∈ B : t ∈ b} are uncountable.

Proof of lemma 4.7. By contraposition, suppose B is a set of branches of T^{∗} with different order types so that if s, t are incompatible then either B(s) = {b ∈ B : s ∈ b} is countable or B(t) = {b ∈ B : t ∈ b} is countable. Then S = {s : B(s) is uncountable} forms a chain, hence is countable. So there is α with T^{∗}(α) ∩ S = ∅, where T^{∗}(α) = the set of elements of T^{∗} of height α. But all but countably many elements of B are elements of ⋃_{s∈T^{∗}(α)} B(s), so B is countable.

Proof of theorem 4.6. Let T^{∗} be a Suslin tree so that every element has successors at arbitrarily high levels, and for each t ∈ T^{∗} construct c_{t} ∈ [ω]^{ω} so if s < t then c_{s} ⊃^{∗} c_{t} and if s, t are not comparable then c_{s} ∩ c_{t} =^{∗} ∅. Let B be an uncountable set of branches of T^{∗} so no two elements of B have the same order type and so that every element of ⋃ B is in uncountably many branches of B.

Let B = {b_{α} : α < ω_{1}}.

We will define A = {a_{α} : α ∈ ω_{1}} where

13. for all s ∈ b_{α}, c_{s} ⊃^{∗} a_{α}. A will clearly be almost disjoint. Let {T_{α} = (T_{α}, ≺_{α}) : α < ω_{1}} enumerate all perfect trees whose underlying set

is some infinite subset of ω.

We further require

14. for all β < α either for some s ∈ b_{α} c_{s} ∩ T_{β} is contained, mod finite, in a branch of T_{β}, or a_{α} ∩ T_{β} is not a subset, mod finite, of a branch of T_{β}.

The family A is constructed recursively in ω_{1} many steps. In the αth step we apply lemma 4.8 below to get a_{α}.

Lemma 4.8. Suppose {a_{β} : β < α} satisfies property 13. Then there is a set a satisfying properties 13 and 14.

Proof. Rather than describe the proof as an induction, we will (equivalently) use the Rasiowa-Sikorski lemma (see [K,Theorem 2.21]), defining a countable set of forcing conditions and countably many dense sets so that any generic filter meeting the dense sets gives rise to the desired object.

The partial order is as follows: ℙ consists of all pairs p = (a_{p}, b_{p}) where a_{p} is a finite subset of ω and b_{p} is a finite subset of b_{α}. The order is as follows: p ≤ q iff a_{p} ⊃ a_{q}, b_{p} ⊃ b_{q}, and a_{p} \ a_{q} ⊂ ⋂_{t∈b_{q}} c_{t}.

Clearly {p : |a_{p}| > n} and {p : s ∈ b_{p}} are dense for each n < ω, s ∈ b_{α}, so if G is a filter meeting each of these dense sets then ⋃_{p∈G} a_{p} satisfies property 13.

Towards property 14, fix T = T_{β}, T = T_{β}. We may assume that for every t ∈ b_{α} c_{t} ∩ T is not a subset, mod finite, of a branch of T . For each n < ω define

D(T , n) = {p : a_{p} \ n contains T -incomparable elements}.

We show that D(T , n) is dense for each n.

Fix q ∉ D(T , n). Let c = ⋂_{t∈b_{q}} c_{t}. Since c ∩ T \ n is not a subset, mod finite, of a branch of T , there are two ≺_{β}-incompatible elements, ξ and η, of T ∩ (c \ n). Set a_{p} = a_{q} ∪ {ξ, η}, b_{p} = b_{q}. Then p ∈ D(T , n) and p ≤ q.

If, for all n, G meets D(T , n), ⋃_{p∈G} a_{p} ∩ T will not be a subset, mod finite, of any branch of T . Lemma 4.8 is proved.

The following two lemmas, once proved, will complete the proof of Theorem 4.6.

Lemma 4.9. If property 14 holds, A has no uncountable hidden weak tree families.

Proof. This is where we use that T^{∗} is Suslin.

So suppose B is an uncountable subset of A, T ⊂ ω is infinite, and C = {a ∩ T : a ∈ B} is a collection of infinite sets. We show that C is not a very weak tree family.

Let T = (T, ≺) and ϕ : C → Br(T ). We show that ϕ does not satisfy the properties of definition 4.5.

For some β, T = T_{β}.

Let S = {s ∈ T^{∗} : c_{s} ∩ T is a subset, mod finite, of a branch of T }. If S = ∅, then by property 14 for all but countably many a ∈ B, a ∩ T ⊄^{∗} ϕ(a ∩ T).

Suppose s ∈ S, c_{s}∩T ⊂^{∗} d, where d is a branch of T . Then if s ∈ b_{α}, a_{α}∩T ⊂^{∗} d. Let S′ be the set of T^{∗}-minimal elements of S. By T^{∗} Suslin, S′ is countable. So there is s ∈ S′ with {b_{α} : a_{α} ∈ B and s ∈ b_{α}} uncountable. But then either there are uncountably many α with a_{α} ⊄ ϕ(a_{α} ∩ T), or ϕ is not 1-1.

Lemma 4.10. If property 13 holds, A is anti-Luzin.

Proof. Suppose B is an uncountable subset of A. By lemma 4.7 there are incompatible s, t ∈ T^{∗} with C = {b_{α} ∈ B : s ∈ b_{α}} and D = {b_{α} ∈ B : t ∈ b_{α}} uncountable. Without loss of generality, we may assume that for some n ≥ sup c_{s} ∩ c_{t} if b_{α} ∈ C then a_{α} \ c_{s} ⊂ n and if b_{α} ∈ D then a_{α} \ c_{t} ⊂ n. But then ⋃ C ∩ ⋃ D ⊂ n, as desired.

5. Between near-Luzin and strongly near-Luzin

Definition 5.1. An uncountable almost disjoint family A is k-near-Luzin iff for every C_{0}, ...C_{k−1} ∈ [A]^{ω_{1}}, ⋂_{i<k} ⋃ C_{i} is infinite.

The purpose of this section is to show that these notions are (consistently) distinct.

Clearly near-Luzin is 2-near-Luzin and so every Luzin family is 2-near-Luzin, but not necessarily contains 3-near-Luzin subfamily, as we will see it in theorem 5.5.

Theorem 5.2. The following is consistent: ∀k ∈ [2, ω) there is an uncountable almost disjoint family A_{k} so A_{k} is k-near-Luzin, contains no uncountable Luzin subfamilies, and contains no uncountable k + 1-near-Luzin subfamilies.

The proof proceeds by showing that for every k there is a partial order ℙ_{k} with precaliber ω_{1} forcing A_{k} to exist, and iterating with precaliber ω_{1}. It is easy to see that both k-near Luzin and “no Luzin subfamilies” are preserved by precaliber ω_{1} forcing. The way we ensure no k + 1-near-Luzin subfamilies will also be preserved by precaliber ω_{1} forcing.

Unlike our earlier constructions, each |A_{k}| = 2^{ω}. Each A_{k} is again a family of functions, but instead of functions on ω the domains come from a k-linked not (k + 1)-linked family E_{k} with special properties. This family was first constructed by Hajnal; the construction appeared in [JS].

Lemma 5.3. For all k < ω there is a family E_{k} ⊂ [ω]^{ω} with |E_{k}| = 2^{ω} so that 15. if e_{0}, ...e_{k−1} ∈ E_{k} then ⋂_{i<k} e_{i} is infinite

16. if e_{0}, ...e_{k} are distinct elements of E_{k} then | ⋂_{i≤k} e_{i}| < ω
17. if X ∈ [E_{k}]^{ω_{1}} there are X_{0}, ...X_{k} ∈ [X]^{ω_{1}} with

| ⋂_{i≤k} ⋃ X_{i}| < ω.

Proof. Let S_{k} = {[^{n}2]^{k} : n < ω}. We will construct E_{k} as a subset of [S_{k}]^{ω} but since |S_{k}| = ω, this construction proves the lemma. For f : ω → 2 let e_{f} = ⋃_{n<ω}{s ∈ [2^{n}]^{k} : f|` n ∈ s}. Let E_{k} = {e_{f} : f ∈ 2^{ω}}.

We show that property 15 holds: Given f_{0}, ...f_{k−1} distinct, pick m so {f_{i}|` m : i < k} are distinct. But then for each n ≥ m

{f_{i}|` n : i < k} ∈ ⋂_{i<k} e_{f_{i}}.

We show that property 16 holds: Given f_{0}, ...f_{k} distinct, there is m so {f_{i}|` m : i ≤ k} are distinct. But then ⋂_{i≤k} e_{f_{i}} ⊂ ⋃_{j<m}[2^{j}]^{k+1}.

We show that property 17 holds: Fix X ∈ [E]^{ω_{1}}. Let I = {f : e_{f} ∈ X} and let g_{0}, ...g_{k} be distinct complete accumulation points of I in the usual topology on 2^{ω}. Fix n so g_{0}|` n, ...g_{k}|` n are distinct. Define X_{i} = {e_{f} ∈ E : f|` n = g_{i}|` n}. Then

⋂_{i≤k} ⋃ X_{i} ⊂ ⋂_{j<n}[2^{j}]^{k}

which completes the proof.

Note that by construction properties 15 and 16 are absolute in the following sense: let E = (E_{k})^{M}, and let M ⊂ N, where M, N are models of enough set theory. Then 15 and 16 hold for E in N.

The next lemma says that property 17 is preserved in some models. In this and succeeding proofs we will refer to the following easy fact about ccc forcing:

Fact 5.4. If ℙ is a ccc partial order, P is an uncountable subset of ℙ and Ġ names the generic filter, then there is p ∈ ℙ p ⊩ P ∩ Ġ is uncountable.

Lemma 5.5. Suppose E has the property that if X ∈ [E]^{ω_{1}} there are X_{0}, ...X_{k} ∈ [X]^{ω_{1}} with

| ⋂_{i≤k} ⋃ X_{i}| < ω.

Then E will still have this property in a forcing extension by a precaliber ω_{1} partial order.

Proof. Let ℙ have precaliber ω_{1}, and suppose ⊩_{ℙ} Ẋ = {ẋ_{α} : α < ω_{1}} ∈ [E]^{ω_{1}}. Fix p ∈ ℙ. For each α pick p_{α} ≤ p so for some e_{α} ∈ E p_{α} ⊩ ẋ_{α} = e_{α}. Then there is an uncountable centered family {p_{α} : α ∈ I}. Let Y = {e_{α} : α ∈ I}. By hypothesis there are I_{0}, ...I_{k} ∈ [I]^{ω_{1}} and m < ω with

⋂_{i≤k} ⋃{e_{α} : α ∈ I_{i}} ⊂ m.

Let Ġ be the generic filter, and define

J̇_{i} = {α ∈ I_{i} : p_{α} ∈ Ġ}.

List each I_{i} as {α_{γ}^{i} : γ < ω_{1}}. Let q_{γ} ≤ p_{α_{γ}^{i}} for all i ≤ k. Let Q = {q_{γ} : γ < ω_{1}}. By fact 5.4 there is p ∈ ℙ with p ⊩ |Q ∩ Ġ| = ω_{1}. So ∀i ≤ k p ⊩ J̇_{i} is uncountable, which by a density argument completes the proof.

Lemma 5.6. Suppose E ⊂ ℘(ω) satisfies the following:

if X ∈ [E]^{ω_{1}} there are X_{0}, ...X_{k} ∈ [X]^{ω_{1}} with

| ⋂_{i≤k} ⋃ X_{i}| < ω.

If A = {f_{e} : e ∈ E} where each f_{e} : e → ω then A has no uncountable (k+1)-near Luzin subfamilies.

Proof. If for some finite m

⋂_{i≤k} ⋃ X_{i} ⊂ m

then

⋂_{i≤k} ⋃_{e∈X_{i}} f_{e} ⊂ m × ω.

Let Y_{i} ∈ [X_{i}]^{ω_{1}} so ∃σ_{i} ∀e ∈ Y_{i} f_{e}|` m = σ_{i}. Then

⋂_{i≤k} ⋃_{e∈Y_{i}} f_{e} ⊂ ⋂_{i} σ_{i}.

This completes the proof of lemma 5.6.

Proof of theorem 5.2. Let E_{k} ⊂ [ω]^{ω} be a family satisfying 15–17 from lemma 5.3. We will have A_{k} = {f_{e} : e ∈ E_{k}}, where f_{e} : e → ω is a function for e ∈ E_{k}. By lemma 5.6, this assumption guarantee that A_{k} has no (k +1)-near-Luzin subfamily.

Define ℙ_{k}, a pre-caliber ω_{1} forcing which adds generic almost disjoint functions f_{e} : e → ω for e ∈ E_{k} as follows:

elements of ℙ_{k} have the form p = {σ_{p,e} : e ∈ E_{p}}, E_{p} is a finite subset of E_{k}, each σ_{p,e} is a finite function from e to ω.

The order is: p ≤ q iff E_{p} ⊃ E_{q}

for e ∈ E_{q} σ_{p,e} ⊃ σ_{q,e}
for e ≠ e′ ∈ E_{q} σ_{p,e} ∩ σ_{p,e′} = σ_{q,e} ∩ σ_{q,e′}.

ℙ_{k} is easily seen to have pre-caliber ω_{1}. We define p ⊩ ḟ_{e}(i) = j iff e ∈ E_{p} and σ_{p,e}(i) = j. By a standard genericity argument, ⊩_{ℙ_{k}} [ domḟ_{e} = e and if e ≠ e′ then |ḟ_{e} ∩ ḟ_{e′}| < ω].

Lemma 5.7. ⊩_{ℙ_{k}} Ȧ_{k} is k-near-Luzin.

Proof. Working in V^{ℙ_{k}}, suppose for each i < k we have Ẋ_{i} an uncountable subset of E_{k}. We want to show that ⋂_{i<k} ⋃{ḟ_{e} : e ∈ Ẋ_{i}} is infinite.

We may assume the Ẋ_{i}’s are disjoint, and each Ẋ_{i} = {ė_{α,i} : α < ω_{1}} in a 1-1 enumeration. Fix p ∈ ℙ_{k}. For each α there is p_{α} ≤ p and for each α, i there is d_{α,i} so

p_{α} ⊩ ∀i < k ė_{α,i} = d_{α,i}

and for each α the d_{α,i}’s are distinct.

We may assume the p_{α}’s are centered.

Since the p_{α}’s are centered, and the enumeration is 1-1,

∀i if α ≠ β then d_{α,i} ≠ d_{β,i}.

Pick distinct α_{0}, ...α_{k−1} so that for i ≠ j d_{α_{i},i} ≠ d_{α_{j},j} and (by a Δ-system argument) d_{α_{i},i} ∉ E_{p_{α_{j}}}. By property 15

| ⋂_{i<k} d_{α_{i},i}| = ω.

Let m ∈ ⋂_{i<k} d_{α_{i},i}, m > sup domσ_{p_{α_{i}} ,e} for all i, all e ∈ E_{p_{α_{i}}}. There is q < p_{α_{i}} for all i with σ_{q,d_{α_{i},i}}(m) = 0. So q ⊩ ∃m > n(m, 0) ∈ ⋂_{i<k} ⋃{ḟ_{e} : e ∈ Ẋ_{i}}. A density argument completes the proof.

Lemma 5.8. ⊩_{ℙ_{k}} Ȧ_{k} has no uncountable Luzin subfamilies.

Proof. Suppose {ȧė_{α} : α < ω_{1}} ⊂ A_{k} and p ⊩ the enumeration {ȧė_{α} : α < ω_{1}} witnesses that the family is Luzin. Choose p_{α} ≤ p, d_{α} ∈ E_{k} with p_{α} ⊩ ė_{α} = d_{α} ∈ E_{p_{α}}. We may assume

18. the p_{α}’s are centered

19. {E_{p_{α}} : α < ω} is a Δ-system with root E 20. ∃n∀α E_{p_{α}} = {e_{α,i} : i < n}

21. ∀i∃σ_{i}∀ασ_{p_{α},e_{α,i}} = σ_{i} By necessity

22. ∃m∀i σ_{i} ⊂ m × m. There is q ≤ p_{ω} and k such that q ⊩ ∀i > k ȧė_{i} ∩ ȧė_{ω} ⊄ m × m. By property 19 ∃j ≥ k with E_{q} ∩ E_{p_{j}} = E. We define r ≤ q:

E_{r} = E_{q} ∪ E_{r_{j}}

for e ∈ E_{q}, σ_{r,e} = σ_{q,e}
for e ∈ E_{r_{j}} \ E, σ_{r,e} = σ_{r_{j},e}.

Then r ⊩ ȧė_{j} ∩ ȧė_{ω} = ȧ_{d_{j}} ∩ ȧ_{d_{ω}} ⊂ m × m, a contradiction.

Theorem 5.2 is proved.

Finally, we note that Luzin does not imply 3-near Luzin

Theorem 5.9. There is a Luzin almost disjoint family with no uncountable 3-near Luzin subfamily.

Proof. Let E = E_{2} be as in lemma 5.3. As in theorem 5.2, we construct A = {f_{e} : e ∈ E} where each domf_{e} = e, so A has no uncountable 3-near Luzin subfamily. Here is how we get Luzin.

Let E = {e_{α} : α < ω_{1}}, f_{α} = f_{e_{α}}.

Our induction hypothesis at stage α is that for all β < α and all n < ω {γ < β : f_{e_{γ}} ∩ f_{e_{β}} ⊂ n × ω} is finite. This will certainly give us Luzin.

At stage α fix a 1-1 enumeration {β_{n} : n < ω} of α. In the n^{th} step of the construction of f_{α} we ensure that domf_{α} ∩ n = e_{α} ∩ n and f_{α} ∩ f_{β_{n}} ⊄ n × ω, without increasing f_{α} ∩ f_{β_{m}} for m < n. Since e_{α} ∩ e_{β_{n}} \ ⋃{e_{β_{m}} : m < n} is finite, this can be done, and the construction is complete.

References

[AT]. U. Abraham and S. Todorcevic, Partition properties of ω_{1} compatible with CH, Fund.

Math. 152, 165–181. [EF]. F. Eckertson, W. Fleissner, A. Korovin, R. Levy, Not realcompact images of not Lindel̈of

spaces, Top. and Appl. 58 (1994), 115-125. [HJ]. A. Hajnal, I. Juhász, Intersection properties of open sets, Top. and Appl. 19 (1985), 201-

209. [JN]. I. Juhász, Zs. Nagy, L. Soukup, Z. Szentmiklóssy, Intersection properties of open sets, II,

Delft, Netherlands, Proceedings of the Tenth Summer Conference in General Topology and Applications, (1994,).

[JS]. I. Juhász, L. Soukup, Z. Szentmiklóssy, Combinatorial principles from adding Cohen reals,

Logic Colloquium 95, Haifa, Israel, to appear. [K]. S. Koppelberg, Handbook of Boolean Albegras, Vol I., North Holland, Amsterdam- New

York, 1987. [L]. N. Luzin, O Chastaya natural’nogo ryada, Izv. Akad. Nauk SSSR Ser. Mat. 11 (1947),

714–722. [S]. S. Shelah,, Proper forcing, Springer Lecture Notes in Mathematics Vol 940, (1982). [V]. B. Velickovic, OCA and automorphisms of P(ω)/fin, Top. Appl. 49, (1992), 1–12.

Nov1997

Lawrence, KS 66045; POB 127, H-1364 Budapest, Hungary E-mail address: roitman@math.ukans.edu, soukup@math-inst.hu