What Must an Enumeration Establish?
A proposed list can look systematic and still fail to enumerate the set it is meant to describe. It might leave out an element, repeat entries while claiming to list each element exactly once, or describe an order that cannot be carried out in a sequence. The right test is not whether a pattern looks plausible: it is whether the entries satisfy the required coverage and distinctness conditions.
This distinction matters. If the aim is only to prove that a set is countable, a sequence that hits every element is enough, even if some terms repeat. If the claim is that every element appears exactly once, then both coverage and distinctness must be checked. Conversely, a list with no repeated terms is not an enumeration of \(A\) if it misses even one element.
Proof. If \((a_n)\) is a one-to-one enumeration, its range is \(A\), so every term belongs to \(A\), every element of \(A\) occurs, and distinct indices give distinct terms. Conversely, conditions (1) and (2) say exactly that the range of the sequence equals \(A\), while condition (3) says that the sequence is one-to-one. Thus the sequence is a bijection from \(\mathbb{N}\) to \(A\). \(\square\)
Check Coverage, Not Just the Pattern
Worked Example: A List That Misses Integers
Consider the proposed list \(0,1,2,3,\dots\), claimed to enumerate \(\mathbb{Z}\). The rule for its terms is \(a_n=n-1\) for \(n\in\mathbb{N}\). For example, \(a_1=1-1=0\), \(a_2=2-1=1\), and \(a_3=3-1=2\). In general, \(a_n=n-1\ge 0\), so every term is nonnegative. But \(-1\in\mathbb{Z}\), and there is no \(n\in\mathbb{N}\) with \(n-1=-1\), since that equation would require \(n=0\). The list therefore does not enumerate \(\mathbb{Z}\).
A familiar correct list is \(0,1,-1,2,-2,3,-3,\dots\). To check its pattern rather than rely on its appearance, set \(a_1=0\), \(a_{2k}=k\), and \(a_{2k+1}=-k\) for \(k\in\mathbb{N}\). Every integer is either \(0\), a positive integer \(k\), or the negative integer \(-k\), so every integer occurs. The terms are distinct: zero occurs only at index \(1\); positive values occur at even indices; negative values occur at odd indices greater than \(1\); and within each of those two groups different \(k\)'s give different values.
Check: \(a_1=0\), \(a_2=1\), \(a_3=-1\), \(a_4=2\), and \(a_5=-2\), by substituting into the formulas. In particular, the earlier list \(0,1,2,\dots\) cannot be repaired merely by saying it “continues”; its stated rule never produces a negative integer.
When testing an omission, it is enough to identify one target element and prove that no index produces it. When testing coverage in a complicated list, the useful question is the reverse: given an arbitrary target element, can an index be found by a specified rule? A finite sample of entries can suggest the rule, but it cannot prove coverage of an infinite set.
Infinite Rows Need a Schedule
Worked Example: Why “Finish One Infinite Row First” Fails
Suppose someone proposes to list \(\mathbb{N}\times\mathbb{N}\) by writing every pair in the first row, then every pair in the second row, and so on: first \((1,1),(1,2),(1,3),\dots\), then \((2,1),(2,2),\dots\). This describes an order of rows, but it does not define a sequence that reaches the second row after a finite number of terms.
Indeed, if \((2,1)\) appeared at index \(N\), then all pairs \((1,j)\) would have to appear before index \(N\), because the rule says the first row is listed completely first. But the first \(N-1\) positions cannot contain all of the distinct pairs \((1,1),\dots,(1,N)\). There are \(N\) such pairs and only \(N-1\) earlier positions. This contradicts the claim that \((2,1)\) occurs at index \(N\). So no finite index can reach \((2,1)\) under the proposed rule.
A valid schedule uses diagonals of constant coordinate sum. For each \(s\ge 2\), list the pairs \((i,j)\) with \(i+j=s\), in increasing order of \(i\). The beginning is \((1,1)\) for \(s=2\); then \((1,2),(2,1)\) for \(s=3\); then \((1,3),(2,2),(3,1)\) for \(s=4\). Each diagonal is finite, so it can be completed before the next one begins.
Check: The pair \((2,3)\) has coordinate sum \(2+3=5\). The earlier diagonals contain \(1+2+3=6\) pairs, and on the sum-\(5\) diagonal it is second, after \((1,4)\). Thus this schedule places \((2,3)\) at position \(6+2=8\). Every pair \((i,j)\in\mathbb{N}\times\mathbb{N}\) occurs: it lies on the diagonal \(s=i+j\), and within that finite diagonal it has a definite position.
The same error can appear in lists of fractions: one might say “list all denominators for numerator \(1\), then all denominators for numerator \(2\), and continue.” If each row is infinite, the instructions never advance past the first row. A valid enumeration needs a rule that assigns every target a finite position, not just an informal promise to move on eventually.
Repeated Fractions: Harmless for Coverage, Not for Uniqueness
Worked Example: A Diagonal List of Positive Rationals
Consider listing \(p/q\) for positive integers \(p,q\), by increasing \(p+q\), and within each diagonal by increasing \(p\). The first few unreduced fractions are \(1/1\); then \(1/2,2/1\); then \(1/3,2/2,3/1\); then \(1/4,2/3,3/2,4/1\). The entry \(2/2\) repeats the value \(1/1\), because \(2/2=1\). Thus this is not a one-to-one enumeration by fraction values.
Repetition does not by itself prevent the list from enumerating the positive rationals. If \(r\) is any positive rational, write \(r=p/q\) with positive integers \(p,q\). The pair \((p,q)\) lies on the finite diagonal with sum \(p+q\), so its fraction occurs. The list covers all positive rationals, although it repeats some of them.
To obtain a one-to-one enumeration, retain only fractions \(p/q\) with \(\gcd(p,q)=1\), where \(\gcd(p,q)\) is the greatest common divisor of \(p\) and \(q\). The first diagonals then give \(1\); \(1/2,2\); \(1/3,3\); and \(1/4,2/3,3/2,4\). The middle entry \(2/2\) on the sum-\(4\) diagonal is removed because \(\gcd(2,2)=2\), not \(1\).
Every positive rational has a reduced representation \(p/q\) with \(\gcd(p,q)=1\), so this rule still covers all positive rationals. It also produces no repeated values. To verify the latter claim, suppose reduced positive fractions \(p/q\) and \(r/s\) are equal. Then \(ps=rq\). Since \(\gcd(p,q)=1\), there are integers \(u,v\) with \(up+vq=1\). Multiplying by \(r\) gives \(upr+vqr=r\). Both terms on the left are divisible by \(p\): the first is visibly divisible by \(p\), and \(qr=ps\) makes the second divisible by \(p\). Hence \(p\) divides \(r\). Reversing the roles of the two fractions shows \(r\) divides \(p\), so \(p=r\); the equality \(ps=rq\) then gives \(q=s\).
Check: On the sum-\(5\) diagonal, \(1/4,2/3,3/2,4/1\) are all retained because each numerator-denominator pair has greatest common divisor \(1\). The removed fraction \(2/2\) has value \(1\), which was already listed on the sum-\(2\) diagonal. Thus the removal rule removes that duplicate without losing its value from the list.
This example illustrates two different claims that should not be confused. The unreduced list is a valid enumeration in the sense of coverage, but it is not one-to-one. The reduced list is one-to-one because each positive rational has a unique reduced representation and each such representation is assigned to exactly one finite diagonal.
A Decimal Pattern Can Omit Rationals
Worked Example: Finite Decimal Expansions Do Not List All Rationals
A proposed list might claim to contain every rational by listing only numbers with terminating decimal expansions. Each such number has the form \(m/10^k\) for some integer \(m\) and some integer \(k\ge 0\). But \(1/3\) cannot have this form. If \(1/3=m/10^k\), then cross-multiplication gives \(10^k=3m\), so \(3\) would divide \(10^k\). This is impossible: \(10\) has remainder \(1\) upon division by \(3\), and therefore \(10^k\) also has remainder \(1\) upon division by \(3\) for every \(k\ge0\).
For example, \(10^0=1\), \(10^1=10\), and \(10^2=100\) each have remainder \(1\) upon division by \(3\); multiplying a number with remainder \(1\) by \(10\), which also has remainder \(1\), preserves that remainder. Hence \(1/3\in\mathbb{Q}\) is omitted by the proposed list. Having a rule that generates many rational numbers does not establish that it generates all of them.
Check: The contradiction does not depend on a decimal approximation to \(1/3\). It follows directly from the exact equation \(10^k=3m\), which cannot hold for any integer \(k\ge0\) and integer \(m\).
A Reliable Audit for Proposed Lists
Before accepting an enumeration, identify exactly what is being claimed. If the claim is only that a set is countable, repetitions are allowed, but every element must occur. If the claim is that the sequence is a bijection, every element must occur exactly once. Then test the proposed rule at three levels:
- Membership: Does every term belong to the claimed set?
- Coverage: Given an arbitrary element of the set, can the rule produce it at a finite index?
- Uniqueness: If the list is claimed to be one-to-one, can two different indices produce the same element?
Common pitfall. A frequent incorrect argument is: “The fractions \(1/1,1/2,1/3,\dots\) occur, and the same pattern works for every numerator, so the list contains every positive rational.” The listed row for numerator \(1\) contains \(1/q\), not an arbitrary \(p/q\). For instance, \(2/3\) does not equal \(1/q\) for any positive integer \(q\), since \(1/q=2/3\) would imply \(3=2q\), which has no integer solution. The correction is to specify a schedule that reaches every numerator-denominator pair at a finite position, such as the diagonal schedule, and then prove coverage from an arbitrary pair.
These checks separate genuine enumerations from patterns that merely look comprehensive. They also prevent the opposite mistake: rejecting a valid countability argument solely because its sequence contains duplicates. Coverage proves enumeration; distinctness is an additional requirement only when a one-to-one listing is claimed.
Check Your Understanding
For each proposed list, identify whether the issue is coverage, repetition, or an ordering that cannot reach a later row.
- Does the sequence \(2,4,6,8,\dots\) enumerate the positive integers? Give one omitted element and show why no term equals it.
- Does listing all positive fractions \(p/q\) by increasing \(p+q\), without reducing them, enumerate the positive rationals? Is it one-to-one?
- Why can a rule that lists every pair in row \(1\) before beginning row \(2\) fail to define a sequence when each row is infinite?
- Can every terminating decimal be written as \(m/10^k\) for integers \(m\) and \(k\ge0\)? Does that show that every rational has a terminating decimal expansion?
- State separately the conditions needed for a sequence to enumerate a set and for it to be a one-to-one enumeration.