Exercises in Set Theory: Classical Independence Results

20 Mar 2013

I worked on Chapter 13 and 14 of Thomas Jech’s book ‘‘Set Theory’’.

Doing the exercises from these chapters gave me the opportunity to come back to the ‘‘classical’’ results about the independence of the Axiom of Choice and (Generalized) Continuum Hypothesis by Kurt Gödel and Paul Cohen. It’s funny to note that it’s easier to prove that AC holds in $L$ (essentially, the definition by ordinal induction provides the well-ordering of the class of contructible sets) than to prove that GCH holds in $L$ (you rely on AC in $L$ and on the technical condensation lemma). Actually, I believe Gödel found his proof for AC one or two years after the one for GCH. On the other hand, it is easy to make GCH fails (just add $\aleph_{2}$ Cohen reals by Forcing) but more difficult to make AC fails (e.g. AC is preserved by Forcing). This can be interpreted as AC being more ‘‘natural’’ than GCH.

After reading the chapters again and now I analyzed in details the claims, I’m now convinced about the correctness of the proof. There are only two points I didn’t verify precisely about the Forcing method (namely that all axioms of predicate calculus and rules of inference are compatible with the Forcing method ; that the Forcing/Generic Model theorems can be transported from the Boolean Algebra case to the general case) but these do not seem too difficult. Here are some notes about claims that were not obvious to me at the first reading. As usual, I hope they might be useful to the readers of that blog:

1. 1.

   In the first page of chapter 13, it is claimed that for any set $M$, $M\in\mathrm{def}(M)$ and $M\subseteq\mathrm{def}(M)\subseteq\operatorname{\mathcal{P}}(M)$. The first statement is always true because $M=\{x\in M:(M,\in)\models x=x\}\in\mathrm{def}(M)$ and ${(x=x)}^{(M,\in)}$ is $x=x$ by definition. However, the second statement can only be true if $M$ is transitive (since that implies $M\subseteq\operatorname{\mathcal{P}}(M)$). Indeed, if $M$ is transitive then for all $a\in M$ we have $a\subseteq M$ and since $x\in a$ is $\Delta_{0}$ we get $a=\{x\in M:(M,\in)\models x\in a\}\in\mathrm{def}(M)$. If moreover we consider $x\in X\in\mathrm{def}(M)$ then $x\in X\subseteq M$ so $x\in M\subseteq\mathrm{def}(M)$ and $\mathrm{def}(M)$ is also transitive. Hence the transitivity of the $L_{\alpha}$ can still be shown by ordinal induction.

2. 2.

   The proof of lemma 13.7 can not be done exactly by induction on the complexity of $G$, as suggested. For example to prove (ii) for $G=G_{2}=\cdot\times\cdot$, we would consider $\exists u\in F(...)\times H(...)\varphi(u)\Leftrightarrow\exists a\in F(...),\exists b\in H(...),\varphi((a,b))$ and would like to say that $\varphi((a,b))$ is $\Delta_{0}$. Nevertheless, we can not deduce that from the induction hypothesis. Hence the right thing to do is to prove the lemma for $G_{1}=\{\cdot,\cdot\}$ first and deduce the lemma for $G=(\cdot,\cdot)$ (and $G^{\prime}=(\cdot,\cdot,\cdot)$). Then we can proceed by induction.

3. 3.

   In the proof of theorem 13.18, it is mentioned that the assumption

   1. (i)

      $x<_{\alpha}y$ implies $x<_{\beta}y$

   2. (ii)

      $x\in L_{\alpha}$ and $y\in L_{\beta}\setminus L_{\alpha}$ implies $x<_{\beta}y$

   implies that if $x\in y\in L_{\alpha}$ then $x<_{\alpha}y$. To show that, we consider $\beta\leq\alpha$ the least ordinal such that $y\in L_{\beta}$. In particular, $\beta$ is not limit ($L_{0}=\emptyset$ and if $y\in L_{\beta}$ for some limit $\beta>0$ then there is $\gamma<\beta$ such that $y\in L_{\gamma}$) and we can write it $\beta=\gamma+1$. We have $y\in L_{\beta}=L_{\gamma+1}$ so there is a formula $\varphi$ and elements $a_{1},...,a_{n}\in L_{\gamma}$ such that $x\in y=\{z\in L_{\gamma}:(L_{\gamma},\in)\models\varphi(z,a_{1},...,a_{n})\}$. Hence $x\in L_{\gamma}$. Moreover by minimality of $\beta$, $y\in L_{\beta}\setminus L_{\gamma}$ so by (ii) we have $x<_{\beta}y$ and by (i) $x<_{\alpha}y$.

4. 4.

   In lemma 14.18, we have expressions that seem ill-defined for example $a_{u}(t)$ where $t\notin\operatorname{dom}(a_{u})$. This happens in other places, like lemma 14.17 or definition 14.27. The trick is to understand that the functions are extended by 0. Indeed, for any $x,y\in V^{B}$ if $x\subseteq y$ and $\forall t\in\operatorname{dom}(y)\setminus\operatorname{dom}(x),y(t)=0$ then

   $$\begin{gathered}\displaystyle\|y\subseteq x\|\\ \displaystyle=\prod_{t\in\operatorname{dom}(y)}\left(-y(t)+{\|t\in x\|}\right)\\ \displaystyle=\prod_{t\in\operatorname{dom}(x)}\left(-x(t)+{\|t\in x\|}\right)\\ \displaystyle=\|x\subseteq x\|=1\end{gathered}$$

   and similarly we get $\|x=y\|=1$. Then we can use the inequality page 207 ($\|\varphi(x)\|=\|x=y\|\cdot\|\varphi(x)\|\leq\|\varphi(y)\|=\|x=y\|\cdot\|\varphi(y)\|\leq\|\varphi(x)\|$) to replace $x$ by its extension $y$.

5. 5.

   In lemma 14.23, the inequality

   $$\|x\text{ is an ordinal}\|\leq\|x\in\check{\alpha}\|+\|x=\check{\alpha}\|+\|\check{\alpha}\in x\|$$

   seems obvious but I don’t believe that it can be proved so easily at that point. For example the proof from chapter 2 requires at least the Separation axiom and the $\Delta_{0}$ formulation from chapter 10 is based on the Axiom of Regularity. To solve that issue, it seems to me that the lemma should be moved after the proof that axioms of ZFC are valid in $V^{B}$. This is not an issue since lemma 14.23 is only used much later in lemma 14.31.

6. 6.

   Many details could be added to the proof of theorem 14.24, but let’s just mention Powerset. For any $u\in V^{B}$, some $u^{\prime}\in\operatorname{dom}(Y)$ is defined and satisfies $\|u\subseteq X\|\leq\|u=u^{\prime}\|$ (this follows from the definitions, using the Boolean inequality $-a+b\leq-a+b\cdot a$ to conclude). Since moreover $\forall t\in\operatorname{dom}(Y),Y(t)=1$ we get

   	$\displaystyle\|u\subseteq X\|\implies\|u\in Y\|$	$\displaystyle\geq-\|u=u^{\prime}\|+\sum_{t\in\operatorname{dom}(Y)}\left(\|u=t\|\cdot Y(t)\right)$
   		$\displaystyle=\sum_{t\in\operatorname{dom}(Y)}-\left(\|u\neq t\|\cdot\|u=u^{\prime}\|\right)$
   		$\displaystyle\geq\sum_{t\in\operatorname{dom}(Y)}\|u^{\prime}=t\|=1$

7. 7.

   In theorem 14.34, we prove that any $\kappa$ regular in $V$ remains regular in $V[G]$ (the hard case is really $\kappa$ uncountable and this assumption is implicitely used later to say that $\bigcup_{\alpha<\lambda}A_{\alpha}$ is bounded). It may not be obvious why this is enough. First recall that for any ordinal $\alpha$, $\operatorname{cf}^{V[G]}(\alpha)\leq\operatorname{cf}^{V}(\alpha)$, ${|\alpha|}^{V[G]}\leq{|\alpha|}^{V}$, and any (regular) cardinal in $V[G]$ is a (regular) cardinal in $V$. Next we have,

   	$\displaystyle\exists\alpha\in\mathrm{Ord},\operatorname{cf}^{V[G]}(\alpha)\leq\operatorname{cf}^{V}(\alpha)$	$\displaystyle\implies\exists\alpha\in\mathrm{Ord},\operatorname{cf}^{V[G]}(\operatorname{cf}^{V}(\alpha))\leq\operatorname{cf}^{V[G]}(\alpha)<\operatorname{cf}^{V}(\alpha)$
   		$\displaystyle\implies\exists\beta\textrm{ regular cardinal in }V,\textrm{ not regular cardinal in }V[G]$
   		$\displaystyle\implies\exists\beta\in\mathrm{Ord},\operatorname{cf}^{V[G]}(\beta)<\beta=\operatorname{cf}^{V}(\beta)$

   that is $\forall\alpha\in\mathrm{Ord},\operatorname{cf}^{V[G]}(\alpha)=\operatorname{cf}^{V}(\alpha)$ is equivalent to ‘‘$V$ and $V[G]$ have the same regular cardinals’’. Similarly, we can prove that $\forall\alpha\in\mathrm{Ord},{|\alpha|}^{V[G]}={|\alpha|}^{V}$ is equivalent to ‘‘$V$ and $V[G]$ have the same cardinals’’.

   The proof of theorem 14.34 shows that ‘‘$V$ and $V[G]$ have the same regular cardinals’’ and so to complete the proof, it is enough to show that $\forall\alpha,\operatorname{cf}^{V[G]}(\alpha)=\operatorname{cf}^{V}(\alpha)$ implies $\forall\alpha,{|\alpha|}^{V[G]}={|\alpha|}^{V}$. So suppose $\forall\alpha,\operatorname{cf}^{V[G]}(\alpha)=\operatorname{cf}^{V}(\alpha)$ and assume that there is $\alpha$ such that ${|\alpha|}^{V[G]}<{|\alpha|}^{V}$. Consider the least such $\alpha$. If $\beta={|\alpha|}^{V}$ then $\beta\leq\alpha$ so ${|\beta|}^{V[G]}\leq{|\alpha|}^{V[G]}<{|\alpha|}^{V}=\beta$. By minimality of $\alpha$, $\beta=\alpha$ and so $\alpha$ is a cardinal in $V$. $\alpha$ is actually regular in $V$. Otherwise, suppose $\operatorname{cf}^{V}(\alpha)<\alpha$ and let $\alpha=\bigcup_{\beta<\operatorname{cf}^{V}(\alpha)}X_{\beta}$ such that ${|X_{\beta}|}^{V}<{|\alpha|}^{V}$. By minimality of $\alpha$, we have ${|\operatorname{cf}^{V}(\alpha)|}^{V[G]}={|\operatorname{cf}^{V}(\alpha)|}^{V}$ and ${|X_{\beta}|}^{V[G]}={|X_{\beta}|}^{V}$. Then ${|\alpha|}^{V[G]}={|\operatorname{cf}^{V}(\alpha)|}^{V[G]}\sup_{\beta<\operatorname{cf}^{V}(\alpha)}{|X_{\beta}|}^{V[G]}={|\operatorname{cf}^{V}(\alpha)|}^{V}\sup_{\beta<\operatorname{cf}^{V}(\alpha)}{|X_{\beta}|}^{V}={|\alpha|}^{V}$, a contradiction. Finally, we get $\operatorname{cf}^{V}(\alpha)=\alpha={|\alpha|}^{V}>{|\alpha|}^{V[G]}\geq\operatorname{cf}^{V[G]}(\alpha)$. This is again a contradiction and so $\forall\alpha,{|\alpha|}^{V[G]}={|\alpha|}^{V}$.