Countability Criteria Using Injections

Countability and Injections into \(\mathbb{N}\)

Countability is often introduced by listing the elements of a set. An injection into the natural numbers gives a different way to describe the same size restriction: it assigns distinct natural-number labels to distinct elements. To get a listing from those labels, order the labels and recover the corresponding elements. We will prove that this works for every infinite countable set, while keeping track of the finite case as well.

Throughout, \(\mathbb{N}=\{1,2,3,\dots\}\). A function \(f:S\to\mathbb{N}\) is an injection if \(f(s)=f(t)\) implies \(s=t\). We use the convention that a set is countable if it is finite or countably infinite; it is countably infinite if there is a bijection from \(\mathbb{N}\) to it. An enumeration without repetitions of an infinite set \(S\) is a bijection \(e:\mathbb{N}\to S\).

The key step is to show that an infinite subset of \(\mathbb{N}\) can itself be listed in increasing order. This gives a systematic way to arrange the labels assigned by an injection.

Ordering an Infinite Set of Labels

Proof. Define \(m_1\) to be the least element of \(M\). After \(m_1,\dots,m_k\) have been defined, let \(m_{k+1}\) be the least element of \(M\setminus\{m_1,\dots,m_k\}\). This set is nonempty: if removing finitely many elements from the infinite set \(M\) left nothing, then \(M\) would be finite. Its least element exists by the well-ordering principle for \(\mathbb{N}\). At each step the chosen element is larger than the previous ones, so the sequence is strictly increasing.

It remains to show that every \(m\in M\) occurs. Suppose, to the contrary, that some \(m\in M\) never occurs. At every step, \(m\) remains among the available elements, so the least available element satisfies \(m_k\le m\). The terms \(m_k\) are distinct, which would give infinitely many distinct elements of the finite set \(\{1,2,\dots,m\}\). This is impossible. Thus every element of \(M\) occurs, and the sequence lists \(M\) without repetitions. \(\square\)

The least-element rule matters: it fixes a definite next label at every stage. No arbitrary choices of elements are needed. The proof that nothing is missed uses the fact that only finitely many natural numbers are at most any fixed \(m\).

Proof of the Injection Criterion

Proof of the theorem. First suppose \(S\) is countable. If \(S\) is empty, the empty function from \(S\) to \(\mathbb{N}\) is an injection. If \(S\) is finite and has \(n\ge1\) elements, a bijection from \(S\) to \(\{1,\dots,n\}\) is also an injection into \(\mathbb{N}\). If \(S\) is countably infinite, a bijection from \(S\) to \(\mathbb{N}\) is, in particular, an injection.

Conversely, suppose \(f:S\to\mathbb{N}\) is injective, and let \(M=f(S)\subseteq\mathbb{N}\). If \(M\) is finite, then \(S\) is finite: every element of \(M\) has exactly one preimage in \(S\), by the definition of \(M\) and injectivity. Thus the correspondence \(s\mapsto f(s)\) pairs the elements of \(S\) with the elements of \(M\).

If \(M\) is infinite, apply the lemma to obtain a strictly increasing sequence \((m_k)\) listing all of \(M\). For each \(k\), there is exactly one \(s_k\in S\) such that \(f(s_k)=m_k\): existence follows from \(m_k\in f(S)\), and uniqueness follows from injectivity. Define \(e(k)=s_k\). If \(e(k)=e(j)\), applying \(f\) gives \(m_k=m_j\); since the \(m_k\) are distinct, \(k=j\). Thus \(e\) is injective. Every \(s\in S\) is included because \(f(s)\in M\), so \(f(s)=m_k\) for some \(k\), and uniqueness of the preimage gives \(s=e(k)\). Hence \(e:\mathbb{N}\to S\) is a bijection. This proves that \(S\) is countable and, when \(S\) is infinite, supplies an enumeration without repetitions. \(\square\)

This proof also explains the direction of the construction. The injection assigns a natural-number label to each element. The labels that are actually used form \(M\). Listing \(M\) in increasing order and taking the unique element with each label turns the injection into an enumeration.

Worked Applications

A Common Direction Error

Common pitfall. An injection \(f:S\to\mathbb{N}\) does not take natural numbers as inputs. For example, if \(S=\{x,y,z\}\) and \(f(x)=2\), \(f(y)=5\), \(f(z)=8\), the expression \(f(1)\) is undefined because \(1\) is not an element of the domain \(S\). So one cannot obtain an enumeration by writing \(f(1),f(2),\dots\).

The correction is to use the inverse correspondence on the image \(M=\{2,5,8\}\): the label \(2\) corresponds to \(x\), \(5\) to \(y\), and \(8\) to \(z\). In an infinite case, the lemma orders the image labels, after which the unique element carrying each label is read off. An injection into \(\mathbb{N}\) is therefore enough to produce a listing, but only after the direction of the correspondence is handled correctly.

The criterion is useful because it lets us prove countability by assigning distinct natural-number labels, even when a set is not already presented as a list. The proof supplies more than a size comparison: for an infinite set, it explains precisely how to turn those labels into a repetition-free enumeration. For a finite set, by contrast, an injection still certifies countability, but there is no bijection from \(\mathbb{N}\) to that set.