The Cichon’s Diagram

The Cichon’s Diagram is a diagram that shows the relationships among ten small cardinals – four cardinals associated with the \sigma-ideal of sets of Lebesgue measure zero, four cardinals associated with the \sigma-ideal of sets of meager sets, the bounding number \mathfrak{b}, and the dominating number \mathfrak{d}. What makes this interesting is that elements of analysis, topology and set theory flow into the same spot. Here’s the diagram.

Figure 1 – The Cichon’s Diagram

In this diagram, \alpha \rightarrow \beta means \alpha \le \beta. The preceding three posts (the first post, the second post and the third post) give the necessary definitions and background to understand the diagram. In addition to the above diagram, the following relationships also hold.

Figure 2 – The Cichon’s Diagram – Additional Relationships

The Cardinal Characteristics of a \sigma -Ideal

For any \sigma-ideal \mathcal{I} on a set X, there are four associated cardinals – \text{add}(\mathcal{I}), \text{non}(\mathcal{I}), \text{cov}(\mathcal{I}) and \text{cof}(\mathcal{I}). The first one is the additivity number, which is the least number of elements of \mathcal{I} whose union is not an element of \mathcal{I}. The second cardinal is called the uniformity number, which is the least cardinality of a subset of X that is not an element of \mathcal{I}. The third cardinal is called the covering number, which is the least cardinality of a subfamily of \mathcal{I} that is also a covering of X. The fourth cardinal is called the cofinality number, which is the least cardinality of a subfamily of \mathcal{I} that is cofinal in \mathcal{I}. For more information, see the first post. The four cardinals are related in a way that is depicted in the following diagram. Again, \alpha \Rightarrow \beta means \alpha \le \beta.

Figure 3 – Cardinal Characteristics of a \sigma -Ideal

…Cichon…\displaystyle \begin{array}{ccccccccccccc} \text{ } & \text{ } & \text{ } &\text{ } & \bold n \bold o \bold n ( \mathcal{I} ) &\text{ } &\Longrightarrow &\text{ } &\bold c \bold o \bold f (\mathcal{I} )&\text{ } &\Longrightarrow & \text{ } & \lvert \mathcal{I} \lvert\\  \text{ } & \text{ } & \text{ } &\text{ } & \text{ } &\text{ } &\text{ } &\text{ } &\text{ }&\text{ } &\text{ }  & \text{ } & \text{ } \\     \text{ } & \text{ } & \text{ } &\text{ } & \Uparrow &\text{ } &\text{ } &\text{ } &\Uparrow&\text{ } &\text{ }  & \text{ }& \text{ } \\    \text{ }& \text{ }  & \text{ } &\text{ } & \text{ } &\text{ } &\text{ } &\text{ } &\text{ }&\text{ } &\text{ }  & \text{ }& \text{ } \\    \aleph_1 & \text{ } & \Longrightarrow & \text{ } &\bold a \bold d \bold d ( \mathcal{I} ) & \text{ } &\Longrightarrow & \text{ } &\bold c \bold o \bold v ( \mathcal{I} ) &\text{ } &\text{ } &\text{ }  & \text{ }    \end{array}

Figure 3 explains the basic orientation of the Cichon’s Diagram. Filling it with three \sigma-ideals produces the Cichon’s Diagram.

The Three \sigma -Ideals in the Cichon’s Diagram

Let \mathcal{K} be the \sigma-ideal of bounded subsets of \omega^\omega. It is known that \mathfrak{b}=\text{add}(\mathcal{K})=\text{non}(\mathcal{K}) (this is called the bounding number) and \mathfrak{d}=\text{cov}(\mathcal{K})=\text{cof}(\mathcal{K}) (this is called the dominating number). The ideal \mathcal{K} is discussed in this previous post. Let \mathcal{M} be the \sigma-ideal of meager subsets of the real line \mathbb{R} (this is discussed in this previous post). Let \mathcal{L} be the \sigma-ideal of Lebesgue measure zero subsets of the real line.

Thus the Cichon’s Diagram (Figure 1 above) houses information about three \sigma-ideals. The two numbers for the \sigma-ideal \mathcal{K} are situated in the middle of the diagram (\mathfrak{b} and \mathfrak{d}). The four numbers for the \sigma-ideal \mathcal{M} are situated in the center portion of the diagram. The four numbers for the \sigma-ideal \mathcal{L} are located on the left side and the right side. The Cichon’s Diagram (Figure 1) is flanked by \aleph_1 on the lower left and by continnum 2^{\aleph_0} on the upper right.

More on the Cichon’s Diagram

One interesting aspect of the Cichon’s Diagram: it is a small diagram with small cardinals where elements of analysis (measure) and topology (category) come together. The following diagram shows the path that includes both the bounding number and the dominating number.

Figure 4 – The Cichon’s Diagram – The Main Path

The path circled in the above diagram involves all three \sigma-ideals. It is also one of the longest increasing paths in the diagram.

    \aleph_1 \le \text{add}(\mathcal{L}) \le \text{add}(\mathcal{M}) \le \mathfrak{b} \le \mathfrak{d} \le \text{cof}(\mathcal{M}) \le \text{cof}(\mathcal{L}) \le 2^{\aleph_0}

There are fifteen arrows in Figure 1. The proofs of these arrows (or inequalities) require varying degrees of effort. Three are basic information – \aleph_1 \le \text{add}(\mathcal{L}), \mathfrak{b} \le \mathfrak{d} and \text{cof}(\mathcal{L}) \le 2^{\aleph_0}. Because \mathcal{L} is a \sigma-ideal, its additivity number must be uncountable. By definition, \mathfrak{b} \le \mathfrak{d}. The \sigma-ideal \mathcal{L} has a cofinal subfamily consisting of Borel sets. Thus \text{cof}(\mathcal{L}) \le 2^{\aleph_0}.

Four of the arrows follow from the relative magnitude of the four cardinals of a \sigma-ideal as shown in Figure 3 – \text{add}(\mathcal{L}) \le \text{cov}(\mathcal{L}), \text{non}(\mathcal{L}) \le \text{cof}(\mathcal{L}), \text{add}(\mathcal{M}) \le \text{cov}(\mathcal{M}) and \text{non}(\mathcal{M}) \le \text{cof}(\mathcal{M}).

Three of the arrows are proved in this previous post\mathfrak{b} \le \text{non}(\mathcal{M}), \mathfrak{d} \le \text{cov}(\mathcal{M}) and \text{add}(\mathcal{M}) \le \mathfrak{b}. The last inequality follows from this fact: if F \subset \omega^\omega is an unbounded set, then there exist \lvert F \lvert many meager subsets of the real line whose union is a non-meager set, essentially a result in Miller [8].

The proofs of the remaining five arrows can be found in [3] – \mathfrak{d} \le \text{cof}(\mathcal{M}), \text{add}(\mathcal{L}) \le \text{add}(\mathcal{M}), \text{cov}(\mathcal{L}) \le \text{non}(\mathcal{M}), \text{cof}(\mathcal{M}) \le \text{cof}(\mathcal{L}) and \text{cov}(\mathcal{M}) \le \text{non}(\mathcal{L}). The proofs of two additional relationships displayed in Figure 2 can also be found in [3].

The fifteen arrows in the Cichon’s Diagram represent the only inequalities among the ten cardinals (not counting \aleph_1 and 2^{\aleph_0}) that are provable in ZFC [1] and [5]. As illustration, we give an example of non-ZFC provable relation in the next section.

An Example of an Inequality Not Provable in ZFC

In the following diagram, the cardinals \mathfrak{b} and \text{cov}(\mathcal{M}) are encircled. These two numbers are not connected by arrows.

Figure 5 – The Cichon’s Diagram – An Example of Non-ZFC Provable

We sketch out a proof that no inequalities can be established between \mathfrak{b} and \text{cov}(\mathcal{M}). First Martin’s Axiom (MA) implies that \mathfrak{b} \le \text{cov}(\mathcal{M}). Topologically, the statement MA (\kappa) means that any compact Hausdorff space X that satisfies the countable chain condition cannot be the union of \kappa or fewer many nowhere dense sets. The Martin’s Axiom (MA) is the statement that MA (\kappa) holds for all \kappa less than 2^{\aleph_0}. It follows that MA implies that \text{cov}(\mathcal{M}) cannot be less than 2^{\aleph_0} and thus \text{cov}(\mathcal{M})=2^{\aleph_0}. It is always the case that the bounding number \mathfrak{b} is \le 2^{\aleph_0}.

On the other hand, in Laver’s model [6] for the Borel conjecture, \mathfrak{b} > \text{cov}(\mathcal{M}). In Laver’s model, every subset of the real line that is of strong measure zero is countable. Since any set with the Rothberger property is of strong measure zero, every subset of the real line that has the Rothberger property is countable in Laver’s model. Let \text{non}(\text{Rothberger}) be the least cardinality of a subset of the real line that does not have the Rothberger property. Thus in Laver’s model, \text{non}(\text{Rothberger})=\aleph_1. It is well known that \text{non}(\text{Rothberger})=\text{cov}(\mathcal{M}); see Theorem 5 in [10]. Thus in Laver’s model, \text{cov}(\mathcal{M})=\aleph_1.

In Laver’s model, \mathfrak{b} > \aleph_1. Note that \mathfrak{b}= \aleph_1 implies that there is an uncountable subset of the real line that is concentrated about \mathbb{Q}, the set of all rational numbers; see Theorem 10.2 in [12]. Any concentrated set is of strong measure zero; see Theorem 3.1 in [9]. Thus it must be the case that \mathfrak{b} > \aleph_1=\text{cov}(\mathcal{M}) in Laver’s model.

Remarks

The Cichon’s Diagram is a remarkable diagram. It blends elements of analysis and topology into a small diagram. The fifteen arrows shown in the diagram are obviously far from the end of the story. The Cichon’s Diagram had been around for a long time. Much had been written about it. The article [13] posted some questions about the diagram. See [1], [2], [4] and [11] for further information on the cardinals in the diagram.

Reference

  1. Bartoszynski, T., Judah H., Shelah S.,The Cichon Diagram, J. Symbolic Logic, 58(2), 401-423, 1993.
  2. Bartoszynski, T., Judah H., Shelah S.,Set theory: On the structure of the real line, A K
    Peters, Ltd.. Wellesley, MA, 1995.
  3. Blass, A., Combinatorial Cardinal Characteristics of the Continuum, Handbook of Set Theory (M. Foreman, A. Kanamori, eds), Springer Science+Business Media B. V., Netherlands, 395-489, 2010.
  4. Fremlin, D. H., Cichon’s diagram. In Seminaire d’Initiation ´a l’Analyse, 23, Universite Pierre et Marie Curie, Paris, 1984.
  5. Garcia, H., da Silva S. G., Identifying Small with Bounded: Unboundedness, Domination, Ideals and Their Cardinal Invariants, South American Journal of Logic, 2 (2), 425-436, 2016.
  6. Laver, R., On the consistency of Borel’s conjecture, Acta Math., 137, 151-169, 1976.
  7. Miller, A. W., Some Properties of Measure and Category, Trans. Amer. Math. Soc., 266 (1), 93-114, 1981.
  8. Miller, A. W., A Characterization of the Least Cardinal for Which the Baire Category Theorem Fails, Proc. Amer. Math. Soc., 86 (3), 498-502, 1982.
  9. Miller, A. W., Special Subsets of the Real Line, Handbook of Set-Theoretic Topology (K. Kunen and J. E. Vaughan, eds), Elsevier Science Publishers B. V., Amsterdam, 201-233, 1984.
  10. Miller A. W., Fremlin D. H., On some properties of Hurewicz, Menger, and Rothberger, Fund. Math., 129, 17-33, 1988.
  11. Pawlikowski, J., Reclaw I., Parametrized Cichon’s diagram and small sets, Fund. Math., 127, 225-239, 1987.
  12. Van Douwen, E. K., The Integers and Topology, Handbook of Set-Theoretic Topology (K. Kunen and J. E. Vaughan, eds), Elsevier Science Publishers B. V., Amsterdam, 111-167, 1984.
  13. Vaughn, J. E., Small uncountable cardinals and topology, Open Problems in Topology (J. van Mill and G.M. Reed, eds), Elsevier Science Publishers B.V. (North-Holland), 1990.

\text{ }

\text{ }

\text{ }

Dan Ma topology

Daniel Ma topology

Dan Ma math

Daniel Ma mathematics

\copyright 2020 – Dan Ma

The ideal of bounded sets

This is the second in a series of posts leading to a diagram called The Cichon’s Diagram. In this post, we examine an ideal that will provide insight on the ideal of meager sets, which is part of the Cichon’s Diagram. For the definitions of ideal and \sigma-ideal, see the first post.

The next two posts are: the third post and the fourth post – the Cichon’s Diagram.

Let \omega be the set of all non-negative integers, i.e. \omega=\{ 0,1,2,\cdots \}. Let X=\omega^\omega, the set of all functions from \omega into \omega. We can also think of X as a topological space since it is a product space of countably many copies of the discrete space \omega. As a product space, X=\omega^\omega is homeomorphic to \mathbb{P}, the space of all irrational numbers with the usual real line topology (see here).

Recall that for f,g \in \omega^\omega, f \le^* g means that f(n) \le g(n) for all but finitely many n. This is a partial order that is called the eventual domination order. A subset F of \omega^\omega is a bounded set if there is a g \in \omega^\omega such that g is an upper bound of F with respect to the partial order \le^*, i.e. for each f \in F, we have f \le^* g. The set F is an unbounded set of it is not bounded. The set F is a dominating set if for each g \in \omega^\omega, there exists f \in F such that g \le^* f, i.e. the set F is cofinal in \omega^\omega with respect to the eventual domination order \le^*.

We are interested in the least cardinality of an unbounded set and the least cardinality of a dominating set. The former is denoted by \mathfrak{b} and is called the bounding number while the latter is denoted by \mathfrak{d} and is called the dominating number.

An Interim Ideal

We define two ideals on X=\omega^\omega. Let \mathcal{S} be the collection of all \sigma-compact subsets of \omega^\omega.

    \mathcal{K}_\sigma=\{ A \subset \omega^\omega: \exists \ B \in \mathcal{S} \text{ such that } A \subset B \}

    \mathcal{K}_b=\{ A \subset \omega^\omega: A \text{ is a bounded set} \}

The first one \mathcal{K}_\sigma is the set of all subsets of \omega^\omega, each of which is contained in a \sigma-compact set. The second one \mathcal{K}_b is simply the set of all bounded subsets. It is straightforward to verify that \mathcal{K}_\sigma is a \sigma-ideal on \omega^\omega. Note that any countable set \{ f_0, f_1,f_2,\cdots \} \subset \omega^\omega is a bounded set (via a diagonal argument). Thus the union of countably many bounded sets A_0,A_1,A_2,\cdots with A_n having an upper bound f_n must be a bounded set. The f_n have an upper bound f, which is an upper bound of the union of the sets A_n. Thus \mathcal{K}_b is a \sigma-ideal on \omega^\omega.

Furthermore, since \omega^\omega is not \sigma-compact, \mathcal{K}_\sigma is a proper ideal. Likewise \omega^\omega is an unbounded set, \mathcal{K}_b is a proper ideal. The ideal \mathcal{K}_\sigma is called the \sigma-ideal generated by \sigma-compact subsets of \omega^\omega. The ideal \mathcal{K}_b is the \sigma-ideal of bounded subset of \omega^\omega. However, these two ideals are one and the same.

Theorem 1
Let F \subset \omega^\omega. Then the following conditions are equivalent.

  1. The set F is bounded.
  2. There exists a \sigma-compact set X such that F \subset X \subset \omega^\omega.
  3. With F as a subset of the real line, the set F is an F_\sigma-subset of F \cup \mathbb{Q} where \mathbb{Q} is the set of all rational numbers.

Theorem 1 is the Theorem 1 found in
. The sets satisfying Condition 1 of this theorem are precisely the elements of the \sigma-ideal \mathcal{K}_b. The sets satisfying Condition 2 of this theorem are precisely the elements of the \sigma-ideal \mathcal{K}_\sigma. According to this theorem, the two \sigma-ideals are the same. Each is a different characterization of the same \sigma-ideal. As a result, we drop the subscript and call this \sigma-ideal \mathcal{K}.

Four Cardinals

With the \sigma-ideal \mathcal{K} from the preceding section, we would like to examine the four associated cardinals \text{add}(\mathcal{K}) (the additivity number), \text{non}(\mathcal{K}) (the uniformity number), \text{cov}(\mathcal{K}) (the covering number) and \text{cof}(\mathcal{K}) (the cofinality number). For the definitions of these numbers, see the first post.

Figure 1 – Cardinal Characteristics of the \sigma -Ideal Generated by \sigma -Compact Sets

…Cichon…\displaystyle \begin{array}{ccccccccccccc} \text{ } & \text{ } & \text{ } &\text{ } & \bold n \bold o \bold n ( \mathcal{K} ) &\text{ } &\Longrightarrow &\text{ } &\bold c \bold o \bold f (\mathcal{K} )&\text{ } &\Longrightarrow & \text{ } & 2^{\aleph_0}\\  \text{ } & \text{ } & \text{ } &\text{ } & \text{ } &\text{ } &\text{ } &\text{ } &\text{ }&\text{ } &\text{ }  & \text{ } & \text{ } \\     \text{ } & \text{ } & \text{ } &\text{ } & \Uparrow &\text{ } &\text{ } &\text{ } &\Uparrow&\text{ } &\text{ }  & \text{ }& \text{ } \\    \text{ }& \text{ }  & \text{ } &\text{ } & \text{ } &\text{ } &\text{ } &\text{ } &\text{ }&\text{ } &\text{ }  & \text{ }& \text{ } \\    \aleph_1 & \text{ } & \Longrightarrow & \text{ } &\bold a \bold d \bold d ( \mathcal{K} ) & \text{ } &\Longrightarrow & \text{ } &\bold c \bold o \bold v ( \mathcal{K} ) &\text{ } &\text{ } &\text{ }  & \text{ }    \end{array}

In the diagram, \alpha \Rightarrow \beta means that \alpha \le \beta. The additivity number \text{add}(\mathcal{K}) is lowered bounded by \aleph_1 on the lower right in the diagram since the ideal \mathcal{K} is a \sigma-ideal. The middle of the diagram shows the relationships that hold for any \sigma-ideal. To see that \text{cof}(\mathcal{K}) \le 2^{\aleph_0}, define B_f=\{ h \in \omega^\omega: h \le^* f \} for each f \in \omega^\omega. The set of all B_f is cofinal in \mathcal{K}. The inequality holds since there are 2^{\aleph_0} many sets B_f.

We can further refine Figure 1. The following theorem shows how.

Theorem 2
The values of the four cardinals associated with the \sigma-ideal \mathcal{K} are the bounding numbers \mathfrak{b} and the dominating number \mathfrak{d}. Specifically, we have the following equalities.

    \mathfrak{b}=\text{add}(\mathcal{K})=\text{non}(\mathcal{K})
    \mathfrak{d}=\text{cov}(\mathcal{K})=\text{cof}(\mathcal{K})

Proof of Theorem 2
Based on the discussion in the first post, \text{add}(\mathcal{K}) \le \text{non}(\mathcal{K}) and \text{cov}(\mathcal{K}) \le \text{cof}(\mathcal{K}) always hold. We establish the equalities by showing the following.

    \mathfrak{b} \le \text{add}(\mathcal{K}) \le \text{non}(\mathcal{K}) = \mathfrak{b}
    \mathfrak{d} \le \text{cov}(\mathcal{K}) \le \text{cof}(\mathcal{K}) \le \mathfrak{d}

Viewing \mathcal{K} as a \sigma-ideal of bounded sets, \text{non}(\mathcal{K}) is the least cardinality of an unbounded set. Thus \mathfrak{b}=\text{non}(\mathcal{K}).

To see \mathfrak{b} \le \text{add}(\mathcal{K}), let \mathcal{A} \subset \mathcal{K} such that \lvert \mathcal{A} \lvert=\text{add}(\mathcal{K}) and Y=\bigcup \mathcal{A} \notin \mathcal{K}. Note that each A \in \mathcal{A} is a bounded set with an upper bound f(A) \in \omega^\omega. We claim that F=\{ f(A): A \in \mathcal{A} \} is unbounded. This is because Y=\bigcup \mathcal{A} is unbounded. Since there exists an unbounded set F with cardinality \text{add}(\mathcal{K}), it follows that \mathfrak{b} \le \text{add}(\mathcal{K}).

To see \text{cof}(\mathcal{K}) \le \mathfrak{d}, let F \subset \omega^\omega be a dominating set such that \lvert F \lvert=\mathfrak{d}. Note that for each f \in \omega^\omega, the set B_f=\{ h \in \omega^\omega: h \le^* f \} is a bounded set and thus B_f \in \mathcal{K}. It can be verified that \mathcal{B}=\{ B_f: f \in F \} is cofinal in \mathcal{K}. Since there is a cofinal set \mathcal{B} with cardinality \mathfrak{d}, it follows that \text{cof}(\mathcal{K}) \le \mathfrak{d}.

To see \mathfrak{d} \le \text{cov}(\mathcal{K}), let \mathcal{W} \subset \mathcal{K} such that \lvert \mathcal{W} \lvert=\text{cov}(\mathcal{K}) and \bigcup \mathcal{W}=\omega^\omega. For each A \in \mathcal{W}, let f(A) be an upper bound of A. It can be verified that the set F=\{ f(A): A \in \mathcal{W} \} is a dominating set. Since we have a dominating set F with cardinality \text{cov}(\mathcal{K}), we have \mathfrak{d} \le \text{cov}(\mathcal{K}). This completes the proof of Theorem 2. \square

With additional information from Theorem 2, Figure 1 can be revised as follows:

Figure 2 – Revised Figure 1

…Cichon…\displaystyle \begin{array}{ccccccccccccc} \text{ } & \text{ } & \text{ } &\text{ } & \mathfrak{b}=\bold n \bold o \bold n ( \mathcal{K} ) &\text{ } &\Longrightarrow &\text{ } &\mathfrak{d}=\bold c \bold o \bold f (\mathcal{K} )&\text{ } &\Longrightarrow & \text{ } & 2^{\aleph_0}\\  \text{ } & \text{ } & \text{ } &\text{ } & \text{ } &\text{ } &\text{ } &\text{ } &\text{ }&\text{ } &\text{ }  & \text{ } & \text{ } \\     \text{ } & \text{ } & \text{ } &\text{ } & \parallel &\text{ } &\text{ } &\text{ } &\parallel&\text{ } &\text{ }  & \text{ }& \text{ } \\    \text{ }& \text{ }  & \text{ } &\text{ } & \text{ } &\text{ } &\text{ } &\text{ } &\text{ }&\text{ } &\text{ }  & \text{ }& \text{ } \\    \aleph_1 & \text{ } & \Longrightarrow & \text{ } &\mathfrak{b}=\bold a \bold d \bold d ( \mathcal{K} ) & \text{ } &\Longrightarrow & \text{ } &\mathfrak{d}=\bold c \bold o \bold v ( \mathcal{K} ) &\text{ } &\text{ } &\text{ }  & \text{ }    \end{array}

Note that there are only four cardinals in this diagram – \aleph_1, \mathfrak{b}, \mathfrak{d} and 2^{\aleph_0}. Of course, if continuum hypothesis holds, there would only one number in the diagram, namely \aleph_1.

The next post is on the \sigma-ideal \mathcal{M} of meager sets.

\text{ }

\text{ }

\text{ }

Dan Ma topology

Daniel Ma topology

Dan Ma math

Daniel Ma mathematics

\copyright 2020 – Dan Ma

Adding up to a non-meager set

The preceding post gives a topological characterization of bounded subsets of \omega^\omega. From it, we know what it means topologically for a set to be unbounded. In this post we prove a theorem that ties unbounded sets to Baire category.

A set is nowhere dense if its closure has empty interior. A set is a meager set if it is the union of countably many nowhere dense sets. By definition, the union of countably many meager sets is always a meager set. In order for meager sets to add up to a non-meager set (though taking union), the number of meager sets must be uncountable. What is this uncountable cardinal number? We give an indication of how big this number is. In this post we give a constructive proof to the following fact:

Theorem 1 …. Given an unbounded set F \subset \omega^\omega, there exist \kappa=\lvert F \lvert many meager subsets of the real line whose union is not meager.

We will discuss the implications of this theorem after giving background information.

We use \omega to denote the set of all non-negative integers \{ 0,1,2,\cdots \}. The set \omega^\omega is the set of all functions from \omega into \omega. It is called the Baire space when it is topologized with the product space topology. It is well known that the Baire space is homeomorphic to the space of irrational numbers \mathbb{P} (see here).

The notion of boundedness or unboundedness used in Theorem 1 refers to the eventual domination order (\le^*) for functions in the product space. For f,g \in \omega^\omega, by f \le^* g, we mean f(n) \le g(n) for all but finitely many n. A set F \subset \omega^\omega is bounded if it has an upper bound with respect to the partial order \le^*, i.e. there is some f \in \omega^\omega such that g \le^* f for all g \in F. The set F is unbounded if it is not bounded. To spell it out, F is unbounded if for each f \in \omega^\omega, there exists g \in F such that g \not \le^* f, i.e. f(n)<g(n) for infinitely many n.

All countable subsets of the Baire space are bounded (using a diagonal argument). Thus unbounded sets must be uncountable. It does not take extra set theory to obtain an unbounded set. The Baire space \omega^\omega is unbounded. More interesting unbounded sets are those of a certain cardinality, say unbounded sets of cardinality \omega_1 or unbounded sets with cardinality less than continuum. Another interesting unbounded set is one that is of the least cardinality. In the literature, the least cardinality of an unbounded subset of \omega^\omega is called \mathfrak{b}, the bounding number.

Another notion that is part of Theorem 1 is the topological notion of small sets – meager sets. This is a topological notion and is defined in topological spaces. For the purpose at hand, we consider this notion in the context of the real line. As mentioned at the beginning of the post, a set is nowhere dense set if its closure has empty interior (i.e. the closure contains no open subset). Let A \subset \mathbb{R}. The set A is nowhere dense if no open set is a subset of the closure \overline{A}. An equivalent definition: the set A is nowhere dense if for every nonempty open subset U of the real line, there is a nonempty subset V of U such that V contains no points of A. Such a set is “thin” since it is dense no where. In any open set, we can also find an open subset that has no points of the nowhere dense set in question. A subset A of the real line is a meager set if it is the union of countably many nowhere dense sets. Another name of meager set is a set of first category. Any set that is not of first category is called a set of second category, or simply a non-meager set.

Corollaries

Subsets of the real line are either of first category (small sets) or of second category (large sets). Countably many meager sets cannot fill up the real line. This is a consequence of the Baire category theorem (see here). By definition, caountably many meager sets cannot fill up any non-meager subset of the real line. How many meager sets does it take to add up to a non-meager set?

Theorem 1 gives an answer to the above question. It can take as many meager sets as the size of an unbounded subset of the Baire space. If \kappa is a cardinal number for which there exists an unbounded subset of \omega^\omega whose cardinality is \kappa, then there exists a non-meager subset of the real line that is the union of \kappa many meager sets. The bounding number \mathfrak{b} is the least cardinality of an unbounded set. Thus there is always a non-meager subset of the real line that is the union of \mathfrak{b} many meager sets.

Let \kappa_A be the least cardinal number \kappa such that there exist \kappa many meager subsets of the real line whose union is not meager. Based on Theorem 1, the bounding number \mathfrak{b} is an upper bound of \kappa_A. These two corollaries just discussed are:

  • There always exists a non-meager subset of the real line that is the union of \mathfrak{b} many meager sets.
  • \kappa_A \le \mathfrak{b}.

The bounding number \mathfrak{b} points to a non-meager set that is the union of \mathfrak{b} many meager sets. However, the cardinal \kappa_A is the least number of meager sets whose union is a non-meager set and this number is no more than the bounding number. The cardinal \kappa_A is called the additivity number.

There are other corollaries to Theorem 1. Let A(c) be the statement that the union of fewer than continuum many meager subsets of the real line is a meager set. For any cardinal number \kappa, let A(\kappa) be the statement that the union of fewer than \kappa many meager subsets of the real line is a meager set. We have the following corollaries.

  • The statement A(c) implies that there are no unbounded subsets of \omega^\omega that have cardinalities less than continuum. In other words, A(c) implies that the bounding number \mathfrak{b} is continuum.
  • Let \kappa \le continuum. The statement A(\kappa) implies that there are no unbounded subsets of \omega^\omega that have cardinalities less than \kappa. In other words, A(\kappa) implies that the bounding number \mathfrak{b} is at least \kappa, i.e. \mathfrak{b} \ge \kappa.

Let B(c) be the statement that the real line is not the union of less than continuum many meager sets. Clearly, the statement A(c) implies the statement B(c). Thus, it follows from Theorem 1 that A(c) \Longrightarrow B(c) + \mathfrak{b}=2^{\aleph_0}. This is a result proven in Miller [1]. Theorem 1.2 in [1] essentially states that A(c) is equivalent to B(c) + \mathfrak{b}=2^{\aleph_0}. The proof of Theorem 1 given here is essentially the proof of one direction of Theorem 1.2 in [1]. Our proof has various omitted details added. As a result it should be easier to follow. We also realize that the proof of Theorem 1.2 in [1] proves more than that theorem. Therefore we put the main part of the constructive in a separate theorem. For example, Theorem 1 also proves that the additivity number \kappa_A is no more than \mathfrak{b}. This is one implication in the Cichon’s diagram.

Proof of Theorem 1

Let 2=\{ 0,1 \}. The set 2^\omega is the set of all functions from \omega into \{0, 1 \}. When 2^\omega is endowed with the product space topology, it is called the Cantor space and is homemorphic to the middle-third Cantor set in the unit interval [0,1]. We use \{ [s]: \exists \ n \in \omega \text{ such that } s \in 2^n \} as a base for the product topology where [s]=\{ t \in 2^\omega:  s \subset t \}.

Let F \subset \omega^\omega be an unbounded set. We assume that the unbounded set F satisfies two properties.

  • Each g \in F is an increasing function, i.e. g(i)<g(j) for any i<j.
  • For each g \in F, if j>g(n), then g(j)>g(n+1).

One may wonder if the two properties are satisfied by any given unbounded set. Since F is unbounded, we can increase the values of each function g \in F, the resulting set will still be an unbounded set. More specifically, for each g \in F, define g^*\in \omega^\omega as follows:

  • g^*(0)=g(0)+1,
  • for each n \ge 1, g^*(n)=g(n)+\text{max}\{ g^*(i): i<n \} + n+1.

The set F^*=\{ g^*: g \in F \} is also an unbounded set. Therefore we use F^* and rename it as F.

Fix g \in F. Define an increasing sequence of non-negative integers n_0,n_1,n_2,\cdots as follows. Let n_0 be any integer greater than 1. For each integer j \ge 1, let n_j=g(n_{j-1}). Since n_0>1, we have n_1=g(n_0)>g(1). It follows that for all integer k \ge 1, n_k>g(k).

For each g \in F, we have an associated sequence n_0,n_1,n_2,\cdots as described in the preceding paragraph. Now define C(g)=\{ q \in 2^\omega: \forall \ k, q(n_k)=1 \}. It is straightforward to verify that each C(g) is a closed and nowhere dense subset of the Cantor space 2^\omega. Let X=\bigcup \{C(g): g \in F \}. The set X is a union of meager sets. We show that it is a non-meager subset of 2^\omega. We prove the following claim.

Claim 1
For any countable family \{C_n: n \in \omega \} where each C_n is a nowhere dense subset of 2^\omega, we have X \not \subset \bigcup \{C_n: n \in \omega \}.

According to Claim 1, the set X cannot be contained in any arbitrary meager subset of 2^\omega. Thus X must be non-meager. To establish the claim, we define an increasing sequence of non-negative integers m_0,m_1,m_2,\cdots with the property that for any k \ge 1, for any i<k, and for any s \in 2^{m_k}, there exists t \in 2^{m_{k+1}} such that s \subset t and [t] \cap C_i=\varnothing.

The desired sequence is derived from the fact that the sets C_n are nowhere dense. Choose any m_0<m_1 to start. With m_1 determined, the only nowhere dense set to consider is C_0. For each s \in 2^{m_1}, choose some integer y>m_1 such that there exists t \in 2^{y+1} such that s \subset t and [t] \cap C_0=\varnothing. Let m_2 be an integer greater than all the possible y‘s that have been chosen. The integer m_2 can be chosen since there are only finitely many s \in 2^{m_1}.

Suppose m_0<\cdots<m_{k-1}<m_k have been chosen. Then the only nowhere dense sets to consider are C_0,\cdots,C_{k-1}. Then for each i \le k-1, for each s \in 2^{m_k}, choose some integer y>m_k such that there exists t \in 2^{y+1} such that s \subset t and [t] \cap C_i=\varnothing. As before let m_{k+1} be an integer greater than all the possible y‘s that have been chosen. Again m_{k+1} is possible since there are only finitely many i \le k-1 and only finitely many s \in 2^{m_k}.

Let Z=\{ m_k: k \in \omega \}. We make the following claim.

Claim 2
There exists h \in F such that the associated sequence n_0, n_1,n_2,\cdots satisfies the condition: \lvert [n_k,n_{k+1}) \cap Z \lvert \ge 2 for infinitely many k where [n_k,n_{k+1}) is the set \{ m \in \omega: n_k \le m < m_{k+1} \}.

Suppose Claim 2 is not true. For each g \in F and its associated sequence n_0, n_1,n_2,\cdots,

    (*) there exists some integer b such that for all k>b, \lvert [n_k,n_{k+1}) \cap Z \lvert \le 1.

Let f \in \omega^\omega be defined by f(k)=m_k for all k. Choose \overline{f} \in \omega^\omega in the following manner. For each k \in \omega, define d_k \in \omega^\omega by d_k(n)=f(n+k) for all n. Then choose \overline{f} \in \omega^\omega such that d_k \le^* \overline{f} for all k.

Fix g \in F. Let m_j be the least element of [n_b, \infty) \cap Z. Then for each k>b, we have g(k) \le n_k \le m_{j+k}=f(j+k)=d_j(k). Note that the inequality n_k \le m_{j+k} holds because of the assumption (*). It follows that g \le^* d_j \le^* \overline{f}. This says that \overline{f} is an upper bound of F contradicting that F is an unbounded set. Thus Claim 2 must be true.

Let h \in F be as described in Claim 2. We now prove another claim.

Claim 3
For each n, C_n is a nowhere dense subset of C(h).

Fix C_n. Let p be an integer such that [n_p,n_{p+1}) \cap Z has at least two points, say m_k and m_{k+1}. We can choose p large enough such that n<k. Choose s \in 2^{m_k}. Since n_p is arbitrary, [s] is an arbitrary open set in 2^\omega. Since m_k is in between n_p and n_{p+1}, [s] contains a point of C(h). Thus [s] \cap C(h) is an arbitrary open set in C(h). By the way m_k and m_{k+1} are chosen originally, there exists t \in 2^{m_{k+1}} such that s \subset t and [t] \cap C_n=\varnothing. Because m_k and m_{k+1} are in between n_p and n_{p+1}, [t] \cap C(h) \ne \varnothing. This establishes the claim that C_n is nowhere dense subset of C(h).

Note that C(h) is a closed subset of the Cantor space 2^\omega and hence is also compact. Thus C(h) is a Baire space and cannot be the union of countably many nowhere dense sets. Thus C(h) \not \subset \cup \{C_n: n \in \omega \}. Otherwise, C(h) would be the union of countably many nowhere dense sets. This means that X=\bigcup \{C(g): g \in F \} \not \subset \cup \{C_n: n \in \omega \}. This establishes Claim 1.

Considering the Cantor space 2^\omega as a subspace of the real line, each C(g) is also a closed nowhere dense subset of the real line. The set X=\bigcup \{C(g): g \in F \} is also not a meager subset of the real line. This establishes Theorem 1. \square

Reference

  1. Miller A. W., Some properties of measure and category, Trans. Amer. Math. Soc., 266, 93-114, 1981.

\text{ }

\text{ }

\text{ }

Dan Ma topology

Daniel Ma topology

Dan Ma math

Daniel Ma mathematics

\copyright 2020 – Dan Ma