After my previous post on Mekler’s characterization of c.c.c. notions of forcing, Sam, Mike and myself discussed the value of it . We noticed that a prevalent verification of the c.c.c. goes like this: given an uncountable set of conditions, apply the $\Delta$-system lemma, thin out the outcome some more (typically, a few iterations are needed) and then find two conditions in the thinned-out set which are already compatible. This successful method usually ends up showing more than the c.c.c. — it shows that the poset has the Knaster property (i.e., every uncountable set of conditions, contains an uncountable subset of pairwise compatible conditions). However, if the notion of forcing does not have the Knaster property, then this method is unlikely to do the job. A-ha! So, that’s perhaps the value of Mekler’s verification method – to establish c.c.c. for posets which are not better than that. We decided to test this conjecture.
Todorcevic was around during our conversation, so we asked him for an example of a poset which is c.c.c., but does not have the Kanster property (of course, a Souslin tree is such an example, but Souslin trees are c.c.c. by definition, and we wanted to examine the verification method). He provided the following hint.
Example. Suppose that $\mathfrak b=\omega_1$, and let $\overrightarrow f=\langle f_\alpha\mid\alpha<\omega_1\rangle$ witness that. That is:
- $f_\alpha\in{}^\omega\omega$ is an increasing function for all $\alpha<\omega_1$;
- $\{ n<\omega\mid f_\alpha(n)\ge f_\beta(n)\}$ is finite, whenever $\alpha<\beta<\omega_1$;
- for every $g\in{}^\omega\omega$, there exists some $\alpha<\omega_1$ such that $\{ n<\omega\mid g(n)<f_\beta(n)\}$ is infinite, whenever $\alpha<\beta<\omega_1$.
Let $\alpha\unlhd\beta$ iff $\{ n<\omega\mid f_\alpha(n)>f_\beta(n)\}$ is empty. Now, let $\mathbb P$ be the collection of all finite antichains of the poset $\langle\omega_1,\unlhd\rangle$, ordered by inclusion.
So, I tried to use the Mekler method to verify that $\mathbb P$ is c.c.c., without much of success. (What about you? can you suggest such a proof?)
Eventually, I did find a proof, and this finding lead me to yet another characterization:
(Ridiculously trivial) Observtion. Suppose that $\mathbb P$ is a given notion of forcing. Then the following are equivalent:
- $\mathbb P$ is c.c.c.;
- for every large enough regular cardinal $\kappa$, there exists an elementary submodel $\mathcal N\prec(\mathcal H(\kappa),\in)$ with $\mathbb P\in\mathcal N$, that enjoys the following feature. For every uncountable $A\subseteq\mathbb P$ in $\mathcal N$, there exists $q\in A\setminus\mathcal N$, and $r\in A\cap\mathcal N$ which are compatible.
A second look at Mekler’s proof of the Devlin-Shelah theorem makes it clear that the latter characterization may be utilized to establish the c.c.c. of the Devlin-Shelah notion of forcing. So, we did not lose anything. Yet, the above (ridiculously trivial) characterization is the key to the proof that I came up with of the following.
Proposition. $\mathbb P$ is c.c.c.
Proof. Let $\mathcal N$ be an arbitrary elementary submodel of $(\mathcal H(\kappa),\in)$ for a large enough $\kappa$, such that $\overrightarrow f,\mathbb P\in\mathcal N$. Suppose that we are given an uncountable subset $A\subseteq\mathbb P$ in $\mathcal N$. Fix an arbitrary $q\in A\setminus\mathcal N$, and let us find some $r\in A\cap\mathcal N$ which is compatible with $q$.
Before we begin, we introduce some notation.
- For all $\alpha<\beta$, denote $$\Delta(\alpha,\beta):=\min\{ m<\omega\mid m\le n<\omega\rightarrow(f_\alpha(n)\le f_\beta(n))\};$$
- For all $\alpha<\beta$, denote $$\Gamma(\alpha,\beta):=\min\{ m<\omega\mid m\le n<\omega\rightarrow(f_\alpha(n)< f_\beta(n))\};$$
- For all $p\in\mathbb P$, and $m<\omega$, let $h_p^m:|p|\rightarrow{}^m\omega$ be the function satisfying $h_p^m(i)=f_\alpha\restriction m$ for the unique $\alpha\in p$ such that $|p\cap\alpha|=i$.
Here we go. Let $\rho=q\cap\mathcal N$. Then $\rho$ is a finite subset of $\mathcal N$, and hence in $\mathcal N$. Let $$S:=\{ \nu<\omega_1\mid \exists p\in A(p\cap\nu=\rho)\}.$$ Since $S\in\mathcal N$, and $\mathcal N\cap\omega_1\in S$ (as witnessed by $q$), we infer that $S$ is stationary. In particular, we may fix some $\nu\in S$ above $\max(q)$. Pick $p\in A\setminus\mathcal N$ such that $p\cap\nu=\rho$. Since $p\not\in\mathcal N$, we get that $p\neq\rho$ and $p\neq q$, so let $$m:=\max\{\Gamma(\alpha,\gamma)\mid \alpha<\gamma, \alpha\in q, \gamma\in p\}.$$
Put $h:=h^{m+1}_p$. Then $h\in\mathcal N$, and $p$ is a member of the following set (which lies in $\mathcal N$, as well): $$A(h,\rho):=\{ r\in A\mid h^{m+1}_r=h\ \& \exists\alpha<\omega_1(r\cap\alpha=\rho)\}.$$ In particular, we may pick some $r\in A(h,\rho)\cap\mathcal N$.
As $h^{m+1}_r=h^{m+1}_p$, we get that $|r|=|p|$, so let $\pi:r\rightarrow p$ be the order-preserving isomorphism. Then $\pi\restriction\rho$ is the identity map, and $f_\beta\restriction(m+1)=f_{\pi(\beta)}\restriction(m+1)$ for all $\beta\in r$.
We claim that $r$ and $q$ are compatible. Namely, that $\Delta(\beta,\alpha)>0$ for all $\beta<\alpha$ in $r\cup q$. Suppose that $\beta<\alpha$ are in $r\cup q$. For $\beta,\alpha\in r$ or $\beta,\alpha\in q$, it is immediate that $\Delta(\beta,\alpha)>0$, so suppose that $\beta\in r\setminus q$ and $\alpha\in q\setminus r$. As $r\cap q=\rho$, we get that $\beta<\alpha$. Let $\gamma:=\pi(\beta)$. By $f_\beta\restriction(m+1)=f_\gamma\restriction(m+1)$ and $\Gamma(\alpha,\gamma)\le m$, we get that $f_\alpha(m)< f_\gamma(m)=f_\beta(m)$, and hence $\Delta(\beta,\alpha)>m\ge 0$. $\square$
Note that essentially the same proof as above shows that $\mathbb P$ is productively c.c.c., and also that this works to any uncountable sequence of reals $\overrightarrow f$. So, what’s the role of $\mathfrak b=\aleph_1$? It is here to insure the following.
Proposition. $\mathbb P$ does not have the Knaster property.
Proof. Suppose that $A$ is an uncountable subset of $\mathbb P$. We shall find two conditions in $A$ which are incompatible. For this, we may already assume that $A$ forms a $\Delta$-system with a root $\rho$. In particular, $p\mapsto\min(p\setminus\rho)$ is an injection, and $B=\{ \min(p\setminus\rho)\mid p\in A\}$ is an uncountable subset of $\omega_1$. If we can find $\alpha<\beta$ in $B$ for which $\Delta(\alpha,\beta)=0$, then for the corresponding conditions $p,q\in A$ (i.e., $\alpha=\min(p\setminus\rho), \beta=\min(q\setminus\rho))$, we get that $p\cup q$ is not an antichain in the poset $\langle \omega_1,\unlhd\rangle$, and hence, $p$ and $q$ are incompatible.
Here we go. Fix a large enough regular cardinal $\kappa$, and then a countable elementary submodel $\mathcal N\preceq(H(\kappa),\in)$ with $B,\overrightarrow f\in\mathcal N$. Let $\delta:=\min(B\setminus\mathcal N)$. Evidently, $B\setminus(\delta+1)=\bigcup_{n<\omega}\{\beta\in B\setminus(\delta+1)\mid \Delta(\delta,\beta)=n\}$, so let us fix some $n<\omega$ such that $B_n:=\{\beta\in B\setminus(\delta+1)\mid \Delta(\delta,\beta)=n\}$ is uncountable. By the choice of $\overrightarrow f$ (more specifically, by item (3) there), we get that the set $$M:=\{ m<\omega\mid \sup\{ f_\beta(m)\mid \beta\in B_n\}=\omega\}$$ is non-empty (in fact, infinite), so consider its minimal element, $m:=\min(M)$.
For $t\in{}^m\omega$, denote $B^t_n:=\{ \beta\in B_n\mid t\subseteq f_\beta\}$. By minimality of $m$, the set $\{ t\in{}^m\omega\mid B^t_n\neq\emptyset\}$ is finite, so we can easily find some $t\in{}^m\omega$ such that $$\sup\{ f_\beta(m)\mid \beta\in B^t_n\}=\omega.$$ Since $\{ \beta\in B\mid t\subseteq f_\beta\}$ is a non-empty set that lies in $\mathcal N$, let us fix some $\alpha\in\mathcal N\cap B$ such that $t\subseteq f_\alpha$. Put $k:=\Delta(\alpha,\delta)$, and then pick $\beta\in B^t_n$ such that $f_\beta(m)>f_\alpha(k+n)$. Of course, $\alpha<\delta<\beta$.
We claim that $\Delta(\alpha,\beta)=0$. This is best seen by dividing into three cases:
- if $i<m$, then $f_\alpha(i)=t(i)=f_\beta(i)$;
- if $m\le i\le k+n$, then $f_\alpha(i)\le f_\alpha(k+n)<f_\beta(m)\le f_\beta(i)$ (recall that the elements of $\overrightarrow f$ are increasing functions!);
- if $k+n<i<\omega$, then $\Delta(\alpha,\delta)=k<i$ and $f_\alpha(i)\le f_\delta(i)$, as well as $\Delta(\delta,\beta)=n<i$ and $f_\delta(i)\le f_\beta(i)$. Altogether, $f_\alpha(i)\le f_\beta(i)$. $\square$
We conclude this post with an awkward proof of the following.
Fact. $\text{MA}_{\aleph_1}$ entails $\mathfrak b>\omega_1$.
Proof. Suppose not. Then $\text{MA}_{\aleph_1}$ is consistent together with the existence of a poset $\mathbb P=\langle P,\preceq\rangle$ of size $\aleph_1$ which is productively $c.c.c.$, but not Knaster. Define a poset $\mathbb Q=\langle Q,\le\rangle$, by $Q:={}^{<\omega}P$, and $q_1\le q_2$ (i.e., $q_2$ extends $q_1$) iff $\text{dom}(q_1)\subseteq \text{dom}(q_2)$, and $q_1(i)\preceq q_2(i)$ for all $i\in\text{dom}(q_1)$. Since $\mathbb P$ is productively $c.c.c$, $\mathbb Q$ is $c.c.c.$. Also, it a trivial fact that for any $p\in P$, and $q\in Q$, $q{}^\frown p\in Q$. So, $D_p:=\{ q\in Q\mid p\in\text{rng}(q)\}$ is dense in $\mathbb Q$, for all $p\in P$.
Finally, by $\text{MA}_{\aleph_1}$, let $G\subseteq Q$ be a directed set that meets any of the sets from the sequence $\langle D_p\mid p\in \mathbb P\rangle$. Denote $P_i:=\{ q(i)\mid q\in G\}$ for all $i<\omega$. Then $P=\bigcup_{i<\omega}P_i$. Since $G$ is $\le$-directed, $P_i$ is $\preceq$-directed for all $i<\omega$. It follows that for every uncountable $A\subseteq P$, there exists some $i<\omega$ such that $A\cap P_i$ is an uncountable subset of $A$ whose elements are pairwise compatible. That is, $\mathbb P$ has the Knaster property, contradicting the very choice of $\mathbb P$. $\square$
