Prikry Forcing

Posted on October 19, 2012 by Assaf Rinot in categories: Blog, Expository.

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

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

$σ \in [κ]^{< ω}$ , and
$A \in U$ with $max (σ) < min (A)$ .

$▸$ A condition $(σ_{2}, A_{2})$ extends $(σ_{1}, A_{1})$ iff $A_{2} \subseteq A_{1}$ and $σ_{2} ∖ σ_{1} \subseteq A_{1}$ . That is, we are allowed to shrink the $A$ -part, and allowed to end-extend $σ$ by adding to it finitely many elements from $A$ .

Let us point out that $Chr (P_{U}, ⊥) \geq κ$ :
Suppose not, as witnessed by some chromatic coloring $c : P_{U} \to λ$ , with $λ < κ$ . Define $f : [κ]^{2} \to λ$ , by letting $f (α, β) := c (⟨ α, β ⟩, κ)$ . Then, by the Erdos-Rado theorem, there exists an infinite set $A$ (indeed, a set of size $λ^{+}$ ), for which $f ↾ [A]^{2}$ is constant. Let $α < β < γ$ be elements of $A$ . Then $c (⟨ α, β ⟩, κ) = f (α, β) = f (α, γ) = c (⟨ α, γ ⟩, κ)$ , contradicting the fact that $(⟨ α, β ⟩, κ) ⊥ (⟨ α, γ ⟩, κ)$ .

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

The Prikry property. There exists a chromatic coloring $c : P_{U} \to κ$ such that:

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

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

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

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

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

$▸$ The obvious set that it adds is $g = ⋃ {σ ∣ (σ, A) \in G}$ , where $G$ is $P_{U}$ -generic. A density argument shows that $g$ is countable set such that $g ∖ A$ is finite for every $A \in U$ . In particular, $sup (g) = κ$ , and hence $g \cap K$ is finite for any ground model $K \in [κ]^{< κ}$ .

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

Example. Suppose that $cf (U, \supseteq) = κ^{+}$ . Since $U$ is normal, we can find an enumerated family ${A_{α} ∣ α < κ^{+}} \subseteq U$ which is cofinal in $(U, \supseteq)$ , and such that $α < β < κ^{+}$ implies that $A_{β} ∖ A_{α}$ is bounded in $κ$ . In the generic extension, let $g : ω \to κ$ denote the increasing enumeration of the generic Prikry sequence. Using $g$ , we can define $F : κ^{+} \to ω$ by letting $F (α) := min {n < ω ∣ g [ω ∖ n] \subseteq A_{α}}$ .
Let $π : κ^{+} \leftrightarrow κ^{+} \times ω$ be a bijection. Towards a contradiction, suppose that $p = (σ, A) \in P_{U}$ forces that a ground model $F^{'} \subseteq κ^{+}$ of size $κ^{+}$ is a subset of $π^{- 1} [F]$ . In particular, $π [F^{'}]$ is a partial function. Fix a large enough $α \in dom (π [F^{'}])$ such that $A_{α}$ is small enough to satisfy $| A ∖ A_{α} | \geq ω$ . Then pick $η \in [A ∖ A_{α}]^{π [F^{'}] (α) + 1}$ , and consider $q = (σ \cup η, A ∖ max (η) + 1)$ . Then $q$ is an extension of $p$ that forces that $F (α) > n = π [F^{'}] (α)$ . This is a contradiction.

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

This entry was posted in Blog, Expository and tagged Prikry-type forcing. Bookmark the permalink.

17 Responses to Prikry Forcing

Mohammad says:

October 31, 2013 at 1:35 am

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

Reply
- saf says:
  
  October 31, 2013 at 3:52 pm
  
  Thank you, Mohammad!
  I wonder whether the perspective of negative partition relations sheds new light on the Prikry property?
  
  Reply
Mohammad says:

November 1, 2013 at 3:29 am

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.

Reply
- saf says:
  
  November 10, 2013 at 10:28 am
  
  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.
  
  Reply
  - Yechiel M. Kimchi says:
    
    May 22, 2022 at 9:03 pm
    
    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.
    
    Reply
Mohammad says:

November 28, 2013 at 2:55 am

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

Reply
- saf says:
  
  December 21, 2013 at 12:39 pm
  
  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.
  
  Reply
Mohammad says:

January 17, 2015 at 5:47 am

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 $κ^{< κ} = κ, W \supseteq V, k a p p a$ is preserved in $W$ and $A \subseteq κ, A \in W ∖ V .$ Then there is $B \subseteq κ, B \in W$ such that no subset of $B$ of size $k a p p a$ is in $V$ .

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

Reply
- saf says:
  
  January 18, 2015 at 11:44 am
  
  Hi Mohammad,
  I believe your result and Magidor’s are incomparable, as yours deals with subsets of $κ$ , while Magidor’s with subsets of $κ^{+}$ .
  
  Reply
  - Mohammad says:
    
    January 18, 2015 at 11:22 pm
    
    My result is in general; for the Magidor case, take $k a p p a^{+},$ and note that as he assumes $2^{k} a p p a = k a p p a^{+},$ so we have $(k a p p a^{+})^{< k a p p a^{+}} = k a p p a^{+} .$ So if we have a subset of $k a p p a^{+}$ of size $k a p p a^{+}$ in the Prikry extension, then by the above, we have one which has no ground model subset of the same size.
    
    Reply
- Mohammad says:
  
  February 11, 2015 at 1:46 pm
  
  I realized that the above argument works when every bounded subset of $κ$ is in $V$ .
  
  So the above argument does not work for your case above (Magidor’s example).
  
  Reply
  - saf says:
    
    February 11, 2015 at 2:30 pm
    
    that’s right. thanks for the update!
    
    Reply
Mohammad says:

January 17, 2015 at 5:53 am

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”.

Reply
- saf says:
  
  January 18, 2015 at 11:50 am
  
  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.
  
  Reply
Mohammad says:

May 6, 2017 at 2:40 am

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

Reply
- saf says:
  
  May 6, 2017 at 3:14 am
  
  Thanks a lot, Mohammad!
  
  Reply
- Tom B. says:
  
  November 4, 2024 at 4:09 am
  
  Dear Mohammad and Assaf,
  
  I’m sorry for the 7-year delay, I just came across this post.
  
  In relation to Gitik’s paper, it turns out that the property of sets in the generic extension of certain cardinality containing ground model sets of the same cardinality is fully characterized by a pretty simple combinatorial property of the ultrafilter we use for the Prikry forcing. The so-called Galvin property.
  
  Def. Let U be an ultrafilter on \kappa. Gal(U,\mu,\lambda) holds if any collection of \lambda many elements in U contains a subcollection of size \mu whose intersection is in U.
  
  The result is more general in the following sense:
  Gal(U,\mu,\lambda) characterizes the situation where every set of ordinals of size \lambda in the U-Prikry extension V[G] contains a ground model set of size \mu. This is proven in my paper with Alejandro Poveda and Shimon Garti- “negating the Galvin property” (one of the directions is a slight modification of the argument from Gitik’s paper mentioned above):
  
  https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/jlms.12743
  
  see theorem 4.10 (there is a typo there- the assumption that U is normal is redundant)
  
  Now under 2^\kappa=\kappa^{+} it is known that Gal(U,\kappa^+,\kappa^+) must fail (this is a result of Kanamori from the 70’s). A more general result which I recently proved is that Gal(U,cf(Ch(U)),cf(Ch(U)) must fail where Ch(U) is the minimal size of a base for U (if 2^\kappa=\kappa^+ the ch(Ch(U))=\kappa^+). So you can always find a set of size cf(Ch(U)) in V[G] that does not contain a ground model set of size cf(Ch(U)).
  
  Also for Gal(U,\kappa^+,\kappa^+) to hold we need more than o(\kappa)=\kappa^{++} (which is the naive lower bound as we must violate GCH at a measurable according to Kanamori (or Magidor’s example))
  
  Reply

Prikry Forcing

17 Responses to Prikry Forcing

Leave a Reply to Yechiel M. Kimchi Cancel reply

Archives

Keywords

Set Theory Colloquium

Friends’ Blogs

Recent Comments