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 meager sets

This is the third in a series of four posts leading to a diagram called The Cichon’s Diagram. This post focuses on the \sigma-ideal of meager subsets of the real line. The links to the previous posts: the first post and the second post.

The next post is: the Cichon’s Diagram.

The notion of meager sets can be defined on any topological space. Let Y be a space. A subset A of Y is a nowhere dense set if \overline{A}, the closure of A in the space Y, contains no open sets. Equivalently, A is a nowhere dense set if for each non-empty open subset U of Y, there exists a non-empty open subset V of U such that V \cap A=\varnothing. We can always find a part of any open set that misses a nowhere dense set. Thus nowhere dense sets are considered “thin” sets. A subset of Y is said to be a meager set if it is the union of countably many nowhere dense sets. A meager set is also called a set of first category. A non-meager set is then called a set of second category.

Though the notion of meager sets can be considered in any space, we would like to focus on the real line \mathbb{R} or the space of all irrational numbers \mathbb{P}. Note that \mathbb{P} is homeomorphic to \omega^\omega (see here). Instead of working with \mathbb{P}, we work with \omega^\omega, which is the product space of countably many copies of the countable discrete space \omega.

\sigma -Ideal of Meager Sets

The notion of meager sets is a topological notion of small sets. The real line and the space of irrationals \omega^\omega are “big” sets. This means that they are not the union of countably many meager sets (this fact is a consequence of the Baire category theorem). Let \mathcal{M} be the set of all subsets of the real line that are meager sets. It is straightforward to verify that \mathcal{M} is a \sigma-ideal on the real line \mathbb{R}. Because of the Baire category theorem, \mathcal{M} is a proper ideal, i.e. \mathbb{R} \notin \mathcal{M}. Naturally, we would like to consider the four cardinals associated with this ideal – \text{add}(\mathcal{M}) (the additivity number), \text{cov}(\mathcal{M}) (the covering number), \text{non}(\mathcal{M}) (the uniformity number) and \text{cof} (\mathcal{M}) (the cofinality number). These four numbers are displayed in the following diagram.

Figure 1 – Cardinal Characteristics of the \sigma -Ideal of Meager Sets

…Cichon…\displaystyle \begin{array}{ccccccccccccc} \text{ } & \text{ } & \text{ } &\text{ } & \bold n \bold o \bold n ( \mathcal{M} ) &\text{ } &\Longrightarrow &\text{ } &\bold c \bold o \bold f (\mathcal{M} )&\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{M} ) & \text{ } &\Longrightarrow & \text{ } &\bold c \bold o \bold v ( \mathcal{M} ) &\text{ } &\text{ } &\text{ }  & \text{ }    \end{array}

In the above diagram, an arrow means \le. So \alpha \Rightarrow \beta means \alpha \le \beta. The inequalities displayed in this diagram always hold for any \sigma-ideal. The only inequality that requires explanation is \text{cof} (\mathcal{M}) \le 2^{\aleph_0}. Any meager set is a subset of an F_\sigma-set. To see this, let A=\bigcup_{n \in \omega} X_n where each X_n is a nowhere dense subset of the real line. Then A \subset \bigcup_{n \in \omega} \overline{X_n}. Each \overline{X_n} is also nowhere dense. Thus the set of all F_\sigma nowhere dense sets is cofinal in \mathcal{M}. This cofinal set has cardinality continuum. Of course, if continuum hypothesis holds (\aleph_1=2^{\aleph_0}), then all four cardinals are identical and are \aleph_1.

\sigma -Ideal of Bounded Sets

In some respects, it is more advantageous to consider the \sigma-ideal of meager subsets of \mathbb{P}, the set of all irrational numbers, or equivalently \omega^\omega. Thus we consider the \sigma-ideal of meager subsets of \omega^\omega. We also use \mathcal{M} denote this \sigma-ideal. Note that the calculation of the four cardinals \text{add}(\mathcal{M}), \text{cov}(\mathcal{M}), \text{non}(\mathcal{M}) and \text{cof} (\mathcal{M}) yields the same values regardless of whether \mathcal{M} is the \sigma-ideal of meager subsets of the real line or of \omega^\omega. In the remainder of this post, \mathcal{M} is the \sigma-ideal of meager subsets of \omega^\omega, the space of the irrational numbers.

Let \mathcal{S} be the collection of all \sigma-compact subsets of \omega^\omega. In this previous post, the following \sigma-ideal is discussed.

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

It is straightforward to verify that \mathcal{K} is indeed a \sigma-ideal on \omega^\omega. This is what we know about this \sigma-ideal from this previous post.

  • A \in \mathcal{K} if and only if A is a bounded subset of \omega^\omega.
  • \mathfrak{b}=\text{add}(\mathcal{K})=\text{non}(\mathcal{K}).
  • \mathfrak{d}=\text{cov}(\mathcal{K})=\text{cof}(\mathcal{K}).

So the sets in \mathcal{K} are simply the bounded sets. For this \sigma-ideal, the additivity number and the uniformity numbers are \mathfrak{b}, the bounding number. The covering number and the cofinality number are the dominating number \mathfrak{d}. As we will see below, these facts provide insight on the \sigma-ideal \mathcal{M}.

The following lemma connects the \sigma-ideal \mathcal{K} with the \sigma-ideal \mathcal{M}.

Lemma 1
Let A be a compact subset of \omega^\omega. Then A is a closed and nowhere dense subset of \omega^\omega. Hence any \sigma-compact subset of \omega^\omega is a meager subset of \omega^\omega.

Proof of Lemma 1
Since A is compact, for each n, the projection of A into the nth factor of \omega^\omega is compact and thus finite. Let [0, g(n)]=\{ j \in \omega: 0 \le j \le g(n) \} be a finite set that contains the nth projection of A. Thus A \subset \prod_{n \in \omega} [0, g(n)]. It is straightforward to verify that \prod_{n \in \omega} [0, g(n)] is nowhere dense in \omega^\omega. Thus A is a closed nowhere dense subset of \omega^\omega. It follows that any \sigma-compact subset of \omega^\omega is a meager subset of \omega^\omega. \square

Theorem 2
As a result of Lemma 1, we have \mathcal{K} \subset \mathcal{M}. However, \mathcal{M} \not \subset \mathcal{K}. Thus the two \sigma-ideals are not the same.

Any example that proves Theorem 2 would be an unbounded meager set. One such example is constructed in this previous post.

More on \sigma -Ideal of Meager Sets

For \mathcal{K}, the \sigma-ideal generated by \sigma-compact subsets of \omega^\omega, and for \mathcal{M}, the \sigma-ideal of meager sets in \omega^\omega, we are interested in the four associated cardinals add, non, cov and cof in each \sigma-ideal. For \mathcal{K}, the four cardinals are just two, \mathfrak{b} and \mathfrak{d}. We would like to relate these six cardinals, plus \aleph_1 and 2^{\aleph_0}. They are represented in the following diagram.

Figure 5 – Partial Cichon’s Diagram

…Cichon…\displaystyle \begin{array}{ccccccccccccc} \text{ } & \text{ } & \text{ } &\text{ } & \bold n \bold o \bold n ( \mathcal{M} ) &\text{ } &\Longrightarrow &\text{ } &\bold c \bold o \bold f (\mathcal{M} )&\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{ } \\     \text{ } & \text{ } & \text{ } &\text{ } & \mathfrak{b} &\text{ } &\Longrightarrow &\text{ } &\mathfrak{d}&\text{ } &\text{ }  & \text{ }& \text{ } \\    \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{M} ) & \text{ } &\Longrightarrow & \text{ } &\bold c \bold o \bold v ( \mathcal{M} ) &\text{ } &\text{ } &\text{ }  & \text{ }    \end{array}

As in the other diagrams, arrows mean \le. So \alpha \Longrightarrow \beta means \alpha \le \beta. Furthermore, we have two additional relations.

Additional Relationships

…Cichon…\text{add}(\mathcal{M})=\text{min}(\mathfrak{b},\ \text{cov}(\mathcal{M}))
…Cichon…\text{cof}(\mathcal{M})=\text{max}(\mathfrak{d},\ \text{non}(\mathcal{M}))

As shown, Figure 5 is not complete. It only has information on the \sigma-ideal \mathcal{M} on meager sets. The usual Cichon’s diagram would also include the four associated cardinals for \mathcal{L}, the \sigma-ideal of Lebesgue measure zero sets. In this post we focus on \mathcal{M}. The full Cichon’s diagram will be covered in a subsequent post. insert

In Figure 5, the cardinals go from smaller to the larger from left to right and bottom to top. It starts with \aleph_1 on the lower left and moves toward the continuum on the upper right. Because of Theorem 3, the cardinals associated with the \sigma-ideal \mathcal{K} are represented by \mathfrak{b} and \mathfrak{d} in the diagram. We next examine the inequalities between the cardinals associated with \mathcal{M} and \mathfrak{b} and \mathfrak{d}.

There are four inequalities to account for. First, \mathfrak{b} \le \text{non}(\mathcal{M}) and \text{cov}(\mathcal{M}) \le \mathfrak{d}. The first inequality follows from the fact that \mathfrak{b} = \text{non}(\mathcal{K}) and that \mathcal{K} \subset \mathcal{M}. The second inequality follows from the fact that \mathfrak{d} = \text{cov}(\mathcal{K}) and that \mathcal{K} \subset \mathcal{M}.

The inequality \text{add}(\mathcal{K}) \le \mathfrak{b} follows from the fact that if F \subset \omega^\omega is an unbounded set, then there exist \lvert F \lvert many meager sets whose union is a non-meager set. This fact is established in this previous post (see Theorem 1 in that post).

For the inequality \mathfrak{d} \le \text{cof}(\mathcal{M}), see Corollary 5.4 of [1]. For the additional inequalities, see Theorem 5.6 in [1].

The next post is on the full Cichon’s Diagram.

Reference

  1. 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.

\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

Cardinals associated with an ideal

This is the first in a series of posts leading to a diagram called the Cichon’s diagram. The diagram displays relationships among twelve small cardinals, eight of which are defined by using \sigma-ideals. The purpose of this post is to set up the scene.

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

Ideals and \sigma -Ideals

Let X be a set. Let \mathcal{I} be a collection of subsets of X. We say that \mathcal{I} is an ideal on X if the following three conditions hold.

  1. \varnothing \in \mathcal{I}.
  2. If A \in \mathcal{I} and B \subset A, then B \in \mathcal{I}.
  3. If A, B \in \mathcal{I}, then A \cup B \in \mathcal{I}.

If X \notin \mathcal{I}, then \mathcal{I} is said to be a proper ideal. Note that if X \in \mathcal{I}, then \mathcal{I} would simply be the power set of X. Thus we would only want to focus on proper ideals. Thus by ideal we mean proper ideal.

We say that \mathcal{I} is a \sigma-ideal on X if it is an ideal with the additional property that it is closed under taking countable unions, i.e. if for each n \in \omega, A_n \in \mathcal{I}, then \bigcup_{n \in \omega} A_n \in \mathcal{I}. For the discussion that follows, we even require that all singleton subsets of X are members of any \sigma-ideal \mathcal{I}.

Elements of an ideal or a \sigma-ideal are considered “small sets” or “negligible sets”. The definition of \sigma-ideal does indeed reflect how small sets should behave. The empty set is naturally a small set. Any subset of a small set should be a small set. The union of countably many small sets should also be a small set as is any countable set (the union of countably many singleton sets).

Let \mathcal{B} be a collection of subsets of the set X. We assume that \mathcal{B} is closed under taking countable unions. It is easy to verify that the set

    \mathcal{I}=\{ A \subset X: \exists \ B \in \mathcal{B} \text{ such that } A \subset B \}

is a \sigma-ideal on X. This \sigma-ideal \mathcal{I} is said to be generated by the set \mathcal{B}. The set \mathcal{B} is called a base for the \sigma-ideal \mathcal{I}. A subbase for a \sigma-ideal is simply a collection of subsets of X. Then a base would be generated by taking countable unions of sets in the subbase.

Four Cardinals

We now discuss the cardinal characteristics associated with a \sigma-ideal. As before, let X be a set and \mathcal{I} be a \sigma-ideal on X. As discussed above, we require that all singleton sets are in \mathcal{I}. We define the following four cardinals.

    Additivity Number
    \text{add}(\mathcal{I})=\text{min} \{ \lvert \mathcal{A} \lvert: \mathcal{A} \subset \mathcal{I} \text{ and } \bigcup \mathcal{A} \notin \mathcal{I} \}

    Covering Number
    \text{cov}(\mathcal{I})=\text{min} \{ \lvert \mathcal{A} \lvert: \mathcal{A} \subset \mathcal{I} \text{ and } \bigcup \mathcal{A} = X \}

    Uniformity Number
    \text{non}(\mathcal{I})=\text{min} \{ \lvert A \lvert: A \subset X \text{ and } A \notin \mathcal{I} \}

    Cofinality Number
    \text{cof} (\mathcal{I})=\text{min} \{ \lvert \mathcal{B} \lvert: \mathcal{B} \subset \mathcal{I} \text{ and } \mathcal{B} \text{ is cofinal in } \mathcal{I} \}

A subset \mathcal{B} of \mathcal{I} is said to be cofinal in \mathcal{I} if for each A \in \mathcal{I}, there exists B \in \mathcal{B} such that A \subset B, i.e. \mathcal{B} is cofinal in the partial order \subset. Such a \mathcal{B} is a base for \mathcal{I}.

The numbers \text{add}(\mathcal{I}), \text{cov}(\mathcal{I}) and \text{cof} (\mathcal{I}) are the minimum cardinalities of certain subfamilies of the \sigma-ideal \mathcal{I} which fail to be small, i.e. not in \mathcal{I}. The additivity number \text{add}(\mathcal{I}) is the least cardinality of a subfamily of \mathcal{I} whose union is not in \mathcal{I}. The covering number \text{cov}(\mathcal{I}) is the minimum cardinality of a subfamily of \mathcal{I} whose union is the entire set X. The covering number is the minimum cardinality of a covering of X with elements of \mathcal{I}. The cofinality number \text{cof} (\mathcal{I}) is the least cardinality of a subfamily of \mathcal{I} that is a cofinal in \mathcal{I}. Equivalently, the cofinality number is the least cardinality of a base that generates the \sigma-ideal. The uniformity number \text{non}(\mathcal{I}) is the least cardinality of a subset of X that is not an element of \mathcal{I}.

The elements of the \sigma-ideal \mathcal{I} are “small” sets. The additivity number \text{add}(\mathcal{I}) is the smallest number of small sets whose union is not small. The covering number \text{cov}(\mathcal{I}) is then the smallest number of small sets that fill up the entire set X. The uniform number is the least cardinality of a non-small set.

Of these four cardinals, the smallest one is \text{add}(\mathcal{I}) and the largest one is \text{cof} (\mathcal{I}). Because \mathcal{I} is a \sigma-ideal, all four cardinals must be uncountable, hence \ge \aleph_1. Obviously \mathcal{I} is confinal in \mathcal{I}. Thus \text{cof} (\mathcal{I}) \le \lvert \mathcal{I} \lvert. The following inequalities also hold.

    \aleph_1 \le \text{add}(\mathcal{I}) \le \text{cov}(\mathcal{I}) \le \text{cof} (\mathcal{I}) \le \lvert \mathcal{I} \lvert

    \aleph_1 \le \text{add}(\mathcal{I}) \le \text{non}(\mathcal{I}) \le \text{cof} (\mathcal{I}) \le \lvert \mathcal{I} \lvert

    \displaystyle \aleph_1 \le \text{add}(\mathcal{I}) \le \text{min} \{ \text{cov}(\mathcal{I}), \text{non}(\mathcal{I}) \} \le \text{max} \{ \text{cov}(\mathcal{I}), \text{non}(\mathcal{I}) \} \le \text{cof} (\mathcal{I}) \le \lvert \mathcal{I} \lvert

Displaying the Four Cardinals in a Diagram

The inequalities shown in the preceding section can be displayed in a diagram such as the following.

Figure 1 – 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}

In the above diagram, a \Rightarrow b means a \le b. The smallest cardinal \text{add}(\mathcal{I}) is lower bounded by \aleph_1 on the lower left since \mathcal{I} is a \sigma-ideal. The largest cardinal \text{cof}(\mathcal{I}) is upper bounded by the cardinality of \mathcal{I} on the upper right since \mathcal{I} is cofinal in \mathcal{I}. The diagram tells us that the additivity number is less than or equal to the minimum of the uniformity number and the covering number. On the other hand, the cofinality number is greater than or equal to the maximum of the uniformity number and the covering number.

Examples

In the subsequent posts, we would like to focus on two \sigma-ideals, hence eight associated cardinals. To define these two ideals, let X=\mathbb{R}, the real line. Let \mathcal{M} be set of all meager subsets of the real line and let \mathcal{L} be the set of all subsets of the real line that are of Lebesgue measure zero.

    \mathcal{M}=\{ A \subset \mathbb{R}: A \text{ is a Meager set} \}

    \mathcal{L}=\{ A \subset \mathbb{R}: A \text{ is of Lebesgue measure zero} \}

In the real line, a set is nowhere dense if its closure contains no open set. A meager set is the union of countably many nowhere dense sets. It is straightforward to verify that \mathcal{M} is a \sigma-ideal on the real line \mathbb{R}. Because of the Baire category theorem, \mathbb{R} \notin \mathcal{M}. Thus it is a proper ideal. Similarly, it is straightforward to verify that \mathcal{L} is a \sigma-ideal as well as a proper ideal.

Before we examine the ideal \mathcal{M}, we consider the \sigma-ideal of bounded subsets of \omega^\omega in the next post.

\text{ }

\text{ }

\text{ }

Dan Ma topology

Daniel Ma topology

Dan Ma math

Daniel Ma mathematics

\copyright 2020 – Dan Ma