Prove That a Set Is Uncountably Infinite

Date: 10/31/97 at 00:21:17
From: Matt Ramos
Subject: Prove that a set is uncountably infinite

How can one prove that the set [0,1]x[0,1] is uncountably infinite?

(We are given the hint to show that if this set were put into 
one-to-one correspondence with the natural numbers, then so could 
[0,1].)

I am having problems picturing the contents of the set and how to set 
up a correspondence.

Thank you in advance,
Matt Ramos

Date: 10/31/97 at 05:51:42
From: Doctor Mitteldorf
Subject: Re: Prove that a set is uncountably infinite

Dear Matt,

Picture [0,1] as the set of all points on a line between 0 and 1, 
inclusive. The points are so "close together" that you can't count 
them.

Your picture for [0,1]x[0,1] is all the points in the square with 
corners at (0,0), (0,1), (1,0) and (1,1).

Your intuition should tell you that the number of points in a plane 
area must be "greater than" the number of points on a line.  

To prove that this set isn't countable, we assume that it is countable
and derive a contradiction.  What does it mean to say it's countable?  
It just means that there's some systematic method for listing them 
all. For example, suppose the list looked like this:

1)  (0,0)
2)  (0,.1)
3)  (.1,0)
4)  (.33333..., 0)
5)  (.2, .1415926...)
etc...

In fact, there's no rhyme or reason to the above list.  There's no
way of telling what the point number (6) is.

But the proof says, suppose there were a method to this madness, and I
claimed to be sure that, by this method, I would cover every single
pair of real numbers between 0 and 1 somewhere in my list.

Well, then you could just take apart my list, throwing out duplicates.
You could construct your own list

1)  0
2)  .1
3)  .33333...
4)  .2
5)  .1415926...
   
that came from just extracting both numbers from my list of ordered 
pairs and removing the duplicates, and then you'd have a listing of 
the points on a line.

But you proved in class that it's impossible to make a list of points 
on the line, so it must have been impossible for me to come up with my 
list. QED.

-Doctor Mitteldorf,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/