Beweis: Eine n-elementige Menge hat 2^n Teilmengen

21.09.2005, 12:58	way	Auf diesen Beitrag antworten »
Beweis: Eine n-elementige Menge hat 2^n Teilmengen Hi Leute, ich hab ein paar Fragen zu dem Beweis, wieso eine n-elementige Menge, 2^n Teilmengen hat. Ich führe den Beweis durch vollständige Induktion nach n. Der Induktionsanfang ist klar: Für die leere Menge gibt es eine Teilmenge, 2^0=1. Die Indukitonsvoraussetzung ist, dass folgendes gilt: Die Potenzmenge der Menge M (,die n Elemente enhält) hat genau 2^n Teilmengen. Ich habe jetzt meine erste Frage zum Induktionsschluss: Ich betrachte eine n-elemntige Menge und füge ein weiteres Element x_0 hinzu. Jetzt kann ich doch die Teilmengen in zwei Klassen aufteilen. Einmal in die 1. Klasse, die die Teilmengen enthält, die das x_0 enthalten, und einmal in die 2. Klasse, die die Teilmengen enthält, die das x_0 nicht enthalten. Jetzt heisst es hier im Beweis: Die Teilmengen, die das x_0 nicht enthalten, sind genau die Teilmengen der n-Elementigen Menge und haben somit 2^n Teilmengen. Wie kommt man darauf, dass das genau die Teilmengen der n-Elementigen Menge sind??? Danke und Grüsse...
21.09.2005, 13:27	therisen	Auf diesen Beitrag antworten »
Hallo way, du hast eine Menge M, die $\begin{eqnarray} x_0 \end{eqnarray}$ nicht enthält und die Mächtigkeit n hat. Nun fügst du ein Element $\begin{eqnarray} x_0 \end{eqnarray}$ zu M hinzu und erhältst die Menge $\begin{eqnarray} A := M \cup \{x_0\} \end{eqnarray}$ und $\begin{eqnarray} \|A\|=n+1 \end{eqnarray}$ Jede Teilmenge $\begin{eqnarray} T \subset A \end{eqnarray}$ enthält also entweder $\begin{eqnarray} x_0 \end{eqnarray}$ oder nicht $\begin{eqnarray} x_0 \end{eqnarray}$ . Nach Konstruktion von A ist klar, dass jede Teilmenge, die $\begin{eqnarray} x_0 \end{eqnarray}$ nicht enthält, eine Teilmenge von M ist. Und davon gibt es nach Induktionsvoraussetzung eben $\begin{eqnarray} 2^n \end{eqnarray}$ . Ist das verständlich? Gruß, therisen
21.09.2005, 13:32	way	Auf diesen Beitrag antworten »
Hallo therisen, ja, vielen Dank!, das war sehr veständlich. Habe es jetzt verstanden! Grüsse...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »