Proving the set of subsequences of a sequence are uncountable I am attempting to solve the following problem. 
Let ($s_n$) be a subsequence of real numbers. Prove that the set of subsequences of ($s_n$) is uncountable.
I was thinking that approaching this problem by contradiction might be a good approach, but I'm not sure where to start. Any tips would be much appreciated.
 A: First lets fix notation:


*

*A sequence of reals is a function $s:\mathbb{N}\to\mathbb{R}$

*A subsequence $a\circ f$ of a given sequence $a$ is obtained by composing $a$ with some strictly increasing function $f:\mathbb{N}\to\mathbb{N}$. 


In general the statement is not true, a constant sequence only has one subsequence. Let us assume that there are infinitely many different elements in the sequence $(a_i)_{i\in\mathbb{N}}$. Thus (by taking an appropriate subsequence) we can safely assume that the sequence is strictly increasing: $a_0<a_1<\dots$
Now to prove that there are uncountably many subsequences of $a$, it is enough to show that for any two different strictly increasing functions $f,g:\mathbb{N}\to\mathbb{N}$ the subsequences $a\circ f$ and $a\circ g$ are distinct. Let $n$ be the least natural number such that $f(n)\neq g(n)$, we may assume that $f(n)<g(n)$. Obviousely $(a\circ f)(n)$ is not an element of the image of $a\circ g$, thus the subsequences are distinct.
EDIT: There is an easier and more general way. If the sequence $a$ is not becoming stationary ie. there is no $n\in\mathbb{N}$ such that $(a)_{i>n}$ is constant, then there are already uncountably many subsequences of $a$ as basically all "binary sequences" can be realized as a subsequence of $a$.
A: A subsequence is given by a subset of the index set $\Bbb N$. There are continuum-many such subsets. However, we have to ignore the finite subsequences - of which there are countably many. Continuum-many minus countably many is still continuum-many.
A: Any sequence is in one-to-one correspondence to $\Bbb N$, for example via its indexes.
Its subsequences are therefore in correspondence with subsets of $\Bbb N$, such that every non-finite subset of $\Bbb N$ is associated to one subsequence, and vice-versa.
Now, consider the power set $\mathcal{P}(\Bbb N)$: it is uncountable, since it is clearly not finite and $|\mathcal{P}(X)|\geq|X|$ for any set $X$.
Let us split $\mathcal{P}(\Bbb N)$ in two disjoint parts: $F$, the finite sets, and $I$, the infinite sets.
Now, for each integer $n$, $F$ contains all subsets of $\Bbb N$ with $n$ elements: there are countably many of them, since they are elements of $\Bbb N^n$, which is countable because finite product of countable sets.
Therefore, $F$ is the countable union of countable sets, and is thus countable itself.
If $I$ was countable too, then $\mathcal{P}(\Bbb N)$ would be, as union of countables: therefore, $I$ is not countable, and since it is in bijection with the subsequences, those are not countable either.
Note that I am considering subsequences different if they are constructed of differently-indexed elements of the starting sequence, even if the values are the same.
If such were not the case, then a constant sequence would have only one possible subsequence, and serve as counterexample.
