Proof of Bounds for Darboux Sums, Monotonicity under Refinement, the Supremum of the Lower Sums and the Infimum of the Upper Sums, and Concatenation of Partitions

For a partition $R$ of $[a,b]$ we use its $n$ and its increasing listing $x$ of The Increasing Listing of a Partition: Endpoints, Lengths, Covering, Unions, Inserting a Point, Concatenation and Uniform Partitions (i), and $S_{i}$ for $i\in[n]$, as in Upper and Lower Darboux Sums of a Bounded Function on a Partition (i), and we write $M_{i}=M(i)$ and $m_{i}=m(i)$ for the values of the maps $M,m:[n]\to\mathbb{R}$ of Upper and Lower Darboux Sums of a Bounded Function on a Partition (i), so that $U(f,R)=\sum_{i=1}^{n}M_{i}(x_{i+1}-x_{i})$ and $L(f,R)=\sum_{i=1}^{n}m_{i}(x_{i+1}-x_{i})$ by Upper and Lower Darboux Sums of a Bounded Function on a Partition (ii) and Upper and Lower Darboux Sums of a Bounded Function on a Partition (iii); sums $\sum_{i=1}^{n}$ are sums over the finite set $[n]$ (Natural Numbers as Indices: ℕ ⊆ ℕ₀, 1 ∈ ℕ₀, and the Two Readings of an Operation from 1 to n (v)). By Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order (iv) and Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order (i), $M_{i}$ is an upper bound of $S_{i}$ with $M_{i}\le c$ for every upper bound $c$ of $S_{i}$, and $m_{i}$ is a lower bound of $S_{i}$ with $c\le m_{i}$ for every lower bound $c$ of $S_{i}$. The elements of $S_{i}$ are the values $f(t)$ with $t\in[x_{i},x_{i+1}]$, by Upper and Lower Darboux Sums of a Bounded Function on a Partition (i).

Proof of (i). Let $n$ and $x$ belong to $P$, and let $i\in[n]$. Every element of $S_{i}$ is a value $f(t)$ with $t\in[x_{i},x_{i+1}]\subseteq[a,b]$, so $\ell$ is a lower bound and $C$ an upper bound of $S_{i}$; hence $\ell\le m_{i}$ and $M_{i}\le C$. As $x_{i}\in[x_{i},x_{i+1}]$, $f(x_{i})\in S_{i}$, so $m_{i}\le f(x_{i})\le M_{i}$. Thus $\ell\le m_{i}\le M_{i}\le C$. Since $x_{i+1}-x_{i}>0$ by The Increasing Listing of a Partition: Endpoints, Lengths, Covering, Unions, Inserting a Point, Concatenation and Uniform Partitions (iii),

$$\ell\,(x_{i+1}-x_{i})\le m_{i}(x_{i+1}-x_{i})\le M_{i}(x_{i+1}-x_{i})\le C\,(x_{i+1}-x_{i})$$

for every $i\in[n]$. Summing over $i\in[n]$ by Finite Sums in a Commutative Ring and in an Ordered Field: Distributivity, Differences, Telescoping, Constant Terms, Comparison and the Triangle Inequality (v), and using Finite Sums in a Commutative Ring and in an Ordered Field: Distributivity, Differences, Telescoping, Constant Terms, Comparison and the Triangle Inequality (i) and $\sum_{i=1}^{n}(x_{i+1}-x_{i})=b-a$ from The Increasing Listing of a Partition: Endpoints, Lengths, Covering, Unions, Inserting a Point, Concatenation and Uniform Partitions (iii), we obtain $\ell(b-a)\le L(f,P)\le U(f,P)\le C(b-a)$, by Upper and Lower Darboux Sums of a Bounded Function on a Partition (iii) and Upper and Lower Darboux Sums of a Bounded Function on a Partition (ii).

In particular, with $\ell=-B$ and $C=B$, which satisfy $-B\le f(t)\le B$ for every $t\in[a,b]$, we have $L(f,R)\le U(f,R)$ for every partition $R$ of $[a,b]$.

Proof of (ii). Step 1: inserting one point. Let $R$ be a partition of $[a,b]$, with $n$ and $x$, let $y\in[a,b]$ with $y\notin R$, and let $R'=R\cup\{y\}$. By The Increasing Listing of a Partition: Endpoints, Lengths, Covering, Unions, Inserting a Point, Concatenation and Uniform Partitions (vi), $R'$ is a partition of $[a,b]$ whose $n$ of The Increasing Listing of a Partition: Endpoints, Lengths, Covering, Unions, Inserting a Point, Concatenation and Uniform Partitions (i) is $n+1$, there is $j\in[n]$ with $x_{j}<y<x_{j+1}$, and the increasing listing $z$ of $R'$ satisfies $z_{k}=x_{k}$ for $k\in[n+1]$ with $k\le j$, $z_{j+1}=y$, and $z_{k+1}=x_{k}$ for $k\in[n+1]$ with $j<k$. For $l\in[n+1]$ let $S'_{l}$ be the sets and $M'_{l}=M'(l)$ and $m'_{l}=m'(l)$ the values of the maps $M',m':[n+1]\to\mathbb{R}$ of Upper and Lower Darboux Sums of a Bounded Function on a Partition (i) for $R'$, and put

$$T_{i}=m_{i}(x_{i+1}-x_{i}),\quad V_{i}=M_{i}(x_{i+1}-x_{i})\quad(i\in[n]),\qquad T'_{l}=m'_{l}(z_{l+1}-z_{l}),\quad V'_{l}=M'_{l}(z_{l+1}-z_{l})\quad(l\in[n+1]).$$

As $j\in[n]\subseteq[n+1]$, Bijections between Intervals: the Gap Map and the Reversal (i) gives a bijection $g$ from $[n]$ onto $[n+1]\setminus\{j\}$ with $g(k)=k$ for $k<j$ and $g(k)=k+1$ for $k\ge j$; in particular $g(j)=j+1$. Let $g'$ be the restriction of $g$ to $[n]\setminus\{j\}$; by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction (ix), $g'(k)=g(k)$ for every $k\in[n]\setminus\{j\}$. As $g$ is injective and $g(j)=j+1$, these values lie in $[n+1]\setminus\{j,j+1\}$ and are distinct for distinct $k$; and every $l\in[n+1]\setminus\{j,j+1\}$ is $g(k)$ for some $k\in[n]$, with $k\neq j$ as $l\neq j+1$. So $g'$ is a bijection from $[n]\setminus\{j\}$ onto $[n+1]\setminus\{j,j+1\}$, by Injective, Surjective and Bijective Functions between Classes (iii).

Let $k\in[n]$ with $k\neq j$; we show $T'_{g(k)}=T_{k}$ and $V'_{g(k)}=V_{k}$. By Arithmetic and Order of the Natural Numbers (vii), $k<j$ or $j<k$. If $k<j$, then $j=k+d$ for some $d\in\mathbb{N}$ by Arithmetic and Order of the Natural Numbers (viii), and $1\le d$ by Arithmetic and Order of the Natural Numbers (x), so $k+1\le j$ by Arithmetic and Order of the Natural Numbers (ix); hence $z_{k}=x_{k}$ and $z_{k+1}=x_{k+1}$, and $g(k)=k$. If $j<k$, then $j<k+1$ by Arithmetic and Order of the Natural Numbers (xi) and Arithmetic and Order of the Natural Numbers (vi), so $z_{k+1}=x_{k}$ and $z_{(k+1)+1}=x_{k+1}$, and $g(k)=k+1$. In both cases $[z_{g(k)},z_{g(k)+1}]=[x_{k},x_{k+1}]$, so $S'_{g(k)}=S_{k}$, and the claim follows.

Next, $z_{j}=x_{j}$, $z_{j+1}=y$, and, as $j<j+1$, $z_{(j+1)+1}=x_{j+1}$. So $[z_{j},z_{j+1}]=[x_{j},y]$ and $[z_{j+1},z_{(j+1)+1}]=[y,x_{j+1}]$, both contained in $[x_{j},x_{j+1}]$; hence $S'_{j}\subseteq S_{j}$ and $S'_{j+1}\subseteq S_{j}$. Then $m_{j}$ is a lower bound and $M_{j}$ an upper bound of $S'_{j}$ and of $S'_{j+1}$, so $m_{j}\le m'_{j}$, $m_{j}\le m'_{j+1}$, $M'_{j}\le M_{j}$ and $M'_{j+1}\le M_{j}$. As $y-x_{j}>0$ and $x_{j+1}-y>0$,

$$T'_{j}+T'_{j+1}\ge m_{j}(y-x_{j})+m_{j}(x_{j+1}-y)=T_{j},\qquad V'_{j}+V'_{j+1}\le M_{j}(y-x_{j})+M_{j}(x_{j+1}-y)=V_{j}.$$

Now $[n]$ is the disjoint union of $[n]\setminus\{j\}$ and $\{j\}$, and $[n+1]$ the disjoint union of $[n+1]\setminus\{j,j+1\}$, $\{j\}$ and $\{j+1\}$, as $j\neq j+1$. By Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (ii), Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (i) and Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (iii), the last applied to the restriction of $g$ above,

$$L(f,R)=\sum_{k\in[n]\setminus\{j\}}T_{k}+T_{j},\qquad L(f,R')=\sum_{l\in[n+1]\setminus\{j,j+1\}}T'_{l}+T'_{j}+T'_{j+1}=\sum_{k\in[n]\setminus\{j\}}T'_{g(k)}+T'_{j}+T'_{j+1}=\sum_{k\in[n]\setminus\{j\}}T_{k}+T'_{j}+T'_{j+1},$$

and likewise for $U(f,R)$ and $U(f,R')$ with $V$ and $V'$. Hence $L(f,R')-L(f,R)=T'_{j}+T'_{j+1}-T_{j}\ge0$ and $U(f,R)-U(f,R')=V_{j}-V'_{j}-V'_{j+1}\ge0$. So

$$L(f,R)\le L(f,R\cup\{y\})\quad\text{and}\quad U(f,R\cup\{y\})\le U(f,R),$$

and this also holds when $y\in R$, as then $R\cup\{y\}=R$.

Step 2: adding a finite set. For a set $C$ let $\varphi(C)$ be the statement: for every partition $R$ of $[a,b]$ such that $R\cup C$ is a partition of $[a,b]$, $L(f,R)\le L(f,R\cup C)$ and $U(f,R\cup C)\le U(f,R)$. It is given by a predicative formula with parameters $a$, $b$, $f$ and those of Predicative Formulas for Upper and Lower Darboux Sums, and the Maps and Sets of Darboux Sums over All Partitions (i): with $\psi_{U}$ and $\psi_{L}$ predicative formulas expressing the conditions "$f$ is a bounded map $f:[a,b]\to\mathbb{R}$, $R\in\Pi_{a,b}$ and $z=U(f,R)$", respectively with $L(f,R)$, on $f$, $R$ and $z$, which Predicative Formulas for Upper and Lower Darboux Sums, and the Maps and Sets of Darboux Sums over All Partitions (i) provides, $\varphi(C)$ is $\forall R\,\forall D\,\forall s\,\forall s'\,\forall r\,\forall r'\,\bigl((D=R\cup C\wedge\psi_{L}(f,R,s)\wedge\psi_{L}(f,D,s')\wedge\psi_{U}(f,R,r)\wedge\psi_{U}(f,D,r'))\Rightarrow(s\le s'\wedge r'\le r)\bigr)$, with $D=R\cup C$ as in Predicativity of Expressions with Abbreviations, and Symbol-Free Forms of the Basic Defined Set Symbols (ix), predicative by Predicativity of Expressions with Abbreviations, and Symbol-Free Forms of the Basic Defined Set Symbols (i). $\varphi(\emptyset)$ holds as $R\cup\emptyset=R$. Let $C$ be a finite set with $\varphi(C)$ and $w$ a set with $w\notin C$, and let $R$ be a partition of $[a,b]$ such that $R\cup(C\cup\{w\})$ is a partition of $[a,b]$. Then $w\in[a,b]$, so $R_{1}=R\cup\{w\}$ is a partition of $[a,b]$ by The Increasing Listing of a Partition: Endpoints, Lengths, Covering, Unions, Inserting a Point, Concatenation and Uniform Partitions (vi), and Step 1 gives $L(f,R)\le L(f,R_{1})$ and $U(f,R_{1})\le U(f,R)$. As $R_{1}\cup C=R\cup(C\cup\{w\})$ is a partition, $\varphi(C)$ applied to $R_{1}$ gives $L(f,R_{1})\le L(f,R_{1}\cup C)$ and $U(f,R_{1}\cup C)\le U(f,R_{1})$. Combining, $\varphi(C\cup\{w\})$ holds. By induction over finite sets, Induction over Finite Sets, and Predicative Formulas for the Segments [n] and for Finiteness (iii), $\varphi(C)$ holds for every finite set $C$.

Step 3. Let $Q$ refine $P$, that is $P\subseteq Q$ by Partitions of a Closed Interval, the Set of Partitions, and Refinements (iii). Then $C=Q\setminus P$ is finite by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (iv), as $Q$ is finite, and $P\cup C=Q$ is a partition. By Step 2, $L(f,P)\le L(f,Q)$ and $U(f,Q)\le U(f,P)$; and $L(f,Q)\le U(f,Q)$ by (i), applied with $Q$ in place of $P$, $\ell=-B$ and $C=B$.

Proof of (iii). By The Increasing Listing of a Partition: Endpoints, Lengths, Covering, Unions, Inserting a Point, Concatenation and Uniform Partitions (v), $P\cup Q$ is a partition of $[a,b]$ refining $P$ and $Q$. By (ii), applied to $P$ and to $Q$, $L(f,P)\le L(f,P\cup Q)\le U(f,P\cup Q)\le U(f,Q)$.

Proof of (iv). Let $\Pi_{a,b}$ be the set of partitions of $[a,b]$ (Partitions of a Closed Interval, the Set of Partitions, and Refinements (ii)). By Predicative Formulas for Upper and Lower Darboux Sums, and the Maps and Sets of Darboux Sums over All Partitions (ii), $\mathcal{L}=\{L(f,R):R\in\Pi_{a,b}\}$ and $\mathcal{U}=\{U(f,R):R\in\Pi_{a,b}\}$ are subsets of $\mathbb{R}$ whose elements are the lower sums $L(f,R)$, respectively the upper sums $U(f,R)$, $R$ ranging over the partitions of $[a,b]$. The set $Q_{0}=\{a,b\}=\{a\}\cup\{b\}$ is finite by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (iii) and Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (v), is contained in $[a,b]$ and contains $a$ and $b$, so it is a partition of $[a,b]$ by Partitions of a Closed Interval, the Set of Partitions, and Refinements (i); hence $\mathcal{L}$ and $\mathcal{U}$ are nonempty. By (iii), $U(f,Q_{0})$ is an upper bound of $\mathcal{L}$ and $L(f,Q_{0})$ a lower bound of $\mathcal{U}$, so $\mathcal{L}$ has a supremum $\lambda_{*}$ and $\mathcal{U}$ an infimum $\lambda^{*}$ in $\mathbb{R}$, by The Real Line: Standing Notation and Background for Calculus on Intervals (iii). By Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order (i), the upper bounds of $\mathcal{L}$ in $\mathbb{R}$ are the $\mu\in\mathbb{R}$ with $L(f,R)\le\mu$ for every partition $R$ of $[a,b]$, and by Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order (iv) $\lambda_{*}$ is one of them and lies below all of them: so $\lambda_{*}$ has the two properties stated. If $\lambda'\in\mathbb{R}$ has them too, then $\lambda'\le\lambda_{*}$, as $\lambda_{*}$ is an upper bound in the sense of the first property, and $\lambda_{*}\le\lambda'$ likewise; so $\lambda'=\lambda_{*}$. In the same way, the lower bounds of $\mathcal{U}$ in $\mathbb{R}$ are the $\mu\in\mathbb{R}$ with $\mu\le U(f,R)$ for every partition $R$, and $\lambda^{*}$ is the only real number with the two properties stated for it. Finally, for every partition $Q$ of $[a,b]$, $U(f,Q)$ is an upper bound of $\mathcal{L}$ by (iii), so $\lambda_{*}\le U(f,Q)$; thus $\lambda_{*}\le U(f,R)$ for every partition $R$, and $\lambda_{*}\le\lambda^{*}$ by the second property of $\lambda^{*}$.

Proof of (v). As $a<c<b$, $c\in[a,b]$, so $[a,c]\subseteq[a,b]$ and $[c,b]\subseteq[a,b]$ by Basic Facts about Intervals of the Real Line (v) and Basic Facts about Intervals of the Real Line (ii). By Domains and Restrictions of Maps (ii) and Domains and Restrictions of Maps (iii), $f_{1}=f|_{[a,c]}$ is a map $f_{1}:[a,c]\to\mathbb{R}$ with $f_{1}(t)=f(t)$ for $t\in[a,c]$, and $f_{2}=f|_{[c,b]}$ a map $f_{2}:[c,b]\to\mathbb{R}$ with $f_{2}(t)=f(t)$ for $t\in[c,b]$; so $|f_{1}(t)|\le B$ and $|f_{2}(t)|\le B$ on their domains, and both are bounded. By The Increasing Listing of a Partition: Endpoints, Lengths, Covering, Unions, Inserting a Point, Concatenation and Uniform Partitions (vii), $P_{1}\cup P_{2}$ is a partition of $[a,b]$; with $p,q\in\mathbb{N}$ and $y:[p+1]\to P_{1}$, $z:[q+1]\to P_{2}$ the $n$ and the listings of The Increasing Listing of a Partition: Endpoints, Lengths, Covering, Unions, Inserting a Point, Concatenation and Uniform Partitions (i) for $P_{1}$ and $P_{2}$, the $n$ of $P_{1}\cup P_{2}$ is $p+q$ and its listing $x$ satisfies $x_{i}=y_{i}$ for $i\in[p+1]$ and $x_{p+j}=z_{j}$ for $j\in[q+1]$.

Let $M,m:[p+q]\to\mathbb{R}$, $M^{1},m^{1}:[p]\to\mathbb{R}$ and $M^{2},m^{2}:[q]\to\mathbb{R}$ be the maps of Upper and Lower Darboux Sums of a Bounded Function on a Partition (i) for $f$ and $P_{1}\cup P_{2}$, for $f_{1}$ and $P_{1}$, and for $f_{2}$ and $P_{2}$. Let $i\in[p]$. Then $i,i+1\in[p+1]$ by The Increasing Listing of a Partition: Endpoints, Lengths, Covering, Unions, Inserting a Point, Concatenation and Uniform Partitions (ii), so $x_{i}=y_{i}$ and $x_{i+1}=y_{i+1}$, and $[y_{i},y_{i+1}]\subseteq[a,c]$ as $y_{i},y_{i+1}\in P_{1}\subseteq[a,c]$. Hence, by Upper and Lower Darboux Sums of a Bounded Function on a Partition (i), the set of values of $f$ on $[x_{i},x_{i+1}]$ and the set of values of $f_{1}$ on $[y_{i},y_{i+1}]$ have the same elements, so they are equal, and $M(i)=M^{1}(i)$, $m(i)=m^{1}(i)$ and $x_{i+1}-x_{i}=y_{i+1}-y_{i}$. Let $j\in[q]$. Then $j,j+1\in[q+1]$, so $x_{p+j}=z_{j}$ and $x_{p+j+1}=x_{p+(j+1)}=z_{j+1}$ by Arithmetic and Order of the Natural Numbers (ii), and $p+j\in[p+q]$ by Splitting the Segment [m+n] into [m] and a Shifted Copy of [n] (ii); in the same way, as $[z_{j},z_{j+1}]\subseteq[c,b]$, $M(p+j)=M^{2}(j)$, $m(p+j)=m^{2}(j)$ and $x_{p+j+1}-x_{p+j}=z_{j+1}-z_{j}$.

Let $T(k)=M(k)\,(x_{k+1}-x_{k})$ for $k\in[p+q]$. By Splitting the Segment [m+n] into [m] and a Shifted Copy of [n] (i) and Splitting the Segment [m+n] into [m] and a Shifted Copy of [n] (iii), $[p+q]$ is the union of the disjoint sets $[p]$ and $[p+q]\setminus[p]$, and by Splitting the Segment [m+n] into [m] and a Shifted Copy of [n] (ii), $j\mapsto p+j$ is a bijection from $[q]$ onto $[p+q]\setminus[p]$. By Upper and Lower Darboux Sums of a Bounded Function on a Partition (ii), Natural Numbers as Indices: ℕ ⊆ ℕ₀, 1 ∈ ℕ₀, and the Two Readings of an Operation from 1 to n (v), Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (ii) and Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (iii),

$$U(f,P_{1}\cup P_{2})=\sum_{k\in[p]}T(k)+\sum_{k\in[p+q]\setminus[p]}T(k)=\sum_{i\in[p]}M^{1}(i)\,(y_{i+1}-y_{i})+\sum_{j\in[q]}M^{2}(j)\,(z_{j+1}-z_{j})=U(f_{1},P_{1})+U(f_{2},P_{2}),$$

the last step again by Upper and Lower Darboux Sums of a Bounded Function on a Partition (ii) and Natural Numbers as Indices: ℕ ⊆ ℕ₀, 1 ∈ ℕ₀, and the Two Readings of an Operation from 1 to n (v). The same computation with $m$, $m^{1}$ and $m^{2}$ and Upper and Lower Darboux Sums of a Bounded Function on a Partition (iii) gives $L(f,P_{1}\cup P_{2})=L(f_{1},P_{1})+L(f_{2},P_{2})$.