Exercise 2.5.6 of Understanding Analysis Let $(a_n)$ be a bounded sequence and define the set S = $\{ x \in R : x < a_n$ for infinitely many terms of $a_n\}$. 
Show that there exists a subsequence $(a_{n_j})$ converging to $s$ = sup $S$.
The book says it is a direct proof of the Bolzano-Weierstrass Theorem using the Axiom of Completeness, but I'm not seeing how one would do it. 
 A: Here's the idea of how this is done.
Fix $n_1\in\mathbb N$.  Show by induction, and using the definition of the set $S$, that for each $k\in\mathbb N$, there is some $n_{k+1}\in\mathbb N$ such that $n_{k+1}>n_k$ and $|a_{n_k}-s|<\frac{1}{k}$.  Then show that the subsequence $(a_{n_k})_{k\in\mathbb N}$ works.  
A: Besides other nice answers, let me provide a solution which is verbose but slightly more elementary.

Proof. Write $s = \sup S$. Then we can find a sequence $(s_j)_{j\geq 1}$ in $S$ which is strictly increasing and converges to $s$. (For instance, pick $s_j = s - 2^{-j}$ or $s_j = s - (1/j)$, etc.)
Now, given the choice of such $(s_j)$, we run the following algorithm to define $(n_j)_{j\geq 1}$.


*

*Set $n_0 = 0$ for simplicity.

*Suppose that $j \geq 1$ and $n_{j-1}$ is defined. Since $s_j \in S$, we can find $n_j$, larger than $n_{j-1}$, so that $a_{n_j} > s_j$.
Now we claim that $(a_{n_j})_{j\geq 1}$ converges to $s$. To this end, we need to initiate the $\epsilon$-$N$ argument. So let $\epsilon > 0$ be arbitrary. Then


*

*Since $s+\epsilon/2$ is not an element of $S$, there are only finitely many $j$'s for which $a_{n_j} > s+\epsilon/2$. So we can pick $N_{\text{above}}$ so that $a_{n_j} \leq s+\epsilon/2$ for all $j > N_{\text{above}}$.

*Since $s_j \uparrow s$, there exists $N_{\text{below}}$ such that $j > N_{\text{below}}$ implies $s_j > s-\epsilon$.
Now set $N = \max\{N_{\text{above}}, N_{\text{below}} \}$. By combining two statements, we find that $|a_{n_j} - s| < \epsilon$ for all $j > N$. Then the $\epsilon$-$N$ definition of the limit kicks in, proving the desired claim.

As an advice, try to identify $S$ and visualize the above process for each of the following examples:


*

*$a_n = \frac{1}{n}$,

*$a_n = -\frac{1}{n}$,

*$a_n = (-1)^n \frac{n+11}{n}$,

*$a_n = \sin(\pi n/2019)$.
A: Let $a = \lim \sup a_n$. Let us show that $(-\infty, a) \subset S \subset (-\infty, a]$. This implies that $s=a$ from which the conclusion follows easily. 
Let $x <a$. Then $x <a_n$ for infinitely many $n$ (s0 $x \in S$). To see this prove by contradiction: if $x \geq a_n$ for all $n$ exceeding some $n_0$ the we get $x \geq a$, a contradiction.
This proves the first inclusion. For the second inclusion let $x \in S$. There is a subsequence $a_{n_j}$ such that $x<a_{n_j}$ for all $j$ so $x \leq a$.
A: The only difference between this answer and the one given by Aweygan is here we construct the subsequence with an algorithm.
By our assumptions/setup, we can define a mapping $\Gamma: \Bbb N \times \Bbb N \to \Bbb N \times \Bbb N$ by
$$\tag 1 (k,m) \mapsto \left(k+1,\, \text{min} (\{n \, : \, |a_n - s| \lt \frac{1}{k+1} \text{ and } n \gt m\})\right)$$
Using recursion define a function $\rho: \Bbb N \to \Bbb N \times \Bbb N$ by
$\quad \rho(1) = (1,1)$
and
$\quad \rho(j+1) = \Gamma(\rho(j))$
Let $\pi_2: \Bbb N \times \Bbb N \to \Bbb N$ be the projection onto the $2^{\text{nd}}$ coordinate. The subsequence,
$ \quad k \mapsto a_{\pi_2(\rho(k))}$
is readily seen to converge to $s$.
