c.c.c. forcing without combinatorics

In this post, we shall discuss a short paper by Alan Mekler from 1984, concerning a non-combinatorial verification of the c.c.c. property for forcing notions.

Recall that a notion of forcing $\mathbb P$ is said to satisfy the c.c.c. iff all of its antichains are countable. A generalization of this property is that of being proper:

Definition (Shelah). Suppose that $\mathbb P$ is a given notion of forcing.

• Given a collection $\mathcal N$, we say that a condition $p\in\mathbb P$ is $(\mathcal N,\mathbb P)$-generic iff for every dense subset $D\subseteq\mathbb P$ such that $D\in\mathcal N$ and every extension $q$ of $p$, there exists some $r\in D\cap\mathcal N$ such that $q$ and $r$ are compatible.
•  We say that $\mathbb P$ is proper iff for every large enough regular cardinal $\kappa$ (i.e., so large that the collection of dense subsets of $\mathbb P$ is a member of $\mathcal H(\kappa)$),  and every countable elementary submodel $\mathcal N\prec(\mathcal H(\kappa),\in)$ with $\mathbb P\in\mathcal N$,  every condition $p\in\mathbb P\cap\mathcal N$ admits an extension which is $(\mathcal N,\mathbb P)$-generic.

Observation (Shelah/folklore). Every c.c.c. poset is proper.
Moreover, if $\mathbb P$ is a c.c.c poset and $\emptyset$ denotes its unique condition which is compatible with all elements of $\mathbb P$ (i.e., the maximal element, or the minimal element, depending on your forcing conventions), then $\emptyset$ is $(\mathcal N,\mathbb P)$-generic, for every relevant $\mathcal N$.
Proof. Suppose that $\kappa$ is large enough, and that $\mathcal N\prec (\mathcal H(\kappa),\in)$ is a countable elementary submodel containing $\mathbb P$. Suppose that $D$ is a dense subset of $\mathbb P$ that lies in $\mathcal N$, and that $q\in P$ (i.e., an extension of $\emptyset$), and let us find some $r\in\mathcal N\cap D$ which is compatible with $q$.
As $(\mathcal H(\kappa),\in)$ witnesses that $\mathbb P$ has the c.c.c., it witnesses that $D$ contains a countable maximal antichain, and hence there is some $A\in\mathcal N$, which is a countable maximal antichain, and a subset of $D$. Since $A$ is a maximal antichain, we may find some $r\in A$ which is compatible with $q$. Finally, since $A\in\mathcal N$ and $A$ is countable, we get that $A\subseteq\mathcal N\cap D$, and hence $r\in\mathcal N\cap D$ is a condition compatible with $q$. $\square$

Main observation (Mekler, 1984).  Suppose that $\mathbb P$ is a given notion of forcing. Then the following are equivalent:

1. $\mathbb P$ is c.c.c.;
2. for every large enough regular cardinal $\kappa$,  and every stationary subset $\mathcal S$ of $[\mathcal H(k)]^\omega$, there exists an elementary submodel $\mathcal N\prec(\mathcal H(\kappa),\in)$ with $\mathbb P\in\mathcal N\in\mathcal S$, for which  $\emptyset$ is $(\mathcal N,\mathbb P)$-generic.

Proof. We have already seen that $(1)\Rightarrow(2)$, so let us verify that $\neg(1)\Rightarrow\neg(2)$. Suppose that $A$ is a maximal uncountable antichain of $\mathbb P$, and let $D$ denote the collection of all the conditions that extends one of the elements of $A$. Then $D$ is a dense subset of $\mathbb P$. Let $\mathcal S$ be as in (2). Pick an elementary submodel $\mathcal N\in\mathcal S$ such that $A\in\mathcal N$ (and hence $D\in\mathcal N$, as well). In particular, $\mathcal N$ is countable, and we may find some $q\in A\setminus\mathcal N$. As $q$ extends $\emptyset$, there must exist some $r\in D\cap\mathcal N$ which is compatible with $q$. But $r$ extends some element $p\in A\cap\mathcal N$, and hence $q$ and $p$ are compatible. This is a contradiction to the fact that $p$ and $q$ are distinct (note that one lies in $\mathcal N$, and the other does not) elements of the antichain $A$. $\square$

I admit that Mekler’s characterization of c.c.c. notions of forcing seems artificial at a first glance. But, then he goes further and demonstrates the utility of this characterization by providing an elegant proof of a theorem of Devlin and Shelah. Let’s see!

Definition (Devlin-Shelah, 1978). The uniformization principle asserts that for every sequence of functions $\langle f_\alpha:L_\alpha\rightarrow 2\mid \alpha<\omega_1\rangle$ with $L_\alpha$ being a cofinal subset of $\alpha$ of minimal order-type for all $\alpha<\omega_1$, there exists some function (a “uniformizing function”) $h:\omega_1\rightarrow 2$ such that $f_\alpha\setminus h$ is finite for all $\alpha<\omega_1$.

The uniformization principle entails the failure of Whitehead’s conjecture, and in fact, a variation of it characterizes the failure of the conjecture when restricted to groups of size $\aleph_1$ (see here).

Devlin and Shelah proved that the uniformization principle follows from Martin’s axiom together with the failure of CH. Their proof amounts to showing that the natural notion of forcing for introducing a uniformizing function (via finite approximations) is c.c.c. Here, we shall provide two different proofs of this fact — the combinatorial one (following Devlin and Shelah), and the model-theoretic one (following Mekler).

Thus, given a sequence $\langle f_\alpha\mid\alpha<\omega_1\rangle$ as in the above definition, we consider the collection $\mathbb P$ of all triplets $\langle X,h,F\rangle$ that satisfy:

• $X\in[\omega_1]^{<\omega}$;
• $h:F\cup(\bigcup_{\alpha\in X}L_\alpha)\rightarrow 2$;
•  $f_\alpha\setminus h$ is finite for all $\alpha\in X$.

A triplet $\langle Y,g,G\rangle$ extends $\langle X,h,F\rangle$ if $Y\supseteq X, g\supseteq h, G\supseteq F$ and $g\restriction\text{dom}(h)=h$.

It is obvious that $\mathbb P$ introduces a uniformizing function (and that all needed for this, is meeting merely $\aleph_1$-many dense subsets), but not completely trivial to verify that $\mathbb P$ has the c.c.c. Here are the two proofs.

The combinatorial proof. Suppose that $\{ \langle X_\delta,h_\delta,F_\delta\rangle \mid i<\omega_1\}$ is a given collection of $\aleph_1$ many conditions. By the $\Delta$-system lemma, we may assume that $\{F_\delta\mid \delta<\omega_1\}$ forms a $\Delta$-system, with root $F$. Of course, we may moreover assume that $\{ h_\delta\restriction F\mid \delta<\omega_1\}$ is a singleton.
Let $\psi_1:\omega_1\rightarrow\omega_1$ be the regressive function satisfying:
$$\psi_1(\delta)=\max(X_\delta\cap \delta),\quad(\delta<\omega_1).$$
Fix $\theta<\omega_1$ such that $S_1:=\psi_1^{-1}\{\theta\}$ is stationary.
For all $\delta\in S_1$, put $\delta^+:=\min(S_1\setminus\delta+1)$.
Now, define a function $\psi_2:S_1\rightarrow\omega_1$ by letting:
$$\psi_2(\delta):=\sup\{\sup(\delta\cap L_\alpha)\mid {\alpha\in X_{\delta^+}}\},\quad(\delta\in S_1).$$
Notice that for all $\delta\in S_1$, and all $\alpha\in X_{\delta^+}$, either $\alpha<\delta^+$ and then $\alpha<\theta<\delta$ and $\sup(\delta\cap L_\alpha)\le\theta$, or, $\alpha\ge\delta^+$, and then $\delta\cap L_\alpha$ is finite.
It follows that $\psi_2$ is regressive, so pick $\theta^*<\omega_1$ such that $S_2:=\psi_2^{-1}\{\theta^*\}$ is stationary.

Since $\theta^*$ is countable, we get that $[\theta^*]^{<\omega}$ is countable, so let us pick a stationary subset $S_3\subseteq S_2$, such that $X_{\delta_1^+}\cap\theta^*=X_{\delta_2^+}\cap\theta^*$ for all $\delta_1,\delta_2\in S_3$.

For all $\delta\in S_3$, consider the following finite subsets of $\theta^*$:
$$Y_{\delta^+}:=\{ \beta\in\theta^*\mid \exists \alpha\in X_{\delta^+}(h_{{\delta^+}}(\beta)\neq f_\alpha(\beta))\},$$
and
$$Z_{\delta^+}:=\bigcup\{ L_\alpha\cap\theta^*\mid \alpha\in X_{{\delta^+}}\setminus\theta^*\}.$$
Fix a finite $Z\in[\theta^*]^{<\omega}$ such that $S_4:=\{\delta\in S_3\mid Y_{\delta^+}\cup Z_{\delta^+}= Z\}$ is stationary.
Now, find a stationary $S_5\subseteq S_4$ such that $h_{{\delta^+}}\restriction Z$ is independent of the choice of $\delta\in S_5$.

Finally, since $\sup(S_5)=\omega_1$, we may pick $\delta_1<\delta_2$ in $S_5$ such that $\text{dom}(h_{\delta_1^+})\subseteq \delta_2$.

Towards a contradiction, assume that $\langle X_{\delta_1^+},h_{\delta_1^+},F_{\delta_1^+}\rangle$ and $\langle X_{\delta_2^+},h_{\delta_2^+},F_{\delta_2^+}\rangle$ are incompatible,
and fix $\beta\in  \text{dom}(h_{\delta_1^+})\cap\text{dom}(h_{\delta_2^+})$ such that $h_{\delta_1^+}(\beta)\not=h_{\delta_2^+}(\beta)$. Clearly, $\beta\not\in F=F_{\delta_1^+}\cap F_{\delta_2^+}$.

Pick $\alpha\in X_{\delta_2^+}$ such that $\beta\in L_\alpha$.

• if $\alpha<\theta^*$, then $\beta$ must be a member of $Y_{\delta_1^+}\cup Y_{\delta_2^+}\subseteq Z$.
• if $\alpha\ge\theta^*$, then by $\text{dom}(h_{\delta_1^+})\subseteq\delta_2$ and $\delta_2\in S_2$, we get that $\beta\in L_\alpha\cap\theta^*$, so $\beta\in Z_{\delta_2^+}\subseteq Z$.

In either case, we get that $\beta\in Z$, thus, yielding a contradiction to the fact that $h_{{\delta^+}}\restriction Z$ is independent of the choice of $\delta\in S_5$. $\square$

The model-theoretic proof. Suppose that $\kappa$ is a large enough regular cardinal, and that $\mathcal S$ is a given stationary subset of $[\mathcal H(\kappa)]^\omega$. Pick an elementary submodel $\mathcal N\prec(\mathcal H(\kappa),\in)$ in $\mathcal S$ such that $\mathcal N$ is the limit (i.e., the union) of an incraesing chain of elementary submodels $\{ \mathcal N_i\mid i<\omega\}$ such that $\mathbb P,\langle f_\alpha\mid\alpha<\omega_1\rangle\in\mathcal N_0$. To see that $\emptyset$ is $(\mathcal N,\mathbb P)$-generic, we fix a condition $q=\langle X,h,F\rangle\in\mathbb P$ and a dense subset $D\in\mathcal N$, and argue the existence of some $r\in D\cap\mathcal N$ which is compatible with $q$. Here goes:
Put $\delta:=\mathcal N\cap\omega_1$, and consider the sets $$X_0:=X\cap\delta,\ X_1:=X\cap\{\delta\},\ X_2:=X\setminus(\delta+1).$$ (Note that if $X_1=\emptyset$, then finding a compatible $q\in D\cap\mathcal N$ is a straight-forward task. However, there is absolutely no reason to assume this.)

As $\bigcup\{ L_\alpha\mid \alpha\in X_2\}\cap\delta$ is a finite subset of $\delta$, we may find a large enough $i<\omega$ such that $\bigcup_{\alpha\in X_2}L_\alpha\cap\delta\subseteq\mathcal N_i$. Of course, we may assume that $i<\omega$ is so large such that $D, X_0\in\mathcal N_i$ and $F\cap\delta\in\mathcal N_i$. Denote $\delta_i:=\mathcal N_i\cap\omega_1$. As $L_\delta\cap\delta_i$ is finite, we altogether conclude that $\text{dom}(h)\cap\delta_i\subseteq\mathcal N_i$.
As $h\restriction\delta_i$ differs from $\bigcup_{\alpha\in X_0}f_\alpha$ by a finite set, and $\langle f_\alpha\mid\alpha\in X_0\rangle\in\mathcal N_i$, we get that $h\restriction\delta_i\in\mathcal N_i$. Put $g:=h\restriction\delta_i$ and $G:=(\text{dom}(h)\cap\delta_i)\setminus\bigcup_{\alpha\in X_0}L_\alpha$. Then $p:=\langle X_0,g,G\rangle\in\mathbb P\cap\mathcal N_i$, and compatible with $q$. Finally, since $D$ is a dense subset, and $D,p$ belongs to the elementary submodel $\mathcal N_i$, we may find some $r=\langle X^r,h^r,F^r\rangle\in D\cap\mathcal N$ that extends $p$. In particular, $\text{dom}(h^r)\subseteq\delta_i$ and $h^r\restriction\text{dom}(g)=h\restriction\text{dom}(g)$, and hence $r$ and $q$ are compatible. $\square$

So, which one of the proofs do you prefer?

If you prefer the model-theoretic proof, let me suggest the following exercise. Find a model-theoretic proof of Baumgartner’s theorem that the natural forcing notion for specializing an Aronszajn tree (via finite approximations) is c.c.c.