Set Theory HT25, Cardinals and cardinalities

There exists a bijection $X \to Y$.

\[|X| := \lbrace Y : Y \sim X\rbrace\]

i.e. the equivalence class of $X$ under $\sim$.

• $ \vert X \vert \le \vert Y \vert $: There exists an injection $X \to Y$.
• $ \vert X \vert < \vert Y \vert $: $ \vert X \vert \le \vert Y \vert $ and $ \vert X \vert \ne \vert Y \vert $.

For all $\beta \in \alpha$, $ \vert \beta \vert \ne \vert \alpha \vert $.

$A \subseteq B$ implies $H(A) \subseteq H(B)$.

Suppose:

• $X$ is a set
• $H : \mathcal P(X) \to \mathcal P(X)$ is monotone

Then:

• $H$ has a fixed point
• One fixed point is $H(C) = C$ where:
  • $D := \lbrace A \subseteq X : A \subseteq H(A)\rbrace$
  • $C := \bigcup D$

Let $D := \lbrace A \subseteq X : A \subseteq H(A)\rbrace$ and $C := \bigcup D$. Then:

• $C \subseteq H(C)$:
  • Pick some $c \in C$.
  • Then $c \in A \in D$ for some $A$.
  • Then $A \subseteq H(A)$, so $c \in H(A)$.
  • But $A \subseteq C$, so $H(A) \subseteq H(C)$ by monotonicity, so $c \in H(C)$.
• $H(C) \subseteq C$:
  • Since $C \subseteq H(C)$, by monotonicity $H(C) \subseteq H(H(C))$, so $H(C) \in \mathcal D$.
  • Hence $H(C) \subseteq C$.

Hence $H(C) = C$ as required.

If $ \vert X \vert \le \vert Y \vert \le \vert X \vert $, then $ \vert X \vert = \vert Y \vert $.

@important~

In other words, we have to show that the existence of injections $f : X \hookrightarrow Y$ and $g : Y \hookrightarrow X$ imply the existence of a bijection $X \to Y$.

Define $H : \mathcal P(X) \to \mathcal P(X)$ by

\[\begin{aligned} H(A) &:= X \setminus g[Y \setminus f[A]] \end{aligned}\]

Then $H$ is monotone, since $f[\cdot]$ and $g[\cdot]$ are inclusion-preserving while complementation is inclusion reversing, so that

\[\begin{aligned} A \subseteq B \subseteq X &\implies f[A] \subseteq f[B] \\\\ &\implies Y \setminus f[A] \supseteq Y \setminus f[B] \\\\ &\implies g[Y \setminus f[A]] \supseteq g[Y \setminus f[B]] \\\\ &\implies X \setminus g[Y \setminus f[A]] \subseteq X \setminus g[Y \setminus f[B]] \\\\ &\implies H(A) \subseteq H(B) \end{aligned}\]

Hence by Tarski’s fixed point theorem, we have some $A \subseteq X$ with $H(A) = A$. Then

\[\begin{aligned} X \setminus A &= X \setminus H(A) \\\\ &= X \setminus (X \setminus g[Y \setminus f[A]]) \\\\ &= g[Y \setminus f[A]] \end{aligned}\]

(by the definition of $H(A)$).

Hence we have bijections

\[\begin{aligned} &f| _ A : A \to f[A] \\\\ &g| _ {Y \setminus f[A]} : Y \setminus f[A] \to g[Y \setminus f[A]] = X \setminus A \end{aligned}\]

then we can define:

\[h(x) = \begin{cases} f| _ A(x) &\text{if }x \in A \\\\ g| _ {Y\setminus f[A]}^{-1}(x) &\text{if } x \in X \setminus A \end{cases}\]

@important~

The first point is immediate.

For the second, we have that $ \vert X \vert \le \vert Z \vert $ by composing the injections corresponding to $ \vert X \vert \le \vert Y \vert \le \vert Z \vert $. If $ \vert X \vert = \vert Z \vert $, then $ \vert X \vert \le \vert Y \vert \le \vert X \vert $, so $ \vert X \vert = \vert Y \vert $ by Schröder-Bernstein, a contradiction.

There exists a bijection $f : X \to n$ for some $n \in \mathbb N$.

We first show that every subset of a natural number is finite by induction.

Base case: $n = 0$. Then $n$ only has the subset $\emptyset$, but this is clearly finite ($f : \emptyset \to \emptyset$ is a bijection).

Inductive step: $n > 0$. Suppose we know every subset of $n$ is finite. Then consider the subsets of $n^+ = n \cup \lbrace n \rbrace$, say $x \subseteq n^+$. If $n \notin x$, then $x \subseteq n$ and hence $x$ is finite by the inductive hypothesis.

If $n \in x$, consider $x’ \in x \setminus \lbrace n \rbrace$. Then $x’ \subseteq n$, and so $x’$ is finite. Hence there exists a bijection $f : x’ \to m$ for some $m$. Extend this to a bijection $g : x \to m^+$ by sending $n$ to $m$. Hence $x$ is also finite.

---

Now suppose $X$ is an arbitrary finite set with corresponding bijection $f : X \to n$ for some $n \in \mathbb N$.

Let $Y \subseteq X$, and consider $f \vert _ Y : Y \to n$. Since $\text{ran}(f \vert _ Y) \subseteq n$ and all subsets of $n$ are finite, there exists another bijection $g : \text{ran}(f \vert _ Y) \to m$ for some $m \in \mathbb N$.

By taking the composition (which exists by comprehension),

\[g \circ f : Y \to m\]

gives a bijection from $Y$ to some $m \in \mathbb N$, and hence $Y$ is finite.

If $X$ is finite, then any injective function $f : X \to X$ is surjective.

Induct on the size of the set $n = \vert X \vert $.

If $X = \emptyset$, then the result is immediate.

Otherwise, suppose $h : X \to X$ is a non-surjective injection of finite sets where $ \vert X \vert = n^+$. As $X$ is finite, there exists some $b : X \to n^+$ for some $n^+$ where $b$ is a bijection.

Consider

\[f : n^+ \to n^+\]

defined by $f := b \circ h \circ b^{-1}$ which is also a non-surjective injection. As $f$ is non-surjective, there exists $k \in n^+$ such that $k \notin \text{ran}(f)$. Let $\tau : n^+ \to n^+$ be the bijective transposition that swaps $n$ and $k$, and fixes everything else.

Then $f’ : n^+ \to n$ defined by $f’ := \tau \circ f$ is also an injection. But so is $f’ \vert _ n : n \to n$. Hence there exists $m \in n$ such that $f’(n) = f’(m)$, a contradiction, as $f’ \vert _ n$ is surjective by the inductive hypothesis.

Note that the successor function $n \mapsto n^+$ on $\mathbb N$ is injective but not surjective.

\[\aleph _ 0 = |\mathbb N|\]

1. Countable: $ \vert X \vert \le \aleph _ 0$
2. Countably infinite: It is countable and infinite
3. Uncountable: It is not countable

1.

---

There is a result which says a non-empty set is countable iff there is a surjection $\mathbb N \twoheadrightarrow X$, but the definition is in terms of injections.

A set $X$ is countably infinite iff $ \vert X \vert = \aleph _ 0$.

(i.e. there is no infinite cardinality below $\aleph _ 0$).

$ \vert X \vert = \aleph _ 0$ implies $X$ is countably infinite:

$X$ must be infinite since $\mathbb N$ is infinite. Hence $X$ is countably infinite.

---

$X$ is countably infinite implies $ \vert X \vert = \aleph _ 0$:

Overall idea: Since $X$ is countable, we already have an injection $X \hookrightarrow \mathbb N$. Hence it suffices by Schröder-Bernstein to exhibit an injection $\mathbb N \hookrightarrow X$. We do this by defining a function by recursion on $\mathbb N$ which picks out an increasing sequence of elements using the fact that $X$ is infinite.

In detail: We may assume that $X \subseteq \mathbb N$, since $X$ is in bijection with its image under an injection $X \to \mathbb N$.

Since $X$ is infinite, and subsets of finite sets are finite, it follows that $X \setminus n \ne \emptyset$ for all $n \in \mathbb N$ (since otherwise $X \subseteq n$).

Hence define by recursion $f : \mathbb N \to X$ by

\[\begin{aligned} f(0) &:= \min(X) \\\\ f(n^+) &:= \min(X \setminus f(n)^+) \end{aligned}\]

where $\min$ is well-defined by the fact $\mathbb N$ is well-ordered.

Then $f$ is injective because $n > m \implies f(n) > f(m)$ by induction on $n$: If $n = 0$, this is trivial, and now suppose for $n$ and suppose $m < n^+$; then $f(n) \ge f(m)$ by the inductive hypothesis, and $f(n^+) = \min(X \setminus f(n)^+) > f(n)$, so $f(n^+) > f(m)$ as required.

Hence $ \vert \mathbb N \vert \le \vert X \vert $, and hence $ \vert X \vert = \vert \mathbb N \vert $ by Schröder-Bernstein.

---

For reference, here are the definitions for countable, infinite and countably infinite:

1. Countable: $ \vert X \vert \le \aleph _ 0$, i.e. injection from $X$ to $\mathbb N$.
2. Infinite: Not finite, so there it is not in bijection with a natural number.
3. Countably infinite: It is countable and infinite.

And Schröder-Bernstein says that if $ \vert X \vert \le \vert Y \vert \le \vert X \vert $, then $ \vert X \vert = \vert Y \vert $.

A non-empty set $X$ is countable iff there exists a surjection $\mathbb N \to X$.

For the backward direction, if $f : \mathbb N \to X$ is surjective, then $g(x) := \min \lbrace n \in \mathbb N : f(n) = x\rbrace$ defines an injection $g : X \to \mathbb N$.

For the forward direction, note that by composing with a bijection we may assume that either $X = \mathbb N$, in which case the result is immediate, or $X = n$ for some $n \in \mathbb N$. Then $n > 0$ since $X$ is nonempty, and we can define a surjection $f : \mathbb N \to n$ by

\[f(i) := \begin{cases} i &\text{if } i < n \\\\ 0 &\text{otherwise} \end{cases}\]

• $ \vert X \vert + \vert Y \vert := \vert X \cup Y \vert $ if $X \cap Y \ne \emptyset$, if not disjoint consider e.g. $X \times \lbrace 0\rbrace$ and $Y \times \lbrace 1\rbrace$, which have same cardinalities as original group.
• $ \vert X \vert \cdot \vert Y \vert := \vert X \times Y \vert $
• $ \vert X \vert ^{ \vert Y \vert } := \vert X^Y \vert $

Define $F : \mathcal P(X) \to 2^X$ by

\[F(Y)(x) = \begin{cases} 0 &\text{if } x \notin Y \\\\ 1 &\text{if } x \in Y \end{cases}\]

so that $F(Y)$ is the indicator function of $Y$. This is a bijection.

For any set $X$, there is no surjection $X \to \mathcal P(X)$.

Let $f : X \to \mathcal P(X)$. Consider

\[D := \lbrace x \in X : x \notin f(x)\rbrace \subseteq X\]

But $D \notin \text{ran}(f)$: suppose that $a \in X$ such that $f(a) = D$. Then $a \in D$ iff $a \notin f(a) = D$, a contradiction. So therefore $f$ is not surjective.

Suppose $\kappa = \vert X \vert $, so $2^\kappa = \vert \mathcal P(X) \vert $.

Then $x \mapsto \lbrace x\rbrace$ is an injection $X \to \mathcal P(X)$, so $\kappa \le 2^\kappa$. If $\kappa$ were equal to $2^\kappa$, then there would a bijection $X \to \mathcal P(X)$, contradicting the fact that no surjection $X \to \mathcal P(X)$ exists.

---

For reference, the proof there is no surjection $X \to \mathcal P(X)$ is as follows: let $f : X \to \mathcal P(X)$. Consider

\[D := \lbrace x \in X : x \notin f(x)\rbrace \subseteq X\]

Suppose that $a \in X$ such that $f(a) = D$. Then $a \in D$ iff $a \notin f(a) = D$, a contradiction. So therefore

\[D \in \mathcal P(X) \setminus \text{ran}(f)\]

Hence $f$ is not surjective.

\[|X| := \min \lbrace \alpha \in \mathbf{ON} : \alpha \sim X\rbrace\]

Choice is equivalent to the statement that every set can be well-ordered. This implies every set is equinumerous with an ordinal, so for the minimum to be over a non-empty set requires choice.

For an ordinal $\alpha$, the following are equivalent characterisations of what it means to be a cardinal:

1. $\alpha = \vert X \vert $ for some set $X$
2. $\alpha = \vert \alpha \vert $
3. For all $\beta \in \alpha$, $\beta \not\sim \alpha$ (where $\sim$ denotes that there exists a bijection).

Property 3 also makes sense in ZF, so this can be used to define some ordinals as cardinals without choice.

An ordinal $\alpha$ such that $\alpha = \vert X \vert $ for some set $X$.

Two ways:

• $ \vert \mathcal P(\kappa) \vert > \vert \kappa \vert = \kappa$
• By Hartog’s theorem and the fact choice is equivalent to cardinal comparability, there is an ordinal $\alpha$ such that $ \vert \alpha \vert > \vert \kappa \vert = \kappa$.

The class of all cardinals.

We aim to show $ \vert \bigcup K \vert = \bigcup K$, since in ZFC this is equivalent to $\bigcup K$ being a cardinal.

In the following, let $\le _ \text{ord}$ denote ordinal comparison (i.e. one is a subset of the other) and let $\le _ \text{card}$ denote cardinal comparison (i.e. the existence of an injection).

Note that $\bigcup K$ is an ordinal by the result that says the union of ordinals is an ordinal, and each cardinal in $K$ is in particular an ordinal.

• $ \vert \bigcup K \vert \le _ \text{ord} \bigcup K$:
  • This follows from the definition of $ \vert \cdot \vert $.
  • Explicitly: $ \vert \bigcup K \vert = \min \lbrace \alpha \in \mathbf{ON} \mid \alpha \sim \bigcup K \rbrace$, and since $\bigcup K \sim \bigcup K$, $ \vert \bigcup K \vert \le \bigcup K$.
• $ \vert \bigcup K \vert \not< _ \text{ord} \bigcup K$:
  • Suppose $ \vert \bigcup K \vert < _ \text{ord} \bigcup K$, so $ \vert \bigcup K \vert \in \bigcup K$.
  • Then $ \vert \bigcup K \vert \in \kappa$, for some $\kappa \in K$.
  • Then $ \vert \bigcup K \vert < _ \text{card} \vert \kappa \vert $ (recall the characterisation of cardinals $\kappa$ as ordinals where all their elements are less than $\kappa$).
  • But by transitivity, we must also have $\kappa \subseteq \bigcup K$, and hence $ \vert \kappa \vert \le _ \text{card} \vert \bigcup K \vert $.
  • This is a contradiction, since then $ \vert \bigcup K \vert < _ \text{card} \vert \kappa \vert \le _ \text{card} \vert \bigcup K \vert $.

Hence $ \vert \bigcup K \vert = \bigcup K$.

Let $\aleph _ {(\cdot)} : \mathbf{ON} \to \mathbf{CN}$ be the class function defined by transfinite recursion like so:

• $\aleph _ 0 = \omega$
• $\aleph _ {\alpha^+}$ is the smallest cardinal greater than $\aleph _ \alpha$
• $\aleph _ \eta = \bigcup _ {\beta \in \eta} \aleph _ \beta$ if $\eta$ is a limit ordinal

We use two results about $\aleph _ {(\cdot)}$:

1. $\aleph _ \gamma \ge \gamma$ for all $\gamma \in \mathbf{ON}$ (follows from transfinite induction)
2. If $\gamma < \eta \in \mathbf{ON}$, then $\aleph _ \gamma < \aleph _ \eta$ (follows from transfinite induction on $\eta$)

---

Let $\kappa$ be an infinite cardinal and consider the set

\[\begin{aligned} \alpha &= \lbrace \beta : \aleph _ \beta < \kappa\rbrace \\\\ &= \lbrace \beta \in \kappa : \aleph _ \beta < \kappa\rbrace \end{aligned}\]

where the equality follows from (1), since $\aleph _ \beta < \kappa$ and $\beta < \aleph _ \beta$ implies $\beta < \kappa$.

• $\aleph _ \alpha \ge \kappa$:
  • By foundation, $\alpha \notin \alpha$, so $\aleph _ \alpha \not< \kappa$, which implies by choice $\aleph _ \alpha \ge \kappa$.
  • (There is also an argument that $\alpha$ is an initial segment of an ordinal by (2), so it itself is an ordinal, so $\alpha \notin \alpha$, but doesn’t it just follow from foundation?)
• $\aleph _ \alpha \le \kappa$:
  • If $\alpha = 0$, this follows from $\kappa$ being infinite.
  • If $\alpha$ is a successor ordinal, say $\alpha = \gamma^+$, then $\aleph _ \gamma < \kappa$, so $\aleph _ \alpha = \aleph _ {\gamma^+} \le \kappa$ by definition of $\aleph _ {\gamma^+}$.
  • If $\alpha$ is a limit ordinal, then $\aleph _ \alpha = \bigcup _ {\beta \in \alpha} \aleph _ \beta \le \kappa$, since each $\aleph _ \beta < \kappa$.

By the result that every infinite cardinal is of the form $\aleph _ \alpha$ for some $\alpha \in \mathbf{ON}$ and hence the function $\aleph _ {(\cdot)} : \mathbf{ON} \to \mathbf{CN}$ given by $\alpha \mapsto \aleph _ \alpha$ is a well-defined surjective class function $\mathbf{CN} \setminus \omega \to \mathbf{ON}$. If $\mathbf{CN}$ were a set, then by replacement, $\mathbf{ON}$ would also be a set, a contradiction.

Note that

\[\mathcal P _ \text{fin}(\mathbb R) = \bigcup _ {n \in \omega} \lbrace S \subseteq \mathbb R : |S| = n\rbrace\]

Since $ \vert X \cup Y \vert = \vert X \vert + \vert Y \vert $ when $X$ and $Y$ disjoint, it follows that

\[|\mathcal P _ \text{fin}(\mathbb R)| = \sum _ {n \in \omega} n \cdot 2^{\aleph _ 0} = \aleph _ 0 \cdot 2^{\aleph _ 0} = 2^{\aleph _ 0}\]

• $\kappa + \lambda := \vert (\kappa \times \lbrace 0\rbrace ) \cup (\lambda \times \lbrace 1\rbrace ) \vert $
• $\kappa \cdot \lambda := \vert \kappa \times \lambda \vert $
• $\kappa^\lambda := \vert \lbrace f : \lambda \to \kappa\rbrace \vert $

This is ambiguous because these definitions don’t agree with ordinal arithmetic operations (which were defined inductively, or by considering the sum and product orders). This is handled notationally by using $\kappa, \lambda, \mu, \nu$ and $\aleph _ \alpha$ for cardinals whereas we use $\alpha$, $\beta$, $\gamma$, $\delta$ and $\omega _ \alpha$ to refer to ordinals.

1. Cardinal addition and multiplication is commutative and associative
2. If $\kappa$ is an infinite cardinal, then $\kappa \cdot \kappa = \kappa$
3. If $\kappa$ is an infinite cardinal and $\lambda$ is a cardinal with $1 \le \lambda \le \kappa$, then $\kappa + \lambda = \kappa \cdot \lambda = \kappa$.
4. If $\kappa$ and $\lambda$ are infinite cardinals, then $\kappa + \lambda = \kappa \cdot \lambda = \max(\kappa, \lambda)$.

In the following, let $\le _ \text{ord}$ denote ordinal comparison (i.e. one is a subset of the other) and let $\le _ \text{card}$ denote cardinal comparison (i.e. the existence of an injection).

We proceed by transfinite induction. Assume $ \vert \alpha \vert \cdot \vert \alpha \vert = _ \text{card} \vert \alpha \vert $ for all infinite ordinals $\alpha < _ \text{ord} \kappa$. Then $ \vert \alpha \vert \cdot \vert \alpha \vert < _ \text{card} \kappa$ for all $\alpha < _ \text{ord} \kappa$ for finite $\alpha$, this is because $ \vert \alpha \vert \cdot \vert \alpha \vert $ is finite.

Define an order $\triangleleft$ on $\kappa \times \kappa$ by

\[(\alpha, \beta) \triangleleft (\alpha', \beta') \iff (\alpha, \beta, \max(\alpha, \beta)) <_r (\alpha', \beta', \max(\alpha', \beta'))\]

where $< _ r$ is the reverse lexicographic order.

This is a well-order, so $(\kappa \times \kappa, \triangleleft)$ is isomorphic to an ordinal $\gamma$.

Let $S$ be a proper initial segment, say $S = (\kappa \times \kappa) _ {\triangleleft(\alpha, \beta)}$. Set $\delta := \max(\alpha, \beta)$. Then $S \subseteq \delta^+ \times \delta^+$, and $\delta^+ \in \kappa$ (holds if $\delta$ is finite since $\kappa$ is infinite, and if $\delta$ is infinite, then $ \vert \delta^+ \vert = \vert \delta \vert < \kappa)$, so by the very first result, $ \vert S \vert \le \vert \delta^+ \vert \cdot \vert \delta^+ \vert < \kappa$.

Let $\gamma$ be the ordinal isomorphic to $S$. Hence $\gamma \le \kappa$, since otherwise $\gamma$ would have a proper initial segment $\gamma _ {<\kappa}$ of cardinality $\kappa$.

---

Alternative proof:

For any infinite cardinal $\kappa$, either $\kappa < \kappa \cdot \kappa$ or $\kappa = \kappa \cdot \kappa$. Let $\kappa$ be the smallest cardinal such that $\kappa < \kappa \cdot \kappa$; we aim to show that no such cardinal exists.

Let $K = \kappa \times \kappa$, and note that $K$ has a well-ordering given by the reverse lexicographic ordering.

Since $\kappa < \kappa \cdot \kappa = \vert K \vert $, there is an initial segment $L$ of $K$ that is isomorphic to $\kappa$.

Since $L$ is an initial segment of $K$,

\[L = \lbrace (\beta_1, \beta_2) \mid (\beta_1, \beta_2) <_r (\alpha_1, \alpha_2) \rbrace\]

for some $(\alpha _ 1, \alpha _ 2) \in K$.

Let $\lambda = \max(\alpha _ 1, \alpha _ 2)$. Since $L \subset K$, $L \subset K = \kappa \times \kappa$, it follows that $\alpha _ 1 < \kappa$ and $\alpha _ 2 < \kappa$, and therefore $\lambda < \kappa$.

For any $(\beta _ 1, \beta _ 2) \in L$, we have $(\beta _ 1, \beta _ 2) < _ r (\alpha _ 1, \alpha _ 2)$, which implies $\max (\beta _ 1, \beta _ 2) \le \lambda$. Therefore $L \subseteq \lambda^+ \times \lambda^+$, so $ \vert L \vert \le \vert \lambda^+ \times \lambda^+ \vert \le \vert \lambda^+ \vert \cdot \vert \lambda^+ \vert $.

If $L$ is finite, so is $\lambda^+ \times \lambda^+$, which is a contradiction as $L$ is isomorphic to $\kappa$, an infinite set.

Hence $L$ must be infinite, and so $\lambda$ is infinite. If $\lambda$ is infinite, so is $\lambda^+$. Since $\lambda < \kappa$ and $\kappa$ is a limit ordinal (all infinite cardinals are limit ordinals, since $\kappa^+ \sim \kappa)$, $ \vert \lambda^+ \vert < \kappa$ also.

But by assumption on the minimality of $\kappa$, it follows $ \vert \lambda^+ \vert \cdot \vert \lambda^+ \vert = \vert \lambda^+ \vert $. Therefore

\[|L| \le |\lambda^+| \cdot |\lambda^+| = |\lambda^+| \le \lambda^+ < \kappa\]

and so $L$ cannot be order isomorphic to $\kappa$.

(1): For addition, this follows from the commutativity and associativity of union.

For multiplication, associativity follows from the associativity of “$\times$”. For commutativity, note that $\langle x, y \rangle \mapsto \langle y, x \rangle$ defines a bijection $X \times Y \to Y \times X$.

---

(2): Since ordinal addition is monotonic, by (1) we have

\[\begin{aligned} \kappa &\le \kappa + \lambda \le \kappa + \kappa = \kappa \cdot 2 \le \kappa \cdot \kappa = \kappa \\\\ \kappa &\le \kappa \cdot \lambda \le \kappa \cdot \kappa = \kappa \end{aligned}\]

Hence $\kappa = \kappa + \lambda = \kappa \cdot \lambda$.

---

(3): By (2) and commutativity of cardinal addition and multiplication.

If $f : X \to Y$ is a surjection, then $ \vert X \vert \ge \vert Y \vert $.

(contrast to the result that if $f : X \to Y$ is an injection, then $ \vert X \vert \le \vert Y \vert $).

Let $h$ be a choice function for $X$. Then

\[g(y) := h(\lbrace x \in X : f(x) = y\rbrace )\]

defines an injection $Y \to X$. Hence $ \vert Y \vert \le \vert X \vert $.

Suppose:

• $\kappa$ is an infinite cardinal
• $X$ is a set
• $ \vert X \vert \le \kappa$
• $ \vert a \vert \le \kappa$ for all $a \in X$

Then:

• $ \vert \bigcup X \vert \le \kappa$

---

The familiar special case is that a countable union of countable sets is countable (take $\kappa = \aleph _ 0$).

Overall idea: Consider the set of pairs $Z := \lbrace \langle g(\alpha), f _ \alpha(x)\rangle \mid x \in \alpha \in X \rbrace$, where $g : X \hookrightarrow \kappa$ and $f _ \alpha : \alpha \hookrightarrow \kappa$ are injections we can find by choice. Then $Z \subseteq \kappa \times \kappa$, but the map which sends the pair $\langle g(\alpha), f _ \alpha(x) \rangle$ to $x$ surjects onto $\bigcup X$, and thus we have the required cardinality.

For every $a \in X$, there exists an injection $a \to \kappa$. By choice, we can uniformly choose such injections: let $I _ a$ be the set of injections $f : a \to \kappa$, let $h$ be a choice function on $\bigcup \lbrace I _ a : a \in X\rbrace$ and let $f _ a := h(I _ a)$.

Let $g : X \to \kappa$ be an injection. Then $Z := \lbrace \langle g(a), f _ a(x) \rangle : x \in a \in X\rbrace$ is a subset of $\kappa \times \kappa$, so $ \vert Z \vert \le \kappa \cdot \kappa = \kappa$.

Finally $\langle g(a), f _ a(x)\rangle \mapsto x$ is a surjection $Z \to \bigcup X$, so by the result which gives upper bounds in terms of surjections, it follows $ \vert \bigcup X \vert \le \vert Z \vert \le \kappa$.

Suppose for a contradiction that $2^\kappa = \aleph _ 0$. Then there is a set $X$ such that $\mathcal P(X)$ is in bijection with $\omega$. Since there is an injection $X \hookrightarrow \mathcal P(X)$ given by $x \mapsto \lbrace x \rbrace$, it follows $X$ is in bijection with a subset of $\omega$.

Hence $X$ is countable.

If $X$ is finite, then $\mathcal P(X)$ is finite, a contradiction.

If $X$ is infinite, then $ \vert X \vert = \aleph _ 0$, and so $2^\kappa \ne \aleph _ 0$ by Cantor’s theorem.

@example~ @exam~

$\aleph _ 0 \cdot \aleph _ 0 = \aleph _ 0$

---

$\aleph _ 0 \le \aleph _ 0 \cdot \aleph _ 0$ follows from the injection $n \to \langle n, 0 \rangle$. $\aleph _ 0 \cdot \aleph _ 0 \le \aleph _ 0$ follows from the injection $\langle n, m \rangle \mapsto 2^n \cdot 3^m$.

---

Alternatively, $\aleph _ 0 \cdot \aleph _ 0 = \aleph _ 0$ follows from the bijection $\langle n, m \rangle \mapsto \frac 1 2 (n + m) (n + m + 1)$.

There is also a more general result that for all infinite cardinals $\kappa$, $\kappa \cdot \kappa = \kappa$.

@example~

$ \vert \mathbb Q \vert = \aleph _ 0$

---

$ \vert \mathbb Q \vert \ge \aleph _ 0$ follows from $n \to \frac n 1$ being an injection.

$ \vert \mathbb Q \vert \le \aleph _ 0$ follows from

\[\begin{aligned} (\mathbb N \times \mathbb N) \times \mathbb N &\to \mathbb Q \\\\ \langle \langle n, m \rangle, k \rangle &\mapsto \frac{n-m}{k+1} \end{aligned}\]

being a surjection and $ \vert (\mathbb N \times \mathbb N) \times \mathbb N \vert = \aleph _ 0$.

@example~

$ \vert \mathbb R \vert = 2^{\aleph _ 0}$.

---

$ \vert \mathbb R \vert \le 2^{\aleph _ 0}$ follows from the map

\[\begin{aligned} \mathbb R &\to \mathcal P(\mathbb Q) \\\\ x &\mapsto \lbrace q \in \mathbb Q : q < x\rbrace \end{aligned}\]

being an injection since $\mathbb Q$ is dense in $\mathbb R$. Hence $ \vert \mathbb R \vert \le \vert \mathcal P(\mathbb Q) \vert = 2^{ \vert \mathbb Q \vert } = 2^{\aleph _ 0}$.

$ \vert \mathbb R \vert \ge 2^{\aleph _ 0}$ follows from the map

\[\begin{aligned} 2^\mathbb N &\to \mathbb R \\\\ f &\mapsto \sum^\infty _ {n = 0} \frac{f(n)}{3^n} \end{aligned}\]

Then $\Phi$ is injective, so $2^{\aleph _ 0} \le \vert \mathbb R \vert $.

@example~

$2^{2^{\aleph _ 0} }$

---

Call this set $F = \mathbb R^{\mathbb R}$. Then

\[\begin{aligned} |F| &= |\mathbb R|^{|\mathbb R|} \\\\ &= 2^{\aleph _ 0 \cdot 2^{\aleph _ 0} } \\\\ &= 2^{2^{\aleph _ 0} } \end{aligned}\]

@example~

$2^{2^{\aleph _ 0} }$

---

Call this set $S$.

$ \vert S \vert \le 2^{2^{\aleph _ 0} }$, since every element of $S$ is a subset of $\mathbb R \times \mathbb R$, and hence an element of $\mathcal P(\mathbb R \times \mathbb R)$. Then $ \vert S \vert \le \vert \mathcal P(\mathbb R \times \mathbb R) \vert = 2^{2^{\aleph _ 0} }$.

To see $2^{2^{\aleph _ 0} } \le \vert S \vert $, we exhibit an injection $\mathcal P(\mathbb R \setminus \lbrace 0\rbrace ) \hookrightarrow S$. For $X \in \mathcal P(\mathbb R \setminus \lbrace 0\rbrace )$, consider $Y = \mathbb R \setminus (\lbrace 0\rbrace \cup X)$. Then both $X$ and $Y$ can be strict totally ordered by $< _ \mathbb R$.

We can construct a new strict total order $(\mathbb R, <’)$:

• $x <’ x’ \iff x < _ {\mathbb R} x’$ and $x, x’ \in X$
• $y <’ y’ \iff y < _ {\mathbb R} y’$ and $y, y’ \in Y$
• $x < y$ for all $x \in X$ and $y \in Y$

This is a distinct strict total order for every $X \subseteq \mathcal P(\mathbb R \setminus \lbrace 0\rbrace )$, so the map taking $X$ to this strict total order is injective.

@example~

Call this set $E$.

$ \vert E \vert \le 2^{2^{\aleph _ 0} }$, since every element of $E$ is a subset of $\mathcal P(\mathbb N) \times \mathcal P(\mathbb N)$ and hence an element of $\mathcal P(\mathcal P(\mathbb N) \times \mathcal P(\mathbb N))$, so $ \vert E \vert \le \vert \mathcal P(\mathcal P(\mathbb N) \times \mathcal P(\mathbb N)) \vert = 2^{2^{\aleph _ 0} }$.

To see $2^{2^{\aleph _ 0} }$, we exhibit an injection $\mathcal P(\mathcal P(\mathbb N) \setminus \lbrace \lbrace 0\rbrace \rbrace ) \hookrightarrow E$. Send $S \in \mathcal P(\mathbb N) \setminus \lbrace \lbrace 0\rbrace \rbrace$ to the equivalence relation with the two equivalence classes $S \cup \lbrace \lbrace 0\rbrace \rbrace$ and $\mathcal P(\mathbb N) \setminus (S \cup \lbrace \lbrace 0\rbrace \rbrace )$. This is a distinct strict total order for every $S \subseteq \mathcal P(\mathbb N) \setminus \lbrace 0\rbrace$, so the map taking $S$ to this equivalence relation is injective.

---

Why exclude zero? If we didn’t, then $S$ and $\mathcal P(\mathbb N) \setminus S$ would get sent to the same equivalence relation. Excluding zero as a point means we can mark which set is the “actual” one, rather than the complement.

@example~

$ \vert X \vert $

---

Every countable subset of $X$ is always the image of some map $f : \omega \to X$. Hence

\[\begin{aligned} |P| &\le |f : \omega \to X| \\\\ &= |X^\omega| &&(\text{def.}) \\\\ &= |X|^{\aleph _ 0} &&(\text{def.}) \\\\ &= |X| &&(\text{assump.}) \end{aligned}\]

But also $ \vert X \vert \le \vert P \vert $ as we may consider the injection $x \mapsto \lbrace x\rbrace$. Hence $ \vert P \vert = \vert X \vert $.

@example~ @exam~

$2^{2^{\aleph _ 0} }$.

---

By definition:

\[|\lbrace f : \mathcal P(\omega) \to \omega \rbrace| = |\omega^{\mathcal P(\omega)}| = (\aleph _ 0)^{2^{\aleph _ 0} }\]

We first show $2^{\aleph _ 0} = \aleph _ 0 \times 2^{\aleph _ 0}$:

\[\begin{aligned} 2^{\aleph _ 0} &\le \aleph _ 0 \times 2^{\aleph _ 0} && (\text{injection}) \\\\ &\le 2^{\aleph _ 0} \times 2^{\aleph _ 0} &&(\text{injection}) \\\\ &= 2^{\aleph _ 0 + \aleph _ 0} &&(\text{properties of exp.}) \\\\ &= 2^{\aleph _ 0} &&(\text{properties of addition}) \end{aligned}\]

and hence $2^{\aleph _ 0} = \aleph _ 0 \times 2^{\aleph _ 0}$ by Schröder-Bernstein.

Then

\[\begin{aligned} 2^{2^{\aleph _ 0} } &\le (\aleph _ 0)^{2^{\aleph _ 0} } &&(\text{injection}) \\\\ &\le (2^{\aleph _ 0})^{2^{\aleph _ 0} } &&(\text{injection}) \\\\ &= 2^{\aleph _ 0 \times 2^{\aleph _ 0} } &&(\text{properties of exp.}) \\\\ &= 2^{2^{\aleph _ 0} } &&(\text{prev. result}) \end{aligned}\]

and hence $2^{2^{\aleph _ 0} } = (\aleph _ 0)^{2^{\aleph _ 0} }$ by Schröder-Bernstein.

@example~ @exam~

Take $\kappa = 2^{\aleph _ 0}$ and $\lambda = \aleph _ 0$. Then

\[(2^{\aleph _ 0})^{\aleph _ 0} = 2^{\aleph _ 0 \cdot \aleph _ 0} = 2^{\aleph _ 0}\]

and hence $\kappa^\lambda = \kappa$.

@example~ @exam~

$2^{\aleph _ 0}$.

---

Call this set $S$, so that

\[S = \lbrace f : \mathbb R \to \mathbb R, f \text{ is monotonically increasing} \rbrace\]

If $f$ is a monotonically increasing function and $x$ is a point of discontinuity, then there must be a rational between $f(x^-) = \sup \lbrace f(y) : y < x \rbrace$ and $f(x^+) = \inf \lbrace f(y) : y > x \rbrace$. So $f$ must have at most countably many points of discontinuity.

$ \vert S \vert \le 2^{\aleph _ 0}$:

For each $f$, let $F(f)$ be $\langle A, g, B, h \rangle$ where:

• $A$ is the set of all points of discontinuity
• $g$ is a function whose domain is $A$ such that $g(x) = \langle f(x^-), f(x), f(x^+)\rangle$ for each $x \in A$, $B$ is a countable dense subset of $\mathbb R \setminus A$, and $h = f \vert _ B$.

Then $F$ is one-to-one. The set of all possible values of $A$ has size $2^{\aleph _ 0}$. For each $A$, the set of all possible $g$ has size $2^{\aleph _ 0}$. The set of all possible $B$ has the same size, and so does the set of all possible $h$. So the set of all monotonically increasing functions from $\mathbb R \to \mathbb R$ has size at most $2^{\aleph _ 0}$.

$2^{\aleph _ 0} \le \vert S \vert $:

Since every function $k _ a : x \to x + a$ is monotonically increasing, the injection $a \mapsto k _ a$ shows that our set has size at least $2^{\aleph _ 0}$.

$2^{2^{\aleph _ 0} }$.

---

Call this set $X$.

$ \vert X \vert \le 2^{2^{\aleph _ 0} }$: Every basis is a subset of $\mathbb R$, so the number of bases is at most $ \vert \mathcal P(\mathbb R) \vert = 2^{2^{\aleph _ 0} }$.

$2^{2^{\aleph _ 0} } \le \vert X \vert $: Start with some basis

\[B = \lbrace x _ \alpha \mid \alpha < \kappa \rbrace\]

where $\kappa$ is the cardinality of the basis.

Then $B$ has $\kappa$-many finite subsets (consider the number of maps $f : \omega \to B$), each of which has a countable span (since the combinations are $\mathbb Q$-linear).

So the cardinality of $\mathbb R$ is $\kappa \cdot \aleph _ 0$, which equals $\max(\kappa, \aleph _ 0) = \kappa$. So $\kappa = 2^{\aleph _ 0}$.

Now we find an injection $2^{2^{\aleph _ 0} } \hookrightarrow \vert X \vert $: For any function $f : \mathbb R \to \lbrace 0, 1 \rbrace$, let $B _ f = \lbrace x _ \alpha \mid f(\alpha) = 0 \rbrace \cup \lbrace 2 x _ \alpha \mid f(\alpha) = 1\rbrace$. Then each $B _ f$ is a basis, and the function mapping $f$ to $B _ f$ is one-to-one. Hence the number of bases is at least $ \vert \lbrace 0, 1\rbrace \vert ^{2^{\aleph _ 0} } = 2^{2^{\aleph _ 0} }$.

$ \vert W \vert = 2^{\aleph _ 0}$.

---

$ \vert W \vert \le 2^{\aleph _ 0}$: Any subset $X \subseteq \mathbb R$ that is well-ordered by $<$ is countable. Hence such a set is finite or countably infinite.

In either case, such a set is the image of a map $f : \omega \to \mathbb R$, and hence using the axiom of choice, there is an injection of $W$ into $\mathbb R^\omega$. Since

\[|\mathbb R^\omega| = (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0}\]

$2^{\aleph _ 0} \le \vert W \vert $: Note any $x \in \mathbb R$ can be mapped to the well-ordered subset $\lbrace x \rbrace$.

@example~ @exam~

$ \vert I \vert = 2^{2^{2^{\aleph _ 0} } }$.

---

$ \vert I \vert \le 2^{2^{2^{\aleph _ 0} } }$: Note that $I$ is a subset of $\mathcal P(\mathbb R)^{\mathcal P(\mathbb R)}$. But

\[|\mathcal P(\mathbb R)^{\mathcal P(\mathbb R)}| = |\mathcal P(\mathbb R)|^{|\mathcal P(\mathbb R)|} = (2^{2^{\aleph_0} })^{2^{2^{\aleph_0} } } = 2^{2^{2^{\aleph_0} } }\]

as required.

$2^{2^{2^{\aleph _ 0} } } \le \vert I \vert $: We show that $ \vert \mathcal P(\mathbb R)^{\mathcal P(\mathbb R)} \vert \le \vert I \vert $, which has the correct cardinality by the above.

Let $f : \mathcal P(\mathbb R) \to \mathcal P(\mathbb R)$ be any function. Then $f^\ast : P \to P \times P$ given by $f^\ast(X) = (X, f(X))$ is injective. Since $\mathcal P(\mathbb R)$ is infinite, we also know that there exists a bijection $\varphi : \mathcal P(\mathbb R) \times \mathcal P(\mathbb R) \to \mathcal P(\mathbb R)$ (since infinite cardinal multiplication is idempotent).

Then the map which takes $f$ to $\varphi \circ f^\ast$ is an injection $\mathcal P(\mathbb R)^{\mathcal P(\mathbb R)} \hookrightarrow I$. Hence $ \vert \mathcal P(\mathbb R)^{\mathcal P(\mathbb R)} \vert \le \vert I \vert $.

@example~ @exam~