Proof of Approximation of Measurable Functions by Dyadic Simple Functions

Step 1: the dyadic maps. Arithmetic on real numbers is done in the ordered ring of The Real Numbers as a Type (vi), with the laws of The Real Numbers as a Type (iv) and The Real Numbers as a Type (v); differences, reciprocals, quotients and absolute values of real numbers lie in $\mathbb{R}$ and are read there by Differences, Quotients and Absolute Values of Real Numbers, and Their Order in the Extended Real Line, Read in the Type Real (i), Differences, Quotients and Absolute Values of Real Numbers, and Their Order in the Extended Real Line, Read in the Type Real (ii) and Differences, Quotients and Absolute Values of Real Numbers, and Their Order in the Extended Real Line, Read in the Type Real (iii). For $z\in\mathbb{R}$, $\lfloor z\rfloor$ is the integer part of $z$, an integer with $\lfloor z\rfloor\le z<\lfloor z\rfloor+1$ by The Integer Part of a Real Number (i), which read in $\mathbb{R}$ is a real number by Maps Used to Build the Integral: Fibres of a Map, Pointwise Combinations with Finite Image, Tail Extrema of a Sequence of Maps, the Integer Part, and Indicators (iv); for $y,z\in\mathbb{R}$, $\min\{y,z\}$ is formed in $\mathbb{R}$ as in The Maximum and Minimum of Two Elements of a Total Order (i). For $y\in\mathbb{R}$ and $m\in\mathbb{N}$ write $q_{m}(y)=2^{-m}\lfloor2^{m}y\rfloor$. By Dyadic Approximations of a Map into [0,∞] (i), for a map $g:X\to[0,\infty]$, $x\in X$ and $m\in\mathbb{N}$, $s_{m}(g)(x)=\min\{m,q_{m}(g(x))\}$ if $g(x)\in\mathbb{R}$ and $s_{m}(g)(x)=m$ if $g(x)=\infty$. For $m\in\mathbb{N}$, the number $2$, the image of $m$ in $\mathbb{R}$ and the power $2^{m}$ lie in $\mathbb{R}$ by Closure Facts in an Ordered Field: Negatives, Differences, Quotients, Absolute Values, Powers, Natural Numbers, Halves and Minima (vi), Closure Facts in an Ordered Field: Negatives, Differences, Quotients, Absolute Values, Powers, Natural Numbers, Halves and Minima (v) and Closure Facts in an Ordered Field: Negatives, Differences, Quotients, Absolute Values, Powers, Natural Numbers, Halves and Minima (iv); further $0<m<2^{m}$ and $0<2^{-m}<1/m$ by The Integer Part as the Greatest Integer Below, the Integer Part of a Double, and Powers of Two (iii), where $2^{-m}=1/2^{m}$ and $1/m$ lie in $\mathbb{R}$ by Closure Facts in an Ordered Field: Negatives, Differences, Quotients, Absolute Values, Powers, Natural Numbers, Halves and Minima (ii), as $m\neq0$ and $2^{m}\neq0$.

(a) For $n,n'\in\mathbb{Z}$ with $n<n'$, read in $\mathbb{R}$, we have $n+1\le n'$. Otherwise $n\le n'<n+1$, and also $n'\le n'<n'+1$, so $n=\lfloor n'\rfloor=n'$ by the uniqueness in The Integers in the Real Numbers: Greatest Elements, the Integer Part, and Archimedean Consequences (iv), contradicting $n<n'$.

(b) Let $y\in\mathbb{R}$ and $m\in\mathbb{N}$. Multiplying $\lfloor2^{m}y\rfloor\le2^{m}y<\lfloor2^{m}y\rfloor+1$ by $2^{-m}>0$ gives $y-2^{-m}<q_{m}(y)\le y$; if $y\ge0$, then $\lfloor2^{m}y\rfloor\ge0$ by The Integers in the Real Numbers: Greatest Elements, the Integer Part, and Archimedean Consequences (vi), so $q_{m}(y)\ge0$. Here $m+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), and $2^{m+1}=2^{m}\cdot2$ by Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality (i) and Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality (ii); as $2^{-m}\cdot2^{m}=1$ and $2^{-(m+1)}\cdot2^{m+1}=1$ (Differences, Quotients and Absolute Values of Real Numbers, and Their Order in the Extended Real Line, Read in the Type Real (ii)), it follows that $2^{-(m+1)}\cdot2=2^{-m}$. With $z=2^{m}y$ we have $2^{m+1}y=2z$, and $2\lfloor z\rfloor\le\lfloor2z\rfloor$ by The Integer Part as the Greatest Integer Below, the Integer Part of a Double, and Powers of Two (ii), so $q_{m}(y)=2^{-(m+1)}\cdot2\lfloor z\rfloor\le2^{-(m+1)}\lfloor2z\rfloor=q_{m+1}(y)$.

(c) Let $g:X\to[0,\infty]$, $x\in X$ and $m\in\mathbb{N}$. If $g(x)=\infty$, then $s_{m}(g)(x)=m$. If $g(x)=y\in\mathbb{R}$, then $y\ge0$ by The Extended Real Line, Its Order, and [0,∞] (ii), and $s_{m}(g)(x)=\min\{m,q_{m}(y)\}$ is one of $m$ and $q_{m}(y)$ and is at most each of them, by The Maximum and Minimum of Two Elements of a Total Order (i) and The Maximum and Minimum of Two Elements of a Total Order (iii); if moreover $y\le m$, then $q_{m}(y)\le y\le m$ by (b), so $s_{m}(g)(x)=q_{m}(y)$ by The Maximum and Minimum of Two Elements of a Total Order (ii) and $y-2^{-m}<s_{m}(g)(x)\le y$ by (b). In every case $0\le s_{m}(g)(x)\le m$, by (b) and since $0<m$ by The Integer Part as the Greatest Integer Below, the Integer Part of a Double, and Powers of Two (iii).

(d) For $y\in\mathbb{R}$ with $y\ge0$ and real $\varepsilon>0$ there is $N\in\mathbb{N}$ with $y<m$ and $2^{-m}<\varepsilon$ for every $m\in\mathbb{N}$ with $m\ge N$. Indeed, The Integers in the Real Numbers: Greatest Elements, the Integer Part, and Archimedean Consequences (vii), applied to $y+1/\varepsilon$, gives $N\in\mathbb{N}$ with $y+1/\varepsilon<m$ for every $m\in\mathbb{N}$ with $m\ge N$. For such $m$, $y<m$ and $1/\varepsilon<m$, as $1/\varepsilon>0$ and $y\ge0$; multiplying by $\varepsilon/m>0$ gives $1/m<\varepsilon$, and $2^{-m}<1/m$ by The Integer Part as the Greatest Integer Below, the Integer Part of a Double, and Powers of Two (iii).

(e) Let $g:X\to[0,\infty]$, $x\in X$ and $m\in\mathbb{N}$. Then $s_{m}(g)(x)\le s_{m+1}(g)(x)\le g(x)$, where between real numbers $\le$ is the order of $\mathbb{R}$ by Order and Suprema in the Extended Real Line (i). Here $m+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), and $m+1$ read in $\mathbb{R}$ is the sum of $m$ and $1$ 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 (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 (i), so $m\le m+1$ in $\mathbb{R}$. If $g(x)=\infty$, the claim reads $m\le m+1\le\infty$, the second by The Extended Real Line, Its Order, and [0,∞] (iii). If $g(x)=y\in\mathbb{R}$, then by (c) and (b) $s_{m}(g)(x)\le m\le m+1$ and $s_{m}(g)(x)\le q_{m}(y)\le q_{m+1}(y)$, so $s_{m}(g)(x)\le\min\{m+1,q_{m+1}(y)\}=s_{m+1}(g)(x)$ by The Maximum and Minimum of Two Elements of a Total Order (v); and $s_{m+1}(g)(x)\le q_{m+1}(y)\le y$.

Proof of (i). Fix $m\in\mathbb{N}$. Finite image. By The Integers Lying in a Bounded Real Interval Form a Finite Set (i), with $a=0$ and $b=2^{m}m$, there is a finite subset $E$ of $\mathbb{R}$ whose elements are exactly the integers read in $\mathbb{R}$ lying between $0$ and $2^{m}m$. Let $\psi:E\to\mathbb{R}$, $u\mapsto2^{-m}u$, be the restriction to $E$ (Domains and Restrictions of Maps (ii), Domains and Restrictions of Maps (iii)) of the map $\mathbb{R}\to\mathbb{R}$, $u\mapsto2^{-m}\cdot u$, given by Maps Formed Pointwise: Constant Maps, Pairs of Values, Maps Applied to Values, and Families of Maps (iv) applied to the multiplication of $\mathbb{R}$. Then $D=\psi[E]\cup\{m\}$ 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 (vi), 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). Let $x\in X$. By (c), $s_{m}(f)(x)$ is either $m\in D$, or $q_{m}(y)$ with $y=f(x)\in\mathbb{R}$, $y\ge0$ and $q_{m}(y)=s_{m}(f)(x)\le m$; in the latter case the integer $n=\lfloor2^{m}y\rfloor$ satisfies $0\le n$ by The Integers in the Real Numbers: Greatest Elements, the Integer Part, and Archimedean Consequences (vi), as $2^{m}y\ge0$, and $n=2^{m}q_{m}(y)\le2^{m}m$, so $n\in E$ and $s_{m}(f)(x)=2^{-m}n=\psi(n)\in D$. Hence $s_{m}(f)[X]\subseteq D$ 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).

Measurability. By criterion (b) of Measurable Maps: Generators, Composition, Continuous Maps, Restrictions, and Criteria for Real- and [0,∞]-Valued Maps (v) it suffices that $L_{a}=\{x\in X:s_{m}(f)(x)>a\}$ lies in $\mathcal{F}$ for every $a\in\mathbb{R}$. If $a\ge m$, then $L_{a}=\emptyset\in\mathcal{F}$ by (c) and Closure Properties of σ-Algebras, Intersections and Traces of σ-Algebras, and the Generated σ-Algebra (vi). Let $a<m$, let $p=\lfloor2^{m}a\rfloor$ and $b=2^{-m}(p+1)\in\mathbb{R}$; we show $L_{a}=\{x\in X:f(x)\ge b\}$. If $f(x)=\infty$, then $s_{m}(f)(x)=m>a$ by (c), and $\infty\ge b$ by The Extended Real Line, Its Order, and [0,∞] (iii). If $f(x)=y\in\mathbb{R}$, let $n=\lfloor2^{m}y\rfloor$. As $a<m$ and $s_{m}(f)(x)=\min\{m,q_{m}(y)\}$ is one of $m$ and $q_{m}(y)$ and at most each of them (The Maximum and Minimum of Two Elements of a Total Order (i), The Maximum and Minimum of Two Elements of a Total Order (iii)), $s_{m}(f)(x)>a$ holds if and only if $q_{m}(y)>a$, that is, multiplying by $2^{m}>0$, $n>2^{m}a$. If $n>2^{m}a$, then $p\le2^{m}a<n$ by The Integer Part of a Real Number (i), so $p+1\le n\le2^{m}y$ by (a) and The Integer Part of a Real Number (i), that is $b\le y$. Conversely, let $b\le y$, so $p+1\le2^{m}y$; if $n\le2^{m}a$, then $n\le p$ by The Integer Part as the Greatest Integer Below, the Integer Part of a Double, and Powers of Two (i), applied to the integer $n$ and the real number $2^{m}a$, and $2^{m}y<n+1\le p+1\le2^{m}y$, which is impossible; so $n>2^{m}a$. So $L_{a}=f^{-1}(R)$ with $R=\{u\in[0,\infty]:u\ge b\}$, which lies in $\mathcal{B}([0,\infty])$ by Borel Subsets of [0,∞]: Rays, the Point ∞, and Traces on ℝ (i); hence $L_{a}\in\mathcal{F}$ by Measurable Map, and the Set of Measurable Maps (vi) and Measurable Map, and the Set of Measurable Maps (i).

So $s_{m}(f)$ is measurable as a map into $\mathbb{R}$ with finite image, a simple function, hence in $\mathcal{S}$ by Simple Functions, Nonnegative Simple Functions, and the Simple Integral (ii); its values are $\ge0$ by (c), so $s_{m}(f)\in\mathcal{S}^{+}$ by Simple Functions, Nonnegative Simple Functions, and the Simple Integral (iii). The inequalities $s_{m}(f)(x)\le s_{m+1}(f)(x)\le f(x)$ are (e).

Supremum. Fix $x\in X$ and let $A=\{s_{m}(f)(x):m\in\mathbb{N}\}\subseteq\mathbb{R}$, whose elements are the values $s_{m}(f)(x)$ (Preimages, Unions and Intersections over an Index Set, Suprema and Infima, and Superlevel Sets as Typed Terms (iv)). If $f(x)=\infty$, then $s_{n}(f)(x)=n$ for every $n\in\mathbb{N}$ by (c), so for every $c\in\mathbb{R}$ the $N\in\mathbb{N}$ of The Integers in the Real Numbers: Greatest Elements, the Integer Part, and Archimedean Consequences (vii), applied to $c$, satisfies $c<N=s_{N}(f)(x)\in A$: $A$ is not bounded above in $\mathbb{R}$, and $\sup A=\infty=f(x)$ by Order and Suprema in the Extended Real Line (v). If $f(x)=y\in\mathbb{R}$, then $A$ is nonempty, as $s_{1}(f)(x)\in A$ with $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 (ii), and $y$ is an upper bound of $A$ in $\mathbb{R}$ by (e). Let $c\in\mathbb{R}$ be an upper bound of $A$ and suppose $c<y$. As $y\ge0$ by The Extended Real Line, Its Order, and [0,∞] (ii), (d) with $\varepsilon=y-c$ gives $N\in\mathbb{N}$ with $y<N$ and $2^{-N}<y-c$, and by (c) $s_{N}(f)(x)>y-2^{-N}>c$, a contradiction. So $y\le c$ for every upper bound $c$, and $y$ is the least element of the set of upper bounds of $A$ in $\mathbb{R}$, that is the supremum of $A$ in $\mathbb{R}$, unique by Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order (iv). Hence $\sup A=y=f(x)$ by Order and Suprema in the Extended Real Line (iv).

Proof of (ii). As $f$ is measurable as a map into $\mathbb{R}$ with values $\ge0$, it is measurable as a map into $[0,\infty]$ by Measurable Maps: Generators, Composition, Continuous Maps, Restrictions, and Criteria for Real- and [0,∞]-Valued Maps (vii), so $s_{m}(f)\in\mathcal{S}^{+}$ for every $m\in\mathbb{N}$ by (i). Let $x\in X$ and $m\in\mathbb{N}$ with $m\ge K$, and $y=f(x)$. Then $y\in\mathbb{R}$ and $0\le y\le K\le m$, so $y-2^{-m}<s_{m}(f)(x)\le y$ by (c), that is $0\le f(x)-s_{m}(f)(x)<2^{-m}$.

Proof of (iii). The maps $f^{+}$ and $f^{-}$ are measurable as maps into $\mathbb{R}$ by Arithmetic of Measurable Real- and [0,∞]-Valued Maps (i), and their values are $\ge0$ by The Maximum and Minimum of Two Elements of a Total Order (iii); so they are measurable as maps into $[0,\infty]$ by Measurable Maps: Generators, Composition, Continuous Maps, Restrictions, and Criteria for Real- and [0,∞]-Valued Maps (vii), and $s_{m}(f^{+}),s_{m}(f^{-})\in\mathcal{S}^{+}$ for every $m\in\mathbb{N}$ by (i). Fix $m$. Then $t_{m}$ is measurable as a map into $\mathbb{R}$ by Arithmetic of Measurable Real- and [0,∞]-Valued Maps (i), applied to the difference of the maps $s_{m}(f^{+})$ and $s_{m}(f^{-})$, which are simple functions, so measurable as maps into $\mathbb{R}$ with finite images, by Simple Functions, Nonnegative Simple Functions, and the Simple Integral (iii), Simple Functions, Nonnegative Simple Functions, and the Simple Integral (ii) and Simple Functions, Nonnegative Simple Functions, and the Simple Integral (i). Let $F=\pi_{1}-\pi_{2}:\mathbb{R}\times\mathbb{R}\to\mathbb{R}$, the pointwise difference (Pointwise Operations on Real-Valued Maps (i)) of the projections $\pi_{1}$ and $\pi_{2}$ of Projection, Evaluation and Currying Maps (i), so that $F(c,c')=c-c'$ for $c,c'\in\mathbb{R}$. Then $t_{m}$ is the map with $t_{m}(x)=F(s_{m}(f^{+})(x),s_{m}(f^{-})(x))$ for every $x\in X$, so $t_{m}[X]$ is finite by Maps Used to Build the Integral: Fibres of a Map, Pointwise Combinations with Finite Image, Tail Extrema of a Sequence of Maps, the Integer Part, and Indicators (ii). So $t_{m}\in\mathcal{S}$ by Simple Functions, Nonnegative Simple Functions, and the Simple Integral (i) and Simple Functions, Nonnegative Simple Functions, and the Simple Integral (ii).

Fix $x\in X$. If $f(x)\ge0$, then $f^{+}(x)=f(x)=|f(x)|$ and $f^{-}(x)=0$, by The Maximum and Minimum of Two Elements of a Total Order (ii) and Absolute Value in an Ordered Field (i); $0\le s_{m}(f^{-})(x)\le0$ by (c), with $y=f^{-}(x)=0\le m$, so $s_{m}(f^{-})(x)=0$ and $t_{m}(x)=u_{m}$ with $u_{m}=s_{m}(f^{+})(x)$. If $f(x)<0$, then likewise $f^{+}(x)=0$ and $f^{-}(x)=-f(x)=|f(x)|$, and $0\le s_{m}(f^{+})(x)\le0$ by (c), so $t_{m}(x)=-u_{m}$ with $u_{m}=s_{m}(f^{-})(x)$. In both cases $u_{m}=s_{m}(g)(x)$ for a map $g\in\{f^{+},f^{-}\}$ with $g(x)=|f(x)|$, so $0\le u_{m}\le|f(x)|$ by (c) and (e), and Absolute Value in an Ordered Field (i) gives $|t_{m}(x)|=u_{m}\le|f(x)|$ and $|t_{m}(x)-f(x)|=|f(x)|-u_{m}$, for every $m\in\mathbb{N}$. Now let $\varepsilon>0$ be real. By (d) with $y=|f(x)|$ there is $N\in\mathbb{N}$ with $|f(x)|<m$ and $2^{-m}<\varepsilon$ for every $m\in\mathbb{N}$ with $m\ge N$; for such $m$, (c) gives $|f(x)|-2^{-m}<u_{m}$, so $|t_{m}(x)-f(x)|<2^{-m}<\varepsilon$. By Convergent Sequences of Real Numbers (i), $(t_{m}(x))_{m\in\mathbb{N}}$ converges to $f(x)$.