ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 10, Pages 51–57 (May 26, 2004) S 1079-6762(04)00129-5

THEOREMS ON SETS NOT BELONGING TO ALGEBRAS

L. Š. GRINBLAT

(Communicated by David Kazhdan)

Abstract. Let A_{1}, …, A_{n}, A_{n+1} be a finite sequence of algebras of sets given on a set X, ⋃_{k=1}^{n} A_{k} ≠ 𝔓(X), with more than \frac{4}{3} n pairwise disjoint sets not belonging to A_{n+1}. It has been shown in the author’s previous articles that in this case ⋃_{k=1}^{n+1} A_{k} ≠ 𝔓(X). Let us consider, instead of A_{n+1}, a finite sequence of algebras A_{n+1}, …, A_{n+l}. It turns out that if for each natural i ≤ l there exist no less than \frac{4}{3} (n + l) − \frac{l}{24} pairwise disjoint sets not belonging to A_{n+i}, then ⋃_{k=1}^{n+l} A_{k} ≠ 𝔓(X). Besides this result, the article contains: an essentially important theorem on a countable sequence of almost σ-algebras (the concept of almost σ-algebra was introduced by the author in 1999), a theorem on a family of algebras of arbitrary cardinality (the proof of this theorem is based on the beautiful idea of Halmos and Vaughan from their proof of the theorem on systems of distinct representatives), a new upper estimate of the function 𝔳(n) that was introduced by the author in 2002, and other new results.

1. Introducton

1.1. Definition. By an algebra A on a set X we mean a nonempty system of subsets of X possessing the following property: if M_{1}, M_{2} ∈ A, then M_{1}∪M_{2}, M_{1}\M_{2} ∈ A.

1.2. Here is some information necessary for understanding the article. All algebras are considered on some abstract set X ≠ ∅. Unless the contrary follows from the context, by a set we always mean a subset of X. As usual, 𝔓(M) denotes the set of all subsets of M. The symbol #(M) denotes the cardinality of the set M. By ℕ^{+} we denote the set of natural numbers. By ℕ we denote the set of nonnegative integers. If n_{1}, n_{2} ∈ ℕ^{+} and n_{1} ≤ n_{2}, then

[n_{1}, n_{2}] = {k ∈ ℕ^{+} | n_{1} ≤ k ≤ n_{2}}.

By ⌈ρ⌉ we denote the maximum integer ≤ ρ. By ⌊ρ⌋ we denote the minimum integer ≥ ρ.

1.3. A few words about the results of the present article. The theorems deduced further develop the theory introduced in [Gr1] and [Gr2]. Note that [Gr1] is fully comprised in [Gr2]. Suppose n ∈ ℕ^{+} and ψ : [1, n] → ℕ^{+} is a function such that if a sequence of algebras A_{1}, …, A_{n} is given and for each k ∈ [1, n] there exist ψ(k)

Received by the editors February 15, 2004. 2000 Mathematics Subject Classification. Primary 03E05; Secondary 54D35. Key words and phrases. Algebra on a set, almost σ-algebra, ultrafilter, pairwise disjoint sets.

\begin{matrix}c \\ ◯ \end{matrix}2004 American Mathematical Society

pairwise disjoint sets not belonging to A_{k}, then ⋃_{k=1}^{n} A_{k} ≠ 𝔓(X). Let us construct the following function:

ψ′(k) = \begin{cases}ψ(k) & if k ∈ [1, n], \\ ⌈\frac{4}{3}n⌉ + 1 & if k = n + 1. \end{cases}

In both [Gr1] and [Gr2] it is shown that if a sequence of algebras A_{1}, …, A_{n+1} is given and for each k ∈ [1, n+1] there exist ψ′(k) pairwise disjoint sets not belonging to A_{k}, then ⋃_{k=1}^{n+1} A_{k} ≠ 𝔓(X). Note that the estimate ⌈\frac{4}{3}n⌉ + 1 is the best possible in a certain sense (see Theorem 2.2(2) in [Gr2]). Now, take l ∈ ℕ^{+} and construct the function as follows:

ψ′′(k) = \begin{cases}ψ(k) & if k ∈ [1, n], \\ ⌊\frac{4}{3}(n + l)⌋ − ⌈\frac{l+24}{24}⌉ & if k ∈ [n + 1, n + l]. \end{cases}

It turns out that if a sequence of algebras A_{1}, …, A_{n+l} is given and for each k ∈ [1, n+l] there exist ψ′′(k) pairwise disjoint sets not belonging to A_{k}, then ⋃_{k=1}^{n+l} A_{k} ≠ 𝔓(X). If l = 1, we arrive at the above-mentioned result from [Gr1] and [Gr2].

Let ψ_{∗} : ℕ^{+} → ℕ^{+} be a function such that if n ∈ ℕ^{+}, a sequence of algebras A_{1}, …, A_{n} is given and for each k ∈ [1, n] there exist ψ_{∗}(k) pairwise disjoint sets not belonging to A_{k}, then ⋃_{k=1}^{n} A_{k} ≠ 𝔓(X). Now, let B_{1}, …, B_{k}, … be a countable sequence of algebras and for each k ∈ ℕ^{+} there exist ψ_{∗}(k) pairwise disjoint sets not belonging to B_{k}. Can we assert that ⋃ B_{k} ≠ 𝔓(X)? Generally speaking, no (see [Gr2]). However, for B_{k} being σ-algebras, it is true. We are interested in the situation when B_{k} are almost σ-algebras. (The concept of an almost σ-algebra was introduces in [Gr1]. Here, it is given in Section 2.5.) We have deduced an essentially important Theorem 2.6 on a countable sequence of almost σ-algebras.

We consider the families of algebras {A_{λ}}_{λ∈Λ} such that for each λ there exist two sets U_{1}^{λ}, U_{2}^{λ} ∉ A_{λ} and U_{i_{1}}^{λ_{1}} ∩U_{i_{2}}^{λ_{2}} = ∅ unless λ_{1} = λ_{2}, i_{1} = i_{2}. Interesting results have been achieved here: Theorem 2.10, when the cardinality of Λ is not restricted in any way, and Theorem 2.14, when #(Λ) = ℵ_{0} and A_{λ} are almost σ-algebras. It should be pointed out that, as was shown in [Gr1] and [Gr2], ⋃_{λ∈Λ} A_{λ} ≠ 𝔓(X) if 1 ≤ #(Λ) < ℵ_{0} and the algebras A_{λ} are not restricted in any way.

Last but not least, we consider an interesting function 𝔳(n), which was introduced in [Gr2]. The problem on the upper estimate is both complicated and interesting. Given here is a new upper estimate of 𝔳(n).

1.4. This section deals with the Main Idea which first appeared in [Gr1] and on which the investigation in [Gr1] and [Gr2] was based. We will consider ultrafilters on X. Each ultrafilter is a point βX, and vice versa, each point βX is an ultrafilter on X. (Here, as usual, βX is the Stone-C̆ech compactification of X in discrete topology.)

Consider an algebra A and a set U ∉ A. There are two possible cases:

1) If U ⊂ D, then D ∉ A; and then there exists an ultrafilter a ∋ U such that if M ∈ a, then M ∉ A.

2) There exists a set D ⊃ U such that D ∈ A; then there exist ultrafilters a, b such that a ∋ U, b ∋ D \ U, and if M belongs to one of those ultrafilters but does not belong to the other one, then M ∉ A.

These arguments lead one to accept the following concepts. An ultrafilter a is said to be A-special if a ∩ A = ∅. Two ultrafilters a, b are said to be A-similar if a ≠ b, there exists D ∈ A, a, b, and, whenever M belongs to one of these ultrafilters but not to the other one, we have M ∉ A.

Notation. If M ⊂ βX , then we denote by \overline{M} the closure of M in βX.

Main Statement. Let {A_{λ}} be a family of algebras. Then ⋃ A_{λ} ≠ 𝔓(X) if and only if there exist sets S, T ⊂ βX such that \overline{S} ∩ \overline{T} = ∅ and for each λ at least one of the following two conditions holds:

(1) there exists an A_{λ}-special ultrafilter z_{λ} ∈ S;

(2) there exist A_{λ}-similar ultrafilters s_{λ}, t_{λ} such that s_{λ} ∈ S and t_{λ} ∈ T.

The considerations given in this section are used in the proofs of all the theorems below.

2. Formulating the results

2.1. Definition. For each pair of numbers n, l ∈ ℕ^{+} define the minimum number 𝔮_{n}^{l} ∈ ℕ such that if A_{1}, …, A_{n}, A_{n+1}, …, A_{n+l} is a sequence of algebras and (1) ⋃_{k=1}^{n} A_{k} ≠ 𝔓(X), (2) for each i ∈ [1, l] there exist ⌈\frac{4}{3}n⌉ + 𝔮_{n}^{l} pairwise disjoint sets not belonging to A_{n+i}, then ⋃_{k=1}^{n+l} A_{k} ≠ 𝔓(X).

2.2. Estimation of numbers 𝔮_{n}^{l} is, no doubt, a very complicated and interesting problem. From what was said in Section 1.3, it follows that

𝔮_{n}^{l} ≤ ⌊\frac{4}{3}(n + l)⌋ − ⌈\frac{l + 24}{24}⌉ − ⌈\frac{4}{3}n⌉.

We have managed to prove the following theorem.

Theorem. 𝔮_{n}^{l} ≤ ⌊\frac{4}{3}(n + l)⌋ − ⌈\frac{l+21}{21}⌉ − ⌈\frac{4}{3}n⌉ if l ≥ 42; 𝔮_{n}^{l} ≤ ⌊\frac{4}{3}(n + l)⌋ − ⌈\frac{l+18}{18}⌉ − ⌈\frac{4}{3}n⌉ if l ≥ 72;

𝔮_{n}^{l} ≤ ⌊\frac{4}{3}(n + l)⌋ − ⌈\frac{l+17}{17}⌉ − ⌈\frac{4}{3}n⌉ if l ≥ 85;
𝔮_{n}^{l} ≤ ⌊\frac{4}{3}(n + l)⌋ − ⌈\frac{l+16}{16}⌉ − ⌈\frac{4}{3}n⌉ if l ≥ 112;
𝔮_{n}^{l} ≤ ⌊\frac{4}{3}(n + l)⌋ − ⌈\frac{l+15}{15}⌉ − ⌈\frac{4}{3}n⌉ if l ≥ 195.

2.3. This section contains concepts and assertions from [Gr2]. Denote by Ψ^{n} (n ∈ ℕ^{+}) the totality of all functions ψ : [1, n] → ℕ^{+} such that if ψ ∈ Ψ^{n}, a sequence of algebras A_{1}, …, A_{n} is given, and for each k ∈ [1, n] there exist ψ(k) pairwise disjoint sets not belonging to A_{k}, then ⋃_{k=1}^{n} A_{k} ≠ 𝔓(X). For each n ∈ ℕ^{+}, denote by 𝔤(n) the minimum natural number such that the function ψ(k) = 𝔤(n) for all k ∈ [1, n] belongs to Ψ^{n}. Let us fix n ∈ ℕ^{+}. By definition, ξ(n; k) is any function (of the variable k) defined on [1,n], taking values in ℕ^{+}, and satisfying

∑_{k=1}^{n} 2^{−⌈\frac{ξ(n;k)+1}{2}⌉} ≤ 1.

It is easy to show that ξ(n; k) ∈ Ψ^{n}. Assume that n ∈ ℕ^{+} and for each k ∈ [1, n] a nonempty class Ψ̃^{k} ⊂ Ψ^{k} is chosen. Let m ∈ ℕ, p ∈ ℕ^{+}, and n ≥ p − m > 0. Define the function (of the variable k) on [m + 1, p] taking values in ℕ^{+} as follows:

ψ(m, p; k) = 2m + ψ(k − m), where ψ ∈ Ψ̃^{p−m}.

Let m ≤ n be natural numbers. One can show that the function

ψ(k) = \begin{cases}ψ(0, m; k) & if k ∈ [1, m], \\ ψ(m, n + 1; k) & if k ∈ [m + 1, n + 1] \end{cases}

belongs to Ψ^{n+1}.

2.4. Fix n ∈ ℕ^{+}. Let m ∈ [1, n]. Using the numbers 𝔮_{m}^{l}, the considerations from [Gr2], and knowing that for each k ∈ [1, n] a nonempty class Ψ̃^{k} ⊂ Ψ^{k} is chosen, one can construct the class Ψ̃^{n+1} ⊂ Ψ^{n+1}. The class Ψ̃^{n+1} is formed by:

1) the functions of the type

ψ(k) = \begin{cases}ψ(0, m; k) & if k ∈ [1, m], \\ ⌈\frac{4}{3}m⌉ + 𝔮_{m}^{n+1−m} & if k ∈ [m + 1, n + 1]; \end{cases}

2) the function ψ(k) ≡ 𝔤(n + 1);

3) the functions of the type ξ(n + 1; k);

4) the functions of the type

ψ(k) = \begin{cases}ψ(0, m; k) & if k ∈ [1, m], \\ ψ(m, n + 1; k) & if k ∈ [m + 1, n + 1]. \end{cases}

(In [Gr2], we present the inductive metod for constructing functions from Ψ^{n}. Yet, it is less perfect since it makes no use of the numbers 𝔮_{m}^{l}.)

2.5. An algebra A is called a σ-algebra if for any countable sequence M_{1}, …, M_{k}, … ∈ A we have A ∋ ⋃_{k=1}^{∞} M_{k}. In [Gr1], there was introduced an essentially important concept: an algebra A is said to be an almost σ-algebra if for any countable sequence of sets M_{1}, …, M_{k}, … such that 𝔓(M_{k}) ⊂ A_{k} for each k, we have ⋃ M_{k} ∈ A. Denote by Ψ the totality of all functions ψ: ℕ^{+} → ℕ^{+} possessing the following property: for each n ∈ ℕ^{+} there exists a function ψ_{n} ∈ Ψ^{n} such that ψ_{n}(k) = ψ(k) for all k ∈ [1, n].

2.6. Let ψ ∈ Ψ, and let A_{1}, …, A_{k}, … be a countable sequences of σ-algebras such that for each k there exist ψ(k) pairwise disjoint sets not belonging to A_{k}. Then, as was mentioned in Section 1.3, ⋃ A_{k} ≠ 𝔓(X). It is not known whether this statement holds true when σ-algebras are replaced with almost σ-algebras.

Let η ∈ ℕ^{+}. If n ∈ [1, η], put Ψ^{n}(η) = Ψ^{n}. If n = η + 1, Ψ^{n}(η) will denote the class of all functions from Ψ^{n} derived with the help of the functions of classes Ψ^{k}(η), where k ≤ n − 1, and by means of the inductive method from Section 2.4. On the analogy, by induction, a class of functions Ψ^{n}(η) is built for each natural n ≥ η + 2. Consider the class of functions Ψ(η) ⊂ Ψ: a function ψ ∈ Ψ(η) if and only if for each n ∈ ℕ^{+} there exists a function ψ_{n} ∈ Ψ^{n}(η) such that ψ_{n}(k) ≤ ψ(k) for all k ∈ [1, n]. Put

Ψ̃ = ⋃_{η=1}^{∞} Ψ(η).

The next theorem generalizes in depth some of the main results from [Gr1] and [Gr2].

Theorem. Let ψ ∈ Ψ̃, and let A_{1}, …, A_{k}, … be a countable sequence of almost σ-algebras such that for each k there exist ψ(k) pairwise disjoint sets not belonging to A_{k}. Then ⋃ A_{k} ≠ 𝔓(X).

2.7. Remark. It should be pointed out that, besides the Main Statement, the proofs of the result on σ-algebras given in Section 2.6 and Theorem 2.6 use the deep and nontrivial theorem of Gitik-Shelah from [G-S]. The authors’ proof of this theorem is metamathematical and uses the forcing method. Purely mathematical proofs have been proposed by Fremlin in [F1] and [F2], and by Kamburelis in [K]. In [Gr2] we give a purely mathematical proof of the Gitik-Shelah theorem following [K].

2.8. In [Gr1] and [Gr2], the following theorem was proved.

Theorem. Let A_{1}, …, A_{k}, … be a countable sequence of σ-algebras, and let for each k there exist two sets U_{1}^{k}, U_{2}^{k} ∉ A_{k}; U_{i}^{k} ∩ U_{j}^{l} = ∅ unless k = l, i = j. Then ⋃ A_{k} ≠ 𝔓(X).

2.9. Remark. As was mentioned in Section 1.3, if considered in Theorem 2.8 is a finite sequence of algebras, the condition of σ-additivity of algebras can be ignored.

2.10. The following theorem deals with a family of algebras having arbitrary cardinality. Its proof uses the idea of the proof of Theorem 2.8 (which, in turn, uses the Main Statement) as well as the idea of applying the Tychonoff theorem to proving a theorem on a system of distinct representatives (see [H-V]).

Theorem. Let {A_{λ}}_{λ∈Λ} be a family of σ-algebras, and {U_{1}^{λ}, U_{2}^{λ}}_{λ∈Λ} a family of sets such that

1) U_{i}^{λ} ∉ A_{λ},
2) U_{i_{1}}^{λ_{1}} ∩ U_{i_{2}}^{λ_{2}} = ∅ unless λ_{1} = λ_{2}, i_{1} = i_{2}.

Suppose, for each λ ∈ Λ there exists Λ′(λ) ⊂ Λ such that

a) λ ∉ Λ′(λ),
b) #(Λ \ Λ′(λ)) ≤ ℵ_{0},
c) A_{λ} ∋ ⋃_{λ′∈Λ′(λ)}(U_{1}^{λ′} ∪ U_{2}^{λ′}).

Then ⋃_{λ∈Λ} A_{λ} ≠ 𝔓(X).

2.11. Remark. Taking into account Remark 2.9, one can prove the following statement. Theorem 2.10 remains true if the algebras A_{λ} are not required to be σadditive and condition b) is replaced by a stronger condition

b^{∗}) #(Λ \ Λ′(λ)) < ℵ_{0}.

2.12. We do not know whether Theorem 2.8 is true if σ-algebras are replaced by almost σ-algebras. Yet the following theorem, the proof of which is based on the idea of the proof of Theorem 2.8, is true.

Theorem. Let A_{1}, …, A_{k}, … be a countable sequence of almost σ-algebras and let for each k there exist three sets U_{1}^{k}, U_{2}^{k}, U_{3}^{k} ∉ A_{k}; U_{i}^{k} ∩ U_{j}^{l} = ∅ unless k = l, i = j, and

#({l ∈ ℕ^{+}|U_{i}^{k} ∉ A_{l}}) < ℵ_{0}

for each U_{i}^{k}. Then ⋃ A_{k} ≠ 𝔓(X).

2.13. Before proceeding to the next theorem, it is necessary to mention a definition used in [Gr2].

Definition. Assume that ℕ^{∗} ⊂ ℕ^{+} and let n be an arbitrary natural number. The number

\overline{lim}_{n→∞} \frac{# (\{k ≤ n | k ∈ ℕ^{∗}\})}{n}

denoted p(ℕ^{∗}) is called the density of ℕ^{∗}. The number

\underline{lim}_{n→∞} \frac{# (\{k ≤ n | k ∈ ℕ^{∗}\})}{n}

denoted p_{a}(ℕ^{∗}) is called the absolute density of ℕ^{∗}.

2.14. The idea of the proof of Theorem 2.8 is used in the proof of the following interesting theorem.

Theorem. Let A_{1}, …, A_{k}, … be a countable sequence of almost σ-algebras and let for each k there exist two sets U_{1}^{k}, U_{2}^{k} ∉ A_{k}; U_{i}^{k} ∩ U_{j}^{l} = ∅ unless k = l, i = j, and

p({l ∈ ℕ^{+}|U_{i}^{k} ∉ A_{l}}) = 0

for each U_{i}^{k}. Then there will be ℕ^{∗} ⊂ ℕ^{+} such that p(ℕ^{∗}) = 1, p_{a}(ℕ^{∗}) ≥ \frac{2}{3}, and ⋃_{k∈ℕ^{∗}} A_{k} ≠ 𝔓(X).

2.15. Remark. Here, it is appropriate to give a quotation from [Gr2]. If in the assumptions of Theorem 2.8 one does not impose any restrictions on the algebras A_{k}, such as σ-additivity or almost σ-additivity, then, clearly, one can only assert the following: for any real number ρ < 1 there exists ℕ^{∗} ⊂ ℕ^{+} such that p_{a}(ℕ^{∗}) > ρ and ⋃_{k∈ℕ^{∗}} A_{k} ≠ 𝔓(X).

2.16. Let us proceed to another problem we tackled in [Gr2].

Definition. For each n ∈ ℕ^{+}, denote by 𝔳(n) the minimum natural number such that if A_{1}, …, A_{n} is a sequence of algebras, and for each k ∈ [1, n] there exist 𝔳(n) pairwise disjoint sets not belonging to A_{k}, then there exist pairwise disjoint sets U_{1}, …, U_{n}, V_{1}, …, V_{n} such that if Q ⊃ U_{k} and Q ∩ V_{k} = ∅, then Q ∉ A_{k}.

2.17. It is shown in [Gr2] that:

(1) 𝔳(n) = 4n − 3 for n ≤ 3.

(2) 𝔳(n) ≤ 4n − 5 for n > 3.

(3) 𝔳(n) ≤ 4n − ⌈\frac{n+3}{2}⌉.

(4) 3n − 2 ≤ 𝔳(n).

2.18. The proof of the following theorem is based on the considerations from [Gr2].

Theorem. 𝔳(n) ≤ ⌊\frac{10}{3}n + \frac{2}{\sqrt{3}} \sqrt{n}⌋.

References

[F1] D. H. Fremlin, The Gitik-Shelah theorem on real-valued measurable cardinals, Circulated notes, November 7, 1988.

[F2] D. H. Fremlin, Real-valued-measurable cardinals, Set Theory of the Reals (Ramat Gan, 1991), Israel Math. Conf. Proc., vol. 6, 1993, pp. 151–304. MR 95f:03084

[G-S] M. Gitik and S. Shelah, Forcing with ideals and simple forcing notions, Israel J. Math. 68

(1989), 129–160. MR 91g:03104

[Gr1] L. Š. Grinblat, On sets not belonging to algebras of subsets, Mem. Amer. Math. Soc. 480 (1992). MR 93d:04001 [Gr2] L. Š. Grinblat, Algebras of sets and combinatorics, Translations of Mathematical Mono-

graphs, vol. 214, Amer. Math. Soc., Providence, RI, 2002. MR 2003m:03073 [H-V] P. R. Halmos and H. E. Vaughan, The marriage problem, Amer. J. Math. 72 (1950), 214–

215. MR 11:423h

[K] A. Kamburelis, A new proof of the Gitik-Shelah theorem, Israel J. Math. 72 (1990), 373–380. MR 92h:03069

Department of Mathematics, The College of Judea and Samaria, P.O.Box 3, Ariel 44837, Israel

   E-mail address: grinblat@yosh.ac.il