Counting Infinite Sets
Date: 06/02/97 at 03:33:50 From: Boaz Binnun Subject: Counting infinite sets Hi, I am a computer science student from Israel and I have this problem from my mathematical logic class: What is the cardinality of all the pieces (as small as you wish) that are part of the line? How do you prove this? (A piece is a finite line between two points.) Thanks a lot, Boaz
Date: 06/04/97 at 18:16:29 From: Doctor Daniel Subject: Re: Counting infinite sets Hi Boaz, I believe it's fairly clear that the cardinality of this set is identical to the cardinality of the real line. Let's let A = the set of all closed intervals in the real line R = the set of real numbers R+ = the set of positive real numbers Here in the U.S., we usually represent closed intervals by their endpoints; [a,b] is the interval from a to b. You should know by now that R has the same cardinality as R+, so I'll assume that you do; it's not a hard proof. It's clear that A is at least as big as R+; there's a member [0,x] for every positive real number x. It's also clear that we can go from [a,b] to a unique real number which only corresponds to that real number; it's not easy, but not too hard. Suppose that we knew that a and b were both between zero and 1. Then a = .nnnnnnnnn... (it's an infinite decimal), and b = .mmmmmmmmmmm... For each [a,b], just map it into .nmnmnmnmnnmnmnmnmnmnmnmnm... That is, just interleave the digits from the decimal representation of a with the digits from the decimal representation of b. It's that easy; given a real number, we can reconstruct a and b automatically! Now, if a and b have digits before the decimal, we'll just need to find some way to encode how many; maybe we'll start with the base 2 representation of the number of digits before the decimal point of a, then a three, then the base 2 representation of the number of digits before the decimal point of b, then a three, and then interleave the digits as before. So, for example, if a = 23.12555555555... and b = 8.9898989889898..., we could assign them to the real number 10313283918295859585958595859... The 10 before the first 3 says that a has two digits before the decimal point, the 1 before the second 3 says that b has one. And, similarly, we could encode negative numbers. What matters is that we can inject A into R. So they have the same cardinality. Of course, this whole thing is cheating, since you probably have learned that _any_ subset of RxR has at most as high cardinality as R; clearly A is isomorphic with a subset of RxR. So it has as high cardinality as R. Good luck, -Doctor Daniel, 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.