Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Analysis

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