$f : \mathbb{R} \to \mathbb{R}$ (Lipschitz) continuous implies $f(A)$ is Borel for all Borel $A$.

Full question:

Let $(\mathbb{R}, \mathfrak{M}, m)$ denote the measure space $\mathbb{R}$ equipped with the Borel $\sigma$-algebra and the Lebesgue measure. Suppose $f : \mathbb{R} \to \mathbb{R}$ is Lipschitz continuous with Lipschitz constant $L$. Show $f(A) \in \mathfrak{M}$ and $m(f(A)) \le L m(A)$ for all $A \in \mathfrak{M}$.

This is a question from an old preliminary exam. I feel quite comfortable, after assuming measurability of $f(A)$, in showing that $m(f(A)) \le L m(A)$ for all $A \in \mathfrak{M}$. I have found similar questions on this site, but none that do not assume $f$ is either one-to-one or onto, as well as the closest one to my question having an accepted answer that says the question is wrong.

My progress (aka simple cases):

If $A \subset \mathbb{R}$ is connected, we know that $A$ is either a point, or an interval (possibly infinite, and can be open, closed, or half-open). However, since $f$ is continuous, the set $f(A)$ must also be connected, so $f(A)$ is also a point, or an interval. In particular, if $A$ is connected, then $f(A)$ is either an $F_{\sigma}$ or a $G_{\delta}$ set (countable union of closed sets and countable intersection of open sets respectively).

If $A \subset \mathbb{R}$ is open, due to the separability of $\mathbb{R}$, it must be a countable union of open intervals, so $A = \cup_{i=1}^{\infty} I_{i}$ for intervals $I_{i}$ and consequently $f(A) = \cup_{i=1}^{\infty} f(I_{i})$ is an $F_{\sigma}$ or $G_{\sigma \delta}$ set (the latter being countable unions of $G_{\delta}$ sets).

If $A \subset \mathbb{R}$ is compact, then $f(A)$ is compact, and hence closed. If $A \subset \mathbb{R}$ is closed but not compact, we can write $A = \cup_{n = 1}^{\infty} A \cap [-n,n]$, and consequently, $f(A) = \cup_{n=1}^{\infty} f(A \cap [-n,n])$ is the countable union of compact sets, and hence a $G_{\sigma}$ set.

My issue:

I know that the Borel hierarchy continues on for an uncountable number of steps. So, I cannot use induction to try to finish the proof based off of these simple cases.

So far unsuccessful, but yet a promising idea:

I'm tempted to appeal to the monotone class lemma, (see Folland's Real Analysis page 66, Lemma 2.35) by showing that the sets from my simple case combined with some sets that involve $\mathbb{R} \setminus f(A)$ form an algebra and a monotone class, and consequently their $\sigma$-algebra is the same $\sigma$-algebra that is generated by the sets from the simple cases (which I believe is the Borel $\sigma$-algebra).

The big guns:

There's a remark (2.2.13) on the bottom of page 69 and top of page 70 in Federer's "Geometric Measure Theory" that says:

If $f : X \to Y$ is continuous, $X$ is a complete, separable metric space, $Y$ is a Hausdorff space, $\mu$ measures $Y$, and every closed subset of $Y$ is $\mu$-measurable, then the $f$ image of every Borel subset of $X$ is $\mu$-measurable.

This remark seems to imply the problem is true. However, this remark follows from two sections of Federer's GMT that are far beyond the expected knowledge for the prelim I'm studying for, and the sections are too terse for me to yet understand. Moreover, Federer goes through the process of defining Suslin sets, and considering the image of Borel sets as projections of Suslin sets. Again, none of this seems like "prelim-level" material. However, since Lebesgue originally thought he'd proved something along these lines (the error in his proof was found by Suslin) I'd be surprised if there's a more elementary proof. Maybe some of the restrictions in this specific problem make it possible.

Thanks for reading. Cheers.

Solution 1:

It's false; $f(A)$ need not be Borel.

Let $C$ be the middle-thirds Cantor set. Define $\pi_1:C\times C\to C$ by $\pi_1(x,y)=x$.

True Fact There exists a Borel set $B\subset C\times C$ such that $\pi_1(B)$ is not Borel.

Hand Waving Well, that's well known with $\Bbb R$ in place of $C$. There simply cannot be any difference between $\Bbb R$ and $C$ in this regard, qed. Indeed it seems likely that the construction is going to be simpler for $C$. Look for instance at the sketch here. The sorts of codings needed there can certainly be done just as well with $C$ in place of $\Bbb R$. In fact when I think about natural ways to code well-orders, etc., as reals what I actually get are codings as elements of a Cantor set! For example, a natural way to code $R\subset\Bbb N\times \Bbb N$ as a real is $$R\mapsto\sum_{(n,m)\in R}3^{-2^n3^m},$$and that does map $R$ to an element of a certain Cantor set.

If someone who knows that stuff is inclined to confirm the true fact that would be fine.

Recall that $C$ is the set of all sums $$x=\sum_{j=1}^\infty x_j3^{-j}$$where each $x_j$ is $0$ or $2$. In defining various maps it will be convenient to write as though $$x=(x_1,x_2,\dots).$$Various inequalities below will be clear if you note that if $x,y\in C$ with $x\ne y$ then $$|x-y|\sim 3^{-n},\quad n=\min\{j:x_j\ne y_j\}.$$

We begin. Let $h:C\to C\times C$ be the obvious bijection $$h(x)=((x_1,x_3,\dots),(x_2,x_4,\dots)).$$Note that $$|h(x)-h(y)|\le c|x-y|^{1/2}.$$Suppose $B\subset C\times C$ is a Borel set such that $\pi_1(B)$ is not Borel, and let $$A=h^{-1}(B).$$Let $$g=\pi_1\circ h.$$Now $g:C\to C$ is continuous, $A\subset C$ is Borel but $g(A)$ is not Borel.

But $g$ is not Lipschitz; we have just $|g(x)-g(y)|\le c|x-y|^{1/2}$. Here's the part that works for $C$ but not for $\Bbb R$: Define $s:C\to C$ by $$s(x)=(x_1,0,x_2,0,\dots).$$Then $s$ is injective, in particular $s$ is a homeomorphism from $C$ onto $s(C)$, and $s$ satisfies $$|s(x)-s(y)|\le c|x-y|^2.$$(Exercise: Show that if $\phi:\Bbb R\to\Bbb R$ satisifes $|\phi(x)-\phi(y)|\le c|x-y|^2$ then $\phi$ is constant. Figure out why that argument does not apply here.)

So we define $f:C\to C$ by $f=s\circ g$; then $f$ is Lipchitz but $f(A)$ is not Borel.

Finally, any Lipschitz $f:C\to C$ can easily be extended to a Lipschitz map $f:\Bbb R\to\Bbb R$. For example, define $f$ to be constant on $(-\infty,0]$, constant on $[1,\infty)$, and if $(a,b)$ is a bounded component of $\Bbb R\setminus C$ define $f$ to be linear on $[a,b]$.