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/