IMC 2003 · Day 2 · P11

a) Let $\varphi : \mathbb{Q} \to \mathbb{N}$ be a bijection. Define $g(x) = \max \{ |f(s, t)| : s, t \in \mathbb{Q},\ \varphi(s) \le \varphi(x),\ \varphi(t) \le \varphi(x) \}$. We have $f(x, y) \le \max \{ g(x), g(y) \} \le g(x) + g(y)$.

b) We shall show that the function defined by $f(x, y) = \dfrac{1}{|x - y|}$ for $x \ne y$ and $f(x, x) = 0$ satisfies the problem. If, by contradiction there exists a function $g$ as above, it results, that $g(y) \ge \dfrac{1}{|x - y|} - f(x)$ for $x, y \in \mathbb{R}$, $x \ne y$; one obtains that for each $x \in \mathbb{R}$, $\lim\limits_{y \to x} g(y) = \infty$. We show, that there exists no function $g$ having an infinite limit at each point of a bounded and closed interval $[a, b]$.

For each $k \in \mathbb{N}_+$ denote $A_k = \{ x \in [a, b] : |g(x)| \le k \}$.

We have obviously $[a, b] = \bigcup_{k=1}^{\infty} A_k$. The set $[a, b]$ is uncountable, so at least one of the sets $A_k$ is infinite (in fact uncountable). This set $A_k$ being infinite, there exists a sequence in $A_k$ having distinct terms. This sequence will contain a convergent subsequence $(x_n)_{n \in \mathbb{N}}$ convergent to a point $x \in [a, b]$. But $\lim\limits_{y \to x} g(y) = \infty$ implies that $g(x_n) \to \infty$, a contradiction because $|g(x_n)| \le k$, $\forall n \in \mathbb{N}$.

Second solution for part (b). Let $S$ be the set of all sequences of real numbers. The cardinality of $S$ is $|S| = |\mathbb{R}|^{\aleph_0} = 2^{\aleph_0^2} = 2^{\aleph_0} = |\mathbb{R}|$. Thus, there exists a bijection $h : \mathbb{R} \to S$.

Now define the function $f$ in the following way. For any real $x$ and positive integer $n$, let $f(x, n)$ be the $n$th element of sequence $h(x)$. If $y$ is not a positive integer then let $f(x, y) = 0$. We prove that this function has the required property.

Let $g$ be an arbitrary $\mathbb{R} \to \mathbb{R}$ function. We show that there exist real numbers $x, y$ such that $f(x, y) > g(x) + g(y)$. Consider the sequence $(n + g(n))_{n=1}^{\infty}$. This sequence is an element of $S$, thus $(n + g(n))_{n=1}^{\infty} = h(x)$ for a certain real $x$. Then for an arbitrary positive integer $n$, $f(x, n)$ is the $n$th element, $f(x, n) = n + g(n)$. Choosing $n$ such that $n > g(x)$, we obtain $f(x, n) = n + g(n) > g(x) + g(n)$.