= Countable set
{wiki}
= Countable
{synonym}
A countable set is a <set> that admits an <injective function> into the <natural numbers>. It is therefore either a <finite set> or a <countably infinite set>.
For a <countably infinite set>, countability means that its members can be arranged as a <sequence> in which every member occurs exactly once. The order need not resemble the order already present in the <set>. For example, the <integers> can be listed as $0,1,-1,2,-2,\ldots$. Simply increasing through positive values would never reach a negative one.
The <Cartesian product> $\mathbb N^2$ needs a similar change of strategy. Listing a whole horizontal row first would never finish that row, so later rows would be missed. Instead list pairs by increasing coordinate sum $x+y$, and within each finite diagonal by increasing $y$:
$$
(0,0),\ (1,0),\ (0,1),\ (2,0),\ (1,1),\ (0,2),\ldots.
$$
Every pair has a finite coordinate sum and therefore appears after finitely many earlier pairs. This is the construction made explicit by the <Cantor pairing function>. It explains why having two infinite coordinates does not, by itself, mean a larger <cardinality>.
\Image[/countable-pair-enumeration.png]
{title=Enumerating natural-number pairs along finite diagonals reaches every point of the infinite grid}
Back to article page
