Why Finite Tuples Need a Single Code
A set of tuples can have many coordinates, but to prove it countable we need to assign each tuple a distinct natural-number code. Encoding each coordinate separately is not enough: the full tuple needs one code that preserves all its information. A pairing function provides a way to combine two natural-number codes into one, and repeating that construction handles any fixed finite number of coordinates.
We use \(\mathbb{N}=\{1,2,\dots\}\). A set is countable if it is finite or countably infinite; equivalently, it admits an injection into \(\mathbb{N}\). The equivalence of these criteria is part of the earlier material on countability criteria. In particular, the empty set is countable: its unique function to \(\mathbb{N}\) is injective.
The pairing construction combines two positive integers. Its diagonal ordering matters: it lists pairs with fixed coordinate sum in successive finite blocks. We recall its formula and verify the properties needed here.
Proof. Put \(r=m+n-2\), so \(r\) is a nonnegative integer and \(m\) ranges from \(1\) to \(r+1\) on the diagonal with this value of \(r\). Write \(T_r=r(r+1)/2\). The formula becomes \(p(m,n)=T_r+m\). Thus, as \(m\) runs from \(1\) to \(r+1\), the codes on this diagonal are precisely \(T_r+1,\dots,T_r+r+1\), which is the block \(T_r+1,\dots,T_{r+1}\). These blocks are disjoint consecutive blocks, since \(T_{r+1}=T_r+r+1\), and they cover \(\mathbb{N}\): their endpoints increase without bound because \(T_r=r(r+1)/2\). Therefore each positive integer belongs to exactly one block. If \(q\) belongs to the block for \(r\), then \(m=q-T_r\) is uniquely determined and satisfies \(1\le m\le r+1\); setting \(n=r+2-m\) gives a positive integer and the unique pair with code \(q\). So \(p\) is both onto and one-to-one. \(\square\)
Iterating the Pairing Construction
Suppose each coordinate set has an injection into \(\mathbb{N}\). First encode each coordinate separately, and then combine those codes two at a time. For one coordinate there is nothing to pair; this case must be kept distinct from the recursive step.
Proof. Since each \(A_i\) is countable, choose an injection \(e_i:A_i\to\mathbb{N}\). If any \(A_i\) is empty, then the product is empty, hence countable. Otherwise the following construction applies directly; it also defines an injection when a factor is empty, since in that case there are no tuples to test.
For a tuple \((a_1,\dots,a_k)\), define codes recursively. Set \(c_1=e_1(a_1)\). For each integer \(j\) with \(2\le j\le k\), set \(c_j=p(c_{j-1},e_j(a_j))\). The final code is \(c_k\). When \(k=1\), this final-code function is \(e_1\), which is injective.
Now suppose \(k\ge2\) and two \(k\)-tuples have the same final code. Since \(p\) is injective, equality of their \(c_k\) codes implies equality of their \(c_{k-1}\) codes and equality of their \(e_k\) codes. Injectivity of \(e_k\) gives equality of their last coordinates. Repeating this argument for the \(c_{k-1}\) codes, down to the first pairing, gives equality of the codes \(e_i(a_i)\) in every coordinate. Since each \(e_i\) is injective, the coordinates themselves are equal, so the tuples are equal. Thus the final-code function is an injection from the product into \(\mathbb{N}\), proving that the product is countable. Finally, the zero-factor product is a singleton, and a singleton injects into \(\mathbb{N}\), so it too is countable. \(\square\)
The construction is an iteration of a two-coordinate encoding, not a claim that a tuple can be identified with a single coordinate at every stage. At stage \(j\), the code \(c_j\) retains the information in the first \(j\) coordinates; pairing it with the code for coordinate \(j+1\) adds that coordinate without losing injectivity.
Worked Example: Coding a Triple of Natural Numbers
Use the recursive code to encode \((2,1,3)\in\mathbb{N}^3\). For the first two coordinates, \(c_1=2\), and \(c_2=p(2,1)=\frac{(2+1-2)(2+1-1)}{2}+2=\frac{1\cdot2}{2}+2=3\).
Now pair this code with the third coordinate: \(c_3=p(3,3)=\frac{(3+3-2)(3+3-1)}{2}+3=\frac{4\cdot5}{2}+3=13\). So the triple’s code is \(13\).
Check: The sum of the two inputs to the final pairing is \(3+3=6\), so \(r=6-2=4\) and \(T_4=4\cdot5/2=10\). The code is \(T_4+3=10+3=13\), as computed. The pairing bijection recovers the pair of codes \((3,3)\); the earlier pairing \(p(2,1)=3\) then recovers the first two coordinates.
Worked Example: Coding an Integer Tuple
To use the construction for integers, first assign each integer a positive-integer code. Define \(e:\mathbb{Z}\to\mathbb{N}\) by \(e(0)=1\), \(e(n)=2n\) for \(n\ge1\), and \(e(-n)=2n+1\) for \(n\ge1\). The code for zero is \(1\), positive integers have even codes at least \(2\), and negative integers have odd codes at least \(3\); these disjoint cases show that \(e\) is injective.
Encode \((-2,0,3)\in\mathbb{Z}^3\). The coordinate codes are \(e(-2)=2\cdot2+1=5\), \(e(0)=1\), and \(e(3)=2\cdot3=6\). Pair the first two: \(c_2=p(5,1)=\frac{(5+1-2)(5+1-1)}{2}+5=\frac{4\cdot5}{2}+5=15\).
Pair this result with the final coordinate code: \(c_3=p(15,6)=\frac{(15+6-2)(15+6-1)}{2}+15=\frac{19\cdot20}{2}+15=205\). Thus the tuple’s code is \(205\).
Check: Since \(T_{19}=19\cdot20/2=190\), the number \(205\) lies in the block \(T_{19}+1,\dots,T_{20}\), and its first coordinate code is \(205-190=15\). The second is \(19+2-15=6\). Decoding \(15\) by the same pairing construction gives \((5,1)\). Finally, \(5=e(-2)\), \(1=e(0)\), and \(6=e(3)\), recovering \((-2,0,3)\).
Worked Example: A Finite Set Times \(\mathbb{N}\)
Let \(A=\{a,b,c\}\) and assign the codes \(e_A(a)=1\), \(e_A(b)=2\), and \(e_A(c)=3\). Use the identity code \(e_{\mathbb{N}}(n)=n\) for \(\mathbb{N}\). The product \(A\times\mathbb{N}\) receives the code \(p(e_A(x),n)\) for \((x,n)\).
For \(n=1\), the three codes are \(p(1,1)=1\), \(p(2,1)=3\), and \(p(3,1)=6\). For \(n=2\), they are \(p(1,2)=2\), \(p(2,2)=5\), and \(p(3,2)=9\). For example, \(p(2,2)=T_2+2=3+2=5\), while \(p(3,2)=T_3+3=6+3=9\).
Check: The six displayed codes \(1,3,6,2,5,9\) are distinct. More generally, if two pairs in \(A\times\mathbb{N}\) have the same code, injectivity of \(p\) gives equality of their label codes and their natural-number coordinates; the distinct labels \(1,2,3\) then give equality of the elements of \(A\). This example illustrates why only finitely many labels are needed—the pairing function still encodes every \(n\in\mathbb{N}\).
A Common Coding Mistake
Common pitfall. Adding coordinate codes does not generally encode a pair injectively. For instance, the incorrect proposed code \(s(m,n)=m+n\) gives \(s(1,2)=1+2=3\) and \(s(2,1)=2+1=3\). The distinct pairs \((1,2)\) and \((2,1)\) therefore receive the same code. The correction is to use the pairing function \(p\), whose diagonal blocks assign each pair a unique number. When extending the method to tuples, also keep the one-coordinate case separate: its code is \(e_1\), not a result of applying \(p\).
Finite products occur whenever an object is specified by a fixed finite list of countable choices. For example, integer-coordinate points in any fixed finite dimension form a countable set by the theorem and the explicit integer coding above. The number of coordinates must be fixed and finite in this argument: the recursion ends after finitely many pairings, producing one natural-number code. This result concerns products; counting a union of infinitely many countable sets requires a separate argument.
Check Your Understanding
Use the pairing formula and the recursive construction to answer the following questions.
- Compute the code of \((1,2,1)\in\mathbb{N}^3\), pairing from left to right.
- Why does the proof of injectivity treat \(k=1\) separately from \(k\ge2\)?
- For countable sets \(A_1,A_2,A_3,A_4\), describe the code construction for a tuple \((a_1,a_2,a_3,a_4)\).
- What does the finite-product theorem say when one of the factors is empty?
- Find two distinct pairs that receive the same value under \(s(m,n)=m+n\), and explain why that prevents \(s\) from serving as the pairing function.