7
$\begingroup$

The following question is inspired by Function with vector space , which has been closed for unknown reason and which may have a wellknown answer. Is the following true?

Let $X$ be an uncountable set. Then there is a function $f \colon X \times X \to \mathbb{N}$ such that for any function $g \colon X \to \mathbb{N}$ there is $(x,y) \in X^2$ with $f(x,y) > g(x) + g(y)$.

It is easy to show that this is false if $X$ is countable.

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ Suppose $c:[\omega_1]^2 \to \omega$ satisfies: For every uncountable $Y \subseteq \omega_1$, the range of $c \upharpoonright [Y]^2$ is unbounded in $\omega$. The existence of such $c$ and much more is well known (See S. Todorcevic, Partitioning pairs of countable ordinals, Acta Math., 159(3–4):261–294, 1987). So you can define $f(x, y) = c(\{x, y\})$ if $x \neq y$, and $0$ otherwise. It follows that there is such an $f:X^2 \to \omega$ iff $X$ is uncountable. $\endgroup$
    – Ashutosh
    Commented Jun 8, 2020 at 7:30
  • 3
    $\begingroup$ @Ashutosh Todorcevic's result is much stronger, but you don't need Todorcevic to get $f$ with the property you need, it's just an exercise in elementary set theory. For each $\alpha\in\omega_1$ choose an injection $\psi_\alpha:\alpha\to\mathbb N$. For $\beta\lt\alpha\in\omega_1$ define $f(\alpha,\beta)=f(\beta,\alpha)=\psi_\alpha(\beta)$. So $f:\omega_1\times\omega_1\to\mathbb N$, and $f$ is unbounded on $X\times X$ if $X\subseteq\omega_1$ is uncountable, indeed, if $X$ has order type $\ge\omega+1$. $\endgroup$
    – bof
    Commented Jun 8, 2020 at 16:10
  • $\begingroup$ Thank you bof and @Ashutosh. I'm sorry, but I prefer the answer of bof. It is simple and effective. Can you make it to an answer? $\endgroup$
    – Dieter Kadelka
    Commented Jun 8, 2020 at 18:32

1 Answer 1

Reset to default
8
$\begingroup$

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 Z$. Since $\{f(\alpha,\beta):\beta\in Z\cap\alpha\}=\{\psi_\alpha(\beta):\beta\in Z\cap\alpha\}$ is an infinite subset of $\mathbb N$, we can choose $\beta\in Z\cap\alpha$ with $f(\alpha,\beta)\gt2n\ge g(\alpha)+g(\beta)$.


More generally, if $|X|\gt\aleph_\alpha$, then there is a function $f:X\times X\to\omega_\alpha$ such that, for any function $g:X\to\omega_\alpha$, there are $x,y\in X$ with $f(x,y)\gt g(x)+g(y)$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .