Set Theory

Cardinal Arithmetic

content/set-theory/card-arithmetic/card-arithmetic.tex

% Part: set-theory% Chapter: card-arithmetic\documentclass[../../../include/open-logic-chapter]{subfiles}\begin{document}\olchapter{sth}{card-arithmetic}{Cardinal Arithmetic}\olimport{opps}\olimport{simp}\olimport{expotough}\olimport{ch}\olimport{fix}\OLEndChapterHook\end{document}

content/set-theory/card-arithmetic/opps.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{card-arithmetic}{opps}\olsection{Defining the Basic Operations}Since we do not need to keep track of order, cardinal arithmetic israther easier to define than ordinal arithmetic. We will defineaddition, multiplication, and exponentiation simultaneously. \begin{defn}When $\cardfont{a}$ and $\cardfont{b}$ are cardinals:\begin{align*}	\cardfont{a} \cardplus \cardfont{b} &\defis 	\card{\cardfont{a} \disjointsum \cardfont{b}}\\	\cardfont{a} \cardtimes \cardfont{b} &\defis 	\card{\cardfont{a} \times \cardfont{b}}\\	\cardexpo{\cardfont{a}}{\cardfont{b}} &\defis 	\card{\funfromto{\cardfont{b}}{\cardfont{a}}}\end{align*}where $\funfromto{X}{Y} = \Setabs{f}{f \text{ is a function } X \to Y}$.(It is easy to show that $\funfromto{X}{Y}$ exists for any sets $X$and $Y$; we leave this as an exercise.) \end{defn}\begin{prob}Prove in $\Zminus$ that $\funfromto{X}{Y}$ exists for any sets $X$and~$Y$. Working in $\ZF$, compute $\setrank{\funfromto{X}{Y}}$ from$\setrank{X}$ and $\setrank{Y}$, in the manner of\olref[sth][ord-arithmetic][using-addition]{rankcomputation}. \end{prob}It might help to explain this definition. Concerning addition: thisuses the notion of disjoint sum, $\disjointsum$, as defined in\olref[ord-arithmetic][add]{defdissum}; and it is easyto see that this definition gives the right verdict for finite cases.Concerning multiplication: \olref[sfr][set][pai]{cardnmprod} tells usthat if $A$ has $n$ members and $B$ has $m$ members then $A \times B$has $n \cdot m$ members, so our definition simply generalises the ideato transfinite multiplication. Exponentiation is similar: we aresimply generalising the thought from the finite to the transfinite.Indeed, in certain ways, transfinite cardinal arithmetic looks muchmore like ``ordinary'' arithmetic than does transfinite ordinalarithmetic:\begin{prop}\ollabel{cardplustimescommute}$\cardplus$ and $\cardtimes$ are commutative and associative. \end{prop}\begin{proof}For commutativity, by\olref[cardinals][cardsasords]{lem:CardinalsBehaveRight} itsuffices to observe that $\cardeq{(\cardfont{a} \disjointsum\cardfont{b})}{(\cardfont{b} \disjointsum \cardfont{a})}$ and$\cardeq{(\cardfont{a} \times \cardfont{b})}{(\cardfont{b} \times\cardfont{a})}$. We leave associativity as an exercise.\end{proof}\begin{prob}Prove that $\cardplus$ and $\cardtimes$ are associative.\end{prob}\begin{prop}$A$ is infinite iff $\card{A} \cardplus 1 = 1 \cardplus \card{A} = \card{A}$.\end{prop}\begin{proof}As in\olref[cardinals][classing]{generalinfinitycharacter}, from\olref[ord-arithmetic][using-addition]{ordinfinitycharacter} and\olref[cardinals][cardsasords]{lem:CardinalsBehaveRight}. \end{proof}This explains why we need to use different symbols for ordinal versuscardinal addition/multiplication: these are genuinely \emph{different}operations. This next pair of results shows that ordinal versuscardinal exponentiation are also different operations. (Recall that\olref[z][infinity-again]{defnomega} entails that $2 = \{0,1\}$):\begin{lem}\ollabel{lem:SizePowerset2Exp}$\card{\Pow{A}} = \cardexpo{2}{\card{A}}$, for any $A$.\end{lem}\begin{proof}For each subset $B \subseteq A$, let $\chi_B \in \funfromto{A}{2}$ be given by:\begin{align*}	\chi_{B}(x) &\defis	\begin{cases}		1 & \text{if }x\in B\\		0 & \text{otherwise.}	\end{cases}\end{align*}Now let $f(B) = \chi_B$; this defines !!a{bijection} $f \colon \Pow{A}\to \funfromto{A}{2}$. So $\cardeq{\Pow{A}}{\funfromto{A}{2}}$. Hence$\cardeq{\Pow{A}}{\funfromto{\card{A}}{2}}$, so that$\card{\Pow{A}} = \card{\funfromto{\card{A}}{2}} =2^{\card{A}}$.\end{proof}This snappy proof essentially subsumes the discussion of\olref[sfr][siz][red-alt]{sec}. There, we showed how to ``reduce'' theuncountability of $\Pow{\omega}$ to the uncountability of the set ofinfinite binary strings, $\Bin^\omega$. In effect, $\Bin^{\omega}$ isjust $\funfromto{\omega}{2}$; and the preceding proof showed that thereasoning we went through in \olref[sfr][siz][red-alt]{sec} will gothrough using any set~$A$ in place of~$\omega$. The result also yieldsa quick fact about cardinal exponentiation:\begin{cor}\ollabel{cantorcor}$\cardfont{a} < \cardexpo{2}{\cardfont{a}}$ for any cardinal~$\cardfont{a}$.\end{cor}\begin{proof}From Cantor's Theorem (\olref[sfr][siz][car]{thm:cantor}) and\olref{lem:SizePowerset2Exp}.\end{proof}\noindentSo $\omega < \cardexpo{2}{\omega}$. But note: this is a result about\emph{cardinal} exponentiation. It should be contrasted with\emph{ordinal} exponentiation, since in the latter case $\omega =\ordexpo{2}{\omega}$ (see \olref[ord-arithmetic][expo]{sec}).Whilst we are on the topic of cardinal exponentiation, we can also bea bit more precise about the ``way'' in which $\Real$ is!!{nonenumerable}.\begin{thm}\ollabel{continuumis2aleph0}$\card{\Real} = \cardexpo{2}{\omega}$\end{thm}\begin{proof}[Proof skeleton]There are plenty of ways to prove this. The most straightforward is toargue that $\cardle{\Pow{\omega}}{\Real}$ and$\cardle{\Real}{\Pow{\omega}}$, and then use Schr\"oder-Bernstein toinfer that $\cardeq{\Real}{\Pow{\omega}}$, and\olref[card-arithmetic][opps]{lem:SizePowerset2Exp} to inferthat $\card{\Real} = \cardexpo{2}{\omega}$. We leave it as an(illuminating) exercise to define injections $f \colon\Pow{\omega} \to \Real$ and $g \colon \Real \to \Pow{\omega}$.\end{proof}\begin{prob}Complete the proof of\olref[sth][card-arithmetic][opps]{continuumis2aleph0}, byshowing that $\cardle{\Pow{\omega}}{\Real}$ and$\cardle{\Real}{\Pow{\omega}}$.\end{prob}\end{document}

content/set-theory/card-arithmetic/simp.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{card-arithmetic}{simp}\olsection{Simplifying Addition and Multiplication}It turns out that transfinite cardinal addition and multiplication is\emph{extremely} easy. This follows from the fact that cardinals are(certain) ordinals, and so well-ordered, and so can be manipulated ina certain way. Showing this, though, is \emph{not} so easy. To start,we need a tricksy definition:\begin{defn}We define a \emph{canonical ordering}, $\canonord$, on pairs ofordinals, by stipulating that $\tuple{\alpha_1, \alpha_2} \canonord\tuple{\beta_1, \beta_2}$ iff either:\begin{enumerate}	\item $\max(\alpha_1, \alpha_2) < \max(\beta_1, \beta_2)$; or	\item $\max(\alpha_1, \alpha_2) = \max(\beta_1, \beta_2)$ and	$\alpha_1 < \beta_1$; or	\item $\max(\alpha_1, \alpha_2) = \max(\beta_1, \beta_2)$ and	$\alpha_1 = \beta_1$ and $\alpha_2 < \beta_2$\end{enumerate}\end{defn}\begin{lem}$\tuple{\alpha \times \alpha, \canonord}$ is a well-order, for anyordinal $\alpha$.\end{lem}\begin{proof}Evidently $\canonord$ is connected on $\alpha \times \alpha$. Forsuppose that neither $\tuple{\alpha_1, \alpha_2}$ nor $\tuple{\beta_1,\beta_2}$ is $\canonord$-less than the other. Then $\max(\alpha_1,\alpha_2) = \max(\beta_1, \beta_2)$ and $\alpha_1 = \beta_1$ and$\alpha_2 = \beta_2$, so that $\tuple{\alpha_1, \alpha_2} =\tuple{\beta_1,  \beta_2}$.To show well-ordering, let $X \subseteq \alpha\times\alpha$ benon-empty. Since $\alpha$ is an ordinal, some $\delta$ is the leastmember of $\Setabs{\max(\gamma_1, \gamma_2)}{\tuple{\gamma_1,\gamma_2} \in X}$. Now discard all pairs from$\Setabs{\tuple{\gamma_1,\gamma_2} \in X}{\max(\gamma_1, \gamma_2) =\delta}$ except those with least first coordinate; from among these,the pair with least second coordinate is the $\canonord$-least elementof $X$.\end{proof}\noindentNow for a teensy, simple observation:\begin{prop}\ollabel{simplecardproduct}If $\cardeq{\alpha}{\beta}$, then $\cardeq{\alpha \times \alpha}{\beta\times \beta}$. \end{prop}\begin{proof}Just let $f \colon \alpha \to \beta$ induce $\tuple{\gamma_1,\gamma_2} \mapsto \tuple{f(\gamma_1), f(\gamma_2)}$.\end{proof}\noindentAnd now we will put all this to work, in proving a crucial lemma:\begin{lem}\ollabel{alphatimesalpha}$\cardeq{\alpha}{\alpha \times \alpha}$, for any infinite ordinal$\alpha$\end{lem}\begin{proof}For reductio, let $\alpha$ be the least infinite ordinal for whichthis is false. \olref[sfr][siz][zigzag]{natsquaredenumerable} showsthat $\cardeq{\omega}{\omega\times\omega}$, so $\omega \in \alpha$.Moreover, $\alpha$ is a cardinal: suppose otherwise, for reductio;then $\card{\alpha} \in \alpha$, so that$\cardeq{\card{\alpha}}{\card{\alpha} \times \card{\alpha}}$, byhypothesis; and $\cardeq{\card{\alpha}}{\alpha}$ by definition; sothat $\cardeq{\alpha}{\alpha\times\alpha}$ by\olref{simplecardproduct}. Now, for each $\tuple{\gamma_1, \gamma_2} \in \alpha \times \alpha$,consider the segment:\begin{align*}	\text{Seg}(\gamma_1, \gamma_2) &= \Setabs{\tuple{\delta_1, \delta_2} \in \alpha \times \alpha}{\tuple{\delta_1, \delta_2} \canonord \tuple{\gamma_1, \gamma_2}}\end{align*}Letting $\gamma = \max(\gamma_1, \gamma_2)$, note that $\tuple{\gamma_1, \gamma_2} \canonord \tuple{\gamma+1, \gamma + 1}$. So, when $\gamma$ is infinite, observe:\begin{align*}	\text{Seg}(\gamma_1, \gamma_2) & 	\precsim ((\gamma \ordplus 1)\ordtimes (\gamma \ordplus 1))\\	&\approx (\gamma \ordtimes \gamma)	\text{, by \olref[ord-arithmetic][using-addition]{ordinfinitycharacter} and 	\olref{simplecardproduct}}\\	&\approx \gamma \text{, by the induction hypothesis}\\	& \prec \alpha\text{, since $\alpha$ is a cardinal}\end{align*}So $\ordtype{\alpha\times \alpha, \canonord} \leq \alpha$, and hence$\cardle{\alpha \times \alpha}{\alpha}$. Since of course$\cardle{\alpha}{\alpha \times \alpha}$, the result follows bySchr\"oder-Bernstein. \end{proof}Finally, we get to our simplifying result:\begin{thm}\ollabel{cardplustimesmax}If $\cardfont{a}, \cardfont{b}$ are infinite cardinals, then:\[	\cardfont{a}\cardtimes \cardfont{b} = \cardfont{a} \cardplus \cardfont{b} =\text{max}(\cardfont{a}, \cardfont{b}).\]\end{thm}\begin{proof}Without loss of generality, suppose $\cardfont{a} = \max(\cardfont{a},\cardfont{b})$. Then invoking \olref{alphatimesalpha},$\cardfont{a}\cardtimes\cardfont{a} = \cardfont{a} \leq \cardfont{a}\cardplus \cardfont{b} \leq \cardfont{a} \cardplus \cardfont{a} \leq\cardfont{a} \cardtimes \cardfont{a}$. \end{proof}\noindent Similarly,if $\cardfont{a}$ is infinite, an $\cardfont{a}$-sized union of$\leq\cardfont{a}$-sized sets has size $\leq\cardfont{a}$:\begin{prop}\ollabel{kappaunionkappasize}Let $\cardfont{a}$ be an infinite cardinal. For each ordinal $\beta\in \cardfont{a}$, let $X_\beta$ be a set with $\card{X_\beta} \leq\cardfont{a}$. Then $\card{\bigcup_{\beta \in \cardfont{a}} X_\beta}\leq \cardfont{a}$.\end{prop}\begin{proof}For each $\beta \in \cardfont{a}$, fix !!a{injection} $f_\beta \colonX_\beta \to \cardfont{a}$.\footnote{How are these ``fixed''? See \olref[sth][choice][countablechoice]{sec}.} Define !!a{injection} $g \colon\bigcup_{\beta \in \cardfont{a}} X_\beta \to \cardfont{a} \times\cardfont{a}$ by $g(v) = \tuple{\beta, f_\beta(v)}$, where $v \inX_\beta$ and $v \notin X_\gamma$ for any $\gamma \in \beta$. Now$\bigcup_{\beta \in \cardfont{a}} X_\beta \preceq \cardfont{a} \times\cardfont{a} \approx \cardfont{a}$ by \olref{cardplustimesmax}.\end{proof}\end{document}

content/set-theory/card-arithmetic/expotough.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{card-arithmetic}{expotough}\olsection[Some Simplifications]{Some Simplification with Cardinal Exponentiation}Whilst defining $\canonord$ was a little involved, the upshot is auseful result concerning cardinal addition and multiplication,\olref[simp]{cardplustimesmax}. Transfinite exponentiation, however,cannot be simplified so straightforwardly. To explain why, we startwith a result which extends a familiar pattern from the finitary case(though its proof is at a high level of abstraction):\begin{prop}\ollabel{simplecardexpo}$\cardexpo{\cardfont{a}}{\cardfont{b} \cardplus \cardfont{c}} =\cardexpo{\cardfont{a}}{\cardfont{b}} \cardtimes\cardexpo{\cardfont{a}}{\cardfont{c}}$ and$\cardexpo{(\cardexpo{\cardfont{a}}{\cardfont{b}})}{\cardfont{c}} =\cardexpo{\cardfont{a}}{\cardfont{b} \cardtimes \cardfont{c}}$, forany cardinals $\cardfont{a}, \cardfont{b}, \cardfont{c}$.\end{prop}\begin{proof}For the first claim, consider a function $f \colon(\cardfont{b}\disjointsum\cardfont{c}) \to \cardfont{a}$. Now ``splitthis'', by defining $f_\cardfont{b}(\beta) = f(\beta, 0)$ for each$\beta \in \cardfont{b}$, and $f_\cardfont{c}(\gamma) = f(\gamma, 1)$for each $\gamma \in \cardfont{c}$. The map $f \mapsto(f_{\cardfont{b}} \times f_\cardfont{c})$ is !!a{bijection}$\funfromto{\cardfont{b} \disjointsum \cardfont{c}}{\cardfont{a}} \to(\funfromto{\cardfont{b}}{\cardfont{a}} \times\funfromto{\cardfont{c}}{\cardfont{a}})$. For the second claim, consider a function $f \colon \cardfont{c} \to(\funfromto{\cardfont{b}}{\cardfont{a}})$; so for each $\gamma \in\cardfont{c}$ we have some function $f(\gamma) \colon \cardfont{b} \to\cardfont{a}$. Now define $f^*(\beta, \gamma) = (f(\gamma))(\beta)$for each $\tuple{\beta, \gamma} \in \cardfont{b} \times \cardfont{c}$.The map $f \mapsto f^*$ is !!a{bijection}$\funfromto{\cardfont{c}}{(\funfromto{\cardfont{b}}{\cardfont{a}})}\to \funfromto{\cardfont{b} \cardtimes \cardfont{c}}{\cardfont{a}}$. \end{proof}Now, what we would \emph{like} is an easy way to compute$\cardexpo{\cardfont{a}}{\cardfont{b}}$ when we are dealing withinfinite cardinals. Here is a nice step in this direction:\begin{prop}\ollabel{cardexpo2reduct}If $2 \leq \cardfont{a} \leq \cardfont{b}$ and $\cardfont{b}$ isinfinite, then $\cardexpo{\cardfont{a}}{\cardfont{b}} =\cardexpo{2}{\cardfont{b}}$\end{prop}\begin{proof}\begin{align*}	\cardexpo{2}{\cardfont{b}} &\leq 	\cardexpo{\cardfont{a}}{\cardfont{b}}\text{, as $2 \leq \cardfont{a}$}\\	&\leq \cardexpo{(2^\cardfont{a})}{\cardfont{b}}	\text{, by \olref[opps]{lem:SizePowerset2Exp}}\\	&= \cardexpo{2}{\cardfont{a} \cardtimes \cardfont{b}}	\text{, by \olref{simplecardexpo}} \\	&= \cardexpo{2}{\cardfont{b}}	\text{, by \olref[simp]{cardplustimesmax}}\end{align*}\end{proof}We should not really expect to be able to simplify this any further,since $\cardfont{b} < \cardexpo{2}{\cardfont{b}}$ by\olref[card-arithmetic][opps]{lem:SizePowerset2Exp}.However, this does not tell us what to say about$\cardexpo{\cardfont{a}}{\cardfont{b}}$ when $\cardfont{b} <\cardfont{a}$. Of course, if $\cardfont{b}$ is \emph{finite}, we knowwhat to do.\begin{prop}If $\cardfont{a}$ is infinite and $n \in \omega$ then$\cardexpo{\cardfont{a}}{n} = \cardfont{a}$\end{prop}\begin{proof}$\cardexpo{\cardfont{a}}{n} = \cardfont{a} \cardtimes \cardfont{a}\cardtimes \ldots \cardtimes \cardfont{a} = \cardfont{a}$, by \olref[simp]{cardplustimesmax}.\end{proof}\noindent Additionally, in some other cases, we can control the size of$\cardexpo{\cardfont{a}}{\cardfont{b}}$:\begin{prop}If $2 \leq \cardfont{b} < \cardfont{a} \leq\cardexpo{2}{\cardfont{b}}$ and $\cardfont{b}$ is infinite, then$\cardexpo{\cardfont{a}}{\cardfont{b}} = \cardexpo{2}{\cardfont{b}}$\end{prop}\begin{proof}$\cardexpo{2}{\cardfont{b}}\leq \cardexpo{\cardfont{a}}{\cardfont{b}}\leq \cardexpo{(\cardexpo{2}{\cardfont{b}})}{\cardfont{b}} =\cardexpo{2}{\cardfont{b}\cardtimes\cardfont{b}} =\cardexpo{2}{\cardfont{b}}$, reasoning as in \olref{cardexpo2reduct}.\end{proof}\noindent But, beyond this point, things become rather more subtle.\end{document}

content/set-theory/card-arithmetic/ch.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{card-arithmetic}{ch}\olsection{The Continuum Hypothesis}The previous result hints (correctly) that cardinal exponentiationwould be quite \emph{easy}, if infinite cardinals are guaranteed to``play straightforwardly'' with powers of $2$, i.e., (by\olref[opps]{lem:SizePowerset2Exp}) with taking powersets. But wecannot assume that infinite cardinals \emph{do} play straightforwardly powersets. To start unpacking this, we introduce some nice notation.\begin{defn}Where $\cardsucc{\cardfont{a}}$ is the least cardinal strictly greaterthan $\cardfont{a}$, we define two infinite sequences:\begin{align*}	\aleph_{0} &\defis \omega & 			\beth_{0} &\defis \omega\\	\aleph_{\alpha \ordplus 1} &\defis \cardsucc{(\aleph_{\alpha})} &	\beth_{\alpha+1} &\defis \cardexpo{2}{\beth_{\alpha}}\\	\aleph_{\alpha} &\defis \bigcup_{\beta< \alpha} \aleph_{\beta} &	\beth_{\alpha} &\defis \bigcup_{\beta < \alpha}\beth_{\beta} & \text{when $\alpha$ is a limit ordinal}.	\end{align*}\end{defn}The definition of $\cardsucc{\cardfont{a}}$ is in order, since\olref[cardinals][classing]{lem:NoLargestCardinal} tells us that, for eachcardinal $\cardfont{a}$, there is some cardinal greater than$\cardfont{a}$, and Transfinite Induction guarantees that there is a\emph{least} cardinal greater than $\cardfont{a}$. The rest of thedefinition of $\cardfont{a}$ is provided by transfinite recursion. Cantor introduced this ``$\aleph$'' notation; this is \emph{aleph},the first letter in the Hebrew alphabet and the first letter in theHebrew word for ``infinite''. Peirce introduced the ``$\beth$''notation; this is \emph{beth}, which is the second letter in theHebrew alphabet.\footnote{Peirce used this notation in a letter toCantor of December 1900. Unfortunately, Peirce also gave a badargument there that $\beth_\alpha$ does not exist for $\alpha \geq\omega$.} Now, these notations provide us with infinite cardinals.\begin{prop}$\aleph_\alpha$ and $\beth_\alpha$ are cardinals, for everyordinal $\alpha$. \end{prop}\begin{proof}Both results hold by a simple transfinite induction. $\aleph_0 =\beth_0 = \omega$ is a cardinal by\olref[cardinals][classing]{omegaisacardinal}. Assuming $\aleph_\alpha$ and$\beth_\alpha$ are both cardinals, $\aleph_{\alpha+1}$ and$\beth_{\alpha+1}$ are explicitly defined as cardinals. And the unionof a set of cardinals is a cardinal, by\olref[cardinals][classing]{unioncardinalscardinal}.\end{proof}\noindentMoreover, every infinite cardinal is an $\aleph$:\begin{prop}If $\cardfont{a}$ is an infinite cardinal, then $\cardfont{a} =\aleph_\gamma$ for some unique $\gamma$.\end{prop}\begin{proof}By transfinite induction on cardinals. For induction, suppose that if$\cardfont{b} < \cardfont{a}$ then $\cardfont{b} =\aleph_{\gamma_\cardfont{b}}$. If $\cardfont{a} =\cardsucc{\cardfont{b}}$ for some $\cardfont{b}$, then $\cardfont{a} =\cardsucc{(\aleph_{\gamma_\cardfont{b}})}=\aleph_{\gamma_\cardfont{b}+1}$. If $\cardfont{a}$ is not thesuccessor of any cardinal, then since cardinals are ordinals$\cardfont{a} = \bigcup_{\cardfont{b} < \cardfont{a}} \cardfont{b} =\bigcup_{\cardfont{b} < \cardfont{a}}{\aleph_{\gamma_\cardfont{b}}}$,so $\cardfont{a} = \aleph_\gamma$ where $\gamma =\bigcup_{\cardfont{b} < \cardfont{a}}\gamma_\cardfont{b}$. \end{proof}Since every infinite cardinal is an $\aleph$, this prompts us to ask:is every infinite cardinal a~$\beth$? Certainly if that \emph{were}the case, then the infinite cardinals would ``play straightforwardly''with the operation of taking powersets. Indeed, we would have thefollowing:\begin{defish}\emph{Generalized Continuum Hypothesis} (GCH). $\aleph_\alpha  = \beth_\alpha$, for all $\alpha$. \end{defish}Moreover, if GCH held, then we could make some considerablesimplifications with cardinal exponentiation. In particular, we couldshow that when $\cardfont{b} < \cardfont{a}$, the value of$\cardexpo{\cardfont{a}}{\cardfont{b}}$ is trapped by$\cardfont{a}\leq \cardexpo{\cardfont{a}}{\cardfont{b}} \leq\cardsucc{\cardfont{a}}$. We could then go on to give preciseconditions which determine which of the two possibilities obtains(i.e., whether $\cardfont{a} = \cardexpo{\cardfont{a}}{\cardfont{b}}$or $\cardexpo{\cardfont{a}}{\cardfont{b}} =\cardsucc{\cardfont{a}}$).\footnote{The condition is dictated by\emph{cofinality}.}But GCH is a \emph{hypothesis}, not a \emph{theorem}. In fact,\citet{Godel1938} proved that if $\ZFC$ is consistent, then so is$\ZFC + \text{GCH}$. But it later turned out that we can equally add$\lnot$GCH to $\ZFC$. Indeed, consider the simplest non-trivial\emph{instance} of GCH, namely: \begin{defish}\emph{Continuum Hypothesis} (CH). $\aleph_1 = \beth_1$. \end{defish}\citet{Cohen1963} proved that if $\ZFC$ is consistent then so is $\ZFC+ \lnot\text{CH}$. So the Continuum Hypothesis is independent from $\ZFC$.The Continuum Hypothesis is so-called, since ``the continuum'' isanother name for the real line, $\Real$.\olref[opps]{continuumis2aleph0} tells us that $\card{\Real} =\beth_1$. So the Continuum Hypothesis states that there is no cardinalbetween the cardinality of the natural numbers, $\aleph_0 = \beth_0$,and the cardinality of the continuum, $\beth_1$.Given the \emph{independence} of (G)CH from $\ZFC$, what should sayabout their \emph{truth}? Well, there is \emph{much} to say. Indeed,and much fertile recent work in set theory has been directed atinvestigating these issues. But two very quick points are certainly worthemphasising. First: it does not \emph{immediately} follow from these formalindependence results that either GCH or CH is \emph{indeterminate} intruth value. After all, maybe we just need to add more axioms, whichstrike us as natural, and which will settle the question one way oranother. G\"odel himself suggested that this was the right response. Second: the independence of CH from $\ZFC$ is certainly\emph{striking}, but it is certainly not \emph{incredible} (in theliteral sense). The point is simply that, for all $\ZFC$ tells us,moving from cardinals to their successors may involve a less blunttool than simply taking powersets. %The operation of taking powersets moves us from one stage of the %hierarchy to its successor stage (from $V_{\alpha}$ to %$V_{\alpha+1}$). With those two observations made, if you want to know more, you willnow have to turn to the various philosophers and mathematicians withhorses in the race.\footnote{Though you might want to start by reading \citet[\S15.6]{Potter2004}.}\end{document}

content/set-theory/card-arithmetic/fix.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{card-arithmetic}{fix}\olsection{$\aleph$-Fixed Points}In \olref[spine][]{chap}, we suggested that Replacement stands in needof justification, because it forces the hierarchy to be rather tall.Having done some cardinal arithmetic, we can give a littleillustration of the height of the hierarchy. Evidently $0 < \aleph_0$, and $1 < \aleph_1$, and $2 < \aleph_2$\ldotsand, indeed, the difference in size only gets \emph{bigger} with everystep. So it is tempting to conjecture that $\kappa< \aleph_\kappa$for every ordinal $\kappa$. But this conjecture is \emph{false}, given $\ZFC$. In fact, we canprove that there are \emph{$\aleph$-fixed-points}, i.e.,cardinals $\kappa$ such that $\kappa=\aleph_\kappa$. \begin{prop}\ollabel{alephfixed}There is an $\aleph$-fixed-point.\end{prop}\begin{proof}Using recursion, define:\begin{align*}	\kappa_0 &= 0\\	\kappa_{n+1} &= \aleph_{\kappa_n}\\	\kappa&= \bigcup_{n < \omega}\kappa_n\end{align*}Now $\kappa$ is a cardinal by\olref[cardinals][classing]{unioncardinalscardinal}. But now:\[	\kappa= \bigcup_{n < \omega} \kappa_{n+1} = 	\bigcup_{n < \omega}\aleph_{\kappa_n} = 	\bigcup_{\alpha < \kappa}\aleph_\alpha = \aleph_\kappa\]%	By construction, $\kappa$ is the least cardinal greater than each%	$\kappa_n$. So $\aleph_\kappa$ is the least cardinal greater than%	each $\aleph_{\kappa_n}$, and hence greater than each%	$\kappa_{n+1}$. But equally $\kappa$ is the least cardinal greater%	than each $\kappa_{n+1} = \aleph_{\kappa_n}$. So $\kappa=%	\aleph_\kappa$.\end{proof}Boolos once wrote an article about exactly the $\aleph$-fixed-point wejust constructed. After noting the existence of $\kappa$, at the startof his article, he said:\begin{quote}	[$\kappa$ is] a \emph{pretty big} number, by the lights of those	with no previous exposure to  set theory,  so big, it seems to me,	that  it calls into question the truth of any theory, one of whose	assertions is the claim that there are at least $\kappa$ objects.	\citep[p.~257]{Boolos2000}\end{quote}And he ultimately concluded his paper by asking:\begin{quote}	[do] we  suspect that,  however  it  may  have  been  at  the	beginning  of  the  story,  by  the  time  we have come thus  far	the wheels  are  spinning  and  we  are no longer  listening  to	a description  of  anything  that  is the case?	\citep[p.~268]{Boolos2000}\end{quote}If we have, indeed, outrun ``anything that is the case'', then we mustpoint the finger of blame directly at Replacement. For it is thisaxiom which allows our proof to work. In which case, one assumes,Boolos would need to revisit the claim he made, a few decades earlier,that Replacement has ``no undesirable'' consequences (see\olref[replacement][extrinsic]{sec}).But is the existence of $\kappa$ so bad? It might help, here, toconsider Russell's \emph{Tristram Shandy paradox}. Tristram Shandydocuments his life in his diary, but it takes him a year to record asingle day. With every passing year, Tristram falls further andfurther behind: after one year, he has recorded only one day, and haslived 364 days unrecorded days; after two years, he has only recordedtwo days, and has lived 728 unrecorded days; after three years, he hasonly recorded three days, and lived 1092 unrecordeddays \dots\footnote{Forgetting about leap years.} Still, if Tristramis \emph{immortal}, Tristram will manage to record every day, for hewill record the $n$th day on the $n$th year of his life. And so, ``atthe end of time'', Tristram will have a complete diary. Now: why is this so different from the thought that $\alpha$ issmaller than $\aleph_\alpha$---and indeed, increasingly, desperatelysmaller---up until $\kappa$, at which point, we catch up, and $\kappa= \aleph_\kappa$?Setting that aside, and assuming we accept $\ZFC$, let's close with alittle more fun concerning fixed-point constructions. The next threeresults establish, intuitively, that there is a (non-trivial) point atwhich the hierarchy is as wide as it is tall:\begin{prop}\ollabel{bethfixed}There is a $\beth$-fixed-point, i.e., a $\kappa$ such that $\kappa=\beth_\kappa$.\end{prop}\begin{proof}As in \olref{alephfixed}, using ``$\beth$'' in place of ``$\aleph$''. \end{proof}\begin{prop}\ollabel{stagesize}$\card{V_{\omega+\alpha}} = \beth_{\alpha}$. If $\omega \ordtimes\omega \leq \alpha$, then $\card{V_\alpha} = \beth_\alpha$.\end{prop}\begin{proof}The first claim holds by a simple transfinite induction. The secondclaim follows, since if $\omega \ordtimes \omega \leq \alpha$ then$\omega + \alpha = \alpha$. To establish this, we use facts aboutordinal arithmetic from \olref[ord-arithmetic][]{chap}. First notethat $\omega \ordtimes \omega = \omega \ordtimes (1 \ordplus \omega) =(\omega  \ordtimes 1) \ordplus (\omega\ordtimes\omega) = \omega\ordplus (\omega \ordtimes \omega)$. Now if $\omega \ordtimes \omega\leq \alpha$, i.e., $\alpha = (\omega\ordtimes\omega) \ordplus \beta$for some $\beta$, then $\omega \ordplus \alpha = \omega \ordplus((\omega \ordtimes \omega) \ordplus \beta) = (\omega \ordplus (\omega\ordtimes \omega)) \ordplus \beta = (\omega \ordtimes \omega) \ordplus\beta = \alpha$. \end{proof}\begin{cor}There is a $\kappa$ such that $\card{V_\kappa} = \kappa$.\end{cor}\begin{proof}Let $\kappa$ be a $\beth$-fixed point, as given by \olref{bethfixed}.Clearly $\omega \ordtimes \omega < \kappa$. So $\card{V_\kappa} =\beth_\kappa= \kappa$ by \olref{stagesize}.\end{proof}There are as many stages beneath $V_\kappa$ as there are !!{element}sof $V_\kappa$. Intuitively, then, $V_\kappa$ is as wide as it is tall.This is very Tristram-Shandy-esque: we move from one stage to the nextby taking \emph{powersets}, thereby making our hierarchy \emph{much}bigger with each step. But, ``in the end'', i.e., at stage $\kappa$,the hierarchy's width catches up with its height. One might ask: \emph{How often does the hierarchy's width match itsheight?} The answer is: \emph{As often as there are ordinals.} Butthis needs a little explanation. We define a term $\tau$ as follows. For any $A$, let:\begin{align*}	\tau_0(A) & \defis \card{A}\\	\tau_{n+1}(A) & \defis \beth_{\tau_n(A)}\\	\tau(A) & \defis \bigcup_{n < \omega}\tau_n(A)\intertext{As in \olref{bethfixed}, $\tau(A)$ is a$\beth$-fixed point for any $A$, and trivially $\card{A} < \tau(A)$.So now consider this recursive definition:}	W_0 &\defis 0\\	W_{\alpha + 1} & \defis \tau(W_\alpha)\\	W_\alpha & \defis \bigcup_{\beta < \alpha} W_\beta	\text{, when $\alpha$ is a limit}\end{align*}The construction is defined for all ordinals. Intuitively, then,$W$ is ``!!a{injection}'' from the ordinals to $\beth$-fixed points.And, exactly as before, $V_{W_\alpha}$ is as wide as it is tall, for any $\alpha$.\end{document}