Bell’s theorem on the cardinal invariant $\mathfrak{p}$

In this post, we shall provide a proof to a famous theorem of Murray Bell stating that $M{A}_{\kappa }(\text{the class of }\sigma \text{-centered posets})$ holds iff $\kappa <\mathfrak{p}$.

We commence with defining the cardinal invariant $\mathfrak{p}$. For sets $A$ and $B$, we write $B{\subseteq }^{\ast }A$ iff $sup(B\setminus A)<sup(B)$. We say that $B$ is a pseudointersection of a family $\mathcal{A}$, if $B{\subseteq }^{\ast }A$ for all $A\in \mathcal{A}$. Then, the cardinal $\mathfrak{p}$ stands for the smallest size of a family $\mathcal{A}$ of subsets of $\omega$ such that any finite subcollection of $\mathcal{A}$ admits an infinite pseudointersection, while $\mathcal{A}$ itself does not.

(To see that $\mathfrak{p}$ is well-defined, let $\mathcal{A}$ be any uniform ultrafilter on $\omega$. Also, note that a standard diagonlization argument entails that $\mathfrak{p}>{\mathrm{\aleph }}_0$.)

Lemma. If $X$ is a countable set, $\kappa <\mathfrak{p}$, and $⟨f_i:X\to \omega \mid i<\kappa ⟩$ is a sequence of functions, then there exists a function $g:X\to \omega$ such that for all $i<\kappa$: $$\{x\in X\mid g(x)<f_i(x)\}\text{ is finite}.$$
Proof. Suppose that $⟨f_i\mid i<\kappa ⟩$ is as above. Without loss of generality, $X=\omega$ and $f_i(j)<f_i(n)$ for all $j<n<\omega$ and $i<\kappa$. Fix a bijection $\pi :\omega \times \omega \leftrightarrow \omega$.  For each $i<\kappa$ and $j<\omega$, let

• $A_i:=\{\pi (n,m)\mid n<\omega ,m\ge f_i(n)\}$, and
• $B_j:=\{\pi (n,m)\mid j<n<\omega ,m<\omega \}$.

It is trivial to verify that $\bigcap _{i\in F,j\in J}{A}_i\cap B_j$ is infinite for every finite $F\subseteq \kappa$ and finite $J\subseteq \omega$. In particular, every finite subset of $\mathcal{A}:=\{A_i,B_j\mid i<\kappa ,j<\omega \}$ admits a pseudointersection. By $max\{\kappa ,\omega \}<\mathfrak{p}$, we then pick a pseudointersection P of $\mathcal{A}$. For all $j<\omega$, we have $P{\subseteq }^{\ast }{B}_j$, and hence we may let:

$$g(j):=min\{m<\omega \mid j<n<\omega ,\pi (n,m)\in P\}.$$

Finally, fix $i<\kappa$, and let us verify that $J:=\{j<\omega \mid g(j)<f_i(j)\}$ is finite. Fix $j\in J$. Let $(n,m)$ be such that $\pi (n,m)\in P$, $j<n$ and $g(j)=m$. Since $m=g(j)<f_i(j)$ and $f_i$ is increasing, we also get that $m<f_i(n)$. So $\pi (n,m)\notin A_i$. Thus, we have shown that for every $j\in J$, there exists some $(n_j,m_j)\in P\setminus A_i$ with $j<n_j$. Since $P\setminus A_i$ is finite, it must be the case that $J$ is finite. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Corollary. Suppose that $\kappa <\mathfrak{p}$, and $⟨A_{\sigma }^{\alpha }\mid \alpha <\kappa ,\sigma \in {}^{<\omega }\omega ⟩$ is a collection of subsets of $\omega$ with the property that for every $\sigma \in {}^{<\omega }\omega$ and $I\in [\kappa {]}^{<\omega }$, the set $\bigcap _{\alpha \in I}{A}_{\sigma }^{\alpha }$ is infinite.
Then there exists $h:\omega \to \omega$ such that $\{n<\omega \mid h(n)\notin A_{h\upharpoonright n}^{\alpha }\}$ is finite for all $\alpha <\kappa$.

Proof. Since $\kappa <\mathfrak{p}$, let us fix for every $\alpha <\kappa$, an infinite pseudointersection $A_{\sigma }$ of $\{A_{\sigma }^{\alpha }\mid \alpha <\kappa \}$. For every $\alpha <\kappa$, this induces a function $f^{\alpha }:{}^{<\omega }\omega \to \omega$ as follows: $$f^{\alpha }(\sigma ):=min\{n<\omega \mid (A_{\sigma }\setminus A_{\sigma }^{\alpha })\subseteq n\}.$$
By the preceding lemma, we then get a function $g:{}^{<\omega }\omega \to \omega$ such that $\{\sigma \in {}^{<\omega }\omega \mid g(\sigma )<f^{\alpha }(\sigma )\}$ is finite for all $\alpha <\kappa$. By pointwise increasing the function $g$, we may moreover assume that $g(\sigma )\in A_{\sigma }$ for all $\sigma \in {}^{<\omega }\omega$. Finally, define $h:\omega \to \omega$ by letting $h(0):=0$ and, recursively, $h(n):=g(h\upharpoonright n)$ for all positive $n<\omega$.

To see that $h$ works, fix $\alpha <\kappa$. Since $\{\sigma \in {}^{<\omega }\omega \mid g(\sigma )<f^{\alpha }(\sigma )\}$ is finite, let us pick a large enough $m<\omega$ such that $f^{\alpha }(\sigma )\le g(\sigma )$ whenever $\sigma \in {}^{<\omega }\omega$ has $\text{dom}(\sigma )>m$. In particular, $(A_{\sigma }\setminus A_{\sigma }^{\alpha })\subseteq g(\sigma )\in A_{\sigma }$ whenever $\sigma \in \{h\upharpoonright n\mid m<n<\omega \}$. Consequently, $h(n)=g(h\upharpoonright n)\in A_{h\upharpoonright n}^{\alpha }$ whenever $m<n<\omega$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Our next perspective is partial orders. For a poset $\mathbb{P}=⟨P,\le ⟩$, and a subset $A\subseteq P$, we write:

• $A^{\uparrow }=\{p\in P\mid \mathrm{\exists }a\in A(a\le p)\}$;
• $A_{\downarrow }:=\{p\in P\mid \mathrm{\exists }a\in A(p\le a)\}$.

Recall that $A$ is said to be cofinal in $\mathbb{P}$ in case that $A_{\downarrow }=P$.

Definition. $M{A}_{\kappa }(\mathcal{C})$ asserts that for every partial order $\mathbb{P}\in \mathcal{C}$, and every sequence $⟨D_{\alpha }\mid \alpha <\kappa ⟩$ of cofinal subsets of $\mathbb{P}$, there exists a subset $G\subseteq P$ that satisfies the following two:

1. $\{p{\}}^{\uparrow }\cap \{q{\}}^{\uparrow }\cap G\ne \mathrm{\varnothing }$ for all $p,q\in G$;
2. $G_{\downarrow }\cap D_{\alpha }\ne \mathrm{\varnothing }$ for all $\alpha <\kappa$.

Observation. $M{A}_{{\mathrm{\aleph }}_0}(\text{the class of posets})$ holds.
Proof. Given a poset $\mathbb{P}=⟨P,\le ⟩$, and  a sequence $⟨D_n\mid n<\omega ⟩$ of cofinal subsets of $\mathbb{P}$, let us construct an order-preserving injection $g:\omega \to P$ by recursion on $n\in \omega$. Let $g(0)$ be an arbitrary element of $D_0$, and let $g(n+1)$ be some element of $D_{n+1}$ such that $g(n)\le g(n+1)$ (by utilizing the fact that $D_{n+1}$ is cofinal in $\mathbb{P}$). Finally, put $G:=g[\omega ]$.
As $⟨G,\le ⟩$ is isomorphic to $⟨\omega ,\in ⟩$, we see that item (1) above is satisfied. As $G=g[\omega ]$ and $g\in \prod _{n<\omega }{D}_n$, we get in particular that item (2) above is satisfied. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Next, let us study $M{A}_{\kappa }(\mathcal{C})$ for $\kappa >{\mathrm{\aleph }}_0$.

Definition. We say that a poset $⟨P,\le ⟩$ is $\sigma$-centered if there exists $⟨P_n\mid n<\omega ⟩$ s.t. :

1. $P=\bigcup _{n<\omega }{P}_n$;
2. for all $n<\omega$, $P_n$ is centered, that is, $\{p_0{\}}^{\uparrow }\cap \cdots \cap \{p_{k+1}{\}}^{\uparrow }\cap P\ne \mathrm{\varnothing }$ for any finite subset $\{p_0,\dots ,p_{k+1}\}\subseteq P_n$.

Observation. $M{A}_{\mathfrak{p}}$(the class of $\sigma$-centered posets) fails.
Proof. By definition of $\mathfrak{p}$, it is easy to pick a family $\mathcal{A}\subseteq [\omega {]}^{\omega }$ such that:

1. for any finite subcollection $\mathcal{F}\subseteq \mathcal{A}$, we have $\bigcap \mathcal{F}\in \mathcal{A}$;
2. $\mathcal{A}$ does not admit an infinite pseudointersection;
3. $|\mathcal{A}|=\mathfrak{p}$.

Next, consider the poset $⟨P,\le ⟩$, where $P:=[\omega {]}^{<\omega }\times [\mathcal{A}{]}^{<\omega }$, and $({\sigma }_0,{\mathcal{F}}_0)\le ({\sigma }_1,{\mathcal{F}}_1)$ if the following three hold:

1. ${\sigma }_0\subseteq {\sigma }_1$;
2. ${\mathcal{F}}_0\subseteq {\mathcal{F}}_1$;
3. ${\sigma }_1\setminus {\sigma }_0\subseteq \bigcap {\mathcal{F}}_0$.

For any finite subset $\sigma$ of $\omega$, denote $P_{\sigma }:=\{(\sigma ,\mathcal{F})\mid \mathcal{F}\in [\mathcal{A}{]}^{<\omega }\}$. Clearly, $⟨P_{\sigma }\mid \sigma \in [\omega {]}^{<\omega }⟩$ witnesses that $⟨P,\le ⟩$ is $\sigma$-centered. Next, for all $A\in \mathcal{A}$ and $n<\omega$ define

• $D_A:=\{(\sigma ,\mathcal{F})\in P\mid A\in \mathcal{F}\}$, and
• $D_n:=\{(\sigma ,\mathcal{F})\in P\mid \sigma \setminus n\ne \mathrm{\varnothing }\}$.

For any $(\sigma ,\mathcal{F})$, and $A\in \mathcal{A}$, we have $(\sigma ,\mathcal{F}\cup \{A\})\in D_A$, and hence $D_A$ is cofinal. Also, for any $(\sigma ,\mathcal{F})$ and $n<\omega$, since $\mathcal{F}$ is a finite subset of $\mathcal{A}$, we have $\bigcap \mathcal{F}\in \mathcal{A}\subseteq [\omega {]}^{\omega }$, and hence we may pick some $m\in \bigcap \mathcal{F}\setminus n$, and infer that $(\sigma ,\mathcal{F})\le (\sigma \cup \{m\},\mathcal{F})\in D_n$. This shows that $D_n$ is cofinal.

Finally, assume towards a contradiction that $M{A}_{\mathfrak{p}}$(the class of $\sigma$-centered posets) does not fail. Then, by $|\{D_A,D_n\mid A\in \mathcal{A},n<\omega \}|=\mathfrak{p}$, we find a set $G$ such that:

1. $\{p{\}}^{\uparrow }\cap \{q{\}}^{\uparrow }\cap G\ne \mathrm{\varnothing }$ for all $p,q\in G$;
2. $G_{\downarrow }\cap D_A\ne \mathrm{\varnothing }$ for all $A\in \mathcal{A}$;
3. $G_{\downarrow }\cap D_n\ne \mathrm{\varnothing }$ for all $n<\omega$.

Let $B:=\bigcup \{\sigma \mid (\sigma ,\mathcal{F})\in G\}$. By clause (3) above, we see that $B$ is infinite. Thus, to meet a contradiction, it suffices to show that for all $A\in \mathcal{A}$, we have $B{\subseteq }^{\ast }A$. Fix $A\in \mathcal{A}$. By clause (2) above, let us pick $({\sigma }_0,{\mathcal{F}}_0)\le ({\sigma }_1,{\mathcal{F}}_1)$ such that $({\sigma }_0,{\mathcal{F}}_0)\in D_A$ and $({\sigma }_1,{\mathcal{F}}_1)\in G$. We claim that $B\setminus A$ is contained in the finite set ${\sigma }_0$. To see this, pick $k\in B\setminus A$. By definition of $B$ then, there exists some $({\sigma }_2,{\mathcal{F}}_2)\in G$ such that $k\in {\sigma }_2$. By clause (3) above, let us pick $({\sigma }_3,{\mathcal{F}}_3)\in \{p{\}}^{\uparrow }\cap \{q{\}}^{\uparrow }\cap G$.
By $k\in {\sigma }_2$, and $({\sigma }_2,{\mathcal{F}}_2)\le ({\sigma }_3,{\mathcal{F}}_3)$, we have $k\in {\sigma }_3$.
By $A\in {\mathcal{F}}_0$, and $({\sigma }_0,{\mathcal{F}}_0)\le ({\sigma }_3,{\mathcal{F}}_3)$, we have ${\sigma }_3\setminus {\sigma }_0\subseteq \bigcap {\mathcal{F}}_0\subseteq A$.
Altogether, either $k\in {\sigma }_0$ or $k\in A$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Lemma. For every infinite cardinal $\kappa$, the following are equivalent:

1. $M{A}_{\kappa }$(the class of $\sigma$-centered posets);
2. $M{A}_{\kappa }$(the class of $\sigma$-centered posets of size $\le \kappa$).

Proof. Suppose that $M{A}_{\kappa }$(the class of $\sigma$-centered posets of size $\le \kappa$) holds and that $⟨D_{\alpha }\mid \alpha <\kappa ⟩$ is a sequence of cofinal subset of some $\sigma$-centered poset $\mathbb{P}=⟨P,\le ⟩$. Let $⟨P_n\mid n<\omega ⟩$ witness that $\mathbb{P}$ is $\sigma$-centered. Let $\mathcal{M}$ be an elementary submodel of $(\mathcal{H}(\theta ),\in ,{<}_{\theta })$ for a large enough regular cardinal $\theta$ such that $|\mathcal{M}|=\kappa$ and $\mathbb{P}\in \mathcal{M}$ and $D_{\alpha },P_n\in \mathcal{M}$ for all $\alpha <\kappa$ and $n<\omega$. Let $Q:=P\cap \mathcal{M}$ and $Q_n:=Q_n\cap \mathcal{M}$. It is easy to see that $⟨Q_n\mid n<\omega ⟩$ witnesses that $(Q,\le \upharpoonright [Q{]}^2)$ is a $\sigma$-centered poset. For all $\alpha <\kappa$, put $E_{\alpha }:=D_{\alpha }\cap \mathcal{M}$. By elementarity, $E_{\alpha }$ is cofinal in $Q$. As $|Q|\le \kappa$, we then infer the existence of a subset $G\subseteq Q$ such that

1. $\{p{\}}^{\uparrow }\cap \{q{\}}^{\uparrow }\cap G\ne \mathrm{\varnothing }$ for all $p,q\in G$;
2. $G_{\downarrow }\cap E_{\alpha }\ne \mathrm{\varnothing }$ for all $\alpha <\kappa$.

In particular, $G_{\downarrow }\cap D_{\alpha }\ne \mathrm{\varnothing }$ for all $\alpha <\kappa$, and we are done. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

We now arrive to the main result of this post.

Theorem (Bell, 1981). $M{A}_{\kappa }$(the class of $\sigma$-centered posets) holds iff $\kappa <\mathfrak{p}$.
Proof. By all of the above, it suffices to show that if $\kappa <\mathfrak{p}$, then $M{A}_{\kappa }$(the class of $\sigma$-centered posets of size $\le \kappa$) holds. Thus, let $\mathbb{P}=⟨P,\le ⟩$ be some $\sigma$-centered poset of size $\le \kappa$, as witnessed by $⟨P_n\mid n<\omega ⟩$. Without loss of generality, the set $\{n<\omega \mid P_n=P_m\}$ is infinite for all $m<\omega$. This will entail that the sets $A_{\sigma }^{\alpha }$ defined below will either be empty or infinite.
Let $⟨D^{\alpha }\mid \alpha <\kappa ⟩$ be a sequence of cofinal subsets of $\mathbb{P}$. For any $p_0,p_1\in P$, let $$E_{p_0,p_1}:=\{q\in P\mid q\in \{p_0{\}}^{\uparrow }\cap \{p_1{\}}^{\uparrow }\text{ or }\{q{\}}^{\uparrow }\cap \{p_0{\}}^{\uparrow }=\mathrm{\varnothing }\text{ or }\{q{\}}^{\uparrow }\cap \{p_1{\}}^{\uparrow }=\mathrm{\varnothing }\}.$$
A moment reflection makes it clear that for every $r\in P$, there exists some $q\in E_{p_0,p_1}$ with $r\le q$. Thus, by $|P|\le \kappa$, we may assume that $$\{E_{p_0,p_1}\mid p_0,p_1\in P\}\subseteq \{D^{\alpha }\mid \alpha <\kappa \}.$$

Fix $\alpha <\kappa$.

• Let $p_{\mathrm{\varnothing }}^{\alpha }$ be an arbitrary element of $P_0$.
• Next, if $\sigma \in {}^{<\omega }\omega$ and $p_{\sigma }^{\alpha }$ is defined, then for all $n<\omega$, we let $p_{\sigma {}^{⌢}n}^{\alpha }$ be an element of $P_n$.  Whenever possible, we require in addition that $p_{\sigma {}^{⌢}n}^{\alpha }$ be an element of $\{p_{\sigma }^{\alpha }{\}}^{\uparrow }\cap (D^{\alpha }{)}^{\uparrow }$.

For every  $\sigma \in {}^{<\omega }\omega$, let $$A_{\sigma }^{\alpha }:=\{n<\omega \mid \{p_{\sigma }^{\alpha }{\}}^{\uparrow }\cap (D^{\alpha }{)}^{\uparrow }\cap P_n\ne \mathrm{\varnothing }\}.$$

Next, notice that for every $\sigma \in {}^{<\omega }\omega$, there exists some $n<\omega$ such that $\{p_{\sigma }^{\alpha }\mid \alpha <\kappa \}\subseteq P_n$. As the latter is centered, we then get that for every $\sigma \in {}^{<\omega }\omega$ and $I\in [\kappa {]}^{<\omega }$, there exists some $p\in P$ such that $p\in \bigcap _{\alpha \in I}\{p_{\sigma }^{\alpha }{\}}^{\uparrow }$. Since $\{D_{\alpha }\mid \alpha \in I\}$ is a finite collection of cofinal sets, it is easy to find $q\in \bigcap _{\alpha \in I}(D^{\alpha }{)}^{\uparrow }\cap \{p{\}}^{\uparrow }$. Let $m<\omega$ be such that $q\in P_m$, then $m\in \bigcap _{\alpha \in I}{A}_{\sigma }^{\alpha }$. So $\bigcap _{\alpha \in I}{A}_{\sigma }^{\alpha }$ is infinite.

It follows that may invoke the corollary established earlier in this post, and get a function $h:\omega \to \omega$ together with $g:\kappa \to \omega$ such that $h(n)\in A_{h\upharpoonright n}^{\alpha }$ whenever $g(\alpha )\le n<\omega$ and $\alpha <\kappa$. Write $p_{\alpha }:=p_{h\upharpoonright (g(\alpha )+1)}^{\alpha }$, and then put $$G:=\{p_{\alpha }\mid \alpha <\kappa \}.$$

Given $\alpha <\kappa$, let us verify that $G_{\downarrow }\cap D^{\alpha }\ne \mathrm{\varnothing }$ by pointing out that $p_{h\upharpoonright (g(\alpha )+1)}^{\alpha }\in (D^{\alpha }{)}^{\uparrow }$. Indeed, we have $h(g(\alpha ))\in A_{h\upharpoonright g(\alpha )}^{\alpha }$ and hence $p_{h\upharpoonright (g(\alpha )+1)}^{\alpha }$ has been defined according to the “whenever possible” case.

The same argument shows that if $\alpha <\kappa$, then $\{p_{h\upharpoonright n}^{\alpha }\mid g(\alpha )\le n<\omega \}$ is a linearly-ordered set. So for every $\alpha <\beta <\kappa$, if we take $n=max\{g(\alpha ),g(\beta )\}$, then $p_{\alpha }=p_{h\upharpoonright (g(\alpha )+1)}^{\alpha }\le p_{h\upharpoonright n+1}^{\alpha }\in P_{h(n)}$ and $p_{\beta }=p_{h\upharpoonright (g(\beta )+1)}^{\beta }\le p_{h\upharpoonright n+1}^{\beta }\in P_{h(n)}$. So $\{p_{\alpha }{\}}^{\uparrow }\cap \{p_{\beta }{\}}^{\uparrow }\ne \mathrm{\varnothing }$ for all $\alpha <\beta <\kappa$.

Finally, given $\alpha <\beta <\kappa$, pick $q\in G\cap (E_{p_{\alpha },p_{\beta }}{)}^{\uparrow }$. Then $q=p_{\gamma }$ for some $\gamma <\kappa$, and hence  $\{p_{\alpha }{\}}^{\uparrow }\cap \{p_{\gamma }{\}}^{\uparrow }\ne \mathrm{\varnothing }$, as well as $\{p_{\beta }{\}}^{\uparrow }\cap \{p_{\gamma }{\}}^{\uparrow }\ne \mathrm{\varnothing }$. Recalling that $q\in G\cap (E_{p_{\alpha },p_{\beta }}{)}^{\uparrow }$, we conclude that $q\in \{p_{\alpha }{\}}^{\uparrow }\cap \{p_{\beta }{\}}^{\uparrow }\cap G$, as required. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$