2

The question is pretty vague because it arises from an application scenario and is open-ended.

$\mathcal{S}$ is a countable infinite set, $f$ is a function defined on the power set of $\mathcal{S}$, mapping any subset of $\mathcal{S}$ to a real number in $[0, 1]$. $f$ is known to satisfy the following properties:

  • For any $S_0 \subseteq S_1$, $f(S_0) \leq f(S_1)$.
  • For any $S$ with $|S| \leq 1$ ($|S|$ being the carnality of $S$) we have $f(S) \in \{0, 1\}$.
  • There exists infinitely many $S$ (not depending on $f$) such that $|S| = 2$ and $f(S) = 1$.
  • There exists a set $S_T$ (not depending on $f$) such that $|S_T| = \infty$ and $f(S_T) = 0$.

What's the best way to "characterize" $f$? i.e., what extra information (as minimal as possible) is needed to determine or construct $f$? For example, it would be great if we can say $f$ is uniquely determined by (or can be constructed from) $f(S)$ for any $S$ with $|S| = 3$ (this is not necessarily true, just an example of a helpful result).

David M
  • 121
  • 1
    In general, it takes an enormous amount of additional information to uniquely specify $f$. In particular, $f$ is not uniquely determined by its values on ${S \in \mathcal{P}(\mathcal{S}) : \lvert S \rvert \leq n}$ for any natural number $n$. – diracdeltafunk Aug 29 '22 at 22:04
  • @diracdeltafunk it's ok if $f$ is not uniquely determined. Any approach to quantify $f$, say, given this and that extra information, we can construct an eligible $f$ explicitly (without uniqueness) would also be helpful. – David M Aug 29 '22 at 23:10
  • It would be wonderful if this really were a question of carnality… – Lubin Aug 30 '22 at 18:29

1 Answers1

1

In the comments, you clarified that it would be helpful to have a way to extend a partially-defined function to all of $P(\mathcal{S})$. There is in fact a "universal" way to do this!

Let $\mathcal{P}$ be any subset of $P(\mathcal{S})$ which contains all the subsets of cardinality at most $2$. Then let $f_0 : \mathcal{P} \to [0,1]$ be a function satisfying the following conditions:

(i) For any $S_0 \subseteq S_1 \in \mathcal{P}$, $f_0(S_0) \leq f_0(S_1)$
(ii) For any $S \in \mathcal{P}$ with $\lvert S \rvert \leq 1$, we have $f_0(S) \in \{0,1\}$
(iii) There exist infinitely many $S \in \mathcal{P}$ with $\lvert S \rvert = 2$ and $f_0(S) = 1$
(iv) There exist infinitely many $S \in \mathcal{P}$ such that $S$ has maximal cardinality among elements of $\mathcal{P}$ and $f_0(S) = 0$, OR $\mathcal{P}$ has no element of maximal cardinality but has an ascending chain $S_0 \subset S_1 \subset \dots$ such that $f_0(S_i) = 0$ for all $i$

Then the function $f : P(\mathcal{S}) \to [0,1]$ defined by $$f(S) = \sup_{\substack{S' \in \mathcal{P} \\ S' \subseteq S}} f_0(S')$$ extends $f_0$ to all of $P(\mathcal{S})$ and satisfies the desired properties.

diracdeltafunk
  • 14,911
  • 1
    Thanks very much! That helps (as I said this question arises from a real application scenario so I need to investigate whether I can directly use this method but this is illuminating).

    So let's say $\mathcal{P}$ is just the set of subsets with cardinality 2 (i.e. the smallest $\mathcal{P}$ satisfying your description), then the extension of $f_0$ is obviously the lower bound of all eligible $f$. Do you think there is a possibly easy way to also get an upper bound?

     – David M Aug 30 '22 at 00:03
  • There is no single upper bound. Indeed, suppose $f : P(\mathcal{S}) \to [0,1]$ is any function satisfying the desired properties, and let $S_0 \subseteq \mathcal{S}$ be an infinite subset such that $f(S_0) = 0$. Pick some $x \in S_0$. Then define $g : P(\mathcal{S}) \to [0,1]$ by $g(S) = 1$ whenever ($x \in S$ and $S$ is infinite) and $g(S) = f(S)$ whenever ($x \notin S$ or $S$ is finite). $g$ satisfies all the conditions, agrees with $f$ on all finite subsets of $\mathcal{S}$, and $g$ is larger than $f$ in the sense that $g(S_0) = 1 > 0 = f(S_0)$. Therefore, $f$ is not an upper bound. – diracdeltafunk Aug 30 '22 at 03:26
  • My bad, I didn't clearly state the desired properties of $f$. In the 3rd and 4th properties, the existence of those sets is not depending on $f$ (I just edited the problem to make this clearer). So the $g$ here is not an eligible function. – David M Aug 30 '22 at 18:22
  • Nevermind. I realized the upper bound is trivial and uninteresting: $f(S) = 0$ for $S \subseteq S_T$ and $f(S) = 1$ otherwise. This is not very helpful... – David M Aug 30 '22 at 20:43