One-to-One Correspondence and Transfinite Numbers

Date: 12/10/1999 at 00:00:41
From: Lisa Huang
Subject: Set Theory

Hi,

I am doing a project in which I have to explain the set theory that 
George Cantor discovered in the late 1800s. I got an article from the 
Math Forum site that explained how he went about it, but it has math 
terms that I don't really understand. I don't understand what he means 
by putting elements into "one-to-one" correspondences, and I also 
don't really understand what a "transfinite number" is. The page that 
I went to is:

   http://mathforum.org/~isaac/problems/cantor2.html   

If you could please explain just the very, very basics of set theory 
to me, I would be very grateful. Thank you for your time.

Date: 12/10/1999 at 19:04:50
From: Doctor Ian
Subject: Re: Set Theory

Hi Lisa, 

Let's say that you have a collection of baseball cards, and a 
collection of pens, and you want to know which collection is larger.

Normally, you would count the number of cards, count the number of 
pens, and compare the two numbers. But what if you didn't know how to 
count? Or you knew how to count, but only up to 5 or so?

Well, you could start pairing cards with pens: take one card and one 
pen, put them off to the side; take another card and another pen, put 
them off to the side; and so on.

If you run out of cards first, you know that you have more pens, while 
if you run out of pens first, you know that you have more cards - even 
though you can't say exactly how many you have of either.

And if you run out of both cards and pens at the same time, then you 
know you have the same number of each. In this case, what you've done 
is to put the cards and the pens into a one-to-one correspondence.

This is sort of the situation that Cantor was in when he wanted to 
show that the number of integers is the same as the number of rational 
numbers. Obviously he couldn't just count all the integers and all the 
rationals and just compare the numbers. But what he _could_ do was try 
to set up a one-to-one correspondence between the two sets of numbers. 
In effect, he wanted to pair up each integer with one particular 
rational number. Then he could do the same thing with integers and 
rational numbers that we were just doing a moment ago with baseball 
cards and pens.

But it's a tough problem, because between any two rationals, you can 
always put another rational. So if he tried to do something like this,

     1 <-> 1/2
     2 <-> 1/3
     3 <-> 1/4

and so on, someone could always say, "But you've left out all the 
rationals between 1/2 and 1/3," or "You've left out all the rationals 
between 1/3 and 1/4," and so on. So it looked as if he would always 
run out of integers first, which, to be truthful, is what 'common 
sense' says should happen.

However, by laying the rationals out in a checkerboard pattern,

      :    :    :

     1/4  2/4  3/4 ...

     1/3  2/3  3/3 ...

     1/2  2/2  3/2 ...

     1/1  2/1  3/1 ...

he found that since every rational would show up somewhere on the 
board (do you see why?), and since every square on the board could be 
assigned a unique integer,

     10  11 12 ...
     ----------+
     5   6   7 |
     ------+   |
     2   3 | 8 |
     --+   |   |
     1 | 4 | 9 |

he had in fact found a one-to-one correspondence between integers and 
rationals.

So, how many rationals are there? The number of rationals is the same 
as the number of integers. They are both infinite. But there are other 
sets that are larger than either of these sets - for example, the set 
of real numbers.

So while it's tempting to just use one word - 'infinity' - to describe 
the sizes of all these sets, that would cause confusion. So he decided 
to give different names to the different kinds of infinities, and 
those names are what we call 'transfinite numbers.'

I hope this helps. Set theory is a big topic so I'm not going to try 
to explain it all to you in this message. But be sure to write back if 
you have questions about specific things you're having trouble 
understanding.

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/