The Size of Finity

Previously, we showed that bijections preserve sets in a rather friendly manner. We almost have the necessary groundwork to discuss cardinality.

The idea is that cardinality should match (i.e. be consistent) with our notion of size as “number of items” is a consistent (i.e. well-defined) notion, at least for finite sets.

Lemma 1. For any $n \in \mathbb N$ , if $K \sim [n]$ , then $K \sim [m]$ implies $m = n$ .

Proof. We will prove this result by induction.

Base case: Suppose $n = 0$ . If $K \sim [m]$ , then the transitivity of $\sim$ yields $[m] \sim K \sim \emptyset$ . Let $f : [m] \to \emptyset$ denote a bijection, which must be the empty function $f : \emptyset \to \emptyset$ defined by $f = \emptyset$ . In particular, $[m] = \emptyset$ . Now, if $m \geq 1$ , then $[m]$ contains the element $1$ and thus $m \neq \emptyset$ , a contradiction. This means that $m = 0 = n$ , as required.

Induction step: Fix $n \in \mathbb N$ . Suppose $K \sim [n+1]$ and $K \sim [m]$ . We need to show that $m = n + 1$ . Firstly, $n + 1 \geq 1 > 0$ implies that $m \geq 1$ , otherwise $K = \emptyset$ , a contradiction. Let $f : [n+1] \to K, g : [m] \to K$ be relevant bijections. In particular, there exists $j \in [m]$ such that $g(j) = f(n+1)$ .

Define $K^- := K \backslash \{f(n+1)\} \sim [n]$ and $M := [m] \backslash \{j\}$ . Then $M \sim [m-1]$ via the bijection $h : M \to [m-1]$ defined by

$\displaystyle h(i) := \begin{cases} i & \text{if}\quad 1 \leq i < j, \\ i-1 & \text{if}\quad j < i \leq m. \end{cases}$

By construction and the transitivity of $\sim$ , $K^- \sim M \sim [m-1]$ . By the induction hypothesis, since $K^- \sim [n]$ , we have $n = m-1$ , which simplifies to $m = n+1$ , as required.

Now, we are ready to define cardinality. Define $|[n]| = n$ for any $n \in \mathbb N$ , and $|\mathbb N| = \aleph_0$ , pronounced aleph-naught.

Definition 1. Let $K$ be a countable set. Suppose $K \sim L$ for sets $L$ of the form $[n]$ or $\mathbb N$ . Define the cardinality of $K$ by $|K| = |L|$ .