Cantor function 2: Electric boogaloo

Thinking out loud about the recursive Cantor function construction again. I realized shortly after the post that the points \(x = k/2^N\) do not become fixed points. On the other hand it seems right to focus on the plateaus where \(y = f_N(x) = k/2^N\)... the difficulty is showing that these plateaus are "stable" when going beyond \(n = N\) in the sequence.

I think the way to do this is to figure out how it is that the plateaus can be stable. The middle plateau present in \(f_1\) is obviously stable by construction, but how can we say that others are? I think the answer is: The plateaus in \(f_n\) were constructed recursively from the plateau/s in \(f_{n - 1}\), which latter plateaus are still present in \(f_n\), so when we recursively construct \(f_{n+1}\) from \(f_n\), the plateaus from \(f_{n - 1}\) are still present and end up reconstructing the plateaus from \(f_n\). That's a messy mouthful of an argument, though, and sounds annoying to formalize.

More concretely – the two "new" plateaus in \(f_2\) were each constructed from the single plateau in \(f_1\). That means that when we construct \(f_3\) by shrinking \(f_2\), we're going to recreate the plateaus from \(f_2\). They're "new again." (Convergent evolution, sort of. Recursive evolution? So, \(f_3\) contains the same plateaus as \(f_2\) because it contains the same plateaus as \(f_1\), and because we always "shrink down" in the same way, those older plateaus "shrink down" to the same thing they did before: The plateaus of \(f_2\).

This is kind of neat.

It also sounds like a pain to describe in a formal proof. Where would I even start?

I thought about it for a bit and I think this works...

We're going to first define a sequence of sets of arbitrary points. Each set \(S_N\) will contain one point on every plateau in \(f_N\). Define \(S_1 = \{1/2\} \). Define \(S_n\) recursively as follows: \(S_{n+1} = \{1/2\} \cup (1/3)S_n \cup \left((1/3)S_n + 2/3\right)\), where multiplication/addition is defined pointwise.

These sets are nested

I claim first of all that \(S_n \subset S_{n+1}\) for all \(n\).

Clearly this is true for \(n = 1\). Suppose it's true for some specific \(n\) that \(S_n \subset S_{n+1}\). We then want to show \(S_{n+1} \subset S_{n+2}\).

Let \(x \in S_n\). If \(x\ = 1/2\) then \(x\in S_{n+2}\) trivially. Otherwise, either \(x \in (1/3)S_n\) or \(x \in (1/3)S_n + 2/3\). Suppose \(x \in (1/3)S_n\). Then \(x = (1/3)x'\) where \(x' \in S_n\). But \(S_n \subset S_{n+1}\), so \(x' \in S_{n+1}\). This means that \((1/3)x' = x \in (1/3)S_{n+1}\), so \(x \in S_{n+2}\). A similar argument shows that if \(x \in (1/3)S_n + 2/3\) then \(x \in (1/3)S_{n+1} + 2/3\), hence \(x \in S_{n+2}\). \(\blacksquare\)

(The space before the halmos there should be a non-breaking space but oh well.)

The value on these points never changes

Second, I claim that under the recursive definition of \(f_n\), we have \(f_n(x) = f_N(x)\) for all \(n \geq N\) whenever \(x \in S_N\).

This is going to be a double induction argument, so sort of ugly, but bear with me. First, induction on \(N\), then induction on \(n\). The base case \(N = 1\) is clear since \(S_1 = \{1/2\}\) and \(f_n(1/2) = 1/2\) by definition. Suppose now the property is true for \(N-1\), that is that for all \(x \in \S_{N-1}\) and all \(k \geq N - 1\) we have \(f_k(x) = f_{N-1}(x)\). I'll show that the desired property holds for \(N\).

Suppose \(x \in S_N\). The base case where \(n = N\) is clear. Suppose we can show that \(f_n(x) = f_N(x)\). I will show that also \(f_{n+1}(x) = f_N(x)\).

If \(x = 1/2\), trivially \(f_{n+1}(x) = f_n(x) = f_N(x) = 1/2\).

Otherwise, suppose \(x \in (1/3)S_{N-1}\). By definition \(x = (1/3)x'\) for some \(x' \in S_{N-1} \subset S_N\). Then \(x \leq 1/3\), so \(f_{n+1}(x) = (1/2) f_n(x')\). Now because \(x' \in S_N\) we have \(f_{n+1}(x) = (1/2)f_N(x')\). But by definition \(f_N(x) = (1/2)f_{N-1}(x')\), and by the earlier inductive assumption, \(f_N(x') = f_{N-1}(x')\) because \(x' \in S_{N-1}\). This shows that \(f_{n+1}(x) = (1/2)f_{N-1}(x') = f_N(x)\), as desired.

Finally suppose \(x \in (1/3)S_{N-1} + 2/3\). Then \(x = (1/3)x' + 2/3\) for some \(x' \in S_{N-1} \subset S_N\). It's clear that \(x \geq 2/3\), which means \(f_{n+1}(x) = (1/2)f_n(3x - 2) + 1/2 = (1/2)f_n(x') + 1/2\). Again \(x' in S_N\) so \(f_{n+1}(x) = (1/2)f_N(x') + 1/2\) by way of \(f_n(x')\). By definition \(f_N(x) = (1/2)f_{N-1}(x') + 1/2\), and by the earlier inductive assumption, \(f_N(x') = f_{N-1}(x')\) since \(x' \in S_{N-1}\). Hence, we have that \(f_{n+1}(x) = (1/2)f_{N-1}(x') + 1/2 = f_N(x)\) as desired. \(\blacksquare\)

Phew.

Interlude

So we've shown so far that the points \(x \in S_N\) are actually "nice" in the sense that their value \(f_n(x)\) never changes as we increase \(n\) beyond \(N\).

What I would now really like to do is show that \(f_N(S_N) = \{k/2^N : k \in \mathbb{Z}_{\geq 0} \wedge k < 2^N\}\). I'd also like to show that \(f_n(x)\) is increasing (non-strictly).

If we knew that, would that be enough to prove \(f_n\) converges uniformly?

I think so. For any \(\epsilon > 0\) we can find \(N\) such that \(1/2^N < \epsilon\). Let \(m, n \geq N\) and \(x \in [0, 1]\). Then \(x\) must be either (1) one of the points we know, in which case \(f_m(x) = f_n(x) = f_N(x)\) and we're happy, or (2) between two "plateaus" of \(f_N\), or (3) between a boundary point, that is 0 or 1, and a plateau. In case (2) it's between points \(a < b\) with known value \(k/2^N\) and \((k+1)/2^N\) respectively. These values are correct for \(f_N\) but from the work we just did, we know that \(f_m\) and \(f_n\) must have the same value at \(a\) and \(b\). Now, because \( in which case we know that both \(f_m(a) \leq f_m(x) \leq f_m(b)\), and likewise for \(f_n\). But this implies that \(f_m(a) - f_n(b) \leq f_m(x) - f_n(x) \leq f_m(b) - f_n(a)\). That is: \(-1/2^N \leq f_m(x) - f_n(x) \leq 1/2^N\), or \(|f_m(x) - f_n(x)| \leq 1/2^N < \epsilon\). The argument for (3) is almost identical, except that either \(a = 0\) with value \(0\), or \(b = 1\) with value \(1\). \(\blacksquare\)

So, uh, yes, this would let us prove exactly what we want to prove.

I guess let's get on with the "image" and "increasing" proofs.

Image

Reminder: We want to show that \(f_N(S_N) = \{k/2^N : k \in \mathbb{Z}_{\geq 0} \wedge k < 2^N\}\).

I think we can do this by induction again. Just a single induction – yay! Much less confusing!

The base case here is again easy. For \(N = 1\) we have \(f_1(\{1/2\}) = \{1/2\}\).

Suppose that \(f_N(S_N) = \{k/2^N : k \in \mathbb{Z}_{\geq 0} \wedge 0 < k < 2^N\}\). We want to show that \(f_{N+1}(S_{N+1}) = \{k/2^{N+1} : k \in \mathbb{Z}_{\geq 0} \wedge 0 < k < 2^{N+1}\}\).

Well, this is simple. Our recursive definition defines \(S_{N+1}\) as a union, and images of unions are "nice" in that they are just the union of the images. Defining that more formally: Given \(g : A \to B\) for \(A, B\) some sets, and given some subsets \(U, V\) of \(A\), we have \(g(A \cup B) = g(A) \cup g(B)\)).

This applies in our case as follows:

\begin{align} f_{N+1}(S_N) &= f_{N+1}(\{1/2\}) & \;\cup\; & f_{N+1}((1/3)S_N) & \;\cup\; & f_{N+1}((1/3)S_N + 2/3) \\ &= \{1/2\} & \;\cup\; & (1/2)f_N(S_N) & \;\cup\; & ((1/2)f_N(S_N) + 1/2) \end{align}

We can then rewrite each term into the proper form:

\begin{align} \{1/2\} &= \{2^N/2^{N+1}\} \\ (1/2)f_N(S_N) &= \{k/2^{N+1} : k \in \mathbb{Z}_{\geq 0} \wedge 0 < k < 2^N\} \\ (1/2)f_N(S_N) + 1/2 &= \{k/2^{N+1} : k \in \mathbb{Z}_{\geq 0} \wedge 2^N < k < 2^{N+1}\} \end{align}

Now clearly between these we have:

\[f_{N+1}(S_{N+1}) = \{k/2^{N+1} : k \in \mathbb{Z}_{\geq 0} \wedge 0 < k < 2^{N+1}\}\]

That proves the inductive step, thus the image property holds for all \(N\), as desired. \(\blacksquare\)

Increasing

Finally we want to show that for all \(n\), the function \(f_n\) is increasing.

Clearly it's true for \(n = 1\). It's a piecewise function whose pieces are all increasing and where the pieces agree on the boundary points.

Suppose it's true that \(f_n\) is increasing. We want to show that \(f_{n+1}\) is increasing. Well, on \([0, 1/3]\) it's clearly increasing because it's just \((1/2)f_n(3x)\). That's a composition of 3 increasing functions, so the result is increasing. On \([1/3, 2/3]\) it's also clearly increasing because it's just always equal to \(1/2\) on that interval. And on \([2/3, 1]\), it's again increasing, because it's equal to \((1/2)f_n(3x - 2) + 1/2\). We can write that as a composition of 3 increasing functions, so the result is increasing.

This proves the inductive step, so by induction \(f_n\) is increasing for all \(n\).

Final proof

I gave the actual proof of uniform convergence back in the interlude. We have now proven all of the pieces that are required to make that proof work. So... it works. We've proven this sequence of functions converges uniformly. Yay.

Postmortem

What a clumsy mess of a proof.

Well, the final stages worked out nicely. It's just everything up to that point. It's having to define this auxilliary set that we don't care about in and of itself. It's the double induction. Figuring out how to avoid those messy things would be even more work, though. Ugh.

The final part of this exercise is to prove that the limit function \(f\) is continuous and increasing with boundary values being what you'd expect, and that the derivative \(f'\) equals zero on \([0, 1] \backslash C\), where \(C\) is the Cantor set. That sounds like a pain overall.

Most of the pieces re simple. Continuity isn't bad. Proving increasingness... well, if we can show that increasing-ness is preserved under uniform convergence, that would do it. The boundary values are easy because the value of \(f\) at boundary \(x\) is the limit of the sequence \(f_n(x) = x\) for both \(x = 0\) and \(x = 1\). That limit is pretty clearly \(x\) because the sequence is constant on these boundary points.

The hard part is the derivative. I think it shouldn't be all that hard though. I think the same ideas explored in this proof would work, although there is probably a mechanically easier way to use them. Obviously \([0, 1] \backslash C_1 = (1/3, 2/3)\) is the first plateau, on which it should be easy to prove that \(f'(x) = 0\). I think we can do a similar recursive argument to the one in "The value on these points never changes" to prove that \(f_n'(x) = 0\) on \([0, 1] \backslash C_N\) for all \(n \geq N\). That is: The derivative is eventually zero on every point in \([0, 1] \backslash C\). Then it just remains to prove that \(f'(x) = 0\) under these conditions.

That seems like it should follow from some other things we know, but I'm not sure how. I'd have to review the definition of the derivative (it's been a while) and the various derivative-related theorems. I think the derivative is not necessarily continuous here, so we can't make that sort of an argument. But it feels like we could argue it from some slightly more general theorem... maybe.

It feels like it would be nicer to prove things directly about \(f'\)'s value on \([0, 1] \backslash C\). But we don't actually have a definition of it other than "it's the limit of the sequence." So I don't think that this is practical.