Set Theory

Cardinals

content/set-theory/cardinals/cardinals.tex

% Part: set-theory% Chapter: cardinals\documentclass[../../../include/open-logic-chapter]{subfiles}\begin{document}\olchapter{sth}{cardinals}{Cardinals}\olimport{cp}\olimport{cardsasords}\olimport{milestone}\olimport{classing}\olimport{hp}\OLEndChapterHook\end{document}

content/set-theory/cardinals/cp.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{cardinals}{cp}\olsection{Cantor's Principle}Cast your mind back to \olref[ordinals][vn]{sec}. We were discussingwell-ordered sets, and suggested that it would be nice to have objectswhich go proxy for well-orders. With this is mind, we introducedordinals, and then showed in\olref[ordinals][ordtype]{ordtypesworklikeyouwant} that thesebehave as we would want them to, i.e.:\[	\ordtype{A, <} = \ordtype{B, \lessdot} 	\text{ iff } \tuple{A, <} \isomorphic \tuple{B, \lessdot}.\]Cast your mind back even further, to \olref[sfr][siz][equ]{sec}.There, working na\"ively, we introduced the notion of the ``size'' ofa set. Specifically, we said that two sets are equinumerous,$\cardeq{A}{B}$, just in case there is !!a{bijection} $f \colon A \toB$. This is an intrinsically {simpler} notion than that of awell-ordering: we are only interested in !!{bijection}s, and not (aswith order-isomorphisms) whether the !!{bijection}s ``preserve anystructure''.This all gives rise to an obvious thought. Just as we introducedcertain objects, \emph{ordinals}, to calibrate well-orders, we canintroduce certain objects, \emph{cardinals}, to calibrate size. Thatis the aim of this chapter. Before we say what these cardinals will be, we should lay down aprinciple which they ought to satisfy. Writing $\card{X}$ for thecardinality of the set $X$, we would want them to obey:\[	\card{A} = \card{B} \text{ iff } \cardeq{A}{B}.\]We'll call this \emph{Cantor's} Principle, since Cantor was probablythe first to have it very clearly in mind. (We'll say more about itsrelationship to \emph{Hume's} Principle in \olref[hp]{sec}.) Soour aim is to define $\card{X}$, for each $X$, in such a way that itdelivers Cantor's Principle.\end{document}

content/set-theory/cardinals/cardsasords.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{cardinals}{cardsasords}\olsection{Cardinals as Ordinals}In fact, our theory of cardinals will just make (shameless) use of ourtheory of ordinals. That is: we will just define cardinals as certainspecific ordinals. In particular, we will offer the following:\begin{defn}\ollabel{defcardinalasordinal}If $A$ can be well-ordered, then $\card{A}$ is the least ordinal$\gamma$ such that $\cardeq{A}{\gamma}$. For any ordinal $\gamma$, wesay that $\gamma$ is a \emph{cardinal} iff $\gamma = \card{\gamma}$.\end{defn}We just used the phrase ``$A$ can be well-ordered''. As is almostalways the case in mathematics, the modal locution here is just ahand-waving gloss on an existential claim: to say ``$A$ can bewell-ordered'' is just to say ``there is a relation whichwell-orders~$A$''. But there is a snag with \olref{defcardinalasordinal}. We would likeit to be the case that \emph{every} set has a size, i.e., that$\card{A}$ exists for every~$A$. The definition we just gave, though,begins with a conditional: ``\emph{If} $A$ can bewell-ordered\ldots''. If there is some set $A$ which cannot bewell-ordered, then our definition will simply fail to define an object~$\card{A}$.So, to use \olref{defcardinalasordinal}, we need a guarantee thatevery set can be well-ordered. Sadly, though, this guarantee isunavailable in~$\ZF$. So, if we want to use\olref{defcardinalasordinal}, there is no alternative but to add a newaxiom, such as:\begin{axiom}[Well-Ordering]Every set can be well-ordered.\end{axiom}We will discuss whether the Well-Ordering Axiom is acceptable in\olref[choice][]{chap}. From now on, though, we will simply helpourselves to it. And, using it, it is quite straightforward to provethat cardinals (as defined in \olref{defcardinalasordinal}) exist andbehave nicely:\begin{lem}\ollabel{lem:CardinalsExist}For every set $A$:\begin{enumerate}	\item\ollabel{cardaexists} $\card{A}$ exists and is unique;	\item\ollabel{cardaapprox}  $\cardeq{\card{A}}{A}$;	\item\ollabel{cardaidem}  $\card{A}$ is a cardinal, i.e.,	$\card{A} = \card{\card{A}}$;\end{enumerate}\end{lem}\begin{proof}Fix $A$. By Well-Ordering, there is a well-ordering $\tuple{A, R}$. By\olref[ordinals][ordtype]{thmOrdinalRepresentation}, $\tuple{A,R}$ is isomorphic to a unique ordinal, $\beta$. So$\cardeq{A}{\beta}$. By Transfinite Induction, there is a uniquelyleast ordinal, $\gamma$, such that $\cardeq{A}{\gamma}$. So $\card{A}= \gamma$, establishing \olref{cardaexists} and \olref{cardaapprox}.To establish \olref{cardaidem}, note that if $\delta \in \gamma$ then$\cardless{\delta}{A}$, by our choice of $\gamma$, so that also$\cardless{\delta}{\gamma}$ since equinumerosity is an equivalencerelation (\olref[sfr][siz][equ]{equinumerosityisequi}). So $\gamma =\card{\gamma}$. %So, for reductio, suppose that there is some ordinal $\delta \in \gamma$ such that $\cardeq{\gamma}{\delta}$. Then, $\cardeq{\cardeq{A}{\gamma}}{\delta}$ so that $\cardeq{A}{\delta}$ by \olref[sfr][set][equ]{equinumerosityisequi}, which contradicts the choice of $\gamma$ as the least ordinal such that $\cardeq{A}{\gamma}$. \end{proof}The next result guarantees Cantor's Principle, and more besides.(Note that cardinals inherit their ordering from the ordinals, i.e.,$\cardfont{a} < \cardfont{b}$ iff $\cardfont{a} \in \cardfont{b}$. Informulating this, we will use Fraktur letters for objects we know to becardinals. This is fairly standard. A common alternative is to useGreek letters, since cardinals are ordinals, but to choose them fromthe middle of the alphabet, e.g.: $\kappa, \lambda$.):\begin{lem}\ollabel{lem:CardinalsBehaveRight}For any sets $A$ and $B$:\begin{align*}	\cardeq{A}{B} &\text{ iff } \card{A} = \card{B}\\	\cardle{A}{B} &\text{ iff } \card{A} \leq \card{B}\\	\cardless{A}{B}&\text{ iff } \card{A} < \card{B}\end{align*}\end{lem}\begin{proof}We will prove the left-to-right direction of the second claim (theother cases are similar, and left as an exercise). So, consider thefollowing diagram:\begin{center}	\begin{tikzpicture}	\node (nodea) {$A$};	\node[right = 6em of nodea] (nodeb) {$B$};	\node[below = 2em of nodea] (nodecarda) {$\card{A}$};	\node[below = 2em of nodeb] (nodecardb) {$\card{B}$};	\draw[->] (nodea)--(nodeb);	\draw[<->] (nodea)--(nodecarda);	\draw[<->] (nodeb)--(nodecardb);	\draw[->, dashed] (nodecarda)--(nodecardb);\end{tikzpicture}\end{center}The double-headed arrows indicate !!{bijection}s, whose existence isguaranteed by \olref{lem:CardinalsExist}. In assuming that$\cardle{A}{B}$, there is !!a{injection}  $A\to B$. Now,chasing the arrows around from $\card{A}$ to $A$ to $B$ to $\card{B}$,we obtain !!a{injection} $\card{A} \to \card{B}$ (the dashed arrow).\end{proof}\noindent We can also use \olref{lem:CardinalsBehaveRight}to re-prove Schr\"{o}der--Bernstein. This is the claim that if$\cardle{A}{B}$ and $\cardle{B}{A}$ then $\cardeq{A}{B}$. We statedthis as \olref[sfr][siz][sb]{thm:schroder-bernstein}, but first provedit---with some effort---in \olref[sfr][infinite][card-sb]{sec}.Now consider:\begin{proof}[Re-proof of Schr\"oder-Bernstein]If $\cardle{A}{B}$ and $\cardle{B}{A}$, then $\card{A} \leq \card{B}$and $\card{B} \leq \card{A}$ by \olref{lem:CardinalsBehaveRight}. So$\card{A} = \card{B}$ and $\cardeq{A}{B}$ by Trichotomy and\olref{lem:CardinalsBehaveRight}.\end{proof}\noindentWhilst this is a very simple proof, it implicitly relies on bothReplacement (to secure\olref[ordinals][ordtype]{thmOrdinalRepresentation}) and onWell-Ordering (to guarantee \olref{lem:CardinalsBehaveRight}). Bycontrast, the proof of \olref[sfr][infinite][card-sb]{sec} was muchmore self-standing (indeed, it can be carried out in~$\Zminus$).\end{document}

content/set-theory/cardinals/milestone.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{cardinals}{zfc}	\olsection{$\ZFC$: A Milestone}With the addition of Well-Ordering, we have reached the finaltheoretical milestone. We now have all the axioms required for~$\ZFC$.In detail:\begin{defn}The theory $\ZFC$ has these axioms: Extensionality, Union, Pairs,Powersets, Infinity, Foundation, Well-Ordering and all instances ofthe Separation and Replacement schemes. Otherwise put, $\ZFC$ addsWell-Ordering to~$\ZF$. \end{defn}$\ZFC$ stands for \emph{Zermelo--Fraenkel} set theory with\emph{Choice}. Now this might seem slightly odd, since the axiom weadded was called ``Well-Ordering'', not ``Choice''. But, when we laterformulate {Choice}, it will turn out that Well-Ordering is equivalent(modulo~$\ZF$) to Choice (see \olref[choice][woproblem]{thmwochoice}).So which to take as our ``basic'' axiom is a matter of indifference.And the name ``$\ZFC$'' is entirely standard in the literature. \end{document}

content/set-theory/cardinals/classing.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{cardinals}{classing}\olsection{Finite, \usetoken{S}{enumerable}, \usetoken{S}{nonenumerable}}Now that we have been introduced to cardinals, it is worth spending alittle time talking about different varieties of cardinals;specifically, finite, !!{enumerable}, and !!{nonenumerable} cardinals.Our first two results entail that the finite cardinals will be exactlythe finite ordinals, which we defined as our \emph{natural numbers}back in \olref[z][infinity-again]{defnomega}: \begin{prop}\ollabel{finitecardisoequal}Let $n, m \in \omega$. Then $n = m$ iff $\cardeq{n}{m}$.\end{prop}\begin{proof}\emph{Left-to-right} is trivial. To prove \emph{right-to-left},suppose $\cardeq{n}{m}$ although $n \neq m$. By Trichotomy, either $n\in m$ or $m \in n$; suppose $n \in m$ without loss of generality.Then $n \subsetneq m$ and there is !!a{bijection} $f \colon m \to n$,so that $m$ is Dedekind infinite, contradicting\olref[z][infinity-again]{naturalnumbersarentinfinite}.\end{proof}\begin{cor}\ollabel{naturalsarecardinals}If $n \in \omega$, then $n$ is a cardinal. \end{cor}\begin{proof}Immediate.\end{proof}\noindentIt also follows that several reasonable notions of what it might meanto describe a cardinal as ``finite'' or ``infinite'' coincide:\begin{thm}\ollabel{generalinfinitycharacter}For any set $A$, the following are equivalent:\begin{enumerate}	\item\ollabel{card:notinomega} $\card{A} \notin \omega$, i.e.,	$A$ is not a natural number;	\item\ollabel{card:omegaplus} $\omega \leq \card{A}$;	\item\ollabel{card:infinite} $A$ is Dedekind infinite.\end{enumerate}\end{thm}\begin{proof}From \olref[ord-arithmetic][using-addition]{ordinfinitycharacter},\olref[cardinals][cardsasords]{lem:CardinalsBehaveRight}, and\olref{naturalsarecardinals}. \end{proof}This licenses the following \emph{definition} of some notions which weused rather informally in \olref[sfr][][]{part}:\begin{defn}\ollabel{defnfinite}We say that $A$ is \emph{finite} iff $\card{A}$ is a natural number,i.e., $\card{A} \in \omega$. Otherwise, we say that $A$ is\emph{infinite}.\end{defn}\noindent But note that this definition is presented against the background of$\ZFC$. After all, we needed Well-Ordering to guarantee that every sethas a cardinality. And indeed, without Well-Ordering, there can be aset which is neither finite nor Dedekind infinite. We will return tothis sort of issue in \olref[choice][]{chap}. For now, we continue torely upon Well-Ordering.Let us now turn from the finite cardinals to the infinite cardinals.Here are two elementary points:\begin{cor}\ollabel{omegaisacardinal}$\omega$ is the least infinite cardinal. \end{cor}\begin{proof}$\omega$ is a cardinal, since $\omega$ is Dedekind infinite and if$\cardeq{\omega}{n}$ for any $n \in \omega$ then $n$ would be Dedekindinfinite, contradicting\olref[z][infinity-again]{naturalnumbersarentinfinite}. Now$\omega$ is the least infinite cardinal by definition. \end{proof}\begin{cor}Every infinite cardinal is a limit ordinal.\end{cor}\begin{proof}Let $\alpha$ be an infinite successor ordinal, so $\alpha = \beta\ordplus 1$ for some $\beta$. By \olref{finitecardisoequal}, $\beta$is also infinite, so $\cardeq{\beta}{\beta \ordplus 1}$ by\olref[ord-arithmetic][using-addition]{ordinfinitycharacter}. Now$\card{\beta} = \card{\beta\ordplus 1} = \card{\alpha}$ by\olref[cardinals][cardsasords]{lem:CardinalsBehaveRight}, sothat $\alpha \neq \card{\alpha}$.\end{proof}Now, as early as \olref[sfr][siz][enm-alt]{defn:enumerable}, we flagged wecan distinguish between !!{enumerable} and !!{nonenumerable} infinitesets. That definition naturally leads to the following:\begin{prop}$A$ is !!{enumerable} iff $\card{A} \leq \omega$, and $A$ is!!{nonenumerable} iff $\omega < \card{A}$.\end{prop}\begin{proof}By Trichotomy, the two claims are equivalent, so it suffices to provethat $A$ is !!{enumerable} iff $\card{A} \leq \omega$. For\emph{right-to-left}: if $\card{A} \leq \omega$, then$\cardle{A}{\omega}$ by\olref[cardinals][cardsasords]{lem:CardinalsBehaveRight} and\olref{omegaisacardinal}. For \emph{left-to-right}: suppose $A$ is!!{enumerable}; then by \olref[sfr][siz][enm-alt]{defn:enumerable} thereare three possible cases:\begin{enumerate}	\item if $A = \emptyset$, then $\card{A} = 0 \in \omega$, by	\olref{naturalsarecardinals} and	\olref[cardinals][cardsasords]{lem:CardinalsBehaveRight}.	\item if $\cardeq{n}{A}$, then $\card{A} = n \in \omega$, by	\olref{naturalsarecardinals} and	\olref[cardinals][cardsasords]{lem:CardinalsBehaveRight}.	\item if $\cardeq{\omega}{A}$, then $\card{A} = \omega$, by \olref{omegaisacardinal}.\end{enumerate}So in all cases, $\card{A} \leq \omega$. \end{proof}\noindentIndeed, $\omega$ has a special place. Whilst there are many countable ordinals:\begin{cor}$\omega$ is the only !!{enumerable} infinite cardinal.\end{cor}\begin{proof}Let $\cardfont{a}$ be !!a{enumerable} infinite cardinal. Since$\cardfont{a}$ is infinite, $\omega \leq \cardfont{a}$. Since$\cardfont{a}$ is !!a{enumerable} cardinal, $\cardfont{a} =\card{\cardfont{a}} \leq \omega$. So $\cardfont{a} = \omega$ byTrichotomy. \end{proof}Of course, there are infinitely many cardinals. So we might ask:\emph{How many cardinals are there?} The following results show thatwe might want to reconsider that question.\begin{prop}\ollabel{unioncardinalscardinal}If every member of $X$ is a cardinal, then $\bigcup X$ is a cardinal.\end{prop}\begin{proof}It is easy to check that $\bigcup X$ is an ordinal. Let $\alpha \in\bigcup X$ be an ordinal; then $\alpha \in \cardfont{b} \in X$ forsome cardinal $\cardfont{b}$. Since $\cardfont{b}$ is a cardinal,$\cardless{\alpha}{\cardfont{b}}$. Since $\cardfont{b} \subseteq\bigcup X$, we have $\cardle{\cardfont{b}}{\bigcup X}$, and so$\cardneq{\alpha}{\bigcup X}$. Generalising, $\bigcup X$ is acardinal.\end{proof} \begin{thm}\ollabel{lem:NoLargestCardinal}There is no largest cardinal.\end{thm}\begin{proof}For any cardinal $\cardfont{a}$, Cantor's Theorem(\olref[sfr][siz][car]{thm:cantor}) and\olref[cardinals][cardsasords]{lem:CardinalsExist} entail that$\cardfont{a} < \card{\Pow{\cardfont{a}}}$.\end{proof}\begin{thm}The set of all cardinals does not exist.\end{thm}\begin{proof}For reductio, suppose $C = \Setabs{\cardfont{a}}{\cardfont{a} \text{is a cardinal}}$. Now $\bigcup C$ is a cardinal by\olref{unioncardinalscardinal}, so by \olref{lem:NoLargestCardinal}there is a cardinal $\cardfont{b} > \bigcup C$. By definition$\cardfont{b} \in C$, so $\cardfont{b} \subseteq \bigcup{C}$, so that$\cardfont{b} \leq \bigcup C$, a contradiction.\end{proof}You should compare this with both Russell's Paradox and Burali-Forti. \end{document}

content/set-theory/cardinals/hp.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{cardinals}{hp}\olsection{Appendix: Hume's Principle}In \olref[cp]{sec}, we described Cantor's Principle. This was:\begin{align*}	\card{A} = \card{B} & \text{ iff } A \approx B.\intertext{This is very similar to what is now called\emph{Hume's Principle}, which says:}	\fregenum{x} {F(x)} = \fregenum{x}{G(x)} & \text{ iff } F \sim G\end{align*}where `$F \sim G$' abbreviates that there are exactly as many $F$s as$G$s, i.e., the $F$s can be put into a bijection with the $G$s, i.e.:\begin{align*}	\exists R(&\forall v\forall y(Rvy \lif (Fv \land Gy)) \land {}\\		&\forall v(Fv \lif \lexists![y][Rvy]) \land {}\\		&\forall y(Gy \lif \lexists![v][Rvy]))\end{align*}But there is a type-difference between Hume's Principle and Cantor'sPrinciple. In the statement of Cantor's Principle, the variables``$A$'' and ``$B$'' are first-order terms which stand for \emph{sets}.In the statement of Hume's Principle, ``$F$'', ``$G$'' and ``$R$'' are\emph{not} first-order terms; rather, they are in \emph{predicateposition}. (Maybe they stand for \emph{properties}.) So we might glossHume's Principle in English as: the number of $F$s is the number of$G$s iff the $F$s are bijective with the~$G$s. This is called\emph{Hume's Principle}, because Hume once wrote this:\begin{quote}  When two numbers are so combined as that the one has always an unit  answering to every unit of the other, we pronounce them equal.  \citep[Pt.III Bk.1 \S1]{Hume1740}\end{quote}And Hume's Principle was brought to contemporary mathematico-logicalprominence by \citet[\S63]{Frege1884}, who quoted this passage fromHume, before (in effect) sketching (what we have called) Hume'sPrinciple. You should note the structural similarity between Hume's Principle andBasic Law~V. We formulated this in \olref[story][blv]{sec} asfollows:\[	\fregeext{x}{F(x)} = \fregeext{x}{G(x)} \text{iff } \lforall[x][(F(x) \liff G(x))].\]And, at this point, some commentary and comparison might help. There are two ways to take a principle like Hume's Principle or BasicLaw~V: \emph{predicatively} or \emph{impredicatively} (recall\olref[story][predicative]{sec}). On the impredicative reading ofBasic Law~V, for each~$F$, the object $\fregeext{x}{F(x)}$ fallswithin the domain of quantification that we used in formulating BasicLaw~V itself. Similarly, on the impredicative reading of Hume'sPrinciple, for each~$F$, the object $\fregenum{x}{F(x)}$ falls withinthe domain of quantification that we used in formulating Hume'sPrinciple. By contrast, on the \emph{predicative} understanding, theobjects $\fregeext{x}{F(x)}$ and~$\fregenum{x}{F(x)}$ would beentities from some \emph{different} domain. Now, if we read Basic Law~V impredicatively, it leads toinconsistency, via Na\"ive Comprehension (for the details, see\olref[story][blv]{sec}). Much like Na\"ive Comprehension, it can berendered consistent by reading it \emph{predicatively}. But itprobably will not do everything that we wanted it to. Hume's Principle, however, \emph{can} consistently be readimpredicatively. And, read thus, it is quite powerful.To illustrate: consider the predicate ``$x \neq x$'', which obviouslynothing satisfies. Hume's Principle now yields an object $\# x( x\neqx)$. We might treat this as the number~$0$. Now, on the\emph{impredicative} understanding---but \emph{only} on theimpredicative understanding---this entity $0$ falls within ouroriginal domain of quantification. So we can sensibly apply Hume'sPrinciple with the predicate ``$x = 0$'' to obtain an object $\#x (x =0)$. We might treat this as the number~$1$. Moreover, Hume's Principleentails that $0 \neq 1$, since there cannot be a bijection from thenon-self-identical objects to the objects identical with $0$ (thereare none of the former, but one of the latter). Now, workingimpredicatively again, $1$~falls within our original domain ofquantification. So we can sensibly apply Hume's Principle with thepredicate ``$(x = 0 \lor x = 1)$'' to obtain an object $\#x(x = 0 \lorx = 1)$. We might treat this as the number~$2$, and we can show that$0\neq 2$ and $1 \neq 2$ and so on. In short, taken impredicatively, Hume's Principle entails that thereare \emph{infinitely many objects}. And this has encouraged\emph{neo-Fregean logicists} to take Hume's Principle as thefoundation for arithmetic. Frege \emph{himself}, though, did not take Hume's Principle as hisfoundation for arithmetic. Instead, Frege proved Hume's Principle froman explicit definition: $\fregenum{x}{F(x)}$ is defined as the extension ofthe concept $F \sim \Phi$. In modern terms, we might attempt to renderthis as $\fregenum{x}{F(x)} = \Setabs{G}{F \sim G}$; but this will pull usback into the problems of Na\"ive Comprehension.\end{document}