Countability of SetsDate: 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. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/