How do set functions work in this example?

Question

I'm sure this is a very simple question, and that I'm missing something quite fundamental, but here goes:

Defintion: A function $f: 2^N \to \mathbb{R}$ is called submodular if $$f(S) + f(T) \ge f(S \cup T)+f(S \cap T) \quad \forall S,T \subseteq N$$

If $f(x)= c^T x$, for some real vector $c$, what does it mean that we are plugging sets into $f$? How can you possibly plug a set into this function and yield a scalar?

Any help would be appreciated.

Answer 1

A submodular function is a function on a set. We have to assume the input to be a set.

A set function could be for example, the product of its elements or the sum of its elements, or its cardinality.

$f(x)=c^Tx$ is not a function on a set. You are assuming that the inputs are real vectors and not a set.

Edit:

Let $A=\{a_1, \ldots, a_n\}$, then each subset of $A$ can be represented as a binary vector, where the position $i$ of the binary vector is $1$ if $a_i$ is chosen to be in the subset and $0$ otherwise.