Das Power Set eines Satzes EIN ist die Sammlung aller Teilmengen von A. Bei der Arbeit mit einem Endlichen einstellen mit n Eine Frage, die wir uns stellen könnten, lautet: „Wie viele Elemente enthält die Potenzmenge von EIN? " Wir werden sehen, dass die Antwort auf diese Frage 2 istn und mathematisch beweisen, warum dies wahr ist.
Beobachtung des Musters
Wir werden nach einem Muster suchen, indem wir die Anzahl der Elemente in der Potenzmenge von beobachten EIN, wo EIN hat n Elemente:
- Wenn EIN = {} (die leere Menge) also EIN hat aber keine elemente P (A) = {{}}, eine Menge mit einem Element.
- Wenn EIN = {a} also EIN hat ein Element und P (A) = {{}, {a}}, eine Menge mit zwei Elementen.
- Wenn EIN = {a, b} also EIN hat zwei Elemente und P (A) = {{}, {a}, {b}, {a, b}}, eine Menge mit zwei Elementen.
In all diesen Situationen ist es einfach zu sehen setzt mit einer kleinen Anzahl von Elementen, die, wenn es eine endliche Anzahl von gibt n Elemente in EIN, dann die Leistung eingestellt P. (EIN) hat 2
n Elemente. Aber geht dieses Muster weiter? Nur weil ein Muster wahr ist für n = 0, 1 und 2 bedeutet nicht unbedingt, dass das Muster für höhere Werte von gilt n.Dieses Muster setzt sich jedoch fort. Um zu zeigen, dass dies tatsächlich der Fall ist, werden wir Beweise durch Induktion verwenden.
Beweis durch Induktion
Der Nachweis durch Induktion ist nützlich, um Aussagen zu allen natürlichen Zahlen zu beweisen. Dies erreichen wir in zwei Schritten. Für den ersten Schritt verankern wir unseren Beweis, indem wir eine wahre Aussage für den ersten Wert von zeigen n das möchten wir berücksichtigen. Der zweite Schritt unseres Beweises besteht darin, anzunehmen, dass die Aussage für gilt n = kund die Show, die dies impliziert, gilt für die Aussage n = k + 1.
Eine weitere Beobachtung
Um unseren Beweis zu erleichtern, benötigen wir eine weitere Beobachtung. Aus den obigen Beispielen können wir sehen, dass P ({a}) eine Teilmenge von P ({a, b}) ist. Die Teilmengen von {a} bilden genau die Hälfte der Teilmengen von {a, b}. Wir können alle Teilmengen von {a, b} erhalten, indem wir das Element b zu jeder der Teilmengen von {a} hinzufügen. Diese Mengenaddition wird mittels der Mengenoperation der Vereinigung erreicht:
- Leere Menge U {b} = {b}
- {a} U {b} = {a, b}
Dies sind die beiden neuen Elemente in P ({a, b}), die keine Elemente von P ({a}) waren.
Wir sehen ein ähnliches Vorkommen für P ({a, b, c}). Wir beginnen mit den vier Mengen von P ({a, b}) und fügen zu jeder dieser Mengen das Element c hinzu:
- Leere Menge U {c} = {c}
- {a} U {c} = {a, c}
- {b} U {c} = {b, c}
- {a, b} U {c} = {a, b, c}
Und so erhalten wir insgesamt acht Elemente in P ({a, b, c}).
Der Beweis
Wir sind jetzt bereit, die Aussage zu beweisen: „Wenn das Set EIN enthält n Elemente, dann die Leistung eingestellt P (A) hat 2n Elemente. "
Wir beginnen mit der Feststellung, dass der Beweis durch Induktion für die Fälle bereits verankert ist n = 0, 1, 2 und 3. Wir nehmen durch Induktion an, dass die Aussage für gilt k. Nun lass das Set EIN enthalten n + 1 Elemente. Wir können schreiben EIN = B. U {x}, und überlegen Sie, wie Teilmengen von gebildet werden EIN.
Wir nehmen alle Elemente von P (B)und nach der induktiven Hypothese gibt es 2n von diesen. Dann fügen wir das Element x zu jeder dieser Teilmengen von hinzu B., was zu weiteren 2 führtn Teilmengen von B.. Dies erschöpft die Liste der Teilmengen von B.und so ist die Summe 2n + 2n = 2(2n) = 2n + 1 Elemente des Kraftsatzes von EIN.