title: "Countable"

Countable

Definition. A set is countable if it is finite or its elements can be arranged in a single infinite list $s_1, s_2, s_3, \ldots$ in which every element appears at some finite position.

The burden in a countability proof is the finite position: you must be able to point at an arbitrary element and say where it shows up. When the natural ordering fails, reorder, often by Dovetailing. Equivalently, an infinite set is countable when it admits a Bijection with the positive integers (Lecture 2, Example 13). Defined in Lecture 2; contrast Uncountable.