 Countable set

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,\dots$. 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$: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.

A **countable set** is a set that has the same size (cardinality) as some subset of the set of natural numbers. In more formal terms, a set \( S \) is countable if there exists a bijection (a one-to-one and onto function) between \( S \) and the set of natural numbers \( \mathbb{N} \) or a finite subset of \( \mathbb{N} \).