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
[0,1].)

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

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/

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search