2
$\begingroup$

An “infinite increasing sequence of binary strings” is a series $w1, w2, …$ of finite binary strings, such that for every number $i$, string $w_i$ is a prefix of $w_{i+1}$.

For example, $“101”, “10100”, “101001”,“1010010111”, … $

Let $S$ be the set of infinite increasing sequences of binary strings. What is the cardinality of $S$? Prove your answer. $$$$

I know that cardinality of finite binary strings is $ℵ_0$ , and cardinality of infinite binary strings is $ℵ$ . Every sequence in $S$ is:$${\{0,1\}}^{ℵ_0} \Rightarrow 2^{ℵ_0} = ℵ $$

$S$ is a countable union of infinite increasing sequences of binary strings, so I have $|S|\leq ℵ$.

How can I prove that $ ℵ\leq|S|$, and is my first direction correct?

Thank you!

$\endgroup$

1 Answer 1

2
$\begingroup$

To show $\aleph \le |S|$ you can establish a bijection between the infinite binary strings and the subset of $S$ consisting of those sequences that increase by one bit at a time just by reading off the sequence.
As an example the string $1011000101\ldots$ would correspond to $1,10,101,1011,10110,101100,1011000,101100010,1011000101,\ldots$

To show that $|S| \le \aleph$ I would inject $S$ into $\aleph \times \aleph$. Each sequence in $S$ can be matched with one binary string for the bits and one binary string that shows where we stop adding bits at each stage. We let a $1$ mean "stop here" so the sequence $1,101,1011,10110001,101100010,1011000101\ldots$ would have the same string as above as the first entry and $1011000111\ldots$ as its second entry. Now if you have $|\aleph \times \aleph|=\aleph$ you are done.

$\endgroup$

You must log in to answer this question.

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