Too many people think Math is Dull. 

Astounding Math Stories exists to show you

the kinds of weird things that happen when you do math.

These Astounding Stories also illustrate some important ideas in math,

so this blog also has a Secret Educational Agenda. 

 

 Table of contents

Sizes of Infinity

A conversation recorded by the Six Winged Seraph, a certified member of the Society of Recording Angels

18 December 2008

Gyr: Gimble, did you know that there are exactly as many positive integers as there are rational numbers?  Isn’t that astounding?

Gimblos:  But that’s obviously wrong.  Every integer is a rational number, like 3 is the same as 6/2.   But there are rational numbers that are not integers, like 1/3.  So the set of integers is a proper subset of the set of rationals.  A set can’t have the same number of elements as a proper subset, because there are elements left over!

Gyr:  Ah, but the positive integers and the rational numbers are both infinite sets and you intuition gets  when you are dealing with infinite sets.  The world of infinite sets is full of weird things.  You can’t depend on your experience with counting things when you are dealing with infinite sets. 

Gimblos:  Well, I don’t believe it.  You need to prove it!

Gyr:  It’s not hard.  I will show you a way to lay out the rational numbers in order, so there is a first one, a second one, and so on.  The usual order doesn’t allow this because of density.  It’s like this: make sure you write each one in lowest terms and list them in order by the sum of the absolute values of their numerator and denominator.  So:

¨  The first one is 0, which is , so the sum of the numerator and denominator is 1. 

¨  Then  and  have sum 2, so you list them left to right in the usual order. 

¨  Then  and  have sum 3 and you list them left to right. 

¨  For those that add up to 4 you get .  Notice that  also has numerator and denominator adding up to 4 but you don’t include it because it is not in lowest terms. 

¨  So you wind up with this list:

 

and so on. 

¨  Now you count them:  The first one is , the second one is , the third one is , and so on.   You get a one to one correspondence between the positive integers and the rational numbers! 

 So your intuition is ALL WRONG.  A set and a proper subset can have the same number of elements.

Gimblos:  Now wait a minute, you have four rational numbers whose numerators and denominators add up to 4, but eight where they add up to 5 and only two where they add up to six.  Well, I guess that’s right, all the others that add up to 6 aren’t in lowest terms, like  and .  So, yes, you have matched up the positive integers and the rationals in a bijective way. 

Gyr (looking smug):  Well, that’s what I said, there are the same number of positive integers as rational numbers.  Infinite sets are simply weird.    

Gimblos:      … You are trying to   You are like a magician who does something over here so I don’t look at what you are doing over there so I think you’ve done something impossible! 

¨  You said there are the same number of positive integers as rational numbers.

¨  Let’s stipulate that you have proved that there is a bijection between the positive integers and the rational numbers.  (I just discovered that word “stipulate”.  Isn’t it great?)

¨  The positive integers and the rational numbers each form infinite sets.  

¨  We count finite sets, not infinite sets.

¨  Two finite sets have the same number if there is a bijection between them.

¨  So you secretly extended the definition of “number of” to infinite sets by saying two infinite sets have the same number of elements if there is a bijection between them. 

¨  Then you tried to bamboozle me into thinking the set of positive integers and the set of rational numbers have the same number of elements.  But that is only because you changed the meaning of the word “number”.  You haven’t told me anything astounding, you just tried to trick me. [Goes out and slams the door.]

 

Six Winged Seraph:  Well, reader, who is right?  Did Gyr do something Astounding or did she try and fail to trick Gimblon?

If you want to learn more:

 Wikipedia article on cardinality