Tuesday, October 28, 2014

Spencinar #3: Saturated ideals (part 2)

Now we'll construct an $\aleph_2$-saturated ideals on $\omega_1$. The construction is originally due to Kunen.

The idea is similar to the previous construction. We will look at the ideal induced by a large cardinal embedding $j$ after a collapsing the large cardinal $\kappa$ to become $\omega_1$. We know the quotient algebra is equivalent to the image of the collapse, so we hope that this is $\kappa^+$-c.c. To do this requires a huge cardinal, which gives a situation where where $j(\kappa)$ is also the amount of closure of the target model in $V$. We want to collapse to turn $j(\kappa)$ into $\kappa^+$, but in order to have a master condition to extend the embedding to the extension by this collapse, we cannot use the Levy collapse. Instead, we will use the Silver collapse. The first poset collapsing $\kappa$ to become $\omega_1$ must absorb the Silver collapse and so also cannot be the Levy collapse: we will construct a poset which will fulfill this purpose by design.

(Drinking game: consume a designated amount of an alcoholic beverage every time you read the word "collapse" in this post...)

Definition: The Silver collapse $S(\kappa,\lambda)$ is the forcing whose elements are partial functions $p: \kappa\times \lambda\rightarrow\kappa$ with domain of size $\le \kappa$ so that there is some $\eta<\kappa$ so that the domain is contained in $\eta\times \lambda$, and for all $(\alpha,\beta)$ in the domain, $p(\alpha,\beta)<\beta$.

Like the Levy collapse $\mathrm{Col}(\kappa,<\lambda)$, the Silver collapse adds surjections from $\kappa$ to everything less than $\lambda$ with uniformly bounded domain, but we are allowed to have some conditions with support of size equal to $\kappa$. It is $\lambda$-c.c., $<\kappa$-closed, and every regular cardinal of the ground model between $\kappa$ and $\lambda$ is collapsed with cofinality $\kappa$.

Start with a huge cardinal $\kappa$ and a huge embedding $j:V\rightarrow M$ with critical point $\kappa$ so that $j(\kappa)=\lambda$ and $M$ is closed under $\lambda$-sequences. We will define a "universal collapse" $\mathbb{P}$ with the $\kappa$-c.c. which will turn $\kappa$ into $\omega_1$, and then use the Silver collapse in the extension to turn $\lambda$ into $\omega_2$.

The crucial property of $\mathbb{P}$ is the following: if $\mathbb{Q}$ completely embeds into $\mathbb{P}$ and has inaccessible cardinality $\alpha$, then there is a complete embedding $i:\mathbb{Q}\ast S(\alpha,\kappa)\rightarrow \mathbb{P}$ extending the embedding of $\mathbb{Q}$. Thus, we are preparing $\mathbb{P}$ to absorb the Silver collapse.

The construction of $\mathbb{P}$ is an iteration with finite support starting with 0th stage $\mathrm{Col}(\omega,<\kappa)$, and at inaccessible stages $\alpha$, forcing with the Silver collapse of $V^\mathbb{Q}$ for some poset $\mathbb{Q}$ which completely embeds into $\mathbb{P}_\alpha$. By a suitable bookkeeping, we can achieve the crucial property. By the chain condition of the Silver collapse, it is easy to see that $\mathbb{P}$ has the $\kappa$-c.c.

Since $\mathbb{P}$ is $\kappa$-c.c., $\mathbb{P}$ completely embeds into $j(\mathbb{P})$ via $j$ (any maximal antichains of $\mathbb{P}$ have size $<\kappa$, so they are fixed by $j$ and remain maximal in $j(\mathbb{P})$).

So, letting $G$ be generic for $\mathbb{P}$ over $V$, we can force further to obtain $\hat{G}$ which is $V[G]$-generic for $j(\mathbb{P})$ and extend $j$ to $j^+:V[G]\rightarrow M[\hat{G}]$. Note that $M[\hat{G}]$ is $\lambda$-closed in $V[\hat{G}]$.

Therefore using the crucial property of $j(\mathbb{P})$, there is a complete embedding $i:\mathbb{P}\ast S(\kappa,\lambda)\rightarrow j(\mathbb{P})$ extending $j$ restricted to $\mathbb{P}$. Let $\mathbb{Q}$ be this Silver collapse, and let $H\in M[\hat{G}]$ be the generic for $\mathbb{Q}$ over $V[G]$ induced by $\hat{G}$ via the complete embedding (using closure of $M[\hat{G}]$. We can extend the embedding $j^+$ to $V[G\ast H]$, since $\bigcup j``H$ is a condition in $j(\mathbb{Q})$. This is where we used the Silver collapse--for the Levy collapse, $\bigcup j``H$ would have too large of a domain, it does not interact well with the huge embedding. The usual large cardinal techniques allow us to extend to $\hat{j}:V[G\ast H]\rightarrow M[\hat{G}\ast\hat{H}]$.

Now consider the $V[G\ast H]$-ultrafilter $U(\hat{j},\kappa)$ (defined in $V[\hat{G}\ast\hat{H}]$). We can use the $<\lambda$-closure of $j(\mathbb{Q})$ to find a $\tilde{U}$ in $V[\hat{G}]$ which is a $V[G\ast H]$-ultrafilter, normal, and $V[G\ast H]$-$\kappa$-complete. The construction works by taking a decreasing $\lambda$-sequence of conditions which together decide $\kappa\in \hat{j}(X)$ for every $X$ in $V[G\ast H]$, and additionally meeting dense sets which ensure that $V[G\ast H]$-sequences of fewer than $\kappa$-many of such $X$ which are forced in to be $U(\hat{j},\kappa)$ will also be in the ultrafilter.

In $V[G\ast H]$, $\kappa=\omega_1$ and $\lambda=\omega_2$. Let $I=\{X\subseteq \kappa: 1\Vdash X\in \dot{\tilde{U}}\}$. Then it can be checked that $I$ is normal and $\kappa$-complete, and since (using similar arguments as in Part 1) $j(\mathbb{P})/G\ast H$ is $\lambda$-c.c. and equivalent to the quotient algebra of $I$, $I$ is $\aleph_2$-saturated.

Spencinar #3: Precipitous ideals (part 1)

This week I'll continue the theme of Spencinar #1 by introducing some more concepts around the idea of generic ultrapowers by ideals. The emphasis will be on using large cardinals to construct ideals on small cardinals. The material comes mostly from Foreman's comprehensive chapter in the Handbook.

Prerequisites: Basic theory of large cardinals, forcing, and ultrapowers, some ideas in the first Spencinar post. The Boolean algebra approach to forcing will be helpful.

Recall the basic situation. If $I$ is an ideal on a set $Z$, then we can force with the poset $P(Z)/I$ as defined in Spencer's talk. Its elements are the mod $I$ equivalence classes of the positive subsets of $P(Z)$, ordered by the subset relation (also taken mod $I$). We denote the class of $S\subseteq Z$ by $[S]_I$. This poset is often called the quotient algebra of $I$. The generic object $G$, obtained by forcing with this poset is (equidefinable with) a $V$-ultrafilter, and so in the extension $V[G]$ we can take the $V$-ultrapower of $V$ by $G$. We denote this ultrapower by $V^Z/G$.

The basic definition, due to Jech and Prikry, is:

Definition: An ideal $I$ on a set $Z$ is precipitous if it is forced by $P(Z)/I$  that:

$V^Z/G$ is well-founded (in V[G]).

There are several combinatorial characterizations of precipitousness for an ideal $I$.

Let's give some nontrivial examples of this. A very basic result is that saturated ideals are precipitous.

Proposition: Suppose $I$ is $\kappa$-complete and $\kappa^+$-saturated. Then $I$ is precipitous.

Proof: Suppose that $I$ is not precipitous, so we can find $[S]_I$ forcing that $V^Z/G$ is ill-founded. Then let $\langle\dot{F}_n:n<\omega\rangle$ be $P(Z)/I$-names for functions $Z\rightarrow V$ in $V$ so that $[S]_I$ forces that for every $n$, $[\dot{F}_{n+1}]_G \in [\dot{F}_n]_G$ in the ultrapower.

The key is that one can replace the  $\langle\dot{F}_n:n<\omega\rangle$ by actual functions in $V$ without changing $S$. Let $n<\omega$. Find a maximal $P(Z)/I$ antichain $\mathcal{A}$ below $[S]_I$ deciding the value of $\dot{F}_n$. By a "disjointifying" argument using saturation and completeness, we can find a system of pairwise disjoint representatives $\langle A_i:i\in \mathcal{A}\rangle$ for the elements of this antichain. Define $f_n(z)$ to be the value of $\dot{F}_n$ forced by $[A_i]_I$ if $z\in A_i$, and 0 otherwise. Then we can see that $[S]_I$ forces $[\dot{F}_n]_G = [f_n]_G$. 

But now (using countable completeness of $I$), in $V$, for almost every $z\in S$, $f_{n+1}(z)\in f_n(z)$ for every $n$, giving an ill-foundedness in $V$. $\Box$

So the generic ultrapowers we considered last time (which didn't exist) were well-founded.

An immediate question is: can there be a precipitous ideal on small cardinals, e.g., $\omega_1$? The generic ultrapower construction and absoluteness of constructibility show that existence of any precipitous ideal implies that it is consistent that there is an embedding $L\rightarrow L$, so existence of a precipitous ideal has consistency strength at least that of the existence of $0^\#$.

We construct a precipitous ideal in a forcing extension starting from a measurable cardinal. The ideal is a fundamental one--start from a large cardinal ideal $J$, force to collapse the large cardinal to a small cardinal, and show that the ideal $I$ generated by $J$ in the extension retains some of the nice properties of $J$.

Actually, we'd like our precipitous idea to be a natural ideal, e.g., the nonstationary ideal on $\omega_1$. This is possible. However, today we will only get precipitousness for an induced (read: unnatural) ideal, that is an ideal which is defined to be the collection of subsets forced not to be in a particular ultrafilter of the form $U(\hat{j},i)=\{X:i\in \hat{j}(X)\}$ derived by a certain generic embedding $\hat{j}$. (We'll see this in action below).

Theorem: Suppose $\kappa$ is a measurable cardinal and let $U$ be a $\kappa$-complete normal ultrafilter on $\kappa$. Let $\mathbb{P}=\mathrm{Col}(\omega, <\kappa)$ be the Levy poset collapsing $\kappa$ to $\omega_1$. Then the ideal $I$ in $V^\mathbb{P}$ generated by the dual of $U$ is precipitous in $V^\mathbb{P}$.

Proof. By the basic theory of elementary embeddings and large cardinals, the ultrapower embedding $j:V\rightarrow M$ given by $U$ can be extended to $j^+:V[G]\rightarrow M[G\ast H]$, where $G$ is generic for $\mathbb{P}$ and $G\ast H$ is $V$-generic for $j(\mathbb{P})$ (here we used that $\mathbb{P}$ completely embeds into $j(\mathbb{P})=Col(\omega, <j(\kappa))^M$, and we'll write $j(\mathbb{P})=\mathbb{P}\ast \mathbb{Q}$). The extension takes the object $\mathbb{P}$-named by $\dot{\tau}$ (evaluated by $G$) to the object $j(\mathbb{P})$-named by $j(\dot{\tau})$ (evaluated by $G\ast H$).

The correct way to think of this is that forcing with $\mathbb{Q}$ over $V$ adds the embedding $j^+$.

First we show that (in $V[G]$) 

Claim: $I$ is equal to the ideal $\{X \subset \kappa : 1\Vdash  \kappa \not\in  j^+(X) \}$. 

Clearly, $I$ is contained in this ideal. Conversely, work in $V$ and suppose $\dot{X}$ is a $\mathbb{V}$ name for a subset of $\kappa$, and $p\in \mathbb{P}$ forces that $1\Vdash_\mathbb{ Q} \kappa \not\in  j^+(X)$. Define $A=\{\alpha:p\Vdash\alpha\not\in \dot{X}\}$. Then $A\in U$ (and so $p$ forces that $\dot{X}\in \dot{I}$, finishing the proof), otherwise we can define $F:(\kappa \setminus A)\rightarrow \mathbb{P}/p$ so that $F(\alpha)$ forces $\alpha\in X$. But then in $M$, $F$ represents a condition below $j(p)=p$ which forces $\kappa$ into $j^+(X)$, contradicting the choice of $p$. This proves the claim.

Now we show the precipitousness. Work in $V[G]$. Define a Boolean algebra embedding $P(\kappa)\rightarrow \mathcal{B}(\mathbb{Q})$ (here the codomain is the Boolean completion of $\mathbb{Q}$) which sends a set $X$ to the truth value $\lVert \kappa\in j^+(X)\rVert$. The use of the Boolean completion is so that this map is defined--in general, many different members of $\mathbb{Q}$ could force $\kappa\in j^+(X)$, but in the Boolean completion there is a greatest such member. Since $I$ is the kernel of this embedding, we see that the embedding factors to $\iota:P(\kappa)/I\rightarrow \mathcal{B}(\mathbb{Q})$. We will show that $\iota$ gives a dense embedding from the quotient algebra of $I$ into $\mathbb{Q}$. 

Claim: The range of $\iota$ is dense in $\mathcal{B}(\mathbb{Q})$. 

Since $\mathbb{Q}$ is densely embedded in $\mathcal{B}(\mathbb{Q})$, it suffices to show that for any $q\in\mathbb{Q}$ there is $X\subseteq \kappa$ with $\iota(X)=q$. Let $q=j(F)(\kappa)$, where $F\in V$ is a function such that for all $\alpha$, $F(\alpha)\in \mathrm{Col}(\omega, <\kappa)$. Define $X=\{\alpha: F(\alpha)\in G\}$. Now for any $H$ which is $V[G]$ generic for $\mathbb{Q}$, we have

 $\iota(X)\in H$ iff $\kappa \in j^+(X)$ (definition of $\iota$)
 iff $j(F)(\kappa)\in j^+(G)$ (definition of $X$)
iff $q\in j^+(G)$ (definition of $F$)
iff $q\in H$

so by separativity, $\iota(X)=q$, proving the claim.

So forcing with the quotient algebra of $I$ is equivalent to forcing with $\mathbb{Q}$; generic filters are equidefinable using the $\iota$ function. So let $H$ be obtained by applying $\iota$ image to an arbitrary $V[G]$-generic filter for $P(Z)/I$.

Now in $V[G\ast H]$, let $U^+=\{X\subseteq \kappa: \kappa\in j^+(X)\}$ be the ultrafilter derived from $j^+$, so we know from general considerations that the ultrapower of $V[G]$ by $U^+$ embeds into $M[G\ast H]$ (the embedding takes the element represented by a function $f $ to $j^+(f)(\kappa)$). But $U^+$ is exactly the filter generated the $\iota$-preimage of $H$, by the definition of $\iota$, so it is the original generic for $P(Z)/I$.

Wednesday, October 22, 2014

Spencinar #2: Martin's Maximum and Weak Square

Today John Susice gave an excellent presentation about a paper of Cummings and Magidor entitled "Martin's Maximum and Weak Square". Since the content of the talk was pretty close to the paper (which is well-written and available online), I won't blog about the precise details of the proof. Instead, I'll try to summarize what I see are the main points, and offer some soft speculation on future possibilities. I realize that what I write below might be unreadable, but I hope it conveys my general understanding of things, which might be helpful in a different way from careful writeups of proofs.

First, let me explain the two title principles. Martin's Maximum (MM) is a very strong forcing axiom, i.e., a principle which, for posets belonging to certain classes, asserts the existence of filter of each poset which meets every family of dense sets up to a certain size. We informally call this filter, meeting the appropriate choice of dense sets, a pseudogeneric. Martin's Axiom is perhaps the most well-known example of a forcing axiom; MM is the analogue of this for the class of posets whose generic extensions preserve the stationarity of ground model subsets of $\omega_1$ (the class of posets is usually simply called stationary preserving), and we must meet any $\omega_1$ many dense sets at a time. John made an amusing remark and said the name "non-forcing axiom" might be more appropriate, since the pseudogeneric objects they provide exist in the ground model, without any actual forcing taking place.

Weak square is a combinatorial principle introduced by Jensen. Generally, square principles assert the existence of sequences $\langle C_\alpha: \alpha<\lambda^+\rangle$ so that each $C_\alpha$ is club in $\alpha$, and there is some coherence between the $C_\alpha$. The "weak" part means that we will also allow multiple clubs at each level. I won't get into it too much, because we will really be working with a consequence of weak square: the existence of good scales.

Let $\lambda$ be a singular cardinal, and $\langle \lambda_i : i<\mathrm{cf}(\lambda)\rangle$ a cofinal sequence of regular cardinals less than $\lambda$. In this case, a scale is a sequence of functions $\langle g_\alpha: \alpha<\lambda^+\rangle$ in $\prod_{i<\mathrm{cf}(\lambda)} \lambda_i$ which is increasing and unbounded in the eventual domination ordering. Shelah proved that these scales exist for any singular cardinal (for some careful choice of $\langle \lambda_i : i<\mathrm{cf}(\lambda)\rangle$).

A good point of the scale is just an $\alpha_0<\lambda^+$ with cofinality $>\mathrm{cf}(\lambda)$ for which the ordering on $\langle g_\alpha: \alpha<\alpha_0\rangle$ is particularly nice: there is an unbounded set $A$ in $\alpha$ and some $i_0$ so that $\langle g_\alpha: \alpha\in A\rangle$ is pointwise increasing at each coordinate above $i_0$. A good scale is just a scale with club many good points. If you have some experience with the definitions, it's not too hard to show that a weak square sequence at $\lambda$ implies that every scale at $\lambda$ is good.

John went over the proof of the following theorem:

Theorem: If Martin's Maximum holds, then there are no good scales on $\lambda$ for any singular $\lambda$ with $\mathrm{cf}(\lambda)=\omega$. In particular, weak square fails at $\lambda$.

The proof, of course, went by defining a poset $\mathbb{P}$, proving that it is stationary preserving, and then applying MM. Suppose there is a good scale on $\langle \lambda_n:n<\omega\rangle$. The poset was a version of Namba forcing: its conditions are trees $T$ whose nodes are sequences of ordinals of countable cofinality with $n$th coordinate less than $\lambda_n$, and which (after some finite stem) split into stationary sets, i.e., for every $t\in T$ above the stem, there are stationary (in $\lambda_n$ for $n$ equal to the length of $t$) many $i$ so that $i$ appended to $t$ is in $T$.

The heart of the argument is the stationary preserving property, which was proven by appealing to the Gale-Stewart theorem for closed games. It was a very clever argument that involved showing that for any name for a club $\dot{C}\subset \lambda^+$, any ground model stationary set $S$, and any condition $T$ in the poset, you could find $\delta\in S$ so that:

$T$ can be thinned to a stationarily splitting subtree $T'$ so that the nodes at the $i$th level of $T'$ forces points in $(\delta_i, \delta)$ into $C$ below $\delta$, where $\delta_i$ is a fixed cofinal sequence in $\delta$.

This ensures that in the generic extension obtained by forcing with $T'$, $\delta\in S\cap C$. This is shown with a "Namba combinatorics" argument. A family of two-player games of length $\omega$ were defined, with a parameter for $\delta<\lambda^+$. In the game with parameter $\delta$, player II will build a branch through $T'$ after $\omega$ moves. Player I's $i$th move consists of blocking a nonstationary set of points below $\lambda_i$, and player II responds by naming the next coordinate of his branch, with the condition that he must play outside of the set that player I just blocked. Player II winning if at each stage $i$, taking $T'$ with his branch as the stem forces that a certain member of $C$ into the interval $(\delta_i,\delta)$. It was shown that player II wins this game for almost every $\delta$.

Now, in the generic extension by $\mathbb{Q}=\mathbb{P}\ast \mathrm{Col}(\omega_1, \lambda^+)$ (which is a stationary preserving poset), it is not hard to see by a density argument that the generic element $h$ of $\prod \lambda_i$ added by $\mathbb{Q}$ is an upper bound of every ground model member of $\prod \lambda_i$, under the eventual domination ordering. In fact it is an exact upper bound in the sense that any element of $\prod \lambda_i$ which is below $h$ is eventually dominated by a ground model function. Furthermore, every coordinate of $h$ has countable cofinality.

Back to the ground model. For any club $C\subset \lambda^+$, we can use MM to find a pseudogeneric $h$ which (VERY roughly) has some of the properties of the actually generic $h$ of the previous paragraph, but just working with the scale functions indexed below some cofinality $\omega_1$ ordinal $\gamma\in C$. Through some arguments which I omit, you can show that $\gamma$ is not good. So the set of nongood points is stationary!

Some vague parting thoughts: Are there any other constructions of such nongood points $\gamma$ for a scale, without MM? (Part of this question involves understanding the essential properties of the point $\gamma$, which I did not talk about). Are they similar to the nongood points you get from a supercompact cardinal? (I think the answer is no.) More generally, can we classify nongood points somehow? On the technical side, is there a general form of the Namba lemma which we can directly apply to see that $\mathbb{P}$ is stationary preserving?

Saturday, October 18, 2014

Combinations modulo a prime

My officemate Chris Scaduto and I are slowly working through Richard Stanley's Enumerative Combinatorics Vol. 1. One of the many interesting problems in this book asks to prove the following identity:

  • $\binom{pa}{pb}\equiv \binom{a}{b} (\mathrm{mod}\, p)$ for any prime $p$ and $a,b \in \mathbb{N}_+$.
We found a pretty simple proof based on Wilson's theorem that $(p-1)!\equiv -1 (\mathrm{mod}\, p)$, but we were really surprised by the elegant combinatorial proof in the solutions section.

Later Chris found a similar problem from a math contest, and used it for the algebra course he's TAing:

  • $\binom{a}{p}\equiv \lfloor \frac{a}{p} \rfloor (\mathrm{mod}\, p)$ for any prime $p$ and $a \in \mathbb{N}_+$.

He thought this was unexpected because of the appearance of the floor function. We noticed this could be proven by the same elegant combinatorial argument as in Stanley's book, and in fact we easily obtain the following generalization of both problems:

  • $\binom{a}{pb}\equiv \binom{\lfloor \frac{a}{p}\rfloor }{b} (\mathrm{mod}\, p)$ for any prime $p$ and $a \in \mathbb{N}_+$.
Proof: We will count the number of ways to choose a subset of $pb$ elements from $a$ objects. First, divide the $a$ objects into $p$ rows of $k=\lfloor \frac{a}{p}\rfloor$ objects:
  • $x_{1,1}, x_{1,2},\ldots,x_{1,k}$
  • $x_{2,1}, x_{2,2},\ldots,x_{2,k}$
  • $\cdots$
  • $x_{p,1}, x_{p,2},\ldots,x_{p,k}$
with a leftover pile for the remainder. Imagine the rows are stacked on top of each other. 

First, let us count the number of subsets so that for each column, either every object is chosen or none is. Let us call such a subset smooth. The leftover pile contains fewer than $p$ elements so a smooth subset cannot contain any elements from the leftover pile (since its intersection with the $p$ rows has size a multiple of $p$). Therefore these subsets are obtained by choosing a subset of $b$ elements from a single row and then just copying this choice for every row: there are $\binom{\lfloor \frac{a}{p}\rfloor }{b}$ ways to do this.

Let us say that two choices of $pb$ subset are equivalent if they agree on the leftover pile and their corresponding columns are cyclic shifts of each other. This latter condition can be stated more precisely as: for every $i\le k$, there is an $n$ so that $x_{j,i}=x_{j\oplus_p n,i}$, where the $\oplus_p$ indicates that the sum is reduced $\mod p$ to be between 1 and $p$.

A nonsmooth subset $A$ must have some column $i$ for which there is $j$ with $x_{j,i}\in A$ and $j'$ with $x_{j',i}\not\in A$. Now by cyclically shifting the column, we see that the equivalence class of $A$ has size dividing $p$. This completes the proof. $\Box$

Stanley's book had some other extensions of this result in a different direction. By a more careful counting technique one can prove the following identity:
  • $\binom{pa}{pb}\equiv \binom{a}{b} (\mathrm{mod}\, p^2)$ for any prime $p$ and $a,b \in \mathbb{N}_+$.
In fact, I think this was also true for $p^3$ replacing $p^2$. I wonder: how can we strengthen this result further?

Friday, October 17, 2014

Spencinar #1, part 2

We just saw that the nonstationary ideal cannot be $\kappa$-saturated. A more refined question is whether it can even be $\kappa^+$ saturated. Sometimes this is just called saturated. Gitik and Shelah proved that the answer is no, if $\kappa>\omega_1$.

Theorem: If $\kappa,\theta$ are regular with $\theta^+<\kappa$, then $NS_\kappa \upharpoonright\mathrm{cof}(\theta)$ is not $\kappa^+$-saturated.

They start off with a principle that is inconsistent. Let $\kappa, \theta$ be regular, $\kappa>\omega_2, \theta^+$. The strong club guessing principle $\lozenge^*_\textrm{club}(\kappa,\theta)$ states that there exists a sequence $\langle S_\alpha : \alpha\in\kappa\cap \mathrm{cof}(\theta)\rangle$ such that

  1. $S_\alpha\subseteq \alpha$,
  2. $\sup S_\alpha =\alpha$,
  3. $|S_\alpha|=\theta$,
  4. For all $\beta\in S_\alpha$, $\mathrm{cf}(\beta)>\theta$ and if $\theta=\aleph_0$ then $\mathrm{cf}(\beta)>\omega_1$ (Spencer remarks that the "and if" part is an ad hoc condition used to handle a special case),
  5. For all $C\subseteq \kappa$ club, $\{\alpha: \exists \beta<\alpha \, S_\alpha\setminus \beta\subseteq C\}$ contains a club intersected with $\mathrm{cof}(\theta)$. (Such an $\alpha$ is said to guess $C$)
Lemma 1: $\lozenge^*_\textrm{club}(\kappa,\theta)$ is false.

Proof: Otherwise there is such a sequence $\langle S_\alpha : \alpha\in\kappa\cap \mathrm{cof}(\theta)\rangle$.

Case 1: $\theta>\aleph_0$.

We will build a decreasing sequence of clubs $\langle E_n: n<\omega \rangle$ by
$$E_{n+1} \subseteq E'_n \textrm{ such that every point of }E_{n+1}\cap \mathrm{cof}(\theta) \textrm{ guesses } E'_n.$$

Let $E=\bigcap_n E_n$, and $\delta =\min(E\cap \mathrm{cof}(\theta))$. Since $\theta>\aleph_0$, there is a $\beta\in S_\delta \subseteq E$ and $S_\delta\setminus \beta \subseteq E$. Therefore $\beta \in E'_n$ for all $n$ and hence in $E'$, and $\mathrm{cf}(\beta)>\theta$ by (4). Thus we can find a point in $E\cap \mathrm{cof}(\theta))$ less than $\beta$, contradicting the minimality of $\delta$. 

Case 2: $\theta=\aleph_\omega$. 

This case is similar to Case 1, and is handled using the ad hoc condition. $\Box$

Now that we've defined this inconsistent principle, we will derive it from the assumption of a saturated nonstationary ideal. This would be enough to prove the theorem.

Lemma 2: Suppose $\kappa,\theta$ are regular cardinals with $\theta^+<\kappa$. If $NS_\kappa\upharpoonright \mathrm{cof}(\theta)$ is $\kappa^+$-saturated, then $\lozenge^*_\textrm{club}(\kappa,\theta)$ holds.

Proof: Consider the principle $\lozenge'_\textrm{club}(S)$ which is like $\lozenge^*_\textrm{club}(\kappa,\theta)$ above but weakening (5) to (5'):
  • for all closed unbounded $C\subseteq \kappa$, $\{\alpha: \exists \beta<\alpha \, S_\alpha\setminus \beta\subseteq C\}$ is stationary.
It's a famous result of Shelah that this club-guessing theorem holds for all stationary $S\subseteq \kappa\cap\mathrm{cof}(\theta)$.

From the saturation assumption we can first get a local version of the strong club guessing principle.

Claim: Let $S\subseteq \kappa\cap\mathrm{cof}(\theta)$ be stationary and $\langle S_\alpha: \alpha\in S\rangle$ witness $\lozenge'_\textrm{club}(S)$. Then there is $S^*\subseteq S$ stationary such that for all $C\subseteq \kappa$ club, $\{\alpha: \exists \beta<\alpha \, S_\alpha\setminus \beta\subseteq C\}$ contains a club intersected with $S^*$.

Proof of the Claim: Suppose not. We will define clubs $\langle C_\alpha: \alpha<\kappa^+\rangle$ so that if $\xi<\zeta$ then for some $\gamma<\kappa$, $C_\zeta\setminus \gamma \subseteq C_\xi$ (so the sequence is "almost decreasing"). We will simultaneously define stationary sets $\langle A_\alpha:\alpha<\kappa^+\rangle$ which are subsets of $S$ and whose pairwise intersections are nonstationary. This will yield a contradiction to saturation.

For any club $D$, let $N(D)=\{\alpha: \exists \beta<\alpha \, S_\alpha\setminus \beta\subseteq D\}$ be the set of points that guess $D$.

By the contradictory assumption, pick $C_0$ club so that $S-N(C_0)$ is stationary, and let $A_0=S-N(C_0)$. Suppose $\langle C_\beta:\beta<\alpha\rangle$ and $\langle A_\beta:\beta<\alpha$ have already been constructed. Let $C=\Delta_{\beta<\alpha} C_\alpha$ (technically, the diagonal intersections are taken using some fixed surjection from $\kappa$ to $\alpha$ in the background).

Again using the contradictory assumption, there is $C_\alpha$ club so that $N(C)-N(C_\alpha)$ is stationary. Let $A_\alpha = N(C)-N(C_\alpha)$.

These $A_\alpha$ are have nonstationary (in fact, bounded) pairwise intersection: if $\beta<\alpha$, then coboundedly many points of $A_\alpha$ guess the diagonal intersection of the $C_\xi, \xi<\alpha$, so coboundedly many points of $A_\alpha$ guess $C_\beta$. But $A_\beta$ was taken to be disjoint from $C_\beta$. The claim is proven.

Find a maximal collection $\langle T_\alpha:\alpha<\kappa\rangle$ of pairwise intersection nonstationary sets so that each $T_\alpha$ has the property of $S^*$ in the claim. The sequence has size $\kappa$ by saturation. Gluing the pieces together, we have proved the Lemma, so we're done.

Thursday, October 16, 2014

Spencinar #1: Solovay's splitting: Smash it with a hammer (10/15/14), part I

Spencinar. The Spencinar is a graduate student seminar started and organized last year by Spencer Unger (blame Zach Norwood for the corny name). In this seminar, graduate students and Spencer meet for two hours weekly to present interesting results that they've read about and want to share, or little research ideas which are not appropriate for the Cabal Seminar. It's one way we can help each other acquire knowledge more quickly, and a great excuse for grabbing a drink afterwards with our fellow set theorists!

These posts are based off of my notes taken during the seminar, and any mistakes herein should not be attributed to the speaker. You should expect the notes to be less thorough in the future, as they are based on my own comprehension of the lecture, which can be extremely lacking outside of my immediate research interests.

This year, Spencer Unger started off with Solovay splitting: Smash it with a hammer.

Prerequisites: Knowledge of ultrapowers and forcing, some club guessing results will be stated as black boxes in the second part.

Today's Spencinar was about saturated ideals. The title of the talk refers to Solovay's theorem about splitting stationary sets, and the hammer is forcing. It leads to a proof of the theorem (in fact, the original one) that seems more principled than the elementary combinatorial one in Jech's book, but Spencer notes that the essence of the two proofs is the same.

Theorem (Solovay splitting): If $S\subseteq \kappa$ is stationary, then there $\langle S_i: i<\kappa\rangle$ disjoint stationary subsets of $S$.

Recall that an ideal $I$ on $X$ is $\kappa$-saturated if $P(X)/I$ is $\kappa$-c.c. Here $P(X)/I$ is the poset whose elements are $\mod I$-equivalence classes of subsets of $X$, without the equivalence class consisting of the members of $I$. The ordering is by $[A] \leq [B]$ iff $A \setminus B \in I$ (i.e., inclusion $\mod I$). An equivalent formulation of $\kappa$-saturation is that for any $\kappa$ many $I$-positive subsets of $X$, there are two which intersect in an $I$-positive set.

Let us denote the nonstationary ideal on $\kappa$ by $NS_\kappa$. If $S$ is stationary, then $NS_\kappa \upharpoonright S$ is the ideal generated over $NS_\kappa$ by adding $S$.

Lemma: If Solovay splitting fails for $S$, then $NS_\kappa\upharpoonright S$ is $\kappa$-saturated.

Proof: An easy "disjointify" argument using $\kappa$-completeness. Let $\langle A_\alpha : \alpha <\kappa\rangle$ be stationary such that $A_\alpha \cap A_\beta \in NS_\kappa\upharpoonright S$ for all $\alpha \neq \beta$. Define $B_\alpha = A_\alpha - \bigcup_{\beta<\alpha} A_\beta$. Then $\langle B_\alpha: \alpha<\kappa\rangle$ witnesses Solovay splitting for $S$. $\Box$

Lemma (*): If $S\subseteq \kappa \cap \mathrm{cof}(>\omega)$ is stationary, then $T=\{\alpha\in S: S\cap \alpha \textrm{ is nonstationary}\}$ is stationary. (Note: $T$ is the set of points in $S$ that do not reflect $S$).

Proof: Fix a club $C\subseteq \kappa$. Let $C'$ be the set of limit points of $C$. If $\alpha$ is the least element in $S\cap C'$, then $\alpha$ does not reflect $S$ (as $C\cap \alpha$ is club in $\alpha$), so $\alpha \in T$. Since $C$ was an arbitrary club, the lemma is proved. $\Box$

Now we are ready to prove the Solovay splitting theorem.

Suppose the result fails for some $S$. Split into cases (Spencer hesitated about this, he really wanted a uniform proof).

Case 1. If $S$ concentrates on $\mathrm{cof}(\theta)$ for some $\theta<\kappa$, then forcing with $P(\kappa)/NS_\kappa\upharpoonright S\cap \mathrm{cof}(\theta)$ gives a $V$-ultrafilter $U$ concentrating on $S\cap \mathrm{cof}(\theta)$ which is $V$-$\kappa$-complete. This means the ultrafilter measures sets from $V$, and is closed under intersections of families in $V$ of $<\kappa$ many measure one sets, with the tacit meaning that the ultrafilter itself is not in $V$.

In the generic extension, form the ultrapower $j:V\rightarrow \mathrm{Ult}(V,U)$. Then $\mathrm{Ult}(V,U) \vDash \kappa \in j(S)$ (this was glossed over and uses the fact that $U$ is normal and $V$-$\kappa$-complete, which follows from a genericity argument), so $M \vDash \mathrm{cf}(\kappa)=\theta$. This is a contradiction.

Case 2. The remaining case is that $S$ concentrates on $\{\alpha : \mathrm{cf}(\alpha)=\alpha\}$. Let $T\subseteq S$ be defined as in Lemma (*). Since $T$ is stationary, it is an element of the forcing $P(\kappa)/NS_\kappa\upharpoonright S\cap \mathrm{cof}(\theta)$ so force below $T$ to get a generic $U$. Taking the ultrapower by $U$, $M\vDash \kappa\in j(T)$, so $$M\vDash j(S)\cap \kappa \textrm{ is not stationary. }$$
But $j(S)\cap \kappa=S$ and $\kappa$-c.c. forcing preserves stationarity of subsets of $\kappa$, so we again arrive at a contradiction.

Thus Solovay's theorem is proved.

I'll type up the second part of the talk later, which investigated the possibility of the nonstationary ideal on $\kappa$ being $\kappa^+$-saturated.

The Journey of a Thousand Miles

Welcome to my blog! I'm Bill, a graduate student in mathematics at UCLA studying set theory. I'm starting this blog to improve my math communication skills, and to share in the experience of learning math with people from all around the world.

Here are some of the kinds of posts you can expect from me:

  • My account of any talks, seminars, or conferences I attend. Live your UCLA dream vicariously through me!
  • Announcements of my own work. (Hopefully!!)
  • Random set theory facts.
  • My own Math Overflow-type problems for you, the reader, to think about! (Warning: may be trivial)
  • Multi-post projects to understand a deep result or a series of related results.
  • Attempts to learn mathematical things outside of set theory (recent dabblings include topology, analytic number theory, enumerative combinatorics).

I hope this blog will suit your interests. I'm trying to cater to:

  • Students and researchers in set theory, the main audience.
  • Other mathematicians who are trying to understand our rich subject.
  • People who can offer their insight on my posts outside of set theory. Enlighten me!
  • People interested in problem-solving and Olympiad math.
  • Myself, to create a record of ideas that occupied me at some time. Extended mind and all that!

Not every post will be interesting to everyone, but I think I'll have good things to write about! Are you excited?