Countability of Sets

Date: 09/23/2004 at 14:21:33
From: Nedzad
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

Hi Nedzad,

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
From: Nedzad
Subject: Countability of a set question

Dear Dr. Math,

Thank you for your prompt response.  Yes, I have proved that theorem 
and went over it again.  How about this for a proof:

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

Hi Nedzad,

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
From: Nedzad
Subject: Countability of a set question

Good evening Dr. Schwa.

I like your proof better.  Thanks for your thoughts on this problem.