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 $MA_\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^* A$ iff $\sup(B\setminus A)<\sup(B)$. We say that $B$ is a pseudointersection of a family $\mathcal A$, if $B\subseteq^* 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>\aleph_0$.)

Lemma. If $X$ is a countable set, $\kappa<\mathfrak p$, and $\langle f_i:X\rightarrow\omega\mid i<\kappa\rangle$ is a sequence of functions, then there exists a function $g:X\rightarrow\omega$ such that for all $i<\kappa$: $$\{ x\in X\mid g(x)<f_i(x)\}\text{ is finite}.$$
Proof. Suppose that $\langle f_i\mid i<\kappa\rangle$ 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^* 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)\not\in 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. $\square$

Corollary. Suppose that $\kappa<\mathfrak p$, and $\langle A^\alpha_\sigma\mid \alpha<\kappa, \sigma\in{}^{<\omega}\omega\rangle$ 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^\alpha_\sigma$ is infinite.
Then there exists $h:\omega\rightarrow\omega$ such that $\{ n<\omega\mid h(n)\not\in A^\alpha_{h\restriction n}\}$ 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^\alpha_\sigma\mid \alpha<\kappa\}$. For every $\alpha<\kappa$, this induces a function $f^\alpha:{}^{<\omega}\omega\rightarrow\omega$ as follows: $$f^\alpha(\sigma):=\min\{ n<\omega\mid (A_\sigma\setminus A^\alpha_\sigma)\subseteq n\}.$$
By the preceding lemma, we then get a function $g:{}^{<\omega}\omega\rightarrow\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\rightarrow\omega$ by letting $h(0):=0$ and, recursively, $h(n):=g(h\restriction 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^\alpha_\sigma)\subseteq g(\sigma)\in A_\sigma$ whenever $\sigma\in\{h\restriction n\mid  m<n<\omega\}$. Consequently, $h(n)=g(h\restriction n)\in A^\alpha_{h\restriction n}$ whenever $m<n<\omega$. $\square$

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

  • $A^\uparrow=\{ p\in P\mid \exists a\in A(a\le p)\}$;
  • $A_\downarrow:=\{ p\in P\mid \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. $MA_\kappa(\mathcal C)$ asserts that for every partial order $\mathbb P\in\mathcal C$, and every sequence $\langle D_\alpha\mid \alpha<\kappa\rangle$ 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\neq\emptyset$ for all $p,q\in G$;
  2. $G_\downarrow\cap D_\alpha\neq\emptyset$ for all $\alpha<\kappa$.

Observation. $MA_{\aleph_0}(\text{the class of posets})$ holds.
Proof. Given a poset $\mathbb P=\langle P,\le\rangle$, and  a sequence $\langle D_n\mid n<\omega\rangle$ of cofinal subsets of $\mathbb P$, let us construct an order-preserving injection $g:\omega\rightarrow 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 $\langle G,\le\rangle$ is isomorphic to $\langle \omega,\in\rangle$, 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. $\square$

Next, let us study $MA_\kappa(\mathcal C)$ for $\kappa>\aleph_0$.

Definition. We say that a poset $\langle P,\le\rangle$ is $\sigma$-centered if there exists $\langle P_n\mid n<\omega\rangle$ 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\neq\emptyset$ for any finite subset $\{p_0,\ldots,p_{k+1}\}\subseteq P_n$.

Observation. $MA_{\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 $\langle P,\le\rangle$, 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, $\langle P_\sigma\mid \sigma\in[\omega]^{<\omega}\rangle$ witnesses that $\langle P,\le\rangle$ 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\neq\emptyset\}$.

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 $MA_{\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\neq\emptyset$ for all $p,q\in G$;
  2. $G_\downarrow\cap D_A\neq\emptyset$ for all $A\in\mathcal A$;
  3. $G_\downarrow\cap D_n\neq\emptyset$ 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^* 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$. $\square$

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

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

Proof. Suppose that $MA_{\kappa}$(the class of $\sigma$-centered posets of size $\le\kappa$) holds and that $\langle D_\alpha\mid \alpha<\kappa\rangle$ is a sequence of cofinal subset of some $\sigma$-centered poset $\mathbb P=\langle P,\le\rangle$. Let $\langle P_n\mid n<\omega\rangle$ 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 $\langle Q_n\mid n<\omega\rangle$ witnesses that $(Q,\le\restriction[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\neq\emptyset$ for all $p,q\in G$;
  2. $G_\downarrow\cap E_\alpha\neq\emptyset$ for all $\alpha<\kappa$.

In particular, $G_\downarrow\cap D_\alpha\neq\emptyset$ for all $\alpha<\kappa$, and we are done. $\square$

We now arrive to the main result of this post.

Theorem (Bell, 1981). $MA_{\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 $MA_{\kappa}$(the class of $\sigma$-centered posets of size $\le\kappa$) holds. Thus, let $\mathbb P=\langle P,\le\rangle$ be some $\sigma$-centered poset of size $\le\kappa$, as witnessed by $\langle P_n\mid n<\omega\rangle$. 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^\alpha_\sigma$ defined below will either be empty or infinite.
Let $\langle D^\alpha\mid \alpha<\kappa\rangle$ 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=\emptyset\text{ or }\{q\}^\uparrow\cap\{p_1\}^\uparrow=\emptyset\}.$$
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^\alpha_\emptyset$ be an arbitrary element of $P_0$.
  • Next, if $\sigma\in{}^{<\omega}\omega$ and $p^\alpha_\sigma$ is defined, then for all $n<\omega$, we let $p^\alpha_{\sigma{}^\frown n}$ be an element of $P_n$.  Whenever possible, we require in addition that $p^\alpha_{\sigma{}^\frown n}$ be an element of $\{p^\alpha_\sigma\}^\uparrow\cap (D^\alpha)^\uparrow$.

For every  $\sigma\in{}^{<\omega}\omega$, let $$A^\alpha_\sigma:=\{ n<\omega\mid \{p^\alpha_\sigma\}^\uparrow\cap (D^\alpha)^\uparrow\cap P_n\neq\emptyset\}.$$

Next, notice that for every $\sigma\in{}^{<\omega}\omega$, there exists some $n<\omega$ such that $\{ p^\alpha_\sigma\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^\alpha_\sigma\}^\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^\alpha_\sigma$. So $\bigcap_{\alpha\in I}A^\alpha_\sigma$ is infinite.

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

Given $\alpha<\kappa$, let us verify that $G_\downarrow\cap D^\alpha\neq\emptyset$ by pointing out that $p^\alpha_{h\restriction(g(\alpha)+1)}\in (D^\alpha)^\uparrow$. Indeed, we have $h(g(\alpha))\in A^\alpha_{h\restriction g(\alpha)}$ and hence $p^\alpha_{h\restriction(g(\alpha)+1)}$ has been defined according to the “whenever possible” case.

The same argument shows that if $\alpha<\kappa$, then $\{ p^\alpha_{h\restriction n}\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^\alpha_{h\restriction(g(\alpha)+1)}\le p^\alpha_{h\restriction n+1}\in P_{h(n)}$ and $p_\beta=p^\beta_{h\restriction(g(\beta)+1)}\le p^\beta_{h\restriction n+1}\in P_{h(n)}$. So $\{p_\alpha\}^\uparrow\cap\{p_\beta\}^\uparrow\neq\emptyset$ 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\neq\emptyset$, as well as $\{p_\beta\}^\uparrow\cap\{p_\gamma\}^\uparrow\neq\emptyset$. 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. $\square$

 

This entry was posted in Blog, Expository and tagged , . Bookmark the permalink.

2 Responses to Bell’s theorem on the cardinal invariant $\mathfrak p$

  1. Pingback: Jones’ theorem on the cardinal invariant p | Assaf Rinot

  2. Pingback: The S-space problem, and the cardinal invariant p | Assaf Rinot

Leave a Reply

Your email address will not be published. Required fields are marked *