An Alternating List of Integers
The integers extend without bound in two directions: there are positive integers and negative integers, as well as zero. To show that they can nevertheless be listed using the natural numbers, we need a rule that assigns each index exactly one integer and includes every integer somewhere in the list. Alternating between nonnegative and negative values provides such a rule.
Here \(\mathbb{N}=\{1,2,3,\ldots\}\), and \(\mathbb{Z}\) denotes the integers. An enumeration of a set \(A\) is a sequence indexed by \(\mathbb{N}\) that contains every element of \(A\) exactly once. Equivalently, it is a bijection from \(\mathbb{N}\) onto \(A\). A set is countably infinite if there is a bijection between it and \(\mathbb{N}\).
Consider the list
The first entry is zero; after it, each positive integer \(k\) is paired with the negative integer \(-k\). The list is not in the usual increasing order on \(\mathbb{Z}\). Its purpose is instead to give each integer a definite position.
Every natural number is either \(2k-1\) or \(2k\) for a unique \(k\in\mathbb{N}\), so the two rules specify \(f(n)\) at every index \(n\). The index \(2k-1\) is odd and the index \(2k\) is even; the formula is organized by parity so that it can be checked separately on the two parts of the list.
Reading the Formula and Finding an Index
Worked Example: Computing the First Ten Entries
Use the formula to write out the entries at indices \(1\) through \(10\). For odd indices, write the index as \(2k-1\); for even indices, write it as \(2k\).
At index \(1=2(1)-1\), \(k=1\), so \(f(1)=1-1=0\). At index \(2=2(1)\), \(k=1\), so \(f(2)=-1\). At index \(3=2(2)-1\), \(k=2\), so \(f(3)=2-1=1\). At index \(4=2(2)\), \(k=2\), so \(f(4)=-2\).
Continuing with the same substitutions, index \(5=2(3)-1\) gives \(f(5)=3-1=2\); index \(6=2(3)\) gives \(f(6)=-3\); index \(7=2(4)-1\) gives \(f(7)=4-1=3\); index \(8=2(4)\) gives \(f(8)=-4\); index \(9=2(5)-1\) gives \(f(9)=5-1=4\); and index \(10=2(5)\) gives \(f(10)=-5\).
Conclusion. The first ten entries are \(0,-1,1,-2,2,-3,3,-4,4,-5\). Check: there are five odd indices, producing \(0,1,2,3,4\), and five even indices, producing \(-1,-2,-3,-4,-5\). Each computed entry agrees with the alternating pattern.
The formula can also be reversed: given an integer, determine its position. Zero occurs at index \(1\). If \(m\) is positive, then \(m=k-1\) when \(k=m+1\), so it occurs at the odd index \(2(m+1)-1=2m+1\). If an integer is negative, write it as \(-k\) for a positive integer \(k\); it occurs at the even index \(2k\).
Worked Example: Locating Selected Integers
Find the indices of \(0\), \(6\), and \(-7\), then check each by substituting the index into \(f\).
Zero has index \(1\), and \(f(1)=f(2(1)-1)=1-1=0\).
Since \(6>0\), its index is \(2(6)+1=13\). To check, \(13=2(7)-1\), so \(f(13)=7-1=6\).
Since \(-7<0\), its index is \(-2(-7)=14\). To check, \(14=2(7)\), so \(f(14)=-7\).
Conclusion. The respective indices are \(1\), \(13\), and \(14\). Each substitution returns the original integer, confirming all three locations.
Worked Example: Listing a Symmetric Finite Range
Use the enumeration to list every integer from \(-3\) to \(3\), inclusive, and identify its index. The endpoints are included because the range is specified with \(\le\).
For zero, the index rule gives \(1\). For the positive integers, it gives \(1\mapsto 2(1)+1=3\), \(2\mapsto 2(2)+1=5\), and \(3\mapsto 2(3)+1=7\). For the negative integers, it gives \(-1\mapsto -2(-1)=2\), \(-2\mapsto -2(-2)=4\), and \(-3\mapsto -2(-3)=6\).
In increasing order of index, these values appear as \(0,-1,1,-2,2,-3,3\). Check: the seven indices \(1\) through \(7\) have values \(f(1)=0\), \(f(2)=-1\), \(f(3)=1\), \(f(4)=-2\), \(f(5)=2\), \(f(6)=-3\), and \(f(7)=3\). These are exactly the seven integers satisfying \(-3\le z\le 3\), with no endpoint omitted.
Why the Enumeration Contains Each Integer Exactly Once
A list that appears to cover positive and negative integers is not enough: we must show that it never repeats a value and that it misses no integer. Together, these properties say that \(f\) is a bijection.
Proof. We first prove injectivity. Suppose \(f(n_1)=f(n_2)\), where \(n_1,n_2\in\mathbb{N}\). Each index is odd or even. An odd index has the form \(2k-1\) and its value \(k-1\) is nonnegative, because \(k\ge1\). An even index has the form \(2j\) and its value \(-j\) is negative, because \(j\ge1\). Therefore an odd index and an even index cannot have equal values. The two indices must have the same parity.
If both are odd, write \(n_1=2k-1\) and \(n_2=2j-1\). Equality of their values gives \(k-1=j-1\), hence \(k=j\), and therefore \(n_1=n_2\). If both are even, write \(n_1=2k\) and \(n_2=2j\). Equality gives \(-k=-j\), hence \(k=j\), and again \(n_1=n_2\). Thus \(f\) is injective.
Now let \(z\in\mathbb{Z}\). If \(z\ge0\), set \(k=z+1\), which is a positive integer. Then \(2k-1=2(z+1)-1=2z+1\in\mathbb{N}\), and \(f(2k-1)=k-1=(z+1)-1=z\). If \(z<0\), set \(k=-z\). Since \(z\) is a negative integer, \(k\in\mathbb{N}\), and \(f(2k)=-k=-(-z)=z\). In either case \(z\) is the value of \(f\) at a natural-number index, so \(f\) is surjective. Since \(f\) is both injective and surjective, it is a bijection. \(\square\)
Proof. By the theorem, \(f\) is a bijection from \(\mathbb{N}\) onto \(\mathbb{Z}\). By definition, this makes \(\mathbb{Z}\) countably infinite. \(\square\)
The surjectivity proof explicitly handles zero along with the positive integers in the case \(z\ge0\): when \(z=0\), it uses \(k=1\) and index \(2(1)-1=1\). The negative case uses only negative integers, so its choice \(k=-z\) is always positive. These details prevent zero or a sign case from being lost in the argument.
A Common Off-by-One Error
Common pitfall. A tempting attempt is to define the odd-indexed terms as \(k\) and the even-indexed terms as \(-k\). That gives the proposed rule \(g(2k-1)=k\) and \(g(2k)=-k\) for \(k\in\mathbb{N}\). It does alternate signs, but it does not enumerate all of \(\mathbb{Z}\).
Worked Example: Detecting the Missing Integer
At the first two indices, the incorrect rule gives \(g(1)=g(2(1)-1)=1\) and \(g(2)=g(2(1))=-1\). At the next two indices it gives \(g(3)=g(2(2)-1)=2\) and \(g(4)=g(2(2))=-2\). The pattern continues as \(1,-1,2,-2,\ldots\).
For every odd index \(2k-1\), \(g(2k-1)=k\ge1\); for every even index \(2k\), \(g(2k)=-k\le-1\). Thus every value of \(g\) is nonzero, so zero is missing and \(g\) is not surjective onto \(\mathbb{Z}\).
The correction is to shift the odd-indexed value down by one: use \(f(2k-1)=k-1\) instead. At \(k=1\) this gives \(f(1)=1-1=0\), while the even rule still gives \(f(2)=-1\). The resulting list begins \(0,-1,1,-2,\ldots\), and the bijection proof above verifies that it includes every integer exactly once.
The main point is that countability is established by an exact correspondence, not merely by observing that a pattern continues indefinitely. The odd positions account for every nonnegative integer, including zero, and the even positions account for every negative integer. Injectivity prevents duplication, while surjectivity guarantees that no integer is left out. The same discipline—stating the rule, checking its cases, and proving both properties—is useful whenever a set is claimed to be countably infinite.
Check Your Understanding
Use the stated alternating enumeration and its index rule to answer the questions.
- Compute \(f(11)\) and \(f(12)\) directly from the defining formula.
- What is the index of \(-10\)? Substitute that index into \(f\) to verify your answer.
- Explain why an odd-indexed term can never equal an even-indexed term.
- For the integer \(z=0\), show explicitly which case of the index rule applies and verify the corresponding value of \(f\).
- What integer is omitted by the proposed rule \(g(2k-1)=k,\ g(2k)=-k\), and which part of surjectivity does this invalidate?