Countable Set

A countable set is a set whose elements can be assigned distinct natural numbers. Under the inclusive convention, this means that the set is either finite or countably infinite. A countably infinite set admits a one-to-one correspondence with $\mathbb N$, so its elements can be listed without omission or repetition. Countability is a fundamental concept in set theory: it distinguishes the smallest infinite size from larger infinities, including that of the real numbers. Some authors use “countable” exclusively for countably infinite sets and “at most countable” for the inclusive meaning. (web.stanford.edu)

Definition and equivalent characterizations

Let $\mathbb N=\{0,1,2,\ldots\}$. A set $A$ is countable if there exists an injective function

Injectivity ensures that different elements receive different labels. The empty set satisfies this definition, as does every finite set. If $A$ is infinite, countability is equivalent to the existence of a bijection between $A$ and $\mathbb N$: every element then has exactly one index, and every index identifies exactly one element. (web.stanford.edu)

For a nonempty set $A$, another equivalent condition is the existence of a surjective function $g:\mathbb N\to A$. Such a listing may repeat elements; an infinite listing can be made repetition-free by retaining each element’s first occurrence. In terms of cardinality, countability is written

where aleph-null is the cardinality of $\mathbb N$. Equality holds precisely when $A$ is countably infinite. These conditions concern the existence of a function, not necessarily an effective procedure for computing it. (web.stanford.edu)

Examples and enumeration methods

The even natural numbers are countably infinite because $n\mapsto 2n$ is a bijection onto them. Thus an infinite set can have the same cardinality as a proper subset. The integers are also countably infinite, as demonstrated by the listing

Their extension in both positive and negative directions does not produce a larger infinite cardinality. (web.stanford.edu)

The rational numbers provide a less immediate example. Every rational number has a representation $p/q$, with $p\in\mathbb Z$ and positive integer $q$. List these pairs in successive finite groups according to $|p|+q$, then omit fractions representing values already listed. Every rational number appears after finitely many groups, proving that $\mathbb Q$ is countably infinite. This construction illustrates why completing one infinite row of fractions before beginning another would fail: a valid enumeration must eventually reach every entry. (web.stanford.edu)

Closure properties

Several operations preserve countability:

• Every subset of a countable set is countable.
• The image of a countable set under any function is countable.
• A finite Cartesian product of countable sets is countable.
• In the usual set-theoretic framework with choice, a countable union of countable sets is countable. (web.stanford.edu)

For the product $\mathbb N\times\mathbb N$, list pairs $(i,j)$ by increasing $i+j$. Each diagonal contains finitely many pairs, and every pair belongs to one diagonal. Applying this construction repeatedly handles products with any fixed finite number of factors. Similarly, if $A_n$ has a listing $a_{n,0},a_{n,1},\ldots$, diagonal traversal of the indices $(n,k)$ lists the union; repetitions can be discarded. (math.mit.edu)

There is a foundational qualification to the union theorem. Knowing that each set admits an enumeration does not automatically provide a simultaneous selection of enumerations in set theory without choice. The axiom of choice supplies such selections, whereas the general countable-union theorem is not provable in Zermelo–Fraenkel set theory alone. When the enumerations are already supplied, diagonal traversal requires no additional selection. (people.math.osu.edu)

Uncountability and diagonal arguments

A set that is not countable is an uncountable set. An important example is the collection $\{0,1\}^{\mathbb N}$ of all infinite binary sequences. Suppose these sequences could be listed as $s_0,s_1,s_2,\ldots$. Define a new sequence by

For every $n$, the sequence $t$ differs from $s_n$ at position $n$, so it cannot occur anywhere in the proposed list. This diagonal argument proves that no listing exhausts the collection. (math.mit.edu)

Binary sequences correspond to subsets of $\mathbb N$ through their membership indicators. Consequently, the power set $\mathcal P(\mathbb N)$ is uncountable. A related diagonal proof establishes that the real numbers are uncountable. Finite products of countable sets therefore behave differently from infinite products: even an infinite product of two-element sets can be uncountable. (theory.stanford.edu)

Significance in analysis and computation

In analysis and topology, countability is distinct from geometric density. The rationals form a dense subset of the real line, meeting every nonempty open interval, despite being countable. A metric space possessing a countable dense subset is called separable. The entire space need not itself be countable. (math.mit.edu)

In measure theory, every countable subset of $\mathbb R$ has Lebesgue measure zero. Covering its successive points by intervals with arbitrarily small total length proves this property. Thus density and measure describe different features: the rationals are dense but have measure zero. (ocw.mit.edu)

In computer science, finite strings over a finite alphabet are countable: list them by length, then in a fixed order within each length. Programs with finite descriptions are therefore countable. This does not equate countability with computability; a set-theoretic listing need not be generated by an algorithm. (theory.stanford.edu)