We proceed by induction on the number
\(m\) of properties. If
\(m=1\text{,}\) then the formula reduces to
\(N(\emptyset)-N(\{1\})\text{.}\) This is correct since it says just that the number of elements which do not satisfy property
\(P_1\) is the total number of elements minus the number which do satisfy property
\(P_1\text{.}\)
Now assume validity when
\(m\le k\) for some
\(k\ge1\) and consider the case where
\(m=k+1\text{.}\) Let
\(X'=\{x\in X: x\) satisfies
\(P_{k+1}\}\) and
\(X''=X-X'\) (i.e.,
\(X''\) is the set of elements that do not satisfy
\(P_{k+1}\)). Also, let
\(\mathcal{Q}=\{P_1,P_2,\dots,P_k\}\text{.}\) Then for each subset
\(S\subseteq [k]\text{,}\) let
\(N'(S)\) count the number of elements of
\(X'\) satisfying property
\(P_i\) for all
\(i\in
S\text{.}\) Also, let
\(N''(S)\) count the number of elements of
\(X''\) satisfying property
\(P_i\) for each
\(i\in S\text{.}\) Note that
\(N(S)=N'(S)+N''(S)\) for every
\(S\subseteq
[k]\text{.}\)
Let
\(X'_0\) denote the set of elements in
\(X'\) which satisfy none of the properties in
\(\mathcal{Q}\) (in other words, those that satisfy only
\(P_{k+1}\) from
\(\mathcal{P}\)), and let
\(X''_0\) denote the set of elements of
\(X''\) which satisfy none of the properties in
\(\mathcal{Q}\text{,}\) and therefore none of the properties in
\(\mathcal{P}\text{.}\)
Now by the inductive hypothesis, we know
\begin{equation*}
|X'_0| = \sum_{S\subseteq [k]} (-1)^{|S|}N'(S)\qquad \text{and} \qquad
|X''_0| = \sum_{S\subseteq [k]} (-1)^{|S|}N''(S).
\end{equation*}
It follows that
\begin{align*}
|X''_0| \amp = \sum_{S\subseteq [k]} (-1)^{|S|}N''(S) = \sum_{S\subseteq [k]}
(-1)^{|S|}\left(N(S)-N'(S)\right)\\
\amp = \sum_{S\subseteq [k]} (-1)^{|S|}N(S)+
\sum_{S\subseteq [k]} (-1)^{|S|+1}N(S\cup\{k+1\})\\
\amp = \sum_{S\subseteq [k+1]} (-1)^{|S|}N(S).
\end{align*}