Countability of Rational Numbers as a Union of Finite Sets

Elsewhere countability of the rationals was based on the fact that the union of countably many countable sets is countable. However the enumeration that has been used to establish that result is suggestive of a weaker statement that is still sufficient for proving countability of \(\mathbb{Q}\).

Proposition

The function \(h\) with the property just defined is often called height for the set \(X\). Define \(Y_{1}=X_{1}\) and \(Y_{n}=X_{n}\setminus X_{n-1}\), for \(n\gt 1\). It is obvious that sets \(\{X_n\}\) are finite only if so are sets \(\{Y_n\}\). The above statement could have been formulated in terms of finiteness of the sets \(Y_{n}=h^{-1}(n)=\{x\in X:\space h(x)=n\}\).

The proof of the statement of countability of a countable union of countable sets was implicitly based on the Proposition. Indeed, Let there be countable sets \(A_n=\{a_{n,i}:\space i=1,2,\ldots\},\space n=1,2,\ldots\) Set \(X=\cup_{n=1}A_{n}\) and \(h(a_{n,m})=n+m-1\). Then every \(Y_{n}\) has exactly \(n\) elements and is, therefore, finite, falling into the framework of the above Proposition. The enumeration function

\(\displaystyle f(a_{m, n}) = \frac{(m + n - 1)(m + n - 2)}{2} + m \)

did the counting of each of the sets \(Y_n\) in turn. The counting in the more general Proposition is less regular but still manageable.

Let \(|S|\) denote the number of elements in set \(S\). Note that in the Proposition \(X_{n}=\cup_{i=1}^{n}Y_{n}\). So define, say, \(K_{n}=|X_{n}|\) and let \(Y_{m}=x_{m,1},\ldots,x_{m,|Y_{m}|}\). Set \(h(x_{n+1,k})=K_{n}+k\), \(k=1,\ldots,|Y_{n+1}|\), which will assign the elements of \(K_{n+1}\) the counting sequence starting with \(K_{n}+1\) through \(K_{n+1}=K_{n}+|Y_{n+1}|\).

To show that the set of fractions \(\displaystyle \frac{p}{q},\space p,q\in\mathbb{Z}\) is countable we now simply define \(\displaystyle h(\frac{p}{q})=|p|+|q|\), and the Proposition applies.

Reference

1. V. H. Moll, Numbers and Functions: From a Classical-Experimental Mathematician's Point of View, AMS, 2012, 33-34

Countability of Rational Numbers

• Counting Ordered Pairs
• Countable Times Countable Is Countable
• Countability of Rational Numbers
• Countability of Rational Numbers: PWW
• Countability Principle
• Countability of Rational Numbers via Conitnued Fractions
• Fractions on a Binary Tree II
• Countability of Rational Numbers as a Union of Finite Sets
• A New Proof That the Rationals Are Countable

|Contact| |Front page| |Contents| |Algebra| |Up|

Copyright © 1996-2018 Alexander Bogomolny