Kardinalna aritmetika Lecture notes
Lecture 8: Cardinal arithmetic with choice
For this lecture, we will assume the axiom of choice. We will still flag its usage. The axiom makes some things more straightforward and flattens a lot of concepts.
- Every infinite cardinality is an aleph. If \(X\) is infinite, then \(\abs{X} = \aleph_{\alpha}\) for a unique ordinal \(\alpha\).
- Every infinite cardinality is its own square. This already implies choice!
- Cardinalities are linearly ordered. Since infinte cardinalities are alephs, they inherit the order from the ordinals. This is also equivalent to choice.
- Under the axiom of choice, the relations \(<\) become equivalent to \(\ll\).
- For all infinite sets \(X, Y\), we have \[ \abs{X} + \abs{Y} = \max(\abs{X}, \abs{Y}) = \abs{X} \times \abs{Y}. \]
Suppose \(X_{(-)} : I \rightarrow \Class{\text{Set}}\) to be a family of sets. We defined \[ \sum\limits_{i\in I} X_i := \left\{ (i, x) \mid i \in I, x \in X_i \right\} \] and \[ \prod\limits_{i \in I} X_i := \left\{ f : I \rightarrow \bigcup\limits_{i \in I} X_i \mid \forall i \in I .\, f(i) \in X_i \right\} \] as the family of choice functions. We sometimes write a choice function as \((X_i)_{i \in I}\) and call it a family of elements.
These operations are functorial. If \((f_i : X_i \rightarrow Y_i)_{i\in I}\) then we can derive the functions
\begin{align*} \sum\limits_{i\in I} X_i &\rightarrow \sum\limits_{i \in I} Y_i & \sum\limits_{i\in I} X_i &\rightarrow \prod\limits_{i \in I} Y_i \\ \sum\limits_{i\in I} f_i := (i, x) &\mapsto (i, f_i(x)) & \prod\limits_{i\in I} f_i := g &\mapsto (i \mapsto f_i(g(i))) \end{align*}which obviously preserve identity and composition, i.e. are factorial.
Suppose \((X_i)_{i \in I}\) and \((Y_i)_{i\in I}\) enjoy the property that \[ \forall i \in I.\, \abs{X_i} \leq \abs{Y_i}, \] then \[ \abs{\sum\limits_{i\in I} X_i} \leq \abs{\sum\limits_{i\in I} Y_i} \text{ and } \abs{\prod\limits_{i\in I} X_i} \leq \abs{\prod\limits_{i\in I} Y_i} \]
By assumption, for every \(i \in I\), there is an injection \(f_i : X_i \rightarrow Y_i\). Applying functorial actions to \((f_i : X_i \rightarrow Y_i)\), we get functions \(\sum\limits_{_{i\in I}} f_i : \sum\limits_{i\in I} X_i \rightarrow \sum\limits_{i\in I} Y_i\) and \(\prod\limits_{_{i\in I}} f_i : \prod\limits_{i\in I} X_i \rightarrow \prod\limits_{i\in I} Y_i\). It is easily checked that both functions are injective.
\noindent Note the proof uses the axiom of choice when we take a specific family \(f_i : X_i \rightarrow Y_i\).
Suppose \((X_i)_{i \in I}\) and \((Y_i)_{i\in I}\) enjoy the property that \[ \forall i \in I.\, \abs{X_i} = \abs{Y_i}, \] then \[ \abs{\sum\limits_{i\in I} X_i} = \abs{\sum\limits_{i\in I} Y_i} \text{ and } \abs{\prod\limits_{i\in I} X_i} = \abs{\prod\limits_{i\in I} Y_i} \]
CSB.
It also makes sense to talk about operations on families of cardinals. If \((\kappa_i)_{i \in I}\) is a family of cardinals, i.e. initial ordinals, then we say
\begin{align*} \sum\limits_{i \in I} \kappa_i &:= \abs{\sum\limits_{i \in I} [\kappa_i]} \\ \prod\limits_{i \in I} \kappa_i &:= \abs{\prod\limits_{i \in I} [\kappa_i]} \end{align*}Note that \([\kappa_i]\) is the set of ordinals less than \(\kappa_i\).
Suppose \(\lambda\) and \(\kappa\) are cardinalities. We can consider the sum \[ \sum\limits_{\alpha < \lambda} \kappa = \lambda \cdot \kappa. \] i.e. self-sum \(\kappa\) \(\lambda\)-many times. It's true in general that \[ \sum\limits_{i \in I}^{} X = I \times X \] (because we have no dependency in the second component). Let us consider the general case.
FINISH Give name
Suppose \(\lambda\) is an infinite cardinal and \((\kappa_{\alpha})_{\alpha < \lambda}\) are nonzero cardinals. Then \[ \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} = \lambda \cdot \left( \sup_{\alpha < \lambda} \kappa_{\alpha} \right). \]
We need to prove \[ \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} = \lambda \cdot \kappa. \] We prove this by showing the two inequalities. Since \(\kappa_{\alpha} \leq \kappa\) we have \[ \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} \leq \sum\limits_{\alpha < \lambda}^{} \kappa = \lambda \cdot \kappa. \] by proposition.
We have \(\kappa_{\alpha} \leq \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha}\) so \(\kappa \leq \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha}\) because \(\kappa\) is a supremum. Also we have \(\lambda = \sum\limits_{\alpha < \lambda}^{} 1 \leq \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha}\) so we get \[ \lambda \cdot \kappa \leq \left( \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} \right) \cdot \left( \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} \right) = \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} \] because \(\sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} \) is its own square.
If \(\lambda \leq \sup_{\alpha < \lambda} \kappa_{\alpha}\) then \[ \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} = \sup_{\alpha < \lambda} \kappa_{\alpha}. \]
If \((\kappa_i)_{i \in I}\) and \((\lambda_i)_{i \in I}\) are families of cardinals with \(\kappa_i \ll \lambda_i\) for every \(i \in I\). Then \[ \sum\limits_{i \in I}^{} \kappa_i \ll \prod\limits_{i \in I}^{} \lambda_i. \]
\noindent
We can use this to rederive Cantor's theorem.
For any cardinality \(\kappa\), we have \(\kappa < 2^{\kappa}\).
\[ \kappa = \sum\limits_{\alpha < \kappa}^{} 1 < \prod\limits_{\alpha < \kappa}^{} 2 = 2^{\kappa} \] where we use König's theorem for the strict inequality.
We prove the strict inequality by showing the nonstrict inequality and showing it is not equality.
We define an injective function
\begin{align*} \sum\limits_{i \in I}^{} [\kappa_i] &\rightarrow \prod\limits_{i \in I}^{} [\lambda_i] \\ (i, \alpha) &\mapsto \left(j \mapsto \begin{cases} \alpha & \text{ if } j = i \\ \kappa_j & \text{ if } j \neq i \end{cases} \right) \end{align*}It's easily checked that this is injective.
We prove there is no bijection \(\sum\limits_{i \in I}^{} [\kappa_i] \cong \prod\limits_{i \in I}^{} [\lambda_i]\). Suppose for contradiction there is. Note that we can view the sum set as an \(I\)-indexed partition of the whole sum set. If we transport this via the bijection, we end up transporting the partition in the product. This would give us an isomorphism to a disjoint union \[ \prod\limits_{i \in I}^{} [\lambda_i] = \bigcup\limits_{i \in I}^{} X_i \] where \(X_i\) is the image of \(\left\{ i \right\} \times [\kappa_i]\) under the bijection.
For every \(i \in I\) the set \[ Y_i = \left\{ x_i \mid x_{(-)} \in X_i \right\} \subseteq [\lambda_i] \] Since \(x_{(-)} \mapsto x_i\) is a surjection from \(X_i \rightarrow Y_i\), we have \(\abs{Y_i} \leq \abs{X_i} = \kappa_i < \lambda_i\). Therefore \([\lambda_i] \setminus Y_i\) is nonempty, hence has a least element. Consider now the function \[ i \in I \setminus \text{the smallest ordinal in } [\lambda_i] \setminus Y_i. \] This is clearly in \(\prod\limits_{i \in I}^{} [\lambda_i]\). On the other hand it is not in any \(X_i\). This is a contradiction to the partition isommorphism.
\noindent
Cardinal exponentiation is a special case of products. In particular, \[ \kappa^{\lambda} = \prod\limits_{\alpha < \lambda}^{}. \] Cardinal exponentiation enjoys expected laws. \[ \left( \prod\limits_{i \in I}^{} \kappa_i \right)^{\lambda} = \prod\limits_{i \in I}^{} \kappa_i^{\lambda} \text{ and } \kappa^{\sum\limits_{i \in I}^{} \lambda_i} = \prod\limits_{i \in I}^{} \left( \kappa^{\lambda_i} \right) \]
The question now is to find a \(\gamma\) so that \(\aleph_{\alpha}^{\aleph_{\beta}} = \aleph_{\gamma}\). This question arguably has no good answer. One potential answer is given by the generalised continuum hypothesis (GCH): For any infinite \(\aleph_{\alpha}\) we have \[ 2^{\aleph_{\alpha}} = \aleph_{\alpha + 1}. \] If we have this, everything can be answered. Sadly both it and its negation are independent from our axioms.
We can prove two things.
- (A) \(2^{\aleph_{\alpha}} \geq \aleph_{\alpha + 1}\)
- (B) \(\alpha \leq \beta \implies 2^{\aleph_{\alpha}} \leq 2^{\aleph_{\beta}}\)
For the next statement we will need a few more definitions.
For every \(\alpha\), we have \[ \operatorname{cf}(2^{\aleph_{\alpha}}) > \aleph_{\alpha}. \]
For a limit ordinal \(\gamma\), an increasing sequence of ordinals of length \(\gamma\) is \((\alpha_\beta)_{\beta < \gamma}\) satisfying \[ \beta < \beta' \implies \alpha_{\beta} < \alpha_{\beta'}. \] The limit of such a sequence is \[ \lim_{\beta \rightarrow \gamma} \alpha_{\beta} := \sup_{\beta < \gamma} \alpha_{\beta}. \]
If \(\alpha\) is a limit ordinal, then its cofinality \(\operatorname{cf}(\alpha)\) is the smallest ordinal \(\gamma\) such that \(\alpha\) is the limit of an increasing sequence of ordinals of length \(\gamma\).
- \(\operatorname{cf}(\omega) = \omega\), since we can see \(\omega\) as a limit of the naturals.
- \(\operatorname{cf}(\omega^2) = \omega\) since \(\omega^2 = \lim \omega, \omega \cdot 2, \omega \cdot 3, \cdots\)
- \(\operatorname{cf}(\omega_1) = \omega_1\) since \(\omega_1 = \lim_{\alpha \rightarrow \omega} \alpha\)
- Similarly, \(\operatorname{cf}(\omega_2) = \omega_2\) and so on.
- \(\operatorname{cf}(\omega_{\omega}) = \omega\) since \[ \omega_{\omega} = \lim \omega, \omega_1, \omega_2, \dots \] i.e. we approximate it with an \(\omega\)-chain of ordinals.
\noindent
Theorem: initiality of cofinality noindent
We always have that \(\operatorname{cf}(\alpha)\) is always an infinite initial ordinal, i.e. an \(\aleph\).
\noindent Thus we often write \(\operatorname{cf}(\omega) = \omega = \aleph_0\) and the like.
- \(\operatorname{cf}(\aleph_0) = \operatorname{cf}(\omega) = \omega = \aleph_0\)
- \(\operatorname{cf}(\aleph_1) = \operatorname{cf}(\omega_1) = \omega_1 = \aleph_1\)
- \(\operatorname{cf}(\aleph_2) = \operatorname{cf}(\omega_2) = \omega_2 = \aleph_2\)
- \(\operatorname{cf}(\aleph_{\omega}) = \operatorname{cf}(\omega_{\omega}) = \omega = \aleph_0\)
By the cofinality theorem, we get
\begin{align*} 2^{\aleph_0} &\neq \aleph_0 \\ &= \aleph_1 \text{ is possible} \\ &= \aleph_2 \text{ is possible} \\ &\vdots\\ &\neq \aleph_{\omega} \text{ is ruled out by the theorem} \\ &= \aleph_{\omega + 1} \text{ is possible} \\ &\vdots \end{align*}Before we prove the above theorem C, we will have a few technical lemmata.
Every infinite cardinal \(\kappa\) can be expressed as \[ \kappa = \sum\limits_{\alpha < \operatorname{cf}(\kappa)}^{} \kappa_{\alpha} \] where we have \(\kappa_{\alpha} < \kappa\) for every \(\alpha < \operatorname{cf}(\kappa)\).
By the definition of cofinality, we have \(\kappa = \lim_{\alpha \rightarrow \operatorname{cf}(\kappa)} \beta_{\alpha}\) where \((\beta_{\alpha})_{\alpha < \operatorname{cf}(\kappa)}\) is an increasing sequence. If we look at all the ordinals between \(\beta_i\) and \(\beta_{i+1}\), we can partition \([\kappa]\) as the disjoint union \[ [\kappa] = \bigcup_{\alpha < \operatorname{cf}(\kappa)} \left( [\beta_{\alpha}] \setminus \bigcup\limits_{\alpha' < \alpha}^{} [\beta_{\alpha'}] \right) = \bigcup\limits_{\alpha < \operatorname{cf}(\kappa)}^{} B_{\alpha} \] Each \(B_{\alpha}\) is a subset of \([\beta_{\alpha}]\) and \(\abs{B_{\alpha}} \leq \abs{\beta_{\alpha}} < \kappa\). Since this is a disjoint union, we have \[ \kappa = \abs{\bigcup\limits_{\alpha < \operatorname{cf}(\kappa)}^{} B_{\alpha}} = \sum\limits_{\alpha < \operatorname{cf}(\kappa)}^{} \abs{B_{\alpha}} \] So \(\kappa = \sum\limits_{\alpha < \operatorname{cf}(\kappa)}^{} \abs{B_{\alpha}} and each \(\abs{B_{\alpha}} < \kappa\).
We need to show \(\operatorname{cf}(2^{\aleph_{\alpha}}) > \aleph_{\alpha}\). By the lemma, we have that \[ 2^{\aleph_{\alpha}} = \sum\limits_{\beta < \operatorname{cf}(2^{\aleph_{\alpha}})}^{} \kappa_{\beta} \] where every \(\kappa_{\beta} < 2^{\aleph_{\alpha}}\). By König's theorem we have \[ 2^{\aleph_\alpha} = \sum\limits_{\beta < \operatorname{cf}(2^{\aleph_{\alpha}})}^{} \kappa_{\beta} < \prod\limits_{\beta < \operatorname{cf}(2^{\aleph_{\alpha}})}^{} 2^{\aleph_{\alpha}} = \left( 2^{\aleph_{\alpha}} \right)^{\operatorname{cf}(2^{\aleph_{\alpha}})} \]
Suppose for contradiction that we \(\operatorname{cf}(2^{\aleph_{\alpha}}) \leq \aleph_{\alpha}\). Then we continue the inequality chain above as \[ 2^{\aleph_\alpha} = \sum\limits_{\beta < \operatorname{cf}(2^{\aleph_{\alpha}})}^{} \kappa_{\beta} < \prod\limits_{\beta < \operatorname{cf}(2^{\aleph_{\alpha}})}^{} 2^{\aleph_{\alpha}} = \left( 2^{\aleph_{\alpha}} \right)^{\operatorname{cf}(2^{\aleph_{\alpha}})} \leq \left( 2^{\aleph_{\alpha}} \right)^{\aleph_{\alpha}} = 2^{\aleph_{\alpha} \cdot \aleph_{\alpha}} = 2^{\aleph_{\alpha}}. \] We proved \(2^{\aleph_{\alpha}} < 2^{\aleph_{\alpha}}\) which is a contradiction.