25
$\begingroup$

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be a function. It is well-known that, using transfinite recursion with a well-ordering of $\mathbb{R}$, one can construct two injective functions $g,h: \mathbb{R} \rightarrow \mathbb{R}$ such that $f=g+h$. For example, see §12.17 of "Problems and Theorems in Classical Set Theory" by Komjáth and Totik.

My question is to what "definable" extent does this result generalize. More specifically, can we write every Borel map $f: \mathbb{R} \rightarrow \mathbb{R}$ as a sum of two Borel injections? Indeed, it is not clear to me whether we can even do this decomposition for continuous functions as a sum of two Borel injections.

$\endgroup$
3
  • 12
    $\begingroup$ Nice question. For a differentiable function $f$ on $[0,1]$ (or even just Lipschitz), there will be some $m$ large enough that $g(x) = f(x)+mx$ and $h(x) = f(x)-mx$ are both injective. By choosing larger and larger $m$'s on the intervals $[n,n+1]$, you can probably get every differentiable function $\mathbb R \rightarrow \mathbb R$ as a sum of two Borel injections. The same idea doesn't quite work for general continuous functions, though. $\endgroup$
    – Will Brian
    Nov 24, 2023 at 17:39
  • 2
    $\begingroup$ Does it get any easier with three or more summands? $\endgroup$ Nov 25, 2023 at 15:48
  • $\begingroup$ It seems to me that we should talk here about Baire function classification (rather than Borel). $\endgroup$
    – Wlod AA
    Nov 29, 2023 at 2:37

2 Answers 2

27
$\begingroup$

The answer is yes. Every function on the reals is the sum of two injective functions, and this can be done in a highly effective manner, constructing the two functions $g,h$ from $f$ without any need for the axiom of choice or transfinite recursion.

Theorem. (ZF)

  1. Every function on the reals is the sum of two injective functions: for every $f:\newcommand\R{\mathbb{R}}\R\to\R$ there are injective $g,h:\R\to\R$ with $f=g+h$.
  2. Furthermore, this is possible with functions $g$ and $h$ that are arithmetically definable from $f$, and indeed, the digits of $g(x)$ and $h(x)$ are uniformly computable from oracles specifying the digits of $x$ and $f(x)$.
  3. In particular, every Borel function $f$ is the sum of two injective Borel functions $g$ and $h$.

The proof will rely on the following key lemma.

Key lemma. There is a pairing function on the reals $x,y\mapsto\langle x,y\rangle$ such that $y-\langle x,y\rangle$ also is a pairing function. That is, for reals $x,y$ we can define a real number $\langle x,y\rangle$ for which:

  1. From the value of $\langle x,y\rangle$ we can uniformly recover both $x$ and $y$.
  2. From the value of the difference $y-\langle x,y\rangle$ we can uniformly recover both $x$ and $y$.

Proof. Given $x$ and $y$, let $z$ be a binary sequence that encodes both $x$ and $y$ in some sensible concrete manner. We shall first specify the even digits of $\langle x,y\rangle$ with $0$s and $1$s in such a way so as to list out $z$ on those digits, so that the $k$th digit of $z$ is the same as the $2k$th digit of $\langle x,y\rangle$. This will ensure that $\langle x,y\rangle$ is a pairing function, regardless of how we define the odd digits. Next, we specify the odd digits of $\langle x,y\rangle$ in such a way that the parity pattern of the odd digits of the difference $y-\langle x,y\rangle$ is again the binary pattern of $z$. So from the value of $y-\langle x,y\rangle$ we can recover $z$ and hence both $x$ and $y$. $\Box$

Proof of theorem. Let's now prove the theorem. Note that the pairing function $\langle x,y\rangle$ in the key lemma is computable in the relevant sense from oracles for $x$ and $y$. Let $$g(x)=\langle x,f(x)\rangle\qquad$$ and $$h(x)=f(x)-\langle x,f(x)\rangle.$$ The function $g$ is injective, since from $\langle x,f(x)\rangle$ we can recover $x$. The function $h$ is injective, since the key lemma ensures that from $f(x)-\langle x,f(x)\rangle$ we can recover $x$. And clearly $f=g+h$, so we have achieved $f$ as the sum of two injective functions.

The proof is effective, since the functions $g$ and $h$ are computable from $f$. $\Box$

If we were working on Baire space $\mathbb{N}^{\mathbb{N}}$ instead of $\R$, that is, with infinite sequences of natural numbers $x:\mathbb{N}\to\mathbb{N}$ instead of real numbers, it is a slightly more natural context, since working digit-by-digit is more natural in Baire space. In particular, in that context the functions $g$ and $h$ arising in the proof would be continuous, if $f$ is, since in order to know the first $k$ values of $g$ or $h$ it would suffice to know the first $k$ values of $x$ and $f(x)$. On the real numbers, however, this reasoning does not quite transfer to $\R$, because the non-unique representations cause certain boundary issues — interleaving digits is not a continuous process since $1=0.999\bar 9$. And so my functions $g$ and $h$ are not continuous, even when $f$ is. But I think it might be possible to patch this up somehow to achieve the continuous case as a special case of the fully general case as I have. (Update: Will Sawin explains how the answer of Joonas Ilmavirta shows that the continuous case will be impossible.)

Let me finally observe that once we know the two-injective-summand case is true, then we easily get three injective summands or any number by simple scaling. For example, from $f=g+h$ we can write $f=g+\frac12 h+\frac12 h$ and so forth.

Constructive logic? My answer has a computable nature, but I am unsure whether the proof can be made completely constructive, that is, in constructive logic. I would welcome answers by those who could say something about that. (Update: Will Sawin explains in his comment below why we should expect no constructive proof.)

$\endgroup$
2
  • 5
    $\begingroup$ I think the continuous case is impossible. $g$ and $h$ would have to be continuous and injective, so monotonic, so locally have bounded variation, but while $f$ must be continuous it need not have bounded variation even locally. (Inspired by Joonas Ilmavirta's answer mathoverflow.net/a/459108/18060). I guess this has applications to your last question about constructive logic as this should give a negative answer in constructive models where all functions are continuous. $\endgroup$
    – Will Sawin
    Nov 28, 2023 at 19:11
  • $\begingroup$ @WillSawin Thank you, that is very clear. $\endgroup$ Nov 28, 2023 at 19:40
13
$\begingroup$

It works at least for (locally) absolutely continuous functions. Such a function is the integral of a locally $L^1$ function. This weak derivative can be written as a sum of a positive and negative function, and their integrals then define your functions $g$ and $h$.

That is, an absolutely continuous function on the reals can be written as a sum of an increasing and a decreasing function. These monotonicties are not necessarily strict, but that is easily fixed by adding and subtracting the same small linear function to these functions. Strict monotonicity implies injectivity.


A bounded function can be written as the sum of two monotone functions if and only if it has (locally) bounded variation. If you want to get injectivity via monotonicity, this class is optimal.

$\endgroup$
4
  • 5
    $\begingroup$ More generally, this holds for functions of bounded variation. $\endgroup$ Nov 25, 2023 at 7:56
  • 2
    $\begingroup$ @EmilJeřábek Good point! I added that in. $\endgroup$ Nov 25, 2023 at 11:51
  • $\begingroup$ Given a Borel $f:\mathbb{R}\rightarrow\mathbb{R}$, does there necessarily exist a Borel bijection with Borel inverse $T:\mathbb{R}\rightarrow\mathbb{R}$ where $f\circ T$ is locally of bounded variation? $\endgroup$ Nov 26, 2023 at 13:46
  • $\begingroup$ @JosephVanName That'd make a good follow-up question. What springs to mind is trying to rearrange $f\circ T$ to be (almost) monotone, but I'm not sure if it's possible. $\endgroup$ Nov 26, 2023 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.