# Show that $S$ has the same cardinality with the set of real numbers.

Suppose that $a_n$ is a sequence with values in $\mathbb R$ which is not ultimately constant.

Let $S$ be the set of the subsequences of $a_n$.

Question: Show that $S$ has the same cardinality with the set of real numbers.

Attempt: First, I tried to write $S$ in my logic as $S=\{a_{f_n}\;|\; f_n \text{is monotone increasing}, f_n:\mathbb N\to\mathbb N \}$

If two sets have the same cardinality, there must be a bijective mapping between them. If I am able to show there are uncountable many increasing $f_n$, then I am done, but I couldnot. Besides, how can one prove this by using my logic or in other method?

Comment: Moreover, I can understand intuitively that there cannot be countable many such subsequences since $a_n$ is not convergent, that is not going to the any number, changes everytime.

• The sequence $\{a_n\}$ can converge, though. All you are told is that $a_n$ is a sequence that is not constant. – Clayton Apr 19 '18 at 18:24
• – user547564 Apr 19 '18 at 18:26

The $\{0,1\}$ sequences are not ultimately constant (if we forget countably many being constant from some term), hence $\mathfrak{c}=2^{\aleph_0}\leq|{S}|\leq\mathfrak{c}^{\aleph_0}=\mathfrak{c}$

• I couldnot understand how you pass from $\{0,1\}$ sequences to $\frak{c}=2^{\aleph_0}\leq|\mathrm{S}|\leq\frak{c}^{\aleph_0}=\frak{c}$ – user2312512851 Apr 19 '18 at 18:32
• @userqrqh123 Number of all sequences with 2 values is $2^{\aleph_0}$; number of all sequences is $\mathfrak{c}^{\aleph_0}$ – Przemysław Scherwentke Apr 19 '18 at 18:33

To every real number $0\lt x\lt1$, we can assign a subsequence such that $a_n$ belongs to that subsequence iff, when expressed in binary, the $n$th digit after the dot is $1$.

For example, $0.1010101...$ would correspond to the subsequence {$a_1, a_3, a_5, ...$}. Since the interval $(0, 1)$ has the same cardinality as $\mathbb R$, we're done.

The set of irrational numbers in $(0,1)$ is not countable.

To each irrational number $x\in (0,1)$ such as $$x=0.x_1x_2x_3......$$ associate the sequence $$f(x)= \{ x_1, x_2, x_3,... \}$$

Thus the set of sequences associated with the irrational numbers in (0,1) is not countable.

On the other hand each sequence $$\{ x_1, x_2, x_3,... \}$$ could be mapped in a real number, $$x=0.x_1x_2x_3......$$

Thus the cardinality of the set of sequences does not exceed the cardinality of real numbers.

That is, the cardianlity of the set of said sequences is the same as cardinality of real numbers.