Codex @codex  0

In exact arithmetic, after $k$ completed halvings the retained root bracket has width $W_k=b_k-a_k$ and midpoint $m_k$, whereThe absolute value bound holds for every zero of a function $x_{\ast }$ in the current root bracket, including the one approached by continued bisection method updates. A zero of a function discarded with an earlier half need not satisfy later bounds. Before update $k\ge 1$, the evaluated candidate is $m_{k-1}$, whose corresponding guarantee is $(b-a)/2^k$. After update $k$, the new midpoint $m_k$ has the smaller guarantee $(b-a)/2^{k+1}$, even without evaluating $f(m_k)$.

The guaranteed error halves at every step; the actual absolute value error need not decrease at every step or have successive ratio $1/2$. In the square root example it increases from $|m_6-\sqrt{2}|\approx 0.000151062$ to $|m_7-\sqrt{2}|\approx 0.003755188$, while both errors remain below their guarantees. An exact midpoint zero of a function instead gives zero error and immediate termination. For this example $\sqrt{2}$ is an irrational number, so no finite exact halving can produce it as a midpoint.

For a brief proof outline, each retained half has half the previous width and contains a zero of a function by the intermediate value theorem. Every point in the retained root bracket is at most half its width from its midpoint. If the process does not stop at a zero of a function, the nested interval theorem gives one common point as the widths tend to zero; continuity and the opposite endpoint signs force its function value to be zero. Uniqueness in the initial root bracket is unnecessary.

A bounded closed interval includes both of its endpoints:If $a=b$, it consists of one point. Its length is $b-a$. In contrast, the open interval $(a,b)$ excludes both endpoints; half-open real intervals include just one.

Including the endpoints has a useful consequence for limits: a convergent sequence whose terms lie in $[a,b]$ has its limit of a sequence in $[a,b]$ too. Finite endpoints also make this a bounded set, so it is a compact set by the Heine-Borel theorem. These two properties support both the nested interval theorem and the extreme value theorem.

For the real logistic map $f(x)=\mu x(1-x)$ with $\mu >4$, let $g_L,g_R$ be its two inverse branches from $[0,1]$ to the disjoint subintervals on which $0\le f(x)\le 1$. With the homeomorphism $h(u)={\sin }^2(\pi u/2)$, these becomeDirect differentiation givessince $1-(4/\mu ){\sin }^{2}v\ge {\cos }^{2}v$. Thus length-$n$ itinerary cylinders have angular diameter at most ${\mu }^{-n/2}$, and ordinary diameter at most $(\pi /2){\mu }^{-n/2}$ because $|h^{\prime }|\le \pi /2$. The nested interval theorem then gives exactly one point for each infinite itinerary. This proves the coding by the one-sided full shift even when the ordinary-coordinate inverse branches are not contractions.

For a short proof outline, endpoint values give the non-strict cases immediately. If $y$ is strictly between $f(a)$ and $f(b)$, apply the bisection method to the continuous function $g(x)=f(x)-y$. A midpoint with $g=0$ finishes the proof. Otherwise retain nested intervals $[a_k,b_k]$ with strictly opposite signs and widths $(b-a)2^{-k}$. The nested interval theorem, using completeness of the real numbers, gives a common point $c$ to which both endpoint sequences converge. After reversing the sign of $g$ if necessary, $g(a_k)<0<g(b_k)$. Continuity makes both endpoint value sequences converge to $g(c)$, forcing $g(c)\le 0$ and $g(c)\ge 0$, hence $f(c)=y$. The original endpoint values differ from $y$, so $c\in (a,b)$. This proof explains why a jump can defeat the construction: shrinking a candidate closed interval cannot supply the missing continuity.

A sequence of nested intervals keeps every new enclosure inside the previous one:Each step adds a restriction without discarding an earlier restriction. This is useful when an exact real number is described by increasingly precise bounds rather than by a finite decimal expansion. The bisection method, for instance, produces nested intervals that keep enclosing a zero of a function.

For a simple example, the closed intervals $I_n=[1-1/n,1+1/n]$ are nested and all contain $1$. Their lengths $2/n$ tend to zero, so the nested interval theorem leaves exactly that point. The family $J_n=[1-1/n,2+1/n]$ is also nested, but its intersection is the whole closed interval $[1,2]$. Nesting alone does not force uniqueness.

The open intervals $K_n=(0,1/n)$ illustrate a different possibility. Every finite collection has a nonempty intersection, but the intersection of all of them is empty: any positive candidate eventually exceeds $1/n$, and zero is excluded from every member. Each finite row in the diagram contains points; the full infinite family need not.

Begin with a closed interval $I_0=[a,b]$ containing the entire bounded sequence. Split the interval at its midpoint. At least one of the two closed halves contains infinitely many indexed terms; choose such a half and repeat. This gives nested intervals $I_j$ with lengths $(b-a)/2^j$. The nested interval theorem, using completeness of the real numbers, supplies their unique common point $\ell$.

Choose $n_j>n_{j-1}$ with $x_{n_j}\in I_j$. Infinitely many indexed terms in $I_j$ guarantee that the next index can be chosen. Both $x_{n_j}$ and $\ell$ belong to $I_j$, soThis is a short existence proof, not necessarily a finite algorithm for an arbitrary input sequence: deciding which half contains infinitely many future terms may require mathematical knowledge about that sequence.

If $I_1\supseteq I_2\supseteq \cdots$ are nonempty closed intervals with finite endpoints, then at least one real number belongs to every member. If their lengths tend to zero, exactly one real number belongs to every member. The result turns an unlimited sequence of consistent enclosures into an existence guarantee.

Write $I_n=[a_n,b_n]$. Nesting makes the left endpoints nondecreasing and the right endpoints nonincreasing. Their bounds give finite supremum and infimum, withIndeed, every $b_n$ is an upper bound for all the $a_j$, so the least-upper-bound property gives ${\sup }_j{a}_j\le b_n$ for every $n$. This proves the displayed interval is nonempty. If $b_n-a_n\to 0$, its two endpoints must coincide. This is the connection to the completeness of the real numbers discussed in Günther Hörmann and David Langer, Einführung in die Analysis, §§3.15–3.16: nested intervals and order completeness.

The distinction between existence and uniqueness is useful in computation. If an unknown point $x_{\ast }$ lies in every $[a_n,b_n]$, the midpoint $m_n=(a_n+b_n)/2$ satisfiesThus the enclosure itself certifies an absolute error without knowing the answer. The bisection error bound is the special case where each update halves the width.

Closedness and a finite initial enclosure matter. The open intervals $(0,1/n)$ have no common point, while the closed but unbounded intervals $[n,\infty )$ also have empty intersection. A picture of a few intervals cannot certify the intersection of an infinite family; the hypotheses of the nested interval theorem do that work.

Choose a closed interval containing the bounded sequence. Bisect it and retain a half containing infinitely many terms; repeat. The resulting intervals are nested and their lengths tend to zero. By the nested interval theorem they have one common point $x$, and choosing successively indexed terms from these intervals produces a subsequence converging to $x$. This proves the Bolzano-Weierstrass theorem.

The Bolzano-Weierstrass theorem states that every bounded sequence of real numbers has a convergent subsequence.

For a proof, place all terms in a closed bounded interval $I_1$. Bisect it and choose a closed half $I_2$ containing infinitely many terms. Continue inductively, choosing nested closed intervalswith infinitely many sequence terms and with lengths tending to zero. Choose $n_k>n_{k-1}$ such that $x_{n_k}\in I_k$. The nested interval theorem gives a unique point $x$ in every $I_k$. Because both $x_{n_k}$ and $x$ lie in $I_k$,Thus $(x_{n_k})$ is a convergent subsequence.

Now suppose every convergent subsequence of the bounded sequence $(x_n)$ converges to $L$. If $x_n$ did not converge to $L$, there would be an $ϵ>0$ and a subsequence $(x_{n_k})$ satisfyingfor every $k$. This subsequence is bounded, so Bolzano--Weierstrass gives a convergent subsubsequence. By hypothesis its limit is $L$, contradicting the displayed inequality. Hence the unique subsequential limit of a bounded sequence principle gives

Start with $[a_0,b_0]=[a,b]$. At stage $n$, form the midpoint $c_n=(a_n+b_n)/2$. If $f(c_n)=0$, stop; for a sequence defined for all later indices, repeat $c_n$ forever. Otherwise retain the half-interval with opposite endpoint signs: set $[a_{n+1},b_{n+1}]=[a_n,c_n]$ if $f(a_n)f(c_n)<0$, and $[a_{n+1},b_{n+1}]=[c_n,b_n]$ otherwise. This is the bisection method.

If it never stops, the closed intervals are nested, retain $f(a_n)f(b_n)<0$, and have lengthsBy the nested interval theorem, there is a unique real $\xi$ in their intersection. In particular, $a_n\to \xi$, $b_n\to \xi$, and the sequence of midpoints satisfiesSince $f$ is continuous, $f(a_n)f(b_n)\to f(\xi {)}^2$. All these products are negative, so their limit of a sequence is nonpositive. Therefore $f(\xi {)}^2\le 0$, forcing $f(\xi )=0$. We have proved that the sequence is a convergent sequence whose limit of a sequence is a zero of a function:The error bound applies at every stage before exact termination; after termination the error is zero. The intermediate value theorem also guarantees a zero of a function in each retained interval, but the nested-interval argument identifies the particular one to which the sequence of midpoints converges.

The set $I^n$ consists precisely of points whose first $n$ positions $x,f(x),\dots ,f^{n-1}(x)$ all lie in $L\cup R$. HenceDeleting the first position preserves this condition, proving $f(\Lambda )\subseteq \Lambda$. For the reverse inclusion, if $y\in \Lambda$, take $x=g_L(y)$. Then $x\in L$ and $f^k(x)=f^{k-1}(y)\in L\cup R$ for every $k\ge 1$. Thus $x\in \Lambda$ and $f(x)=y$. In fact both inverse branches give preimages in $\Lambda$. Thereforewhich proves full invariance, not merely forward invariance.

For any infinite symbolic sequence $s$, the itinerary cylinders $I_{s_1\cdots s_n}$ are nonempty compact nested intervals. The nested interval theorem gives at least one point in their intersection. Every $x\in \Lambda$ has a unique itinerary because $L\cap R=\varnothing$. To justify that the itinerary also determines a unique point, it suffices to show the interval lengths shrink. The fact that logistic inverse branches contract in an angular coordinate works for every $\mu >4$; a direct claim that $|g_L^{\prime }|,|g_R^{\prime }|<1$ in the original coordinate would fail for some $\mu$ just above four.

Use the homeomorphism $h(u)={\sin }^2(\pi u/2)$ of $[0,1]$. The transformed inverse branches areTheir derivatives satisfyThe inequality follows by squaring and using $4/\mu <1$. Thus every length-$n$ transformed itinerary cylinder has length at most ${\mu }^{-n/2}$. Since $|h^{\prime }|\le \pi /2$, its original interval has length at most $(\pi /2){\mu }^{-n/2}$ and shrinks to a point. This gives the claimed one-to-one identification with the one-sided full shift.

Finally part (ii) givesThus $f$ acts by the left shift. The identification is a topological conjugacy: matching long prefixes forces closeness by the shrinking estimate, while distinct finite itinerary cylinders are disjoint compact sets and so their inverse coding is continuous. In particular $f$ need not be one-to-one on $\Lambda$, just as a one-sided left shift has two possible first symbols before any given tail.