(a) We must prove the equality (7). If \(P=Q\), then the only subset \(I\) of \(Q\) satisfying \(P\subseteq I\) is \(Q\) itself, so the sum equals \((-1)^{|Q|} = (-1)^{|P|} \cdot [P = Q]\) (since \([Q = Q] = 1\)).

For the rest of this proof, we assume \(P\neq Q\). Thus, \(\left[ P=Q\right] =0\).

Now, \(P\) is a proper subset of \(Q\), so there exists some \(q\in Q\) such that \(q\notin P\). Fix such a \(q\).

Let

and let \(\operatorname {sign} I := (-1)^{|I|}\) for each \(I\in \mathcal{A}\). Then

We define a map \(f:\mathcal{A}\rightarrow \mathcal{A}\) by

This map \(f\) is well-defined and it is an involution (the symmetric difference with \(\{ q\} \) undoes itself). This involution has no fixed points (since \(f(I) = I \bigtriangleup \{ q\} \neq I\)). Furthermore, for each \(I \in \mathcal{A}\), the set \(f(I) = I \bigtriangleup \{ q\} \) differs from \(I\) in exactly one element (namely \(q\)), so \(|f(I)| = |I| \pm 1\). Therefore

i.e., \(\operatorname {sign}(f(I)) = -\operatorname {sign} I\). Since \(f\) is a sign-reversing fixed-point-free involution on \(\mathcal{A}\), the elements of \(\mathcal{A}\) pair up into pairs with opposite signs, giving

Comparing with (9), we obtain

(since \((-1)^{|P|} \cdot 0 = 0\)). This proves (7).

(b) If \(I\) is any subset of \(Q\), then \(\left\vert Q\setminus I\right\vert =\left\vert Q\right\vert -\left\vert I\right\vert \equiv \left\vert Q\right\vert +\left\vert I\right\vert \pmod{2}\), so

(since \(\left\vert Q\setminus I\right\vert \equiv \left\vert Q\right\vert +\left\vert I\right\vert \pmod{2}\)). Hence

It remains to check that

If \(P\neq Q\), then \([P = Q] = 0\) and both sides are \(0\). If \(P = Q\), then \((-1)^{|Q|}(-1)^{|P|} = (-1)^{2|Q|} = 1\), so both sides equal \(1\). Thus

This proves (8).

Both sides sum the same function \(f\) over all pairs \((J, P)\) of subsets of \(Q\) satisfying \(P \subseteq J \subseteq Q\); only the order of summation differs.

Fix a subset \(Q\) of \(S\). We shall prove that

We begin by rewriting the right hand side. By (13), we have \(b_I = \sum _{J \subseteq I} a_J\) for each \(I\), so

The two summation signs “\(\sum _{I\subseteq Q}\ \ \sum _{P\subseteq I}\)” on the right hand side of this equality result in a sum over all pairs \(\left( I,P\right) \) of subsets of \(Q\) satisfying \(P\subseteq I\subseteq Q\). The same result can be obtained by the two summation signs “\(\sum _{P\subseteq Q}\ \ \sum _{\substack{[I, \subseteq , Q, ;, \\ , P, \subseteq , I]}}\)” (by Lemma 4.69). Hence, (15) rewrites as follows:

We want to prove that this equals \(a_{Q}\). To this end, we show that the coefficient \(\sum _{\substack{[I, \subseteq , Q, ;, \\ , P, \subseteq , I]}}\left( -1\right) ^{\left\vert Q\setminus I\right\vert }\) in front of \(a_{P}\) is \(0\) whenever \(P\neq Q\), and is \(1\) whenever \(P=Q\). That is, every subset \(P\) of \(Q\) satisfies

This is precisely Lemma 4.68 (b).

Now, (16) becomes (using (17))

In other words, \(a_{Q}=\sum _{I\subseteq Q}\left( -1\right) ^{\left\vert Q\setminus I\right\vert }b_{I}\).

Since \(Q\) was an arbitrary subset of \(S\), we have shown that

This proves Theorem 4.70.

Immediate from Theorem 4.70, since the integer scalar multiplication \(n\cdot a\) in any additive abelian group coincides with \(n\) times \(a\) when the group carries a \(\mathbb {Z}\)-module structure.