Countability

A set $𝐴$ is called countable iff it is finite or equinumerous with the Natural numbers $ℕ$ ¹, #m/def/set i.e. $| 𝐴 | \leq | ℕ | = ℵ 0$ . Equivalently, either $𝐴 = \emptyset$ or there exists an enumeration of $𝐴$ , a surjection $𝜋 : ℕ ↠ 𝐴$ of $𝐴$ .

Proof of equivalence

If $𝐴$ has finite size $𝑖$ or equinumerous with the natural numbers, $| 𝐴 | = | ℕ 𝑖 |$ in the first case and $| 𝐴 | = | ℕ |$ in the second case, thus $| 𝐴 | \leq ℵ 0$ .

Assume $| 𝐴 | \leq | ℕ |$ and $𝐴 \neq \emptyset$ , so we may choose $𝑥 0 \in 𝐴$ . Then there exists some injection $𝑓 : 𝐴 ↣ ℕ$ , so we can define

𝜋 (𝑖) = {𝑥 0 𝑖 \notin 𝑓 (𝐴) 𝑓 - 1 (𝑖) 𝑖 \in 𝑓 (𝐴)

Now assume such an enumeration exists. If $𝐴$ is finite we are done, so assume $𝐴$ is infinite but has an enumeration $𝜋 : ℕ ↠ 𝐴$ . We define a new function $𝑓$ by

𝑓 (0) = 𝜋 (0) 𝑚 𝑛 = m i n {𝑚 \in ℕ : 𝜋 (𝑚) \notin {𝑓 (𝑖)} 𝑛 𝑖 = 1} 𝑓 (𝑛 + 1) = 𝜋 (𝑚 𝑛)

which gives a bijection.

#state/develop | #lang/en | #SemBr

2006. Notes on set theory, ¶2.6, p. 8 ↩

Countability

Footnotes