# Measure Theory/Devil's Staircase
## Counter-Examples

It is at this point that it will be instructive to think about counter-examples to the results that we're hoping to obtain. In particular, we want to find examples of functions, for which $\int _{(a,b)}f'=f(b)-f(a)$ does not hold.
Of course we need the derivative to exist, a.e., in order for this conversation to make any sense. We know that this happens when f is monotone, or of bounded variation.
So is monotonicity, or bounded variation, sufficient for the equation to hold?
No it is not, and here is an easy counter-example: the unit step function.
    $u(x)=\mathbf {1} _{[0,\infty )}$
* Unit Step Counter-example
* Show that the unit step function does not satisfy $\int _{(a,b)}u'=u(b)-u(a)$ for some choice of a and b.
But that is simple enough -- clearly the problem with this function is its discontinuity.
Suppose that we impose both conditions. If a function is both of bounded variation and continuous, is it now guaranteed that $\int _{(a,b)}f'=f(b)-f(a)$?

### A Counter-Example

This question is significantly harder to answer, but we will see that the answer is again "no".
This may be dispiriting, because we now are really in a panic over what condition we might actually impose on f to ensure the equation.
Of course being differentiable everywhere (and not just almost everywhere) is one such condition, because that was already proved in elementary analysis! But in measure theory we should want looser conditions that are more appropriate for the concepts of measurability of sets and functions.
But in fact, by inspecting the example below will actually give us some insight into exactly what is needed for the equation to hold.
Below we will construct a function, s, with the amazing collection of properties.
* Monotonically increasing on [0,1].
* Uniformly continuous. (Not merely "continuous"!)
* Its derivative is identically zero a.e.
* $s(0)=0$ and $s(1)=1$.
* For every real number c, there is some interval $[a,b]\subseteq [0,1]$ for which the average rate of change, ${\frac {s(b)-s(a)}{b-a}}$, is greater than c.

## The Devil's Staircase

The construction will look very familiar to our work on the ternary set.
On the interval $x\in (1/3,2/3)$ we defined $s(x)=1/2$. That is to say, on this interval, the function is constant.
On the interval $x\in (1/9,2/9)$ we define $s(x)=1/4$, and on the interval $x\in (7/9,8/9)$ we define $s(x)=3/4$.
The pattern is that we proceed by taking middle thirds of each interval on which we have not yet defined the function. On each such middle third the value is constant, and half-way between the previously defined values (except at the end-points where we use 0 or 1 and a previously defined value).
It is clear that this function will be undefined at 0, 1, 1/3, and many other points, if we leave it as is. We could allow that, or if we want it defined throughout the interval, we could use limits to define the value of the function at any such point.
For instance, if we want to give this function a value at 0, we could observe the sequence $x_{1}={\frac {1}{2}},x_{2}={\frac {1}{6}},x_{3}={\frac {1}{18}},...$ and see that $s(x_{1})={\frac {1}{2}},s(x_{2})={\frac {1}{4}},s(x_{3})={\frac {1}{8}},\dots$. So if we define $s(0)$ by the limit of this sequence of values, we would set $s(0)=0$.
Here is a more formal definition.
Definition: devil's staircase
For each n we define the nth open set,
    ${\mathcal {O}}_{n}=[0,1]\smallsetminus C_{n}$
where $C_{n}$ is the nth ternary set defined in Section 2, Lesson 0: Counter-Examples. Define $s_{n}:{\mathcal {O}}_{n}\to [0,1]$ to be the monotonically increasing function which is constant on each of the $2^{n}-1$ intervals of ${\mathcal {O}}_{n}$, and takes each value in the set $\left\{{\frac {1}{2^{n}}},{\frac {2}{2^{n}}},\dots ,{\frac {2^{n}-1}{2^{n}}}\right\}$. Call $s_{n}$ the nth staircase function.
Define $s_{\infty }=\bigcup _{n=1}^{\infty }s_{n}$.
Define the function $s:[0,1]\to [0,1]$ by the equation $s(x)=\lim _{t\to x^{+}}s_{\infty }(t)$ at all points $x\in [0,1)$ and $s(1)=\lim _{t\to 1^{-}}s_{\infty }(t)$. Call s the Devil's staircase function.
Note that the union of functions is sensible, when a function is identified as a set of pairs.
* Exercise 1. Devil Warmups
* Using the official definition in the green box, compute $s(1/2),s(0),s(1/3)$.
* Then prove that s is monotonically increasing and continuous. Because it is continuous and the domain is compact, infer that s is uniformly continuous.
* Also prove that for any point in any ${\mathcal {O}}_{n}$, the function s is differentiable there and has derivative equal to 0.

### The Up-Shot

Recall that the interest in the Devil's staircase is that it demonstrates the failure of $\int _{(a,b)}f'=f(b)-f(a)$ even for a monotonically increasing, uniformly continuous function.
If we are to hope to ensure this equation by finding some property of f, it must be stronger than these two properties combined.
One way to try to approach what is going "wrong" with the Devil's staircase is to imagine its property of uniform continuity. By the fact that it is uniformly continuous, if we let $\varepsilon \in {\mathbb {R}}^{+}$ then we know there is a $\delta \in {\mathbb {R}}^{+}$ such that if we shrink the domain of s down to any interval of width $\delta$, the function will not change by more than $\varepsilon$.
Just as an example, let's take $\varepsilon =1/2$ and think about the $\delta$ for which, if $I=[c,d]\subseteq [0,1]$ is any interval of width at most $\delta$, then the change of s on I is at most $\varepsilon$.
    $|f(d)-f(c)|<\varepsilon =1/2$
But if you look at a graph of s you can see that it is mostly constant, except at points where it grows steeply. In fact, on some intervals it seems to become arbitrarily steep, although where it does so is on a very thin portion of the domain.
If we would like to try to see something go wrong, what if we didn't just limit ourselves to this interval I? If we had the freedom to chop up I into pieces and then slide them around to convenient places in the domain, we could really make the function grow fast -- perhaps so fast that it will exceed 1/2, no matter how small $\delta$ is.
Let's start by observing that if we set $\delta =1/9$. Then, on a single interval of width $\delta$, the greatest change in the function that you could possibly have is what you get from setting the left edge to 0 and the right edge to 1/9.
That gives a net change of $s(1/9)-s(0)=1/4-0=1/4$. Since this is smaller than $\varepsilon =1/2$, then for uniform continuity this would be an acceptable $\delta$.
But a portion of that interval is "wasted" on the part that stays constant from 1/27 to 2/27. If we had the freedom to break that portion out, and slide it over to, say, 6/27 to 7/27, then we would capture a bit of extra increase. With the intervals (0, 1/27), (2/27, 3/27), (6/27, 7/27), on each interval the function s increases by a total of 1/8. Therefore if we total all of these together, the net change over all the intervals is 3/8.
That's not quite the 1/2 that we need, but clearly it's in the right directly. And it is reasonable to think that if we just played this game one more time, chopping our intervals into pieces of width, say, 1/81, then we might exceed the $\varepsilon =1/2$ that we need.
* Exercise 2. Exceed 1/2
* Show that, on the interval (0, 1/81), the function s increases by 1/16.
* Also show that there are 16 intervals in total, each of width 1/81, on which s increases by this much.
* Infer that, if we use 8 of these intervals, the net width of the intervals combined will be 8/81 which is less than the 1/9 that we chose so long ago. But moreover, the net change in the function totaled over all of these intervals is $8/16=1/2=\varepsilon$.
What this all seems to show is that s lacks this property, which is like uniform continuity except that we have the freedom to chop up the interval in the domain and move the pieces around.
In the next lesson we will define this property rigorously, and then prove that this is exactly the property that ensures
    $\int _{(a,b)}f'=f(b)-f(a)$