Is the following statement true?

For every $f: \mathbb R^2 \to \mathbb R$, there exists $g:\mathbb R \to \mathbb R$, such that $f(x,y) \le g(x) + g(y)$ for all $x,y \in \mathbb R$.

I do not think so. However, I couldn't find a counterexample.

In case that doesn't hold, what conditions could we impose on $f$ so that the statement becomes true?

  • 2
    $\begingroup$ how about $f(x,y)=\frac 1{x-y}$? (extend the definition via, say, $f(x,x)=0$. $\endgroup$ – lulu Oct 1 '15 at 20:42
  • $\begingroup$ @lulu: that is probably the way, to use something locally unbounded. $\endgroup$ – Jack D'Aurizio Oct 1 '15 at 20:44
  • $\begingroup$ Note it's possible to convert this to $f(x,y) \leq g(\max(x,y))$ - the problem can be stated in any linear order, not just reals. $\endgroup$ – sdcvvc Oct 1 '15 at 20:46
  • $\begingroup$ Actually I should say $f(x,y) \leq \max(g(x),g(y))$. $\endgroup$ – sdcvvc Oct 1 '15 at 20:53

The example $$ f\left(x,y\right)=\begin{cases} \frac{1}{\left|x-y\right|}, & x\neq y,\\ 0, & x=y \end{cases} $$ indeed works. Assume towards a contradiction that we have $$ f\left(x,y\right)\leq g\left(x\right)+g\left(y\right) $$ for some function $g$.

Let $$ M_{n}:=\left\{ x\in\mathbb{R}\,\mid\, g\left(x\right)\leq n\right\} . $$ Note that $\mathbb{R}=\bigcup_{n\in\mathbb{N}}M_{n}$, so that at least one of the sets $M_{n}$ is uncountable. As such, it has a point of accumulation in itself (otherwise, it consists of isolated points only and thus is countable, see Accumulation points of uncountable sets).

Hence, there is a sequence $\left(x_{m}\right)_{m}$ in $M_{n}$ with $x_{m}\to x$ for some $x\in M_{n}$ and with $x_{m}\neq x$ for all $m$. Thus, $$ \infty\xleftarrow[m\to\infty]{}\frac{1}{\left|x_{m}-x\right|}=f\left(x_{m},x\right)\leq g\left(x_{m}\right)+g\left(x\right)\leq2n, $$ a contradiction.

EDIT: Note that the property of existence of such a function $g$ as you want to have only depends on the cardinality of the set on which $g$ is defined ($\Bbb{R}$ in your case). If you do not see this, note that $f,g$ are arbitrary functions, so that you can transfer $g$ using a bijection (think about it!).

Thus, for any set of the cardinality of the continuum, there is no such function $g$ in general.

For countable sets, however, the claim is true. To see this, let $f : X\times X \to \Bbb{R}$ with $X$ countable (infinite, otherwise, the claim is trivial). Lets say $X = \Bbb{N}$. Now define (similar to the answer of @jgon) $$ g(n) := \max \{ 0, \max_{i,j \leq n} f(i,j)\}. $$ We then have for $n := \max \{x,y\}$ $$ f(x,y) \leq \max_{i,j \leq n} f(i,j) = g(n) \leq g(x) + g(y), $$ where the last step used that $n = x$ or $n=y$ and $g \geq 0$.

Finally, for continuous functions, the claim also holds as noted in the answer by @jgon.


For every continuous $f$, there is such a $g$. Define $\displaystyle g(x)=\max_{[-x,x]\times[-x,x]}|f|$, where if $x$ is negative, $[-x,x]$ is really $[x,-x]$. Since the domain is compact, the maximum exists, so that $g$ is a well defined function. Further it is clear that $(x,y)$ will either be in $[-x,x]^2$ or $[-y,y]^2$ since either $|x| < |y|$, in which case it will be in the second set, or $|y| \le |x|$, in which case it is in the first set. In either case, $f(x,y) \le g(x)+g(y)$ since it is less than or equal to one of them alone, and it is certainly less than their sum.

For general $f$, I'm not sure.



Go for PhoemueX' answer, he solved it. :)

Just a suggestion

$$f(x,y) :=\begin{cases} \frac{1}{|x-y|} & x\neq y\\ 0 & x=y\end{cases}$$

I'll write $f(x-y)$ since it only depends on the difference. $$f(x-y) \leq g(x) + g(y) \quad \forall x,y$$ is equivalent to $$f(x) \leq g(x+y) + g(y) \quad \forall x,y$$ which is equivalent to $$f(x) \leq \inf_y\{ g(x+y) + g(y)\} \quad \forall x$$ So maybe $x_n := \frac{1}{n}$ will help:

$$n=f(x_n) =\inf_y\left\{ g\left(\frac{1}{n}+y\right) + g(y)\right\} $$

lulu pointed it out two minutes earlier, I wasted time trying to get \beginbraces to align.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy