Proof of A Closed Interval Covered by Open Intervals Is No Longer than Their Total Length

Write $\ell_{m}=b_{m}-a_{m}$ for $m\in\mathbb{N}$. A real number $u\ge0$ is an element of $[0,\infty]$, the sum in $[0,\infty]$ of two such numbers is their real sum (Addition and Multiplication on [0,∞] (i)), and on real numbers the order of $[0,\infty]$ is that of $\mathbb{R}$ (Order and Suprema in the Extended Real Line (i)); these identifications are used throughout. For a set $G\subseteq\mathbb{N}$ and $u,v\in\mathbb{R}$ with $u\le v$, say that $G$ covers $[u,v]$ if every $x\in[u,v]$ lies in $(a_{m},b_{m})$ for some $m\in G$. The empty set covers no such $[u,v]$, since $u\in[u,v]$.

Proof of (i). For $n\in\mathbb{N}$ let $\varphi(n)$ be the statement: for every finite $G\subseteq\mathbb{N}$ with $\#G<n$, where $\#G\in\mathbb{N}_{0}$ is the number of elements of $G$, and all $u,v\in\mathbb{R}$ with $u\le v$ such that $G$ covers $[u,v]$, we have $v-u\le\sum_{m\in G}\ell_{m}$. The condition $\varphi(n)$ on $n$ is expressed by a predicative formula, with the maps $m\mapsto a_{m}$, $m\mapsto b_{m}$ and $m\mapsto\ell_{m}$, $\mathbb{N}_{0}$, $\mathbb{N}$, $\mathbb{R}$, $[0,\infty]$ and their orders and operations as parameters (it quantifies over sets only, such as $G$, $u$, $v$, $x$, $m$, $k$ and a bijection, so it is predicative by Predicativity of Expressions with Abbreviations, and Symbol-Free Forms of the Basic Defined Set Symbols (i), once its parts are: finiteness of $G$ by Substituting Variables and Set Parameters into Predicative Formulas, Extending Assignments, and Finiteness (v); $\#G<n$, which by The Number of Elements of a Finite Set (i) says that there are $k\in\mathbb{N}_{0}$ with $k<n$ and a bijection from $[k]$ onto $G$, by Predicative Formulas for Bijections from a Segment [n] and for Increasing Listings (i); the sum $\sum_{m\in G}\ell_{m}$ over $G$ by Iterated Operations over Finite Sets Are Given by a Predicative Formula (i); the values $a_{m}$, $b_{m}$ by Predicative Substitution of Values of Functions and Binary Operations, and Predicative Formulas for Negatives, Differences, Absolute Values, Distances, Reciprocals and Quotients in an Ordered Field (i); and the difference $v-u$ by Predicative Substitution of Values of Functions and Binary Operations, and Predicative Formulas for Negatives, Differences, Absolute Values, Distances, Reciprocals and Quotients in an Ordered Field (iv)). So we may prove $\varphi(n)$ for every $n\in\mathbb{N}$ by Induction for Predicative Formulas, and the Order of ℕ below 1 and below n+1 (i).

If $G\subseteq\mathbb{N}$ is finite and nonempty, then $\#G\neq0$ by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (ii), so $\#G\in\mathbb{N}$, as $\mathbb{N}=\mathbb{N}_{0}\setminus\{0\}$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (ii)).

Since $p\in[p,q]$ lies in $(a_{m},b_{m})$ for some $m\in F$, $F$ is nonempty, so $\#F\in\mathbb{N}$ by the preceding paragraph; then $\#F<\#F+1$ by Arithmetic and Order of the Natural Numbers (xi), and $\#F+1\in\mathbb{N}$ by Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication (vi). So the statement $\varphi(\#F+1)$, applied to $G=F$, $u=p$ and $v=q$, gives the claim. It remains to prove $\varphi(n)$ for every $n\in\mathbb{N}$.

Base. Let $G$ be finite with $\#G<1$. If $G$ were nonempty, then $\#G\in\mathbb{N}$ with $\#G<1$, which Induction for Predicative Formulas, and the Order of ℕ below 1 and below n+1 (ii) excludes. So $G=\emptyset$, which covers no $[u,v]$, and $\varphi(1)$ holds.

Step. Let $n\in\mathbb{N}$ with $\varphi(n)$, let $G\subseteq\mathbb{N}$ be finite with $\#G<n+1$, and let $u\le v$ be such that $G$ covers $[u,v]$. Then $G\neq\emptyset$, so $\#G\in\mathbb{N}$ and hence $\#G\le n$ by Induction for Predicative Formulas, and the Order of ℕ below 1 and below n+1 (iii). Since $v\in[u,v]$, there is $k\in G$ with $a_{k}<v<b_{k}$. Let $G'=G\setminus\{k\}$; 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 (iv), and $\#G'<\#G$ by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (iv), as $G'\subseteq G$ and $G'\neq G$; hence $\#G'<n$. As $G=G'\cup\{k\}$ with $G'\cap\{k\}=\emptyset$,

$$\sum_{m\in G}\ell_{m}=\sum_{m\in G'}\ell_{m}+\ell_{k}$$

by 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 (i). Put $\Sigma'=\sum_{m\in G'}\ell_{m}\in[0,\infty]$. Two cases.

If $a_{k}<u$, then $v-u<v-a_{k}<b_{k}-a_{k}=\ell_{k}$, and $\ell_{k}\le\ell_{k}+\Sigma'=\Sigma'+\ell_{k}$ by Arithmetic in [0,∞]: Monoid Laws, Distributivity, Monotonicity and Cancellation (v) and Arithmetic in [0,∞]: Monoid Laws, Distributivity, Monotonicity and Cancellation (i); so $v-u\le\sum_{m\in G}\ell_{m}$.

If $u\le a_{k}$, then $u\le a_{k}<v$. Every $y\in[u,a_{k}]$ lies in $[u,v]$, hence in $(a_{m},b_{m})$ for some $m\in G$; and $m\neq k$, as $y\le a_{k}$ means $y\notin(a_{k},b_{k})$. So $G'$ covers $[u,a_{k}]$, and $\varphi(n)$, applied to $G'$, $u$ and $a_{k}$, gives $a_{k}-u\le\Sigma'$. Also $v-a_{k}\le b_{k}-a_{k}=\ell_{k}$, as $v<b_{k}$. By Arithmetic in [0,∞]: Monoid Laws, Distributivity, Monotonicity and Cancellation (iv), applied twice, and Arithmetic in [0,∞]: Monoid Laws, Distributivity, Monotonicity and Cancellation (i),

$$v-u=(a_{k}-u)+(v-a_{k})\le\Sigma'+(v-a_{k})\le\Sigma'+\ell_{k}=\sum_{m\in G}\ell_{m},$$

the first sum being the real sum of two nonnegative reals. This proves $\varphi(n+1)$.

Proof of (ii). For $n\in\mathbb{N}$ the segment $[n]=\{1,\dots,n\}$ is a finite subset of $\mathbb{N}$ (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)). Let

$$S=\{x\in[p,q]:\text{there is }n\in\mathbb{N}\text{ such that }[n]\text{ covers }[p,x]\}.$$

(The defining condition of $S$ is predicative: it quantifies over sets only and is built from the same pieces as the condition $\varphi(n)$ above, namely the values $a_{m}$ and $b_{m}$, membership in the intervals $(a_{m},b_{m})$ and $[p,x]$, the segments $[n]$ and the orders of $\mathbb{R}$ and $\mathbb{N}_{0}$, so it is predicative by Predicativity of Expressions with Abbreviations, and Symbol-Free Forms of the Basic Defined Set Symbols (i). So $S$ is a subclass of the set $[p,q]$, hence a set by Subclasses of Sets Are Sets, the Union and Power Set of a Set Exist Uniquely, Binary Unions of Sets Are Sets, and the Universal Class Is Proper (i).) If $[n]$ covers $[p,x]$ and $n\le n'$, then $[n']$ covers $[p,x]$, as $[n]\subseteq[n']$ by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting (v). For $k,n\in\mathbb{N}$ with $k\le n$, $k\in[n]$ by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting (i); in particular $k\in[k]$, as $k\le k$ by Arithmetic and Order of the Natural Numbers (vi).

$S$ is nonempty and has supremum $q$. By hypothesis $p\in(a_{k},b_{k})$ for some $k\in\mathbb{N}$; as $[p,p]=\{p\}$ and $k\in[k]$, the segment $[k]$ covers $[p,p]$, so $p\in S$. Thus $S$ is a nonempty subset of $\mathbb{R}$ bounded above by $q$, and has a supremum $s\in\mathbb{R}$ by The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness (vii), with $p\le s\le q$. By hypothesis $s\in(a_{k},b_{k})$ for some $k\in\mathbb{N}$. As $a_{k}<s$, the number $a_{k}$ is not an upper bound of $S$ (Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order (iv)), so there is $x\in S$ with $a_{k}<x$; fix such an $x$ and $n_{x}\in\mathbb{N}$ such that $[n_{x}]$ covers $[p,x]$. Let $n=\max\{n_{x},k\}$, which exists by The Maximum and Minimum of Two Elements of a Total Order (i), so that $n_{x}\le n$ and $k\le n$ (The Maximum and Minimum of Two Elements of a Total Order (iii), for the total order of $\mathbb{N}$).

We claim that every $y\in[p,q]$ with $y<b_{k}$ lies in $S$, as $[n]$ covers $[p,y]$. Let $z\in[p,y]$. If $z\le x$, then $z\in[p,x]$ lies in $(a_{m},b_{m})$ for some $m\in[n_{x}]\subseteq[n]$. If $x<z$, then $a_{k}<x<z\le y<b_{k}$, so $z\in(a_{k},b_{k})$ with $k\in[n]$. This proves the claim.

Suppose $s<q$. Let $y=\min\{q,s+(b_{k}-s)/2\}$, which exists by The Maximum and Minimum of Two Elements of a Total Order (i), for the total order of $\mathbb{R}$. As $s<b_{k}$, Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares (vii) gives $s<s+(b_{k}-s)/2<b_{k}$; as also $s<q$, and $y$ is one of $q$ and $s+(b_{k}-s)/2$ (The Maximum and Minimum of Two Elements of a Total Order (ii)), we get $s<y$, and $y\le s+(b_{k}-s)/2<b_{k}$ and $y\le q$ by The Maximum and Minimum of Two Elements of a Total Order (iii). So $y\in[p,q]$ and $y<b_{k}$, hence $y\in S$ by the claim, contradicting $s<y$ and $s=\sup S$. Hence $s=q$.

Conclusion. Now $q=s<b_{k}$ and $q\in[p,q]$, so $q\in S$ by the claim: $[n]$ covers $[p,q]$. By (i), applied to $F=[n]$, and by Sums of Sequences in [0,∞]: Real Series, Linearity, Comparison, Rearrangement, Double Series and Monotone Convergence (iv),

$$q-p\le\sum_{m\in[n]}\ell_{m}\le\sum_{m\in\mathbb{N}}\ell_{m}.$$