Cardinality of a set of sequences of binary strings

Perhaps look at it like this: if $w_i$ is an initial segment of $w_{i+1}$, let $u_i$ be the finite binary string such that $w_{i+1}=w_i^\frown u_i$ (and let $u_1=w_1$). Then we can convert the sequence $w_1,w_2,w_3,\dots$ to $u_1,u_2,u_3,\dots$. It's easy to see that this conversion is bijective. Note that the each $u_i$ could be any finite binary string and does not depend on the value of the previous $u_j$ for $j<i$.

Thus, instead of an infinite sequence of increasingly longer finite binary strings that extend each other, we just have an infinite sequence of arbitrary finite binary strings.

To solve the question, you need the answer to the following two questions:

• How many finite binary strings are there? Let's call this cardinality $X$
• If $S'$ is the set of sequences of length $\alpha$ of elements in $X$, what is the cardinality of $S'$?

Let me know if you need more help.

There are many ways to show $|S|\le 2^{\aleph_0}.$ Assume this is done.

So if we can find $T\subset S$ with $|T|=2^{\aleph_0}$ then $|S|=2^{\aleph_0}$.

Consider each $w_i$ as a member of $\Bbb N_0$ written in binary. Then $w_{i+1}=2^{k_i}w_i+n_i$ for some $k_i\in \Bbb N$ and some $n_i \in\Bbb N_0$ with $n_i<2^{k_i}.$

Let $B$ be the set of all countably infinite binary sequences. For any $b=(n_{i,b})_{i\in\Bbb N}\in B,$ take $w(b)=(w_{i,b})_{i\in\Bbb N}\in S$ where the length of $w_{i,b}$ (considered as a string) is $i$ for all $i\in \Bbb N$ and, when considered as numbers, $w_{1,b}=0$ and $w_{i+1,b}=2w_{i,b}+n_{i,b}$ for all $i\in \Bbb N.$

Let $T=\{w(b): b\in B\}$. If $b,b'$ are unequal members of $B$ then $w(b)\ne w(b').$ So $|T|=|B|=2^{\aleph_0}.$

The answer is $2^{\aleph_0}$.

Some notation ahead: For a positive integer number $n$, we denote the bold $\mathbf{n}$ the set $\{1,2,\ldots,n\}$. For two sets $A$ and $B$, we denote $B^A$ the set of all maps from $A$ to $B$.

Remark: a finite binary string can be viewed as a map $\mathbf{n} \to \mathbf{2}$ where $n$ is the length of the string in question. For example, the string $101$ can be viewed as the map $\mathbf{3} \to \mathbf{2}, 1 \mapsto 1, 2 \mapsto 0, 3 \mapsto 1$.

Alternating the definition: We now define the "infinite increasing sequence of binary strings" in the language of set and map: an infinite increasing sequence of binary strings is a pair of map $(w,l)$ where $$ l: \mathbb{N}^+ \to \mathbb{N}^+ $$ and $$ w: \mathbb{N}^+ \to \mathbf{2} $$

To see why this defines the "infinite increasing sequence of binary strings", consider the following association: given such a pair of map $(w,l)$, we obtain a series of maps $$ w_i: \mathbf{n_i} \to \mathbf{2} $$ which is the restriction of $w$ to $\mathbf{n_i}$ where $i \in \mathbb{N}^+$ and $n_i = \sum_{j=1}^i l(j)$. It is easy that $(w_1,\ldots,w_i,\ldots)$ is an "infinite increasing sequence of binary strings" in the original sense. One checks that this association is actually a bijection.

Evaluation of the cardinality: By identifying $\mathbb{N}^+$ with $\mathbb{N}$, the original problem boils down to evaluate the cardinality of the Cartesian product set $\mathbb{N}^\mathbb{N} \times \mathbf{2}^\mathbb{N}$. It is well-know that each factor set is of cardinality $2^{\aleph_0}$ hence the product set.