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

### Countability of Sets

```Date: 09/23/2004 at 14:21:33
Subject: Countability of a set question

I am just getting a handle on the countability of sets and this
problem bugs me:

Let A be the set of all sequences of the form (d1, d2, 23,...) where
di = 0 or 1 and there are only a finite number of 1's in the sequence.
Prove that A is countable.

I know that I need to pick a bijective function so any element of A
has to be assigned one and only one integer from N.  But I don't know
where to go from there.  Thanks for any help you can give.

```

```
Date: 09/23/2004 at 16:56:34
From: Doctor Schwa
Subject: Re: Countability of a set question

Have you proved the theorem that if you take the union of countably
many sets, and each set is countable, then the union is countable?

That theorem could be very useful in solving this problem!

Give that some thought, and if you'd like more hints, please write back!

- Doctor Schwa, The Math Forum
http://mathforum.org/dr.math/

```

```
Date: 09/23/2004 at 22:38:11
Subject: Countability of a set question

Dear Dr. Math,

Thank you for your prompt response.  Yes, I have proved that theorem

Let j denote the number of 1's in the sequence X.  Let k denote the
number of 0's in the same sequence.  Denote the set A(j) = {X(jk)}.
So, this is a notation determining the number of 1's and 0's in any
particular sequence.

If number of 0's is finite we can set up the following infinte
matrix:

A(1k) = X(11) X(12)...X(1n)
A(2k) = X(21) X(22)...X(2n)
.
.
.

Any A(jk) is a finite set.  Therefore A is the countably infinite
union of finite sets => A is countable.

If number of 0's is countably infinite the matrix changes slightly:

A(1k)= X(11) X(12)...
A(2k)= X(21) X(22)...
.
.
.

Now, each A(jk) is a countably infinite set (since the set N is
countably infinite).  Therefore, A is the countably infinite union of
countably infinite sets => A is countable.

```

```
Date: 09/27/2004 at 08:18:57
From: Doctor Schwa
Subject: Re: Countability of a set question

That sounds fine to me!  I did it with perhaps a less efficient
process.

Let A(jk) be the set of all sequences containing j ones where the last
1 is in the kth spot.

Then each A(jk) is finite--in fact has cardinality of the binomial
coefficient (k-1 choose j-1).  So A(j_) is the countable union of
finite sets, and then A(__) is the countable union of countable sets.

One thing to note: these sets are exactly 1-1 with binary numbers
whose expansions terminate (with finitely many ones, since when you're
writing a number like .1010001 you don't write the infinitely many
zeros after the last 1).  So this is equivalent to all fractions whose
denominator in lowest terms is 2^k, and since the rationals are
countable, this subset of the rationals is also.

Enjoy,

- Doctor Schwa, The Math Forum
http://mathforum.org/dr.math/

```

```
Date: 09/27/2004 at 21:48:38
Subject: Countability of a set question

Good evening Dr. Schwa.

I like your proof better.  Thanks for your thoughts on this problem.
```
Associated Topics:
College Logic

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