Wie viele Elemente enthält das Power-Set?

conceptdraw.com

Das Macht gesetzt eines Satzes EIN ist die Sammlung aller Teilmengen von A. Bei der Arbeit mit endlichen einstellen mit n Elemente, eine Frage, die wir uns stellen könnten, lautet: Wie viele Elemente gibt es in der Potenzmenge von EIN ? Wir werden sehen, dass die Antwort auf diese Frage 2 ist ⁿ und beweise mathematisch, warum das so 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), dann EIN hat keine Elemente aber P (A) = { { } }, eine Menge mit einem Element.
• Wenn EIN = {a}, dann 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 zu erkennen setzt mit einer kleinen Anzahl von Elementen, wenn es eine endliche Anzahl von gibt n Elemente hinein EIN , dann der Leistungssatz P ( EIN ) hat 2 n Elemente. Aber setzt sich dieses Muster fort? Nur weil ein Muster wahr ist n = 0, 1 und 2 bedeutet nicht unbedingt, dass das Muster für höhere Werte von wahr ist n .

Aber dieses Muster setzt sich fort. Um zu zeigen, dass dies tatsächlich der Fall ist, verwenden wir einen Induktionsbeweis.

Beweis durch Induktion

Beweis durch Induktion ist nützlich, um Aussagen zu beweisen, die alle natürlichen Zahlen betreffen. 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 die wir berücksichtigen möchten. Der zweite Schritt unseres Beweises besteht darin, anzunehmen, dass die Aussage gilt n = k , und die Show, dass dies impliziert, dass die Aussage gilt für n = k + 1.

Eine weitere Beobachtung

Um bei unserem Beweis zu helfen, 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 durch die Mengenoperation 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 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 nun bereit, die Aussage If the set zu beweisen EIN enthält n Elemente, dann der Potenzsatz P(A) hat 2 ⁿ Elemente.

Wir stellen zunächst fest, dass der Induktionsbeweis für die Fälle bereits verankert ist n = 0, 1, 2 und 3. Wir nehmen per Induktion an, dass die Aussage für gilt k . Lassen Sie nun das Set EIN enthalten n + 1 Elemente. Wir können schreiben EIN = B U {x}, und überlege, wie man Teilmengen von bildet EIN .

Wir nehmen alle Elemente von P(B) , und nach Induktionsannahme gibt es 2 ⁿ von diesen. Dann fügen wir das Element x zu jeder dieser Teilmengen von hinzu B , was zu weiteren 2 führt ⁿ Teilmengen von B . Damit ist die Liste der Teilmengen von erschöpft B , also insgesamt 2 ⁿ + 2 ⁿ = 2(2 ⁿ ) = 2 ^{n + 1}Elemente der Potenzmenge von EIN .