Odwrotności funkcji

[Konikov]

Ustalamy zbiór \(\displaystyle{ X}\) (być może nieskończony). Niech \(\displaystyle{ P}\) oznacza rodzinę wszystkich skończonych podzbiorów zbioru \(\displaystyle{ X}\) i niech \(\displaystyle{ F}\) oznacza zbiór wszystkich funkcji \(\displaystyle{ f : P \rightarrow Z}\).
Zdefiniujmy funkcje \(\displaystyle{ a, b : F \rightarrow F}\) wzorami:

\(\displaystyle{ (a(f))(A) = \sum_{B \subseteq A} f(B)}\)

\(\displaystyle{ (b(f))(A) = \sum_{B \subseteq A} (-1)^{|A\B|} f(B)}\)

Udowodnij, że funkcje a i b są swoimi odwrotnościami, tzn. \(\displaystyle{ \forall f \in F\ \ a(b(f)) = b(a(f)) = f}\).

[Qń]

Szkic - mamy:
\(\displaystyle{ a(b(f))(A)= \sum_{B \subseteq A} b(f)(B) =
\sum_{B \subseteq A} \sum_{C \subseteq B} (-1)^{|B \backslash C|} f(C)}\)
Teraz używamy pomysłu podobnego do jednego z dowodów zasady włączeń i wyłączeń, to znaczy zliczamy ile razy w tym napisie pojawi się \(\displaystyle{ f(D)}\) dla \(\displaystyle{ D \subseteq A}\). \(\displaystyle{ f(A)}\) pojawi się dokładnie raz (dlaczego?), natomiast dla \(\displaystyle{ D}\) będących podzbiorami właściwymi \(\displaystyle{ A}\) \(\displaystyle{ f(D)}\) pojawi się \(\displaystyle{ \sum_{D \subseteq B \subseteq A} (-1)^{|B \backslash C|}}\) razy (dlaczego?). Ponieważ ta suma jest równa \(\displaystyle{ (1-1)^n}\) (dlaczego?), więc takie \(\displaystyle{ f(D)}\) pojawią się zero razy. To zaś właśnie oznacza, że cały napis jest równy \(\displaystyle{ f(A)}\).

Analogicznie dla drugiego złożenia.

Q.

[Konikov]

Najlepsze jest to, że wydrukowałem sobie i za nic nie mogłem dojść, dlaczego napisałeś "|BC|". Okazało się, że TeX zjadł mi "B" we wzorze, a Ty napisałeś poprawną odpowiedź ;]