Äquivalenz mithilfe vollständiger Induktion zeigen

Question

Aufgabe:

Sei M eine endliche Menge und g,f: Pot(M) → C zwei Funktionen auf der Potenzmenge Pot(M) von M. Zeigen Sie, dass äquivalent sind:

(a) Für alle $$T \subset M$$ gilt $$g(T)=\sum_{S \subset T} f(S)$$

(b) Für alle $$T \subset M$$ gilt $$f(T)=\sum_{S \subset T}(-1)^{\#(T \backslash S)} g(S)$$

Problem/Ansatz:

Ich habe den Tipp bekommen diesen Beweis mit vollständiger Induktion zu lösen, aber wie führt man den Beweis?

Comments

#(T∖S): soll das die Mächtigkeit von (T∖S) sein?

---

Ja, # ist die Mächtigkeit.

Answer 1

Der Tipp ist gut.

Sei n∈ℕ\{0}. #M=n

IndVerankerung: n=1 (einelementiges M)

#M=1     #Pot(M)=2¹=2

(a) Sei T⊂M, also T=M oder T=∅

Dann soll gelten: g(T)= \( \sum\limits_{S⊂T}^{}{f(S)} \)

also: g(M)=f(M)+f(∅), g(∅)=f(∅) einsetzen!

        g(M)=f(M)+g(∅),     g(∅)=f(∅)         Diese Aussage soll gelten!

(b) Sei T⊂M, also T=M oder T=∅

Dann soll gelten: f(T)=\( \sum\limits_{S⊂T}^{}{g(S)} \)(-1)^#(T\S)

also:f(M)=(-1)¹g(∅) + (-1)⁰g(M),   f(∅)=(-1)⁰g(∅)

d.h.: f(M)=   -g(∅)    +    g(M),         f(∅)=g(∅)

d.h.: g(M)=f(M)+g(∅) ,                     f(∅)=g(∅)     Dieselbe Aussage soll gelten!

Ind.Schritt analog

Comments

Magst du mir den Induktionsschritt auch noch zeigen und den Beweis zu Ende führen?