0
$\begingroup$

$A$ is the set of all infinite binary strings. The question is what is the cardinality of $B$ that contains all the strings in $A$ that have finite number of '1' (i.e "ones").

I started by looking at the cardinality of $A$ which is $ |{0,1}|^\mathbb{N} $ meaning all the functions from $N$ to $\{0,1\}$ and it easy to see that the cardinality of $A$ is $2^{\aleph_0}$ But I don't know how to proceed.. Thank you in advance.

$\endgroup$
6
  • $\begingroup$ How many finite subsets of $\Bbb N$ are there? $\endgroup$
    – BrianO
    Apr 9, 2016 at 14:03
  • $\begingroup$ @BrianO: That is another way to view the question, but I don't think it's any easier in this case. However it brings the interesting viewpoint that finite subsets of an infinite set $S$ can be understood as sets of size 1, 2, 3, ... and then one would need (want) $\#(S^1) + \#(S^2) + \#(S^3) + \cdots = \#(S)$. My answer wouldn't work for uncountable $S$. (And did you see my questions to you in the chat-room?) $\endgroup$
    – user21820
    Apr 9, 2016 at 14:17
  • $\begingroup$ @user21820 Thank you for your answer , i dont know what is the "chat-room" and how do I enter it. . $\endgroup$
    – Noam
    Apr 9, 2016 at 14:29
  • $\begingroup$ Noam, my comment was meant for BrianO. Though the first part is also relevant to this question but not as easy as the approach in my answer. $\endgroup$
    – user21820
    Apr 9, 2016 at 14:40
  • $\begingroup$ @user21820 Ok , thank you $\endgroup$
    – Noam
    Apr 9, 2016 at 15:19

1 Answer 1

Reset to default
2
$\begingroup$

Hint If a binary string has finitely many ones, it has a final one. Now how many binary strings have a final one at position $n$? Then you can 'sum' over all natural numbers $n$.

$\endgroup$
10
  • $\begingroup$ Well I think that there are {0,1}^n meaning as many functions as from a set of size n to the set {0,1} but what do you mean by "'sum' over all natural numbers"? $\endgroup$
    – Noam
    Apr 9, 2016 at 14:28
  • $\begingroup$ @Noam: "as many functions as from a set of size n to the set {0,1}".. exactly how many is that? And you want number of binary strings with finitely many ones, which is equal to the number of binary strings with a final one, which splits into many groups, one group for the final one at position $n$. So of course the total is the 'sum'. It's not a proper sum in the usual sense because it does not converge to a real number, but you should get the idea. $\endgroup$
    – user21820
    Apr 9, 2016 at 14:43
  • $\begingroup$ I think that for every string with a final one at position n there are 2^(n-1) different Strings.. But the sum concept is still not clear to me - should I sum 2^0 + 2^1 +...... 2^n ? $\endgroup$
    – Noam
    Apr 9, 2016 at 15:26
  • $\begingroup$ @Noam: Right, assuming you start from position $1$. And the 'sum' is the right idea, but clearly it's not finite, so neither is the set you're asking about. But then is it countably infinite? Are you able to assign a unique natural number to each element by running through each group one at a time? $\endgroup$
    – user21820
    Apr 9, 2016 at 15:28
  • $\begingroup$ Well no , I don't think I can or atleast I can't see how. I know that the set is infinite and I thought of trying to show a bijection between P(N) to those Strings and then conclude that the cardinality is Aleph but I'm not sure how to do so. $\endgroup$
    – Noam
    Apr 9, 2016 at 16:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .