RE: An easy proof that rational numbers are countable.
February 22, 2018 at 1:30 pm
(This post was last modified: February 22, 2018 at 1:35 pm by Kernel Sohcahtoa.)
Here's another way to approach the concept that the set of rational numbers is countable. First, here are a few theorems:
Theorem 1: Let A_1, A_2,... be a countable family of countable sets (the index n of this countable family of countable sets is an element of the positive integers; the set of positive integers is the index set). Then the union of all countable sets A_n is a countable set (Johnsonbaugh & Pfaffenberger, 30-31).
Theorem 2: There exists a bijection from the set of positive integers to the set of integers. Therefore, the set of positive integers has the same cardinality as the set of integers, and so, the set of integers is countable (Hammack, 219).
Result to establish: The set Q of rational numbers is countable
Here's a proof from Foundations of Mathematical Analysis by Johnsonbaugh & Pfaffenberger
For each positive integer n, let A_n={...,-2/n,-1/n,0/n,1/n,2/n,...}. Then A_n is countable for each positive integer n. (1) By Theorem 1, the union of all sets A_n, which is equal to Q, is countable.(2) (Johnsonbaugh & Pfaffenberger, 31)
Notes
(1). In our constructed set A_n, notice that if we ignore the n in the denominator of each element, then we have the entire set of integers, and so, putting an n in the denominator of each element will not change the fact that each A_n has the same cardinality as the set of integers. Since the set of integers is countable and each set A_n has the same cardinality as the set of integers, then it follows that each A_n is countable.
(2). Notice that if we took the intersection of any two sets A_n, then the result would be the empty set. Thus, each A_n is a distinct subset of the rational numbers. Hence, taking the union of all sets A_n produces the set of rational numbers.
References
Hammack, Richard (2013). Book of Proof, 2nd ed. Virginia: Richard Hammack.
Johnsonbaugh, R and Pfaffenberger,W.E. (2002). Foundations Of Mathematical Analysis. New York: Dover Publications, INC.
Theorem 1: Let A_1, A_2,... be a countable family of countable sets (the index n of this countable family of countable sets is an element of the positive integers; the set of positive integers is the index set). Then the union of all countable sets A_n is a countable set (Johnsonbaugh & Pfaffenberger, 30-31).
Theorem 2: There exists a bijection from the set of positive integers to the set of integers. Therefore, the set of positive integers has the same cardinality as the set of integers, and so, the set of integers is countable (Hammack, 219).
Result to establish: The set Q of rational numbers is countable
Here's a proof from Foundations of Mathematical Analysis by Johnsonbaugh & Pfaffenberger
For each positive integer n, let A_n={...,-2/n,-1/n,0/n,1/n,2/n,...}. Then A_n is countable for each positive integer n. (1) By Theorem 1, the union of all sets A_n, which is equal to Q, is countable.(2) (Johnsonbaugh & Pfaffenberger, 31)
Notes
(1). In our constructed set A_n, notice that if we ignore the n in the denominator of each element, then we have the entire set of integers, and so, putting an n in the denominator of each element will not change the fact that each A_n has the same cardinality as the set of integers. Since the set of integers is countable and each set A_n has the same cardinality as the set of integers, then it follows that each A_n is countable.
(2). Notice that if we took the intersection of any two sets A_n, then the result would be the empty set. Thus, each A_n is a distinct subset of the rational numbers. Hence, taking the union of all sets A_n produces the set of rational numbers.
References
Hammack, Richard (2013). Book of Proof, 2nd ed. Virginia: Richard Hammack.
Johnsonbaugh, R and Pfaffenberger,W.E. (2002). Foundations Of Mathematical Analysis. New York: Dover Publications, INC.
