[proofplan] We construct the supremum by a nested-interval / bisection argument. Starting from a point $a_0 \in S$ and an upper bound $b_0$ of $S$, we recursively halve the interval $[a_n, b_n]$, choosing the right half whenever it contains an element of $S$ and the left half otherwise. This produces sequences $(a_n), (b_n)$ with $a_n \in \mathbb{R}$ never an upper bound of $S$ (more precisely, every $a_n$ is dominated by some element of $S$), every $b_n$ an upper bound of $S$, and $b_n - a_n = (b_0 - a_0)/2^n \to 0$. Both sequences are Cauchy and share a common limit $s \in \mathbb{R}$ by completeness of $\mathbb{R}$ (theorem 3226). We then verify in two steps that $s$ is the supremum: it is an upper bound (because it is the limit of upper bounds $b_n$), and it is the least upper bound (any strictly smaller bound would be exceeded by some $a_n$, hence by some element of $S$). [/proofplan] [step:Set up the bisection: pick a starting interval $[a_0, b_0]$ containing data from $S$] Let $S \subset \mathbb{R}$ be non-empty and bounded above. Pick any $a_0 \in S$ (possible since $S \ne \varnothing$) and any upper bound $b_0$ of $S$ (possible since $S$ is bounded above). Then $a_0 \le b_0$ because $a_0 \in S$ and $b_0$ bounds $S$ above. [/step] [step:Recursively bisect to build sequences $(a_n), (b_n)$ with the upper-bound property] We define sequences $(a_n)_{n \ge 0}, (b_n)_{n \ge 0} \subset \mathbb{R}$ recursively. Suppose $a_n, b_n \in \mathbb{R}$ have been chosen with the properties (P1) $a_n \le b_n$; (P2) $b_n$ is an upper bound of $S$; (P3) there exists $s_n \in S$ with $a_n \le s_n$ (equivalently, $a_n$ is **not** a strict upper bound: some element of $S$ is $\ge a_n$); (P4) $b_n - a_n = (b_0 - a_0)/2^n$. Set $m_n := (a_n + b_n)/2 \in \mathbb{R}$ (the midpoint). Define \begin{align*} (a_{n+1}, b_{n+1}) := \begin{cases} (m_n, b_n) & \text{if there exists } s \in S \text{ with } s \ge m_n, \\ (a_n, m_n) & \text{otherwise (i.e. } m_n \text{ is an upper bound of } S). \end{cases} \end{align*} We verify (P1)-(P4) for $n + 1$. *Case 1: there exists $s \in S$ with $s \ge m_n$.* Then $a_{n+1} = m_n$ and $b_{n+1} = b_n$. (P1): $a_{n+1} = m_n \le b_n = b_{n+1}$. (P2): $b_{n+1} = b_n$ still bounds $S$. (P3): $s \in S$ with $s \ge m_n = a_{n+1}$. (P4): $b_{n+1} - a_{n+1} = b_n - m_n = (b_n - a_n)/2 = (b_0 - a_0)/2^{n+1}$. *Case 2: $m_n$ is an upper bound of $S$.* Then $a_{n+1} = a_n$ and $b_{n+1} = m_n$. (P1): $a_n \le m_n$ since $a_n \le b_n$. (P2): $m_n = b_{n+1}$ is an upper bound by hypothesis of this case. (P3): the same $s_n \in S$ from (P3) at level $n$ has $s_n \ge a_n = a_{n+1}$. (P4): $b_{n+1} - a_{n+1} = m_n - a_n = (b_n - a_n)/2 = (b_0 - a_0)/2^{n+1}$. In both cases, (P1)-(P4) hold at level $n + 1$, and $(a_0, b_0)$ satisfies them at level $0$ by Step 1 (with $s_0 = a_0 \in S$). By induction on $n$, the sequences $(a_n), (b_n)$ are well-defined and satisfy (P1)-(P4) for all $n \ge 0$. [guided] We construct the sequences $(a_n)_{n \ge 0}, (b_n)_{n \ge 0} \subset \mathbb{R}$ by recursion, maintaining four invariants at every stage. The invariants encode the geometric picture: the right endpoint $b_n$ is always pinned as an *upper bound* of $S$, while the left endpoint $a_n$ is always *dominated* by some element of $S$. Why both? The first invariant lets us pass to the limit and obtain an upper bound; the second prevents the limit from being too large to be the *least* upper bound. Together they sandwich $\sup S$. Precisely, suppose $a_n, b_n \in \mathbb{R}$ have been chosen with (P1) $a_n \le b_n$ — the interval is non-degenerate; (P2) $b_n$ is an upper bound of $S$ — i.e. $b_n \ge x$ for all $x \in S$; (P3) there exists $s_n \in S$ with $a_n \le s_n$ — equivalently, $a_n$ is *not* a strict upper bound of $S$; (P4) $b_n - a_n = (b_0 - a_0)/2^n$ — the interval halves at each stage. How do we extend to level $n+1$? Form the midpoint \begin{align*} m_n := \frac{a_n + b_n}{2} \in \mathbb{R}. \end{align*} We ask the natural dichotomy: is $m_n$ an upper bound of $S$, or not? Negating "upper bound" gives: there exists $s \in S$ with $s \ge m_n$ (here we use the strict logical negation of "$m_n \ge x$ for all $x \in S$", which produces some $s \in S$ with $s > m_n$, in particular $s \ge m_n$; we keep the weak form because it is what (P3) requires). These two cases are exhaustive, so we define \begin{align*} (a_{n+1}, b_{n+1}) := \begin{cases} (m_n, b_n) & \text{if there exists } s \in S \text{ with } s \ge m_n, \\ (a_n, m_n) & \text{otherwise (}m_n \text{ is an upper bound of } S\text{).} \end{cases} \end{align*} We verify each invariant in each case, since the recursion is well-posed only if (P1)-(P4) propagate. *Case 1: there exists $s \in S$ with $s \ge m_n$.* We move the **left** endpoint forward: $a_{n+1} = m_n$, $b_{n+1} = b_n$. - (P1): $a_{n+1} = m_n = (a_n + b_n)/2 \le (b_n + b_n)/2 = b_n = b_{n+1}$, using (P1) at level $n$. - (P2): $b_{n+1} = b_n$ is still an upper bound — nothing about $S$ has changed. - (P3): the witness $s \in S$ from the case hypothesis satisfies $s \ge m_n = a_{n+1}$, so we may take $s_{n+1} := s$. - (P4): $b_{n+1} - a_{n+1} = b_n - m_n = b_n - (a_n + b_n)/2 = (b_n - a_n)/2 = (b_0 - a_0)/2^{n+1}$, using (P4) at level $n$. *Case 2: $m_n$ is an upper bound of $S$.* We move the **right** endpoint inward: $a_{n+1} = a_n$, $b_{n+1} = m_n$. - (P1): $a_{n+1} = a_n \le (a_n + b_n)/2 = m_n = b_{n+1}$, using (P1) at level $n$. - (P2): $b_{n+1} = m_n$ is an upper bound by the case hypothesis itself. - (P3): the previous witness $s_n \in S$ from (P3) at level $n$ still satisfies $s_n \ge a_n = a_{n+1}$, so set $s_{n+1} := s_n$. - (P4): $b_{n+1} - a_{n+1} = m_n - a_n = (a_n + b_n)/2 - a_n = (b_n - a_n)/2 = (b_0 - a_0)/2^{n+1}$, using (P4) at level $n$. What about the base case $n = 0$? By Step 1, $a_0 \in S$ and $b_0$ is an upper bound of $S$ with $a_0 \le b_0$. So (P1) holds; (P2) holds by choice of $b_0$; (P3) holds with $s_0 := a_0$ since $a_0 \in S$ and $a_0 \le a_0$; (P4) holds since $2^0 = 1$ gives $b_0 - a_0 = (b_0 - a_0)/2^0$. By induction on $n \ge 0$, the recursion produces well-defined sequences $(a_n), (b_n) \subset \mathbb{R}$ satisfying (P1)-(P4) for every $n \ge 0$. Note that the design is asymmetric in a useful way: in each case we keep the *better* endpoint of the two — the one whose invariant we already know — and replace the other by $m_n$, whose invariant we have just verified by case assumption. [/guided] [/step] [step:Show $(a_n)$ and $(b_n)$ are Cauchy and share a common limit $s \in \mathbb{R}$] By the recursion, $(a_n)$ is non-decreasing and $(b_n)$ is non-increasing (Case 1 raises $a$ and fixes $b$; Case 2 fixes $a$ and lowers $b$). By (P1) and (P4), for $n \ge m \ge 0$, \begin{align*} 0 \le a_n - a_m \le b_m - a_m = \frac{b_0 - a_0}{2^m}, \qquad 0 \le b_m - b_n \le b_m - a_m = \frac{b_0 - a_0}{2^m}. \end{align*} Fix $\varepsilon > 0$. By the [Archimedean Property](/theorems/737), there exists $M \in \mathbb{N}$ with $(b_0 - a_0)/2^M < \varepsilon$ (apply the Archimedean property to the positive real $(b_0 - a_0)/\varepsilon$ to obtain $N \in \mathbb{N}$ with $N > (b_0 - a_0)/\varepsilon$, then use $2^M \ge M + 1 > N$ for $M$ large). For $n, m \ge M$ (WLOG $n \ge m$), \begin{align*} |a_n - a_m| \le \frac{b_0 - a_0}{2^m} \le \frac{b_0 - a_0}{2^M} < \varepsilon, \qquad |b_n - b_m| \le \frac{b_0 - a_0}{2^M} < \varepsilon. \end{align*} Hence $(a_n)$ and $(b_n)$ are Cauchy in $\mathbb{R}$. By the [Completeness of $\mathbb{R}$ via Cauchy Sequences](/theorems/3226), there exist $\alpha, \beta \in \mathbb{R}$ with $a_n \to \alpha$ and $b_n \to \beta$. From $b_n - a_n = (b_0 - a_0)/2^n \to 0$, taking the limit gives $\beta - \alpha = 0$, i.e. $\alpha = \beta =: s \in \mathbb{R}$. [/step] [step:Verify that $s$ is an upper bound of $S$] Let $x \in S$. By (P2), $b_n \ge x$ for every $n \ge 0$. The map $t \mapsto t - x$ is continuous on $\mathbb{R}$, and the sequence $b_n - x$ is non-negative for every $n$. Since $b_n - x \to s - x$ and the set $[0, \infty) \subset \mathbb{R}$ is closed, the limit $s - x$ lies in $[0, \infty)$, i.e. $s - x \ge 0$. (This is the standard "preservation of weak inequalities under limits": if $y_n \ge 0$ for all $n$ and $y_n \to y$, then $y \ge 0$, because otherwise $y < 0$ and the open neighbourhood $(-\infty, 0)$ of $y$ would contain $y_n$ for all large $n$, contradicting $y_n \ge 0$.) Hence \begin{align*} s = \lim_{n \to \infty} b_n \ge x. \end{align*} Since $x \in S$ was arbitrary, $s$ is an upper bound of $S$. [/step] [step:Verify that $s$ is the least upper bound] Let $u \in \mathbb{R}$ be any upper bound of $S$. We must show $s \le u$. Suppose, for contradiction, that $s > u$. Set $\varepsilon := s - u > 0$. Since $a_n \to s$, there exists $N \in \mathbb{N}$ such that $|a_n - s| < \varepsilon$ for all $n \ge N$, hence $a_n > s - \varepsilon = u$ for $n \ge N$. By (P3) at level $N$, there exists $s_N \in S$ with $s_N \ge a_N > u$. This contradicts $u$ being an upper bound of $S$. Therefore $s \le u$, so $s$ is the least upper bound, i.e. $s = \sup S \in \mathbb{R}$. [guided] We argue by contradiction. Let $u \in \mathbb{R}$ be an arbitrary upper bound of $S$; our goal is $s \le u$. The whole point of the construction is that the lower endpoints $a_n$ never overshoot $S$ — by (P3) each $a_n$ is dominated by some $s_n \in S$. If we had a candidate upper bound $u$ strictly below $s$, then since the $a_n$ approximate $s$ from below, eventually $a_n$ would exceed $u$, and the dominator $s_n \in S$ would too — but that contradicts $u$ being an upper bound. Let us make this precise. Suppose, for contradiction, that $s > u$, and define \begin{align*} \varepsilon := s - u > 0. \end{align*} **Step (i): use convergence $a_n \to s$.** By the definition of convergence in $\mathbb{R}$, there exists $N \in \mathbb{N}$ such that \begin{align*} |a_n - s| < \varepsilon \quad \text{for all } n \ge N. \end{align*} In particular, $a_n - s > -\varepsilon$ for $n \ge N$, i.e. \begin{align*} a_n > s - \varepsilon = s - (s - u) = u \quad \text{for all } n \ge N. \end{align*} This is the key inequality: the lower endpoint $a_N$ has crept past the candidate bound $u$. **Step (ii): produce an element of $S$ above $u$.** Apply (P3) at level $N$ from the previous step: there exists $s_N \in S$ with $a_N \le s_N$. Combined with $a_N > u$ from Step (i), \begin{align*} s_N \ge a_N > u. \end{align*} So $s_N \in S$ strictly exceeds $u$. **Step (iii): contradiction.** But $u$ is by hypothesis an upper bound of $S$, so $s_N \le u$ for every $s_N \in S$. This contradicts $s_N > u$. Thus the assumption $s > u$ is impossible, so $s \le u$. Since $u$ was an arbitrary upper bound of $S$, we conclude that $s$ is less than or equal to every upper bound of $S$. Combined with Step 4 (which showed $s$ is itself an upper bound), this means $s$ is the *least* upper bound of $S$: \begin{align*} s = \sup S \in \mathbb{R}. \end{align*} What was the role of (P3)? Without it, we could have constructed $a_n \uparrow s$ with no link back to $S$, and there would be nothing to contradict an alleged upper bound $u < s$. Carrying along the witnesses $s_n \in S$ throughout the recursion is exactly the device that converts "$a_N > u$" into "an element of $S$ exceeds $u$". [/guided] [/step] [step:Conclude] By Steps 4 and 5, $s \in \mathbb{R}$ is an upper bound of $S$ and is $\le$ every upper bound of $S$. Hence $\sup S$ exists in $\mathbb{R}$, completing the proof. [/step]