Our server costs ~$56 per month to run. Please consider donating or becoming a Patron to help keep the site running. Help us gain new members by following us on Twitter and liking our page on Facebook!
Current time: August 8, 2022, 11:52 am

Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
An easy proof that rational numbers are countable.
#1
An easy proof that rational numbers are countable.
It's very counter intuitive that one could be able to "count" the set of rational numbers (those numbers that are quotient of two integers, say a/b), because such is an infinite set, but here's the proof:

[Image: rationals-countable.gif]



Quote:A set is countable if you can count its elements. Of course if the set is finite, you can easily count its elements. If the set is infinite, being countable means that you are able to put the elements of the set in order just like natural numbers are in order. Yet in other words, it means you are able to put the elements of the set into a "standing line" where each one has a "waiting number", but the "line" is allowed to continue to infinity.

In mathematical terms, a set is countable either if it s finite, or it is infinite and you can find a one-to-one correspondence between the elements of the set and the set of natural numbers. Notice, the infinite case is the same as giving the elements of the set a waiting number in an infinite line Smile.


https://www.homeschoolmath.net/teaching/...ntable.php
And without delay Peter went quickly out of the synagogue (assembly) and went unto the house of Marcellus, where Simon lodged: and much people followed him...And Peter turned unto the people that followed him and said: Ye shall now see a great and marvellous wonder. And Peter seeing a great dog bound with a strong chain, went to him and loosed him, and when he was loosed the dog received a man's voice and said unto Peter: What dost thou bid me to do, thou servant of the unspeakable and living God? Peter said unto him: Go in and say unto Simon in the midst of his company: Peter saith unto thee, Come forth abroad, for thy sake am I come to Rome, thou wicked one and deceiver of simple souls. And immediately the dog ran and entered in, and rushed into the midst of them that were with Simon, and lifted up his forefeet and in a loud voice said: Thou Simon, Peter the servant of Christ who standeth at the door saith unto thee: Come forth abroad, for thy sake am I come to Rome, thou most wicked one and deceiver of simple souls. And when Simon heard it, and beheld the incredible sight, he lost the words wherewith he was deceiving them that stood by, and all of them were amazed. (The Acts of Peter, 9)
Reply
#2
RE: An easy proof that rational numbers are countable.
(February 22, 2018 at 3:57 am)Jehanne Wrote: It's very counter intuitive that one could be able to "count" the set of rational numbers (those numbers that are quotient of two integers, say a/b), because such is an infinite set, but here's the proof:

[Image: rationals-countable.gif]



Quote:A set is countable if you can count its elements. Of course if the set is finite, you can easily count its elements. If the set is infinite, being countable means that you are able to put the elements of the set in order just like natural numbers are in order. Yet in other words, it means you are able to put the elements of the set into a "standing line" where each one has a "waiting number", but the "line" is allowed to continue to infinity.

In mathematical terms, a set is countable either if it s finite, or it is infinite and you can find a one-to-one correspondence between the elements of the set and the set of natural numbers. Notice, the infinite case is the same as giving the elements of the set a waiting number in an infinite line Smile.


https://www.homeschoolmath.net/teaching/...ntable.php

While this is a function that is onto the *positive* rational numbers, it is NOT a one-to-one function. So for example, 4/1=8/2=12/3. In fact each postitive rational number is hit infinitely often by this counting method.

Since the definition requires a function that is BOTH onto and one-to-one, this doesn't give the result (at least not directly).

There *is* a result that takes an onto function from the natural numbers to an infinite set and gives a one-to-one onto function. But the argument needs to be made for this.
Reply
#3
RE: An easy proof that rational numbers are countable.
I don't think I'll be getting there with 1 potato, 2...........
I don't have an anger problem, I have an idiot problem




Reply
#4
RE: An easy proof that rational numbers are countable.
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.











Reply
#5
RE: An easy proof that rational numbers are countable.
The proof/technique in my OP is also in Rosen, Discrete Mathematics, 7th edition.

Point of my thread is that there are things that are counterintuitive, yet provably true! These are sometimes referred to as "veridical paradoxes".
And without delay Peter went quickly out of the synagogue (assembly) and went unto the house of Marcellus, where Simon lodged: and much people followed him...And Peter turned unto the people that followed him and said: Ye shall now see a great and marvellous wonder. And Peter seeing a great dog bound with a strong chain, went to him and loosed him, and when he was loosed the dog received a man's voice and said unto Peter: What dost thou bid me to do, thou servant of the unspeakable and living God? Peter said unto him: Go in and say unto Simon in the midst of his company: Peter saith unto thee, Come forth abroad, for thy sake am I come to Rome, thou wicked one and deceiver of simple souls. And immediately the dog ran and entered in, and rushed into the midst of them that were with Simon, and lifted up his forefeet and in a loud voice said: Thou Simon, Peter the servant of Christ who standeth at the door saith unto thee: Come forth abroad, for thy sake am I come to Rome, thou most wicked one and deceiver of simple souls. And when Simon heard it, and beheld the incredible sight, he lost the words wherewith he was deceiving them that stood by, and all of them were amazed. (The Acts of Peter, 9)
Reply
#6
RE: An easy proof that rational numbers are countable.
(February 22, 2018 at 3:19 pm)Jehanne Wrote: The proof/technique in my OP is also in Rosen, Discrete Mathematics, 7th edition.

Point of my thread is that there are things that are counterintuitive, yet provably true!  These are sometimes referred to as "veridical paradoxes".

Anyone who has studied math past the level of calculus has seen many of such.

One of my favorites is the Peano space-filling curve:
https://www.youtube.com/watch?v=MaoCp08hznM
Reply
#7
RE: An easy proof that rational numbers are countable.
(February 22, 2018 at 1:30 pm)Kernel Sohcahtoa Wrote: 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.

The biggest problem here is that Theorem 1 is proven by essentially the same techniques as in the OP. A better way is to go as follows:

1. If there is an onto function f:A->B, then there is a one-to-one function g:B->A. This can use the axiom of choice, but if A is the set of naturals, we can use well-ordering of the naturals to get it.

2. If A is a subset of the naturals, then A is countable. This is proved by trivially if A is finite. But if A is infinite, we can send 1 to the smallest element of A, 2 to the next smallest, 3 to the next smallest, etc and this will give a one-to-one and onto function from N to A, showing A is countable.

3. Use the OP method to give an onto function from N to the rationals. Then 1 gives that the rationals are equivalent to a subset of N and thereby are countable.
Reply
#8
RE: An easy proof that rational numbers are countable.
(February 22, 2018 at 4:17 pm)polymath257 Wrote:
(February 22, 2018 at 3:19 pm)Jehanne Wrote: The proof/technique in my OP is also in Rosen, Discrete Mathematics, 7th edition.

Point of my thread is that there are things that are counterintuitive, yet provably true!  These are sometimes referred to as "veridical paradoxes".

Anyone who has studied math past the level of calculus has seen many of such.

One of my favorites is the Peano space-filling curve:
https://www.youtube.com/watch?v=MaoCp08hznM

WLC was a communications major (for actors, news anchors) at Wheaton College, and then he went to Bible school where people go to be evangelical Christian pastors.  I don't think that he took any STEM classes while in college.
And without delay Peter went quickly out of the synagogue (assembly) and went unto the house of Marcellus, where Simon lodged: and much people followed him...And Peter turned unto the people that followed him and said: Ye shall now see a great and marvellous wonder. And Peter seeing a great dog bound with a strong chain, went to him and loosed him, and when he was loosed the dog received a man's voice and said unto Peter: What dost thou bid me to do, thou servant of the unspeakable and living God? Peter said unto him: Go in and say unto Simon in the midst of his company: Peter saith unto thee, Come forth abroad, for thy sake am I come to Rome, thou wicked one and deceiver of simple souls. And immediately the dog ran and entered in, and rushed into the midst of them that were with Simon, and lifted up his forefeet and in a loud voice said: Thou Simon, Peter the servant of Christ who standeth at the door saith unto thee: Come forth abroad, for thy sake am I come to Rome, thou most wicked one and deceiver of simple souls. And when Simon heard it, and beheld the incredible sight, he lost the words wherewith he was deceiving them that stood by, and all of them were amazed. (The Acts of Peter, 9)
Reply



Possibly Related Threads...
Thread Author Replies Views Last Post
  If people were 100% rational, would the world be better? vulcanlogician 188 9059 August 30, 2021 at 4:37 pm
Last Post: vulcanlogician
  [Serious] Criticism of Aquinas' First Way or of the Proof of God from Motion. spirit-salamander 75 3533 May 3, 2021 at 12:18 pm
Last Post: Neo-Scholastic
  A 'proof' of God's existence - free will mrj 54 4369 August 9, 2020 at 10:25 am
Last Post: Sal
  Proof that I'm immortal Shantideva 64 3059 September 11, 2018 at 7:03 pm
Last Post: Angrboda
  Is the fear of irrational fears rational? ErGingerbreadMandude 26 5426 August 13, 2017 at 9:48 pm
Last Post: Losty
  Is there a logical, rational reason why hate is bad? WisdomOfTheTrees 27 2882 February 4, 2017 at 10:43 pm
Last Post: BrianSoddingBoru4
  Who Has the Burden of Proof? Rhondazvous 10 2902 October 26, 2015 at 10:49 pm
Last Post: jenny1972
  Proof Mind is Fundamental and Matter Doesn't Exist Rational AKD 348 69868 October 22, 2015 at 6:34 pm
Last Post: bennyboy
Exclamation Proof For The Materialization Of Dream Objects Into Reality A Lucid Dreaming Atheist 15 3191 August 19, 2015 at 1:44 am
Last Post: Alex K
  Proof of God Harris 257 42143 May 21, 2015 at 8:24 pm
Last Post: IATIA



Users browsing this thread: 1 Guest(s)