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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.