Rational Numbers are Countably Infinite/Proof 1
Jump to navigation
Jump to search
Theorem
The set $\Q$ of rational numbers is countably infinite.
Proof
The rational numbers are arranged thus:
- $\dfrac 0 1, \dfrac 1 1, \dfrac {-1} 1, \dfrac 1 2, \dfrac {-1} 2, \dfrac 2 1, \dfrac {-2} 1, \dfrac 1 3, \dfrac 2 3, \dfrac {-1} 3, \dfrac {-2} 3, \dfrac 3 1, \dfrac 3 2, \dfrac {-3} 1, \dfrac {-3} 2, \dfrac 1 4, \dfrac 3 4, \dfrac {-1} 4, \dfrac {-3} 4, \dfrac 4 1, \dfrac 4 3, \dfrac {-4} 1, \dfrac {-4} 3 \ldots$
It is clear that every rational number will appear somewhere in this list.
Thus it is possible to set up a bijection between each rational number and its position in the list, which is an element of $\N$.
$\blacksquare$
Sources
- 1964: Steven A. Gaal: Point Set Topology ... (previous) ... (next): Introduction to Set Theory: $2$. Set Theoretical Equivalence and Denumerability
- 1968: A.N. Kolmogorov and S.V. Fomin: Introductory Real Analysis ... (previous) ... (next): $\S 2.2$: Countable sets: Example $4$
- 2008: David Joyner: Adventures in Group Theory (2nd ed.) ... (previous) ... (next): Chapter $2$: 'And you do addition?': $\S 2.1$: Functions: Example $2.1.6$
- 2010: Raymond M. Smullyan and Melvin Fitting: Set Theory and the Continuum Problem (revised ed.) ... (previous) ... (next): Chapter $1$: General Background: $\S 2$ Countable or uncountable?