Notes - Set Theory HT25, Cardinalities

There exists a bijection $X \to Y$.

\[|X| := \\{Y : Y \sim X\\}\]

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 $.

$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:
  • $\mathcal D := \{A \subseteq X : A \subseteq H(A)\}$
  • $C := \bigcup \mathcal D$

Let $\mathcal D := \{A \subseteq X : A \subseteq H(A)\}$ and $C := \bigcup D$. Then:

$C \subseteq H(C)$: Pick some $c \in C$. Then $c \in A \in \mathcal 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$.

For this proof, we use the notation $A^\mathsf c := X \setminus A$ and $D^{\mathsf c’} := Y \setminus D$ and that $f[\cdot]$ denotes the extension of $f$ map sets rather than elements.

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

\[\begin{aligned} H(A) &:= g[f[A]^{\mathsf c'}]^{\mathcal c} \\\\ &(:= 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 f[A]^{\mathsf c'} \supseteq f[B]^{\mathsf c'} \\\\ &\implies g[f[A]^{\mathsf c'}] \supseteq g[f[B]^{\mathcal c'}] \\\\ &\implies H(A) = g[f[A]^{\mathsf c'}] \supseteq g[f[B]^{\mathcal c'}] = H[B] \end{aligned}\]

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

\[A^{\mathsf c} = H(A)^{\mathsf c} = g[f[A]^{\mathsf c'}]\]

Hence we have bijections

\[\begin{aligned} f|_A &: A \to f[A] \\\\ g|_{f[A]^{\mathsf c'} } &: f[A]^{\mathsf c'} \to A^{\mathsf c} \end{aligned}\]

and hence putting them together $f \vert _ A \cup (g \vert _ {f[A]^{\mathsf c’}})^{-1} : X \to Y$.

@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.

\[\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

$ \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$: Suppose that $ \vert X \vert \le \aleph _ 0$ and $X$ infinite, we will show that $ \vert X \vert = \aleph _ 0$.

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 \{n \in \mathbb N : f(n) = x\}$ 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 \{0\}$ and $Y \times \{1\}$, 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.

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

\[D := \\{x \in X : x \notin f(x)\\} \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.

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

Then $x \mapsto \{x\}$ 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 := \\{x \in X : x \notin f(x)\\} \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.

$\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)$.

$ \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$.

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

\[\begin{aligned} \mathbb R &\to \mathcal P(\mathbb Q) \\\\ x &\mapsto \\{q \in \mathbb Q : q < x\\} \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 $.

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

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).

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.

$\bigcup K$ is an ordinal by the result that says the union of ordinals is an ordinal. Suppose that $ \vert \bigcup K \vert \in \bigcup K$. Then $ \vert \bigcup K \vert \in \kappa$ for some $\kappa \in K$, so $ \vert \bigcup K \vert < \vert \kappa \vert $ since $\kappa$ is a cardinal, which contradicts $\kappa \subseteq \bigcup K$. 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

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

\[\alpha := \\{\beta : \aleph_\beta < \kappa\\} = \\{\beta \in \kappa : \aleph_\beta < \kappa\\}\]

where the equality follows from the result that $\aleph _ \alpha \ge \alpha$ for all $\alpha \in \mathbf{ON}$.

Then $\alpha$ is an initial segment of $\kappa$, by the result that says if $\alpha < \beta \in \mathbf{ON}$, then $\aleph _ \alpha < \aleph _ \beta$. Hence $\alpha$ is an ordinal.

Then $\alpha \not\in \alpha$, hence $\aleph _ \alpha \ge \kappa$. We conclude by showing that $\aleph _ \alpha \le \kappa$.

• If $\alpha = 0$, this follows from $\kappa$ being infinite.
• If $\alpha$ is a limit ordinal, then $\aleph _ \alpha = \bigcup _ {\beta \in \alpha} \aleph _ \beta \le \kappa$, since each $\aleph _ \beta < \kappa$.
• 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^+}$.

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.

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

This is ambiguous because these definitions don’t agree with ordinal arithmetic operations (which were defined with product and sum 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.

Let $\kappa, \lambda$ be cardinals. Then

1. $\kappa \cdot \kappa = \kappa$
2. If $\lambda$ is a cardinal and $1 \le \lambda \le \kappa$, then $\kappa + \lambda = \kappa = \kappa \cdot \lambda$.
3. If $\lambda$ is an infinite cardinal, then $\kappa + \lambda = \max(\kappa, \lambda) = \kappa \cdot \lambda$.

(1):

We proceed by transfinite induction. Assume

\[|\alpha| \cdot |\alpha| = |\alpha|\]

for all infinite ordinals $\alpha < \kappa$. Then

\[|\alpha| \cdot |\alpha| < \kappa \quad (\ast)\]

for all $\alpha < \kappa$ for finite $\alpha$, since $ \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$ (which holds if $\delta$ is finite since $\kappa$ is infinite, and if $\delta$ is infinite then $ \vert \delta^+ \vert = \vert \delta \vert < \kappa)$, so by $(\ast)$, $ \vert S \vert \le \vert \delta^+ \vert \cdot \vert \delta^+ \vert < \kappa$. Hence $\gamma \le \kappa$, since otherwise $\gamma$ would have a proper initial segment $\gamma _ {<\kappa}$ of cardinality $\kappa$.

Therefore $\kappa \cdot \kappa \le \kappa$.

Conversely, $\kappa = \vert \kappa \cdot \{ 0 \} \vert \le \kappa \cdot \kappa$. So $\kappa \cdot \kappa = \kappa$.

(2):

Since ordinal addition is monotonic, by part (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(\\{x \in X : f(x) = y\\})\]

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$).

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 \{I _ a : a \in X\}$ and let $f _ a := h(I _ a)$.

Let $g : X \to \kappa$ be an injection. Then $Z := \{\langle g(a), f _ a(x) \rangle : x \in a \in X\}$ 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$.