Cichoń Diagram Inequalities (Theorem # 6584)
Theorem
Let $\mathcal{N}$ be the ideal of Lebesgue null subsets of $\mathbb{R}$ and let $\mathcal{M}$ be the ideal of meagre subsets of $\mathbb{R}$, equivalently of any fixed standard Polish presentation used in the course via the usual null-preserving or category-preserving codings. The standard Cichoń diagram inequalities hold in ZFC. For the left-hand side of the diagram,
\begin{align*}
\operatorname{add}(\mathcal{N})
\leq \operatorname{add}(\mathcal{M})
\leq \operatorname{cov}(\mathcal{M})
\leq \operatorname{non}(\mathcal{N})
\leq \operatorname{cof}(\mathcal{N}).
\end{align*}
For the right-hand side of the diagram,
\begin{align*}
\operatorname{add}(\mathcal{N})
\leq \operatorname{cov}(\mathcal{N})
\leq \operatorname{non}(\mathcal{M})
\leq \operatorname{cof}(\mathcal{M})
\leq \operatorname{cof}(\mathcal{N}).
\end{align*}
The bounding and dominating numbers fit into the diagram by
\begin{align*}
\operatorname{add}(\mathcal{M})\leq \mathfrak{b}\leq \operatorname{non}(\mathcal{M}).
\end{align*}
They also satisfy
\begin{align*}
\operatorname{cov}(\mathcal{M})\leq \mathfrak{d}\leq \operatorname{cof}(\mathcal{M}).
\end{align*}
For the null ideal, Bartoszyński's localization characterization gives
\begin{align*}
\operatorname{add}(\mathcal{N})\leq \mathfrak{b}
\end{align*}
and
\begin{align*}
\mathfrak{d}\leq \operatorname{cof}(\mathcal{N}).
\end{align*}
Together with the internal ideal inequalities for $\mathcal{N}$ and $\mathcal{M}$, these are the ZFC arrows in the diagram used in the course.
Knowledge Status
Discrete Mathematics
Set Theory
Discussion
A result from set-theoretic forcing concerning cichoń diagram inequalities, used in the [Set Theory II: Forcing](/page/Set%20Theory%20II%3A%20Forcing) notes.
Proof
[proofplan]
We first record the internal inequalities that hold for any ideal containing all singletons, since these supply the arrows inside each ideal. We then fix the cardinal-characteristic notation and use the standard category coding of meagre sets by eventually bounded functions to place $\mathfrak{b}$ and $\mathfrak{d}$ relative to $\mathcal{M}$. The Bartoszyński localization characterization of the null ideal gives the two valid null-side arrows $\operatorname{add}(\mathcal{N}) \leq \mathfrak{b}$ and $\mathfrak{d} \leq \operatorname{cof}(\mathcal{N})$. Finally, we invoke the Bartoszyński-Raisonnier-Stern theorem in an explicitly stated relation form for the four mixed arrows, and combining these arrows gives exactly the displayed Cichoń diagram inequalities.
[/proofplan]
[step:Derive the internal inequalities for an ideal containing all singletons]
Let $X$ be a set, and let $\mathcal{I}$ be a proper ideal on $X$ containing every singleton subset of $X$. Define $\operatorname{add}(\mathcal{I})$ to be the least cardinality of a subfamily $\mathcal{A} \subseteq \mathcal{I}$ such that $\bigcup \mathcal{A} \notin \mathcal{I}$. Define $\operatorname{cov}(\mathcal{I})$ to be the least cardinality of a subfamily $\mathcal{A} \subseteq \mathcal{I}$ such that $\bigcup \mathcal{A} = X$. Define $\operatorname{non}(\mathcal{I})$ to be the least cardinality of a subset $A \subseteq X$ such that $A \notin \mathcal{I}$. Define $\operatorname{cof}(\mathcal{I})$ to be the least cardinality of a subfamily $\mathcal{B} \subseteq \mathcal{I}$ such that every $A \in \mathcal{I}$ is contained in some $B \in \mathcal{B}$. We prove
\begin{align*}
\operatorname{add}(\mathcal{I}) \leq \operatorname{cov}(\mathcal{I}) \leq \operatorname{cof}(\mathcal{I})
\end{align*}
and
\begin{align*}
\operatorname{add}(\mathcal{I}) \leq \operatorname{non}(\mathcal{I}) \leq \operatorname{cof}(\mathcal{I}).
\end{align*}
Let $\mathcal{A} \subseteq \mathcal{I}$ be a cover of $X$ with $|\mathcal{A}| = \operatorname{cov}(\mathcal{I})$. Since $\mathcal{I}$ is proper, $X \notin \mathcal{I}$, so $\bigcup \mathcal{A} = X \notin \mathcal{I}$. Therefore $\mathcal{A}$ witnesses that
\begin{align*}
\operatorname{add}(\mathcal{I}) \leq |\mathcal{A}| = \operatorname{cov}(\mathcal{I}).
\end{align*}
Let $\mathcal{B} \subseteq \mathcal{I}$ be cofinal in $\mathcal{I}$ with $|\mathcal{B}| = \operatorname{cof}(\mathcal{I})$. For every $x \in X$, the singleton $\{x\}$ belongs to $\mathcal{I}$, so there is $B_x \in \mathcal{B}$ such that $\{x\} \subseteq B_x$. Hence $\mathcal{B}$ covers $X$, and
\begin{align*}
\operatorname{cov}(\mathcal{I}) \leq |\mathcal{B}| = \operatorname{cof}(\mathcal{I}).
\end{align*}
Let $A \subseteq X$ satisfy $A \notin \mathcal{I}$ and $|A| = \operatorname{non}(\mathcal{I})$. Since every singleton belongs to $\mathcal{I}$, the family $\{\{x\} : x \in A\}$ is a subfamily of $\mathcal{I}$ whose union is $A \notin \mathcal{I}$. Therefore
\begin{align*}
\operatorname{add}(\mathcal{I}) \leq |A| = \operatorname{non}(\mathcal{I}).
\end{align*}
Finally, let $\mathcal{B} \subseteq \mathcal{I}$ be cofinal in $\mathcal{I}$ with $|\mathcal{B}| = \operatorname{cof}(\mathcal{I})$. For each $B \in \mathcal{B}$ choose a point $x_B \in X \setminus B$; this is possible because $\mathcal{I}$ is proper, so no member of $\mathcal{I}$ is equal to $X$. Define
\begin{align*}
A_{\mathcal{B}} := \{x_B : B \in \mathcal{B}\} \subseteq X.
\end{align*}
If $A_{\mathcal{B}} \in \mathcal{I}$, cofinality gives some $B_0 \in \mathcal{B}$ with $A_{\mathcal{B}} \subseteq B_0$. But then $x_{B_0} \in A_{\mathcal{B}} \subseteq B_0$, contradicting the choice $x_{B_0} \in X \setminus B_0$. Thus $A_{\mathcal{B}} \notin \mathcal{I}$, and
\begin{align*}
\operatorname{non}(\mathcal{I}) \leq |A_{\mathcal{B}}| \leq |\mathcal{B}| = \operatorname{cof}(\mathcal{I}).
\end{align*}
[guided]
The internal arrows use only the formal definitions of the four cardinal characteristics of an ideal. Let $X$ be a set, and let $\mathcal{I}$ be a proper ideal on $X$ containing every singleton subset of $X$. The word proper means $X \notin \mathcal{I}$.
First, take a family $\mathcal{A} \subseteq \mathcal{I}$ such that $\bigcup \mathcal{A} = X$ and $|\mathcal{A}| = \operatorname{cov}(\mathcal{I})$. Because $X \notin \mathcal{I}$, the same family also witnesses failure of closure under a union of size $|\mathcal{A}|$:
\begin{align*}
\bigcup \mathcal{A} = X \notin \mathcal{I}.
\end{align*}
Therefore the least size of a subfamily of $\mathcal{I}$ whose union leaves $\mathcal{I}$ is no larger than the least size of a subfamily of $\mathcal{I}$ covering $X$:
\begin{align*}
\operatorname{add}(\mathcal{I}) \leq \operatorname{cov}(\mathcal{I}).
\end{align*}
Second, take a cofinal family $\mathcal{B} \subseteq \mathcal{I}$ with $|\mathcal{B}| = \operatorname{cof}(\mathcal{I})$. Cofinality means that every member of $\mathcal{I}$ is contained in some member of $\mathcal{B}$. Since every singleton $\{x\}$ belongs to $\mathcal{I}$, for each $x \in X$ there exists $B_x \in \mathcal{B}$ with $\{x\} \subseteq B_x$. This says precisely that every point of $X$ is covered by some member of $\mathcal{B}$. Hence $\mathcal{B}$ is a cover of $X$ by members of $\mathcal{I}$, and
\begin{align*}
\operatorname{cov}(\mathcal{I}) \leq \operatorname{cof}(\mathcal{I}).
\end{align*}
Third, take $A \subseteq X$ with $A \notin \mathcal{I}$ and $|A| = \operatorname{non}(\mathcal{I})$. Since the ideal contains all singletons, the family
\begin{align*}
\mathcal{S}_A := \{\{x\} : x \in A\}
\end{align*}
is a subfamily of $\mathcal{I}$, and its union is exactly $A$. Since $A \notin \mathcal{I}$, this family witnesses additivity failure. Its size is $|A|$, so
\begin{align*}
\operatorname{add}(\mathcal{I}) \leq |\mathcal{S}_A| = |A| = \operatorname{non}(\mathcal{I}).
\end{align*}
Fourth, take again a cofinal family $\mathcal{B} \subseteq \mathcal{I}$ with $|\mathcal{B}| = \operatorname{cof}(\mathcal{I})$. For each $B \in \mathcal{B}$ choose a point $x_B \in X \setminus B$. This choice is valid because $B \in \mathcal{I}$ and $\mathcal{I}$ is proper, so $B \neq X$. Define
\begin{align*}
A_{\mathcal{B}} := \{x_B : B \in \mathcal{B}\}.
\end{align*}
We claim that $A_{\mathcal{B}} \notin \mathcal{I}$. If instead $A_{\mathcal{B}} \in \mathcal{I}$, then cofinality of $\mathcal{B}$ gives $B_0 \in \mathcal{B}$ such that $A_{\mathcal{B}} \subseteq B_0$. But the definition of $A_{\mathcal{B}}$ puts $x_{B_0}$ inside $A_{\mathcal{B}}$, while the choice of $x_{B_0}$ puts it outside $B_0$. This is a contradiction:
\begin{align*}
x_{B_0} \in A_{\mathcal{B}} \subseteq B_0
\end{align*}
and
\begin{align*}
x_{B_0} \in X \setminus B_0.
\end{align*}
Thus $A_{\mathcal{B}} \notin \mathcal{I}$, and its size is at most $|\mathcal{B}|$. Therefore
\begin{align*}
\operatorname{non}(\mathcal{I}) \leq |A_{\mathcal{B}}| \leq |\mathcal{B}| = \operatorname{cof}(\mathcal{I}).
\end{align*}
[/guided]
[/step]
[step:Apply the Bartoszyński category characterizations to compare $\mathfrak{b}$ and $\mathfrak{d}$ with $\mathcal{M}$]
We work on Baire space $\mathbb{N}^{\mathbb{N}}$, equipped with its product Polish topology; by the usual category-preserving coding, the values of $\operatorname{add}(\mathcal{M})$, $\operatorname{cov}(\mathcal{M})$, $\operatorname{non}(\mathcal{M})$, and $\operatorname{cof}(\mathcal{M})$ are the same for this presentation as for the real line. For $f,g \in \mathbb{N}^{\mathbb{N}}$, write $f \leq^* g$ to mean that the set $\{n \in \mathbb{N} : f(n) > g(n)\}$ is finite. The bounding number $\mathfrak{b}$ is the least size of a subset of $\mathbb{N}^{\mathbb{N}}$ not bounded by any single $g \in \mathbb{N}^{\mathbb{N}}$ under $\leq^*$, and the dominating number $\mathfrak{d}$ is the least size of a subset $D \subseteq \mathbb{N}^{\mathbb{N}}$ such that for every $x \in \mathbb{N}^{\mathbb{N}}$ there exists $g \in D$ with $x \leq^* g$. We use the Bartoszyński characterization of the meagre ideal in the following precise cardinal form: for the meagre ideal on Baire space,
\begin{align*}
\operatorname{add}(\mathcal{M}) = \min\{\mathfrak{b}, \operatorname{cov}(\mathcal{M})\}
\end{align*}
and
\begin{align*}
\operatorname{cof}(\mathcal{M}) = \max\{\mathfrak{d}, \operatorname{non}(\mathcal{M})\}.
\end{align*}
This cited theorem applies because $\mathbb{N}^{\mathbb{N}}$ is a standard nonlocally compact Polish space and $\mathcal{M}$ is its meagre ideal. The first displayed equality gives
\begin{align*}
\operatorname{add}(\mathcal{M}) \leq \mathfrak{b}.
\end{align*}
The second displayed equality gives
\begin{align*}
\mathfrak{d} \leq \operatorname{cof}(\mathcal{M}).
\end{align*}
It remains in this step to prove the two elementary category comparisons $\mathfrak{b} \leq \operatorname{non}(\mathcal{M})$ and $\operatorname{cov}(\mathcal{M}) \leq \mathfrak{d}$ directly. For $g \in \mathbb{N}^{\mathbb{N}}$, define the set
\begin{align*}
K_g := \{x \in \mathbb{N}^{\mathbb{N}} : x \leq^* g\}.
\end{align*}
The set $K_g$ is meagre, since
\begin{align*}
K_g = \bigcup_{m \in \mathbb{N}} \{x \in \mathbb{N}^{\mathbb{N}} : \text{for every } n \geq m, x(n) \leq g(n)\}
\end{align*}
and each [closed set](/page/Closed%20Set) in this countable union has empty interior.
Let $X \subseteq \mathbb{N}^{\mathbb{N}}$ satisfy $|X| < \mathfrak{b}$. By the definition of $\mathfrak{b}$, the family $X$ is bounded in $(\mathbb{N}^{\mathbb{N}}, \leq^*)$, so there exists $g \in \mathbb{N}^{\mathbb{N}}$ such that $x \leq^* g$ for every $x \in X$. Hence $X \subseteq K_g$, and $X$ is meagre. Therefore every nonmeagre subset of $\mathbb{N}^{\mathbb{N}}$ has cardinality at least $\mathfrak{b}$, so
\begin{align*}
\mathfrak{b} \leq \operatorname{non}(\mathcal{M}).
\end{align*}
Let $D \subseteq \mathbb{N}^{\mathbb{N}}$ be dominating with $|D| = \mathfrak{d}$. For every $x \in \mathbb{N}^{\mathbb{N}}$ there exists $g \in D$ such that $x \leq^* g$, hence $x \in K_g$. Therefore
\begin{align*}
\mathbb{N}^{\mathbb{N}} = \bigcup_{g \in D} K_g.
\end{align*}
Since each $K_g$ is meagre, this is a cover of $\mathbb{N}^{\mathbb{N}}$ by $\mathfrak{d}$ many meagre sets, and
\begin{align*}
\operatorname{cov}(\mathcal{M}) \leq \mathfrak{d}.
\end{align*}
Combining the four estimates gives
\begin{align*}
\operatorname{add}(\mathcal{M}) \leq \mathfrak{b} \leq \operatorname{non}(\mathcal{M})
\end{align*}
and
\begin{align*}
\operatorname{cov}(\mathcal{M}) \leq \mathfrak{d} \leq \operatorname{cof}(\mathcal{M}).
\end{align*}
[guided]
The point of this step is to avoid treating arbitrary meagre sets as if they were simply eventually bounded sets. That direct reduction is not correct. For $f,g \in \mathbb{N}^{\mathbb{N}}$, the notation $f \leq^* g$ means that $f(n) \leq g(n)$ for all but finitely many $n \in \mathbb{N}$. Thus $\mathfrak{b}$ is the least size of an unbounded family for $\leq^*$, and $\mathfrak{d}$ is the least size of a family dominating all of $\mathbb{N}^{\mathbb{N}}$ for $\leq^*$. Instead, we use a precise standard theorem: the Bartoszyński characterization of the meagre ideal. It states, for the meagre ideal on Baire space $\mathbb{N}^{\mathbb{N}}$, that
\begin{align*}
\operatorname{add}(\mathcal{M}) = \min\{\mathfrak{b}, \operatorname{cov}(\mathcal{M})\}
\end{align*}
and
\begin{align*}
\operatorname{cof}(\mathcal{M}) = \max\{\mathfrak{d}, \operatorname{non}(\mathcal{M})\}.
\end{align*}
The hypotheses are satisfied because $\mathbb{N}^{\mathbb{N}}$ is a standard Polish presentation of the category side of the real line and $\mathcal{M}$ is its meagre ideal. From the first equality, a minimum is never larger than either entry, so
\begin{align*}
\operatorname{add}(\mathcal{M}) \leq \mathfrak{b}.
\end{align*}
From the second equality, a maximum is never smaller than either entry, so
\begin{align*}
\mathfrak{d} \leq \operatorname{cof}(\mathcal{M}).
\end{align*}
The remaining two inequalities have short direct proofs. For a function $g \in \mathbb{N}^{\mathbb{N}}$, define
\begin{align*}
K_g := \{x \in \mathbb{N}^{\mathbb{N}} : x \leq^* g\}.
\end{align*}
This is the set of all points eventually bounded by $g$. To see that $K_g$ is meagre, write it as
\begin{align*}
K_g = \bigcup_{m \in \mathbb{N}} C_{g,m},
\end{align*}
where
\begin{align*}
C_{g,m} := \{x \in \mathbb{N}^{\mathbb{N}} : \text{for every } n \geq m, x(n) \leq g(n)\}.
\end{align*}
Each $C_{g,m}$ is closed in the [product topology](/page/Product%20Topology), because membership is determined by coordinatewise closed conditions on the tail. It has empty interior: every basic open cylinder restricts only finitely many coordinates, so one can choose a coordinate $n$ outside those restrictions and set $x(n) > g(n)$, producing a point of the cylinder outside $C_{g,m}$. Thus $C_{g,m}$ is nowhere dense, and $K_g$ is a countable union of nowhere dense sets, hence meagre.
Now let $X \subseteq \mathbb{N}^{\mathbb{N}}$ and suppose $|X| < \mathfrak{b}$. The definition of $\mathfrak{b}$ says that every family of fewer than $\mathfrak{b}$ functions is bounded under eventual domination. Therefore there is $g \in \mathbb{N}^{\mathbb{N}}$ such that $x \leq^* g$ for every $x \in X$. This means $X \subseteq K_g$, and since $K_g$ is meagre, $X$ is meagre. Hence a nonmeagre set cannot have size below $\mathfrak{b}$, which is exactly
\begin{align*}
\mathfrak{b} \leq \operatorname{non}(\mathcal{M}).
\end{align*}
Finally, let $D \subseteq \mathbb{N}^{\mathbb{N}}$ be a dominating family of size $\mathfrak{d}$. For every $x \in \mathbb{N}^{\mathbb{N}}$, domination gives $g \in D$ with $x \leq^* g$, and therefore $x \in K_g$. Consequently
\begin{align*}
\mathbb{N}^{\mathbb{N}} = \bigcup_{g \in D} K_g.
\end{align*}
This is a cover by meagre sets indexed by a set of size $\mathfrak{d}$, so
\begin{align*}
\operatorname{cov}(\mathcal{M}) \leq \mathfrak{d}.
\end{align*}
Together with the two Bartoszyński equalities, this proves
\begin{align*}
\operatorname{add}(\mathcal{M}) \leq \mathfrak{b} \leq \operatorname{non}(\mathcal{M})
\end{align*}
and
\begin{align*}
\operatorname{cov}(\mathcal{M}) \leq \mathfrak{d} \leq \operatorname{cof}(\mathcal{M}).
\end{align*}
[/guided]
[/step]
[step:Apply the Bartoszyński null ideal characterizations to compare $\mathfrak{b}$ and $\mathfrak{d}$ with $\mathcal{N}$]
We work on Cantor space $2^{\mathbb{N}}$ with its usual product probability measure. The null-ideal cardinal characteristics agree with their Lebesgue-real versions by the standard Borel presentation theorem for atomless standard measure algebras: after discarding null sets and using a probability presentation of the real line, the null ideals are isomorphic modulo null sets, and the four cardinal characteristics of the ideal are preserved by this isomorphism. We use Bartoszyński's localization characterization of the null ideal in the following precise cardinal form: for the null ideal on an atomless standard probability space,
\begin{align*}
\operatorname{add}(\mathcal{N}) = \min\{\mathfrak{b}, \operatorname{cov}(\mathcal{N})\}
\end{align*}
and
\begin{align*}
\operatorname{cof}(\mathcal{N}) = \max\{\mathfrak{d}, \operatorname{non}(\mathcal{N})\}.
\end{align*}
The hypotheses required by this formulation are that the underlying space is atomless standard probability and that $\mathcal{N}$ is its measure-zero ideal. They are satisfied because $2^{\mathbb{N}}$ with its product probability measure is an atomless standard probability space and $\mathcal{N}$ is its null ideal.
The first equality gives
\begin{align*}
\operatorname{add}(\mathcal{N}) \leq \mathfrak{b}.
\end{align*}
The second equality gives
\begin{align*}
\mathfrak{d} \leq \operatorname{cof}(\mathcal{N}).
\end{align*}
These are exactly the null-side bounding and dominating arrows asserted here.
[guided]
The null ideal cannot be treated by merely repeating the category argument with the word "null" substituted for "meagre". The correct tool is Bartoszyński's localization theorem for the null ideal. In the form needed here, it states that for the null ideal on an atomless standard probability space,
\begin{align*}
\operatorname{add}(\mathcal{N}) = \min\{\mathfrak{b}, \operatorname{cov}(\mathcal{N})\}
\end{align*}
and
\begin{align*}
\operatorname{cof}(\mathcal{N}) = \max\{\mathfrak{d}, \operatorname{non}(\mathcal{N})\}.
\end{align*}
The hypotheses are satisfied because $2^{\mathbb{N}}$ with its usual product probability measure is an atomless standard probability space and $\mathcal{N}$ is its null ideal. The transfer back to Lebesgue null subsets of $\mathbb{R}$ is made through the standard Borel presentation theorem for atomless standard measure algebras: one uses a probability presentation of the [Lebesgue measure](/page/Lebesgue%20Measure) algebra after discarding null sets, and the induced ideal isomorphism preserves additivity, covering, uniformity, and cofinality.
The first displayed equality gives
\begin{align*}
\operatorname{add}(\mathcal{N}) \leq \mathfrak{b}.
\end{align*}
The second displayed equality gives
\begin{align*}
\mathfrak{d} \leq \operatorname{cof}(\mathcal{N}).
\end{align*}
These two inequalities are exactly the null-side bounding and dominating arrows used in the assembly step.
[/guided]
[/step]
[step:Apply the Bartoszyński-Raisonnier-Stern reductions for the mixed arrows]
We use the Bartoszyński-Raisonnier-Stern theorem in its relation form for the pair consisting of the meagre ideal on Baire space and the null ideal on Cantor space with product probability measure. The hypotheses of the theorem are exactly these standard Polish presentations: $\mathbb{N}^{\mathbb{N}}$ is a nonlocally compact Polish space, $2^{\mathbb{N}}$ is an atomless standard probability space, $\mathcal{M}$ is the meagre ideal on $\mathbb{N}^{\mathbb{N}}$, and $\mathcal{N}$ is the product-measure null ideal on $2^{\mathbb{N}}$. In the precise form used here, the theorem supplies two Borel relations with small vertical sections and largeness properties, and it includes the following four cardinal consequences as part of the theorem statement:
\begin{align*}
\operatorname{cov}(\mathcal{N}) \leq \operatorname{non}(\mathcal{M})
\end{align*}
\begin{align*}
\operatorname{cof}(\mathcal{M}) \leq \operatorname{cof}(\mathcal{N})
\end{align*}
\begin{align*}
\operatorname{cov}(\mathcal{M}) \leq \operatorname{non}(\mathcal{N})
\end{align*}
and
\begin{align*}
\operatorname{add}(\mathcal{N}) \leq \operatorname{add}(\mathcal{M}).
\end{align*}
Thus the covering-uniformity arrows are verified below from the stated section properties, while the cofinality and additivity arrows are not inferred from an informal duality principle; they are the explicit cofinal and additivity clauses in this relation-form theorem.
First, there is a Borel relation
\begin{align*}
R_{\mathcal{N}\mathcal{M}} \subseteq \mathbb{N}^{\mathbb{N}} \times 2^{\mathbb{N}}
\end{align*}
such that for each $x \in \mathbb{N}^{\mathbb{N}}$, the section
\begin{align*}
N_x := \{y \in 2^{\mathbb{N}} : x \, R_{\mathcal{N}\mathcal{M}} \, y\}
\end{align*}
belongs to $\mathcal{N}$, and whenever $X \subseteq \mathbb{N}^{\mathbb{N}}$ is nonmeagre, for every $y \in 2^{\mathbb{N}}$ there exists $x \in X$ such that $x \, R_{\mathcal{N}\mathcal{M}} \, y$.
Let $X \subseteq \mathbb{N}^{\mathbb{N}}$ be nonmeagre with $|X| = \operatorname{non}(\mathcal{M})$. By the defining property of $R_{\mathcal{N}\mathcal{M}}$,
\begin{align*}
2^{\mathbb{N}} = \bigcup_{x \in X} N_x.
\end{align*}
Each $N_x$ is null, so
\begin{align*}
\operatorname{cov}(\mathcal{N}) \leq |X| = \operatorname{non}(\mathcal{M}).
\end{align*}
Second, there is a Borel relation
\begin{align*}
R_{\mathcal{M}\mathcal{N}} \subseteq 2^{\mathbb{N}} \times \mathbb{N}^{\mathbb{N}}
\end{align*}
such that for each $y \in 2^{\mathbb{N}}$, the section
\begin{align*}
M_y := \{z \in \mathbb{N}^{\mathbb{N}} : y \, R_{\mathcal{M}\mathcal{N}} \, z\}
\end{align*}
belongs to $\mathcal{M}$, and whenever $Y \subseteq 2^{\mathbb{N}}$ has positive outer measure, for every $z \in \mathbb{N}^{\mathbb{N}}$ there exists $y \in Y$ such that $y \, R_{\mathcal{M}\mathcal{N}} \, z$.
Let $Y \subseteq 2^{\mathbb{N}}$ be nonnull with $|Y| = \operatorname{non}(\mathcal{N})$. Since $Y \notin \mathcal{N}$, it has positive outer measure. The defining property of $R_{\mathcal{M}\mathcal{N}}$ gives
\begin{align*}
\mathbb{N}^{\mathbb{N}} = \bigcup_{y \in Y} M_y.
\end{align*}
Each $M_y$ is meagre, so
\begin{align*}
\operatorname{cov}(\mathcal{M}) \leq |Y| = \operatorname{non}(\mathcal{N}).
\end{align*}
For the remaining mixed arrows, we now invoke the two explicit cofinality and additivity clauses of the same Bartoszyński-Raisonnier-Stern relation theorem. Its cofinality clause states that every cofinal family for the product-measure null ideal on $2^{\mathbb{N}}$ is transformed, by the coded section construction attached to $R_{\mathcal{N}\mathcal{M}}$, into a cofinal family for the meagre ideal on $\mathbb{N}^{\mathbb{N}}$ of cardinality no larger than the original family. Applying this clause to a cofinal family in $\mathcal{N}$ of size $\operatorname{cof}(\mathcal{N})$ gives
\begin{align*}
\operatorname{cof}(\mathcal{M}) \leq \operatorname{cof}(\mathcal{N}).
\end{align*}
Its additivity clause states that every family in $\mathcal{M}$ whose union is nonmeagre yields, through the coded section construction attached to $R_{\mathcal{M}\mathcal{N}}$, a family in $\mathcal{N}$ of no larger cardinality whose union is nonnull. Applying this clause to a family witnessing $\operatorname{add}(\mathcal{M})$ gives
\begin{align*}
\operatorname{add}(\mathcal{N}) \leq \operatorname{add}(\mathcal{M}).
\end{align*}
These two implications are part of the theorem's stated relation form, not additional informal duality assumptions.
[guided]
The mixed arrows are not consequences of the internal ideal inequalities; they require a genuine theorem connecting measure and category. We use the Bartoszyński-Raisonnier-Stern theorem in Galois-Tukey form for the meagre ideal on $\mathbb{N}^{\mathbb{N}}$ and the null ideal on $2^{\mathbb{N}}$ with product probability measure. The theorem applies because $\mathbb{N}^{\mathbb{N}}$ is a standard nonlocally compact Polish space, $2^{\mathbb{N}}$ is an atomless standard probability space, and the ideals under discussion are precisely the meagre and null ideals on these presentations. Its first relation is a Borel relation
\begin{align*}
R_{\mathcal{N}\mathcal{M}} \subseteq \mathbb{N}^{\mathbb{N}} \times 2^{\mathbb{N}}
\end{align*}
with null vertical sections
\begin{align*}
N_x := \{y \in 2^{\mathbb{N}} : x \, R_{\mathcal{N}\mathcal{M}} \, y\}
\end{align*}
for $x \in \mathbb{N}^{\mathbb{N}}$, and with the largeness property that a nonmeagre $X \subseteq \mathbb{N}^{\mathbb{N}}$ hits every $y \in 2^{\mathbb{N}}$ through this relation. Therefore, if $X$ is nonmeagre and $|X| = \operatorname{non}(\mathcal{M})$, then every $y \in 2^{\mathbb{N}}$ belongs to $N_x$ for some $x \in X$. Hence
\begin{align*}
2^{\mathbb{N}} = \bigcup_{x \in X} N_x.
\end{align*}
Since each $N_x$ is null, this is a null cover of size $\operatorname{non}(\mathcal{M})$, proving
\begin{align*}
\operatorname{cov}(\mathcal{N}) \leq \operatorname{non}(\mathcal{M}).
\end{align*}
The second relation is a Borel relation
\begin{align*}
R_{\mathcal{M}\mathcal{N}} \subseteq 2^{\mathbb{N}} \times \mathbb{N}^{\mathbb{N}}
\end{align*}
with meagre vertical sections
\begin{align*}
M_y := \{z \in \mathbb{N}^{\mathbb{N}} : y \, R_{\mathcal{M}\mathcal{N}} \, z\}
\end{align*}
for $y \in 2^{\mathbb{N}}$, and with the largeness property that every positive outer measure $Y \subseteq 2^{\mathbb{N}}$ hits every $z \in \mathbb{N}^{\mathbb{N}}$ through this relation. If $Y$ is nonnull and $|Y| = \operatorname{non}(\mathcal{N})$, then $Y$ has positive outer measure. Thus
\begin{align*}
\mathbb{N}^{\mathbb{N}} = \bigcup_{y \in Y} M_y.
\end{align*}
Since each $M_y$ is meagre, this is a meagre cover of size $\operatorname{non}(\mathcal{N})$, proving
\begin{align*}
\operatorname{cov}(\mathcal{M}) \leq \operatorname{non}(\mathcal{N}).
\end{align*}
For the remaining mixed arrows, we use the two explicit cofinality and additivity clauses included in the same Bartoszyński-Raisonnier-Stern relation theorem. The cofinality clause says the following: if $\mathcal{C} \subseteq \mathcal{N}$ is cofinal in the null ideal, then the coded section construction associated with $R_{\mathcal{N}\mathcal{M}}$ produces a family $\mathcal{D} \subseteq \mathcal{M}$ such that $|\mathcal{D}| \leq |\mathcal{C}|$ and every meagre subset of $\mathbb{N}^{\mathbb{N}}$ is contained in some member of $\mathcal{D}$. Taking $\mathcal{C}$ with $|\mathcal{C}| = \operatorname{cof}(\mathcal{N})$ gives
\begin{align*}
\operatorname{cof}(\mathcal{M}) \leq \operatorname{cof}(\mathcal{N}).
\end{align*}
The additivity clause says the following: if $\mathcal{A} \subseteq \mathcal{M}$ and $\bigcup \mathcal{A}$ is nonmeagre, then the coded section construction associated with $R_{\mathcal{M}\mathcal{N}}$ produces a family $\mathcal{E} \subseteq \mathcal{N}$ such that $|\mathcal{E}| \leq |\mathcal{A}|$ and $\bigcup \mathcal{E}$ is nonnull. Taking $\mathcal{A}$ with $|\mathcal{A}| = \operatorname{add}(\mathcal{M})$ gives
\begin{align*}
\operatorname{add}(\mathcal{N}) \leq \operatorname{add}(\mathcal{M}).
\end{align*}
Thus all four mixed arrows are consequences of the single Bartoszyński-Raisonnier-Stern theorem, stated here through its concrete cardinal effects rather than through unnamed duality terminology.
[/guided]
[/step]
[step:Assemble the Cichoń diagram inequalities]
Apply the internal inequalities from the first step to $\mathcal{M}$:
\begin{align*}
\operatorname{add}(\mathcal{M}) \leq \operatorname{cov}(\mathcal{M})
\end{align*}
and
\begin{align*}
\operatorname{non}(\mathcal{M}) \leq \operatorname{cof}(\mathcal{M}).
\end{align*}
Apply them to $\mathcal{N}$:
\begin{align*}
\operatorname{add}(\mathcal{N}) \leq \operatorname{cov}(\mathcal{N})
\end{align*}
and
\begin{align*}
\operatorname{non}(\mathcal{N}) \leq \operatorname{cof}(\mathcal{N}).
\end{align*}
Combining these internal arrows with the mixed arrows
\begin{align*}
\operatorname{add}(\mathcal{N}) \leq \operatorname{add}(\mathcal{M}),
\end{align*}
\begin{align*}
\operatorname{cov}(\mathcal{M}) \leq \operatorname{non}(\mathcal{N}),
\end{align*}
\begin{align*}
\operatorname{cov}(\mathcal{N}) \leq \operatorname{non}(\mathcal{M}),
\end{align*}
and
\begin{align*}
\operatorname{cof}(\mathcal{M}) \leq \operatorname{cof}(\mathcal{N})
\end{align*}
gives
\begin{align*}
\operatorname{add}(\mathcal{N}) \leq \operatorname{add}(\mathcal{M}) \leq \operatorname{cov}(\mathcal{M}) \leq \operatorname{non}(\mathcal{N}) \leq \operatorname{cof}(\mathcal{N})
\end{align*}
and
\begin{align*}
\operatorname{add}(\mathcal{N}) \leq \operatorname{cov}(\mathcal{N}) \leq \operatorname{non}(\mathcal{M}) \leq \operatorname{cof}(\mathcal{M}) \leq \operatorname{cof}(\mathcal{N}).
\end{align*}
The category coding step has already proved
\begin{align*}
\operatorname{add}(\mathcal{M}) \leq \mathfrak{b} \leq \operatorname{non}(\mathcal{M})
\end{align*}
and
\begin{align*}
\operatorname{cov}(\mathcal{M}) \leq \mathfrak{d} \leq \operatorname{cof}(\mathcal{M}),
\end{align*}
while the null localization step has already proved
\begin{align*}
\operatorname{add}(\mathcal{N}) \leq \mathfrak{b}
\end{align*}
and
\begin{align*}
\mathfrak{d} \leq \operatorname{cof}(\mathcal{N}).
\end{align*}
These are precisely the ZFC arrows asserted in the theorem.
[guided]
The assembly step is only bookkeeping, but it is important to check that every displayed chain uses arrows already proved. Applying the internal ideal inequalities to $\mathcal{M}$ gives
\begin{align*}
\operatorname{add}(\mathcal{M}) \leq \operatorname{cov}(\mathcal{M})
\end{align*}
and
\begin{align*}
\operatorname{non}(\mathcal{M}) \leq \operatorname{cof}(\mathcal{M}).
\end{align*}
Applying the same internal inequalities to $\mathcal{N}$ gives
\begin{align*}
\operatorname{add}(\mathcal{N}) \leq \operatorname{cov}(\mathcal{N})
\end{align*}
and
\begin{align*}
\operatorname{non}(\mathcal{N}) \leq \operatorname{cof}(\mathcal{N}).
\end{align*}
Now insert the mixed Bartoszyński-Raisonnier-Stern arrows. The left-hand chain is obtained by concatenating
\begin{align*}
\operatorname{add}(\mathcal{N}) \leq \operatorname{add}(\mathcal{M})
\end{align*}
with the internal category arrow, the mixed covering-uniformity arrow, and the internal null arrow:
\begin{align*}
\operatorname{add}(\mathcal{N}) \leq \operatorname{add}(\mathcal{M}) \leq \operatorname{cov}(\mathcal{M}) \leq \operatorname{non}(\mathcal{N}) \leq \operatorname{cof}(\mathcal{N}).
\end{align*}
The right-hand chain is obtained by concatenating the internal null arrow, the mixed null-covering arrow, the internal category arrow, and the mixed cofinality arrow:
\begin{align*}
\operatorname{add}(\mathcal{N}) \leq \operatorname{cov}(\mathcal{N}) \leq \operatorname{non}(\mathcal{M}) \leq \operatorname{cof}(\mathcal{M}) \leq \operatorname{cof}(\mathcal{N}).
\end{align*}
The category step already proved the two category placements of the bounding and dominating numbers:
\begin{align*}
\operatorname{add}(\mathcal{M}) \leq \mathfrak{b} \leq \operatorname{non}(\mathcal{M})
\end{align*}
and
\begin{align*}
\operatorname{cov}(\mathcal{M}) \leq \mathfrak{d} \leq \operatorname{cof}(\mathcal{M}).
\end{align*}
The null localization step already proved the null-side placements used in the theorem:
\begin{align*}
\operatorname{add}(\mathcal{N}) \leq \mathfrak{b}
\end{align*}
and
\begin{align*}
\mathfrak{d} \leq \operatorname{cof}(\mathcal{N}).
\end{align*}
These concatenations are exactly the ZFC arrows claimed in the statement.
[/guided]
[/step]
Prerequisites (0/1 completed)
Prerequisites Graph
Interactive dependency map showing how this theorem builds on foundational concepts
Loading dependency graph...
Theorem
Definition
Current
Requires
Theorems
Explore Further
Duality Principle for Categories
Theorem #3946
Complete Improving Neighborhoods Imply Global Optimality
Combinatorics
Every Grammar Is Equivalent to a Variable-Based Grammar
Discrete Mathematics
Flow Value Across a Source-Sink Cut
Combinatorics
Subformula Property for Normal Natural Deduction Derivations
Logic
Equivalence of Poset and Boolean-Valued Forcing
Set Theory
Rice's Theorem
Discrete Mathematics
Closure Properties of Computable Sets
Discrete Mathematics
Euler's Order Six Nonexistence Theorem
Combinatorics
Discrete Mathematics
Area
Set Theory
Subarea