Wie viele Elemente enthält das Kraftpaket?

Der Kraftsatz eines Satzes EIN ist die Sammlung aller Teilmengen von A. Bei der Arbeit mit einer endlichen Menge 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 istⁿ 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) 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 dann EIN hat zwei Elemente und P (A) = , a, b, a, b, eine Menge mit zwei Elementen.

In all diesen Situationen ist es einfach, bei Mengen mit einer kleinen Anzahl von Elementen festzustellen, ob es eine endliche Anzahl von Elementen gibt n Elemente in EIN, dann stellte sich die Kraft ein P (EIN) hat 2n Elemente. Aber setzt sich dieses Muster fort? Nur weil ein Muster zutrifft n = 0, 1 und 2 bedeutet nicht unbedingt, dass das Muster für höhere Werte von wahr ist n.

Dieses Muster setzt sich jedoch fort. Um zu zeigen, dass dies tatsächlich der Fall ist, werden wir den Beweis durch Induktion verwenden.

Beweis durch Induktion

Der Induktionsnachweis ist nützlich, um Aussagen über alle natürlichen Zahlen zu beweisen. Dies erreichen wir in zwei Schritten. Im 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 ist die Annahme, dass die Aussage zutrifft n = k, und die Show, die dies impliziert, gilt für die Aussage n = k + 1.

Eine weitere Beobachtung

Um unseren Beweis zu erbringen, benötigen wir eine weitere Beobachtung. Aus den obigen Beispielen können wir erkennen, 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 Teilmenge von a hinzufügen. Diese Mengenaddition wird durch die Mengenoperation von union 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 Sätzen von P (a, b) und fügen zu jedem dieser Sätze 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 haben wir insgesamt acht Elemente in P (a, b, c).

Der Beweis

Wir sind jetzt bereit, die Aussage zu beweisen: „Wenn der Satz EIN enthält n Elemente, dann die Leistung eingestellt P (A) hat 2ⁿ Elemente. "

Zunächst stellen wir fest, 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 gilt für 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 2ⁿ von diesen. Dann addieren wir das Element x zu jeder dieser Teilmengen von B, was zu einem weiteren 2ⁿ Teilmengen von B. Dies erschöpft die Liste der Teilmengen von B, und so ist die Summe 2ⁿ + 2ⁿ = 2 (2ⁿ) = 2^{n + 1} Elemente des Potenzsatzes von EIN.