Prove |Q| (length of rational #s) = |N| (length of natural numbers) Thanks in Ad

Question

Prove |Q| (length of rational #s) = |N| (length of natural numbers)

Thanks in Advance!

Explanation / Answer

A standard method of analysis to prove this is to find a one to one function from the set of natural numbers to the set of rational numbers.( The set of natural numbers are called countably infinite or infinity of 1st order). 1st solution : An easy way to think of this is that every rational numbers can be written as r=m/n where m,n belongs to N. Hence there is a map of rational numbers to natural numbers, but this is not one to one !! as the same rational number 1/2 can be represented as 1/2,2/4,4/8 etc, So we need to carefully design a one to one function. write the set of rational numbers this way : 1/1 2/1 3/1 4/1 5/1..... 1/2 2/2 3/2 4/2 5/2... 1/3 2/3 3/3 4/3 5/3.. ......................... etc. Now traverse the list diagonally and delete all duplicate entries. When done, traverse the list again in order and keep on assigning natural numbers to every new value encountered, This way we will have maps from all natural numbers to all positive rational numbers. write them in two lists side by side. add 0 in rational side corresponding to 1 in natural side. push all the numbers in rational side one position. Simillarly add negation of all the rational numbers and keep on pushing them one position as you keep on adding numbers.(remember you are pushing down the rational numbers, not natural numbers) . Hence you have one rational number for every natural number and its a one to one correspondence. 2nd solution : all rational numbers can be mapped into the subset of all ordered triplets of natural numbers (a,b,c) such that a>=0, b>0 and c={0,1} such that c=0 if its a positive rational number and 1 otherwise. a and b are coprime, So 0 maps to (0,1,0) 1 maps to (1,1,0) -1 maps to (1,1,1) 1/2 maps to (1,2,0) -1/2 maps to (1,2,1) and so on. Now theorem says that cartesian product of finitely many countable sets is countable. Hence the triplets are countable set. we clearly have a one to one relation from the set of rational numbers to a countably infinite set. Hence the cardinality of the sets are same.(countably infinite or aleph null)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.