Counting Sets by Listing Their Elements
For a finite set, counting its elements means finding a finite list with no repetitions. An infinite set cannot be listed in a finite number of steps, but it may still be possible to list its elements in a sequence indexed by the natural numbers. Countability captures this idea: it says that the set is finite or that its elements can be matched one-to-one with \(\mathbb{N}=\{1,2,3,\dots\}\).
Here, “countable” includes finite sets. Some sources use “countable” to mean only countably infinite; the convention here is to state the distinction explicitly. An enumeration records elements in order, but it is important to check whether the list contains repetitions: infinitely many terms do not by themselves imply that the set being listed is infinite.
Thus, a finite set can be countable without being countably infinite. A repetition-free enumeration of an infinite set gives a bijection with \(\mathbb{N}\). A sequence that lists every element but repeats some terms is still an enumeration, but it is not a bijection. The distinction is between the set of values in the list and the list’s individual positions.
Examples of Enumerations
Worked Example: The Natural Numbers
Show that \(\mathbb{N}\) is countably infinite using an enumeration.
Define \(f:\mathbb{N}\to\mathbb{N}\) by \(f(n)=n\). For every \(m\in\mathbb{N}\), the input \(n=m\) gives \(f(n)=m\), so every natural number occurs. If \(f(n)=f(k)\), then \(n=k\), since \(f(n)=n\) and \(f(k)=k\). Thus \(f\) is both surjective and injective, and therefore bijective. Its first terms are \(f(1)=1\), \(f(2)=2\), and \(f(3)=3\), as required by the formula.
Check: the list \(1,2,3,\dots\) has no repeated values, and its range is exactly \(\mathbb{N}\). Hence it is a repetition-free enumeration, so \(\mathbb{N}\) is countably infinite.
Worked Example: The Positive Even Numbers
Let \(E=\{2,4,6,\dots\}\), the set of positive even natural numbers. Show that \(E\) is countably infinite.
Define \(f:\mathbb{N}\to E\) by \(f(n)=2n\). For \(n=1\), \(f(1)=2\); for \(n=2\), \(f(2)=4\); and for \(n=3\), \(f(3)=6\). In general, \(2n\) is a positive even number, so \(f(n)\in E\). Conversely, each \(m\in E\) has the form \(m=2k\) for some \(k\in\mathbb{N}\), and then \(f(k)=m\). Thus \(f\) is surjective onto \(E\).
If \(f(n)=f(k)\), then \(2n=2k\), and dividing by \(2\) gives \(n=k\). So \(f\) is injective as well. This proves that \(f\) is a bijection from \(\mathbb{N}\) to \(E\), not merely a sequence whose terms happen to be even.
Check: the first three outputs computed from \(f(n)=2n\) are \(2\cdot1=2\), \(2\cdot2=4\), and \(2\cdot3=6\). Every positive even number has exactly one positive half, so each occurs exactly once.
Worked Example: A Finite Set Has a Repeating Enumeration
Let \(A=\{a,b,c\}\), where \(a,b,c\) are distinct. Show that \(A\) is countable but not countably infinite, and give an enumeration of it.
The set is finite, with three elements, so it is countable by definition. To give an enumeration, define a sequence that repeats the three terms in order: \(a_1=a\), \(a_2=b\), \(a_3=c\), \(a_4=a\), \(a_5=b\), \(a_6=c\), and continue with period three. Every member of \(A\) occurs, so the sequence is an enumeration. It is not repetition-free: \(a_1=a_4=a\).
It cannot be countably infinite. Indeed, a bijection from \(\mathbb{N}\) to \(A\) would have to send the four distinct inputs \(1,2,3,4\) to four distinct members of \(A\), but \(A\) has only three members. Therefore \(A\) is countable, but not countably infinite.
Check: the sequence has infinitely many positions, but its range is only \(\{a,b,c\}\). Repetitions do not create new elements of the set.
Worked Example: The Positive Squares
Let \(P=\{n^2:n\in\mathbb{N}\}\). Show that \(P\) is countably infinite.
Define \(f:\mathbb{N}\to P\) by \(f(n)=n^2\). The first three outputs are \(1^2=1\), \(2^2=4\), and \(3^2=9\). By the definition of \(P\), every \(m\in P\) is \(m=k^2\) for some \(k\in\mathbb{N}\), so \(f(k)=m\); hence \(f\) is surjective.
To check injectivity, suppose \(n^2=k^2\) for \(n,k\in\mathbb{N}\). Then \((n-k)(n+k)=0\). Since \(n+k>0\), it follows that \(n-k=0\), so \(n=k\). Thus each positive square occurs at exactly one position, \(f\) is bijective, and \(P\) is countably infinite.
Check: the sequence begins \(1,4,9,\dots\), and every term is a positive square. Conversely, each member of \(P\) is a square \(k^2\) and occurs at position \(k\).
When Can Repetitions Be Removed?
Sometimes a sequence is known only to list every element, and may repeat values. For an infinite set, those repetitions can be removed while keeping a sequence indexed by \(\mathbb{N}\). The idea is to keep only the positions where a value appears for the first time, and then read those positions in increasing order.
Proof. Let \(S\subseteq\mathbb{N}\) consist of the first positions at which values appear: $$ S=\{n\in\mathbb{N}: a(n)\ne a(j)\text{ for every }j<n\}. $$ Every value in the range of \(a\) has a first position, because every nonempty subset of \(\mathbb{N}\) has a least element. Since \(a\) is surjective, every element of \(A\) therefore occurs at some position in \(S\).
The set \(S\) is infinite. If it were finite, the values \(a(n)\) for \(n\in S\) would form a finite set. For any \(m\in\mathbb{N}\), the value \(a(m)\) has a first position \(s\le m\), and that position belongs to \(S\). Thus every value of \(a\) would occur among the finitely many values at positions in \(S\). Surjectivity would then make \(A\) finite, contradicting the assumption that \(A\) is infinite.
List \(S\) in increasing order as \(s_1<s_2<\cdots\): take \(s_1\) to be the least element of \(S\), and after \(s_k\), take \(s_{k+1}\) to be the least element of \(S\) greater than \(s_k\). Such an element exists at every stage because \(S\) is infinite and there are only finitely many natural numbers at most \(s_k\). This increasing list includes every \(s\in S\): there are only finitely many natural numbers at most \(s\), so the process reaches \(s\) after listing the elements of \(S\) that precede it.
Now define \(b(k)=a(s_k)\) for \(k\in\mathbb{N}\). If \(k<\ell\), then \(s_k<s_\ell\), and the defining property of \(s_\ell\) says that \(a(s_\ell)\) differs from every earlier value, including \(a(s_k)\). Thus \(b(k)\ne b(\ell)\), so \(b\) is injective. Every element of \(A\) appears at some first position \(s\in S\), and that position is \(s_k\) for some \(k\). Hence the element equals \(b(k)\), so \(b\) is surjective. Therefore \(b\) is a bijection from \(\mathbb{N}\) to \(A\). \(\square\)
The infinitude assumption matters. A finite set can be the range of a surjective sequence, as the repeating list of \(a,b,c\) shows, but that sequence cannot be changed into a bijection from \(\mathbb{N}\) to the finite set.
Countability in Practice
To show that a set is countably infinite, the direct method is to define a map from \(\mathbb{N}\) to the set and verify two facts: every element is hit, and no two inputs have the same output. These are respectively surjectivity and injectivity. To show that a set is countable, it is also enough to establish that it is finite. An enumeration that repeats values demonstrates that a set is a range of a sequence, but for an infinite set the theorem above explains how to obtain a repetition-free one.
Common pitfall. Consider the sequence \(1,2,1,2,1,2,\dots\), defined by \(a_{2k-1}=1\) and \(a_{2k}=2\) for every \(k\in\mathbb{N}\). It has infinitely many terms, but its range is exactly \(\{1,2\}\). The incorrect conclusion “there are infinitely many terms, so the set is countably infinite” confuses positions with distinct values. The correction is to compute the range: the sequence is surjective onto \(\{1,2\}\), which is finite, and it is not injective because \(a_1=a_3=1\).
| Term | What it says | What to check |
|---|---|---|
| Finite | The set has finitely many elements | A finite list contains every element |
| Countable | The set is finite or countably infinite | Finiteness, or a bijection with \(\mathbb{N}\) |
| Countably infinite | The set is in bijection with \(\mathbb{N}\) | A map from \(\mathbb{N}\) that is both injective and surjective |
| Enumeration | A sequence with the set as its range | Every element occurs; repetitions are allowed |
Check Your Understanding
For each question, distinguish the sequence’s positions from the set of values it lists.
- Give a bijection from \(\mathbb{N}\) to the set \(\{3,6,9,\dots\}\), and verify that it is injective and surjective.
- Explain why a finite set with four elements is countable but not countably infinite.
- Can a sequence be an enumeration of a set while failing to be injective? Give an example and identify its range.
- State the difference between an enumeration and a repetition-free enumeration.
- In the theorem about removing repetitions, where is the assumption that \(A\) is infinite used?