Verwenden Sie den Induktionsbeweis der Formel 2^|M|= 2|M|

Question

Aufgabe:

Verwenden Sie den Induktionsbeweis der Formel

2^|M|= 2|M|
fur endliche Mengen M, um alle Teilmengen von M = {1, 2, 3, 4} aufzuzahlen.

Könnte mir mal jemand helfen?

Comments

Ich befürchte sehr, dass du die Aufgabenstellung nicht korrekt wiedergegeben hast.

Im vorliegenden Beispiel wäre doch offensichtlich

|M| = 4

2^|M| = 2⁴ = 16

2 |M| = 2 · 4 = 8

---

Ich befürchte sehr, dass du die Aufgabenstellung nicht korrekt wiedergegeben hast.

Ich befürchte das überhaupt nicht. Der Standard Induktionsbeweis enthält nämlich ein konstruktives Verfahren zur Bildung der Teilmengen.

Fange an mit 0 Elementen: ∅

Jetzt wähle ein Element aus M aus: zB 1

Übernimm die bisherigen: ∅

Und die bisherigen vereinigt mit dem neuen Element: ∅∪{1}={1}

Bis jetzt haben wir also ∅ und {1}

Wähle das nächste Element: zB 2

Übernimm die bisherigen: ∅, {1}

Und die bisherigen, vereinigt mit dem neuen Element: {2}, {1,2}

Insgesamt bis jetzt ∅, {1}, {2}, {1,2}

Usw usw