\chapter{Cardinality}

The idea of cardinality hasbeen stated previously, albeit in an informal manner. The deeper ideas associated with cardinality were inaccessible to us without first learning more about functions. Sets of infinite elements may not necessarily be of the same 'size'; some infinities are 'larger' than others. This intriguing fact is the first item on our agenda.




Intuitively the idea of cardinality of finite set is how many elements are inside that set, so we'd like to formally develop a system that says the set $\{6502,4,64\}$ has a cardinality of 3, $\{9\}$ has cardinality of 1, etc. 


We aim to define the idea of cardinality rigorously, and we will do that by considering ways to verify that sets are of the same size. Bijections are the primary tool in our theory of cardinality; if two sets have a bijection between them, they have the same 'cardinality'.


The use of bijections is necessary to make the notion of cardinality formal, and moreover, it will become the only way in which we can make sense for cardinality when we study infinite sets.

\section{Ordinal numbers}

\begin{definition}[Transitive set]
\end{definition}
\begin{definition}[Ordinal]
\[\alpha \text{ is an ordinal 1} \iff \alpha \text{ is a transitive set } \land \in \text{ is a well-order on } \alpha\]
\end{definition}

We have the trivial zero ordinal
\[0 \text{ is an ordinal }\]

Given any ordinal, we can generate successor ordinals; here is an example using $0$.
\[0=\emptyset\]
\[1=\{0\}\]
\[2=\{0,1\}\]
\[3=\{0,1,2\}\]
\[n = \mathbb{N}\cap[0,n)\]

Other ordinals are sythetically defined as limit ordinals.


\begin{definition}[First infinite ordinal]
$\omega=\mathbb{N}$
\end{definition}


\[\omega=\mathbb{N}\]
\[\omega+1=\mathbb{N}\cup \{\omega\}\]
\[\omega+2=\mathbb{N}\cup \{\omega, \omega+1\}\]



\begin{definition}[Epsilon numbes]
Epsilon numbers are ordinals satisfying the following relation.
\[\varepsilon = \omega^{\varepsilon}\]
\end{definition}

\begin{definition}[Epsilon naught]
\[ \varepsilon = \omega \uparrow \uparrow \omega\]
\end{definition}


\section{Equinumerous sets}

\begin{definition}[Equinumerous pair of sets]
A pair of sets is equinumerous iff there is a bijection between them.
\end{definition}

\begin{proposition}
Define $A \sim B \iff A \text{ is equinumerous to } B$, then the following hold due to the properties of bijections.
\[A \sim A\]
\[A \sim B \land B \sim C \implies A \sim C\]
\[A \sim B \iff B \sim A\]
\end{proposition}

This is because in the formalized set theory ZFC the set of all finite sets is a paradox, and since we defined equivalence relations work on sets, we therefore technically can't call this an equivalence relation; this is a very technical point that can be ignored.

The fact that equinumerous sets acts as an equivalence relation means that sets can only be apart of exactly 1 'equivalence class', which are exactly what we will be using to define cardinality; a set's 'cardinality class' will be exactly which unique 'equinumerous equivalence class' that set belongs to.

We initiate our study by first defining finite sets and considering how cardinality works on them.

\section{Cardinality}

We would like to use cardinality to make direct compa

The goal is to use ordinal numbers to obtain a notion of cardinality, and we abuse the fact that ordinals are well-ordered. , however in the case of infinite ordinals a set may be equinumerous to multiple ordinals. Fortunately because ordinals are well ordered there is some minimum ordinal equinumerous to the set which we can use as the ordinal to represent this cardinality in a unique way!

\begin{definition}[Cardinality of a set]
$|\cdot|$ is the \emph{cardinality symbol}.
	\[|A| = \min \{\alpha \in \mathrm{Ord} : \alpha \sim A \} \]
\end{definition}




Our definition for cardinality has a slight abuse of notation; $\mathrm{Ord}$ is a paradoxical set in formalized set theories, though due to transfinite induction on ordinals this construction is valid.

\section{Finite sets}



\begin{definition}[Finite set]
%A \emph{finite set} is a set that has a bijection to a set of the form $\mathbb{N}\cap [1,n]$.
A \emph{finite set} is a set with cardinality less than $\omega$.
\end{definition}


Our definition of cardinality aligns well with intuition; we see that the first ordinal to be equinumeral to a set with $n$ elements is indeed $n$ for any finite set.


\[|A \cap B| \leq \min \{ |A|,|B| \} \]
\[|A \cap B| \geq \max \{ |A|,|B| \} \]
\[ |A \setminus B| \leq |A| \]
\[ |A \setminus B| \leq |A| \]
\[ |A^{\complement}| = |U|-|A| \]
\[|A \cup B|  \leq |A| + |B|\]
\[|A|+|B|=|A \sqcup B|\]
\[|A \times B| =|A||B|\]
\[|A \times B| = |B \times A|\]
\[Y \subseteq X \implies |Y| \leq |X|\]
\[\mathcal{P}(X)=2^{|X|}\]


The field of finding the cardinality of special types of finite sets is called enumerative combinatorics.


\section{Infinite sets}


We will now consider infinite sets which cannot be put into bijection with any set of the form $\mathbb{N}\cap[1,n]$.

\begin{definition}[Infinite set]
An \emph{infinite set} is a set that is not finite.
\end{definition}

The infinite brings an immense amount of complexities to the ideas of cardinality, and we must take great care in our definitions.

The most basic infinite set at our disposal is $\mathbb{N}$ (all infinite subsets of $\mathbb{N}$ actually have a bijection to $\mathbb{N}$, so this really is as simple as infinity gets!).

If we consider bijections again as our golden tool for formalizing the theory of cardinality, and with some foresight that not all infinite sets are going to have bijections between eachother, we will consider a special class of infinite sets

\begin{definition}[Countably infinite set]
A \emph{countably infinite set} is a set that has a bijection to $\mathbb{N}$.
\end{definition}

\begin{definition}[Countable set]
A \emph{countable set} is a set that is either a finite or countably infinite set.
\end{definition}


\begin{example}
$\{0,2,4,5,6\}$ is countable.
$\mathbb{N}$ is countable by $f(n)=n$.
$\{n \in \mathbb{N} : n \text{ is even} \}$ is countable by $f(n)=\frac{n}{2}$.
$\mathbb{N}^2$ is countable by $f(n,m)=\frac{(n+m)(n+m+1)}{2}+m$
$\mathbb{Z}$ is countable by $f(n) = \begin{cases} 2n & n >0 \\ -2n+1 & n\leq 0 \end{cases}$.
\end{example}



So far we have used the natural numbers to symbolize each cadinality for finite sets, though we will require new symbols to represent the cardinalities for the infinite sets that we encounter (countably infinite sets to start with). The symbols of $\mathbb{N}$ combined with the symbols we introduce to represent infinite cardinalities will make up the \emph{cardinal numbers}.

We will need to resort back to ordinal numbers to develop this theory however.



\subsection{Aleph numbers}

because ordinals are well-ordered by $\in$, cardinals are well-ordered by $\in$; we will use this fact to form a synthetic notation for general cardinals.


We know that we can use symbols of $\mathbb{N}$ for finite cardinals, and $\omega$ for the countably infinmite cardinal, but what about the next smallest cardinal in the well-ordered chain of cardinals?

A notational trick is to use ordinal numbers to index the infinite cardinals; denote the first infinite cardinal $\omega=\aleph_0$ so that the next infinite cardinal is $\aleph_1$, then the next cardinal is $\aleph_2$ etc.

This is the idea inderpinning the \emph{aleph numbers}; denoting infinite cardinals by their order in the well-ordering of infinite cardinals by $\in$.

\begin{definition}[Aleph numbers]
The \emph{aleph numbers} are a transfinite sequence of ordered cardinal numbers $(\aleph_n)_{n\in \mathrm{Ord}}$ representing the $n$th smallest infinite cardinal.
\[\forall n \in \mathbb{N} ( n < \aleph_0 )\]
\[n < m \implies \aleph_n < \aleph_m \]
\end{definition}



We want to contain the natural numbers in this set of cardinal numbers to handle the finite sets, however we want to augment a cardinal to represent the infinite, but countable sets. These type of sets are the most basic and smallest type of infinite set, and so this cardinal number should be greater than all natural numbers, but less than any future infinite cardinal numebrs we append.

For now, let's denote the cardinality of countably infinite sets with the cardinal number $\aleph_0$.

\begin{proposition}
Countably infinite sets are the sets of cardinality $\aleph_0$.
\[ A \text{ is countably infinite} \iff |A| = \aleph_0 \]
\end{proposition}


We can inductively define the rest of the cardinal numbers by introducing new cardinal number as the next smallest cardinal. 

The details are complicated, however we are assured that this is permissible due to the \emph{well-ordering theorem}, which states that for any set we can create some order upon it that makes it well-ordered (every subset contains a smallest element). Hence if one considers the set of all cardinal largers number than $\aleph_0$, our theorem states this contains a smallest cardinal number, which we may denote as $\aleph_1$.

This can be generalized
\begin{definition}[Aleph numbers]
The \emph{aleph numbers} are a sequence of ordered cardinal numbers $(\aleph)_{n\in \mathbb{N}}$ representing the $n$th smallest infinite cardinal.
\[\forall n \in \mathbb{N} ( \aleph_0 > n)\]
\[n > m \implies \aleph_n > \aleph_m \]
\end{definition}

Recall that for finite sets,  a set with cardinality $n$ has its powerset with  cardinality $2^n$; mathematicians allow a similar notation to describe the cardinalities of infinite powersets. This allows the representation $|\mathcal{P}(\mathbb{N})| =2^{\aleph_0}$.




\subsection{Beth numbers}


In theory, aleph numbers form a representation for every cardinal number, however in practice we don't really have any tools for discerning the aleph number of nontrivial infinite sets unless they have cardinality $\aleph_0$

The only set that we know to be of cardinality $\aleph_1$ is $\aleph_1$ itself; a trivial example. 

We have discussed $\mathbb{N},\mathbb{Q}$ but have avoided discussing $\mathbb{R}$; let's get to that now.


\begin{definition}[Cardinality of the continuum]
The \emph{cardinality of the continuum} is the cardinality of the real numbers.
\[\mathfrak{c}=|\mathbf{R}|\]
\end{definition}[Cardinality of the continuum]

\begin{proposition}
\[\mathfrak{c}= |\mathcal{P}(\mathbf{N})| \]
\end{proposition}


\begin{theorem}[Cantor's theorem]
\[|\mathcal{P}(X)| > |X|\]
\end{theorem}

Cantor's theorem is obvious for finite cardinalities since $2^n > n$ for any natural number $n$. The real kicker is the fact that it holds for the infinite cardinalities too; meaning you can create arbitrarily larger infinities as desired.


\subsection{Cantor's paradox}
I'll take a quick detour to introduce \emph{Cantor's paradox}; a paradox we can arrive at if we do not conduct set theory carefully.
\subsection{Burali-Forti paradox}


\subsection{Continuum hypothesis}


One interesting question is whether taking the powerset of the countable set yields a set with the very next cardinal $\aleph_1$.

- Mention continuum hypothesis

In words, this means that there is no infinite cardinal between the cardinalities $\aleph_0$ and $\mathfrak{c}$, so $\mathfrak{c}$ is the very next cardinal and hence $\mathfrak{c}=\aleph_1$. The truth of this hypothesis is kind of complicated, we will return to this when we study axiomatic set theory.

There is also a generalization of this hypothesis that extends to all the aleph numbers.

- Mention generalized continuum hypothesis
\[ \aleph_{\alpha +1} = 2^{\aleph_{\alpha}} \]

This generalization means that taking powersers of any infinite set always yields the very next cardinal number; Cantor's theorem instantly implies that $ \aleph_{\alpha +1} \leq 2^{\aleph_{\alpha}} $, but there is no apparent reason to believe that $ \aleph_{\alpha +1} \geq 2^{\aleph_{\alpha}} $.
\subsection{Beth numbers}

We now introduce the \emph{beth numbers} to offer a clean notation to describe constructing cardinal numbers by repeatedly taking powersets. We will later tie these in with the generalized continuum hypothesis.



\begin{definition}[Beth numbers]
The \emph{beth numbers} are a sequence of ordered cardinal numbers $(\beth)_{n\in \mathbb{N}}$ representing the cardinality of the powerset of a set with cardinality of the previous beth number. 
\[\beth_0 = \aleph_0\]
\[\beth_{n+1} = \mathcal{P}(\beth_{n})\]
\end{definition}

\begin{proposition}
\[\mathfrak{c}= \beth_1 \]
\end{proposition}


\begin{conjecture}[Continuum hypothesis]
\[ \aleph_1 = \beth_1 \]
\end{conjecture}

There also exists a generalized continuum hypothesis.
\begin{conjecture}[Generalized continuum hypothesis]
\[ \aleph_{\alpha} = \beth_{\alpha} \]
\end{conjecture}



\subsection{Arithmetic on cardinal numbers}


\[|A|=a \land |B|=b \land A\cap B = \emptyset\]
\[a+b=|A \cup B|\]

\[|A|=a \land |B|=b \land A\cap B = \emptyset\]
\[ab=|A \times B|\]


Addition of cardinal numbers is a commutative monoid.
\[a+b=b+a\]
\[a+(b+c)=(a+b)+c\]
\[a+0=a\]


Multiplication of cardinal numbers is a commutative monoid.
\[a+b=b+a\]
\[a+(b+c)=(a+b)+c\]
\[a+0=a\]

\section{Cardinality and functions}

We've used bijective functions to define cardinality, now cardinality will be used to study functions.

\begin{theorem}
If a function is surjective then its image has the same cardinality as its codomain.
\[ f \text{ is surjective } \implies |\mathrm{Im}(f)|=|\mathrm{Codom}(f)| \]
\end{theorem}

\begin{theorem}
If a function is surjective then its domain the same cardinality as its range.
\[ f \text{ is bijective } \implies |\mathrm{Im}(f)|=|\mathrm{Dom}(f)| \]
\end{theorem}