Writing a function on $\mathbb{R}$ as a sum of two injections

Question

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.

Answer 1

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.)

Answer 2

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.