Show that the sequence $(-1)^{n}$ has uncountably many subsequences.

Question

(First time posting on M.SE)

Here is what I have so far, any corrections with the proof or notation would be much appreciated!

Let the sequence $A = \{a_n\}_{n=1}^\infty = \{(-1)^n : n \in \mathbb{N}\}$ and let $B$ be the set of all subsequences of $A$. We want to show that $B$ is uncountable.

$$A = \{-1, 1, -1, 1, -1, 1, \ldots\}$$

Suppose BWOC that $B$ is countable. Then there exists a bijection $f: \mathbb{N} \to B$.

WLOG, let $f(1) = \{1, 1, 1, 1, 1, ...\}$, $f(2) = \{-1, -1, -1, -1, -1, ...\}$, $f(3) = \{1, -1, 1, -1, 1, ...\}$, $f(4) = \{-1, 1, 1, 1, -1, ...\}$, $...$, $f(n)$.

Let $S$ be such that $S_1 \neq f(1)_1$, $S_2 \neq f(2)_2$, $S_3 \neq f(3)_3$, $...$, and in general $S_n \neq f(n)_k$. So $S = \{-1, 1, 1, -1, ...\}$.

Therefore $S \subset A$ and $S \in B$, but $f(n) \neq S$ $\forall n \in \mathbb{N}$. So $f: \mathbb{N} \to B$ is not a bijection, and thus $B$ is uncountable.

Thanks in advance!

Answer 1

We can do this with a Cantor diagonal argument. We know that the subsequences of $\{(-1)^n\}$ consist of all sequences of $1$s and $-1$s.

Suppose an enumeration $\{s_i\}_{1}^{\infty}$ exists. We will construct a sequence of $1$s and $-1$s that cannot be equal to $s_i$ for any $i\in\mathbb N$.

Let $s_{ij}$ be the $j$th element of the $i$th sequence of our enumeration. For example, $s_{23}$ is the third element of $s_2$.

We define a new sequence $\{a_n\}$ by $$a_i=\begin{cases} 1, &\text{if $s_{ii}=-1$} \\ -1, &\text{if $s_{ii}=1$} \end{cases}$$

$\{a_n\}$ is a sequence that differs from $s_i$ in its $i$th place so $\{a_n\}$ cannot be equal to any of the $s_i$. Since we can construct a similar sequence for any enumeration of the subsequences of $\{(-1)^n\}$, the subsequences are uncountable.

Answer 2

Your argument is fine but what remains kind of unclear is why is $S \in B$, i.e. why is $S$ a subsequence of $A$.

In fact, for any sequence $T$ of $1$s and $-1$s we have that $T$ is a subsequence of $A$. Indeed, if you inductively define a strictly increasing function $p : \Bbb{N} \to \Bbb{N}$ as $$p(1) = \begin{cases} 1, \text{ if } T_1 = -1,\\ 2, \text{ if } T_1 = 1, \end{cases}\qquad p(n+1) = \begin{cases} p(n)+2, \text{ if } T_{n+1} = T_n,\\ p(n)+1, \text{ if } T_{n+1} \ne T_n \end{cases} \qquad\text{ for } n \ge 1.$$ Then $T_n = A_{p(n)}$ for all $n \in \Bbb{N}$ and hence $T \in B$.

If you know that the number of such sequences is $|\{-1,1\}^\Bbb{N}| = 2^{\aleph_0}$ which is uncountable, you can also use this directly.

Answer 3

If we know the set of reals on the interval $[0,1]$ is uncountable then we can show this set of subsequences is uncountable.

Consider an arbitrary real number $r \in [0,1] $ which we index the digits of this real number as $r_n$ so $r_0$ is the first digit, $r_1$ is the second digit, $r_2$ is the third digit etc...

Then consider the INVERTIBLE function $q: 1 \rightarrow 1, 0 \rightarrow -1$. Clearly we can then map ANY element $r$ to a sequence of $-1, 1$ via $q$.

So the set of infinite sequences of $\lbrace{-1, -1\rbrace}$ is the same cardinality as the set of real numbers on $[0,1]$

Now with that out of the way we show every such sequence is a subsequence of $(-1)^n$

Consider an arbitrary sequence in $\lbrace{-1, 1\rbrace}$ call it $T_i$ then we want to produce a sequence of natural numbers $L_i$ so that $T_i$ is a subsequence of $(-1)^n$. For each $T_i$ we consider the index

$$ L_i = \left\lbrace \begin{matrix} 2i \ \text{if} \ T_i = 1 \\ 2i+1 \ \text{if} \ T_i = -1\end{matrix} \right\rbrace $$

Cleary this will work since $(-1)^n = 1$ if $n$ is odd and $(-1)^n = -1$ if $n$ is even.

So now we have shown an ARBITRARY sequence of $(-1,1)$ can be a subsequence of $(-1)^n$ AND that cardinality of all such sequences is the same as the cardinality of the real numbers.