What does $f: 2^{\mathcal{S}}\rightarrow\,\mathbb{R}$ mean?

Question

• A function $f: \mathcal{S}^n\rightarrow\,\mathbb{R}$

This is I understand. $x\in\mathrm{dom}\,f$ means that $x$ is a vector of size $n$ where its elements are taken from the set $\mathcal{S}$. e.g., $\mathcal{S}=\{0, 1\}$, $n=3$, so $x$ could be equal $(1, 1, 0)^{\mathrm{T}}$. Am I right?

• A function $f: 2^{\mathcal{S}}\rightarrow\,\mathbb{R}$

This is I could not understand. What does it mean $x\in\mathrm{dom}\,f$?

Answer 1

$x$ is a subset of $\mathcal{S}$. The notation $2^X$ is often used to denote the collection of all subsets of $X$. Other mathematicians prefer $\mathcal{P}(X)$.

Answer 2

Some further generality may be informative: sometimes $A^B$ is used to indicate the set of all functions $B\to A$.

When one of these two sets is replaced by a natural number, it indicates an arbitrary indexing set with that cardinality. So one can think of $\mathcal{S}^n$ as the set of functions $\{1,\dotsc,n\}\to\mathcal{S}$. But each such function $f$ can be identified with the vector $(f(1),\dotsc,f(n))$ of elements of $\mathcal{S}$.

Similarly, one can think of $2^\mathcal{S}$ as the set of functions $\mathcal{S}\to\{0,1\}$. Each such function $f$ can be identified with the subset $\{s\in\mathcal{S}:f(s)=1\}$ of $\mathcal{S}$.

The identifications in the examples are usually taken to be the definitions of $\mathcal{S}^n$ and $2^\mathcal{S}$, but the notation is borrowed from the more general setting of sets of functions.

Answer 3

In general $A^{S}$ denotes the set of functions with domain $S$ and codomain $A$. In the special case $2^{S}$ where $2$ stands for $\left\{ 0,1\right\} $ you are dealing with characteristic functions so that there is a one-to-one correspondence between the elements of $2^{S}$ and the subsets of $S$.