What is wrong with this reasoning: The union (finite or infinite) of countable sets is countable. The set of all binary sequences is the infinite union of the sets $S_n$ of all the binary sequences of length n, which are finite, hence countable.

  • 1
    $\begingroup$ You haven't accounted for all the infinite binary sequences, only the finite ones of any length. $\endgroup$ – Alex J Best Mar 22 '13 at 17:47
  • $\begingroup$ Also, it is not true that an infinite union of countable sets is always countable. A union of countably many countable sets if countable, but the union of uncountably many sets each of which is countable may not be. For example $\bigcup_{x\in [0,1)} (\mathbb Z+x)$ is $\mathbb R$ which is not countable. $\endgroup$ – hmakholm left over Monica Mar 22 '13 at 18:04
  • $\begingroup$ @AlexJBest thanks for the response; I was fearing it will exactly this response, as I cannot make the difference between the two.. $\endgroup$ – Radu Mar 22 '13 at 18:48
  • $\begingroup$ @Radu probably one cannot understand the difference between countable and uncountable without first understanding the difference between finite and infinite $\endgroup$ – Trevor Wilson Mar 22 '13 at 18:56
  • $\begingroup$ @TrevorWilson indeed, I am under the (obviously wrong, as it has already been pointed out) impression that my finite sequences can grow without bound, hence cover all infinite sequences.. $\endgroup$ – Radu Mar 22 '13 at 19:09

The set of all finite binary sequences is countable, by the argument that you gave in your question. The set of all infinite binary sequences is not countable, by Cantor’s diagonal argument. But the two sets are completely different; indeed, they’re disjoint.

| cite | improve this answer | |
  • $\begingroup$ Thanks. The last word was the most important. So none of the sequences I mentioned were actually in the set in question. It remains only to try to figure out what these beasts actually are $\endgroup$ – Radu Mar 22 '13 at 18:55
  • $\begingroup$ @Radu: You’re welcome. Yes, that’s right, assuming that you really meant to count the infinite sequences. $\endgroup$ – Brian M. Scott Mar 22 '13 at 18:56
  • $\begingroup$ I am sadly stuck here. I cannot, after some thought, figure out where these infinite sequences come from. Not induction, those are just finite of any length, I am told. Are they a consequence? Are they due to an axiom? Is it simply postulated that they exist and are larger than any n I could come up with? $\endgroup$ – Radu Mar 30 '13 at 21:14
  • $\begingroup$ @Radu: I’m not sure what you mean by where they come from. They are simply functions from $\Bbb N$ to the set $\{0,1\}$; the existence of that set of functions follows from the usual axioms of set theory, as does the proof that there are uncountably many such functions. $\endgroup$ – Brian M. Scott Mar 30 '13 at 22:27
  • $\begingroup$ @Radu: If it’s any consolation, you’re not alone in that. And I can’t help too much there, because it’s something that always seemed very natural to me. $\endgroup$ – Brian M. Scott Mar 31 '13 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.