Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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!

share|cite|improve this question
I'm sorry, but are you copying this correctly? If $T$ is a subset of $S$, then how do you "add" subsets? And the value of $\phi(f)$ at $T$ should be a complex number, so it's not at all clear to me what it is you are writing in the first part. Please double check your formula! – Arturo Magidin May 28 '11 at 21:42
Should it be$$(\phi(f))(T) = \sum_{T\subseteq Y\subseteq S}f(Y),\qquad T\subseteq S?$$ – Arturo Magidin May 28 '11 at 21:44
up vote 3 down vote accepted

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.

share|cite|improve this answer
Thank you very much for taking so much time explaining this to me! I do now understand what to do and try to solve it on my own :) – muffel May 30 '11 at 7:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.