Prikry Forcing

Recall that the chromatic number of a (symmetric) graph $(G,E)$, denoted $\text{Chr}(G,E)$, is the least (possible finite) cardinal $\kappa$, for which there exists a coloring $c:G\rightarrow\kappa$ such that $gEh$ entails $c(g)\neq c(h)$.
Given a forcing notion $\mathbb P$, it is natural to analyze $\text{Chr}(\mathbb P,\bot)$, where $p\bot q$ iff $p$ and $q$ are incompatible conditions. Here is a concrete example.

Prikry Forcing. Suppose that $\kappa$ is a measurable cardinal, and $\mathcal U$ is a non-principal, normal $\kappa$-complete ultrafilter over $\kappa$. Prikry’s notion of forcing $\mathbb P_{\mathcal U}$ is the collection of all pairs $(\sigma,A)$ such that

  1. $\sigma\in[\kappa]^{<\omega}$, and
  2. $A\in\mathcal U$ with $\max(\sigma)<\min(A)$.

$\blacktriangleright$ A condition $(\sigma_2,A_2)$ extends $(\sigma_1,A_1)$ iff $A_2\subseteq A_1$ and $\sigma_2\setminus\sigma_1\subseteq A_1$. That is, we are allowed to shrink the $A$-part, and allowed to end-extend $\sigma$ by adding to it finitely many elements from $A$.

Let us point out that $\text{Chr}(\mathbb P_{\mathcal U},\bot)\ge\kappa$:
Suppose not, as witnessed by some chromatic coloring $c:\mathbb P_\mathcal U\rightarrow\lambda$, with $\lambda<\kappa$. Define $f:[\kappa]^{2}\rightarrow\lambda$, by letting $f(\alpha,\beta):=c(\langle\alpha,\beta\rangle,\kappa)$. Then, by the Erdos-Rado theorem, there exists an infinite set $A$ (indeed, a set of size $\lambda^+$), for which $f\restriction [A]^2$ is constant. Let $\alpha<\beta<\gamma$ be elements of $A$. Then $c(\langle \alpha,\beta\rangle,\kappa)=f(\alpha,\beta)=f(\alpha,\gamma)=c(\langle \alpha,\gamma\rangle,\kappa)$, contradicting the fact that $(\langle \alpha,\beta\rangle,\kappa)\bot(\langle \alpha,\gamma\rangle,\kappa)$.

Now, let us show that $\text{Chr}(\mathbb P_{\mathcal U},\bot)=\kappa$, and even in a strong sense. For this, it is customary to introduce some terminology. We say that a subset $D\subseteq\mathbb P_\mathcal U$ is a deciding set if there exists a statement $\varphi$ in the forcing language, such that $$D=\{ p\in\mathbb P_\mathcal U\mid p\text{ decides } \varphi\}.$$

The Prikry property. There exists a chromatic coloring $c:\mathbb P_\mathcal U\rightarrow\kappa$ such that:

  1. any $c$-homogeneous set of size $<\kappa$ admits a lower bound;
  2. $c$ witnesses $\mathbb P_{\mathcal U}\nrightarrow[\text{Deciding}]^1_\kappa$, that is, $c[D]=\kappa$ for every deciding set $D\subseteq\mathbb P_\mathcal U$.

Proof. Let $c:\mathbb P_{\mathcal U}\rightarrow[\kappa]^{<\omega}$ be the projection map $(\sigma,A)\mapsto\sigma$. Since $\mathcal U$ is a filter, $c$ is a chromatic coloring. Moreover, if $Q$ is a $c$-homogeneous set of size $<\kappa$, then there exists some $\sigma\in[\kappa]^{<\omega}$ and $\mathcal A\in[\mathcal U]^{<\kappa}$ such that $Q=\{ (\sigma,A)\mid A\in\mathcal A\}$, and so the fact that $\mathcal U$ is $\kappa$-complete, entails that $p=(\sigma,\bigcap\mathcal A)$ is a lower bound for $Q$.
Next, suppose that we are given a statement $\varphi$ in the forcing language, together with some $\sigma\in[\kappa]^{<\omega}$, and let us find some $p\in\mathbb P_\mathcal U$ that decides $\varphi$, and satisfying $c(p)=\sigma$.
We shall take advantage of a theorem of Rowbottom stating that for every function $f:[\kappa]^{<\omega}\rightarrow2$, there exists a set of indiscernibles for $f$ that lies in $\mathcal U$. Indeed, define $f:[\kappa\setminus\max(\sigma)+1]^{<\omega}\rightarrow 2$ by letting $f(\eta)=1$ iff there exists some $B\in\mathcal U$, such that $(\sigma\cup\eta,B)$ forces $\varphi$ to hold.
Let $A\in\mathcal U$ be a set of indiscernibles for $f$, and put $q:=(\sigma,A)$. Then $c(q)=\sigma$, and we are left with showing that $q$ decides $\varphi$. Suppose it does not. Then there exist extensions $q_0=(\sigma_0,A_0)$ and $q_1=(\sigma_1,A_1)$ of $q$ such that $q_0$ forces $\varphi$ to hold, while $q_1$ forces $\varphi$ to fail. Note that by (possibly) further extending one of the conditions, we may assume that $|\sigma_0|=|\sigma_1|$. Let $\eta_0,\eta_1$ be such that $\sigma_0=\sigma\cup\eta_0$ and $\sigma_1=\sigma\cup\eta_1$. Then, there exists some $n<\omega$ such that $\{\eta_0,\eta_1\}\subseteq[\kappa\setminus\max(\sigma)+1]^n$. In particular, $f(\eta_0)=f(\eta_1)$.
By the choice of $q_0$, we get that $f(\eta_0)=1$. It follows that $f(\eta_1)=1$, and hence there exists some $B\in\mathcal U$ such that $(\sigma\cup\eta_1,B)$ forces $\varphi$ to hold. In particular, $(\sigma_1,B\cap A_1)$ is an extension of $q_1$ that forces $\varphi$ to hold. This is a contradiction. $\square$

Corollary. $\mathbb P_{\mathcal U}$ does not add any bounded subsets of $\kappa$.
Proof. Suppose that $\theta<\kappa$ and $q$ forces that $X$ is a name for a subset of $\theta$. For every $\alpha<\theta$, let $D_\alpha:=\{ p\in\mathbb P\mid p\text{ decides whether }\alpha\in X\}$. For every $\alpha<\theta$, let us pick $p_\alpha\in D_\alpha$ such that $c(p_\alpha)=c(q)$. Then $\{ q,p_\alpha\mid \alpha<\theta\}$ is a $c$-homogeneous set of size $<\kappa$, and hence admits a lower bound. Clearly, any such bound forces that $X$ is equal to a ground model set. $\square$

Corollary. Any set of ordinals of size $\ge\kappa$ in the extension, is covered by a ground model set of the same size.
Proof. By $\text{Chr}(\mathbb P_\mathcal U,\bot)=\kappa$, we know that $\mathbb P_\mathcal U$ has the $\kappa^+$-chain-condition, which implies the above assertion. $\square$

It follows that $\mathbb P_\mathcal U$ does not collapse cardinals. But what kind of new sets does it add?

$\blacktriangleright$ The obvious set that it adds is $g=\bigcup\{ \sigma\mid (\sigma,A)\in G\}$, where $G$ is $\mathbb P_\mathcal U$-generic. A density argument shows that $g$ is countable set such that $g\setminus A$ is finite for every $A\in\mathcal U$. In particular, $\sup(g)=\kappa$, and hence $g\cap K$ is finite for any ground model $K\in[\kappa]^{<\kappa}$.

$\blacktriangleright$ I asked Magidor for a concrete example of a subset of $\kappa^+$ in the extension which does not contain a ground model set of the same size. He gave me one under the assumption of $2^\kappa=\kappa^+$:

Example. Suppose that $\text{cf}(\mathcal U,\supseteq)=\kappa^+$. Since $\mathcal U$ is normal, we can find an enumerated family $\{ A_\alpha\mid \alpha<\kappa^+\}\subseteq\mathcal U$ which is cofinal in $(\mathcal U,\supseteq)$, and such that $\alpha<\beta<\kappa^+$ implies that $A_\beta\setminus A_\alpha$ is bounded in $\kappa$. In the generic extension, let $g:\omega\rightarrow\kappa$ denote the increasing enumeration of the generic Prikry sequence. Using $g$, we can define $F:\kappa^+\rightarrow\omega$ by letting $F(\alpha):=\min\{ n<\omega\mid g[\omega\setminus n]\subseteq A_\alpha\}$.
Let $\pi:\kappa^+\leftrightarrow\kappa^+\times\omega$ be a bijection. Towards a contradiction, suppose that $p=(\sigma,A)\in\mathbb P_{\mathcal U}$ forces that a ground model $F’\subseteq\kappa^+$ of size $\kappa^+$ is a subset of $\pi^{-1}[F]$. In particular, $\pi[F’]$ is a partial function. Fix a large enough $\alpha\in\text{dom}(\pi[F’])$ such that $A_\alpha$ is small enough to satisfy $|A\setminus A_\alpha|\ge\omega$.  Then pick $\eta\in[A\setminus A_\alpha]^{\pi[F’](\alpha)+1}$, and consider $q=(\sigma\cup\eta,A\setminus\max(\eta)+1)$. Then $q$ is an extension of $p$ that forces that $F(\alpha)>n=\pi[F’](\alpha)$. This is a contradiction. $\square$

Update: note that the above argument moreover entails (assuming, e.g., $2^\kappa=\kappa^+$) that every ground model stationary set $S\subseteq\kappa^+$, has a stationary subset $T\subseteq S$ in the extension, for which no ground model set of size $\kappa^+$ is a subset of $T$.

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

16 Responses to Prikry Forcing

  1. Mohammad says:

    Dear Assaf,
    The arguments are really interesting.
    I am always surprised, when I see a topic about Prirky type forcings.

  2. Mohammad says:

    The following might be useful:

    Kimchi, Yechiel M. “GENERALIZING PRIKRY FORCING AND PARTITION RELATIONS.” Proceedings of the Israel Mathematical Union Conference: Tel Aviv, 1988. Israel Mathematical Union, 1988.

    I have no access to it, but you may be able to obtain the notes.

    • saf says:

      Thanks a lot! I asked a colleague to borrow the book from the library and scan the relevant pages. Attached!

      Edit: Here’s a relevant video (and abstract).
      Edit 2022: See the abstract for Kimchi’s talk on the book of LC2017.

      • Yechiel M. Kimchi says:

        Please note that the results published in LC2017
        improve the uni-directional results of 1988 into equiconsitency.
        Please note that Remark(c) in the 1988 abstract has a typo in it
        – please refer to Note(2) in the LC2017 for the correct statement.

  3. Mohammad says:

    Thanks a lot for the paper.
    Do you know what the forcing notion introduced in the paper (by Kimchi himself) is and if there are any references to find it

    • saf says:

      I asked Magidor. He said that, at the end, the paper did not make it into print.
      As for the proof – it is probably best to ask him next month, when we all meet in Oberwolfach.

  4. Mohammad says:

    I think the following gives a simpler proof of Magidor’s result. In fact I think it is possible to prove something more:

    Theorem. Suppose $\kappa^{<\kappa}=\kappa, W\supseteq V, kappa$ is preserved in $W$ and $A\subseteq\kappa, A\in W\setminus V.$ Then there is $B\subseteq\kappa, B\in W$ such that no subset of $B$ of size $kappa$ is in $V$.

    To see this, fix a bijection $f\in V, f: [\kappa]^{<\kappa} \rightarrow \kappa,$ and let $B=\{ f[A\cap\alpha]: \alpha < \kappa\}.$

    • saf says:

      Hi Mohammad,
      I believe your result and Magidor’s are incomparable, as yours deals with subsets of $\kappa$, while Magidor’s with subsets of $\kappa^+$.

      • Mohammad says:

        My result is in general; for the Magidor case, take $kappa^+,$ and note that as he assumes $2^kappa=kappa^+,$ so we have $(kappa^+)^{<kappa^+}=kappa^+.$ So if we have a subset of $kappa^+$ of size $kappa^+$ in the Prikry extension, then by the above, we have one which has no ground model subset of the same size.

    • Mohammad says:

      I realized that the above argument works when every bounded subset of $\kappa$ is in $V$.

      So the above argument does not work for your case above (Magidor’s example).

  5. Mohammad says:

    Dear Assaf, I have a suggestion: Why not adding your really nice written notes in your blog (https://blog.assafrinot.com/?page_id=1544), into your paper “surprisingly short”.

    • saf says:

      Thanks, Mohammad. While I agree that PDF layout is much nicer than that of a weblog, I find it more convenient to write+include hyperlinks+maintain/update these short pieces on my weblog, than on a compiled PDF file.

  6. Mohammad says:

    The following paper by Gitik is related to Magidor’s theorem stated above:

    On density of old sets in Prikry type extensions

    http://www.math.tau.ac.il/~gitik/densityoldsets.pdf

Leave a Reply

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