Lebesgue's singular function nondecreasing

Question

I'm reading Hewitt-Stromberg Real and Abstract Analysis. I fail Exercise (8.28). Here Lebesgue's singular function $\psi$ is first defined, after at $0$, on the open intervals excluded from Cantor's set $P$:

$\psi(0)=0$

$\psi(x)=\frac{2k-1}{2^n}$ for $x \in I_{n,k}$

$\psi(x)=sup\{\psi(t):t \in P', t<x\}$ for $x \in P\cap\{0\}' \qquad$ (Note $P'$, the complementary set to $P$, is the union of all $I_{n,k}$, $n=1, ..., \infty, k=1, ..., 2^{n-1})$

I don't succeed proving that $\psi$ is nondecreasing. I see this is true by programming in SAS that whenever $x \in I_{n,k}, y \in I_{m,l}, x<y, n<m$, it follows $2k-1 < \frac{2l-1}{2^{n-m}}$ which may be part of the proof but the induction does'nt jump out at me.

Maybe I should clarify about the $I_{n,k}$, especially the order of $k's$: these are the open 1/3-mid-intervals excluded when constructing the Cantor ternary set (Consider the left and right parts $J_{n,l}$ too):

$I_{1,1}=(\frac{1}{3},\frac{2}{3})$, $J_{1,1}=(\frac{0}{3},\frac{1}{3})$, $J_{1,2}=(\frac{2}{3},\frac{3}{3})$,

$I_{2,1}=(\frac{1}{9},\frac{2}{9})$, $I_{2,2}=(\frac{7}{9},\frac{8}{9})$, $J_{2,1}=(\frac{0}{9},\frac{1}{9})$, $J_{2,2}=(\frac{2}{9},\frac{3}{9})$, $J_{2,3}=(\frac{6}{9},\frac{7}{9})$, $J_{2,4}=(\frac{8}{9},\frac{9}{9})$,

$I_{3,1}=(\frac{1}{27},\frac{2}{27})$, $I_{3,2}=(\frac{7}{27},\frac{8}{27})$, $I_{3,3}=(\frac{19}{27},\frac{20}{27})$, $I_{3,4}=(\frac{25}{27},\frac{26}{27})$, $J_{3,1}=(\frac{0}{27},\frac{1}{27})$, $J_{3,2}=(\frac{2}{27},\frac{3}{27})$, $J_{3,3}=(\frac{6}{27},\frac{7}{27})$, $J_{3,4}=(\frac{8}{27},\frac{9}{27})$, $J_{3,5}=(\frac{18}{27},\frac{19}{27})$, $J_{3,6}=(\frac{20}{27},\frac{21}{27})$, $J_{3,7}=(\frac{24}{27},\frac{25}{27})$, $J_{3,8}=(\frac{26}{27},\frac{27}{27})$,

$I_{4,1}=(\frac{1}{81},\frac{2}{81}), ...$,

$I_{n,k}=(\frac{a_k}{3^n},\frac{a_k+1}{3^n})$, $k=1,...,2^{n-1}$ and $a_k$ chosen as the numerator of the left limit of the 1/3-mid-interval of the considered interval of length $\frac{1}{3^{n-1}}$, i.e. $a_k=1, 7, 19, 25, 55, 61, 73, 85, ...$

Answer 1

I found a proof for points in the inner sets $I_{n,k}$.

As a preparation, find the 2nd indices l of the closest Intervals $I_{n+1,l}$. $I_{n,k}$ has a left and a right neighbor $J_{n,2k-1}$ and $J_{n,2k}$ from which in the next step the interior third is excluded as $I_{n+1,2k-1}$ and $I_{n+1,2k}$. On the left side of $I_{n,k}$ now continuing to $n+2$, $n+3$, ..., $n+i$ only with the right side thus approximating $I_{n,k}$ from left, we're getting by doubling the 2nd index in each step $I_{n+2,2(2k-1)}$, $I_{n+3,2^2(2k-1)}$, ..., $I_{n+i,2^{i-1}(2k-1)}$, and similar approximating on the right side we're getting by doubling the second index and subtracting 1 in each step $I_{n+2,2^2k-1}=I_{n+2,2(2k-1)+1}$, $I_{n+3,2^2(2k-1)+1}$, ..., $I_{n+i,2^{i-1}(2k-1)+1}$.

Now having $x \in I_{n,k}$ and $y \in I_{n+i,l}$, we may restrict to the closest interval $I_{n+i,l}$ to $I_{n,k}$ because $\psi$ is clearly increasing in the intervals of step $n+i$. We have $\psi(x)=\frac{2k-1}{2^n}=\frac{2^i(2k-1)}{2^{n+i}}$ and

• for $y<x$, i.e. $y \in I_{n+i,2^{i-1}(2k-1)}$, $\psi(y)=\frac{2^i(2k-1)-1}{2^{n+i}}$, so $\psi(y)<\psi(x)$, and
• for $y>x$, i.e. $y \in I_{n+i,2^{i-1}(2k-1)+1}$, $\psi(y)=\frac{2^i(2k-1)+1}{2^{n+i}}$, so $\psi(y)>\psi(x)$.

Remains to prove $\psi(y)\le\psi(x)$ for $y<x$ with $y \in P$ or $x \in P$. For $x \in P$ this is immediately clear due to the 3rd definition part. For $y \in P$ and $x \notin P$ it follows too since $x \in I_{n,k}$ for some $n,k$ and $y$ either is the left boundary of $I_{n,k}$ or there is another $I_{m,l}$ in between, and $\psi(y)$ is the supremum of values that are all lower than $\psi(z)$ for $z \in I_{m,l}$.