Partition of $[a,b]$ as a finite strictly increasing list $a=t_0<t_1<\cdots <t_n=b$, its subintervals and their lengths, its mesh, refinement, and the common refinement of two partitions

Standing hypothesis for this page. Throughout, $\mathbb{R}$ is the complete ordered field (Complete ordered field (least-upper-bound property), Ordered field), $\mathbb{N}$ is the set of natural numbers and contains $0$ (The natural numbers $\mathbb{N}$ (von Neumann), Order on the natural numbers), $\iota :\mathbb{N}\to \mathbb{R}$ is the canonical natural (The canonical natural $\iota (n)=n\cdot 1_F$ of a field), and $a,b$ are reals with

$a<b\mathrm{.}$

Intervals and their lengths are those of Intervals of $\mathbb{R}$: the nine order-convex forms, nondegeneracy, and length; finite sums are those of Finite sums and finite products, by recursion, indexed as ${\sum }_{i<n}$ over $i\in \mathbb{N}$.

Partitions

A partition of $[a,b]$ is a pair $P=(n,t)$ consisting of a natural number $n\ge 1$ and a sequence $t:\mathbb{N}\to \mathbb{R}$ (Sequences of reals: bounded, eventually, frequently, tails, subsequences) with

$t_0=a,t_i<t_{i+1}\text{ for every }i<n,t_k=b\text{ for every }k\ge n\mathrm{.}$

The tail convention on the third clause is bookkeeping only: it makes $t$ a genuine sequence, so that the finite-sum laws of Laws of finite sums and finite products apply to it verbatim, and it costs nothing because no index above $n$ is ever read. The first two clauses say exactly that

$a=t_0<t_1<\dots <t_n=b,$

the last equality because $t_n=b$ by the third clause. In particular $i\mapsto t_i$ is strictly increasing, hence injective, on $\{i\in \mathbb{N}:i\le n\}$ (Injection, surjection, bijection), and $a\le t_i\le b$ for every $i\le n$.

The point set of $P$ is the finite set

$\mathrm{pts}(P):=\{t_i:i\le n\}\subseteq [a,b],a,b\in \mathrm{pts}(P)\mathrm{.}$

The subintervals of $P$ are

$I_i:=[t_i,t_{i+1}](i<n),$

and their lengths are ${\mathrm{\Delta }}_i:=t_{i+1}-t_i$. Each ${\mathrm{\Delta }}_i>0$, so each $I_i$ is a nondegenerate closed bounded interval (Intervals of $\mathbb{R}$: the nine order-convex forms, nondegeneracy, and length). There are $n$ of them and they are indexed from $i=0$, not from $i=1$: the first subinterval is $[t_0,t_1]=[a,t_1]$.

The lengths sum to $b-a$. By the telescoping law, clause 5 of Laws of finite sums and finite products,

${\sum }_{i<n}{\mathrm{\Delta }}_i={\sum }_{i<n}(t_{i+1}-t_i)=t_n-t_0=b-a\mathrm{.}$

The mesh. The set $\{{\mathrm{\Delta }}_i:i<n\}$ is a nonempty finite set of reals, nonempty because $n\ge 1$, so it has a maximum (Every nonempty finite set of reals has a maximum and a minimum, Maximum and minimum of a set). The mesh of $P$ is

$\mathrm{\parallel }P\mathrm{\parallel }:=\max \{{\mathrm{\Delta }}_i:i<n\}>0,$

and ${\mathrm{\Delta }}_i\le \mathrm{\parallel }P\mathrm{\parallel }$ for every $i<n$.

The uniform partition. For a natural $N\ge 1$, the uniform partition of $[a,b]$ into $N$ parts is $U_N:=(N,t)$ with

$t_i:=a+\iota (i)\frac{b-a}{\iota (N)}(i\le N),t_k:=b(k\ge N)\mathrm{.}$

This is a partition: $t_0=a$; $t_N=a+(b-a)=b$; and $t_{i+1}-t_i=(b-a)\mathrm{/}\iota (N)>0$ for $i<N$, because $\iota (N)>0$ and $\iota (i+1)=\iota (i)+1$ (Canonical naturals are positive and strictly increasing, The canonical natural $\iota (n)=n\cdot 1_F$ of a field). Its subinterval lengths are all equal to $(b-a)\mathrm{/}\iota (N)$, so

$\mathrm{\parallel }{U}_N\mathrm{\parallel }=\frac{b-a}{\iota (N)}\mathrm{.}$

A partition is determined by its point set

Claim. If $P=(n,t)$ and $P^{\mathrm{\prime }}=(n^{\mathrm{\prime }},t^{\mathrm{\prime }})$ are partitions of $[a,b]$ with $\mathrm{pts}(P)=\mathrm{pts}(P^{\mathrm{\prime }})$, then $n=n^{\mathrm{\prime }}$ and $t_i=t_i^{\mathrm{\prime }}$ for every $i\le n$.

Proof. First, $t_i=t_i^{\mathrm{\prime }}$ for every $i\le \min \{n,n^{\mathrm{\prime }}\}$, by induction on $i$ (The principle of mathematical induction). For $i=0$ both equal $a$. Suppose $t_j=t_j^{\mathrm{\prime }}$ for all $j\le i$ and $i+1\le \min \{n,n^{\mathrm{\prime }}\}$. The set $S:=\{x\in \mathrm{pts}(P):x>t_i\}$ has $t_{i+1}$ as its least element: $t_{i+1}\in S$, and any $x\in S$ is $t_j$ for some $j\le n$ with $t_j>t_i$, which forces $j>i$ because $t$ is increasing on indices $\le n$, hence $j\ge i+1$ and $x=t_j\ge t_{i+1}$. The same argument in $P^{\mathrm{\prime }}$ makes $t_{i+1}^{\mathrm{\prime }}$ the least element of $\{x\in \mathrm{pts}(P^{\mathrm{\prime }}):x>t_i^{\mathrm{\prime }}\}$, which is the same set $S$, since the point sets agree and $t_i^{\mathrm{\prime }}=t_i$. A set has at most one least element (Maximum and minimum of a set), so $t_{i+1}=t_{i+1}^{\mathrm{\prime }}$.

Second, $n=n^{\mathrm{\prime }}$. If $n<n^{\mathrm{\prime }}$ then $t_n^{\mathrm{\prime }}=t_n=b$ by the previous paragraph, while $t_n^{\mathrm{\prime }}<t_{n^{\mathrm{\prime }}}^{\mathrm{\prime }}=b$ because $t^{\mathrm{\prime }}$ is increasing on indices $\le n^{\mathrm{\prime }}$ and $n<n^{\mathrm{\prime }}$; that is impossible. Exchanging the roles of $P$ and $P^{\mathrm{\prime }}$ rules out $n^{\mathrm{\prime }}<n$. $\mathrm{\square }$

So the map $P\mapsto \mathrm{pts}(P)$ is injective, and a partition may be named by its point set whenever one is exhibited.

Inserting a point

Let $P=(n,t)$ be a partition of $[a,b]$ and let $c\in [a,b]$. Define a partition $P+c$ of $[a,b]$ as follows.

• If $c\in \mathrm{pts}(P)$, put $P+c:=P$.
• Otherwise $c\mathrm{\ne }a$ and $c\mathrm{\ne }b$, so $a<c<b$. The set $T:=\{t_i:i\le n\text{ and }{t}_i<c\}$ is a nonempty finite set of reals, nonempty because $t_0=a<c$, so it has a maximum (Every nonempty finite set of reals has a maximum and a minimum); let $i_0\le n$ be the unique index with $t_{i_0}=\max T$, unique because $t$ is injective on indices $\le n$. Then $i_0<n$, since $t_n=b>c$ puts $t_n\mathrm{\notin }T$; and $t_{i_0}<c<t_{i_0+1},$ the right inequality because $t_{i_0+1}\mathrm{\ne }c$ (as $c\mathrm{\notin }\mathrm{pts}(P)$) and $t_{i_0+1}<c$ would put $t_{i_0+1}\in T$ with $t_{i_0+1}>t_{i_0}=\max T$. Put $P+c:=(n+1,s)$ with $s_i:=t_i(i\le i_0),s_{i_0+1}:=c,s_i:=t_{i-1}(i_0+2\le i\le n+1),s_k:=b(k\ge n+1)\mathrm{.}$

In both cases $P+c$ is a partition of $[a,b]$ and

$\mathrm{pts}(P+c)=\mathrm{pts}(P)\cup \{c\},\mathrm{\parallel }P+c\mathrm{\parallel }\le \mathrm{\parallel }P\mathrm{\parallel }\mathrm{.}$

The displayed identity is immediate from the two cases. For the mesh: in the first case nothing changes; in the second the list of subinterval lengths of $P+c$ is that of $P$ with ${\mathrm{\Delta }}_{i_0}$ replaced by the two numbers $c-t_{i_0}$ and $t_{i_0+1}-c$, each of which is smaller than ${\mathrm{\Delta }}_{i_0}=(c-t_{i_0})+(t_{i_0+1}-c)$ because the other is positive. So every length of $P+c$ is at most a length of $P$, and the maximum cannot increase. Finally the index count grows by exactly $1$ in the second case and not at all in the first.

Refinement and the common refinement

$P^{\mathrm{\prime }}$ refines $P$, and is a refinement of $P$, when

$\mathrm{pts}(P)\subseteq \mathrm{pts}(P^{\mathrm{\prime }})\mathrm{.}$

Let $P=(n,t)$ and $Q=(m,s)$ be partitions of $[a,b]$. Applying the recursion theorem (The recursion theorem) to the set $\mathbb{N}\times {\mathcal{P}}_{[a,b]}$, where ${\mathcal{P}}_{[a,b]}$ is the set of partitions of $[a,b]$, with starting element $(0,P)$ and the map $(j,R)\mapsto (j+1,R+s_j)$ — legitimate because $s_j\in [a,b]$ for every $j\in \mathbb{N}$ — gives a unique family $(R_j{)}_{j\in \mathbb{N}}$ of partitions with $R_0=P$ and $R_{j+1}=R_j+s_j$. The common refinement of $P$ and $Q$ is

$P\vee Q:=R_{m+1}\mathrm{.}$

Its point set is the union. By induction on $j$ (The principle of mathematical induction), $\mathrm{pts}(R_j)=\mathrm{pts}(P)\cup \{s_l:l<j\}$; taking $j=m+1$ gives

$\mathrm{pts}(P\vee Q)=\mathrm{pts}(P)\cup \mathrm{pts}(Q)\mathrm{.}$

Hence $P\vee Q$ refines both $P$ and $Q$; by the uniqueness claim above it is the only partition with that point set, so $P\vee Q=Q\vee P$, and

$P^{\mathrm{\prime }}\text{ refines }P⟹P\vee P^{\mathrm{\prime }}=P^{\mathrm{\prime }},$

since then $\mathrm{pts}(P)\cup \mathrm{pts}(P^{\mathrm{\prime }})=\mathrm{pts}(P^{\mathrm{\prime }})$.

Two size bounds, both used later. Writing $n_R$ for the first component of a partition $R$:

$\mathrm{\parallel }P\vee Q\mathrm{\parallel }\le \mathrm{\parallel }P\mathrm{\parallel },n_{P\vee Q}\le n_P+n_Q-1.$

The first is the mesh bound above applied $m+1$ times. For the second, each insertion raises the index count by at most $1$, and the two insertions of $s_0=a$ and $s_m=b$ raise it by $0$, since $a$ and $b$ already lie in $\mathrm{pts}(P)$ and hence in $\mathrm{pts}(R_j)$ for every $j$; so at most $m-1$ of the $m+1$ insertions increase it.

The index map of a refinement

Let $P^{\mathrm{\prime }}=(n^{\mathrm{\prime }},t^{\mathrm{\prime }})$ refine $P=(n,t)$. For each $i\le n$ the point $t_i$ lies in $\mathrm{pts}(P^{\mathrm{\prime }})$, so there is exactly one $\phi (i)\le n^{\mathrm{\prime }}$ with $t_{\phi (i)}^{\mathrm{\prime }}=t_i$, uniqueness because $t^{\mathrm{\prime }}$ is injective on indices $\le n^{\mathrm{\prime }}$. The resulting map $\phi$ satisfies

$\phi (0)=0,\phi (n)=n^{\mathrm{\prime }},\phi (i)<\phi (i+1)(i<n),$

the first two because $t_0^{\mathrm{\prime }}=a=t_0$ and $t_{n^{\mathrm{\prime }}}^{\mathrm{\prime }}=b=t_n$ together with injectivity, and the third because $t_i<t_{i+1}$ and $t^{\mathrm{\prime }}$ is increasing on indices $\le n^{\mathrm{\prime }}$. In particular $n\le n^{\mathrm{\prime }}$. Moreover, for $i<n$ and $\phi (i)\le j<\phi (i+1)$,

$I_j^{\mathrm{\prime }}=[t_j^{\mathrm{\prime }},t_{j+1}^{\mathrm{\prime }}]\subseteq [t_i,t_{i+1}]=I_i,$

because $t_i=t_{\phi (i)}^{\mathrm{\prime }}\le t_j^{\mathrm{\prime }}$ and $t_{j+1}^{\mathrm{\prime }}\le t_{\phi (i+1)}^{\mathrm{\prime }}=t_{i+1}$.

The blocks are counted by telescoping. By clause 5 of Laws of finite sums and finite products, ${\sum }_{i<n}(\phi (i+1)-\phi (i))=\phi (n)-\phi (0)=n^{\mathrm{\prime }}$, so, subtracting ${\sum }_{i<n}1=n$,

${\sum }_{i<n}(\phi (i+1)-\phi (i)-1)=n^{\mathrm{\prime }}-n,$

a sum of $n$ nonnegative integers, one for each block, which vanishes exactly at the blocks consisting of a single index. This identity is the whole content of the quantitative bound in Refining a partition raises the lower Darboux sum and lowers the upper one, and every lower sum is at most every upper sum: $L(f,P)\le L(f,P^{\mathrm{\prime }})\le U(f,P^{\mathrm{\prime }})\le U(f,P)$ when $P^{\mathrm{\prime }}$ refines $P$, and $L(f,P)\le U(f,Q)$ for arbitrary partitions $P$ and $Q$; moreover the two changes are at most $2M(n^{\mathrm{\prime }}-n)\mathrm{\parallel }P\mathrm{\parallel }$, and it is also why $n\le n^{\mathrm{\prime }}$.

Finally, the lengths inside a block sum to the length of the block:

${\sum }_{j=\phi (i)}^{\phi (i+1)-1}{\mathrm{\Delta }}_j^{\mathrm{\prime }}=t_{\phi (i+1)}^{\mathrm{\prime }}-t_{\phi (i)}^{\mathrm{\prime }}=t_{i+1}-t_i={\mathrm{\Delta }}_i(i<n),$

again by telescoping, applied to the sequence $l\mapsto t_{\phi (i)+l}^{\mathrm{\prime }}$ and read through the index-shift convention of Finite sums and finite products, by recursion.

• Why $a<b$ is a standing hypothesis and not a case. With $a=b$ the displayed chain $a=t_0<\cdots <t_n=b$ is unsatisfiable for $n\ge 1$, and admitting $n=0$ would give a partition with no subintervals, an empty mesh set and no maximum. Every statement on this page is about a nondegenerate closed bounded interval, and the convention ${\int }_a^{a}f:=0$ is not adopted here because nothing below needs it.

• The subintervals overlap at their shared endpoints, and that is harmless. $I_i\cap I_{i+1}=\{t_{i+1}\}$, so the union ${\bigcup }_{i<n}{I}_i=[a,b]$ is not disjoint. Every quantity attached to a partition below is a sum over $i<n$ of a number times ${\mathrm{\Delta }}_i$, and a single point contributes length $0$, so no statement on this page is sensitive to the double counting of the $n-1$ interior points.

• Refinement is a relation between point sets, not between lists. Defining it as "$P^{\mathrm{\prime }}$ is obtained from $P$ by inserting points" would be the same relation, by the uniqueness claim above, but it would make every proof carry an insertion order. The index map $\phi$ recovers the list-level picture when it is wanted, and it is what Refining a partition raises the lower Darboux sum and lowers the upper one, and every lower sum is at most every upper sum: $L(f,P)\le L(f,P^{\mathrm{\prime }})\le U(f,P^{\mathrm{\prime }})\le U(f,P)$ when $P^{\mathrm{\prime }}$ refines $P$, and $L(f,P)\le U(f,Q)$ for arbitrary partitions $P$ and $Q$; moreover the two changes are at most $2M(n^{\mathrm{\prime }}-n)\mathrm{\parallel }P\mathrm{\parallel }$ actually uses.