## 116c- Lecture 9

April 30, 2008

We proved König’s theorem and results of Hausdorff and Tarski on cardinal exponentiation, indicated some of their consequences (for example, ${\mathfrak c}\ne\aleph_\omega$), and showed how to compute under ${\sf GCH}$ the function $(\kappa,\lambda)\mapsto\kappa^\lambda$.

We stated Easton’s result essentially saying that without additional assumptions, in ${\sf ZFC}$ nothing can be said about the exponential function $2^\lambda$ beyond monotonicity and König’s theorem.

For singular cardinals the situation is much more delicate. We stated as a sample result Shelah’s theorem that if $\aleph_\omega$ is strong limit, then $2^{\aleph_\omega}$ is regular and smaller than $\aleph_{\min(\omega_4,{\mathfrak c}^+)}$.

This result is beyond the scope of this course. Instead, we will prove a particular case of an earlier result of Silver, namely, that $\aleph_{\omega_1}$ is not the first counterexample to ${\sf GCH}$.

In order to prove Silver’s result, we need to develop the theory of club and stationary sets. We defined these notions and proved some of their basic properties.

## 116c- Homework 4

April 29, 2008

Due Wednesday, May 7 at 2:30 pm.

Update. In exercise 2, $\lambda=\mu$, of course. In exercise 3, $(\kappa)^\lambda$ in the right hand side must be $(<\kappa)^\lambda$.

Hint for exercise 5: Consider the smallest $\alpha$ such that $\alpha+\beta>\beta$ (ordinal addition).

Update. Here is a quick sketch of the solutions:

• 1.(a). Write $\kappa=\sum_{\alpha<{\rm cf}(\kappa)}\kappa_\alpha$ for some (not necessarily strictly) increasing ${\rm cf}(\kappa)$-sequence of cardinals $\kappa_\alpha<\kappa$. (If $\kappa$ is regular, take $\kappa_\alpha=1$ for all $\alpha$. If $\kappa$ is singular, let the $\kappa_\alpha$ be increasing and cofinal in $\kappa$.) Then $2^\kappa=2^{\sum_{\alpha<{\rm cf}(\kappa)}\kappa_\alpha}=\prod_\alpha2^{\kappa_\alpha}\le\prod_\alpha2^{<\kappa}=(2^{<\kappa})^{{\rm cf}(\kappa)}$ but also $(2^{<\kappa})^{{\rm cf}(\kappa)}\le (2^\kappa)^\kappa=2^\kappa$ and the result follows. If $\kappa$ is strong limit, then $2^{<\kappa}=\kappa$, and we get $2^\kappa=\kappa^{{\rm cf}(\kappa)}$.
• 1.(b). Under the assumption, we may choose the $\kappa_\alpha$ as in 1.(a) such that ${\rm cf}(\kappa)<\kappa_0$ and $2^{\kappa_\alpha}=2^{\kappa_\beta}$ for all $\alpha<\beta<{\rm cf}(\kappa)$. Then $2^\kappa=(2^{<\kappa})^{{\rm cf}(\kappa)}=(2^{\kappa_0})^{{\rm cf}(\kappa)}=2^{\kappa_0}=2^{<\kappa}$.

• 2. Write $\mu$ as a disjoint union of $\mu$ sets $A_\alpha$, $\alpha<\mu$, each of size $\mu$. This is possible since $\mu\times\mu=\mu$. Since each $A_\alpha$ has size $\mu$, it is necessarily cofinal in $\mu$. We then have $\kappa^\mu\ge\prod_{i\in\mu}\kappa_i=\prod_{\alpha\in\mu}\prod_{i\in A_\alpha}\kappa_i\ge\prod_\alpha\kappa=\kappa^\mu$.

• 3. If $\kappa\le 2^\lambda$, then $2^\lambda\le\kappa^\lambda\le(2^\lambda)^\lambda=2^\lambda$.
• If $\lambda<{\rm cf}(\kappa)$ then any function $f:\lambda\to\kappa$ is bounded, so ${}^\lambda\kappa=\bigcup_{\alpha<\kappa}{}^\lambda\alpha$, and $\kappa^\lambda\le\sum_\alpha|\alpha|^\lambda\le\kappa\cdot(<\kappa)^\lambda$; the other inequality is clear.
• Suppose that ${\rm cf}(\kappa)\le\lambda$$2^\lambda<\kappa$, and $\rho\mapsto\rho^\lambda$ is eventually constant as $\rho$ approaches $\kappa$. Choose a strictly increasing sequence $(\kappa_\alpha:\alpha<{\rm cf}(\kappa))$ cofinal in $\kappa$ such that $\kappa_\alpha^\lambda=\kappa_\beta^\lambda$ for $\alpha<\beta<{\rm cf}(\kappa)$. Then $\kappa^\lambda\le(\prod_\alpha\kappa_\alpha)^\lambda=\prod_\alpha\kappa_\alpha^\lambda=\prod_\alpha \kappa_0^\lambda=\kappa_0^{\lambda\cdot{\rm cf}(\kappa)}=\kappa_0^\lambda=(<\kappa)^\lambda$. The other inequality is clear.
• Finally, suppose that ${\rm cf}(\kappa)\le\lambda$, $2^\lambda<\kappa$, and $\rho\mapsto\rho^\lambda$ is not eventually constant as $\rho$ approaches $\kappa$. Notice that if $\rho<\kappa$ then $\rho^\lambda<\kappa$. Otherwise, $\tau^\lambda=(\tau^\lambda)^\lambda\ge\kappa^\lambda\ge\tau^\lambda$ for any $\rho\le\tau<\kappa$, and the map $\rho\mapsto\rho^\lambda$ would be eventually constant below $\kappa$ after all. Hence, $(<\kappa)^\lambda=\kappa$. Choose an increasing sequence of cardinals $(\kappa_\alpha:\alpha<{\rm cf}(\kappa))$ cofinal in $\kappa$. Then $\kappa^\lambda\le(\prod_\alpha\kappa_\alpha)^\lambda=\prod_\alpha\kappa_\alpha^\lambda\le\prod_\alpha (<\kappa)^\lambda=\prod_\alpha\kappa=\kappa^{{\rm cf}(\kappa)}$. The other inequality is clear.

• 5. Suppose that $\beta\ge\omega$ and for all $\alpha$, $2^{\aleph_\alpha}=\aleph_{\alpha+\beta}$. Let $\alpha$ be least such that $\beta<\alpha+\beta$; $\alpha$ exists since $\beta<\beta+\beta$. On the other hand, $\alpha$ is a limit ordinal, since $1+\omega=\omega$ and $\omega\le\beta$, so $(\lambda+n)+\beta=\lambda+(n+\beta)=\lambda+\beta$ for any $\lambda$ and any $n<\omega$, and we would have a contradiction to the minimality of $\alpha$. Let $\gamma<\alpha$. Then $\gamma+\beta=\beta$ and $2^{\aleph_{\alpha+\gamma}}=\aleph_{\alpha+\beta}$. By exercise 1.(b), $2^{\aleph_{\alpha+\alpha}}=\aleph_{\alpha+\beta}$ since $\aleph_{\alpha+\alpha}$ is singular (it has cofinality ${\rm cf}(\alpha)\le\alpha<\alpha+\alpha\le\aleph_{\alpha+\alpha}$). This is a contradiction, since by assumption, $2^{\aleph_{\alpha+\alpha}}=\aleph_{\alpha+\alpha+\beta}>\aleph_{\alpha+\beta}$.

• 4. We want to show that $\prod_{\xi<\beta}\aleph_\xi=\aleph_\beta^{|\beta|}$ for all limit ordinals $\beta$. Write $\beta=|\beta|+\alpha$ where $\alpha=0$ or a limit ordinal, and proceed by induction on $\alpha$, noticing that the case $\alpha=0$ follows from exercise 2.
• Notice that any limit ordinal $\alpha$ can be written as $\alpha=\omega\cdot\delta$ for some nonzero ordinal $\delta$. This is easily established by induction. If $\delta$ is a limit ordinal, then any sequence converging to $\delta$ gives rise in a natural way to a sequence of limit ordinals converging to $\alpha$. On the other hand, if $\delta$ is a successor, then $\alpha=\lambda+\omega$ for some $\lambda=0$ or limit. In summary: any limit ordinal is either a limit of limit ordinals, or else it has the form $\lambda+\omega$ for $\lambda=0$ or limit.
• We divide our induction on $\alpha$ in two cases. Suppose first $\alpha=\lambda+\omega$, as above. Then $\prod_{\xi<\beta}\aleph_\xi=\aleph_{|\beta|+\lambda}^{|\beta|}\prod_n\aleph_{|\beta|+\lambda+n}$, by induction. Since $|\beta|=|\beta|\aleph_0$, we have $\aleph_{|\beta|+\lambda}^{|\beta|}\prod_n\aleph_{|\beta|+\lambda+n}=\prod_n\aleph_{|\beta|+\lambda}^{|\beta|}\aleph_{|\beta|+\lambda+n}=\prod_n\aleph_{|\beta|+\lambda+n}^{|\beta|}$, where the last equality holds by Hausdorff’s result that $(\kappa^+)^\tau=\kappa^+\cdot\kappa^\tau$. Finally, $\prod_n\aleph_{|\beta|+\lambda+n}^{|\beta|}=(\prod_n\aleph_{|\beta|+\lambda+n})^{|\beta|}=(\aleph_\beta)^{\aleph_0\cdot|\beta|}=\aleph_\beta^{|\beta|}$ as wanted, where the previous to last equality is by exercise 2.
• Now suppose that $\alpha$ is a limit of limit ordinals. Choose a strictly increasing sequence $(\gamma_\nu:\nu<{\rm cf}(\alpha))$ of limit ordinals cofinal in $\alpha$. We argue according to which of the four possibilities described in exercise 3 holds. If $\aleph_\beta\le 2^{|\beta|}$ then $\aleph_\beta^{|\beta|}=2^{|\beta|}\le\prod_{\xi<\beta}\aleph_\xi\le\aleph_\beta^{|\beta|}$.
• Notice that ${\rm cf}(\alpha)={\rm cf}(\beta)={\rm cf}(\aleph_\beta)$ and ${\rm cf}(\beta)\le|\beta|$, so the second possibility does not occur.
• Suppose now that we are in the third possibility, i.e., $2^{|\beta|}<\aleph_\beta$ and $\rho\mapsto\rho^{|\beta|}$ is eventually constant as $\rho$ approaches $\aleph_\beta$. Then $\aleph_\beta^{|\beta|}=(<\aleph_\beta)^{|\beta|}=\sup_{\nu<{\rm cf}(\alpha)}\aleph_{|\beta|+\gamma_\nu}^{|\beta|}=\sup_\nu\prod_{\xi<|\beta|+\gamma_\nu}\aleph_\xi$, by induction (it is here that we used the assumption that $\alpha$ is a limit of limit ordinals). And $\sup_\nu\prod_{\xi<|\beta|+\gamma_\nu}\aleph_\xi\le\prod_{\xi<\beta}\aleph_\xi\le\aleph_\beta^{|\beta|}$.
• Finally, if $2^{|\beta|}<\aleph_\beta$ and $\rho\mapsto\rho^{|\beta|}$ is not eventually constant as $\rho$ approaches $\aleph_\beta$, then $\aleph_\beta^{|\beta|}=\aleph_\beta^{{\rm cf}(\alpha)}$ and $\aleph_\beta^{{\rm cf}(\alpha)}=\prod_{\nu<{\rm cf}(\alpha)}\aleph_{|\beta|+\gamma_\nu}$, by exercise 2, but $\prod_{\nu<{\rm cf}(\alpha)}\aleph_{|\beta|+\gamma_\nu}\le\prod_{\xi<\beta}\aleph_\xi\le\aleph_\beta^{|\beta|}$, and we are done.

## 116c- Lecture 8

April 24, 2008

We defined infinite sums and products and showed that if $\max\{2,\kappa_i\}\le\lambda_i$ for all $i\in I$, then $\sum_{i\in I}\kappa_i\le\prod_{i\in I}\lambda_i$.

We also showed that if $(\kappa_i:i<\mbox{cf}(\kappa))$ is an increasing sequence of cardinals cofinal in $\kappa$, then $\prod_{i\in\mbox{\small cf}(\kappa)}\kappa_i=\kappa^{\mbox{\small cf}(\kappa)}$. In particular, $\prod_n\aleph_n=\aleph_\omega^{\aleph_0}$.

We defined singular cardinals and showed that (with choice) all successor cardinals are regular and all limit cardinals $\aleph_\alpha$ are singular unless $\alpha=\aleph_\alpha$. We showed that, indeed, there are fixed points of the aleph function, as a particular case of a result about normal functions. We defined (weakly) inaccessible cardinals as the regular limit cardinals (thus, regular fixed points of the aleph function).

Correction. I believe during lecture I mixed two arguments by mistake, making one of the proofs come out unnecessarily confusing, so I will present the correct argument here, for clarity.

In lecture we showed that if $F$ is a normal function, then it has a proper class of fixed points. Thus, we can enumerate them in increasing order. Let $G$ be this enumeration.

Claim. $G$ was also normal.

Proof. We need to check that $G$ is continuous. Let $\gamma$ be a limit ordinal and suppose that $\tau=\sup_{\beta<\gamma}G(\beta)$. We need to show that $G(\gamma)=\tau$.

By definition, this means that:

1. $\tau$ is a fixed point of $F$, and
2. $\tau$ is the $\gamma$-th fixed point of $F$.

But, clearly, if $\tau$ is a fixed point, then it must be the $\gamma$-th one, since we have already enumerated $\gamma$ fixed points below $\tau$, and any fixed point below $\tau$ is below some $G(\beta)$ with $\beta<\gamma$, so it is not even the $\beta$-th one.

So we only need to check that $F(\tau)=\tau$. But $\tau=\sup_{\beta<\gamma}G(\beta)$ and each $G(\beta)$ is a fixed point of $F$ (again, by definition of $G$), so $\tau=\sup_{\beta<\gamma}F(G(\beta))=F(\sup_{\beta<\gamma}G(\beta))=F(\tau)$, where the previous to last equality is by continuity of $F$. ${\sf QED}$

It follows that $G$ itself has a proper class of fixed points. It is also the case that there is a proper class of fixed points of $F$ that are limits of fixed points of $F$: Simply notice that the argument above shows that any limit of fixed points of $F$ is itself a fixed point. Thus, we have:

Corollary. The function $H:{\sf ORD}\to{\sf ORD}$ enumerating the limit points of $G$ (i.e., the fixed points of $F$ that are themselves limit of fixed points) is normal.

I believe during lecture I mixed at some point $H$ and $G$ (although I never explicitly mentioned $H$). Hopefully the above clarifies the argument. For the particular case of $F(\alpha)=\aleph_\alpha$, we have that $G$ enumerates the ordinals $\alpha$ such that $\alpha=\aleph_\alpha$, so $G(0)$ is the first such cardinal. The function $H$ enumerates the limit points of $G$, so $H(0)=G(\omega)$. Notice that $\mbox{cf}(H(0))=\mbox{cf}(G(\omega))=\omega$. One can easily see that if $\kappa$ is a weakly inaccessible cardinal, then $\kappa$ is a fixed point of $F$, $G$ and $H$.

In fact, define $F_0(\alpha)=\aleph_\alpha$ for all $\alpha$, let $F_{\beta+1}$ be the enumeration of the fixed points of $F_\beta$, and let $F_\gamma$ (for $\gamma$ limit) enumerate the ordinals $\kappa$ that are simultaneously fixed points of all the $F_\beta$ for $\beta<\gamma$. Then, if $\kappa$ is weakly inaccessible, then $F_\alpha(\kappa)=\kappa$ for all $\alpha<\kappa$.

Remark.

1.  We did not prove that weakly inaccessible cardinals exist. The examples given in lecture of fixed points of the aleph function have cofinality $\omega$ and, similarly, we can produce fixed points of arbitrarily large cofinality, but the argument falls short of finding regular fixed points (in fact, we can show that each $F_\alpha$ as defined above is normal, but the argument does not show that we can “diagonalize” to obtain a $\kappa$ fixed for all $F_\alpha$ with $\alpha<\kappa$). In fact, it is consistent with ${\sf ZFC}$ that all limit cardinals are singular. However, it is the general consensus among set theorists that the existence of inaccessible cardinals is one of the axioms of set theory that the original list ${\sf ZFC}$ somehow missed.
2. We defined normal functions as proper classes; however, we can as well define for any ordinal $\alpha$ a function $F:\alpha\to{\sf ORD}$ to be normal iff it is strictly increasing and continuous. The same argument as in lecture (or above) then shows that if $\mbox{cf}(\kappa)>\omega$ and $F:\kappa\to\kappa$ is normal, then there is a closed and unbounded subset of $\kappa$ consisting of fixed points of $F$. It turns out that closed unbounded sets are very important in infinitary combinatorics, and we will study them in more detail in subsequent lectures.

## 116c- Lecture 7

April 22, 2008

We presented the proof that “$k$-trichotomy” implies choice. The following is still open:

Question. (${\sf ZF}$) Assume that $X$ is non-well-orderable. Is there a countably infinite family of pairwise size-incomparable sets?

We mentioned a few (familiar) statements that fail in the absence of choice, like the existence of bases for any vector space, Tychonoff’s theorem, or the “surjective” version of the Schröder-Bernstein theorem.

We defined addition, multiplication and exponentiation of cardinals, and verified that addition and multiplication are trivial. We stated the continuum hypothesis ${\sf CH}$, and the generalized continuum hypothesis ${\sf GCH}$.

We want to prove (in subsequent lectures) a few non-trivial results about the behavior of exponentiation. In order to do this, we need the key notion of cofinality. We proved a few basic facts about cofinality and defined regular cardinals.

## 116c- Homework 3

April 22, 2008

Update. Now due Wednesday, April 30 at 2:30 pm.

Corrections. (Thanks to Fedor Manin for noticing these.)

• On Exercise 2.(c), assume in addition that $(\lambda,\alpha)$ satisfies the conditions of $(\alpha,\beta)$ in item 2.(a); this should really be all that is needed of 2.(c) for later parts of the exercise.
• On Exercise 2.(f), we also need $n>0$.
• Update. Here is a quick sketch of the proof of the Milner-Rado paradox.

First notice that the result is clear if $\kappa=\omega$, since we can write any $\alpha<\omega_1$ as a countable union of singletons. So we may assume that $\kappa$ is uncountable.

Notice that $|\kappa^{\cdot\rho}|=\kappa$. This can be checked either by induction on $\rho<\kappa^+$, or by using the characterization of ordinal exponentiation in terms of functions of finite support.

Notice that the function $\alpha\mapsto\omega^{\cdot \alpha}$ is normal. By the above, it follows that $\omega^{\cdot\lambda}=\lambda$ for all uncountable cardinals $\lambda$. In particular, it suffices to prove the result for ordinals $\alpha$ that are an ordinal power of $\kappa$, since these ordinals are cofinal in $\kappa^+$, and a representation as desired for an ordinal gives (by restriction) such a representation for any smaller ordinal.

By the above, $\kappa^{\cdot\rho}=\omega^{\cdot\kappa\cdot\rho}$ for any $\rho$. It is easy to see that for any $\delta$, if $\alpha<\omega^{\cdot\delta}$, then the interval $\null[\alpha,\omega^{\cdot\delta})$ is order isomorphic to $\omega^{\cdot\delta}$; this can be proved by a straightforward induction on $\delta$.

For any $\alpha<\kappa^+$, we can write $\kappa^{\cdot\alpha+1}=\bigcup_{\nu<\kappa}A_\nu$, where $A_\nu=[\kappa^{\cdot \alpha}\cdot\nu,\kappa^{\cdot\alpha}\cdot(\nu+1))$ so it has order type $\kappa^{\cdot\alpha}$.

Also, if $\alpha$ is a limit ordinal below $\kappa^+$, then we can write $\alpha=\sup_{\nu<\mbox{\small cf}(\alpha)}\beta_\nu$ for some strictly increasing continuous sequence $(\beta_\nu:\nu<\mbox{cf}(\alpha))$ cofinal in $\alpha$. Let $A_0=\kappa^{\cdot\beta_1}$ and $A_\nu=[\kappa^{\cdot\beta_\nu},\kappa^{\cdot\beta_{\nu+1}})$ for $0<\nu<\mbox{cf}(\alpha)$. Then $\kappa^{\cdot\alpha}=\bigcup_\nu A_\nu$ and each $A_\nu$ has order type $\kappa^{\cdot\beta_{\nu+1}}$.

[That the sequence $\beta_\nu$ is continuous (at limits) ensures that the $A_\nu$ cover $\kappa^{\cdot \alpha}$. That they have the claimed order type follows from the “straightforward inductive argument” three paragraphs above.]

So we have written each $\kappa^{\cdot\rho}$ as an increasing union of $\sigma$ many intervals whose order types are ordinal powers of $\kappa$, and $\sigma$ is either $\kappa$ or $\mbox{cf}(\rho)$. Now proceed by induction. We may assume that each ordinal below $\kappa^{\cdot\rho}$ can be written as claimed in the paradox. In particular, each $A_\nu$, having order type an ordinal smaller than $\kappa^{\cdot\rho}$, can be written that way, say $A_\nu=\bigcup_n A_{\nu,n}$ where $\mbox{ot}(A_{\nu,n})<\kappa^{\cdot n}$.

If $\sigma=\omega$, this immediately gives the result for $\kappa^{\cdot\rho}$: Take $X_0=\emptyset$ and $X_{2^m(2n+1)}=A_{m,n}$. Clearly their union is $\kappa^{\cdot\rho}$ and they have small order type as required.

If $\sigma>\omega$, take $X_0=X_1=\emptyset$ and $X_{n+2}=\bigcup_\nu A_{\nu,n}$. Again, their union is $\kappa^{\cdot\rho}$, and $\mbox{ot}(X_{n+2})$ is at most the order type of concatenating $\kappa$ many copies of $\kappa^{\cdot n}$ [it is here that we use that $A_\nu for $\nu<\mu$], so $\mbox{ot}(X_{n+2})\le\kappa^{\cdot n+1}$.

## 116c- Lecture 6

April 18, 2008

We revisited the proof of the Schröder-Bernstein theorem and showed how arguments using recursion can provide explicit fixed points for the required map. Recall that if $f:A\to B$ and $g:B\to A$ are injective, we consider the monotone map $\pi:{\mathcal P}(A)\to{\mathcal P}(A)$ given by $\pi(X)=A\setminus g[B\setminus f[X]]$, since if $X$ is a  fixed point of $\pi$, then $A\setminus X=g[B\setminus f[X]]$, and we obtain a bijection $h:A\to B$ by setting $h(x)=f(x)$ if $x\in X$ and $h(x)=g^{-1}(x)$ if $x\in A\setminus X$.

We also presented a combinatorial proof considering “paths” along the graphs of $f$ and $g$ (surely folklore, but apparently first recorded by Paul Cohen) and Cantor’s original argument (using choice).

We then started the proof of the equivalence (in ${\sf ZF}$) of several versions of choice:

1. The well-ordering principle (our official version of ${\sf AC}$).
2. The existence of choice functions $f:{\mathcal P}(X)\setminus\{\emptyset\}\to X$ for any set $X$.
3. Zorn’s lemma.
4. Trichotomy: Given any sets $A$ and $B$, one of them injects into the other. (Called trichotomy as it gives that either $|A|=|B|$, $|A|<|B|$ or $|B|<|A|$.)
5. $k$-trichotomy (for a fixed $2\le k\in\omega$): Given any $k$ sets, at least one of them injects into another.

(The proof that (5) implies (1) will be given in Tuesday.)

## 116c- Homework 2

April 16, 2008

Due Tuesday, April 22 at 2:30 pm.