Vector spaces, Linear mappings and a relation to the inclusion-exclusion principle 
Exercise
Let $S$ be a set containing $n$ elements and $V$ be the $2^n$-dimensional vector space of all mappings $f : 2^S \rightarrow \mathbb{C}$. Let $\phi : V \rightarrow V$ be a linear map that for a map $f : 2^S \rightarrow \mathbb{C}$, the map $\phi(f) : 2^S \rightarrow \mathbb{C}$ is defined by $$(\phi(f))(T) = \sum_{T \subseteq Y \subseteq S}f(Y),\quad T \subseteq S .$$
i) Prove that $\phi$ is bijective and for a $g : 2^V \rightarrow \mathbb{C}$ the $\phi^{-1} : V \rightarrow V$ is defined  by $$\phi^{-1}(g)(T) = \sum_{T \subseteq Y \subseteq S}(-1)^{\# (Y\setminus T)}g(Y), T \subseteq S .$$
ii) Reason the inclusion–exclusion principle from i).


Hi! I don't come along with this at all as I don't even understand the first part. Could you please help me understanding the exercise and finding a suitable solution?
Thank you in advance!
 A: With these kinds of things, it is useful to work out a few small examples to see how this is going.
Suppose $n=1$, so $S$ has one element, $S=\{a\}$. Then $2^S$ has two elements, corresponding to the two subsets of $S$, $\emptyset$ and $S$. You then have the vector space of all mappings $f\colon\{\emptyset, \{a\}\}\to\mathbb{C}$.
Let $f\colon\{\emptyset, \{a\}\}\to\mathbb{C}$ be a map. This is equivalent to having two complex numbers: one for the image of $\emptyset$, one for the image of $\{a\}$, say $(f(\emptyset),f(\{a\})) = (x,y)$. What is $\phi(f)$?
$\phi(f)$ should be a function with domain $\{\emptyset,\{a\}\}$ and codomain the complex numbers. So one way to specify what $\phi(f)$ is would be to say what it's value is at each subset of $S$. This is what the formula is giving. So, for instance,
$$\begin{align*}
\phi(f)(\emptyset) &= \sum_{\emptyset\subseteq Y\subseteq S} f(Y) = f(\emptyset) + f(\{a\}) = x+y.\\
\phi(f)(\{a\}) &= \sum_{\{a\}\subseteq Y\subseteq S}f(Y) = f(\{a\}) = y.
\end{align*}$$
That is, the function $\phi$ takes the function corresponding to $(x,y)$ to the function corresponding to $(x+y,y)$. This is certainly an element of $V$.
Notice also that $\phi$ is linear: because $(f+\alpha g)(Y) = f(Y)+\alpha g(Y)$, so
$$\sum_{T\subseteq Y\subseteq S}(f+\alpha g)(Y) = \sum_{T\subseteq Y\subseteq S}f(Y) + \alpha\sum_{T\subseteq Y\subseteq S}g(Y),$$
which tells you that for every subset $T$ of $S$, $\phi(f+\alpha g)(T) = \phi(f)(T) + \alpha\phi(g)(T)$, hence 
$$\phi(f+\alpha g) = \phi(f) + \alpha\phi(g)$$
proving linearity. 
If we use the given formula for $\phi^{-1}$, what do we get when we plug in $g$, with values $(r,s)$ (that is, $g(\emptyset) = r$, $g({a}) = s$)? We have:
$$\begin{align*}
\phi^{-1}(g)(\emptyset) &= \sum_{\emptyset\subseteq Y\subseteq S}(-1)^{\#(Y-\emptyset)}g(Y)\\
&= (-1)^{0}g(\emptyset) + (-1)^1g(\{a\}) = r-s,\\
\phi^{-1}(g)(\{a\}) &= \sum_{\{a\}\subseteq Y\subseteq S}(-1)^{\#(Y-\{a\})}g(Y)\\
&= (-1)^0g(\{a\}) = s.
\end{align*}$$
So $\phi(g)$ is the function $(r-s,s)$.
Note that if we start with $f$ that corresponds to $(x,y)$ and apply $\phi$, we get the function that corresponds to $(x+y,y)$; if we then apply $\phi^{-1}$, we get the function that corresponds tO $(x,y)$, i.e. $f$; likewise, if we start with the function $(r,s)$ and apply $\phi^{-1}$, we get $(r-s,s)$; then apply $\phi$ and we get $(r,s)$. So all is well.
What if $S$ has two elements, $S=\{a,b\}$. Then $2^S$ has four elements. Say $f$ is a function from $2^S = \{\emptyset,\{a\},\{b\},\{a,b\}\}$ to $\mathbb{C}$.  What is $\phi(f)$?
To quote Leibnitz, let us calculate:
$$\begin{align*}
\phi(f)(\emptyset) &= \sum_{\emptyset\subseteq Y\subseteq S}f(Y)\\
&= f(\emptyset) + f(\{a\}) + f(\{b\}) + f(\{a,b\}).\\
\phi(f)(\{a\}) &= \sum_{\{a\}\subseteq Y\subseteq S}f(Y)\\
&= f(\{a\}) + f(\{a,b\}).\\
\phi(f)(\{b\}) &= \sum_{\{b\}\subseteq Y\subseteq S}f(Y)\\
&= f(\{b\}) + f(\{a,b\}).\\
\phi(f)(\{a,b\}) &= \sum_{\{a,b\}\subseteq Y\subseteq S}f(Y)\\
&= f(\{a,b\}).
\end{align*}$$
What about $\phi^{-1}(f)$?
$$\begin{align*}
\phi^{-1}(f)(\emptyset) &= \sum_{\emptyset\subseteq Y\subseteq S}(-1)^{\#(Y-\emptyset)}f(Y)\\
&= (-1)^0f(\emptyset) + (-1)^1f(\{a\}) + (-1)^1f(\{b\}) + (-1)^2f(\{a,b\})\\
&= f(\emptyset) - (f(\{a\}) + f(\{b\})) + f(\{a,b\}).\\
\phi^{-1}(f)(\{a\}) &= \sum_{\{a\}\subseteq Y\subseteq S}(-1)^{\#(Y-\{a\})}f(Y)\\
&= (-1)^0f(\{a\}) + (-1)^1f(\{a,b\})\\
&= f(\{a\}) - f(\{a,b\}).\\
\phi^{-1}(f)(\{a,b\}) &= \sum_{\{b\}\subseteq Y\subseteq S}(-1)^{\#(Y-\{b\})}f(Y)\\
&= (-1)^0f(\{b\}) + (-1)^1f(\{a,b\})\\
&= f(\{b\}) - f(\{a,b\}).\\
\phi^{-1}(f)(\{a,b\}) &= \sum_{\{a,b\}\subseteq Y\subseteq S}(-1)^{\#(Y-\{a,b\})}f(Y)\\
&= f(\{a,b\}).
\end{align*}$$
So, for example, if $f(\emptyset) = 2$, $f(\{a\}) = i$, $f(\{b\}) = \frac{1}{3}+\sqrt{2}i$, and $f(\{a,b\}) = e+\pi i$ (values chosen entirely arbitrarily), then $\phi(f)$ is the function with values:
$$\begin{align*}
\phi(f)(\emptyset) &= 2 + i + \frac{1}{3}+\sqrt{2}i + e+\pi i = \left(2+\frac{1}{3}+e\right) + \left(\sqrt{2}+\pi\right)i.\\
\phi(f)(\{a\}) &= i + e+\pi i = e + (\pi+1)i.\\
\phi(f)(\{b\}) &= \frac{1}{3}+\sqrt{2}i + e+\pi i = \left(\frac{1}{3}+e\right) + \left(\sqrt{2}+\pi\right)i.\\
\phi(f)(\{a,b\}) &= e + \pi i.\\
\phi^{-1}(f)(\emptyset)&= 2 -\left( i + \frac{1}{3}+\sqrt{2}i\right) + e+\pi i\\
&= \left(2 - \frac{1}{3} + e\right) + \left(-1 - \sqrt{2}+\pi\right)i.\\
\phi^{-1}(f)(\{a\}) &= i - (e+\pi i) = -e + (1-\pi)i.\\
\phi^{-1}(f)(\{b\}) &= \frac{1}{3} + \sqrt{2}i - (e+\pi i)\\
&= \left(\frac{1}{3}-e\right) + \left(\sqrt{2}-\pi\right)i.\\
\phi^{-1}f(\{a,b\}) &= e+\pi i.
\end{align*}$$
If we represent a function from $\{\emptyset,\{a\},\{b\},\{a,b\}\}$ to $\mathbb{C}$ with a $4$-tuple of complex numbers (corresponding to the values at $\emptyset$, at $\{a\}$, at $\{b\}$, and at $\{a,b\}$, respectively), then $\phi$ sends the function corresponding to $(x,y,z,w)$ to the function $(x+y+z+w, y+w, z+w, w)$, while $\phi^{-1}$ sends the function corresponding to $(r,s,t,u)$ to $(r-s-t+u, s-u, t-u, u)$. You can now verify easily that $\phi$ and $\phi^{-1}$ are inverses of each other.
As far as finding a suitable solution, I would not recommend trying to think of the functions as tuples. Instead, I would suggest trying induction on $n$.
You might also notice how similar to "inclusion-exclusion" the formula for $\phi^{-1}$ looks; that suggests trying to find a suitable $f$ so that, on the one hand, the value of $f$ counts something, while the value of $\phi^{-1}(\phi(f))$ gives you the inclusion-exclusion way of counting it. 
