Proof of The Increasing Listing of a Partition: Endpoints, Lengths, Covering, Unions, Inserting a Point, Concatenation and Uniform Partitions

Segments satisfy $[m]=\{k\in\mathbb{N}:k\le m\}$, $[m+1]=[m]\cup\{m+1\}$ and $m+1\notin[m]$ for $m\in\mathbb{N}_{0}$, by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting (i) and Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting (ii). In this proof, for $m\in\mathbb{N}_{0}$ a map $x:[m]\to\mathbb{R}$, $i\mapsto x_{i}$, is called strictly increasing if $x_{i}<x_{k}$ for all $i,k\in[m]$ with $i<k$; so the bijections of (i) are the strictly increasing bijections from $[n+1]$ onto $P$. Two facts are used repeatedly.

(F) For $k,l\in\mathbb{N}$: $k<l$ if and only if $k+1\le l$; and $k<l+1$ if and only if $k\le l$. Indeed, if $k<l$, then $l=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 k+d=l$ by Arithmetic and Order of the Natural Numbers (ix) and Arithmetic and Order of the Natural Numbers (i). Conversely $k<k+1$ by Arithmetic and Order of the Natural Numbers (xi), so $k+1\le l$ gives $k<l$ by Arithmetic and Order of the Natural Numbers (vi). Applying this with $l+1$ in place of $l$, $k<l+1$ holds if and only if $k+1\le l+1$, that is, by Arithmetic and Order of the Natural Numbers (ix), if and only if $k\le l$.

(M) If $x:[m]\to\mathbb{R}$ is strictly increasing and $i,k\in[m]$ with $i\le k$, then $x_{i}\le x_{k}$, since $i=k$ or $i<k$ by Arithmetic and Order of the Natural Numbers (vi).

Step 1: (i). $P$ is a finite subset of $\mathbb{R}$ by Partitions of a Closed Interval, the Set of Partitions, and Refinements (i); let $N=\#P$. By The Number of Elements of a Finite Set (i) there is a bijection from $[N]$ onto $P$, so by A Finite Set of Real Numbers Has Exactly One Increasing Listing (i) there is exactly one strictly increasing bijection $x$ from $[N]$ onto $P$. As $a\in P$ and $[0]=\emptyset$, $N\neq0$, so $N\in\mathbb{N}$ by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (ii); then $1\in[N]$ by The Segments [n]: Each Is a Set, and 1 Lies in [n] for n ∈ ℕ (ii), and $N\in[N]$. Since $a\in P$, $a=x_{k}$ for some $k\in[N]$; as $1\le k$ by Arithmetic and Order of the Natural Numbers (x), (M) gives $x_{1}\le a$, while $a\le x_{1}$ as $x_{1}\in P\subseteq[a,b]$; so $x_{1}=a$. Likewise $b=x_{k}$ for some $k\in[N]$, $x_{k}\le x_{N}$ by (M) as $k\le N$, and $x_{N}\le b$; so $x_{N}=b$. As $a\neq b$, $N\neq1$, so $N=n+1$ for some $n\in\mathbb{N}$ by Arithmetic and Order of the Natural Numbers (xii). Thus $x$ is a strictly increasing bijection from $[n+1]$ onto $P$ with $x_{1}=a$, $x_{n+1}=b$ and $\#P=n+1$. If $n'\in\mathbb{N}$ and there is a strictly increasing bijection from $[n'+1]$ onto $P$, then $n'+1=\#P=n+1$ by The Number of Elements of a Finite Set (i), so $n'=n$ by Arithmetic and Order of the Natural Numbers (v). For this $n$, the strictly increasing bijection from $[n+1]$ onto $P$ is unique by A Finite Set of Real Numbers Has Exactly One Increasing Listing (i), applied with $n+1$ for its $N$, $x$ being a bijection from $[n+1]$ onto $P$.

From now on $n$ and $x$ are as in (i), and for $i\in[n]$ we use $i,i+1\in[n+1]$ by (ii).

Step 2: (iii). For $i\in[n]$, $i<i+1$ by Arithmetic and Order of the Natural Numbers (xi), so $x_{i}<x_{i+1}$, that is, $x_{i+1}-x_{i}>0$. By Finite Sums in a Commutative Ring and in an Ordered Field: Distributivity, Differences, Telescoping, Constant Terms, Comparison and the Triangle Inequality (iii), applied in the commutative ring $\mathbb{R}$ to $x:[n+1]\to\mathbb{R}$,

$$\sum_{i=1}^{n}(x_{i+1}-x_{i})=x_{n+1}-x_{1}=b-a .$$

Step 3: (iv). Let $t\in[a,b]$ and $S=\{i\in[n]:t\le x_{i+1}\}$. As $n\in[n]$ and $x_{n+1}=b\ge t$, $n\in S$. By Arithmetic and Order of the Natural Numbers (xv), $S$ has an element $i$ with $i\le v$ for every $v\in S$; then $t\le x_{i+1}$. If $i=1$, then $x_{i}=x_{1}=a\le t$. If $i\neq1$, then $i=d+1$ for some $d\in\mathbb{N}$ by Arithmetic and Order of the Natural Numbers (xii); $d<i\le n$ by Arithmetic and Order of the Natural Numbers (xi), so $d\in[n]$; and $d\notin S$, since $d\in S$ would give $i\le d$, contrary to $d<i$ by Arithmetic and Order of the Natural Numbers (vii). Hence $x_{d+1}<t$, that is, $x_{i}<t$. In both cases $x_{i}\le t\le x_{i+1}$.

Step 4: (v). $P\cup Q$ 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 (v), it is contained in $[a,b]$, and it 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). As $P\subseteq P\cup Q$ and $Q\subseteq P\cup Q$, it refines $P$ and $Q$ by Partitions of a Closed Interval, the Set of Partitions, and Refinements (iii).

Step 5: (vi). $\{y\}$ 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), so $P\cup\{y\}$ 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 (v); it is contained in $[a,b]$ and contains $a$ and $b$, so it is a partition of $[a,b]$, and it refines $P$, by Partitions of a Closed Interval, the Set of Partitions, and Refinements (i) and Partitions of a Closed Interval, the Set of Partitions, and Refinements (iii).

Let now $y\notin P$. By (iv) there is $j\in[n]$ with $x_{j}\le y\le x_{j+1}$, and both inequalities are strict as $x_{j},x_{j+1}\in P$ and $y\notin P$. If $j'\in[n]$ also satisfies $x_{j'}<y<x_{j'+1}$ and $j\neq j'$, then by Arithmetic and Order of the Natural Numbers (vii) we may name them so that $j<j'$; then $j+1\le j'$ by (F), so $y<x_{j+1}\le x_{j'}<y$ by (M), which is impossible. So $j$ is unique.

Let $P'=P\cup\{y\}$. As $y\notin P$, Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (v) and Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (ii) give $\#P'=\#P+1=(n+1)+1$. If $n'$ is the $n$ of (i) for the partition $P'$, then $n'+1=\#P'=(n+1)+1$, so $n'=n+1$ by Arithmetic and Order of the Natural Numbers (v). Let $D=[(n+1)+1]$.

As $j+1\in[n+1]\subseteq D$, Bijections between Intervals: the Gap Map and the Reversal (i), applied with $n+1$ for its $n$ and $j+1$ for its $j$, gives a bijection $g$ from $[n+1]$ onto $D\setminus\{j+1\}$ with $g(k)=k$ for $k<j+1$ and $g(k)=k+1$ for $k\ge j+1$. By (F) and Arithmetic and Order of the Natural Numbers (vii), for $k\in[n+1]$: $k<j+1$ if and only if $k\le j$, and $k\ge j+1$ if and only if $j<k$. So $g(k)=k$ for $k\le j$ and $g(k)=k+1$ for $j<k$.

By Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction (vi), the inverse $g^{-1}$ is a bijection from $D\setminus\{j+1\}$ onto $[n+1]$ with $g^{-1}\circ g=\mathrm{id}_{[n+1]}$. So $x\circ g^{-1}$ is a bijection from $D\setminus\{j+1\}$ onto $P$, by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction (ii) and Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction (viii), and $(x\circ g^{-1})(g(k))=x_{g^{-1}(g(k))}=x_{k}$ for every $k\in[n+1]$, by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction (ii) and Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction (iii). As $j+1\notin D\setminus\{j+1\}$ and $y\notin P$, Extending a Map by One Point, and Extending a Bijection by One Point (i) and Extending a Map by One Point, and Extending a Bijection by One Point (ii), applied to $x\circ g^{-1}$ as a map into $P'$, with $j+1$ for its $p$, $y$ for its $c$ and $P$ for its $C$, give a bijection $z$ from $(D\setminus\{j+1\})\cup\{j+1\}=D$ onto $P\cup\{y\}=P'$ with $z_{l}=x_{g^{-1}(l)}$ for $l\in D\setminus\{j+1\}$ and $z_{j+1}=y$. Then $z_{g(k)}=x_{k}$ for every $k\in[n+1]$, that is, $z_{k}=x_{k}$ for $k\le j$ and $z_{k+1}=x_{k}$ for $j<k$; and $z_{j+1}=y$.

$g$ is strictly increasing: let $k,k'\in[n+1]$ with $k<k'$. If $j<k$, then $j<k'$ and $g(k)=k+1<k'+1=g(k')$ by Arithmetic and Order of the Natural Numbers (ix). If $k'\le j$, then $k\le j$ and $g(k)=k<k'=g(k')$. If $k\le j<k'$, then $g(k)=k<k'<k'+1=g(k')$. By Arithmetic and Order of the Natural Numbers (vii) these cases are exhaustive.

$z$ is strictly increasing: let $l,l'\in D$ with $l<l'$. If neither is $j+1$, let $k=g^{-1}(l)$ and $k'=g^{-1}(l')$; then $k\neq k'$, and $k'<k$ would give $l'=g(k')<g(k)=l$; so $k<k'$ by Arithmetic and Order of the Natural Numbers (vii), and $z_{l}=x_{k}<x_{k'}=z_{l'}$. If $l'=j+1$, let $k=g^{-1}(l)$; were $j<k$, then $l=k+1>j+1=l'$ by Arithmetic and Order of the Natural Numbers (ix); so $k\le j$, and $z_{l}=x_{k}\le x_{j}<y=z_{l'}$ by (M). If $l=j+1$, let $k'=g^{-1}(l')$; were $k'\le j$, then $l'=k'\le j<j+1=l$; so $j<k'$, hence $j+1\le k'$ by (F), and $z_{l'}=x_{k'}\ge x_{j+1}>y=z_{l}$ by (M).

Thus $z$ is a strictly increasing bijection from $[(n+1)+1]$ onto $P'$, and by the uniqueness in (i) for $P'$ it is the bijection of (i) for $P'$.

Step 6: (vii). Let $c$, $P_{1}$, $P_{2}$, $p$, $q$, $y$ and $z$ be as there; by (i), $y$ and $z$ are strictly increasing, $y_{1}=a$, $y_{p+1}=c=z_{1}$ and $z_{q+1}=b$. As $a<c<b$, $[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). So $P^{*}=P_{1}\cup P_{2}$ is contained in $[a,b]$, it 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 (v), and $a\in P_{1}$, $b\in P_{2}$; hence $P^{*}$ is a partition of $[a,b]$ by Partitions of a Closed Interval, the Set of Partitions, and Refinements (i).

Let $r=p+q$, so $r+1=p+(q+1)$ by Arithmetic and Order of the Natural Numbers (ii). By Splitting the Segment [m+n] into [m] and a Shifted Copy of [n] (iii), with $p$ for its $m$ and $q+1$ for its $n$, every $k\in[r+1]$ lies in exactly one of $[p]$ and $\{p+j:j\in[q+1]\}$, and in the second case $k-p\in[q+1]$ and $k=p+(k-p)$. As $[p]\subseteq[p+1]$ by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting (ii), Maps Defined by Cases (i), with the property $k\in[p]$, gives a map $x:[r+1]\to\mathbb{R}$ with $x_{k}=y_{k}$ for $k\in[p]$ and $x_{k}=z_{k-p}$ for the other $k\in[r+1]$. For $j\in[q+1]$, $p+j\in[r+1]$ and $p+j\notin[p]$ by Splitting the Segment [m+n] into [m] and a Shifted Copy of [n] (ii), and $(p+j)-p=j$ by Splitting the Segment [m+n] into [m] and a Shifted Copy of [n] (iii); so $x_{p+j}=z_{j}$. As $1\in[q+1]$ (Arithmetic and Order of the Natural Numbers (x) and Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting (i)), $x_{p+1}=z_{1}=c=y_{p+1}$, so $x_{i}=y_{i}$ for every $i\in[p+1]=[p]\cup\{p+1\}$.

$x$ is strictly increasing: let $i,k\in[r+1]$ with $i<k$. If $i,k\in[p]$, then $x_{i}=y_{i}<y_{k}=x_{k}$. If $i=p+j$ and $k=p+j'$ with $j,j'\in[q+1]$, then $j<j'$, since $j'\le j$ would give $k\le i$ by Arithmetic and Order of the Natural Numbers (ix) and Arithmetic and Order of the Natural Numbers (i), which Arithmetic and Order of the Natural Numbers (vii) and Arithmetic and Order of the Natural Numbers (vi) exclude; so $x_{i}=z_{j}<z_{j'}=x_{k}$. If $i\in[p]$ and $k=p+j'$ with $j'\in[q+1]$, then $i\le p<p+1$ by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting (i) and Arithmetic and Order of the Natural Numbers (xi), so $i<p+1$ by Arithmetic and Order of the Natural Numbers (vi); and $1\le j'$ by Arithmetic and Order of the Natural Numbers (x); hence $x_{i}=y_{i}<y_{p+1}=c=z_{1}\le z_{j'}=x_{k}$ by (M). The remaining case, $i=p+j$ with $j\in[q+1]$ and $k\in[p]$, does not occur: then $k\le p<p+j=i$ by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting (i) and Arithmetic and Order of the Natural Numbers (viii), so $k<i$ by Arithmetic and Order of the Natural Numbers (vi), which Arithmetic and Order of the Natural Numbers (vii) excludes together with $i<k$. Being strictly increasing, $x$ is injective, by Arithmetic and Order of the Natural Numbers (vii). Its values lie in $P_{1}\cup P_{2}=P^{*}$, and every element of $P^{*}$ is a value: an element of $P_{1}$ is $y_{i}=x_{i}$ for some $i\in[p+1]$, and an element of $P_{2}$ is $z_{j}=x_{p+j}$ for some $j\in[q+1]$. So $x$ is a strictly increasing bijection from $[r+1]$ onto $P^{*}$, and by the uniqueness in (i) for the partition $P^{*}$ of $[a,b]$, the $n$ of that clause for $P^{*}$ is $r=p+q$ and $x$ is its bijection.

Step 7: (viii). Let $c\in\mathbb{R}$ with $a<c<b$, and let $P'=P\cup\{c\}$, a partition of $[a,b]$ by (vi), as $c\in[a,b]$. The sets $P'\cap[a,c]$ and $P'\cap[c,b]$ are 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); $a,c\in P'\cap[a,c]$ and $c,b\in P'\cap[c,b]$, as $a,b\in P$ and $a<c<b$; so they are partitions of $[a,c]$ and of $[c,b]$ by Partitions of a Closed Interval, the Set of Partitions, and Refinements (i). Their union is $P'\cap([a,c]\cup[c,b])=P'$, as every $t\in P'\subseteq[a,b]$ satisfies $t\le c$ or $c\le t$.

Step 8: (ix). Let $N$, $h$ and $w$ be as there. Natural numbers are read in $\mathbb{R}$ as in The Real Line: Standing Notation and Background for Calculus on Intervals (vii); then $1$ is the unit of $\mathbb{R}$, and sums, and differences $m-l$ with $l\le m$, of elements of $\mathbb{N}_{0}$ are the same whether formed in $\mathbb{N}_{0}$ or in $\mathbb{R}$, by The Image of the Natural Numbers with Zero in a Commutative Ring Respects Zero, One, Sums, Products, Differences, Powers, and Finite Sums and Products (i), The Image of the Natural Numbers with Zero in a Commutative Ring Respects Zero, One, Sums, Products, Differences, Powers, and Finite Sums and Products (ii) and The Image of the Natural Numbers with Zero in a Commutative Ring Respects Zero, One, Sums, Products, Differences, Powers, and Finite Sums and Products (iv), and so is the order (The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness (vi)). As $0<b-a$ and $0<N$, $0<h$ by Rules of Arithmetic and Order in an Ordered Field (viii) and Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares (iv), and $Nh=b-a$.

Let $k\in[N+1]$. Then $1\le k\le N+1$ by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting (i) and Arithmetic and Order of the Natural Numbers (x), so in $\mathbb{R}$, $0\le k-1\le N$ by Rules of Arithmetic and Order in an Ordered Field (iv); hence $0\le(k-1)h\le Nh=b-a$ by Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares (v), and $a\le w_{k}\le b$ by Rules of Arithmetic and Order in an Ordered Field (iv). So $k\mapsto w_{k}$ is a map from $[N+1]$ to $[a,b]$ (Values, Restriction and Equality of a Map, and the Map $u\mapsto t(u)$ as a Defined Set Symbol (v)), and $W=\{w_{k}:k\in[N+1]\}$ is a subset of $[a,b]$ by Images of Typed Terms: the Set of Values $\{t:u\in D\}$ Is a Set, Finite when $D$ Is Finite, and a Typed Term (ii), finite by Images of Typed Terms: the Set of Values $\{t:u\in D\}$ Is a Set, Finite when $D$ Is Finite, and a Typed Term (iii), as $[N+1]$ 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 (vii). Since $1,N+1\in[N+1]$ by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting (i), and $1-1=0$ and $(N+1)-1=N$ by The Difference of Two Natural Numbers with Zero (i), $w_{1}=a\in W$ and $w_{N+1}=a+Nh=b\in W$. So $W$ is a partition of $[a,b]$ by Partitions of a Closed Interval, the Set of Partitions, and Refinements (i).

If $i,k\in[N+1]$ and $i<k$, then $0<k-i$ in $\mathbb{R}$ by Rules of Arithmetic and Order in an Ordered Field (iv), and $w_{k}-w_{i}=((k-1)-(i-1))h=(k-i)h>0$ by Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares (iv). So $k\mapsto w_{k}$ is strictly increasing, injective by Arithmetic and Order of the Natural Numbers (vii), and onto $W$ by Images of Typed Terms: the Set of Values $\{t:u\in D\}$ Is a Set, Finite when $D$ Is Finite, and a Typed Term (i). By the uniqueness in (i) for $W$, the $n$ of that clause for $W$ is $N$ and $k\mapsto w_{k}$ is its bijection. Finally, for $k\in[N]$, $k,k+1\in[N+1]$ by (ii), $(k+1)-1=k$ by The Difference of Two Natural Numbers with Zero (i), and so $w_{k+1}-w_{k}=(a+kh)-(a+(k-1)h)=h$.