PROVED (LEAN)
This has been solved in the affirmative and the proof verified in Lean.
Let $A=\{a_1<\cdots<a_t\}\subseteq \{1,\ldots,N\}$ be such that $\phi(a_1)<\cdots<\phi(a_t)$. The primes are such an example. Are they the largest possible? Can one show that $\lvert A\rvert<(1+o(1))\pi(N)$ or even $\lvert A\rvert=o(N)$?
Erdős remarks that the last conjecture is probably easy, and that similar questions can be asked about $\sigma(n)$.
Solved by Tao
[Ta24d], who proved that\[ \lvert A\rvert \leq \left(1+O\left(\frac{(\log\log x)^5}{\log x}\right)\right)\pi(x).\]In
[Er95c] Erdős further asks about the situation when $\phi(a_1)\leq \cdots \leq \phi(a_t)$.
See also
[415].
