Ist jemand von euch gut in Mengenlehre?
Die Aufgabe heißt "Wieviele Teilmengen hat eine Menge mit 2, 3, 4, 5, 6, n Elementen"
Ich weis nicht ob die aufgabe leicht ist oder ob ich einfach zu blöd dafür bin
Wäre euch wirklich dankbar falls mir einer erklärt wie man bei dieser aufgabe auf ein ergebnis kommt :)
2 Antworten
Hi, da gibt es eine kanonische Herangehensweise. Die Idee dahinter ist ganz charmant.
Du kannst jede Teilmenge mit einer binären Folge identifizieren. Binär bedeutet, dass nur 0en und 1en in der Folge vorkommen. Um die Identifikation vorzunehmen, musst du nur einsehen, dass jedes Element der Menge {1, ..., n} entweder in der betrachteten Teilmenge vorkommt (dies entspricht der 1) oder eben nicht (dies entspricht der 0). Für jede mögliche Teilmenge führen wir dann Buch über das Vorhandensein oder Nicht-Vorhandensein des entsprechenden Elements der Grundmenge. Als Beispiel kannst du etwa n=2, d.h. die Menge {1,2}, nehmen und die möglichen Teilmengen als binäre Folgen der Länge 2 betrachten:
- Die Menge {} (leere Menge) entspricht 00 - in Worten: 1 ist nicht drin (kodiert als 0) und 2 ist nicht drin (kodiert als 0)
- Die Menge {1} entspricht 10 - in Worten: 1 ist drin (kodiert als 1) und 2 ist nicht drin (kodiert als 0)
- Die Menge {2} entspricht 01 - in Worten: 1 ist nicht drin (kodiert als 0) und 2 ist drin (kodiert als 1)
- Die Menge {1,2} entspricht 11 - in Worten: 1 ist drin (kodiert als 1) und 2 ist drin (kodiert als 1)
Für n=2 erhälst du also vier mögliche binäre Folgen, jede entspricht einer Teilmenge, d.h. du hast vier Teilmengen.
Betrachten wir ein allgemeines n, dann entsprechen deine Teilmengen nun binären Folgen der Länge n. Um zu beantworten, wie viele Teilmengen es gibt, musst du nur beantworten, wie viele binäre Folgen der Länge n es gibt. Das ist etwas Kombinatorik:
Für das erste Glied der Folge haben wir zwei Möglichkeiten 0/1. Jede Möglichkeit spannt einen Pfad auf, wobei jeder Pfad für die weiteren Stellen der Folge steht. Beide Pfade verzweigen sich jetzt wieder, da wir auch für die zweite Stelle wieder zwei Möglichkeiten haben - das ergibt schon mal auf der zweiten "Ebene" dieses durch die Pfade aufgespannten Baumes insgesamt 2 * 2 = 4 Endpunkte.
Diese Konstruktion führst du nun weiter, bis du jede Stelle der Folge erwischt hast. Mit jeder weiteren Eben verdoppelt sich die Zahl der Pfade. Du musst also lediglich Zweierpotenzen betrachten und die Zahl der Pfade, wenn du alle n Stellen abgearbeitet hast, muss gerade 2^n sein.
Damit hast du deine Antwort: die Zahl der möglichen binären Folgen ist 2^n. Da wir jede solche Folge mit einer Teilmenge identifizieren und umgekehrt, hat die Menge {1, ..., n} folglich auch 2^n Teilmengen.
Du kannst dieses Ergebnis selbst nochmal überprüfen für einige Spezialfälle. Für n=2 erhälst du natürlich gerade die Zahl 4, d.h. das Ergebnis, das wir im einführenden Beispiel gefunden haben.
Der mathematische Beweis ist relativ einfach. Man muss folgendes wissen...
Sei M eine Menge, dann gilt...
(Der Betrag der Potenzmenge, also die Menge aller Teilmengen, ist 2^n mit n = die Anzahl der Elemente in M)
Der Beweis folgt aus vollständiger Induktion.
Induktionsanfang: Sei M = { } (leere Menge). Dann ist...
Sprich: Die Potenzmenge enthält als einziges Element die leere Menge, also ist die Anzahl der Elemente = 1.
Induktionsvoraussetzung: P({x1, x2, ..., xn}) = 2^n
Induktionsbehauptung: P({x1, x2, ..., xn, xn+1}) = 2^(n+1)
Induktionsschritt: Wir wählen eine beliebige Teilmenge U aus M = {x1, x2, ..., xn}.
Für diese gibt es 2 Möglichkeiten.
- Möglichkeit: xn+1 ist nicht in der Teilmenge. Dann bildet sich die Teilmenge U' aus {x1, x2, ..., xn} und damit laut Induktionsvoraussetzung |P({x1, x2, ..., xn)| = 2^n
- Möglichkeit: xn+1 ist in der Teilmenge. Dann gilt, dass U = U' vereinigt mit {xn+1}. Weil es 2^n verschiedene U' gibt, gibt es auch 2^n verschiedene U' vereinigt mit {xn+1}
Daraus folgen wir also, dass
Und damit ist der Beweis fertig.
Du musst eigentlich nur wissen, dass |P(M)| = 2^|M| = 2^n
Und dann ist es auch easy, auszurechnen, wie viele Teilmengen es z.B. mit 4 Elementen gibt. Nämlich 2^4 = 16