Mathematik

Wie viele Elemente enthält das Power Set?

Die Potenzmenge einer Menge A ist die Sammlung aller Teilmengen von A. Wenn wir mit einer endlichen Menge mit n Elementen arbeiten, könnten wir uns die Frage stellen: „Wie viele Elemente enthält die Potenzmenge von A ?“ Wir werden sehen, dass die Antwort auf diese Frage 2 n ist  und mathematisch beweisen, warum dies wahr ist.

 

Beobachtung des Musters

Wir werden durch die Beobachtung der Anzahl der Elemente in dem Leistungssatz für ein Muster aussehen A , wo A hat n Elemente:

  • Wenn A={} (die leere Menge), dann hat A keine Elemente außer P (A)={{}}, eine Menge mit einem Element.
  • Wenn A={a}, dann hat A ein Element und P (A)={{}, {a}} eine Menge mit zwei Elementen.
  • Wenn A={a, b}, dann hat A zwei Elemente und P (A)={{}, {a}, {b}, {a, b}}, eine Menge mit zwei Elementen.

In all diesen Situationen ist es für Mengen  mit einer kleinen Anzahl von Elementen einfach zu erkennen, dass die Potenzmenge P ( A ) 2 n Elemente hat , wenn es eine endliche Anzahl von n Elementen in A gibt . Aber setzt sich dieses Muster fort? Nur weil ein Muster für n=0, 1 und 2 gilt, bedeutet dies nicht unbedingt, dass das Muster für höhere Werte von n gilt .

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. Im ersten Schritt verankern wir unseren Beweis, indem wir eine wahre Aussage für den ersten Wert von n zeigen , den wir berücksichtigen möchten. Der zweite Schritt unseres Beweises besteht darin, anzunehmen, dass die Aussage für n=k gilt , und zu zeigen, dass dies impliziert, dass die Aussage für n=k + 1 gilt.

 

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 die Menge A n Elemente enthält , dann hat die Potenzmenge P (A) 2 n Elemente.“

Wir beginnen mit der Feststellung, dass der Beweis durch Induktion bereits für die Fälle n=0, 1, 2 und 3 verankert wurde . Wir nehmen durch Induktion an, dass die Aussage für k gilt . Nun wollen wir die Menge A enthalten n + 1 Elemente. Wir können A=B U {x} schreiben und überlegen, wie Teilmengen von A gebildet werden sollen .

Wir nehmen alle Elemente von P (B) und nach der induktiven Hypothese gibt es 2 n davon. Dann fügen wir das Element x zu jeder dieser Teilmengen von B hinzu , was zu weiteren 2 n Teilmengen von B führt . Diese entleert die Liste der Untergruppen von B , so dass die insgesamt 2 n + 2 n=2 (2 n )=2 n + 1 Elemente der Potenzmenge von A .

Similar Posts

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.