Let $\mathcal{X}$ be the collection of all non-empty subsets (not necessarily finite) of the positive integer set $\mathbb{N}$. Determine all functions $f: \mathcal{X} \to \mathbb{R}^+$ satisfying the following properties: (i) For all $S$, $T \in \mathcal{X}$ with $S\subseteq T$, there holds $f(T) \le f(S)$. (ii) For all $S$, $T \in \mathcal{X}$, there hold \[f(S) + f(T) \le f(S + T),\quad f(S)f(T) = f(S\cdot T), \]where $S + T = \{s + t\mid s\in S, t\in T\}$ and $S \cdot T = \{s\cdot t\mid s\in S, t\in T\}$. Proposed by Li4, Untro368, and Ming Hsiao.
Problem
Source: 2022 Taiwan TST Round 3 Mock P4
Tags: function, algebra, functional equation, domain, ming
30.04.2022 10:24
Chef's kiss The only solution is $f(S)=(\min_{s\in S} s)^c$ where $c\ge 1$ is some constant real number. The first condition holds because since $T$ contains $S$, the smallest element of $T$ is at least as small as the smallest element of $S$. The second condition holds because $x^c$ is convex and multiplicative. We now show it is the only solution. Let $x,y$ be natural numbers unless otherwise specified. For simplicity, define $f(\{x\})=f(x)$ where $x$ is any positive integer. Note that from condition (ii), $f(x)+f(y)\le f(x+y)$ and $f(x)f(y)=f(xy)$. Obviously, $f(1)=1$, and $f$ is strictly increasing. Consider any $y>2$. Let $r,s$ be positive integers such that $\frac{r}{s}>\frac{\log y}{\log 2}$. Then, $2^r>y^s\implies f(2^r)>f(y^s)\implies f(2)^r>f(y)^s\implies \frac{r}{s}>\frac{\log f(y)}{\log f(2)}$. Similarly, if $\frac{r}{s}<\frac{\log y}{\log 2}$, then $\frac{r}{s}<\frac{\log f(y)}{\log f(2)}$. Since rationals are dense over $\mathbb{R}$, $\frac{\log y}{\log 2} = \frac{\log f(y)}{\log f(2)}\implies \frac{\log f(y)}{\log y}$ is constant. Hence, $\frac{\log f(y)}{\log y}=c\implies f(y)=y^c$ for some constant $c$. Since $f(x)+f(y)\le f(x+y)$, we get $c\ge 1$. Let $S$ be a set containing $1$. Then, $f(S)f(\mathbb{N})=f(\mathbb{N})$ implies $f(S)=1$. Let $S$ be a set with minimal element $a$. Then, from (i) we get $f(S)\le a^c$ and from (ii) we get $f(S)\ge f(S-(a-1))+f(a-1)=1+(a-1)^c$. Hence, $a^c\ge f(S)\ge 1+(a-1)^c$. Take a positive integer $k$, $f(S)^k=f(S^k)\ge 1+(a^k-1)^c$. Thus, $f(S)>\sqrt[k]{(a^k-1)^c}$. The limit of this is $a^c$, and so taking $k$ to infinity we get $f(S)=a^c$. This concludes the proof. wow.
30.04.2022 10:40
The only function is $f(S)=(\min S)^c$ where $c\ge1$ is constant. We prove the following claims. Claim 1: $f(\mathbb N)=1$. Proof: Setting $S=T=\mathbb N$ in the latter equation of condition (ii) gives $$f(\mathbb N)f(\mathbb N)=f(\mathbb N)\implies f(\mathbb N)=1$$ Claim 2: For any set $S$, if $m=\min S$, then we have $f(S)=f(m\mathbb N)$. Proof: Since $m$ is the minimum element of $S$, we have $S\cdot\mathbb N=m\mathbb N$. Setting $T=\mathbb N$ in the latter of condition (ii) gives $$f(S)f(\mathbb N)=f(m\mathbb N)\implies f(S)=f(m\mathbb N)$$since $f(\mathbb N)=1$ from Claim 1. Because of Claim 2, we can define a function $g:\mathbb N\to\mathbb R^+$ such that $f(S)=g(\min S)$ for any subset $S$. In terms of $g$, the new conditions are: (i) For all $s,t\in\mathbb N$ with $t\le s$, we have $g(t)\le g(s)$ (ii) For all $s,t\in\mathbb N$, we have $$g(s)+g(t)\le g(s+t),\quad g(s)g(t)=g(st)$$The proof that $g(n)=n^c$ for some constant $c$ follows similarly as @gghx's solution above. EDIT: Whoops. @below, yes you are right, my solution is incorrect. My apologies.
30.04.2022 10:42
P1kachu wrote: Proof: Since $m$ is the minimum element of $S$, we have $S\cdot\mathbb N=m\mathbb N$. I dont think so? for example $S=\{2,3\}$.