0

Given a set $S$, consider a function mapping its subsets to the reals, $f:\mathcal P(S)\rightarrow \mathbb R$. Assume that for every $T\subseteq S$, there exists an element $i\in T$ such that $f(T\backslash \{i\}) \geq f(T)$, that is, we can remove $i$ and obtain an equal or higher value of $f$.

Question: Is there a name for this property? Has it been studied?

Notice the following implications, for a set $T$ of cardinality $n$:

  • There exists an ordering of the elements of $T$, $i_1, \dots, i_n$, such that $f\left(\bigcup_{j=1}^{k}\{i_j\}\right) \geq f\left(\bigcup_{j=1}^{k+1}\{i_j\}\right)$ for all $1\leq k<n$. (The set can be built incrementally in a non-increasing order).
  • For every $1\leq k<n$ there exists a subset $U\subset T$ of cardinality $k$ such that $f(U)\geq f(T)$.
cangrejo
  • 1,279
  • Wouldn't this just be an isotone function, or am I missing something? – Dave L. Renfro Aug 20 '19 at 13:45
  • I guess you are saying it because of the first implication. Note that this does not define an ordering of $\mathcal P(S)$ (unless I am missing something too), so it does not necessarily mean the function is isotonic with respect to some order. – cangrejo Aug 20 '19 at 14:26
  • Yep, I guess I'm missing something, such as reading (or at least thinking) "for all elements $i \in T$" instead of what you actually wrote, which is "there exist an element $i \in T.$ This is not the first time this has happened to me, which is why I'm usually careful to include "unless I'm missing something" (except when I'm essentially certain). – Dave L. Renfro Aug 20 '19 at 16:18
  • This happens often to everyone. It happens to me, at least... – cangrejo Aug 20 '19 at 21:21

0 Answers0