tag:blogger.com,1999:blog-91238399777052749132018-05-27T18:37:27.155-07:00Games, Sets, Math!Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.comBlogger34125tag:blogger.com,1999:blog-9123839977705274913.post-60637587418249917172018-05-08T14:32:00.001-07:002018-05-08T14:38:09.183-07:00History at the BGU awards ceremony<div class="" data-block="true" data-editor="f41tq" data-offset-key="bsvbb-0-0" style="color: #1d2129; white-space: pre-wrap;"><div class="_1mf _1mj" data-offset-key="bsvbb-0-0" style="direction: ltr; font-family: inherit; position: relative;"><span data-offset-key="bsvbb-0-0" style="font-family: inherit;">At the BGU department awards ceremony, a certain name appeared with spooky regularity, like subtle clues in a novel.</span><br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="font-size: 14px; margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-JD8z8OFzfik/WvIW-In_6YI/AAAAAAAAA6o/dB0aI5WK8UYnWakWwizRpFG6MlDS-1RRwCLcBGAs/s1600/sakurai.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="325" data-original-width="544" height="119" src="https://4.bp.blogspot.com/-JD8z8OFzfik/WvIW-In_6YI/AAAAAAAAA6o/dB0aI5WK8UYnWakWwizRpFG6MlDS-1RRwCLcBGAs/s200/sakurai.png" width="200" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Profs. Miriam Cohen and Daniel Sternheimer at the ceremony in 2016.</td></tr></tbody></table></div><div class="_1mf _1mj" data-offset-key="bsvbb-0-0" style="direction: ltr; font-family: inherit; position: relative;"><span data-offset-key="bsvbb-0-0" style="font-family: inherit;">This figure was mentioned in various connections by mathematicians working in different countries---Israel, France, Japan, and Belgium---and in different areas. He was a friend, a colleague, and an advisor. </span><span style="font-family: inherit;">And the truth turns out to be even more interesting than the imagination. A "sabra bull in a china shop", Moshe Flato was also an Air Force lieutenant who worked on Israel's nuclear program, an outstanding pianist trained by Daniel Barenboim's mother, and a first-rate mathematician and physicist.</span></div></div><div class="" data-block="true" data-editor="f41tq" data-offset-key="bat28-0-0" style="color: #1d2129; white-space: pre-wrap;"><div class="_1mf _1mj" data-offset-key="bat28-0-0" style="direction: ltr; font-family: inherit; position: relative;"><span data-offset-key="bat28-0-0" style="font-family: inherit;"><a href="http://www-groups.dcs.st-and.ac.uk/history/Biographies/Flato.html">http://www-groups.dcs.st-and.ac.uk/history/Biographies/Flato.html</a></span></div></div>Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-3410373418240921842017-12-03T06:41:00.000-08:002017-12-13T06:31:21.830-08:00Balogh's small Dowker space, part 2We are <a href="http://billset.blogspot.co.il/2017/12/baloghs-small-dowker-space-part-1.html" target="_blank">continuing</a> the construction of Balogh's Dowker space of size continuum. From the paper, he says:<br /><div><br /></div><blockquote class="tr_bq">"The heart of the proof of Theorem 1.1 is the following combinatorial lemma."</blockquote> <i>Lemma 1.2 </i>[<a href="http://www.ams.org/journals/proc/1996-124-08/S0002-9939-96-03610-6/S0002-9939-96-03610-6.pdf" target="_blank">Balogh</a>] Let $\lambda=2^{\mathfrak{c}}$, and let $\langle c_\xi:\xi<\lambda\rangle$ be a one-to-one enumeration of ${}^\mathfrak{c}2$. Then there is a sequence $\langle d_\xi:\xi<\lambda\rangle$ of functions $d_\xi:\mathfrak{c}\rightarrow 2$ in such a way that for every $g:\mathfrak{c}\rightarrow [\lambda]^{<\omega}$, $f:\mathfrak{c}\rightarrow \omega$ and $h:\mathfrak{c}\rightarrow [\mathfrak{c}]^{<\omega}$, there are $\alpha<\beta$ in $\mathfrak{c}$ such that $f(\alpha)=f(\beta)$, $\beta\not\in h(\alpha)$ and for every $\xi\in g(\alpha)$, $c_\xi(\alpha)=d_\xi(\beta)$.<br /><br /><br /><h2>1 Explanation</h2><br />Quite a lot to take in! But let's break down how it works, given that we know we want to construct a system of filters satisfying $(*)$ and $(**)$ from last time.<br /><br />First $(**)$: For any function $f:X\rightarrow \omega$ and any assignment $\alpha\mapsto A_\alpha\in \mathcal{F}_\alpha$, there are $\alpha\neq \beta$ so that $f(\alpha)=f(\beta)$ and $\beta\in A_\alpha$.<br /><br />This is roughly what is expressed by Lemma 1.2. But we don't know how to build the filters yet.<br /><br />We want to build them to satisfy $(*)$: For every $A\subseteq \mathfrak{c}$ there exists $B\subseteq \mathfrak{c}$ such that $B\in \mathcal{F}_\alpha \textrm{ if }\alpha\in A$ and $\mathfrak{c}\setminus B\in \mathcal{F}_\alpha \textrm{ if }\alpha\not\in A$.<br /><div><br />Think of the sequence $\langle c_\xi:\xi<\lambda \rangle$ as enumerating the characteristic functions of all possible $A$. For each $A$, we will find a set $B$ as in $(*)$; its characteristic function is $d_\xi$.<br /><br />We will use the $d_\xi$'s to generate our filters $\mathcal{F}_\alpha$. So for each $\xi$, $\{\beta:d(\beta)=1\}\in \mathcal{F}_\alpha$ if $c_\xi(\alpha)=1$ and $\{\beta:d(\beta)=0\}\in \mathcal{F}_\alpha$ if $c_\xi(\alpha)=0$.<br /><br />What else has to be in the filter? We want to be able to take finite intersections of the sets given by $d_\xi$ or complement (depending on which side makes it into the filter). This is expressed by $g$. Also, the filter will contain all cofinite subsets of $\mathfrak{c}$, a necessary condition for neighborhood filters in a space where points are closed. This is expressed by $h$.<br /><br />So Lemma 1.2 succintly expresses $(**)$ for filters satisfying $(*)$!<br /><br /><br /><h2>2 Proof of Lemma 1.2</h2><h3>Basic motivations</h3>This section can be skipped if you are familiar with the use of elementary submodel arguments.<br /><br />If we didn't care about the part involving the $d_\xi$'s the rest is very easy to arrange. By a standard argument, there is a closed unbounded set of $\beta<\mathfrak{c}$ closed under the function $h$; that is, for every $\alpha<\beta$, $h(\alpha)\subseteq \beta$. There is also a closed unbounded set of $\beta$ so that for every $n$ with $f^{-1}[n]$ unbounded, $f^{-1}[n]\cap \beta$ is unbounded in $\beta$. We will do similar, but more sophisticated arguments using the method of elementary submodels.<br /><br />Let $\theta$ be a large enough regular cardinal ($(2^{2^{\mathfrak{c}}})^+$ suffices). One of the basic ideas of the elementary submodel method is that if $N\prec H(\theta)$, $N$ countable, and $\beta<\mathfrak{c}$ is greater than $\sup(N\cap \mathfrak{c})$ (an ordinal of countable cofinality), then formulas true of $\beta$ reflect to unboundedly many $\alpha$ in $N\cap\mathfrak{c}$. This is another way of stating what we did with clubs in the last paragraph.<br /><br />But this idea is a bit more powerful. Suppose that we have $\beta$ and $N$ as above. Then there are unboundedly many $\alpha\in N\cap\mathfrak{c}$ which satisfy the desired properties for $f$ and $h$. Even more crucially, we can reflect some properties of $g(\beta)$, $d_\xi(\beta)$, and $c_\xi(\beta)$ down to these $\alpha$.<br /><br />But we can't reflect all of those properties down, since there are $\lambda$ many $\xi$ to consider and not all of them will be in $N$, and also $g(\beta)$ is some subset of $\lambda$ that may not be in $N$. But we will reflect enough of this information down, given by what happens inside some smaller countable elementary submodel $M\in N$.<br /><br />So we know what happens inside this $M$. But there is a part outside of $M$ as well. This, we will handle by knowing that there are many reflections---so many that we will be able to guess in advance what happens on at least one of them.<br /><br />That's the basic idea, but we need to make sure the construction can be carried out in $\mathfrak{c}$ many steps, while we are constructing $\lambda$-many of these $d_\xi$. The construction outlined above depends in part on the choice of submodels, but not on the full information of $M$ and $N$---we shall see that there are only $\mathfrak{c}$ many choices for the crucial information here, and the construction is in some sense canonical. That is part of the magic of this technique.<br /><br /><h3>Definition of the d's</h3><div>We have the motivation in mind now. We will enumerate <i>control triples</i> $\langle (A_\beta,B_\beta,u_\beta):\beta<\mathfrak{c}\rangle$, which are ordered triples $(A,B,u)$ that satisfy the following properties:</div><div><ol><li> $A\in [\mathfrak{c}]^\omega$, $B\in [{}^A2]^{\le \omega}$,</li><li>$u$ is a function with $\mathrm{dom}(u)\in[A]^\omega$,</li><li>for every $\alpha\in\mathrm{dom}(u), u(\alpha)\in [{}^A2\setminus B]^{<\omega}$,</li><li>(disjoint images) if $\alpha\neq \beta$ in $\mathrm{dom}(u)$, then $u(\alpha)\cap u(\beta)=\emptyset$.</li></ol><div>Furthermore, let us ensure in the enumeration that $\beta>\sup A_\beta$.</div><div><br /></div><div>From the sketch above, $A$ corresponds to $N\cap \mathfrak{c}$, $B$ corresponds to the information we need from $M$, and $u$ captures the information that's not in $M$. But there are only $\mathfrak{c}$ such triples!</div></div><br />Suppose now that $\xi<\lambda$. We will define $d_\xi$. For each $\beta<\mathfrak{c}$, there are three cases.<br /><br /><ol><li>If $c_\xi\upharpoonright A_\beta\in B_\beta$, then let $d_\xi(\beta)=c_\xi(\beta)$. </li><li>If $c_\xi\upharpoonright A_\beta\in u_\beta(\alpha)$ for some $\alpha\in \mathrm{dom}(u_\beta)$, then let $d_\xi(\beta)=c_\xi(\alpha)$.</li><li>Otherwise, set $d_\xi(\beta)=0$.</li></ol><div>Intuitively, Case 1 corresponds to the case when $\xi$ is in the part which is controlled by $M$, and Case 2 to when $u$ captures the information outside of $M$ of a reflected $\alpha$. Note that in Case 2, $c_\xi\upharpoonright A_\beta\not\in B_\beta$, and $\alpha$ is chosen uniquely by the restrictions on $u$ in the definition of a control triple.</div><div><br /></div><h3>Final proof</h3><div>We will show that the sequence of $d_\xi$ we have defined above works. Let $f,g,h$ be functions as in the statement of Lemma 1.2. We will produce the required $\alpha,\beta$.</div><div><br /></div><div>Let $M\in N$ be elementary submodels of $H(\theta)$ containing $\langle c_\xi:\xi<\lambda\rangle, \langle d_\xi:\xi<\lambda\rangle, f,g,h$. Let $A=\mathfrak{c}\cap N$ and $B=\{c_\xi\upharpoonright A:\xi\in \lambda\cap M\}$.</div><div><br /></div><div>We will construct $u:A\rightarrow[{}^A2\setminus B]^{<\omega}$ satisfying the requirements of the control triple such that whenever $v\in N$ is an infinite partial function $\mathfrak{c}\rightarrow [\lambda\setminus M]^{<\omega}$ and $\alpha\neq \alpha'$ in $\mathrm{dom}(v)$ implies that $v(\alpha)\cap v(\alpha')=\emptyset$, then there is $\alpha\in\mathrm{dom}(u)\cap\mathrm{dom}(v)$ such that </div><div>$$u(\alpha)=\{c_\xi\upharpoonright A:\xi\in v(\alpha)\}.$$</div><div>Basically, $u$ agrees with $v$ on at least one point of its domain for any $v$ of the right shape. And here, agreement actually means $u(\alpha)=\{c_\xi\upharpoonright A:\xi\in v(\alpha)\}$, since $u$ cannot actually take the ordinals less than $\lambda$ in its range, as we were careful to only use $\mathfrak{c}$-many control triples.</div><div><br /></div><div>This $u$ is easy to construct. Just enumerate the countably many such $v\in N$ and construct $u^*:\mathfrak{c}\rightarrow [\lambda\setminus M]^{<\omega}$ so that the disjoint images property holds. Then get $u$ by taking restrictions of the $c_\xi$ to $A$. The only thing that requires some argument is to make sure that by taking the restrictions, we do not accidentally break the disjoint images property for $u$. But we will not, since the relevant $\xi$ are in $N$ and if $\xi\neq\xi'$ then this is witnessed by something in $A=N\cap\mathfrak{c}$. </div><br /><br />Now pick $\beta$ so that $\langle A_\beta,B_\beta,u_\beta\rangle=\langle A,B,u\rangle$. Say that $\gamma$ <i>reflects</i> $\beta$ if<br /><br /><ol><li>$f(\gamma)=f(\beta)$,</li><li>$g(\gamma)\cap M=g(\beta)\cap M$,</li><li>for every $\xi\in g(\gamma)\cap M$, $c_\xi(\gamma)=c_\xi(\beta)$.</li></ol><div>Find a maximal $D$ which consists of $\gamma$ reflecting $\beta$ so that $\langle g(\gamma):\gamma\in D\rangle$ forms a $\Delta$-system with root $r:=g(\beta)\cap M$. Choose $D$ in $M$, possible since the definition of reflection only used parameters in $M$. This $D$ is uncountable since otherwise it would be a subset of $M$, but $\beta$ could be then be added to it, contradicting maximality. So there is also an infinite set $H$ of $\gamma\in D\cap N$ so that $g(\gamma)\setminus r$ is disjoint from the countable set $\lambda\cap M$.</div><br /><br />Now define $v:H\rightarrow [\lambda\setminus M]^{<\omega}$ by $v(\gamma)=g(\gamma)\setminus r$. So $v\in N$ and there is $\alpha\in \mathrm{dom}(u)\cap\mathrm{dom}(v)$ with $u(\alpha)=\{c_\xi\upharpoonright A:\xi\in v(\alpha)\}$. This is the $\alpha$ we want.<br /><br />Let's check: since $\alpha$ reflects $\beta$, $f(\alpha)=f(\beta)$. Since $\alpha\in N$, $h(\alpha)\subseteq N$. But $\beta>\sup(A_\beta)$, so $\beta\not\in h(\alpha)$. Finally, if $\xi\in g(\alpha)$, there are two cases depending on if $\xi$ is in the root of the $\Delta$-system or not. In the first case, $\xi\in r$, and then we defined $d_\xi(\beta)=c_\xi(\beta)=c_\xi(\alpha)$. In the second, $c_\xi\upharpoonright A\in u_\beta(\alpha)$, so we directly defined $d_\xi(\beta)=c_\xi(\alpha)$.<br /><br /><br />(These are notes from a seminar given at Bar-Ilan University on December 4, 2017.)<br /><br /></div>Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-28258192915728201932017-12-03T05:55:00.003-08:002017-12-05T01:03:44.540-08:00Balogh's small Dowker space, part 1<div>A <i>Dowker space </i>is a normal space which is not countably paracompact. Here, a (Hausdorff) space $X$ is <i>normal </i>if for every pair of disjoint closed sets $H,K$, there exist disjoint open sets $U,V$ with $H\subseteq U$ and $K\subseteq V$. Normality is, according to M.E. Rudin, the boundary where point-set topology changes from analysis to set theory. </div><div><br /></div><div>A space $X$ is<i> countably paracompact </i>if for every $\subseteq$-increasing sequence of open sets $\langle G_n:n<\omega\rangle$ with $\bigcup_n G_n=X$, there exist closed sets $H_n\subseteq G_n$ so that $\bigcup_n H_n=X$. An interesting history of the concept of paracompactness can be found in the <i>Encyclopedia of General Topology.</i></div><div><i><br /></i></div><div>It turns out that Dowker spaces are the spaces whose normality is not preserved by product with compact metric spaces. See <a href="https://dantopology.wordpress.com/tag/dowker-space/" target="_blank">Dan Ma's topology blog</a> for more information about Dowker spaces and all of the topological concepts considered here.</div><div><br /></div><div>Dowker spaces are considered to be quite rare, and the first ZFC example was due to M.E. Rudin in 1971. In 1996, Zoltan Balogh published an <a href="http://www.ams.org/journals/proc/1996-124-08/S0002-9939-96-03610-6/S0002-9939-96-03610-6.pdf" target="_blank">example</a> of a Dowker space of size continuum in ZFC. The problem of whether there exists a Dowker space of size $\aleph_1$ is still open.</div><div><br /></div><div>Balogh's example was based off an earlier <a href="https://www.jstor.org/stable/2048227" target="_blank">example</a> of Watson which used strongly compact cardinals, together with an earlier argument of Rudin using the submodel method. He was able to use the techniques applied in this Dowker space construction towards other Dowker spaces and the solutions of the second and third Morita conjectures. This post gives a carefully motivated presentation of Balogh's proof.</div><div><br /></div><h2><b>1 Basic construction</b></h2><div><br /></div><div>We start the construction of $X$ with an increasing sequence of open sets $\langle G_n:n<\omega\rangle$ witnessing the failure of paracompactness. So the underlying set of $X$ is $\omega\times\mathfrak{c}$, and we define $G_n=(n+1)\times\mathfrak{c}$. We will also consider the levels of the space, $L_n=\{n\}\times\mathfrak{c}$.</div><div><br /></div><div>The levels $L_n$ will be relatively discrete, which helps in the normality proof later. The set of open neighborhoods of a fixed point $(n,\alpha)$ forms a filter. If $n=0$, a neighborhood base for $(n,\alpha)$ is just the singleton. If $n>0$, the filter concentrates on $\{(n,\alpha\}\cup G_{n-1}$. Following Watson's example, we will define a filter $\mathcal{F}_{(n,\alpha)}$ on $G_{n-1}$. Then, a set $U$ is open if and only if for every $(n,\alpha)\in U$, there is some $A\in \mathcal{F}_{(n,\alpha)}$ so that $A\subseteq U$.</div><div><br /></div><div>Motivated by the normality argument in Watson's paper (which he credits to Rudin), we will end up working on consecutive pairs of levels. So the filter $\mathcal{F}_{(n,\alpha)}$ will be expressed as a filter $\mathcal{F}_\alpha$ on $\mathfrak{c}$ which does not depend on $n$. The filter will contain all cofinite subsets of $\mathfrak{c}$, which is necessary in a space where points are closed.</div><div><br /></div><div>Let us find the properties of this filter system which we need to make $X$ Dowker. </div><div><br /></div><div><br /></div><h2><b>2 Normality</b></h2><div>Let us try to get normality. The first level $G_0$ is relatively normal, since it has the discrete topology. If we consider the first two levels, however, we need to separate arbitrary disjoint sets $A_0,A_1\subseteq L_1$ by disjoint open sets. We may as well assume that $A_1$ is the complement of $A_0$ in its level. In total, we are looking for: </div><div><br /></div><div>$$(*) \textrm{For every }A\subseteq \mathfrak{c}, \textrm{ there exists } B \subseteq \mathfrak{c} \textrm{ such that }$$</div><div>$$B\in \mathcal{F}_\alpha \textrm{ if }\alpha\in A,$$</div><div>$$\mathfrak{c}\setminus B\in \mathcal{F}_\alpha \textrm{ if }\alpha\not\in A.$$</div><div><br /></div><div>For the next few claims, assume $(*)$. We will show that $X$ defined as above is normal.</div><div><br /></div><div>First, we show this for subsets of single levels.</div><div><br /></div><div><b>Claim 1. </b>Suppose that $m\le n$ and $H\subseteq L_n$ and $K\subseteq L_m$ have disjoint closures. Then there are disjoint open sets $U,V$ separating them ($H\subseteq U$ and $K\subseteq V$). Moreover, we can arrange so that $L_n\setminus H\subseteq K$.</div><div><br /></div><div><i>Proof of Claim 1</i>: Using $(*)$ repeatedly, let $U',V'$ be disjoint open sets so that $L_m\setminus K\subseteq U'$ and $K\cap L_m\subseteq V'$. Then take $U=U'\cup(X\setminus (G_m\cup \bar{K}))$ and $V=V'$. $U$ is open since $U'$ and $X\setminus \bar{K}$ are open sets which are spliced together at a single level $m$, and $U'\cap L_m=X\setminus K=(X\setminus \bar{K})\cap L_m$. Clearly $K\subseteq V$, and $H\subseteq U$ since $H\cap \bar{K}=\emptyset$. $\square$</div><div><br /></div><div>Now we can separate a subset of a single level from an arbitrary closed set.<b> </b>Suppose that $H,K$ are disjoint closed subsets of $X$. By taking only finite unions and intersections from the sets produced from Claim 1, we can show that there are disjoint open $U'_n,V'_n$ and disjoint open $U''_n,V''_n$, all subsets of $G_n$, so that </div><div><ul><li>$H\cap L_n\subseteq U'_n$, $K\cap G_n\subseteq V'_n$, and $L_n\setminus H\subseteq V'_n$.</li><li>$H\cap G_n\subseteq U''_n$, $K\cap L_n\subseteq V''_n$, and $L_n\setminus K\subseteq U''_n$.</li></ul><div>Finally, take $$U_n:=\bigcup_n (U'_n\setminus \bigcup_{k\le n}\mathrm{cl}(V''_k))$$ and $$V_n:=\bigcup_n (V''_n\setminus \bigcup_{k\le n}\mathrm{cl}(U'_k)).$$ </div></div><div>These sets are clearly open, and disjoint by the subtraction done at each step. </div><div><br /></div><div>For each $n$, $H\cap L_n\subseteq U'_n\setminus \bigcup_{k\le n}\mathrm{cl}(V''_k)$ and $K\cap L_n\subseteq V''_n\setminus \bigcup_{k\le n}\mathrm{cl}(U'_k)$. This is because $V^*_n:=V'_n\cup(X\setminus (G_n\cup H))$ and $U^*_n:=U''_n\cup(X\setminus (G_n\cup K))$ are open, by the splicing argument. Furthermore, we have $K\subseteq V^*_n$ and $H\subseteq U^*_n$ and $V^*_n\cap U'_n=U^*_n\cap V''_n =\emptyset$. </div><div><br /></div><div>So we have reduced normality to the property $(*)$ of the filter system.</div><div><br /></div><div><i>Remark</i>: In fact, the proof shows that $X$ built from a system satisfying $(*)$ is hereditarily normal.</div><h2>3 Non countable paracompactness</h2><div>To get non-countable paracompactness, we need to show that every sequence of closed sets $\langle H_n:n<\omega\rangle$ with $H_n\subseteq G_n$ cannot have union $X$. The levels of each $F_n$ are small in the following sense. $H_n\cap L_n$ must be measure 0 according to $\mathcal{F}_\alpha$ (that is, the complement is in the filter) for each $\alpha\in\mathfrak{c}$. Otherwise, if $H_n\cap L_n$ is positive measure according to $\mathcal{F}_\alpha$, then $(n+1,\alpha)$ is in its closure, contradicting that $H_n\subseteq G_n$ closed. For each $n$, let us define the ideal $\mathcal{I}^1$ to be the ideal of sets which are measure 0 according to $\mathcal{F}_\alpha$ for every $\alpha\in\mathfrak{c}$.</div><div><br /></div><div>Now if $n>0$, $H_n\cap L_{n-1}$ is measure 0 according to $\mathcal{F}_\alpha$ for all $\alpha$ except for a set in $\mathcal{I}^1$. Let $\mathcal{I}^2$ be the ideal of sets which have this property, and recursively define $\mathcal{I}^m$ for every $m<\omega$. Let $\mathcal{I}$ be the $\sigma$-complete ideal generated by $\bigcup_{m<\omega} \mathcal{I}^m$. For technical reasons, let $\mathcal{I}^0=\{\emptyset\}$. </div><div><br /></div><div>We will be done if we can show that $\mathcal{I}$ is proper, since $\{\alpha:(0,\alpha)\in H_n\cap L_0\}\in\mathcal{I}$ is in $\mathcal{I}$.</div><div><br /></div><div>Suppose otherwise. Then there is a partition of $\mathfrak{c}$ into countably many sets, each in $\mathcal{I}^m$ for some $m$. By partitioning further, we can assume for each class $C$ of the partition, $C\in \mathcal{I}_m$ is witnessed by a set $D\in \mathcal{I}_{m-1}$, so that $C\cap D=\emptyset$ and $C\in \mathcal{F}_\alpha$ for all $\alpha\not\in D$ (any set in $\mathcal{I}_m$ has such a $D$, and if $C\cap D$ is not empty, then it is in $\mathcal{I}_{m-1}$ and we can subtract off this part; repeat the procedure finitely many times to get the further partitioning). Now to each $\alpha\in C$, we can associate a set $A_\alpha \in \mathcal{F}_\alpha$ which is disjoint from $C$.</div><div><br /></div><div>We want to ensure that there are no such partitions. So we want:</div><div><br /></div><div>$(**)$ For any function $f:X\rightarrow \omega$ and any assignment $\alpha\mapsto A_\alpha\in \mathcal{F}_\alpha$, there are $\alpha\neq \beta$ so that $f(\alpha)=f(\beta)$ and $\beta\in A_\alpha$.</div><div><br /></div><div>Then, $\alpha$ and $\beta$ will be in the same class $C$, but we will have $\beta\in A_\alpha$, contradicting that $A_\alpha$ was supposed to be disjoint from $C$.</div><div><br /></div><div>We have reduced non countable paracompactness to $(**)$. Next time we will see how to get $(*)$ and $(**)$.<br /><br />Note that in this part, $\mathfrak{c}$ here can be replaced by any infinite cardinal $\kappa$.<br /><br />We will continue Balogh's proof in <a href="http://billset.blogspot.co.il/2017/12/baloghs-small-dowker-space-part-2.html" target="_blank">Part 2</a>.</div><div><br /></div><div>(These are notes from a seminar given at Bar-Ilan University on November 27, 2017.)</div>Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-73036039315096925722017-11-22T23:26:00.003-08:002017-11-22T23:26:39.824-08:00New material comingI have been in Israel at Ben-Gurion University for the past year (and plan to stay here for one more year), and I'm working on some new things. Look forward to more posts soon!Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-47862340643859004572016-02-25T00:39:00.000-08:002016-02-25T00:39:46.028-08:00UCI Summer School, part 7: Sacks forcing (Brent Cody)This lecture will introduce some basic properties of Sacks forcing for uncountable inaccessible cardinals, and examine an Easton support iteration of such forcing.<div><br /></div><div>The Sacks forcing on $\omega$ adds a real of minimal constructibility degree, and crucially satisfies a fusion property. Although this was reviewed in the summer school, I'm going to omit the discussion for this post.</div><div><br /></div><div>Instead we will start with Sacks forcing on uncountable cardinals, which traces back to Kanamori (1980), where using $\diamond_\kappa$ it was shown that long products and iterations of $\mathrm{Sacks}(\kappa)$ preserve $\kappa^+$.</div><div><br /></div><div><b>Definition: </b>We say $p\subseteq 2^{<\kappa}$ is a <i>perfect $\kappa$-tree </i>if:</div><div><ol><li>If $s\in p$ and $t\subseteq s$ then $t\in p$.</li><li>If $\langle s_\alpha:\alpha<\eta\rangle$ is a sequence of nodes in $p$, then $s=\bigcup_{\alpha<\eta} s_\alpha\in p$.</li><li>For every $s\in p$ there is $t\supset s$ with $t\frown 0, t\frown 1\in p$.</li><li>Let $\mathrm{Split}(p)=\{s\in p: s\frown 0, s\frown 1\in p\}$. Then for some unique club $C(p)\subseteq \kappa$, we have $$\mathrm{Split}(p)=\{s\in p: \mathrm{length}(s)\in C(p)\}.$$</li></ol><div>$\mathrm{Sacks}(\kappa)$ is the poset of perfect $\kappa$-trees ordered by inclusion. We think of the generic subset of $\kappa$ added by $\mathrm{Sacks}(\kappa)$ as the intersection of the trees in the generic filter.</div><div><br /></div><div>The only surprising thing in the generalization is (4): splitting happens for every node on certain levels, which form a club in $\kappa$.</div></div><div><br /></div><div><i>Exercise: </i>$\mathrm{Sacks}(\kappa)$ is $<\kappa$-closed.</div><div><br /></div><div>Assume $\kappa>\omega$ is inaccessible. Then $\mathrm{Sacks}(\kappa)$ is $\kappa^{++}$-c.c. We will really only consider this case.</div><div><br /></div><div><b>Definition: </b>$\mathrm{Split}_\alpha(p)$ is the set of all nodes $s\in p$ with $\mathrm{length}(s)=\beta_\alpha$, where $\langle \beta_\alpha:\alpha<\kappa\rangle$ is an enumeration of $C(p)$, i.e., the level of $p$ at the $\alpha$th member of $C(p)$.</div><div><br /></div><div>For $p,q\in \mathrm{Sacks}(\kappa)$, write $p\le_\beta q$ iff $p\le q$ and $\mathrm{Split}_\alpha(p)=\mathrm{Split}_\alpha(q)$ for all $\alpha<\beta$.</div><div><br /></div><div>A descending sequence $\langle p_\alpha:\alpha<\kappa\rangle$ in $\mathrm{Sacks}(\kappa)$ is a <i>fusion sequence </i>if for all $\alpha<\kappa$, $p_\alpha\le_\alpha p_\alpha$.</div><div><br /></div><div><b>Lemma </b>(fusion lemma): If $\langle p_\alpha:\alpha<\kappa\rangle$ is a fusion sequence, then $p=\bigcap_{\alpha<\kappa} p_\alpha$ is a lower bound in $\mathrm{Sacks}(\kappa)$.</div><div><br /></div><div><i>Proof:</i> exercise. Hint: show that any node $p$ in the intersection is in a cofinal branch of the intersection.</div><div><br /></div><div>This important lemma affords us a kind of $\kappa^+$ closure, with the catch that we require more of our decreasing sequence. We can see this in action in the next lemma.</div><div><br /></div><div><b>Lemma: </b>$\mathrm{Sacks}(\kappa)$ preserves $\kappa^+$.</div><div><br /></div><div><i>Proof: </i>If $\dot{f}$ is the name of a function $\kappa\rightarrow \kappa^+$, then we will find $q\le p$ with $q\Vdash \mathrm{ran}(\dot{f})$ bounded. </div><div><br /></div><div>Let $p_0=p$. Given $p_\alpha$, for each $s\in \mathrm{Split}_\alpha(p_\alpha)$, let $\bar{r}^s_\alpha\le (p_\alpha)_s$ be such that $\bar{r}^s \Vdash \dot{f}(\alpha)=\eta^s_\alpha$. Here the $(p)_s$ means the subtree of $p$ of nodes compatible with $s$. </div><div><br /></div><div>Note $\bigcup\{\bar{r}^s_\alpha:s\in \mathrm{Split}_\alpha(p_\alpha)\}$ might not be a condition by the requirement on splitting levels. Let $C=\bigcap \{C(\bar{r}^s_\alpha:s\in \mathrm{Split}_\alpha(p_\alpha)\}$ and thin each $\bar{r}^s_\alpha$ to some $r^s_\alpha\le \bar{r}^s_\alpha$ with $C(r^s_\alpha)=C$.</div><div><br /></div><div>At limits $\gamma<\kappa$, let $p_\gamma=\bigcap_{\alpha<\gamma} p_\alpha$ by the fusion lemma. This defines a fusion sequence where the limit forces that the range of $f$ is bounded.</div><div><br /></div><div><i>Exercise: </i>Suppose ${}^\kappa M\subseteq M$, for an inner model $M$. Suppose $\mathrm{Sacks}(\kappa)\in M\subseteq V$. If $G$ is $V$-generic for $\mathrm{Sacks}(\kappa)$ then ${}^\kappa M[G]\subseteq M[G]$ in $V[G]$.</div><div><br /></div><div><i>Note: </i>This holds for $\kappa^+$-c.c. forcing, but $\mathrm{Sacks}(\kappa)$ is not $\kappa^+$-c.c.</div><div><br /></div><div>Now we will see what happens when we iterate these Sacks forcings with Easton support below, and at, a measurable cardinal $\kappa$. Think of this like a Sacks forcing version of the Kunen-Paris iteration, where we use the nice fusion property to replace the $\gamma^+$ closure of the factors there.</div><div><br /></div><div><b>Theorem (Friedman-Thompson 2008): </b>Assume GCH holds. Suppose $\kappa$ is measurable and let $\mathbb{P}$ be the length $\kappa+1$ Easton support iteration with $\mathbb{Q}_\gamma=\mathrm{Sacks}(\gamma)$ (computed in $V^{\mathbb{P}_\gamma}$) for $\gamma\le \kappa$ inaccessible, and $\mathbb{Q}_\gamma$ is trivial forcing otherwise. Then if $G\ast H$ is $V$-generic for $\mathbb{P}= \mathbb{P}_\kappa\ast \dot{\mathbb{Q}}_\kappa$, then every normal ultrapower lifts to $V[G\ast H]$ (and in a particularly interesting way!)</div><div><br /></div><div><i>Proof:</i> Let $j:V\rightarrow M$ be a normal ultrapower by $U\in V$. Then $j(\mathbb{P}_\kappa=\mathbb{P}_\kappa\ast \dot{\mathbb{Q}}_\kappa\ast \dot{\mathbb{P}}_{\kappa+1,j(\kappa)}$. We get the actual $\dot{\mathbb{Q}}_\kappa$ factor at the $\kappa$ step by using the $\kappa$ closure of the ultrapower.</div><div><br /></div><div>Using this closure further, and the last exercise, ${}^\kappa M[G\ast H]\subseteq M[G\ast H]$ in $V[G\ast H]$, so $M[G\ast H] \vDash \dot{\mathbb{P}}_{\kappa+1,j(\kappa)}\textrm{ is }\le \kappa-\textrm{closed.}$ So there are $\kappa^+$ maximal antichains of $\mathbb{P}_{\kappa,j(\kappa)}$ in $M[G][H]$. We can now build as usual a generic $G_{\kappa+1,j(\kappa)}\in V[G\ast H]$ for $\mathbb{P}_{\kappa+1,j(\kappa)}$ over $M[G\ast H]$. Lift to $j:V[G]\rightarrow M[j(G)]$. </div><div><br /></div><div>Now we have to lift $j$ through $\mathbb{Q}_\kappa=\mathrm{Sacks}(\kappa)$. Using the Silver method, $j``H$ has size $\kappa^+$, but the target model $M[j(G)]$ does not have this much closure.</div><div><br /></div><div>The crucial point is to just take $t:=\bigcap j``H$. We claim that $t$ is a "tuning fork": by this we mean that $t$ consists of a single branch up to the level $\kappa$, at which point it splits into two branch which are cofinal (and that's everything in $t$).</div><div><ol><li>The function $f:\kappa\rightarrow 2$ determined by $H$ is in $t$, and this is everything in $t$ below $\kappa$.</li><li>Every condition in $j``H$ splits at $\kappa$ since for each $p\in H$, $p$ splits at club many levels below $\kappa$, and therefore $j(p)$ splits at level $\kappa$. Therefore, $f\frown 0,f\frown 1\in t$.</li><li>Since $H$ is a filter, $t$ is cofinal in $j(\kappa)$.</li><li>We will argue that $t$ does not split anywhere else. Given a club $C\subseteq \kappa$, $D_C:=\{p\in \mathrm{Sacks}(\kappa): C(p)\subseteq C\}$ is dense. So there must be $p_C\in H$ so that $C(p_C)\subseteq C$. Now we have:</li></ol><div>Claim: $X=\bigcap \{j(C):C\subseteq \kappa \textrm{ club in } V[G]\}=\{\kappa\}$.</div></div><div><br /></div><div>Proof of Claim: Clearly $\kappa\in X$. For the other inclusion, suppose $\alpha\in X$, $\alpha>\kappa$. Then choose $f:\kappa\rightarrow \kappa$, $f\in V[G]$ so that $j(f)(\kappa)=\alpha$. Then let $C_f=\{\nu<\kappa: f``\nu\subseteq \nu\}$ is club, but $\alpha\not\in j(C_f)$ since $\alpha$ is not a closure point of $j(f)$ ($\kappa<\alpha$ maps to $\alpha$). This proves the claim.</div><div><br /></div><div>Let $t_0, t_1$ be the leftmost and rightmost branches through $t$, respectively. Let $K_0=\{p\in j(\mathbb{Q}_\kappa):t_0\subseteq p\}$. Clearly $j``H\subseteq K_0$.</div><div><br /></div><div>It remains to show that $K_0$ is $M[j(G)]$-generic for $j(\mathbb{Q}_\kappa)$. Let $D$ be a dense open subset of $j(\mathbb{Q}_\kappa$ in $M[j(G)]$. Then there is a sequence $\vec{D}=\langle D_\alpha:\alpha<\kappa\rangle \in V[G]$ such that $j(\vec{D})_\kappa=D$, where each $D_\alpha$ is a dense open subset of $\mathbb{Q}_\kappa$. </div><div><br /></div><div>Claim: Every condition $p\in \mathrm{Sacks}(\kappa)$ can be extended to $q_\infty \le p$ so that for every $\alpha<\kappa$ there is $\beta<\kappa$ so that for any node $s\in \mathrm{Split}_\beta(q_\infty)$, the condition $(q_\infty)_s$ meets $D_\alpha$. </div><div><br /></div><div>Proof of Claim: exercise, a fusion argument.</div><div><br /></div><div>Let $q_\infty\in H$ be as in the claim, using genericity of $H$. By elementarity, $j(q_\infty)$ has the property that at some splitting level of $j(q_\infty)$, say $\beta<j(\kappa)$, any node $s\in \mathrm{Split}_\beta(j(q_\infty))$ is such that $(j(q_\infty))_s$ meets $D$. Now we can just take $s$ to be $t_0\upharpoonright \delta_\beta$, where $\delta_\beta$ is the $\beta$th splitting level of $j(q_\infty)$.</div><div><br /></div><div>Therefore $K_0$ is generic as claimed, and it is in $V[G\ast H]$, so $j$ lifts to</div><div>$$j:V[G\ast H]\rightarrow M[j(G)\ast j(H)].$$ </div>Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-67807448446361403082016-02-19T01:37:00.000-08:002016-02-25T15:47:27.796-08:00The rearrangement inequality is everywhereRecently, I've been talking with John Susice about some elementary Olympiad-style problems. I told him that in high school I was taught that virtually every inequality problem that appeared in this setting follows from the <i>Rearrangement Inequality. </i>This states that if $x_1\le \cdots\le x_n$ and $y_1\le \cdots\le y_n$ are real numbers, then the expression<br />$$x_1 y_{\sigma(1)}+\cdots+x_n y_{\sigma(n)}$$<br />for $\sigma$ a permutation on $[n]$ is maximized when $\sigma$ is the identity permutation and minimized when $\sigma$ is the reversing permutation. To me, this neatly isolates a useful and general principle that seems kind of obvious in hindsight.<br /><br />The proof of the $n=2$ case of the inequality, which is all I'll need below, is just to expand $(x_2-x_1)(y_2-y_1)\ge 0$. This case also implies the AM-GM inequality (taking $x_1=y_1=\sqrt{a}$ and $x_2=y_2=\sqrt{b}$).<br /><br />Now sometime later, John told me an interesting problem about factoring numbers. He had a solution using a trick similar to Euler's product, but for me this was a chance to test my thesis about the rearrangement inequality:<br /><br /><b>Problem: </b>Prove that every natural number $n$ has more factors congruent to 1 (mod 4) than factors congruent to 3 (mod 4).<br /><br /><b>Solution: </b>By induction. Clearly this holds for 1 and for primes. Now suppose $n$ is composite, so write $n=pq$ where $p,q<n$. For any integer $k$, let $r_k$ denote the number of factors it has which are congruent to 1 (mod 4) and $s_k$ the number of factors congruent to 3 (mod 4).<br /><br />The product of two 1 (mod 4) numbers is still 1 (mod 4), and the product of two 3 (mod 4) numbers is 3 (mod 4). On the other hand, the product of a 1 (mod 4) and a 3 (mod 4) is a 3 (mod 4), and even factors can never be 1 or 3 (mod 4). This proves that $r_n=r_pr_q+s_ps_q$, which must be greater than $s_n=r_ps_q+r_qs_p$ by the rearrangement inequality!<br /><br /><br />Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-88505999656086162982016-02-19T01:07:00.000-08:002016-02-24T23:55:07.409-08:00UCI Summer School, part 6: the number of normal measures (Brent Cody)Sorry for the delay, loyal readers. Here is the beginning of Brent's part of the summer school.<br /><br />Assume that is consistent that there is a measurable cardinal.<br /><br />Question: How many normal measures can a measurable cardinal carry?<br /><br />Let $\mathrm{NM}(\kappa)$ denote the set of normal measures on $\kappa$. Trivially, $\#\mathrm{NM}(\kappa)\le 2^{2^\kappa}$.<br /><br />One interesting case happens in a canonical inner model.<br /><br /><b>Theorem (Kunen '71): </b>In $L[U]$, there is exactly one normal measure (on $\kappa$, the unique measurable cardinal).<br /><br />We can also realize the other extreme:<br /><br /><b>Theorem (Kunen-Paris '71): </b>There is a forcing extension in which $\#\mathrm{NM}(\kappa)=2^{2^\kappa}$.<br /><br />We will prove this one later today. In the middle, we have<br /><br /><b>Theorem (Mitchell '74): </b>It is consistent relative to a measurable $\kappa$ of order $\delta$ that $\#\mathrm{NM}(\kappa)=2^{2^\kappa}$.<br /><br />And for one case, we can lower the large cardinal assumption used.<br /><br /><b>Theorem (Apter-Cummings-Hamkins '07): </b>It is consistent relative to a measurable cardinal that that $\#\mathrm{NM}(\kappa)=\kappa^+$.<br /><br />Finally, we can do it in all cases.<br /><br /><b>Theorem (Friedman-Magidor '09): </b>Assume GCH. Suppose $\kappa$ is measurable and let $\mu\le \kappa^{++}$ be a cardinal. Then in a cofinality-preserving forcing extension, $\#\mathrm{NM}(\kappa)=\mu$.<br /><br />The goal eventually will be to show the proof of this result.<br /><br /><b>Lemma: </b>Suppose $j:V\rightarrow M$ is the ultrapower by a normal measure on $\kappa$. Let $G$ be $V$-generic for $\mathbb{P}$. Assume that in $V[G]$,<br />$$j_0:V[G]\rightarrow M[j_0(G)]$$<br />and<br />$$j_1:V[G]\rightarrow M[j_1(G)]$$<br />are elementary embeddings extending $j$. Then the following are equivalent:<br />1) $j_0=j_1$.<br />2) $j_0(G)=j_1(G)$.<br />3) The normal measure $U_0$ derived from $j_0$ is equal to the normal measure $U_1$ derived from $j_1$.<br /><br /><i>Proof: </i>Exercise.<br /><br /><b>Exercise (Levy-Solovay): </b>Show that every normal measure extends uniquely to a normal measure in any forcing extension by small forcing.<br /><br />As promised, we will now prove the Kunen-Paris Theorem.<br /><br /><b>Theorem (Kunen-Paris '71): </b>There is a forcing extension in which $\#\mathrm{NM}(\kappa)=2^{2^\kappa}$.<br /><br /><i>Proof</i>: By a preparation forcing if necessary, assume that $2^\kappa=\kappa^+$. Let $\mathbb{P}$ be the length $\kappa+1$ Easton support iteration that forces at cardinal stages $\gamma\le \kappa$ with $\mathbb{Q}_\gamma:=\mathrm{Add}(\gamma^+,1)$ (computed in the extension by $\mathbb{P}_\gamma$), trivial forcing at other stages. This is a standard way of forcing the GCH to hold below $\kappa$.<br /><br />Let $G\ast H$ be $V$-generic for $\mathbb{P}=\mathbb{P}_\kappa\ast \dot{\mathbb{Q}}_\kappa$. Let $j:V\rightarrow M$ be the ultrapower by a normal measure. Factor $j(\mathbb{P}_\kappa)\simeq \mathbb{P}_\kappa \ast \dot{\mathbb{P}}_{\kappa,j(\kappa)}$.<br /><br />Since ${}^\kappa M[G]\subseteq M[G]$ in $V[G]$ (a name exercise which uses closure under $\kappa$-sequences of $M$ in $V$), we have that in $M[G]$, $\mathbb{P}_{\kappa,j(\kappa)}$ is $\le \kappa$-closed (it is the composition of increasingly closed posets starting with $\mathbb{Q}_\kappa=\mathrm{Add}(\kappa^+,1)$.<br /><br />Furthermore, computing in $V[G]$, $\mathbb{P}_{\kappa,j(\kappa)}$ has at most $\kappa^+$ maximal antichains inside $M[G]$. since $|j(\kappa)|=\kappa^+$ by our cardinal arithmetic assumption, and $\mathbb{P}_{\kappa,j(\kappa)}$ is $j(\kappa)$-c.c. of size $j(\kappa)$ in $M[G]$. By enumerating the maximal antichains of $M[G]$ in order-type $\kappa^+$, we can meet them one by one, with the closure of the poset in $M[G]$, noticing that closure of the model $M[G]$ gives that the proper initial segments of this enumeration are in $M[G]$.<br /><br />Since $j``G\subseteq G\ast G_{\kappa,j(\kappa)}$, we can lift the embedding to<br />$$j^+:V[G]\rightarrow M[j(G)].$$<br />Using the Lemma/Exercise above, different choices of $j(G)$ will give rise to different embeddings which will give different normal measures. By passing to finer antichains, we can assume in the enumeration $\langle A_\alpha:\alpha<\kappa^+\rangle$ that if $i<j$, then $A_j$ (strictly) refines $A_i$. Looking at how we built $G_{\kappa,j(\kappa)}$, we can form the tree of attempts to build the generic, noticing that at each level there are incompatible ways to extend the generic so far to meet the maximal antichain. This gives $2^{\kappa^+}=2^{2^\kappa}$ many different generics, and hence different normal measures. $\Box$<br /><br />So it's not hard to force many normal measures. It is harder to force so that there are few normal measures.<br /><br />We will need to use Hamkins's Gap Forcing Theorem which gives a sufficient condition for an ultrapower embedding in a generic extension to be the lift of a ground model embedding.<br /><br /><b>Definition:</b> A forcing $\mathbb{P}$ <i>admits a closure point at $\delta$ </i>if it factors as $\mathbb{P}\simeq \mathbb{Q}\ast \dot{\mathbb{R}}$ where $\mathbb{Q}$ is nontrivial, $|\mathbb{Q}|\le \delta$, and $\Vdash_{\mathbb{Q}} \mathbb{R} \textrm{ is }<\delta-\textrm{closed}$.<br /><br /><b>Theorem (Hamkins '01, Gap Forcing Theorem): </b>If $V\subseteq V[G]$ admits a closure point at $\delta$ and $j:V[G]\rightarrow M[j(G)]$ is an ultrapower in $V[G]$ with $\mathrm{crit}(j)>\delta$, then $j\upharpoonright V:V\rightarrow M$ is a definable class in $V$.<br /><br />Finally, we prove one more of the theorems in the introduction.<br /><br /><b>Theorem (Apter-Cummings-Hamkins '07): </b>It is consistent relative to a measurable cardinal that that $\#\mathrm{NM}(\kappa)=\kappa^+$.<br /><br /><i>Idea of the proof:</i> Start with at least $\kappa^+$ normal measures on $\kappa$ (e.g., by Kunen-Paris forcing). Force with $\mathrm{Col}(\kappa^+,2^{2^\kappa})$, and show that no new normal measures are added.<br /><br /><i>Proof:</i> Again we assume $2^\kappa=\kappa^+$. Start with $\#\mathrm{NM}(\kappa)\ge \kappa^+$. Let $\mathbb{P}=\mathrm{Add}(\omega,1)\ast \dot{\mathrm{Col}}(\kappa^+, 2^{2^\kappa})$. The point of the Cohen forcing is to give $\mathbb{P}$ a closure point below $\kappa$. Suppose $c\ast G\subseteq \mathbb{P}$ is $V$-generic. Then every normal measure in $V$ generates a normal measure in $V[c]$ by Levy-Solovay, and these remain normal measures in $V[c][G]$ since $\mathrm{Col}(\kappa^+, 2^{2^\kappa})$ is $\le \kappa$-closed in $V[c]$. So there are at least $\kappa^+$ normal measures in $V[c][G]$.<br /><br />To show the other inequality, suppose $U$ is a normal measure on $\kappa$ in $V[c][G]$. Let<br />$$j:V[c][G]\rightarrow M[c][j(G)]$$<br />be the ultrapower. By the gap forcing theorem, $j\upharpoonright V:V\rightarrow M$ is a definable class in $V$. So we can lift to $j\upharpoonright V[c]:V[c]\rightarrow M[c]$. We can now define $U$ in $V[c]$, as the derived measure from this embedding. $\Box$<br /><br /><br />Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-2268505480211315292015-09-01T01:46:00.000-07:002016-02-19T01:10:57.350-08:00UCI Summer School, part 5 (Monroe Eskew)This is just a placeholder, for now. My notes for this part are quite rough, so it will be a while before I will try to record it here. The next installment of these notes will cover Brent Cody's lectures on some results about the number of normal measures.Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-73452882588210575942015-09-01T01:34:00.000-07:002016-02-25T15:47:07.978-08:00UCI Summer School, part 4: Measure algebras (Monroe Eskew)Here are some more applications of the ideas we have been considering.<br /><div><br /></div><div><b>Definition: </b>$\mathcal{B}$ is a <i>measure algebra </i>if it is a complete Boolean algebra equipped with some function $\mu:\mathcal{B}\rightarrow [0,1]$ with $\mu(0)=0, \mu(1)=1, \mu(b)>0$ for $b\neq 0$, and $\mu$ countably additive (i.e., if $\langle b_i:i<\omega\rangle$ is an antichain, then $\mu(\sum b_i)=\sum \mu(b_i)$.</div><div><br /></div><div><i>Exercise: </i>All measure algebras are c.c.c.</div><div><br /></div><div><i>Example:</i> Let $\kappa$ be a cardinal. We will describe a topology on ${}^\kappa 2$. Fix some $x\in [\kappa]^{<\omega}$ and $s:x\rightarrow 2$ (i.e., $s$ is a finite domain partial function from $\kappa$ to $2$). Then basic open sets are of the form $\mathcal{O}_s=\{r\in {}^\kappa 2: \forall \alpha\in x(r(\alpha)=s(\alpha))\}$. Let $\mathcal{B}_\kappa$ be the $\sigma$-algebra generated by these basic open sets, and define $\mu$ on $\mathcal{B}_\kappa$ by setting $\mu(\mathcal{O}_s=\frac{1}{2^{|s|}}$ (standard theorems from real analysis give that $\mu$ extends uniquely to a countably additive probability measure on $\mathcal{B}_\kappa$. </div><div><br /></div><div>Define $\mathrm{Null}=\{A\in\mathcal{B}_\kappa: \mu(A)=0\}$. Then $\mathcal{R}_\kappa:=\mathcal{B}_\kappa/\mathrm{Null}$ is a measure algebra.</div><div><br /></div><div><i>Exercise: </i>Prove that $\mathcal{R}_\kappa$ forces $2^\omega\ge \kappa$.</div><div><br /></div><div><i>Exercise: </i>If $\mathcal{A}$ is a measure algebra and $\Vdash_A \dot{\mathcal{B}}$ is a measure algebra, then $\mathrm{r.o.}(\mathcal{A}\ast \dot{\mathcal{B}})$ is a measure algebra. (Note: this is not as easy as it may seem at first since for example $\mathcal{A}$ might even add new reals which can be measures of elements of $\mathcal{B}$! We use r.o. for the Boolean completion here since the letter $\mathcal{B}$ is overloaded).</div><div><br /></div><div><i>Exercise:</i> If $\mathcal{A}$ is a complete sublagebra of a measure algebra $\mathcal{B}$, then $\mathcal{A}$ is a measure algebra.</div><div><br /></div><div>Continuing along this line,</div><div><br /></div><div><b>Theorem: </b>If $\mathcal{B}$ is a measure algebra, $\mathcal{A}$ a complete subalgebra of $\mathcal{B}$, and $G\subseteq \mathcal{A}$ is generic over $V$, then in $V[G]$ we have that $\mathcal{B}/G$ is a measure algebra.</div><div><br /></div><div>Note that in $V[G]$, $G$ is a filter on $\mathcal{B}$, so $\mathcal{B}/G=\{[b]_G:b\in \mathcal{B}\}$. We use $G^*$ for the dual ideal. It's important to distinguish between the orderings of the two Boolean algebras here, and will be good to see how to translate between them using the forcing relation.</div><div><br /></div><div><b>Lemma: </b>If $\mathcal{B}$ is complete and $\mathcal{A}$ is a complete subalgebra and $G\subseteq \mathcal{A}$ is generic, then $\mathcal{B}/G$ is complete in $V[G]$.</div><div><br /></div><div><i>Proof of Lemma:</i> Suppose $\langle [b_\alpha]_G:\alpha<\kappa\rangle \in P(\mathcal{B}/G)\cap V[G]$. For each $\alpha<\kappa$, let $X_\alpha:=\{b:1\Vdash_{\mathcal{A}} [b]_{\dot{G}}\le [\dot{b}_\alpha]_{\dot{G}}\}$. Let $c_\alpha=\sum X_\alpha\in V$ (meet taken in $\mathcal{B}$).</div><div><br /></div><div>We claim that $1\Vdash_{\mathcal{A}} [c_\alpha]_{\dot{G}}=[\dot{b}_\alpha]_{\dot{G}}$ for each $\alpha$--this suffices to prove the lemma. The proof of the claim is straightforward but a little tedious. First we show $1\Vdash_{\mathcal{A}} [c_\alpha]_{\dot{G}}\le[\dot{b}_\alpha]_{\dot{G}}$. If this doesn't hold, then there are $d,p$ so that $p\in \mathcal{A}$, $d\wedge p\neq 0$, and </div><div>$$p\Vdash [\check{d}]\le [\check{c}_\alpha] \textrm{ and }[\check{d}]\wedge [\dot{b}_\alpha]=0.$$</div><div>The first conjunct implies that $p\wedge d\le c_\alpha$ in $\mathcal{B}$, and since $c_\alpha$ is a lub for $X_\alpha$, there is some $b\in X_\alpha$ so that $p\wedge d\wedge b\neq 0$. So $1\Vdash [p\wedge d\wedge b]\le [b_\alpha]$ by the definition of $b\in X_\alpha$. But the second conjunct gives $p\wedge d\wedge b_\alpha=0$, contradiction.</div><div><br /></div><div>Now to show $1\Vdash_{\mathcal{A}} [c_\alpha]_{\dot{G}}\ge[\dot{b}_\alpha]_{\dot{G}}$, assume for a contradiction that there are $p,a\in \mathcal{A}$ so that $p\Vdash [\check{a}]\le [\dot{b}_\alpha]$ and $p\Vdash [a\wedge \neg c_\alpha]\neq 0$. Now $p$ forces $[p\wedge a \wedge \neg c_\alpha]\le [\dot{b}_\alpha]$. Trivially, $\neg p$ forces $[p\wedge a \wedge \neg c_\alpha]=0$. So it's just outright forced that $[p\wedge a \wedge \neg c_\alpha]\le [b_\alpha]$ and thus $p\wedge a\wedge \neg c_\alpha \in X_\alpha$, which contradicts $c_\alpha$ is an upper bound for $X_\alpha$, completing the proof of the claim and the lemma. $\Box$</div><div><br /></div><div><i>Proof of Theorem: </i>Let $\mu$ be a measure on $\mathcal{B}$, $\mathcal{A}$ a complete subalgebra of $\mathcal{B}$. Define </div><div>$$\mu(b\mid a)=\frac{\mu(a \wedge b)}{\mu(a)}.$$</div><div>(We say the measure of $b$ conditioned on $a$).</div><div><br /></div><div><b>Definition</b>: For $a\in A,b\in B, \epsilon>0$, say $a$ is $\epsilon$-<i>stable for $b$ </i>if for all $x\le a$ in $\mathcal{A}$, $|\mu(b\mid x)-\mu(b\mid a)|<\epsilon$. </div><div><br /></div><div><b>Lemma: </b>For all $b\in B$ and for all $\epsilon>0$ the set $\{a\in A:a \textrm{ is }\epsilon-\textrm{stable for} b\}$ is dense in $A$.</div><div><i>Proof: </i>Exercise. An interesting one.</div><div><br /></div><div>In $V[G]$, let $\nu:\mathcal{B}/G\rightarrow [0,1]$ be given by $\nu([b])=r$ if for every $\epsilon>0$ there is some $a\in G$ so that $a$ is $\epsilon$-stable for $b$ and $|\mu(b\mid a)-r|<\epsilon$. The idea is that $G$ could add new reals, so we can only have approximations to the measure of $[b]$ using ground model reals attached to the members of $\mathcal{A}$.</div><div><br /></div><div>We can check that this is well-defined: if $[b]_G=[c]_G$, then some $a\in G$ forces $b\Delta c\in G^*$. This means that $a\perp (b\Delta c)$, so $\mu(a\wedge (b\Delta c)=0$. Therefore $\mu(b\mid x)=\mu(c\mid x)$ for all $x\le a$. Suppose $r_0\neq r_1$ both satisfy $\nu(b)=r_i$. Take $\epsilon<|r_1-r_0|$. Let $a_0,a_1\in G$ be $\epsilon/4$-stable for $b$ with $|\mu(b\mid a_i)-r_i|<\epsilon/4$. Now take $a\le a_0, a_1$ in $\mathcal{A}$. By a triangle inequality argument, we have $|r_1-r_0|<\epsilon$, a contradiction.</div><div><br /></div><div><i>Exercise</i>: Check that $\nu(b)>0$ for all $b\neq_G 0$.</div><div><br /></div><div><i>Exercise</i>: Check that $\nu$ is countably additive. First prove that it is finitely additive.</div><div>$\Box$.</div><div><br /></div><div>Now suppose $P(Z)/I$ is a measure algebra. The duality theorem (ccc case) says that for any $\theta$, $\mathcal{R}_\theta\ast P(Z)/\bar{I}\cong P(Z)/I\ast j(\mathcal{R}_\theta)$,</div><div>where $j:V\rightarrow M$ is the generic embedding in $V[G]$, $G$ generic for $P(Z)/I$.</div><div><br /></div><div>The right hand side of this isomorphism is a measure algebra, since $P(Z)/I$ is a measure algebra by assumption, and $j(\mathcal{R}_\theta)$ is a measure algebra of $M$, a model which is closed under countable sequences (and so has all the countable sequences to witness countable additivity and completeness of the Boolean algebra).</div><div><br /></div><div>We have a map $e:\mathcal{R}_\theta\rightarrow \mathrm{r.o.}(P(Z)/I\ast j(\mathcal{R}_\theta)$, so $\mathcal{R}_\theta$ is isomorphic to a complete subalgebra of the right hand side. Now if $H\subseteq \mathcal{R}_\theta$ is generic, then $B/e''H$ is a measure algebra. Therefore $P(Z)/\bar{I}$ is also a measure algebra.</div><div><br /></div><div>A real-valued measurable cardinal is a cardinal $\kappa$ which carries a $\kappa$-additive probability measure on all subsets of $\kappa$ which gives measure 0 to singletons. It is atomless if every set of positive measure has a subset of strictly smaller positive measure.</div><div><br /></div><div><b>Corollary: </b>If $\langle \kappa_i:i<\theta\rangle$ is a sequence of measurable cardinals, then if $\gamma=\sup \kappa_i$, $\mathcal{R}_\gamma$ forces all $\kappa_i$ to be atomless real-valued measurable cardinals (RVMs).</div><div><br /></div><div>We note the fact that if $\kappa$ is atomlessly RVM, then $2^\omega\ge \kappa$, so we can't get class many RVMs.</div><div><br /></div><div>However, if $\kappa$ is strongly compact, then $\mathcal{R}_\kappa$ forces that for all regular $\lambda\ge \kappa$, there is a <i>countably additive</i> real-valued probably measure $\mu_\lambda$ on $\lambda$ giving measure 0 to all subsets of size $<\lambda$.</div><div><br /></div><div><br /></div>Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-73046993617552263612015-08-07T13:11:00.000-07:002016-02-19T01:11:15.232-08:00UCI Summer School, part 3: Applications of Duality Theorem (Monroe Eskew)We now turn towards applications of the duality theorem. It is recommended that the reader recalls the notation ($I,j,K,J,\hat{H},e,\iota$, etc.) from the <a href="http://billset.blogspot.com/2015/07/uci-summer-school-part-2-duality.html" target="_blank">previous lecture</a> before proceeding.<br /><br />The basic idea is that one uses the isomorphism there:<br />$$\mathcal{B}(\dot{\mathbb{P}\ast P(Z)/J})\equiv \mathcal{B}(P(Z)/I\ast j(\mathbb{P})/\dot{K})$$<br />to calculate the quotient algebra $P(Z)/J$ as $\mathcal{B}(P(Z)/I\ast j(\mathbb{P})/\dot{K})/e''H$.<br /><br />As discussed near the end of the last lecture, under certain assumptions, the statement of the duality theorem becomes somewhat simpler. The first examples will fall into this case.<br /><br /><i>Special Case:</i><b> </b>If $I$ is $\kappa$-complete and $\mathbb{P}$ is $\kappa$-c.c., then the hypothesis of the duality theorem holds, $K=\{0\}$ and $J=\bar{I}$, the ideal generated by $I$ in $V^\mathbb{P}$.<br /><br /><b>Exercise: </b>Show that in the above case, if $p\in \mathbb{P}$ and $A\in (P(Z)/I)\cap V$, then<br />$$\iota(p,\check{A})=(A,j(\dot{p})).$$<br /><br />A further simplification will be that we will usually start with a measurable cardinal $\kappa$ and take $I$ to be the dual to the measure on $\kappa$, so $P(\kappa)/I$ is the trivial Boolean algebra.<br /><br />A measurable cardinal $\kappa$ has a 2-saturated, $\kappa$-complete ideal, namely the dual to the measure on $\kappa$, and under GCH every cardinal $\kappa$ carries a $\kappa^{++}$-saturated, $\kappa$-complete ideal, namely the ideal of bounded subsets. This motivates the following natural questions, which are the main focus of this lecture:<br /><br /><i>Question</i>: Suppose $\mu\le \kappa^+$ is a regular cardinal. Is it consistent that there is a cardinal $\kappa$ which is not measurable, but still $\kappa$ carries a $\mu$-saturated, $\kappa$-complete ideal? (Here we want the amount of saturation to be exactly $\mu$).<br /><br />Digression: does the answer change if we require $\kappa$ to be a successor cardinal?<br /><br />For the case where $\kappa$ is a successor cardinal, $\kappa^+$-saturation is the strongest we can hope to achieve.<br /><br /><b>Exercise: </b>Prove using the method of generic ultrapowers that if $\kappa$ is a successor cardinal then there is no $\kappa$-complete, $\kappa$-saturated ideal on $\kappa$.<br /><br />Kunen showed that if $\kappa$ is a successor cardinal, then getting a $\kappa^+$-saturated ideal on $\kappa$ requires large cardinals much stronger than a measurable, although we won't do this argument here (you can find it in this <a href="http://billset.blogspot.com/2014/10/spencinar-3-saturated-ideals-part-2.html" target="_blank">previous Specinar post</a>. We now return to the original question.<br /><br /><i>Answer to question 1, if $\mu<\kappa$ ($\mu$ regular)</i>: We will use the basic technique of computing the quotient algebra $P(\kappa)/J$ in $V[H]$ using the duality theorem. Start with $\kappa$ measurable in the ground model. Let $\theta\ge \kappa$, and consider $\mathrm{Add}(\mu,\theta)$ which adds $\theta$ Cohen subsets of $\mu$. $\mathrm{Add}(\mu,\theta)$ is $\kappa$-c.c., and under the GCH it is even $\mu^+$-c.c. Let $I=U^*$, where $U$ is a $\kappa$-complete normal ultrafilter on $\kappa$ (here the star means taking the dual ideal). Let $j:V\rightarrow M$ be the ultrapower embedding.<br /><br />The duality theorem gives the isomorphism:<br />$$\mathrm{Add}(\mu,\theta)\ast P(\kappa)/\bar{I}\cong P(\kappa)/I\ast \mathrm{Add}(\mu,j(\theta))\cong\mathrm{Add}(\mu,j(\theta)),$$<br />since $P(\kappa)/I$ is trivial.<br /><br />If $H$ is generic for $\mathrm{Add}(\mu,\theta)$ over $V$, then<br />$$e''H=\{(1,j(p)):p\in H\}.$$<br />So<br />$$P(\kappa)/\bar{I}\cong \mathrm{Add}(\mu,j(\theta))/e''H\cong \mathrm{Add}(\mu,j(\theta)).$$<br />In $V[H]$, $P(\kappa)/\bar{I}\cong \mathcal{B}(\mathrm{Add}(\mu,j(\theta))$, so $\bar{I}$ is $(\mu^{<\mu})^+$ saturated. Furthermore, it is easy to check that $\bar{I}$ is $\kappa$-complete, and $2^\mu\ge \kappa$ in $V[H]$, so $\kappa$ is not measurable. This answers question 1 for the case where $\mu<\kappa$. $\Box$<br /><br />We might ask what large cardinal properties of $\kappa$ are implied by this ideal hypothesis.<br /><br /><b>Proposition: </b>If $\kappa$ carries a $\kappa$-complete $\mu$-saturated ideal for some $\mu<\kappa$, then:<br /><br /><ol><li>$\kappa$ is weakly Mahlo</li><li>$\kappa$ has the tree property.</li></ol><div><b>Exercise: </b>Prove (1) of the proposition using generic ultrapowers.</div><div><br /></div><div>Proof of Proposition (2): Suppose $T$ is a $\kappa$-tree. If $G\subseteq P(\kappa)/I$ is generic, then in $V[G]$, $T$ has a branch $b$ given by taking any member of level $\kappa$ of $j(T)$, where $j$ is the generic ultrapower embedding. Now for each $\alpha<\kappa$, $S_\alpha=\{x\in T_\alpha: \exists p(p\Vdash \check{x}\in \dot{b})\}<\mu$ by the saturation. Now $\bigcap_{\alpha<\kappa} S_\alpha$ is a $\kappa$-tree all of whose levels have size $<\mu<\kappa$. It is well-known (or a good exercise) that such trees have cofinal branches. $\Box$</div><div><br /></div><div><b>Definition: </b>An ideal $I$ is <i>nowhere prime </i>if there is no $I$-positive set $A$ so that $I\upharpoonright A$ is prime (i.e., dual to an ultrafilter).</div><div><br /></div><div><b>Exercise: </b>Show that if there is a nowhere prime, $\kappa$-complete, $\mu^+$-saturated ideal, where $\mu<\kappa$, then $2^\mu\ge \kappa$.</div><div><br /></div><div>We continue with Question 1 with other arrangements of $\mu$ and $\kappa$.</div><div><br /></div><div><i>Answer to question 1, if $\mu=\kappa^+$</i>: Start with $\kappa$ measurable with $2^\kappa=\kappa^+$, $U$ a normal ultrafilter and $j:V\rightarrow M$ the ultrapower embedding. Let $\langle \mathbb{P}_\alpha,\dot{\mathbb{Q}}_\alpha:\alpha<\kappa\rangle$ be the Easton support iteration where for regular $\alpha$, $\Vdash_{\mathbb{P}_\alpha} \dot{Q}=\mathrm{Add}(\alpha,1)$. It is straightforward to verify that $\mathbb{P}_\kappa$ has the $\kappa$-c.c., so we are in the special case again.</div><div><br /></div><div>Note that $j(\mathbb{P}_\kappa)=\mathbb{P}_\kappa\ast \mathbb{Add}(\alpha,1)\ast (\mathbb{P}_{\kappa+1,j(\kappa)})^M$ (We use the notation $\mathbb{P}_{\xi,j(\kappa)}$ for $j(\mathbb{P}_\kappa)_{\xi,j(\kappa)}$). The tail part is computed differently in $M$ than in $V$, e.g., the support is on $M$-regular cardinals. </div><div><br /></div><div>If $G_\kappa\subseteq \mathbb{P}_\kappa$ is generic over $V$, then the special case of the duality theorem says that in $V[G_\kappa]$, $P(\kappa)/\bar{I}\cong (\mathbb{P}_{\kappa,j(\kappa)})^M$. However, $P(\kappa)/\bar{I}\cong(\mathbb{P}_{\kappa,j(\kappa)})^M$ does not have the $\kappa^+$-c.c. since there are $M$-regular cardinals between $\kappa^+$ and $j(\kappa)$. So $\bar{I}$ is not $\kappa^+$-saturated.</div><div><br /></div><div>Now we could also satisfy the hypothesis of the duality theorem of adding a $j(\mathbb{P}_\kappa)=P(\kappa)/J\cong \mathrm{Add}(\alpha,1)\ast (\mathbb{P}_{\kappa+1,j(\kappa)})^M$ generic filter $\hat{H}$ over $M$ in a different way. By a standard technique, a $j(\mathbb{P})$-generic over $M$ exists in $V[G_{\kappa+1}]$ (where $G_{\kappa+1}$ is $\mathbb{P}_\kappa\ast \mathrm{Add}(\alpha,1)$-generic). This is because we clearly get a generic for the initial part $\mathbb{P}_\kappa\ast \mathrm{Add}(\alpha,1)$, just $G_{\kappa+1}$ itself. For the tail, $(\mathbb{P}_{\kappa+1,j(\kappa)})^{M[G_{\kappa+1}]}$ is is $j(\kappa)$-c.c. of size $j(\kappa)$ in $M[G_{\kappa+1}]$, so $M[G_{\kappa+1}]$ thinks the poset has at most $j(\kappa)$ maximal antichains. In $V[G_{\kappa+1}]$, $|j(\kappa)|=\kappa^+$, and the poset is $\kappa^+$-closed (in $M[G_{\kappa+1}]$, but also in $V[G_{\kappa+1}]$ by the agreement between these models). So we can construct a generic by hand in $V[G_{\kappa+1}]$ by enumerating all of the maximal antichains in $M[G_{\kappa+1}]$. This completes the construction of $\hat{H}$ in the extension by $\mathrm{Add}(\kappa,1)$.</div><div><br /></div><div>In this construction, we have that $j(\mathbb{P})/K\cong \mathbb{P}_\kappa\ast \mathrm{Add}(\kappa,1)$, since the Boolean algebra homomorphism $j(\mathbb{P}_\kappa)\rightarrow \mathbb{P}_\kappa\ast \mathrm{Add}(\kappa,1)$ given by $p\mapsto \|p\in \hat{H}\|$. has kernel exactly $K$ as defined in the last lecture, and the map is surjective since the codomain completely embeds into the domain. So in the duality theorem calculation, we obtain an ideal $J$ so that $P(\kappa)/J\cong \mathrm{Add}(\kappa,1)$. So $J$ is a $\kappa^+$-saturated ideal on $\kappa$. $\Box$<br /><br />Note that $\kappa$ is inaccessible.<br /><br /><b>Exercise: </b>Prove that $\kappa$ is weakly compact in $V[G_\kappa]$. (Hint: use the tree property characterization.)<br /><br /><b>Exercise: </b>Prove that $\kappa$ is not measurable in $V[G_\kappa]$, but it is measurable in $V[G_{\kappa+1}]$.<br /><br /><i>Remark: </i>By forcing with $(\mathbb{P}_{\kappa,j(\kappa)})^{M[G_{\kappa+1}]}$ instead of just $\mathrm{Add}(\kappa,1)$ to add the $j(\mathbb{P})$-generic, we can get a nowhere prime $\kappa$ complete $\kappa^+$-saturated ideal on $\kappa$ in $V[G_{\kappa+1}]$.<br /><br /><i>Answer to question 1, if $\mu=\kappa$</i>: We will find an example so that $\kappa$ is not weakly compact (compare to earlier results for saturation below $\kappa$), and in fact the quotient algebra is isomorphic to a $\kappa$-Suslin tree.<br /><br />In the exercises, we will describe how to construct, for $\alpha$ regular with $\alpha^{<\alpha}=\alpha$, a forcing $\mathbb{Q}_\alpha$ which adds an $\alpha$-Suslin tree $\dot{T}_\alpha$ so that $\mathcal{B}(\mathbb{Q}_\alpha\ast \dot{T}_\alpha)\cong\mathrm{Add}(\alpha,1)$. This is due to Kunen.<br /><br />In the construction for $\mu=\kappa^+$ we got a model (there called $V[G_\kappa]$) where there was an inaccessible $\kappa$ and an ideal $J$ on $\kappa$ so that<br />$$P(\kappa)/J\cong\mathrm{Add}(\kappa,1)\cong \mathbb{Q}_\kappa\ast \dot{T},$$<br />where $\dot{T}$ is the $\kappa$-Suslin tree added by $\mathbb{Q}_\kappa$.<br /><br />Now start with this to be our ground model $V$. Let $H\subseteq \mathbb{Q}_\kappa$ be generic. We want to show that in $V[H]$, there is an ideal $J_1$ on $\kappa$ so that $P(\kappa)/J_1\cong T$.<br /><br />If $G\subseteq \mathrm{Add}(\kappa,1)$ is generic over $V$, then take in $V[G]$ an embedding<br />$$j:V\rightarrow M$$<br />which was constructed before. We want to extend the embedding to $V[H]$.<br /><br />Now $G\in M$ since $M$ is closed under $\kappa$-sequences in $V[G]$. We can extend $j$ to $V[G]$ by constructing a generic $\hat{G}$ for $\mathrm{Add}(j(\kappa))^M$ over $M$ with $\hat{G}\upharpoonright \kappa=G$ (using the standard method; cf the second exercise following previous construction).<br /><br />In $V$, by duality theorem there are $J_1$ and $K$ so that<br />$$\mathbb{Q}_\kappa\ast P(\kappa)/J_1\cong P(\kappa)/J\ast j(\mathbb{Q}_\kappa)/K.$$<br />In this case, $K$ is a maximal ideal since the $j(\mathbb{Q}_\kappa)$-generic over $M$ is already just added by $P(\kappa)/J$. So in $V[H]$, $P(\kappa)/J_1\cong T$.<br /><br />Now we turn to Kunen's forcing construction. Conditions in Kunen's forcing $\mathbb{Q}$ are normal trees of successor ordinal height $<\kappa$ which are homogeneous: for all $t\in T$ not on the top level, $T_t\cong T$, where $T_t$ is the tree $\{s\in T: t\le_T s\}$ with the order inherited from $T$.<br /><br /><b>Exercise:</b><br /><br /><ol><li>Show that Kunen's forcing is $\kappa$-strategically closed. Hint: the strategy will go by choosing a particular branch through each of the small trees chosen in a play of the game so far.</li><li>Show that $\mathbb{Q}\ast \dot{T}$ has a $\kappa$-closed dense subset, and deduce that $\mathbb{Q}\ast \dot{T}\cong \mathrm{Add}(\kappa)$.</li><li>Show that $\dot{T}$ is a Suslin tree.</li></ol><br />$\Box$<br /><br />We will do one last application to construct a precipitous ideal on a cardinal $\kappa$ which is not measurable so that its quotient algebra is $\kappa^+$ closed.<br /><br />Start with $\kappa$ measurable and $2^\kappa>\kappa^+$. We will use the Easton support iteration $\langle \mathbb{P}_\alpha,\dot{\mathbb{Q}}_\alpha:\alpha<\kappa\rangle$, where $\dot{\mathbb{Q}}_\alpha=\dot{\mathrm{Add}(\alpha^+,1)}$ for inaccessible $\alpha<\kappa$ (and is trivial forcing otherwise).<br /><br />Then $\mathbb{P}_\kappa$ is $\kappa$-c.c., and forces that for all inaccessible $\alpha<\kappa$, $2^\alpha=\alpha^+$ (this is a standard coding trick that was assigned as an exercise in one of Spencer Unger's lectures here). By duality,<br />$$\mathbb{P}_\kappa\ast P(\kappa)/\bar{I}\equiv j(\mathbb{P}_\kappa).$$<br />If $G_\kappa\subseteq \mathbb{P}_\kappa$ is generic, then $j(\mathbb{P}_\kappa)/e''G_\kappa\equiv \mathbb{P}_{\kappa,j(\kappa)}$. Since $M[G_\kappa]$ is closed under $\le \kappa$ sequences in $V[G_\kappa]$, this tail is $\kappa^+$-closed forcing over $V[G_\kappa]$.<br /><br />However, GCH holds at every inaccessible $\alpha<\kappa$ and fails at $\kappa$ in $V[G_\kappa]$. By a reflection argument, $\kappa$ cannot be measurable in $V[G_\kappa]$. $\Box$<br /><br /><b>Exercise: </b>Show that if $H\subseteq P(\kappa)/\bar{I}$ is generic, then $\kappa$ is measurable in $V[G_\kappa\ast H]$.<br /><br /></div>Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-1633910015120043252015-07-27T17:06:00.001-07:002016-02-19T01:11:29.499-08:00UCI Summer School part 2: Duality Theorem (Monroe Eskew)The Duality Theorem gives a general technique for forcing to make an ideal whose quotient algebra has various properties. It appears in Matthew Foreman's "Calculating quotient algebras of generic embeddings." My version of these notes omits a lot of the dots which indicate that certain objects are just names in a forcing extension. This is for aesthetic reasons, and hopefully does not lead to confusion.<br /><br /><b>Duality Theorem:</b> <i>Suppose $I$ is a precipitous ideal on $Z$ and $\mathbb{P}$ is any partial order. If: there is a further generic extension of the extension by $P(Z)/I$ so that if $j:V\rightarrow M\subseteq M\subseteq V[G]$ is the ultrapower embedding from $G\subseteq P(Z)/I$, there is $H\subseteq \mathbb{P}$ generic over $V$ and $\hat{H}\subseteq j(\mathbb{P})$ generic over $M$ and some extension of $j$ to $\hat{j}:V[H]\rightarrow M[\hat{H}]$.</i><br /><i><br /></i><i>Then: there is a $\mathbb{P}$-name for an ideal $J$ on $Z$ and a $P(Z)/I$-name for an ideal $K$ on $j(\mathbb{P})$ and a canonical isomorphism $$\iota:\mathcal{B}(\dot{\mathbb{P}\ast P(Z)/J})\equiv \mathcal{B}(P(Z)/I\ast j(\mathbb{P})/\dot{K}).$$</i><br /><br /><br />So a very general statement of lifting a generic ultrapower map to a forcing extension gives a useful isomorphism for computing $P(Z)/J$ in the generic extension by $\mathbb{P}$. We remark that in some cases, this will be an equivalence.<br /><br />Note: In what follows, we tacitly identify all of the posets involved with their Boolean completions. Occasionally for emphasis, this identification will be explicit.<br /><br /><i>Proof</i>: Assume (1). There is some $A\in I^+$ and some $P(Z)/I$-name for a forcing $\dot{\mathbb{Q}}$ so that<br />$$A\Vdash_{P(Z)/I}(\Vdash_\dot{\mathbb{Q}} \dot{H_0}\subseteq j(\mathbb{P}) \textrm{ is generic over }M \textrm{ and }H:=j^{-1}[H_0]\subseteq \mathbb{P}\textrm{ is generic over }V).$$<br /><br />Note that the set $\{p\in\mathbb{P}:\quad \Vdash_{P(A)/I\ast \mathbb{Q}} j(p)\not\in H_0\}$ cannot be dense, since it is the complement of the generic $j^{-1}[H_0]$. So there is $p_0\in \mathbb{P}$ so that for all $p\le p_0$, $\| j(p)\in H_0 \|_{P(A)/I\ast \mathbb{Q}}\neq 0$. We will constrain ourselves to work below this $p_0$ in $\mathbb{P}$ and below $A$ in $P(Z)/I$. For simplicity, assume that $A=Z$ and $p_0=1_\mathbb{P}$.<br /><br />In $V^{P(Z)/I}$, define<br />$$K=\{p\in j(\mathbb{P}):\quad \Vdash_{\mathbb{\dot{Q}^G}} p\not\in H_0\}.$$<br />Let $G\ast h$ be generic for $P(Z)/I\ast j(\mathbb{P})/K$. From the $j(\mathbb{P})/K$-generic $h$, we can define a $j(\mathbb{P})$-generic $\hat{H}=\{p:[p]_K\in h\}$.<br /><b><br /></b><b>Claim: </b>The following properties of $H_0$ are also true of $\hat{H}$:<br /><br /><ol><li>$\Vdash_{P(Z)/I\ast \mathbb{Q}} \hat{H}$ is $j(\mathbb{P})$-generic over $M$.</li><li>$\Vdash_{P(Z)/I\ast \mathbb{Q}} j^{-1}[\hat{H}]$ is $\mathbb{P}$-generic over $V$.</li><li>For all $p\in \mathbb{P}$, $\not\Vdash_{P(Z)/I\ast \mathbb{Q}} j(p)\not\in \hat{H}$.</li></ol><div><i>Proof of Claim:</i> For (1), suppose $D\in M$ is open dense in $j(\mathbb{P})$. Then $\{[d]_K:d\in D\textrm{ and }d\not\in K\}$ is dense in $j(\mathbb{P})/K$. Otherwise, there would exist $p\in j(\mathbb{P})/K$ so that $p\wedge d\in K$ for all $d\in D$. But this is impossible because we could then force with $\mathbb{Q}$ over $V[G]$ to get a generic $H_0$ containing $p$ (as $p\not\in K$), and then $H_0\cap D=\emptyset$, contradicting genericity of $H_0$ over $M$.</div><div><br /></div><div>The remaining parts of the claim can be checked similarly, and are left as an exercise. $\Box$.</div><div><br /></div><div>Now let $e:\mathbb{P}\rightarrow \mathcal{B}(P(Z)/I\ast \dot{j(\mathbb{P})/K})$ be defined by $e(p)=\|j(p)\in \hat{H}\|$.</div><div><br /></div><div>By (3) of the claim above, $\mathrm{ker}(e)=0$. Also $e$ preserves Boolean operations simply by the elementarity of $j$. By (2) of the claim, $e$ is a regular embedding (maps maximal antichains pointwise to maximal antichains). </div><div><br /></div><div><b>Exercise:</b> $e:\mathbb{P}\rightarrow \mathbb{Q}$ is a regular embedding iff for every $q\in\mathbb{Q}$ there is $p\in \mathbb{P}$ so that for every $p'\le p$, $e(p')$ is compatible with $q$.</div><div><br /></div><div>Thus, if $H\subseteq \mathbb{P}$ is generic over $V$, we can force with the quotient $\mathcal{B}(P(Z)/I\ast \dot{j(\mathbb{P})/K})/e"H$ over $V[H]$ to obtain a generic $G\ast h$ for $P(Z)/I\ast j(\mathbb{P})/K$. By the definition of $e$, we have $j_G"H\subseteq \hat{H}$, where $\hat{H}$ is defined from $h$ as before. So we can extend the embedding $j_G$ to $\hat{j}:V[H]\rightarrow M[\hat{H}]$.</div><div><br /></div><div>In $V[H]$ we can finally define $J=\{A\subseteq Z:1\Vdash [\mathrm{id}]\not\in \hat{j}(A)\}$, where the forcing is with the quotient $\mathcal{B}(P(Z)/I\ast \dot{j(\mathbb{P})/K})/e"H$. In $V$, let</div><div>$$\iota(p,\dot{A})=e(p)\wedge \|[id]\in\hat{j}(\dot{A})\|.$$</div><div><br /></div><div><b>Exercise: </b>$\iota$ is order and incompatibility preserving.</div><div><br /></div><div>It remains to show that the range of $\iota$ is dense. So take an arbitrary $(B,\dot{q})\in P(Z)/I\ast j(P)/K$. By strengthening this condition, we may assume without loss of generality that there is $f:Z\rightarrow \mathbb{P}$ in $V$ so that $B\Vdash [[f]_M]_K=\dot{q}$.</div><div><br /></div><div>By regularity of $e$ (using the characterization in the exercise), there is a $p$ so that for all $p'\le p$, $e(p')\wedge (B,\dot{q})\neq 0$. Let $\dot{A}$ be a $\mathbb{P}$-name for a subset of $Z$ such that $p \Vdash \dot{A}=\{z\in B: f(z)\in H\}$ and $\neg p \Vdash \dot{A}\in J^+$.</div><div><br /></div><div>We check that $(p,\dot{A})$ is actually a condition, which involves checking that $p\Vdash \dot{A}\in J^+$. So take a generic $G\ast \dot{h}$ containing $e(p)\wedge (B,\dot{q})$ (which is nonzero by choice of $p$). Then clearly $B\in G$ and since $[[f]_M]_K=q\in h$, we have $[f]_M=j(f)([\mathrm{id}])\in\hat{H}$. Therefore $[\mathrm{id}]\in \hat{j}(A)$, so this generic $G\ast \dot{h}$ shows that it is not forced by $\mathcal{B}(P(Z)/I\ast \dot{j(\mathbb{P})/K}/e"H$ that $[\mathrm{id}]\not\in \hat{j}(A)\}$.</div><div><br /></div><div>By definition $\iota:=\iota(p,\dot{A})$ forces $j(p)\in \hat{H}$ and $[\mathrm{id}]\in\hat{j}(\dot{A})$. Since $\hat{j}$ extends $j$ and it's forced that $\dot{A}\subseteq B$, $\iota$ must force $B\in G$. And since $j(p)\Vdash_{j(\mathbb{P})} j(\dot{A})=j(\{z:j(f)(z)\in \hat{H}\})$, $\iota$ must force $\dot{q}=[j(f)(\mathrm{id})]_K\in h$. $\Box$</div><div><br /></div><div><b>Remark: </b>Suppose $K$ as in the Duality Theorem is forced to be principal, i.e., there is $m$ so that $$\Vdash K=\{p\in j(\mathbb{P}:p\le \neg m\}.$$</div><div>Then the Duality Theorem is easily seen to be an equivalence.</div><div><br /></div><div>We can compute some nice properties of the ideal $J$ arising from the previous theorem.</div><div><br /></div><div><b>Proposition:</b><i style="font-weight: bold;"> </i>Using the notation of the previous theorem, $J$ is forced to be precipitous, with the same completeness as $I$. If $I$ is normal, then $J$ is also normal. Also, if $\bar{G}\subseteq P(Z)/J$ is generic over $V[H]$ and $G\ast h=\iota[H\ast \bar{G}]$ and $\hat{j}:V[H]\rightarrow M[\hat{H}]$ are as before, then $V[H]^Z/{\bar{G}}=M[\hat{H}]$ and $\hat{j}$ is the ultrapower embedding.</div><div><br /></div><div>Finally, we relate $J$ to the ideal in $V[H]$ generated by $I$.</div><div><br /></div><div><b>Proposition: </b>Suppose $K$ as in the Duality Theorem is forced to be principal, with $m$ so that $\Vdash K=\{p\in j(\mathbb{P}):p\le \neg m\}.$ Suppose further that there exist $f$ and $A$ so that $A\Vdash \dot{m}=[f]_G$ and $\dot{B}$ is a $\mathbb{P}$-name for $\{z\in A: f(z)\in \dot{H}\}$. Then $\bar{I}\upharpoonright B=J\upharpoonright B$, and $A\setminus B\in J$, where $\bar{I}$ is the ideal in $V[H]$ generated by $I$.</div>Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-45534939016793724472015-07-17T21:25:00.001-07:002016-02-19T01:11:49.899-08:00UCI Summer School part 1: Basics (Monroe Eskew)The UCI summer school in set theory just finished, and I'll be posting my notes on this blog. They will not be added in chronological order, and the final product will be very different from the actual presentation, assume that all errors were added by me.<br /><div><br /></div><div>There are some exercises which we solved during problem sessions during the day; I will preserve these in the text and can post solutions as well if there is interest.</div><div><br /></div><div>We start off with Monroe Eskew's lectures on the duality theorem. </div><div><br /></div><div><b>Basic facts:</b> This section is meant to be supplemented by my earlier postings about ideal properties. The basic situation is that $I$ is an ideal on $Z\subseteq P(X)$, $G$ is a generic for the forcing $P(Z)/I$, and $j:V\rightarrow M=V^Z/G$ is the generic ultrapower by $G$.</div><div><br /></div><div><b>Definition: </b>An ideal $I$ has the <i>disjointing property </i>if every antichain $A$ in $P(Z)/I$ has a pairwise disjoint system of representatives.</div><div><br /></div><div><i>Exercise: </i>If $I$ is a $\kappa$-complete, $\kappa^+$-saturated ideal, then $I$ has the disjointing property. <i> </i>If $I$ is a normal ideal on $Z\subseteq P(X)$, and $I$ is $|X|^+$-saturated, then $I$ has the disjointing property. </div><div><br /></div><div><b>Lemma: </b>Suppose $A\in I^+$ and $I$ has the disjointing property, and $[A]\Vdash \dot{\tau} \in V^Z/\dot{G}$. Then there is $f:Z\rightarrow V$ such that $A\Vdash \tau = [f]_G$.</div><div><br /></div><div><i>Proof:</i> Exercise.</div><div><br /></div><div><b>Lemma: </b>Suppose $I$ is a countably closed ideal with the disjointing property. Let $\kappa=\mathrm{crit}(j)$. Then $I$ is precipitous, and the generic ultrapower $M$ is closed under $\kappa$-sequences from $V[G]$.</div><div><i>Proof:</i> Precipitousness follows from the combinatorial characterization of precipitousness. Suppose that $\Vdash \langle \tau_\alpha:\alpha<\kappa\rangle \subseteq V^Z/G$. By the previous lemma, for all $\alpha<\kappa$, there is $f_\alpha:Z\rightarrow V$ in $V$ such that $\Vdash \tau_\alpha=[f_\alpha]_G$ and $k:Z\rightarrow \mathrm{ON}$ in $V$ such that $\Vdash \kappa=[k]_G$. Finally, take $f:Z\rightarrow V$ given by $f(z)=\langle f_\alpha(z):\alpha<k(z)\rangle$. In $M$, $[f]_G=\langle \tau_\alpha:\alpha<\kappa\rangle$. $\Box$</div><div><br /></div><div><b>Definition: </b>$I$ is $(\lambda,\kappa)$-<i>presaturated </i>if for any sequence of antichains $\langle A_\alpha:\alpha<\gamma<\lambda\rangle$, the set $\{X:\forall\alpha<\gamma\, |\{a\in A_\alpha:a\cap x\in I^+\}|<\kappa\}$ is dense.</div><div><br /></div><div><i>Exercise: </i>$(\lambda^+, \kappa^+)$-presaturation and $\kappa$-completeness imply that the generic ultrapower $M$ is closed under $\lambda$-sequences from $V[G]$. Also show this for normal and $(\lambda^+,|X|^+)$-presaturated ideals.</div><div><br /></div><div>We will use the notation $\mathcal{B}(\mathbb{P})$ to denote Boolean completion of a poset. As we have seen in previous posts, this is very handy when dealing with generic ultrapowers.</div><div><br /></div><div><i>Exercise: </i>$\mathbb{P}$ and $\mathbb{Q}$ are separative posets. The following are equivalent: </div><div><br /><ol><li>$\mathcal{B}(\mathbb{P})=\mathcal{B}(\mathbb{Q})$.</li><li>There is a $\mathbb{P}$-name $\dot{h}$ and a $\mathbb{Q}$-name $\dot{g}$ so that $$\Vdash_\mathbb{P} \dot{h} \textrm{ is }\mathbb{Q}-\textrm{generic over }V,$$ $$\Vdash_\mathbb{Q} \dot{g} \textrm{ is }\mathbb{P}-\textrm{generic over }V,$$ and$$\Vdash_\mathbb{P} \dot{g}^{\dot{h}^\dot{G}}=\dot{G} \textrm{ and } \Vdash_\mathbb{Q} \dot{h}^{\dot{g}^\dot{H}}=\dot{H}.$$</li></ol></div>Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-24123016984379268152015-06-16T16:38:00.002-07:002015-06-16T16:38:46.635-07:00Tight stationarity and tree-like scalesMy article, "Tight stationarity and tree-like scales," is now available online in the Annals of Pure and Applied Logic.<br /><br />You can also find the final version <a href="http://www.math.ucla.edu/~chenwb/papers/tltsfinal.pdf" target="_blank">here</a>.<br /><br />I have some slides on this topic from last year's BEST conference available <a href="http://www.math.ucla.edu/~chenwb/chenriverside.pdf" target="_blank">here</a>. (Coincidentally, I'm now at the 2015 BEST conference :)Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-51749498842051945942015-04-17T02:03:00.000-07:002015-04-17T02:04:21.792-07:00Spencinar: Morley's categoricity theorem, part 1Unfortunately, I missed posting about some interesting lectures given at the Very Informal Gathering, and the Southern California logic meeting at Caltech. We'll return with this series of posts following Spencer Unger's talks at the first two seminars of the quarter. There may be a larger amount of errors than usual in my transcription because of my limited knowledge of model theory. Basic model theory will be helpful to follow these notes, but I'll do my best to fill in the definitions. The notation follows Marker's text closely.<br /><br />A general question is:<br />Given a first order theory $T$, what can we say about the number of non-isomorphic models of $T$ of size $\lambda$, as $\lambda$ varies through the cardinals?<br /><br />This is addressed by Shelah's classification theory. Historically, the first step was Morley's categoricity theorem (1965) which states:<br /><br /><ul><li><i>If </i>$T$ <i>is a first-order theory in a countable language and </i>$T$<i> is categorical in some uncountable cardinal, then it is categorical in all uncountable cardinals.</i></li></ul><div>The proof of this theorem, which was the content of the lectures, involves the ideas of stability, indiscernibles, saturated models, and splitting types. It's somewhat different from the one I recall from the basic model theory class I took many years ago.</div><div><br /></div><div>To begin with, we can define a rank $R$ on sets of formulas (i.e., types) with parameters in some large saturated model $\mathcal{C}$ (the "monster model"). Let $p$ be a set of formulas. Then, working in $\mathcal{C}$,</div><div><ul><li>$R(p)=-1$ if $p$ is not satisfiable.</li><li>$R(p)\ge 0$ if $p$ is satisfiable.</li><li>$R(p)\ge \alpha+1$ if for any finite $p_0\subseteq p$, there is a formula $\psi$ such that $R(p_0\cup\{\psi\})\ge \alpha$ and $R(p\cup\{\neg \psi\})\ge \alpha$.</li></ul><div>The rank $R(p)$ is then defined inductively to be the minimum value so that all of the above conditions are satisfied. Note: this isn't what is known as Morley rank. Andrew Marks noticed that this rank is the Cantor-Bendixson rank on the Stone space of complete types.</div></div><div><br /></div><div>Some properties of the rank:</div><div><ul><li>(Monotonicity) If $p\vdash q$ then $R(p)\le R(q)$.</li><li>(Finite character) For every $p$, there is a finite $p_0\subseteq p$ so that $R(p)=R(p_0)$. </li><ul><li>Proof: If $R(p)=\alpha$, there is a finite $p_0$ witnessing $R(p)\not\ge \alpha+1$, and monotonicity gives the reverse inequality.</li></ul><li>(Invariance) If $f$ is an automorphism of $\mathcal{C}$, then $R(p)=R(f(p))$.</li><ul><li>Proof is by induction on the rank.</li></ul></ul><div><b>Definition: </b>$T$ is $\lambda$-<i>stable </i>if for any $A\subseteq C$ of size $\lambda$, $|S^n(A)|\le \lambda$. Here $S^n(A)$ is the set of complete $n$-types over $A$, that is, maximal satisfiable sets of formulas with parameters over $A$ and free variables $x_1,\ldots, x_n$.</div></div><div><br /></div><div><b>Theorem: </b>Let $T$ be a theory in a countable language. Then $T$ is $\aleph_0$-stable iff $R(\{\bar{x}=\bar{x}\})<\infty$, i.e., has some ordinal value. In fact, if these equivalent conditions hold, then $R(\{\bar{x}=\bar{x}\})<\omega_1$.</div><div><i><br /></i></div><div><i>Proof: </i>Suppose $R(\{\bar{x}=\bar{x}\})\ge \omega_1$. We will inductively construct a complete binary tree whose nodes are finite sets of formulas $p_\eta$ for $\eta\in 2^{<\omega}$ and whose branches will give $2^{\aleph_0}$ many different complete types, contradicting stability. For the construction, we will maintain that $R(p_\eta)\ge\omega_1$.</div><div><br /></div><div>Let $p_\emptyset=\{\bar{x}=\bar{x}\}$. Given $p_\eta$, there are formulas $\psi_{\eta,i}(\bar{x},\bar{a}_{\eta,i})$ for each $i<\omega_1$ witnessing that $R(p_\eta)\ge i+1$. Using the fact that the language of $T$ is countable together with $\aleph_0$-stability, there are $\psi$ and $t$ so that for an unbounded set of $i<\omega_1$, $\psi=\psi_{\eta,i}$ and $t=\mathrm{tp}(\bar{a}_{\eta,i})$ (the set of all formulas satisfied by $\bar{a}_{\eta,i}$, over the finitely many parameters in $p_\eta$). Pick $a_\eta$ realizing $t$. Then define </div><div><ul><li>$p_{\eta\circ 0}=p_\eta\cup\{\psi(\bar{x},\bar{a}_\eta)\}$</li><li>$p_{\eta\circ 1}=p_\eta\cup\{\neg\psi(\bar{x},\bar{a}_\eta)\}$</li></ul><div>Using invariance of rank under automorphisms and the fact that in $\mathcal{C}$ for any two tuples realizing the same type there exists an automorphism sending one to the other, the ranks of these sets of formulas are at least $i$ for an unbounded set of $i<\omega_1$, so they must be $\ge\omega_1$, allowing the construction to continue. The branches of the tree we construct can be extended to complete types, and the construction ensures that each of these complete types is distinct (for two different branches, look at the first place of disagreement).</div></div><div><br /></div><div>For the converse, assume $R(\bar{x}=\bar{x})<\infty$ and $T$ is not stable. Then there are $A\subseteq \mathcal{C}$, $|A|\le \lambda$ such that there are distinct $\{p_i:i<\lambda^+\}\subseteq S^n(A)$. By assumption, for any $i<\lambda^+$, there is $\alpha_i$ so that $R(p_i)=\alpha_i$. By finite character, there is $q_i\subseteq p_i$ finite with $R(q_i)=R(p_i)=\alpha_i$. By counting, $|\{q_i:i<\lambda^+\}|\le \omega$. Let $i\neq j$ be such that $q_i=q_j$, so $p_i,p_j$ are different completions of $q_i=q_j$. This means there is a formula $\psi$ with $\neg\psi\in p_i$ and $\psi\in p_j$. This gives $R(q_j)\ge R(p_j)+1$, a contradiction to the choice of $q_j$. $\Box$.</div><div><br /></div><div><br /></div>Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-46065308356261950512015-01-26T14:07:00.001-08:002015-01-28T21:13:43.831-08:00Spencinar: Forcing clubs in stationary subsets of $P_\kappa(\lambda)$<div>The first part of this talk follows closely the paper "Forcing closed unbounded sets" by Uri Abraham and Saharon Shelah ([AS]). The second part will follow the paper "Nonsplitting subset of $P_\kappa(\kappa^+)$ by Moti Gitik ([G]).</div><div><br /></div>We have previously seen that given a stationary $S\subseteq \omega_1$, there is a forcing which has the $\omega_2$-c.c. and is $<\omega_1$-distributive (and hence preserves all cardinals) which adds a club $C\subseteq S$, namely the forcing of closed bounded subsets of $S$, ordered by end-extension (Baumgartner--Harrington--Kleinberg).<br /><div><br /></div><div>This generalizes to higher regular cardinals $\kappa$ assuming some cardinal arithmetic (GCH with $\kappa$ the successor of a regular cardinal suffices) and <i>fatness</i> of $S$, which says that for any club $E\subseteq \kappa$, $S\cap E$ contains closed subsets of arbitrarily large order type $<\kappa$ (this is a result of J. Stavi).</div><div><br /></div><div>The focus of this talk will be to obtain analogues for these theorems for subsets of $P_\kappa(\lambda)=\{x\subseteq \lambda: |x|<\kappa\}$.</div><div><br /></div><div>This situation is not as clear as for subsets of ordinals, and in fact there are some sets whose stationarity is quite absolute (By <i>stationary </i>and <i>club</i> I mean here in the sense of Jech, see this previous <a href="http://billset.blogspot.com/2014/11/learning-project-1-part-1-preliminaries.html" target="_blank">post</a>). For example, Theorem 6 in [AS] gives a stationary subset of $P_{\aleph_1}(\omega_2)$ whose stationarity is preserved by any forcing which preserves $\aleph_2$:</div><div><br /></div><div><b>Theorem: </b>Let $W\subseteq V$ be a transitive inner model such that $\omega_2^W=\omega_2^V$, and let $S=(P_{\aleph_1}(\omega_2))^W$. Then $S$ is stationary in $V$.</div><div><br /></div><div><i>Proof: </i>The idea of the proof is to fix an arbitrary club $C\subset P_{\aleph_1}(\omega_2)$ and find submodels which are ordinals, or somehow coded by ordinals in $W$. Then these submodels will automatically be in $S$.</div><div><br /></div><div>By Kueker's theorem, there is a function $F:[\omega_2]^{<\omega}\rightarrow \omega_2$ so that any $x\in P_{\aleph_1}(\omega_2)$ closed under $F$ is in $C$ (this uses the fact that we're working on $\aleph_1$ and $\aleph_2$, but this is a minor technical point). Let $\alpha$ be an ordinal closed under $F$. If $\alpha$ is countable, then we're done; otherwise $\alpha$ has cardinality $\aleph_1$, hence also $W$-cardinality $\aleph_1$, so fix a bijection $h:\omega_1\rightarrow \alpha$ in $W$. Then there is $\xi<\omega_1$ with $h[\xi]$ closed under $F$, and $h[\xi]$ is in $W$ and hence in $S$, so we're done again. $\Box$</div><div><br /></div><div>In [G], it's shown that any forcing which adds reals to $W$ destroys the club-ness of $S$.</div><div><br /></div><div>This paper gives some examples of sets whose stationary can be destroyed. We won't go through those results here. Instead, we now turn towards a result in [G] which also gives examples of this kind.</div><div><br /></div><div><div>Let $\kappa$ be supercompact in $W$, and let $V$ be obtained from $W$ by Radin forcing. We won't need to know much about Radin forcing, just:</div><div><ul><li>the continuum function and all cardinalities are preserved,</li><li>there is a club $C\subseteq \kappa$ of $W$-inaccessible cardinals,</li><li>$\kappa$ remains (sufficiently) supercompact in $V$. </li></ul></div><div>From now on, work in $V$. Let $A$ be any subset of the set of all $t\in P_\kappa(\kappa^+)\cap W$ such that $V\vDash ``|t| \textrm{ is a successor cardinal}"$.</div><div><br /></div><div>We will find a forcing that adds a club in $S:=P_\kappa(\kappa^+)\setminus A$ which is $<\kappa$-distributive (this is crucial, so that $P_\kappa(\kappa^+)$ itself does not change), and has the $\kappa^+$-c.c.</div><div><br /></div><div>Define the poset $\mathbb{P}$ to be the collection of subsets of $S$ of size $<\kappa$ which have a maximum element and are closed under increasing unions, ordered by end-extension. </div><div><br /></div><div><i>Claim: </i>$\mathbb{P}$ is $<\kappa$-distributive.</div><div><br /></div><div>Let $\langle D_\beta: \beta<\alpha\rangle$ be a sequence of dense open subsets of $\mathbb{P}$ for some $\alpha<\kappa$. Then we will prove that $\bigcap_{\beta<\alpha} D_\beta$ is also dense. So let $x\in \mathbb{P}$.</div><div><br /></div><div>Let $M\prec (H(\theta),\in,\triangleleft,A,\langle D_\beta\rangle,x,\ldots)$ be an elementary substructure of size $\kappa$ so that $M\cap \kappa^+\in \kappa^+$ and $M$ is closed under $<\kappa$-sequences. Let $g\in W$ be a bijection from $\kappa$ onto $M\cap \kappa^+$. Using $<\kappa$-closure of $M$, construct $\langle M_i:i<\kappa\rangle$ a continuous IA chain of elementary submodels of $M$ of size $<\kappa$ so that $\alpha+1\subseteq M_0$ and $g``i\subseteq M_i$. There is a club $E\subseteq \kappa$ such that for every $i\in E$, $i\in C$ and $M_i\cap \kappa^+=g``i$. Let $\langle i_\beta:\beta<\kappa\rangle$ be the increasing enumeration of $E$, and let $N_\beta=M_{i_\beta}$.</div><div><br /></div><div>We will inductively construct a decreasing sequence of conditions $\langle x_\beta:\beta\le \alpha\rangle$ such that:</div><div><br /></div><div><ul><li> $x_0\le x$,</li><li> $x_{\beta+1}\in D_\beta$,</li><li> $N_\beta\cap \kappa^+=\max(x_\beta)$,</li><li> $x_\beta\in N_{\beta+1}$.</li></ul></div><div><br /></div><div>Take $x'_0\in N_0$, $x'_0\le x$, and let $x_0=x'_0\cup\{N_0\cap \kappa^+\}$.</div><div><br /></div><div>Now we construct $x_\beta$, assuming that $x_\gamma$ has been constructed for every $\gamma<\beta$. If $\beta=\gamma+1$ for some $\gamma$, then pick $x'_\beta$ to be the $\vartriangleleft$-least in $N_\beta\cap D_\beta$ extending $x_\gamma$, and define $x_\beta=x'_\beta\cup\{N_\beta\cap \kappa^+\}$. This is a valid condition since $N_\beta\cap \kappa^+$ has $W$-cardinality in $C$, so it can't be a member of $A$.</div><div><br /></div><div>If $\beta$ is limit, then let $x'_\beta$ be the closure of $\bigcup \{x_{\gamma}:\gamma<\beta\}$ under increasing unions, and $x_\beta=x'_\beta\cup\{N_\beta\cap \kappa^+\}$. By internal approachability, $x_\beta\in N_{\beta+1}$.</div><div><br /></div><div>It is easy to see that:</div><div><i>Claim: </i>For every $\gamma<\beta$, $x_\beta$ is an end-extension of $x_{\gamma}$.</div><div><br /></div><div>We now check that $x_\beta\in \mathbb{P}$. If not, then there is $t\in x_\beta\cap A$. Since $t\subseteq N_\beta\cap \kappa^+$, we must have $|t|^W\le i_\beta$. Furthermore, $|t|^W$ is a successor cardinal of $W$ and $i_\beta$ is W-inaccessible, so $|t|^W<i_\beta$.</div><div><br /></div><div>Since $i_\beta$ is $W$-regular, there is some $\gamma<\beta$ with $t\subseteq g``i_\gamma=N_\gamma\cap \kappa^+$. But this is impossible by the claim. </div></div><div><br /></div><div>The $\kappa^+$-c.c. follows by a standard $\Delta$-system argument.</div><div><br /></div><div>Gitik used this forcing as the building block of an iteration to produce a stationary subset $Z$ of $P_\kappa(\kappa^+)$ so that the non-stationary ideal restricted to that stationary set is $\kappa^+$-saturated, which is very interesting in light of results that show that the whole nonstationary ideal is not saturated. Another way to look at this is that it shows the consistency of the failure of a natural analogue of Solovay's splitting theorem for stationary subsets of $P_\kappa(\lambda)$.</div><div><br /></div><div>Assuming that $\kappa$ is supercompact, the set $Z$ of all $t\in P_\kappa(\kappa^+)\cap W$ such that $W\vDash ``|t| \textrm{ is a successor cardinal}"$ is stationary. The idea of the iteration is that we will destroy the stationary of the "bad sets" to while maintaining the stationary of $Z$. Maintaining the stationarity of $Z$ is achieved through extending the supercompactness embedding to the final model, but this is not an easy task in this case.<br /><br /><i>An earlier version of this post had several occurrences of $V$ which should have been $W$.</i></div>Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-18512876942927203932014-12-30T23:59:00.000-08:002014-12-31T00:00:51.304-08:00Good and bad terminology in mathematicsHappy holidays! I hope everyone is having a restful vacation. Here's a post which is just for a bit of fun---don't take it too seriously!<br /><br />A lot of people complain about bad terminology in mathematics. I don't really consider myself to be one of those people, but I have to admit they have a point. The choice of a word we use to represent a concept greatly influences the way we read and perceive it. Here are examples of terminology I like and dislike, with some whimsical alternatives for fun. It turned out to be much harder than I expected to come up with good terminology. Leave a comment if you can think of something to add to these lists.<br /><div><br /></div><div><b>Like</b></div><div><ul><li><i>Adjoint</i>: This word seems to only exist in mathematics. It captures a general pattern that appears frequently in different contexts; several formally related concepts share this terminology. Appropriately, it suggests pairing or duality.</li><li><i>Club set</i>: Short for "closed and unbounded". This neat portmanteau helps emphasize that the conjunction of the two properties is somehow more the sum of its parts.</li><li><i>Compactness</i>: This is such a carefully nuanced word for a subtle and fundamental property which occurs in many different contexts in mathematics, although I think it can take some getting used to. It really captures the idea of some kind of finitary character, or a strong notion of "smallness".</li><li><i>Mouse, weasel</i>: Inner model theory words that give a mischievous flavor to a difficult subject.</li><li><i>Mixing</i>: from ergodic theory. It's a gerund, which helps describe this dynamical situation well.</li><li><i>Rational numbers</i>: This is a nice play on words. It makes $\mathbb{Q}$ feel very concrete and friendly and is probably derived from the representation of these numbers as ratios of integers. </li><li><i>Supercompact cardinal</i>: sometimes terminology doesn't totally make sense, it just sounds cool. I have to admit that hearing this word early made me curious about set theory.</li></ul></div><div><br /></div><div><b>Dislike</b></div><div><ul><li><i>Amenable group</i>: This seems to be a pun that only makes sense with British pronunciations. According to Wikipedia, the original name given by von Neumann was "messbar", or "measurable" in English. Of course, this name is even worse. <i>Alternatives: </i>Maybe something like "well-measured" would be better.</li><li><i>Antichain</i>: It's actually a catchy word, if only it didn't have two closely related but nonequivalent meanings. In order theory people use it to mean a collection of pairwise incomparable elements of a poset, while set theorists would say it is a collection of pairwise incompatible elements. Let the order theory people take back the outdated term "Sperner system".</li><li><i>Cardinal collapsing</i>:<i> </i>This term from set theory is really convenient and probably no one else in the world has a problem with it. My gripe is that it's somewhat inaccurate and easily replaced by simpler terms. "Collapsing" a cardinal refers to a forcing extension where a particular ordinal is no longer a cardinal, in other words, its cardinality is decreased (as measured by ordinals) in the extension. The word "collapse" is a bit overloaded (it seems better suited to describe things like Mostowski collapse). <i>Alternatives: "</i>decardinalizing", "cardinality decreasing".</li><li><i>Commutative diagram</i>: To commute just means to go from one place to another. This got twisted into the property that $ab=ba$; I guess I can kind of see that they are moving past each other. So we can also use this for functions $f,g:X\rightarrow X$ to say $fg=gf$ (a special kind of commutative square). But what about commutative triangles, some functions that satisfy $f=gh$? <i>Alternatives</i>: "freely composing", or maybe something made-up and descriptive like "ambicompositional".</li><li><i>Countable chain condition</i> (c.c.c.): This one from set theory is unpopular among some people I know, since it's a property of posets that means there are no <i>un</i>countable <i>anti</i>chains (and I don't mean Sperner systems here). I saw one paper (Abraham--Shelah: Forcing closed unbounded sets) which called this the c.a.c., for countable antichain condition, which seems like a reasonable alternative. I recall that there's actually a good historical reason for this terminology, though I'm not sure exactly what that was.</li><li><i>Maths</i>: OK, so it's not really in the spirit of the other things, and maybe its just my American crudeness, but this sounds totally wrong to me.</li><li><i>One-to-one</i>: I thought it was OK until someone pointed out to me that it sounds like each member of the domain maps to a unique member of the codomain (what some people call <i>single-valued</i>). This has been the source of some confusion in classes I've TA'ed. <i>Alternatives</i>: just use the already existing technical-sounding words "injective" and "surjective."</li><li><i>Proper forcing</i>: It's just a bit too vague and authoritarian for me. <i>Alternatives: </i>Maybe something like "internally generic forcing".</li></ul></div>Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-27997139093723311492014-12-14T05:42:00.000-08:002015-01-05T19:19:09.337-08:00Spencinar flashback: Approachability and stationary reflection at $\aleph_\omega$The Spencinar has been continuing as usual since the Thanksgiving break. Two weeks ago, Spencer talked about diamond principles. I'm working on these notes still. Last week, I talked about precipitousness of the nonstationary ideal (the subject of the learning project #1).<br /><br />I'm about to retire this old seminar notebook, so I thought I would record here a Spencinar that I gave over the summer about the approachability property. This will also provide some useful background for future posts.<br /><br />This material comes mostly from Eisworth's friendly handbook chapter, where I was originally inspired to pursue the line of research that I'm on. I'm going to focus on the following result of Shelah's (interpreted through Eisworth's chapter):<br /><br /><b>Main Theorem: </b>If $\aleph_\omega$ is a strong limit, then $\rm{Refl}(\aleph_{\omega+1})$ implies the approachability property at $\aleph_\omega$.<br /><br />This result is unexpected since approachability is a rather weak "non-reflection" principle. It's interesting since Magidor's model of $\rm{Refl}(\aleph_{\omega+1})$ satisfies approachability property at $\aleph_\omega$, and in fact uses this to show that stationarity is preserved after forcing. It's also interesting since the proof seems to use special properties of $\aleph_\omega$, giving an example of the phenomenon that this singular cardinal in particular seems to have a lot of ZFC structure. This is nice to understand, because there is an important open question asking whether the failure of singular cardinals hypothesis at $\aleph_\omega$ implies approachability (and this is consistently false for larger singular cardinals).<br /><br /><b>I. $\mathrm{AP}_\mu$: review.</b><br /><b><br /></b>Shelah defined the ideal $I[\lambda]$ for a regular cardinal $\lambda$ by:<br /><br />$S\subseteq I[\lambda]$ iff there is<br /><br /><ol><li>a sequence $\langle a_\alpha:\alpha<\lambda\rangle$ of bounded subsets of $\lambda$ and</li><li>$C\subseteq \lambda$ club,</li></ol><br /> so that for every $\delta\in S\cap C$, there is $A_\delta\subseteq \delta$ unbounded of order-type $\rm{cf}(\delta)$ so that<br /><br /><ul><li>$\{A\cap \beta:\beta<\delta\}\subseteq \{a_\beta:\beta<\delta\}$ (or in words, all initial segments of $A_\delta$ are enumerated in $\bar{a}$ at a stage before $\delta$.</li></ul>Such $\delta$ is said to be <i>approachable</i> with respect to $\bar{a}$. It can be shown (cf. Eisworth's handbook chapter) that $I[\lambda]$ is a normal ideal on $\lambda$.<br /><br />For $\mu$ a singular cardinal, the <i>approachability property </i>$\rm{AP}_\mu$ is the statement $\mu^+\in I[\mu^+]$. (Some other authors denote this by $\rm{AP}_{\mu^+}$. Restating the definitions, this means there is $\bar{a}$ and a club of $\delta<\mu^+$ of points which are approachable with respect to $\bar{a}$.<br /><br /><b>2. Elementary substructures</b><br /><br />We will define a $\lambda$-approximating sequence to be a $\subseteq$-increasing sequence $\mathcal{M}=\langle M_\alpha:\alpha<\lambda\rangle$ of elementary substructures of $(H(\theta); \in, \triangleleft)$ for sufficiently large regular $\theta$ so that $\lambda\in M_0$ and for all $\alpha$, $|M_\alpha|<\lambda$ and $M_\alpha\cap \lambda\in \lambda$. Most importantly, we require that $\langle M_\alpha:\alpha\le \beta\rangle\in M_{\beta+1}$. This is a slight strengthening of the concept of "IA sequence" which we saw in the learning project.<br /><br />If $\mathcal{M}$ is a $\lambda$-approximating sequence, then define $S[\mathcal{M}]$ to be the set of $\delta<\lambda$ such that $M_\delta\cap\lambda=\delta$, there is a cofinal $a\subseteq \delta$ of order-type $\rm{cf}(\delta)$ such that every inital segment of $a$ is in $M_\delta$.<br /><br />This gives a useful characterization of approachability. $I[\lambda]$ is just ideal generated by nonstationary sets together with sets of the form $S[\mathcal{M}]$. For a given $\bar{a}$, let $\mathcal{M}$ be a $\lambda$-approximating sequence with $\bar{a}\in M_0$ and $E\subset\lambda$ be club so that $M_\alpha\cap\lambda=\alpha$ for all $\alpha\in E$. In this club, the set of points approachable with respect to $\bar{a}$ is contained in $S[\mathcal{M}]\cap E$.<br /><br />Conversely, given a sequence $\mathcal{M}$, let $\bar{a}$ be the sequence of bounded subsets of $\lambda$ in $\bigcup_\alpha M_\alpha$, and $E$ be the club of $\delta$ so that $\{a_\alpha:\alpha<\delta\}$ is an enumeration of the bounded subsets of $M_\delta$.<br /><br /><b>3. Colorings</b><br /><br />We can also rephrase notions of approachability in terms of colorings, given some extra assumptions. Here $S^\lambda_\kappa$ denotes the set of points of cofinality $\kappa$ below $\lambda$.<br /><br /><b>Theorem 1</b>: Suppose $\kappa<\lambda$ be regular with $2^{<\kappa}<\lambda$. If $d:[\lambda]^2\rightarrow \omega$ and $\mathcal{M}$ is a $\lambda$-approximating sequence containing $\{\kappa, d\}$, then for every $\delta\in S[\mathcal{M}]\cap S^\lambda_\kappa$, there is a cofinal $H\subseteq \delta$ homogeneous for d.<br /><br /><i>Proof</i>: If $\delta\in S[\mathcal{M}]\cap S^\lambda_\kappa$, let $\{\alpha_i:i<\kappa\}$ cofinal in $\delta$ such that $\{a_i:i<\zeta\}\in M_\delta$ for all $\zeta<\kappa$. By induction on $i<\kappa$, we can define $\epsilon_i,f_i$ so that:<br /><br /><ol><li>$\epsilon_0=\alpha_0$.</li><li> $f_i:i\rightarrow \theta$, $f_i(j)=d(\epsilon_j,\delta)$.</li><li>$\epsilon_i$ is the least $\alpha$ so that for all $j<i$, $\alpha>\alpha_j,\epsilon_j$ and $d(\epsilon_j,\alpha)=d(\epsilon_j,\delta)$ for all $j<i$, if such exists. The construction ends if no such exists.</li></ol>This last condition says that the function $d(\epsilon_i,\epsilon_j)$ depends only on $i$, where $i<j$, and uses $\delta$ as a "reference point". Let $i^*$ be the length of the construction.<br /><br />We show the construction goes up to $\delta$. By part of the definition of $S[\mathcal{M}]$, $M_\delta\cap\lambda=\delta$. Since $\kappa\in M_\delta$, $M_\delta$ must be $<\kappa$-closed, so it contains $f_i$ for all $i<i^*$ (this uses $2^{<\kappa}<\lambda$). This means the construction above can be done in $M_\delta$ and therefore all $\epsilon_i<\delta$, $\delta$ witnesses condition in 3.<br /><br />The proof concludes by finding $\xi$ so that $\{i<\kappa:d(\epsilon_i,\delta)=\xi\}$ is unbounded, giving a homogeneous set. $\Box$<br /><br />This motivates yet another conception of "approachability".<br /><br /><b>Definition: </b>For $d:[\lambda]^2\rightarrow\chi$ (some $\chi$), define $S(d)$ to be the set of $\delta<\lambda$ for which there is a cofinal $H_\delta\subseteq \delta$ homogeneous for $d$, and $S^*(d)=\lambda-S(d)$.<br /><br />So $S(d)$ is club for every $d$ if the approachability property holds at the predecessor of $\lambda$ (under the hypotheses of Theorem 1).<br /><br />Actually, under those hypotheses, the approachability ideal is generated by a single set over the nonstationary ideal. We can see this result in a way by using colorings. It turns out there is a certain class of colorings whose members have "all of the complexity" of the general case.<br /><br /><b>Definition</b>: $d:[\lambda]^2\rightarrow\omega$ is a coloring as above with $\lambda=\mu^+$. We say $d$ is <i>normal</i> if $\{\beta<\alpha:d(\beta,\alpha)<i\}|<\mu$ for all $i<\rm{cf}(\mu)$. We say $d$ is <i>transitive</i> if $d(\alpha,\gamma)\le \mathrm{max}\{d(\alpha,\beta),d(\beta,\gamma)\}$ for all $\alpha<\beta<\gamma<\lambda$.<br /><br />Normal transitive colorings are not difficult (but a little tricky) to construct. We'll just take this as an unproven fact (this construction was used, for example, in John's Spencinar talk about Martin's Maximum).<br /><br /><b>Proposition:</b> If $\mu$ is strong limit and $d$ is a normal, transitive coloring of $\mu^+$, then there is $\bar{a}$ so that almost every point of $S(d)$ is approachable with respect to $\bar{a}$.<br /><br /><i>Proof: </i>Let $\langle a_\xi:\xi<\lambda\rangle$ enumerate all subsets of the form $\{\beta<\alpha:d(\beta,\alpha)<i\}$ in some order. This is fine since $\lambda^{<\lambda}=\lambda$ ($\mu$ strong limit). Then for any $\delta\in S(d)$ of uncountable cofinality there exists a cofinal $H_\delta\subseteq\delta$ homogeneous for $d$. Actually, $d(\beta,\delta)$ is bounded in $\omega$: by transitivity, if $\beta_1<\beta_2<\delta$, then $d(\beta_1,\delta)\le \max\{i,d(\beta_2,\delta)\}$, and since $\delta$ has uncountable cofinality and $d(\beta,\delta)$ is increasing in $\beta\in H_\delta$ (if above $i$), then $d(\beta,\delta)$ is bounded. So almost every point of $S(d)$ is approachable. $\Box$<br /><br />So the proposition gives a really nice characterization of approachability property under the hypotheses of Theorem 1: $\mathrm{AP}_\mu$ holds iff there exists (equivalently for all) normal transitive colorings, $S(d)$ contains a club of points of uncountable cofinality.<br /><br /><b>4. Proof of Main Theorem</b><br /><br />Now we start working towards the proof of the theorem. The first result is that $S^*(d)$ can only reflect in itself.<br /><br /><b>Lemma 2: </b>If $S^*(d)\cap \alpha$ is stationary in $\alpha$, then $\alpha\in S^*(d)$.<br /><br /><i>Proof:</i> Otherwise $\alpha\in S(d)$, so let $H\subset \alpha$ be cofinal in $\alpha$ and homogeneous for $d$. Then every limit point of $H$ must be in $S(d)$ by the definition of $S(d)$, so $S^*(d)$ is disjoint from a club in $\alpha$. $\Box$<br /><br />So if the approachability property fails, then there is a coloring $d$ (namely, any normal transitive one) for which $S^*(d)\cap \mathrm{cof}(>\omega)$ is stationary. Take $n<\omega$ such that $S=S^*(d)\cap S^{\aleph_{\omega+1}}_{\aleph_{n+1}}$ is stationary.<br /><br />The next claim is the crucial fact giving a non-reflecting stationary set.<br /><br /><i>Claim: </i>$S$ cannot reflect at points of cofinality $>2^{\aleph_n}$.<br /><br /><i>Proof of Claim: </i>Suppose $S$ reflects at $\tau$. If $\tau>2^{\aleph_n}$, then $\tau^{<\aleph_{n+1}}=\tau$. So we can construct a $\lambda$-approximating sequence containing all the relevant parameters which is $<\aleph_{n+1}$ closed. Then for any $\delta\in S^\tau_{\aleph_{n+1}}$ with $M_\delta=\delta$, any $A\subseteq \delta$ of order-type ${\aleph_{n+1}}$ has all of its initial segments in $M_\delta$. This shows that $S^\tau_{\aleph_{n+1}}\in I[\tau]$. This is impossible by Theorem 1, which says almost all points below $\tau$ are in $S(d)$, so $S$ cannot reflect at $\tau$. $\Box$<br /><br />Now fix $k<\omega$ so that $2^{\aleph_n}=\aleph_{n+k}$. Such exists by $\mu$ strong limit. Define $S_0=S$, and $S_{i+1}$ to be the reflection points of $S_i$. Observe that if $\delta\in S_i$, then $\mathrm{cf}(\delta)\ge \aleph_{n+1+i}$, since the set of points below an ordinal with cofinality less than that ordinal is club. This implies that $S_k$ is empty, so let $i^*<\omega$ be maximal so that $S_{i^*}$ is stationary. Then $S_{i^*}$ does not reflect stationarily often. Hence we have proven the main theorem.<br /><br /><b>5. Normal scales?</b><br /><b><br /></b>Let's try to apply some of these ideas. This section requires a basic knowledge of pcf theory. Let $\langle f_\alpha:\alpha<\mu^+\rangle$ be a scale.<br /><b><br /></b>The "difference function" of the scale is a transitive function $d:[\mu^+]^2\rightarrow\omega$ defined so that $d(\alpha,\beta)$ for $\alpha<\beta$ is the supremum of all $n$ so that $f_\alpha(n)\ge f_\beta(n)$. In light of the previous explorations on approachability, it is natural to ask if it can ever be normal.<br /><br /><b>Proposition</b>: Normal scales don't exist.<br /><br /><i>Proof: </i>Let $\vec{f}$ be a scale on $\langle \mu_i:i<\omega\rangle$. Pick $\gamma_1<\mu_1$ so that $B_1=\{\alpha:f_\alpha(1)<\gamma_1\}$ has size $\kappa^+$. Let $A_0$ be a set of $\mu_0$ many $\alpha<\mu^+$ in $B_1$.<br /><br />If $n>0$, then pick $\gamma_{n+1}$ s.t. $\gamma_{n+1}>\sup_{\alpha\in A_{n-1}} f_\alpha(n+1)$ and $B_{n+1}=\{\alpha\in B_n: f_\alpha(n+1)<\gamma_{n+1}\}$ has size $\mu^+$. Let $A_n$ be a set of $\mu_{n}$ many from $B_{n+1}$.<br /><br />Then $\bigcup_n A_n$ has size $\kappa$ and is bounded by $n\mapsto \gamma_n$.<br /><div><br /></div>Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-15808390329654172892014-11-29T03:12:00.002-08:002015-09-11T02:35:20.727-07:00Learning project #1: a theorem<a href="http://billset.blogspot.com/2014/11/learning-project-1-foreman-magidor.html">0th post</a> in this series<br /><a href="http://billset.blogspot.com/2014/11/learning-project-1-part-1-preliminaries.html" target="_blank">1st post</a> (updated with some more facts about IA structures at the end)<br />(edited 12/10/2014 to improve clarity)<br /><br />We'll explain the proof of Theorem 27 of FMS:<br /><br /><b>Theorem 27:</b> Suppose $\kappa$ is a supercompact cardinal and $\mu<\kappa$ is regular. Then in $V^{\rm{Col}(\mu,<\kappa)}$, the nonstationary ideal on $\mu$ is precipitous.<br /><br />We'll follow the proof in FMS, trying to use Foreman's chapter for some new insights. I think the material is generally covered much better in the Handbook chapter than in the article.<br /><br />Now we have Lemma 1 for proving ideals are precipitous, we can carry out this gameplan.<br /><br />Let $G$ be a generic for $\rm{Col}(\mu,<\kappa)$, and <span style="color: #0b5394;">let's think in the generic extension $V[G]$. We will show:</span><br /><span style="color: #0b5394;"><br /></span><span style="color: #0b5394;"><i> Main Claim:</i> Let $\mathfrak{A}$ be an expansion of $\langle H(\lambda),\in,\Delta\rangle$ </span><span style="color: #0b5394;">(where $\lambda$ is some regular cardinal above, say, $2^{2^{2^\mu}}$)</span><span style="color: #0b5394;">. Then for almost all (in the sense of the nonstationary ideal) $N\prec\mathfrak{A}$ with $N\in \rm{IA}$, $|N|<\mu$, and $N\cap \mu$ an ordinal:</span><br /><span style="color: #0b5394;"><br /></span><span style="color: #0b5394;">For all maximal antichains $\mathcal{A} \in N$ of $P(\mu)/NS$, there is an $A\in \mathcal{A}$ such that </span><br /><br /><ol><li><span style="color: #0b5394;">$N\cap \mu\in A$ and</span></li><li><span style="color: #0b5394;">letting $N^A$ equal the Skolem hull of $N\cup \{A\}$, $N^A\cap \mu=N\cap \mu$ in $\mathfrak{A}$.</span></li></ol><div><span style="color: #0b5394;">Let's explain the usefulness of these conditions. To apply our Lemma 1, let $\mathcal{A}=\langle A \rangle$ be a tree of maximal antichains for $P(\mu)/\rm{NS}$ with underlying tree $T\subseteq \langle\mu^+\rangle^{<\omega}$. We will construct a branch $f:\omega\rightarrow \mu^+$ so that $\bigcap_n A_{f\upharpoonright n}\neq \emptyset$.</span></div><div><span style="color: #0b5394;"><br /></span></div><div><span style="color: #0b5394;">We'll construct the branch $f$ in $\omega$ stages. </span></div><div><span style="color: #0b5394;"><br /></span></div><div><span style="color: #0b5394;">Take $N_0$ containing $\mathcal{A}$ as an element. Let $s_0=\langle\alpha_0\rangle$ be so that $A_{s_0}$ witnesses (1) and (2) with antichain equal to the first level of $\mathcal{A}$. From now on, use the notation $s_i:=\langle \alpha_0,\ldots, \alpha_{i}\rangle$. </span></div><div><span style="color: #0b5394;"><br /></span></div><div><span style="color: #0b5394;">At the $i+1$st stage, let $N_{i+1}:=(N_i)^{\alpha_i}$ (the Skolem hull of $N_i\cup\{\alpha_i\}$ in $\mathcal{L}$). Pick $\alpha_{i+1}$ so that (1) and (2) are satisfied for $N=N_{i+1}$ and $s=\langle \alpha_0,\ldots, \alpha_{i+1}\rangle$ in the maximal antichain consisting of $\langle A_s:s \textrm{ extends }s_i\rangle$ together with some set not containing the single point $N\cap \mu$ (in order to do this construction, we will need to show that the property that $N_i\in\rm{IA}$ is maintained, which is Lemma 2 from last time). </span></div><div><span style="color: #0b5394;"><br /></span></div><div><span style="color: #0b5394;">We have $N_i\cap \mu\in A_{s_i}$ for all $i$, but $N_i\cap\mu$ was always just equal to $N\cap \mu$, so $N\cap \mu$ would be in the intersection of all of the $A_{s_i}$. The key point of absorbing the index of the member of the antichain was so that the construction could continue in a coherent way, ensuring we are actually building a branch of $T$. </span>(Foreman's chapter further develops these ideas, leading to the notion of "catching antichains".)</div><div><br /></div><div><span style="color: #0b5394;">Let us now prove the main claim. Suppose there is a stationary $S\subseteq \rm{IA}$ of structures for which the conclusion of the main claim fails. The idea of the proof is that the supercompact gives us enough reflection of $S$ to catch the antichain. </span>Let $\mathbb{P}=\rm{Col}(\mu,<\kappa)$ and let $j:V\rightarrow M$ be an $|H(\lambda)|$-supercompact embedding. Since $\mathbb{P}$ is $\kappa$-c.c., <span style="color: #38761d;">we can force to find $H\subseteq j(\mathbb{P})$ which contains $G$ as a subset, so we can extend $j$ to $\hat{j}:V[G]\rightarrow M[H]$ in $V[H]$. </span></div><div><br /></div><div><i>Subclaim: </i>$S$ reflects to a set of size $\mu$, i.e., there is $Y\subseteq \lambda$ so that $\mu\subseteq Y$ and $|Y|=\mu$ so that $S\cap P(Y)$ is stationary in $P(Y)$.</div><div><br /></div><div><i>Proof of Subclaim</i>: <span style="color: #38761d;">By Lemma 3 from last time, $\hat{j}(S)\cap P(\hat{j}``H(\lambda))$ is stationary in $V[H]$. Now because of the collapse, $|\hat{j}``H(\lambda)|=\mu$ and $\mu\subseteq \hat{j}``H(\lambda)$ since $\kappa$ is the critical point. </span><span style="color: #274e13;">By closure of $M$ (and, it can be seen, of $M[H]$, $\hat{j}``H(\lambda)\in M[H]$. So ($\hat{j}$ of) the statement of the subclaim holds in $M[H]$,</span><span style="color: #38761d;"> so by elementarity</span><span style="color: #134f5c;"> </span><span style="color: #0b5394;">the subclaim holds in $V[G]$.</span></div><div><br /></div><div><span style="color: #0b5394;">Returning to the proof of the main claim, let $Y$ be given by the subclaim and let $f:\mu\rightarrow Y$ be a bijection. Let $T:=\{\delta<\mu: f``\delta\in S\textrm{ and }\delta=f``\delta\cap\mu\}$. Then it is easy to see that $T$ is stationary, using the fact that $S$ reflects to $Y$. By maximality, there is $A\in\mathcal{A}$ such that $T\cap A$ is stationary. So we can find an IA structure $N'\prec \mathfrak{A}$ containing $A, f$ and with $N'\cap \mu \in T\cap A$. Take $N$ to be $f``(N' \cap\mu)$, so $N\in S$ by definition of $T$. By the second property in the definition of $T$, we also have $N\cap \mu=N'\cap \mu$. But $N'$ contains $A$, so the Skolem Hull of $N\cup\{A\}$ is contained in $N'$ and therefore has the same supremum below $\mu$, and would show that $N$ cannot be in $S$.</span></div><div><br /></div><div>This finishes the proof. </div><div><br /></div>Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-64205607339109103242014-11-20T21:06:00.001-08:002015-02-28T22:52:49.113-08:00Spencinar #6: The Galvin-Prikry TheoremToday Zach Norwood talked about the Galvin-Prikry Theorem.<br /><div><br /></div><div>Prerequisites: basic topology, notions of category, familiarity with Ramsey theory is helpful for motivation. Last week's Spencinar <a href="http://billset.blogspot.com/2014/11/spencinar-5-happy-and-mad-families-part.html" target="_blank">post</a> will be referenced occasionally but only in inessential remarks.<br /><div><br /></div><div>The Galvin-Prikry Theorem is a Ramsey result that is perhaps surprising because it is an example of an "infinite exponent" partition property. This means it deals with colorings of infinite subsets of the underlying space. With the Axiom of Choice, none of the usual partition relations hold with infinite exponents.</div><div><br /></div><div>The Galvin-Prikry Theorem gets around this by only worrying about definable partitions of $[\omega^\omega]$. In order to state the theorem, let's make some definitions:</div><div><br /></div><div><b>Definition</b>: $Y\subseteq [\omega]^\omega$ is <i>Ramsey </i>if there is $A\in [\omega]^\omega$ with $[A]^\omega\subseteq Y$ or $A^\omega\subseteq Y^c$. (Here $Y^c$ is the complement of $Y$.) I'll informally say that $A$ in the first case is $Y$-homogeneous and $A$ in the second case is $Y^c$-homogeneous.</div><div><br /></div><div>$Y$ can also be thought of as a coloring $[\omega]^\omega\rightarrow 2$. As in last week's post, we think of $[X]^\omega$ as the set of all increasing infinite sequences of $X$, or sometimes in a slight abuse of notation as the set of infinite subsets of $X$.</div><div><br /></div><div><b>Galvin-Prikry Theorem:</b> If $Y$ is Borel, then $Y$ is Ramsey.</div><div><br /></div><div>Here the topology on $Y$ is generated by sets of the form $\{X: x \textrm{ is an initial segment of }X\}$. The proof, originally due to Ellentuck, will actually go through a finer topology which is more suited to the situation at hand. Notice the similarity with the Mathias forcing from last week. </div><div><br /></div><div><b>Definition: </b>The Ellentuck topology is generated by sets of the form </div><div>$$[s,B]^\omega:=\{X\in [\omega]^\omega: s \textrm{ is an initial segment of } X, x\setminus s\subseteq B\},$$</div><div>where $s\in [\omega]^{<\omega}$ and $B\in [\omega]^\omega$.</div><div><br /></div><div>We will use "$\ast$-" to indicate the use of the Ellentuck topology over the usual one. Notice that all Borel sets are $\ast$-Borel.<br /><br /></div><div>Fix $Y\subseteq [\omega]^\omega$. We say $B\in[\omega]^\omega$ <i>accepts </i>$s$ (into $Y$) if $[s,B]^\omega\subseteq Y$. We say $B$ <i>rejects </i>$s$ if no infinite subset of $B$ accepts $s$. Informally, $B$ accepts $s$ if $s$ is long enough and $B$ is thin enough so that every subset of $B-\max(s)$ compatible with $s$ is in $Y$. $B$ rejects $s$ if $s$ is too short or $B$ concentrates on the wrong place for acceptance to occur. Although perhaps its best to think just in terms of the Ellentuck topology.</div><div><br /></div><div>Some easy remarks:</div><div><ul><li>if $B$ accepts $s$, then so do all infinite subsets of $B$.</li><li>if $B$ rejects $s$, then so do all infinite subsets of $B$ and all supersets of $B$.</li></ul>The main part of the proof is the following lemma, which clarifies the relationship between acceptance and rejection.</div><div><br /></div><div><b>Galvin-Prikry Lemma</b>: For $Y\subseteq [\omega]^\omega$, exactly one of the following holds:</div><div><ol><li>There is $B\in[\omega]^\omega$ that accepts $\emptyset$, or</li><li>there is $B \in [\omega]^\omega$ which rejects all of its finite subsets.</li></ol>A $B$ that accepts $\emptyset$ is just one that is $Y$-homogeneous, and a $B$ which rejects all of its finite subsets is exactly one for which no $\ast$-open subset of $[B]^\omega$ is $Y$-homogeneous. For those familiar with forcing and last week's seminar, this is a special version of the Prikry lemma for the empty condition in Mathias forcing. Not having read the original source, I wonder if Prikry noticed the analogy with Prikry forcing?</div><div><br /></div><div><i>Proof</i>: Assume that no $B$ accepts $\emptyset$, so $\omega$ rejects $\emptyset$. We will construct recursively</div><div><ul><li>infinite subsets of $\omega$: $B_0\supseteq B_1\subseteq B_2\supseteq\cdots$, and</li><li>natural numbers $a_1<a_2<\cdots$</li></ul></div><div>so that $a_i\in B_i$ and $B_i$ rejects all subsets of $\{a_1,\ldots,a_{i-1}\}$. If this can be done, then $\{a_1,a_2,\ldots\}$ rejects all of its finite subsets. This kind of construction is typical in Ramsey theory.</div><div><br /></div><div>By our assumption, $B_0=\omega$ works. At the $k$th stage of the construction, suppose that $B_0,\ldots, B_k$ and $a_1,\ldots,a_{k-1}$ have already been constructed. We want to define $a_k>a_{k-1}$ in $B_k$ and $B_{k+1}\subseteq B_k$ so that $B_{k+1}$ rejects all subsets of $\{a_1,\ldots,a_k\}$. </div><div><br /></div><div>If such $a_k, B_{k+1}$ did not exist, then we will define a sequence $C_1\supseteq C_2\supseteq\ldots$ of subsets of $B_k$, $b_1<b_2<\ldots$ with $b_{i+1}\in C_i$ and a finite subset $\bar{s}$ of $B_k$ so that $\{b_1,b_2,\ldots\}$ accepts $\bar{s}$. But this contradicts the inductive assumption on $B_k$. (This auxiliary construction is another version of the "typical" Ramsey construction building a kind of homogeneous object in the other direction.)</div><div><br /></div><div>Choose $b_1>a_{k-1}$ in $B_k$. $B_k$ doesn't reject all subsets of $\{a_1,\ldots,a_{k-1},b_1\}$ (otherwise we could pick $b_1$ to be $a_k$ and $B_k$ to be $B_{k+1}$), so we can take $C_1\in [B_k]^{\omega}$ and $S_1\subseteq\{a_1,\ldots,a_{k-1},b_1\}$ so that $C_1$ accepts $s_1$. We must have $b_1\in s_1$ since we assumed that $B_k$ rejects all subsets of $\{a_1,\ldots,a_{k-1}\}$. Put $\bar{s}_1=s_1-\{b_1\}$. </div></div><div><br /></div><div>Continuing the construction, at stage $i+1$ pick $b_{i+1}>b_k$ in $C_i$, $C_{i+1}\in[C_i]^\omega$, and $s_{i+1}\subseteq \{a_1,\ldots,a_{k-1},b_{i+1}\}$ so that $C_{i+1}$ accepts $s_{i+1}$. Let $\bar{s}_{i+1}=s_{i+1}-\{b_{i+1}\}$.</div><div><br /></div><div>Now the $\bar{s}_i$ must be constant for infinitely many $i$, and let this constant value be $\bar{s}$. Then $\{b_1,b_2,\ldots\}$ accepts $\bar{s}$. $\Box$</div><div><br />After this proof, we stopped using the language of acceptance and rejection, which made it easier for me to follow since I don't think that "rejection" is that easy to grasp in the flow of things.</div><div><br /></div><div>As a first application of the Galvin-Prikry lemma,</div><div><br /></div><div><b>Lemma 1: </b>$\ast$-open sets are Ramsey.</div><div><br /></div><div><i>Proof</i>: Let $Y\subseteq [\omega]^\omega$, and take $B$ satisfying the conclusion of the Galvin-Prikry lemma. In the first case, $B$ accepts $\emptyset$, so we're done. In the second case, $B$ rejects all of its finite subsets. We'll show that $B$ is $Y^c$-homogeneous. Otherwise, there is $A$ an infinite subset of $B$ so that $A\in Y$. Using that $Y$ is $\ast$-open, it follows that there is a $\ast$-neighborhood of $A$, say $[s,A]^\omega$, with $[s,A]^\omega\subseteq Y$. But this means that $A$ accepts $s$, contradicting that $B$ rejects $s$. $\Box$</div><div><br /></div><div>Now we introduce a strengthening of the Ramsey property:</div><div><br /></div><div><b>Definition: </b>A set $Y\subseteq [\omega]^\omega$ is <i>completely Ramsey</i> if for every $s\in[\omega]^<\omega$ and every $B\in[\omega]^\omega$, there exists $C\in [B]^\omega$ so that either $[s,C]^\omega\subseteq Y$ or $[s,C]^\omega\subseteq Y^c$. If the second possibility holds for all $s,B$, then $Y$ is called <i>Ramsey null</i>.<br /><br />Thus, completely Ramsey means that a local Ramsey property holds on any $\ast$-open set. This is useful because topological properties are local in this sense; a key idea of this proof will be to show that certain Ramsey properties are equivalent to topological properties in the Ellentuck topology.<br /><br /><b>Lemma 2: </b>$\ast$-open sets are completely Ramsey. As a corollary, $\ast$-closed sets are completely Ramsey.<br /><br /><i>Proof</i>: Let $s\in [\omega]^{<\omega}$ and $B\in [\omega]^\omega$ be arbitrary. The idea of the proof is to use a homeomorphism from $[\omega]^\omega$ to $[s,B]^\omega$ to transfer the result of Lemma 1. Enumerate $B=b_1<b_2<b_2<\cdots$. Then we define $f:[\omega]^\omega\rightarrow [s,B]^\omega$ by $X\mapsto s\cup \{b_i:i\in X\}$ (let's make the harmless assumption that $\min(B)>\max(s)$). It is easy to see that $f$ is $\ast$-continuous, so $f^{-1}Y$ is $\ast$-open, so Ramsey by Lemma 1. Now there is a $C'\in [\omega]^\omega$ so that $[C']^\omega\subseteq Y$ or $Y^c$. We can take $C=f(C')$ to witness completely Ramsey at $[s,B]^\omega$. $\Box$<br /><br />We begin to realize the "key idea" mentioned above.<br /><br /><b>Lemma 3:</b> $Y\in[\omega]^\omega$ is Ramsey null iff it is $\ast$-nowhere dense. (Reminder: a set is nowhere dense iff its closure has empty interior.)<br /><br /><i>Proof:</i> The forward direction follows easily from the definitions: $\ast$-nowhere dense just means that for any basic $\ast$-open set $[s,B]^\omega$, there is a basic $\ast$-open subset $[t,C]^\omega$ disjoint from $Y$. Ramsey null is the prima facie stronger assertion where we cannot change the "stem" part $s$.<br /><br />Conversely, take $[s,B]^\omega$ a basic $\ast$-open set. The $\ast$-closure $\bar{Y}$ of $Y$ is completely Ramsey by Lemma 2. If there were $C\in [B]^\omega$ with $[s,C]^\omega\subseteq \bar{Y}$, then $[s,C]^\omega$ would be a subset of the $\ast$-interior of $\bar{Y}$, contradicting $\ast$-nowhere dense. $\Box$<br /><br />Let's recall some of the basic notions of category, the topological notion of largeness. The meager sets are countable unions of nowhere dense sets. It's a basic result (the Baire category theorem) that under some flexible hypotheses, a space is nonmeager in its own topology, so the category notions are nontrivial.<br /><br />It turns out that Lemma 3 can be improved to $\ast$-meager sets:<br /><br /><b>Lemma 4: </b>If $Y$ is $\ast$-meager, then it is Ramsey null.<br /><br /><i>Proof</i>: Set $Y=\bigcup_{n=0}^\infty Y_n$, $Y_n$ is $\ast$-nowhere dense. The proof is roughly a diagonal argument, similar to some of the earlier ones. Let $s,B$ be arbitrary. We use several applications of Lemma 3 to construct $B_0\supseteq B_1\supseteq B_2\supseteq \cdots$ subsets of $B$ and an increasing sequence of $x_i\in B_i$ so that for each $n$,<br /><br /><div style="text-align: center;">$[s\cup F,B_n]^\omega\subseteq Y_n^c$ for all $F\subseteq\{x_0,\ldots,x_{n-1}\}$.</div><div style="text-align: center;"><br /></div><div style="text-align: left;">So at the $n$th stage, we use Lemma 3 successively to shrink $B_{n-1}$ so that the statement above holds for each $F\subseteq\{x_0,\ldots,x_{n-1}\}$ (one application of Lemma 3 for each $F$).</div><div style="text-align: left;"><br /></div><div style="text-align: left;">Then the sequence of $\{x_0,x_1,\ldots\}$ witnesses completely Ramsey for $s,B$. $\Box$</div><div style="text-align: left;"><br /></div><div style="text-align: left;">So $\ast$-nowhere dense, $\ast$-meager, and Ramsey null are all the same thing.</div><div style="text-align: left;"><br /></div><div style="text-align: left;">We can finally put it all together to get the main theorem of this talk, which implies the Galvin-Prikry Theorem as a corollary (since Borel sets in the usual topology are easily $\ast$-Baire, being in the $\sigma$-ideal generated by the $\ast$-open sets.). Recall that a set $Y$ is <i>Baire </i>(or has the property of Baire) iff there is a meager set $W$ and an open set $Z$ so that $Y= Z\triangle W$ is open (these are the "measurable" sets in terms of category).</div><div style="text-align: left;"><br /></div><div style="text-align: left;"><b>Theorem: </b>$Y$ is $\ast$-Baire iff it is completely Ramsey.</div><div style="text-align: left;"><br /></div><div style="text-align: left;"><i>Proof</i>: For the forward direction, suppose $Y$ is $\ast$-Baire, so there is a $\ast$-meager set $W$ and $\ast$-open $Z$ with $Y=Z\triangle W$. Take $s\in[\omega]^{<\omega}$ and $B\in [\omega]^\omega$ arbitrary. By Lemma 5, there is $C\in [B]^\omega$ so that $[s,C]^\omega\subseteq W^c$. By Lemma 1, there is $D\in[C]^\omega$ so that $[s,D]^\omega\subseteq Z$ or $Z^c$. By choice of $C$, this means that $[s,D]^\omega\subseteq Z-W\subseteq Y$ or $[s,D]^\omega\subseteq Z^c-W\subseteq Y^c$.</div><div style="text-align: left;"><br /></div><div style="text-align: left;">Conversely, assume $Y$ is completely Ramsey. We will show that $Y-\rm{int}(Y)$ is $\ast$-meager. It suffices to show that it's Ramsey null. Take $s\in[\omega]^{<\omega}$ and $B\in [\omega]^\omega$ arbitrary. There is $C\in [B]^\omega$ so that $[s,C]^\omega\subseteq Y$ or $Y^c$. In the first case, $[s,C]^\omega$ is contained in the interior of $Y$, and in the second case, $[s,C]^\omega$ is disjoint from $Y$, so in either case $[s,C]\subseteq Y-\rm{int}(Y)$. $\Box$</div><br />Zach ended by giving an open question. Mathias proved that if it is consistent that an inaccessible cardinal exists, then it is consistent that projective sets are Ramsey (this statement holds in Solovay's model, obtained by collapsing an inaccessible). But is the inaccessible necessary? Does the statement that projective sets are Ramsey have consistency strength above just ZFC?<br /><br /><br /><br /><br /><br /><br /></div>Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com2tag:blogger.com,1999:blog-9123839977705274913.post-43501860232094873252014-11-16T22:08:00.001-08:002015-01-26T13:00:29.727-08:00Learning project #1, part 1: preliminaries<a href="http://billset.blogspot.com/2014/11/learning-project-1-foreman-magidor.html">0th post</a> in this series (updated with some more motivation):<br />(other relevant posts for reference: <a href="http://billset.blogspot.com/2014/10/spencinar-3-precipitous-ideals-part-1.html" target="_blank">Spencinar #3: precipitous ideals</a>)<br /><br /><br />Let's begin! Remember that one of our goals is<br /><br /><b>Theorem: </b>$\rm{Col}(\mu,<\kappa)$ makes the nonstationary ideal restricted to $[\mu]^{<\mu}$ precipitous.<br /><br />First, let's define notions of stationarity on sets of the form $[\lambda]^{<\kappa}=\{x\subseteq \lambda: |x|<\kappa\}$. We will have $\kappa$ regular.<br /><br />There are two different notions here. If $X$ is a set and $C\subseteq P(X)$, then $C$ is <i>strongly</i> club if there is a structure $\mathfrak{A}$ on $X$ with countably many function symbols so that $C$ is the set of elementary substructures of $\mathfrak{A}$ (or equivalently, the set of substructures closed under a function $X^{<\omega}\rightarrow X$). $C$ is J-club if it is unbounded in the $\subseteq$ order on $[\lambda]^{<\kappa}$ and closed under increasing unions of size less than $\kappa$. It turns out the two notions are closely connected, since a result of Kueker says that the filter generated by the J-club sets is the filter generated by the strongly club sets together with all sets of the form $\{x\in [\lambda]^{<\kappa}:x\cap \kappa \in \kappa\}$ (this means that the ordinals of $x\cap \kappa$ are an initial segment of all ordinals).<br /><br />We can correspondingly define weakly stationary (resp. J-stationary) sets as those that intersect every strongly club (resp. J-club) set. For our purposes, strongly club and weakly stationary sets are the right notions, and we will refer to them from now on without the adverbs.<br /><br />In this post, we will get a simple criterion for precipitousness. Read the Spencinar #1 or #3 posts for basic information about generic ultrapowers.<br /><br />Our notation will be that $Z$ is a set and $I$ is an ideal on $Z$. We will use $I^+$ to denote the collection of $I$-<i>positive sets</i>, i.e., the set $P(Z)-I$. We will use $I^\wedge$ to mean the dual filter of $I$, i.e., the collection of sets of the form $Z-A$ for some $A\in I$. The equivalence class of $S\subseteq Z$ in $P(Z)/I$ will be denoted by $[S]$.<br /><br /><b>Definition:</b> A <i>tree of maximal antichains $\mathcal{A}$ for </i>$P(Z)/I$ <i>below </i>$S$ is an underlying tree $T\subseteq \mathrm{ON}^{<\omega}$ labeled with $\langle A_s: s\in T\rangle$ elements of $P(Z)$ such that<br /><br /><ol><li>$A_\emptyset = S$,</li><li>The levels of the tree form increasingly refined maximal antichains of $P(Z)/I$ restricted to $S$, i.e., for each $s\in T$, the set $\{[A_{s\ast \alpha}]:s\ast\alpha\in T\}$ is a maximal antichain below $A_s$ ($\ast$ denotes concatenation). Further, let us assume that $A_{s\ast \alpha}\subseteq A_s$. Denote the levels by $\mathcal{A}_n$, $n<\omega$. </li></ol><b>Lemma 1: </b>(FMS p. 31, originally Jech--Prikry) $I$ is precipitous iff for every $S\in I^+$ and every tree $\mathcal{A}$ of maximal antichains for $P(Z)/I$ restricted to $S$, there is a branch $f$ of the tree so that $\cap_{n<\omega} A_{f\upharpoonright n}$ is nonempty.<br /><br /><i>Proof</i>: If $I$ is precipitous, and $\langle A_s: s\in T$ is a tree of maximal antichains below some $S\in P(Z)$, then consider the <span style="color: #0b5394;">generic ultrapower (see older posts for references) by $P(Z)/I$ restricted to $[S]$. This is a map</span><br /><span style="color: #0b5394;">$$j:V\rightarrow M\subseteq V[G]$$</span><br /><span style="color: #0b5394;">defined in the forcing extension by $G$</span> which is generic for $P(Z)/I$ restricted to $[S]$. <span style="color: #0b5394;">We will think of $G$ as a $V$-ultrafilter extending the dual filter of $I$.</span><br /><br />Let's review the construction of this ultrapower. The elements are represented by functions $F: Z\rightarrow V$ in $V$, and <span style="color: #073763;">we have </span><span style="color: #0b5394;">Los's theorem which says for a formula</span> $\varphi$ in the language of set theory and $F_0,\ldots,F_n$, <span style="color: #3d85c6;">$M\vDash \varphi([F_0],\ldots,[F_n])$</span> <span style="color: #0b5394;">if and only if $\{z:V\vDash \varphi(F_0(z),\ldots,F_n(z))\}\in G$.</span><br /><br /><span style="color: #3d85c6;">In $M$, let $\mathcal{B}=j(\mathcal{A})$ and $i$ be the element represented in the ultrapower by the identity function on $Z$.</span><br /><br /><span style="color: #0b5394;">For each $n<\omega$, there must be a unique $A_{s_n}\in \mathcal{A}_n$ so that $i\in j(A_{s_n})$: this $A_s$ is the one in $G$ (such $A_s$ must exist by a basic density argument using the fact that $\mathcal{A}_n$ is a maximal antichain, and it must be unique). The sequence of these $\langle A_{s_n}:n<\omega\rangle$ can be computed in $V[G]$ and is a branch through $\mathcal{B}$.</span> <span style="color: #3d85c6;">Then there must be a branch in $M$ through the subtree of $\mathcal{B}$ consisting of those nodes which are labeled by a set containing $i$ as an element. (Otherwise, in $M$ there would be a rank function $f$ on this subtree taking ordinal values such that $f(B_s)<f(B_t)$ if $s$ is below $t$,</span> <span style="color: #0b5394;">and this would have to be in $V[G]$, so there couldn't be a branch in $V[G]$.</span> <span style="color: #0b5394;">Note that this is an important pattern of argument that is very common in many different places in set theory).</span><br /><br /><span style="color: #3d85c6;">Now this branch is a branch through $\mathcal{B}$ with nonempty intersection (containing $i$, for one) </span>so by elementarity there is such a branch through $\mathcal{A}$.<br /><br />Conversely, assume that $I$ is not precipitous. Then there is $S\subseteq Z$ such that $[S]$ forces that the generic ultrapower is well-founded. By maximality of the forcing language, we can find names $\dot{F}_n$ such that<br /><br /><ol><li>$[S]\Vdash \dot{F}_n:Z\rightarrow V$,</li><li>$[S]\Vdash \dot{F}_n\in V$,</li><li>$[S]\Vdash ``M \vDash [\dot{F}_{n+1}]\in [\dot{F}_n]''$. </li></ol><br />We can build a tree of maximal antichains $\mathcal{A}$ below $[S]$ such that<br /><br /><ul><li>a condition $A_s$ on the $n$th level decides the value of $\dot{F}_n$, say as $f^s_n$,</li><li>if $s$ is the predecessor of $t$ in the underlying tree, then $f^t_{n+1}(z)\in f^s_n(z)$ for all $z\in A_t$.</li></ul>If we have a tree of maximal antichains with just the first property, we can throw out sets in $I$ from each node to get the second property.<br /><br />This tree has no branch with nonempty intersection, otherwise this would give an infinite descending sequence in $V$. $\Box$<br /><br /><br />Another thing we will need is the notion of an <i>internally approachable </i>(IA) structure. Let $\lambda$ be sufficiently large regular cardinal and consider the structure $\mathfrak{A}=\langle H(\lambda),\epsilon,\Delta,f_i\rangle$ where the $f_i$ are countably many function symbols and $\Delta$ is a fixed well-order of $H(\lambda)$ needed for certain Skolem hull arguments. An elementary substructure $N\prec \mathfrak{A}$ is internally approachable iff it can be written as $N=\bigcup_{j<\delta}N_\delta$ for some $\delta$ such that for all $\beta\in \delta$, $\langle N_\alpha:\alpha<\beta\rangle\in N$ (this definition is slightly weaker than other common definitions of IA structures). Sometimes such an $N$ will be said to be internally approachable of length $\delta$.<br /><br />Because of the way these structures are built in layers, an IA structure can do some pretty "meta" computations (as we will see). This enables us to do some inductive constructions, where the IA condition gives a kind of strengthened inductive hypothesis.<br /><br />First we have a basic lemma about IA structures which is useful in many contexts.<br /><br /><b>Lemma 2: </b>Let $N\prec \langle H(\lambda),\epsilon,\Delta$ be IA of length $\delta$ for $\delta<\lambda$. Suppose $a\in y$ for some $y\in N$. Then the Skolem hull of $N\cup\{a\}$ computed in $H(\lambda)$ is IA of length $\delta$.<br /><br /><i>Proof</i>: Let $\langle N_\alpha:\alpha<\delta\rangle$ witness approachability. For each $\alpha<\delta$, let $N^*_\alpha$ be the closure of $N_\alpha\cup\{a\}$ under all functions $H(\lambda)\rightarrow H(\lambda)$ in $N_{\alpha+1}$. The $N^*_\alpha$ are elementary substructures of $H(\lambda)$ that witness approachability for the Skolem hull of $N\cup\{a\}$: if $\beta<\delta$, then $\langle N^*_\alpha:\alpha<\beta\rangle$ can be computed from $a$ and the sequence $\langle N_\alpha:\alpha\le \beta\rangle$. $\Box$<br /><br />Next is the main importance of IA structures in this project. It is very typical of applications of approachability:<br /><br /><b>Lemma 3: </b>Suppose $S\subseteq \rm{IA}$ be a stationary subset of $[H(\lambda)]^{<\mu}$, for some uncountable regular $\mu<\delta$. Then $S$ remains stationary in $[H(\lambda)^V]^{<\mu}$ after forcing with $\mathbb{P}=\rm{Col}(\mu,<\kappa)$ for any ordinal $\kappa$.<br /><br /><i>Proof</i>: Let $\dot{F}$ be a name for a function $H(\lambda)^{<\omega}\rightarrow H(\lambda)$ in the extension. Let $\lambda^*$ be a sufficiently large regular cardinal, and $N\prec \langle H(\lambda^*),\in,\Delta,\mathbb{P},\dot{F},S\rangle$ with $|N<\mu|$ and $N\cap H(\lambda)\in S$.<br /><br />Then $N\cap H(\lambda)$ is IA of some length $\delta<\mu$, witnessed by $\langle N_\alpha:\alpha<\delta\rangle$. We will define a decreasing sequence $\langle p_\alpha:\alpha<\delta\rangle$ of conditions in $\mathbb{P}$ so that<br /><br /><div><ol><li>For every $\beta<\delta$, there is $M_\beta\in N$ containing $N_\beta$ and each of the previous $M_\alpha$, $\alpha<\beta$, and so that for each $x\in M_\alpha$, $p_\beta$ forces there is $y\in M_\beta$ with $F(x)=y$.</li><li>For every $\beta<\delta$, $\langle p_\alpha:\alpha<\beta\rangle\in N$.</li></ol><div>We just pick the $\Delta$-least $p_\beta$ so that there is a $M_\beta$ satisfying the above, and then pick the $\Delta$-least such $M_\beta$. These things all exist in $N$ since $N$ is IA, and we can get (2) since this computation can be done <i>inside</i> $N$.</div></div><div><br /></div><div>Now use closure of $\mathbb{P}$ to find a $p$ extending all of the $p_\alpha$. This $p$ forces that $N\cap H(\lambda)$ is closed under $F$, so $S$ is stationary.</div><div><br /></div><br /><br />Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-25793684716030420472014-11-14T00:04:00.001-08:002014-11-20T21:25:36.603-08:00Spencinar #5: Happy and mad families, part 2Now we get to Asger's proof.<br /><br /><b>Definition: </b>If $A$ is an almost disjoint family and $B_0,B_1\subseteq A$, then $B_0$, $B_1$ have <i>uniformly bounded intersection by </i>$k$ if for any $x\in B_0$, $y\in B_1$, $x\cap y\subseteq k$.<br /><br /><b>Definition: </b>A <i>polarization </i>of $A$ is a countable partition $\{F_n\}_{n\in\omega}$ of $\{(x,y)\in A^2:x\neq y\}$ such that for each $n$, $\mathrm{proj}_0 F_n$ and $\mathrm{proj}_1 F_n$ have uniformly bounded intersection by some $k$.<br /><br />Here $\mathrm{proj}_0$ and $\mathrm{proj}_1$ are the projections to the left and right coordinates, respectively.<br /><br />The polarization will help us get to a countable situation where we can diagonalize. We will show the following lemmas:<br /><br /><b>Lemma 1: </b>$\mathbf{\Sigma}^1_1$ almost disjoint families have polarizations.<br /><br /><b>Lemma 2: </b>If an almost disjoint family has a polarization, then it is not maximal.<br /><br />This would prove Mathias's result again.<br /><br />To prove Theorem 2, we can use Lemma 2 plus the following (which we won't prove here):<br /><br /><b>Lemma 3: </b>$\mathrm{OCA}_\infty$ + every set of reals has the perfect set property implies that every almost disjoint family has a polarization. ($\mathrm{OCA}_\infty$ is a strengthening of the open coloring axiom)<br /><br /><b>Lemma 4: </b><b> </b>$\mathrm{OCA}_\infty$ holds in Solovay's model.<br /><br /><i>Proof of Lemma 1:</i> Suppose $T\subseteq [\omega]^{<\omega}\times [\omega]^{<\omega}\times [\omega]^{<\omega}$ is such that $p[T]:=\{(x,y)\in ([\omega]^{\omega})^2: \exists t \, (t,x,y)\textrm{ is a branch of T}\}$ is equal to $\{(x,y)\in A^2:x\neq y\}$ which exists since that set is analytic (this is a basic descriptive set theory representation of an analytic set).<br /><br />Consider the set of nodes $(\tau, r,s)$ such that every extension $(\tau',r',s')$ has $r'\cap s'=r\cap s$. Given such $(\tau,r,s)$, let $F=p[T_{(\tau,r,s)}]$. Then $\mathrm{proj}_0 F$ and $\mathrm{proj}_1 F$ have uniformly bounded intersection by $\max(r\cap s)$.<br /><br />We can perform a countable length derivative process, iteratively removing such nodes from $T$. This will terminate in countably many steps (since there are only countably many nodes) and the tree with no such nodes cannot have infinite branches, as this would contradict the almost disjointness of $A$.<br /><br /><i>Proof of Lemma 2</i>: First we make the following observation: if $A$ is an uncountable almost disjoint family and polarized by $\{F_n\}_{n\in \omega}$, then there is a sequence $B_0,B_1,\ldots$ of uncountable subsets of $A$ such that $B_i$ has uniformly bounded intersection with $\bigcup_{j>i} B_j$ and $B_0=\mathrm{proj}_0 F_n$ for some $n$.<br /><br />To prove the observation, take $n$ such that $\mathrm{proj}_0 F_n$ and $\mathrm{proj}_1 F_n$ are both uncountable. Take $B_0=\mathrm{proj}_0 F_n$. Now $\mathrm{proj}_1 F_n$ is polarized by $\{F_m\cap (\mathrm{proj}_1 F_n)^2\}_{m\neq n}$. So we can iterate this process for $\omega$ steps, giving the observation.<br /><br />Suppose $B_i$ are as above. Set $X_{B_i}=\bigcup B_i$. Note that the $X_{B_i}$ form an almost disjoint family, because of the uniform bound on the intersections of sets from $B_i, B_j$ for any given $i,j$.<br /><br />This process is the first step in an iterative procedure, $A_0=A$, $B_{0,i}=B_i$, $X_{0,i}=X_i$. The iteration will extend transfinitely. At stage $\alpha$, let $A_\alpha$ be $A$ minus the free ideal generated by all of the $X_{\beta,i}$, $\beta<\alpha$. Define $B_{\alpha,i}$ and $X_{\alpha,i}$ in the same way as above. This terminates after countably many steps, since each $B_{\alpha_i}$ is a different $\mathrm{proj}_0 F_n$. Let $\lambda$ be the length of this procedure: the termination condition is that $A_\lambda$ is countable. Now we can use the usual diagonalization to find a set almost disjoint from $A_\lambda$ and each of the $X_{\alpha_i}$. This set will be almost disjoint from every member of $A$, so $A$ cannot be maximal.Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-871683700944115742014-11-13T23:22:00.001-08:002015-09-23T12:15:25.958-07:00Spencinar #5: Happy and mad families, part 1Yesterday Andrew Marks gave the Spencinar. I was really excited to hear that Andrew would be coming to UCLA, since all of the talks I heard him give in various seminars and meetings inspired me (and everyone else in the audience as well). What makes his talks so special is that he emphasizes things with the most mathematical substance and sprinkles his presentation with insightful remarks, yet manages to stay completely rigorous. Hopefully, these notes reflect some of the energy and clarity he spoke with at the seminar.<br /><div><br /></div><div>Prerequisites: some descriptive set theory (tree representation of analytic sets, Shoenfield absoluteness), and basic knowledge of forcing is helpful.</div><div><br /></div><div>Andrew was motivated by some problems he was thinking about under the broad program of showing that there are no definable examples of certain kinds of objects whose constructions use the axiom of choice. An <i>almost disjoint family </i>is a collection of infinite subsets of $\omega$ with finite pairwise intersections. A <i>mad family </i>is a maximal such family, which exists by using Zorn's Lemma. The main result of this presentation was:</div><div><br /></div><div><b>Theorem 1 </b>(Mathias 1977): There are no $\mathbf{\Sigma^1_1}$ mad families.</div><div><br /></div><div>Andrew gave two different proofs of Theorem 1: one was the original argument using what is now known as Mathias forcing, together with an absoluteness argument, the other is a recent proof due to Asger Törnquist (which he talked about in the colloquium last year, see these <a href="http://webusers.imj-prg.fr/~jean.saint-raymond/DST/13/asger.pdf">slides</a>). The second proof is both purely elementary and generalizes well to other situations (even those not involving almost disjoint sets). Törnquist used these methods to prove: </div><div><br /></div><div><b>Theorem 2 </b>(Törnquist 2014): There are no mad families in Solovay's model.</div><div><br /></div><div>We will sketch Mathias's proof. You can skip this part if you are not familiar with the method of forcing (but if you are familiar with it, you will find these arguments extremely elegant!).</div><div><br /></div><div><b>Definition:</b> Mathias forcing $\mathbb{M}$ is the poset of pairs $(s, X)$ where $s\in[\omega]^{<\omega}$, $X\in[\omega]^{\omega}$ and $\max(s)<\min(X)$. The ordering is defined by $(r,Y)\le (s, X)$ iff $r$ end-extends $s$ and $r\setminus s\subseteq X$.</div><div><br /></div><div>So this is like a version of Prikry's forcing at $\omega$. It satisfies some similar properties which we will take as black boxes (proofs may be given in next week's seminar):</div><div><br /></div><div><b>Lemma: </b></div><div><ol><li>(Mathias property) If $G$ is Mathias generic (thought of as a member of $[\omega]^\omega$), and $G'\in [\omega]^\omega$ is a subset of $G$, then $G'$ is also generic for $\mathbb{M}$.</li><li>(Prikry property) If $\varphi$ is a formula in the forcing language and $(s,X)$ is a condition, then there is $Y\subseteq X$ infinite such that $(s,Y)\Vdash \varphi$ or $(s,Y)\Vdash \neg\varphi$ (we say that $(s,X)$ <i>decides</i> $\varphi$).</li></ol><div>On a digression, this forcing can be used to show that </div><div><br /></div><div><b>Proposition: </b>Every analytic set is Ramsey. ($A\subseteq [\omega]^{\omega}$ is <i>Ramsey </i>iff there is an $X\in [\omega]^{\omega}$ so that for all infinite subsets $Y\subseteq X$, $Y\in A$ iff $X\in A$. In other words, either all infinite subsets of $X$ are in $A$, or all of them are not in $A$.) </div><div><br /></div><div><i>Proof:</i> If $A\subseteq [\omega]^{\omega}$ is analytic, then there is $X\in [\omega]^{\omega}$ such that $(\emptyset, X)$ decides $\dot{G}\in A$. Note that $A$ used in the forcing language is actually a shorthand for the analytic definition of $A$ (which we will evaluate in the extension to be $A^{V[G]}$: it is not actually the name for the ground model set $A$. Let $G$ be the generic obtained by forcing with $\mathbb{M}$ below $(\emptyset, X)$. Then any infinite subset $G'$ of $G$ is still $\mathbb{M}$ generic containing $(\emptyset, X)$, so the question of $G'\in A^{V[G]}$ is decided the same way as the question for $G$ (this uses Shoenfield absoluteness between $V[G']$ and $V[G]$). So $A^{V[G]}$ is Ramsey in $V[G]$. By absoluteness, $A$ must be Ramsey (in the ground model).</div></div><div><br /></div><div>Mathias's proof uses a variant of Mathias forcing. We'll need some definitions first.</div><div><br /></div><div><b>Definitions:</b> </div><div><ul><li>A <i>free ideal </i>on $\omega$ is an ideal on $\omega$ containing all finite sets. A free filter is the dual of a free ideal.</li><li>A <i>free family </i>is the complement of a free ideal $I$ in $P(\omega)$.</li></ul></div><div>Informally, we think of a free ideal as the collection of "measure zero" sets, its dual filter as the collection of "full measure" sets, and the corresponding free family as the collection of "positive measure" sets.</div><div><br /></div><div>The main definition of this part is of a kind of free family where a certain kind of diagonal intersection can be taken:</div><div><br /></div><div><b>Definition:</b></div><div>A <i>happy family </i>is a free family $\mathcal{H}$ such that whenever $\{X_s:s\in [\omega]^{<\omega}\}$ are infinite subsets of $\omega$ so that any finite intersections of the $X_s$ are in $\mathcal{H}$, then there is an $X\in\mathcal{H}$ diagonalizing the $X_s$: that is,</div><div style="text-align: center;"><ul><li>if $\max(s)\in X$, then $\{n\in X:n>\max(s)\}\subseteq X_s$.</li></ul><div style="text-align: left;"><b>Proposition: </b>$[\omega]^\omega$ is happy. </div><div style="text-align: left;"><i><br /></i></div><div style="text-align: left;"><i>Proof: </i>A diagonal argument.<i> </i>Suppose $\{X_s:s\in [\omega]^{<\omega}\}$ are infinite subsets of $\omega$ with all finite intersections infinite. Pick the first element to be in $X_\emptyset$. At stage $i+1$, pick the next element greater than all previously chosen elements, and a member of the intersection of all $X_s$ with $\max(s)$ less than the element chosen at stage $i$ (this is possible since that intersection is infinite). This construction works. $\Box$</div><div style="text-align: left;"><br /></div><div style="text-align: left;"><b>Definition: </b>The forcing $\mathbb{M}_\mathcal{H}$ is the subposet of $\mathcal{M}$ of condition </div><div style="text-align: left;">whose second coordinate is in $\mathcal{H}$.</div><div style="text-align: left;"><br /></div><div style="text-align: left;">The "happy" property is what is needed so that the proofs of the Lemma on Mathias forcing go through. </div><div style="text-align: left;"><br /></div><div style="text-align: left;">Now we relate mad and happy families.</div><div style="text-align: left;"><br /></div><div style="text-align: left;"><b>Lemma:</b> If $A$ is a mad family, and $I$ is the free ideal generated by $A$, then $\mathcal{H}=P(\omega)\setminus I$ is a happy family.</div></div><div style="text-align: left;"><br /></div><div style="text-align: left;"><i>Proof. </i>Suppose $\{X_s:s\in [\omega]^{<\omega}\}$ are infinite subsets of $\omega$ with all finite intersections in $\mathcal{H}$. Let $X^0$ be constructed as in the proof of the previous proposition. If $X^0\in \mathcal{H}$, then we are done. Otherwise, there is $Y^0\in A$ such that $Y^0\cap X^0$ is infinite. Let $X^1_s=X_s\setminus Y_0$, and let $X_1$ diagonalize the $X^1_s$ as in the proof of the previous proposition, and so on.</div><div style="text-align: left;"><br /></div><div style="text-align: left;">At the end of this construction, we have $X^i$ all diagonalizing the collection of $X_s$ (in the sense of the family $[\omega]^\omega$), and so that $X^i\cap Y^i$ is infinite for all $i$. Take $X$ to be the set $\{x_i:i<\omega\}$ (enumerated in increasing order) so that $x_i\in X^{f(i)}\cap Y^{f(i)}\cap \bigcap\{X_s: \max(s)<x_{i-1} \}$ (forgetting the last intersection if $i=0$), where $f(i):\omega\rightarrow\omega$ is a function so that each $n\in\omega$ has infinite preimage. The point of the function $f$ is to ensure that $X$ has infinite intersection with each $Y^i$, so $X\in\mathcal{H}$. </div><div style="text-align: left;"><br /></div><div style="text-align: left;"><i>Sketch of the proof of Theorem 1</i>: If $A$ is a $\mathbf{\Sigma^1_1}$ mad family, then let $\mathcal{H}$ be the associated happy family. Force with $\mathbb{M}_\mathcal{H}$.</div><div style="text-align: left;"><br /></div><div style="text-align: left;">Claim: It is forced that $\dot{G}\in \mathcal{H}$ (again, $\mathcal{H}$ used here in the forcing language is the name for the set in the extension with the same definition as $\mathcal{H}$). </div><div style="text-align: left;"><br /></div><div style="text-align: left;">Suppose otherwise. Then there is $p=(s,X)$ and a name $\dot{a}$ for a member of $A$ so that $p$ forces that $\dot{G}$ is almost contained in $\dot{a}$, say, above some $n$. But it is forced that $X$ is not almost contained in $\dot{a}$, so we can strengthen $p$ to force some natural number larger than $n$ into $\dot{G}\setminus \dot{a}$.<br /><br /></div><div style="text-align: left;">So if $G$ is generic, any infinite subset $G'\subseteq G$ must also be in $\mathcal{H}^{V[G]}$. So $G$ is almost disjoint with any set in $A^{V[G]}$, hence by absoluteness $A$ is not mad, contradiction. $\Box$</div><div style="text-align: left;"><br /></div><div style="text-align: left;">I wasn't following along 100%, so some of the argument I used in the last few proofs might not be optimal (I just pieced them together to fill gaps in my notes).</div><div style="text-align: center;"><br /></div>Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-90384524030647717702014-11-11T01:10:00.000-08:002014-11-20T21:27:41.148-08:00Learning project #1: Foreman-Magidor-Shelah "Martin's Maximum, saturated ideals, and nonregular ultrafilters I"The paper "Martin's Maximum, saturated ideals, and nonregular ultrafilters I" by Foreman-Magidor-Shelah seems to be perhaps the most influential set theory paper in recent times (let's use a loose definition of "recent"). In this paper, they introduce the "maximal" forcing axiom known as Martin's Maximum, and then prove some consistency results from large cardinals about the saturation of "natural" ideals. We will focus on the second thing; for example:<br /><br />1. Forcing with $\rm{Col}(\mu,<\kappa)$ makes the nonstationary ideal restricted to $[\mu]^{<\mu}$ precipitous.<br /><br />2. Forcing with $\rm{Col}(\omega_1,<\kappa)$ gives an $\aleph_2$-saturated ideal on $\omega_1$.<br /><br />3. To make the nonstationary ideal on $\omega_1$ saturated, we must force with something more than the collapse. But this is also possible and can be done with $\kappa$-c.c. semiproper forcing.<br /><br />All of the conclusions above are also consequences of Martin's Maximum.<br /><br />Recall the definition and motivation of precipitous ideals from the beginning of a <a href="http://billset.blogspot.com/2014/10/spencinar-3-precipitous-ideals-part-1.html">previous post</a>. In that post, we gave the Jech--Magidor--Mitchell--Prikry construction of a precipitous ideal on $\omega_1$. These authors in fact proved that the nonstationary ideal on $\omega_1$ can be precipitous. The method was by an iterated forcing that at each step destroyed the stationarity of sets in the ideal constructed so far.<br /><br />However, the FMS paper managed to find a different consistency proof of precipitousness of the nonstationary ideal on $\omega_1$. In fact, the proof is general to any other regular cardinals, unlike the JMMP construction which uses something special about $\omega_1$ for destroying stationarity (although generalizations of that construction to other cardinals has been carried out in work of Gitik). The drawback is that the FMS construction uses quite large cardinals, whereas Gitik found the equiconsistency.<br /><br />I plan to at least cover (1.) and (2.) in a forthcoming series of posts. The plan is to prove (3.) sometime in a future learning project dealing with semiproper forcing, RCS iterations, and the other parts of the FMS paper.<br /><br />The posts will come out slowly because I want to make sure I fully understand each step. The references will be the FMS paper and Section 8 of Foreman's Handbook chapter.Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-64006246045238227072014-11-06T16:42:00.001-08:002014-11-20T21:27:21.169-08:00Spencinar #4: Weakenings of Martin's AxiomSpencer talked today about weakenings of Martin's Axiom of the form "All c.c.c. posets have a nice property." The nice properties were things like "$\omega_1$-Knaster", or "$\sigma$-centered." Actually, Todorcevic--Velickovic proved that $MA_{\aleph_1}$ is equivalent to "all c.c.c. posets are $\sigma$-centered". We saw how Martin's Axiom implies these other principles.<br /><br />The main thing Spencer talked about was that "All c.c.c. posets $\mathbb{P}$ have $\mathbb{P}\times\mathbb{P}$ c.c.c" implies that the continuum hypothesis fails. To prove this, he uses the CH to construct an <i>entangled linear order</i>, and shows that the poset of chains of this entangled linear order is c.c.c. but its square is not. The proof was very involved, and I'll try to write up some more about this when I have some time to think about the main underlying ideas. I remember reading about entangled linear orders from Shelah's book on cardinal arithmetic, but not being very motivated by it. This talk showed me the power of these linear orders when proving that the poset of chains is c.c.c.Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0tag:blogger.com,1999:blog-9123839977705274913.post-72545999318318069202014-11-06T16:32:00.003-08:002014-11-20T21:23:40.236-08:00Yuval Peres DLSThis week, Yuval Peres gave a Distinguished Lecture Series, which is a series of three talks for a general mathematical audience by a prominent mathematician visiting UCLA. I felt really compelled to attend these talks, since Peres seems to be working on very fundamental problems that have some interest for me. I read some of his work when I was in high school, and I was pleased to finally attend some of his lectures!<br /><br />This blog post deals with the talks on Tuesday and Wednesday. I won't give a comprehensive account, because my comprehension wasn't 100%.<br /><br />The first talk was about Search Games and Optimal Kakeya sets, based on joint work with Babichenko, Peretz, Sousi, and Winkler. He defined a game $G_n$ with two players "Hunter" and "Rabbit" on a cycle with $n$ vertices. At time $0$, each player chooses a position on the cycle. Then for each time step, the hunter moves to an adjacent position (or stays at the same position). The rabbit simultaneously moves to any position on the cycle. The players cannot see each other (Peres said to imagine the game is played in the dark). The game ends when Hunter and Rabbit occupy the same location.<br /><br />The punchline was that the optimal winning strategies for this game can be used to construct an "optimal" Kakeya set. This Kakeya set is the union of a certain number of triangles, and has the smallest area among all such Kakeya sets with the same number of triangles. A Kakeya set is just a subset of the plane that has a unit segment in every direction. The first construction of a Kakeya set was by Besicovitch, and these sets have some importance in harmonic analysis.<br /><br />But I was really fascinated by this simple game for its own interest.<br /><br />For technical reasons, it is easier to consider the game $G^*_n$ which runs for $n$ timesteps, and the Hunter and Rabbit move as above. The payoff for Hunter is 1 if he's successful, 0 otherwise. To make it a zero-sum game, the payoff for Rabbit is -1 if Hunter is successful, 0 otherwise. So von Neumann proved this<i> minimax theorem</i>, which asserts the existence of "optimal" strategies for both players. A strategy is a rule which tells a player what move to make, each move assigned a probability depending on the situation (previous moves and information known to the player). Then von Neumann's theorem (as I understood it from the talk) says that there is a value $v$ such that $v$ is both:<br /><br /><ul><li>the maximum possible expected payoff for any of I's strategies, assuming that II plays optimally <i>against that particular strategy </i>(so the max over all strategies of I of (the min over all strategies of II of the expected payoff of running the strategies against each other))</li><li>the minimum possible expected payoff for I for any of II's strategies, assuming that I plays optimally against that particular strategy (so $-v$ has the same role for II as $v$ had for I above).</li></ul><br />I tried to say it in a way which I think can be easily made precise. It's very nice that you can formulate this notion of optimality, and prove that optimal strategies exist. It seems like this definition of optimality can often involve being as unpredictable as possible, because if the opponent knows your strategy, he can use that information to predict your moves and play against that. So, barring situations where for example there is a sequence of moves with no counterplay, it seems to be greatly beneficial to move around randomly.<br /><br />What's the connection between $G_n$ and $G^*_n$? Peres answered this in his next slides: applying the minimax theorem to our situation, there is a value $p_n$ for the game $G^*_n$, which can be interpreted as the probability of capture under optimal play. Now we argue that in the original game $G_n$, the mean capture time in $G_n$ under optimal play is between $n/p_n$ and $2n/p_n$. The rabbit can just play his $G^*_n$ strategy for every block of time $n$, so he can ensure that the mean capture time is $\ge n/p_n$ (using linearity of expectation). The hunter can play his $G^*_n$ strategy for every other block of time $n$, using the odd blocks to move to the starting position for his next strategy. This ensures a mean capture time $\le 2n/p_n$ (again using linearity of expectation).<br /><br />He then went over some sample strategies for the players, involving staying still, moving in some direction at constant speed, etc. It was amazing because he involved the audience, asking them to try to figure out different strategies. I forgot exactly what $p_n$ turned out to be: I think it was something like $n^{-1/2}$? But the optimal strategy for the hunter turned out to be going at a random speed, like I suspected. The rabbit's optimal strategy actually involved not moving around too much: I stopped taking notes here because I was struggling to keep up with his arguments at this point. Someone in the audience gave an intuitive explanation of this, but I must admit I wasn't sure about this explanation either.<br /><br />I didn't know the minimax theorem before, so this talk was very eye-opening. I wonder how the proof of that theorem goes, since evidently it doesn't construct the optimal strategies (which seem to be found from methods special to the game at hand). If the argument is nice, I'll try to write a blog post about it. I wonder if these probabilistic strategies can be somehow generalized to the infinite situations that set theorists are interested in (probably just nonsense, I know!)<br />--------------------<br /><br />The DLS on Wednesday was about random walks on groups (which seems to just be a random walk on the Cayley graph of a group, each generator has different weights). It was a bit hard to follow for me, but he proved some nice results on the blackboard bounding the expected distance in the graph between the starting point and the $n$th step of the walk (this is the rate of escape). It reminded me a lot of IST 1 class from Caltech, since a lot of inequalities I learned there were used in the talk. Unfortunately, I won't post my notes about this talk.Bill Chenhttp://www.blogger.com/profile/02739700273094533125noreply@blogger.com0