Skip to main content
2 of 4
deleted 18 characters in body
bof
  • 13.4k
  • 2
  • 43
  • 66

Yes, such a function $f:X\times X\to\mathbb N$ exists if $X$ is uncountable. It will suffice to prove it for $X=\omega_1$. The following proof is based on the same idea as a comment by Ashutosh but uses elementary set theory instead of the result of Todorcevic.

For each ordinal $\alpha\in\omega_1$ choose an injective map $\psi_\alpha:\alpha\to\mathbb N$. Define a function $f:\omega_1\times\omega_1\to\mathbb N$ so that $f(\alpha,\beta)=\psi_\alpha(\beta)$ when $\beta\lt\alpha$. Now consider any function $g:\omega_1\to\mathbb N$. Then $g$ is bounded on some uncountable set $Y\subseteq\omega_1$; say $g(\xi)\le n\in\mathbb N$ for all $\xi\in Y$. Let $Z\subset Y$ be a set of order type $\omega+1$ and let $\alpha=\max Y$. Since $\{f(\alpha,\beta):\beta\in Y\cap\alpha\}=\{\psi_\alpha(\beta):\beta\in Y\cap\alpha\}$ is an infinite subset of $\mathbb N$, we can choose $\beta\in Y\cap\alpha$ with $f(\alpha,\beta)\gt2n\ge g(\alpha)+g(\beta)$.

bof
  • 13.4k
  • 2
  • 43
  • 66