## 116c- Lecture 13

May 13, 2008

We explored well-founded relations and proved a generalization of the recursion theorem to well-founded, set like relations. The main application of this result is the Mostowski collapsing theorem.

Finally, we defined relativizations and explained how they are useful to establish relative consistency results; absolute consistency results being precluded by Gödel’s second incompleteness theorem.

## 116c- Lecture 12

May 8, 2008

We completed the proof of Silver’s theorem. Silver’s argument, as understood by Baumgartner and Prikry, started a whole new series of results that culminated in Shelah’s celebrated pcf theory. See

T. Jech, Singular cardinals and the pcf theory, The Bulletin of Symbolic Logic 1(4) (1995), 408-424

for an introduction (without proofs) and historical remarks, or

M. Burke, M. Magidor, Shelah’s pcf theory and its applications, Ann. Pure Appl. Logic 50 (3) (1990), 207-254

for a more technical introduction , including proofs. Jech’s paper is available through JSTOR.

We defined the cumulative hierarchy ${\sf WF}=\bigcup_{\alpha\in{\sf ORD}}V_\alpha$, proved its basic properties and showed that $V={\sf WF}$.

## 116c- Homework 5

May 7, 2008

Homework 5

Due Wednesday, May 14 at 2:30 pm.

Update. In both parts of exercise 2, “closed” should actually be “closed in its supremum;” i.e., the subset $X$of $S$ or of ${\mathbb Q}$ is closed in $S\cap\sup(X)$ or ${\mathbb Q}\cap\sup(X)$, respectively. Or, if you rather, replace the order type $\alpha$ of $X$ with $\alpha+1$. Sorry for the confusion; thanks to Fedor Manin for noticing this.

In exercise 1.(a)iii, “$m” should be “$n.” Thanks to Michael Conley for pointing this out.

Update. Here are sketches of the solutions of exercises 2.(a) and 3:

For 2.(a), let $S\subseteq\omega_1$ be a given stationary set, and argue by induction on $\alpha<\omega_1$ that $S$ contains closed copies $t$ of $\alpha+1$ with $\min(t)$ arbitrarily large. (Of course, if the result of the exercise holds, this must be the case: Given any $\gamma<\omega+1$, notice that $S\setminus(\gamma+1)$ is stationary, so it must contain a closed copy $t$ of $\alpha+1$, and $\min(t)>\gamma$.)

This strengthened version holds trivially for $\alpha$ finite or successor, by induction. So it suffices to show it for $\alpha$ limit, assuming it holds for all smaller ordinals. Define a club $C\subseteq\omega_1$ with increasing enumeration $\{\gamma_\beta:\beta<\omega_1\}$ as follows: Let $(\alpha_n:n<\omega)$ be strictly increasing and cofinal in $\alpha$. Since $S$ contains closed copies $A_n$ of $\alpha_n+1$ for all $n$, with their minima arbitrarily large, by choosing such copies $A_n$ with $\min(A_{n+1})>\sup(A_n)$ and taking their union, we see that $S$ must contain copies of $\alpha$, closed in their supremum, with arbitrarily large minimum element. (I am not claiming that $A=\bigcup_n A_n$ built this way has order type $\alpha$. For example, if $\alpha=\omega+\omega$ and $\alpha_n=\omega+n$, then $A$ would have order type $\omega^2$; but for sure $A\subset S$ is closed in its supremum and has order type at least $\alpha$. So a suitable initial segment of $A$ is as wanted.)

Let $\gamma_0$ be the supremum of such a copy of $\alpha$. At limit ordinals $\beta$, let $\gamma_\beta=\sup_{\delta<\beta}\gamma_\delta$. Once $\gamma_\beta$ is defined, find such a copy of $\alpha$ inside $S$ with minimum larger than $\gamma_\beta$, and let $\gamma_{\beta+1}$ be its supremum.

The set $C$ so constructed is club, so it meets $S$. If they meet in $\gamma_0$ or in a $\gamma_{\beta+1}$, this immediately gives us a closed copy of $\alpha+1$ inside $S$. If they meet in a $\gamma_\beta$ with $\beta$ limit, let $(\beta_n:n<\omega)$ be strictly increasing and cofinal in $\beta$, and consider an appropriate initial segment of $A=(\bigcup_n A_n)\cup{\gamma_\beta}$, where $A_n$ is a closed copy of $\alpha_n+1$ in $S\cap[\gamma_{\beta_n},\gamma_{\beta_{n+1}})$. ${\sf QED}$

For 3, let $\kappa$ be regular and $S\subseteq\kappa$ be stationary, and set $T=\{\alpha\in S:{\rm cf}(\alpha)=\omega$ or $({\rm cf}(\alpha)>\omega$ and $S\cap\alpha$ is not stationary in $\alpha)\}$. We claim that $T$ is stationary. To see this, let $C$ be an arbitrary club subset of $\kappa$. Then the set $C'$ of limit points of $C$ is also club (and a subset of $C$), so it meets $S$, since $S$ is stationary. Let $\alpha=\min(C'\cap S)$. Then either $\alpha$ has cofinality $\omega$, so it is in $T$, or else it has uncountable cofinality. In that case, notice that since $\alpha\in C'$, it is a limit of points in $C$, so $C\cap\alpha$ is club in $\alpha$, so $(C\cap\alpha)'=C'\cap\alpha$ is also club in $\alpha$. Were $S\cap\alpha$ stationary in $\alpha$, it would meet $C'\cap\alpha$, and this would contradict the minimality of $\alpha$. It follows that $\alpha\in T\cap C$, and therefore $T$ is stationary, as wanted.

Let now $\alpha$ be an arbitrary point of $T$. If $\alpha$ has cofinality $\omega$, it is the limit of an $\omega$-sequence of successor ordinals. Let $f_\alpha$ be the increasing enumeration of this sequence, and notice that ${\rm ran}(f_\alpha)\cap T=\emptyset$, since all ordinals in $T$ are limit ordinals. Suppose now that $\alpha$ has uncountable cofinality, so $S\cap\alpha$ is not stationary in $\alpha$. Since $T\subseteq S$, it follows that $T\cap\alpha$ is not stationary either, so there is a club subset of $\alpha$ disjoint from $T$, and let $f_{\alpha}$ be the increasing enumeration of this club set.

With the sequences $f_\alpha$ defined as above for all $\alpha\in T$, we now claim that there is some $\xi<\kappa$ such that  for all $\eta<\kappa$, the set $T_\eta=\{\alpha\in T:\xi\in{\rm dom}(f_\alpha)$ and $f_\alpha(\xi)\ge\eta\}$ is stationary. The proof is by contradiction, assuming that no $\xi<\kappa$ is as wanted.

It follows then that for all $\xi<\kappa$ there is some $\eta=\eta(\xi)<\kappa$ such that the set $T_\eta=T_\eta^\xi$ as above is non-stationary. Fix a club $C_\xi$ disjoint from it, and let $C$ be the club $C=\triangle_\xi C_\xi$. Let $D=C'\cap E$, where $E=\{\alpha<\kappa:\eta[\alpha]\subseteq\alpha\}$; here, $\eta:\kappa\to\kappa$ is the function $\xi\mapsto\eta_xi$. Notice that $E$ is club, and so is $D$. We claim that $|D\cap T|\le 1$. This contradicts that $T$ is stationary, and therefore there must be a $\xi<\kappa$ as claimed.

Suppose then that $\gamma<\alpha$ are points in $D\cap T$. Since $\alpha\in D$, then $\alpha\in C$, so $\alpha\in C_\xi$ (hence, $\alpha\notin T^\xi_{\eta_\xi}$) for all $\xi<\alpha$. We claim that $\gamma\in{\rm dom}(f_\alpha)$. To see this, let $\xi\in\gamma\cap{\rm dom}(f_\alpha)$. Then (by definition of $T^\xi_{\eta_\xi}$), $f_\alpha(\xi)<\eta_\xi$. Since $\gamma\in D$, then $\gamma\in E$ and,  since $\xi<\gamma$, then $\eta_\xi<\gamma$. It follows that $\sup{\rm ran}(f_\alpha\upharpoonright\gamma)\le\gamma<\alpha$. Since $f_\alpha$ is cofinal in $\alpha$, we must necessarily have $\gamma\in{\rm dom}(f_\alpha)$.

Since $f_\alpha$ is continuous and $\gamma$ is a limit ordinal (since it is in $C'$), it follows that $f_\alpha(\gamma)= \sup_{\xi<\gamma}f_\alpha(\xi)\le \gamma$. But, since $f_\alpha$ is increasing, then also $f_\alpha(\gamma)\ge \gamma$. Hence, $f_\alpha(\gamma)=\gamma$. We have finally reached a contradiction, because $\gamma\in T$, but the sequence $f_\alpha$ was chosen so its range is disjoint from $T$. This proves that $|D\cap T|\le 1$, which of course is a contradiction since $T$ is stationary. It follows that indeed there is some $\xi<\kappa$ such that all the sets $T_\eta=\{\alpha\in T: \xi\in{\rm dom}(f_\alpha)$ and $f_\alpha(\xi)\ge\eta\}$ are stationary for $\eta<\kappa$.

Now let $f:T\to\kappa$ be the map $f(\alpha)=\left\{\begin{array}{cl} f_\alpha(\xi)&\mbox{ if }\xi\in{\rm dom}(f_\alpha),\\ 0&\mbox{ otherwise.}\end{array}\right.$ Clearly, $f$ is regressive. Also, from the definition of $f$, it follows that $\{\alpha\in T: f(\alpha)\ge \eta\}=T_\eta$ for all $\eta<\kappa$, so $f$ is unbounded in $\kappa$, since each $T_\eta$ is in fact stationary, as we showed above. Given any $\eta<\kappa$, since $f\upharpoonright T_\eta$ is regressive, there is some $\gamma$ (necessarily, $\gamma\ge\eta$) such that $\{\alpha\in T_\eta:f(\alpha)=\gamma\}$ is stationary, by Fodor’s lemma. A simple induction allows us to define a strictly increasing sequence $(\gamma_\eta:\eta<\kappa)$ such that $\{\alpha\in T_{\gamma_\eta+1}:f(\alpha)=\gamma_{\eta+1}\}$ is stationary for all $\eta$. Notice that these $\kappa$ many subsets of $T$ (hence, of $S$) so defined are all disjoint. By adding to one of them whatever (if anything) remains of $S$ after removing all these sets, we obtain a partition of  $S$ into $\kappa$ many disjoint stationary subsets, as wanted. ${\sf QED}$

## 116c- Lecture 11

May 6, 2008

We proved Fodor’s theorem and showed some of its consequences.

We also proved Ulam’s theorem that any stationary subset of a successor cardinal $\kappa^+$ can be partitioned into $\kappa^+$ disjoint stationary sets. This result also holds for limit regular cardinals $\lambda$, with a more elaborate proof that is sketched in the new homework set.

We then started the proof of Silver’s theorem that $\aleph_{\omega_1}$ is not the first counterexample to ${\sf GCH}$.

## 116c- Lecture 10

May 2, 2008

For $\kappa$ an uncountable regular cardinal, we studied basic properties of club sets, defined diagonal intersection and showed that the intersection of fewer than $\kappa$ many club subsets of an uncountable regular cardinal $\kappa$ is club and also the diagonal intersection of $\kappa$ many club sets is club.

We also showed that if ${\mathcal A}=(\kappa,\dots)$ is a structure in a countable language, then for club many $\alpha<\kappa$, $\alpha$ is the universe of an elementary substructure of ${\mathcal A}$. The proof in fact works as long as the language has size smaller than $\kappa$.

We closed with some basic examples of stationary sets and stated Fodor’s theorem.

Remark. The proof given in lecture of the fact that the diagonal intersection of club sets is club was purely combinatorial. In a forthcoming lecture, I will prove the reflection theorem, that any finite collection of sentences true in the universe is true in arbitrarily large stages $V_\alpha$. With this and a few absoluteness facts, one can give a different proof, in effect showing that many ordinals below a cardinal $\kappa$ “behave like” $\kappa$ itself. This idea, which we will formalize once reflection is presented, is a very useful heuristic that allows us to use (basic) model-theoretic techniques to prove combinatorial arguments.