The least upper bound property of the real numbers (lub) can be used to prove the intermediate value theorem (IVT) as well as the Bolzano-Weierstrass theorem (BWT).
I've been trying to prove the IVT without the lub property, nor the Archimedean property, using the BWT as an axiom. The sketch of my proof goes as follows:
Lemma: If $u$ is a bounded sequence of reals such that $u_{n+1}-u_n \xrightarrow[n \to +\infty]{} 0$ then the set of
accumulation points of $u$ is an interval.
I do not give a proof of this fact as it can be found elsewhere and in more general forms,e.g. in
- Show that set of all accumulation points is the closed interval $[\liminf_{n\rightarrow\infty}(x_n),\limsup_{n\rightarrow\infty}(x_n)]$
- Set of cluster points of a bounded sequence.
- If a sequence satisfies $\lim\limits_{n\to\infty}|a_{n+1} – a_n|=0$ then the set of its limit points is connected
Proof attempt:
Given a function $f$ that is continuous on an interval I, take $(a,b)\in I^2$ s.t. $a<b$ and $f(a)\leqslant 0 \leqslant f(b)$:
- There exists a sequence $(x_n)_{n \in \mathbb{N} }$ dense in $[a,b]$ such that
$x_{n+1}-x_n \xrightarrow[n \to +\infty]{} 0$.
For instance $$x_n=a+(b-a)\sum_{k=0}^{n}\left(-\frac{1}{2}\right)^{\left\lfloor{\log_2(k+1)}\right\rfloor}$$
where $\lfloor \log_2(x)\rfloor$ can be defined without the lub for all integers $x$ as the biggest integer $n$ such that $2^n \leqslant x$. The above expression is essentially just a closed form for a sequence that "bounces" between $a$ and $b$ with increasingly smaller steps (halved at each turn). The subsequences
$(x_{2^{2n+2}-2})_{n\in \mathbb{N}}$ and $(x_{2^{2n+1}-2})_{n\in \mathbb{N}}$ converge (are constant) to $a$ and $b$ respectively, so the lemma applies.
EDIT As pointed out in the comments, showing that the step sizes go to $0$ requires some care to avoid using the Archimedean property.
It can be shown that $\forall n \in \mathbb{N}, 0 \leqslant 2^{-n}\leqslant 1$. This sequence is bounded thus has a convergent subsequence $(2^{-\varphi{(n)}})$. Let $l$ be its limit and assume for the sake of contradiction that $l>0$.
Notice there exists a sequence $(m_n)$ of nonzero natural numbers such that $\forall n \in \mathbb{N}, 2^{-\varphi{(n+1)}} = 2^{-{m_n}} 2^{-\varphi{(n)}}$. Since $(2^{-\varphi{(n+1)}})$ also converges to $l>0$, $(2^{-{m_n}})$ must converge to $1$ which means $m_n = 0$ for large enough $n$. However $\varphi$ can be chosen strictly increasing, a contradiction. Therefore $l=0$
so we can take $(2^{-\varphi{(n)}})$ as a sequence of step sizes. It seems there's no expression in terms of common functions like the one above because $\varphi$ was not constructed but merely assumed to exist. However we can construct a fitting $(x_n)$ sequence by induction from the sequence above.
-
It can be shown using the BWT that $f$ is uniformly continuous over $[a,b]$ (Heine's Theorem).
-
Using uniform continuity, one can show that the sequence $(f(x_n))_{n\in \mathbb{N}}$ satisfies the hypotheses of the lemma.
-
$f(a)$ and $f(b)$ belong to the set of accumulation points of $(f(x_n))_{n\in \mathbb{N}}$ since $(x_n)_{n\in \mathbb{N}}$ is dense in $[a,b]$ and $f$ is continuous.
-
Therefore $[f(a),f(b)]$ is included in this set, so $0$ is an accumulation point of the above sequence. Apply BW once more to extract a convergent subsequence of the (bounded) sequence whose image goes to $0$. Its limit is a real number $l \in [a,b] $ s.t. $f(l)=0 \square$.
Questions:
- Is my proof correct ?
- Does it use the least upper bound theorem/property or the Archimedean property in disguise ?
- Are there simpler/shorter direct proofs of BWT=>IVT ?
Context: I'm currently an engineering college student taking the equivalent of a calculus/real analysis class (more rigorous than a standard calculus course but we didn't construct the reals etc.).
The following MSE post is related and can be used to show BWT=>IVT indirectly through the lub property, but I didn't find any direct proof:
Prove the least upper bound property using Bolzano Weierstrass theorem
Best Answer
Answers:
EDIT In comments, I have been asked how I can prove the very last statement of point 3., i.e. "that limit point is a zero of $f$". Let me answer that. We have actually constructed two sequences of points in $[0, 1]$; one is $(x_n^-)$, at which $f(x_n^-)<0$, the other is $(x_n^+)$, at which $f(x_n^+)>0$. By compactness, we may choose subsequences in such a way that both sequences converge, and by construction, they must converge to the same limit point $x\in[0, 1]$; $$ x_n^-\to x, \quad x_n^+\to x.$$ By the first limit, $f(x)\le 0$. By the second limit, $f(x)\ge 0$. The only possibility is $f(x)=0$.
Comment 1. This is not different in spirit from the construction of the original post. Only the method used to choose points is different. Rather than "bounce through $[0, 1]$" (citing the original question), the bisection method chooses points based on the sign of $f$. It seems to me a more rational way of choosing points. Presumably it is also more efficient in practice.
Comment 2. However, if we want efficiency, both the bisection method and the method of this question fall short of superior ones, such as Newton's method. I suspect that all superior methods do rely on higher assumptions on $f$, though, such as differentiability.