Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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 

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 

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...)

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/   
Associated Topics:
College Analysis
High School Analysis
High School Sets

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994-2013 The Math Forum