Kardinalität Potenzmenge

01.11.2008, 20:33

Svenja1986

Kardinalität Potenzmenge

Hey

Es geht um folgende Aufgabe:

Zeigen Sie bitte auf folgende beiden Weisen, dass eine endliche Menge M mit m Elementen genau $\begin{eqnarray*} 2^m \end{eqnarray*}$ Teilmengen besitzt, d. h. die Kardinalität der Potenzmenge von M ist

$\begin{eqnarray*} |\mathbb{P}(M)|= 2^{|M|} \end{eqnarray*}$ .

(a)
Beweisen Sie die Behauptung mit Hilfe der vollständigen Induktion.
Hinweis: Beschreiben Sie im Induktionsschritt ausgehend von einer Menge M' mit m Elementen die Menge m+1 Elementen mit $\begin{eqnarray*} M=M'\cup{x} \end{eqnarray*}$ , wobei $\begin{eqnarray*} x\notin M' \end{eqnarray*}$ ist, und betrachten Sie die Teilemngen von M, die x enthalten bzw. nicht enthalten.

(b)
Für jede Zahl $\begin{eqnarray*} n \in \mathbb{N}_0 \end{eqnarray*}$ beschreibt der Binomialkoeffizient $\begin{eqnarray*} \binom m n \end{eqnarray*}$ die Anzahl der n-elementigen Teilmengen von M.
Dann ist die Gesamtzahl aller Teilmengen von M gerade die Summe aller Teilmengen mit Kardinalität $\begin{eqnarray*} n\leq m \end{eqnarray*}$ .
Zeigen Sie, dass somit aus dem Binomischen Lehrsatz folgt:
$\begin{eqnarray*} \sum_{n=0}^{m} \binom m n =2^m=|\mathbb{P}(M)|= 2^{|M|} \end{eqnarray*}$ .

zu (a) Da habe ich irgendwie überhaupt keine Ahnung unglücklich

zu (b) Habe mal für m 1 eingesetzt, wo dann 2 rauskommen würde. Aber das ist ja kein Beweis, sondern nur ein Beispiel. Könnte man das Beispiel vll als Induktionsanfang nehmen oder soll man hier gar nicht die vollständige Induktion verwenden? Naja, wenn ich dann mit m+1 weitermachen würde, würde ich ja aber auch nicht wirklich auf ein sinnvolles Ergebnis kommen...

Helft mir mal bitte auf die Sprünge... Tanzen

01.11.2008, 21:02

Leopold

Auf diesen Beitrag antworten »

Zu a): Nehmen wir einmal die Gültigkeit für $\begin{eqnarray*} n=3 \end{eqnarray*}$ an. Dann betrachten wir irgendeine Menge $\begin{eqnarray*} M \end{eqnarray*}$ mit 4 Elementen $\begin{eqnarray*} a,b,c,x \end{eqnarray*}$ . Die ersten drei sollen die Menge $\begin{eqnarray*} M' \end{eqnarray*}$ bilden. Dann gilt offenbar

$\begin{eqnarray*} M = M' \cup \{ x \} \end{eqnarray*}$

Es gibt nun Teilmengen von $\begin{eqnarray*} M \end{eqnarray*}$ , die $\begin{eqnarray*} x \end{eqnarray*}$ nicht enthalten (Kategorie I). Das müssen dann die Teilmengen von $\begin{eqnarray*} M' \end{eqnarray*}$ sein. Da $\begin{eqnarray*} M' \end{eqnarray*}$ drei Elemente enthält, sind das $\begin{eqnarray*} 2^3 = 8 \end{eqnarray*}$ Stück. Und das sind sie:

$\begin{eqnarray*} \emptyset, \{ a \}, \{ b \}, \{ c \}, \{ a,b \}, \{ a,c \}, \{ b,c \} ,\{ a,b,c \} \end{eqnarray*}$

Und jetzt betrachte die Kategorie II derjenigen Teilmengen von $\begin{eqnarray*} M \end{eqnarray*}$ , die $\begin{eqnarray*} x \end{eqnarray*}$ enthalten. Wie stehen die mit den Teilmengen der Kategorie I in Zusammenhang? Genauer: Wie kann man die Teilmengen der Kategorie I denjenigen der Kategorie II eineindeutig zuordnen? Was passiert also bei jedem hinzukommenden Element (Induktionsschritt)?

01.11.2008, 21:24

Svenja1986

Auf diesen Beitrag antworten »

Auf Anhieb würde ich jetzt sagen, dass man jedes Element der Potenzmenge mit {x} vereinigt...

$\begin{eqnarray*} \emptyset \cup \{x\}= \{x\} \end{eqnarray*}$ usw.

Man erhält dann zusätzlich zu den 8, die du oben genannt hast, die folgenden 8:
$\begin{eqnarray*} \{ x \}, \{ a,x \}, \{ b,x \}, \{ c,x \}, \{ a,b,x \}, \{ a,c,x \}, \{ b,c,x \} ,\{ a,b,c,x \} \end{eqnarray*}$

Man hat dann also insgesamt 16 Elemente $\begin{eqnarray*} = 2^4 = 2^{3+1} = 2^{m+1} \end{eqnarray*}$

Und wenn wir jetzt noch eine Teilmenge M'' = {y} hätten, hätten wir die 16 bestehenden Elemente und die 16 Elemente vereinigt mit {y}, insgesamt dann 32=2^5.

Richtig? Aber das ist ja noch kein Beweis... leider unglücklich

01.11.2008, 21:42

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von Svenja1986
Richtig? Aber das ist ja noch kein Beweis... leider unglücklich

Doch! Das ist schon der Beweis. Oder sagen wir besser: die Beweisidee! Das Ganze ist jetzt nur noch nicht formalisiert. Versuche einmal, von dem konkreten Beispiel $\begin{eqnarray*} 3 \mapsto 4 \mapsto 5 \end{eqnarray*}$ wegzukommen und allgemein zu formulieren: $\begin{eqnarray*} n \mapsto n+1 \end{eqnarray*}$ . Dann hast du es.

Ich helfe dir einmal. Nehmen wir die Behauptung als für alle Mengen mit $\begin{eqnarray*} n \end{eqnarray*}$ Elementen als bewiesen an. Und betrachten wir nun eine Menge $\begin{eqnarray*} M \end{eqnarray*}$ mit $\begin{eqnarray*} n+1 \end{eqnarray*}$ Elementen, unter denen wir eines, nennen wir es $\begin{eqnarray*} x \end{eqnarray*}$ , auszeichnen. Die restlichen Elemente bilden dann eine Menge $\begin{eqnarray*} M' \end{eqnarray*}$ mit $\begin{eqnarray*} n \end{eqnarray*}$ Elementen. Es gilt:

$\begin{eqnarray*} M = M' \cup \{ x \} \end{eqnarray*}$

Und jetzt betrachte wieder die Kategorien I und II ...

Und zu guter Letzt schließlich den Induktionsanfang nicht vergessen.

01.11.2008, 22:08

Svenja1986

Auf diesen Beitrag antworten »

Ok...

Es gilt also:

$\begin{eqnarray*} M = M' \cup \{ x \} \end{eqnarray*}$

$\begin{eqnarray*} M = 2^n \cup 2^1 \end{eqnarray*}$

$\begin{eqnarray*} M = 2^{n+1} \end{eqnarray*}$

Wäre das als Induktionsschritt/schluss ausreichend?

01.11.2008, 23:11

Leopold

Auf diesen Beitrag antworten »

Huch! Was machst du denn da?
Du mußt eine Menge von ihrer Kardinalität unterscheiden:

$\begin{eqnarray*} M = M' \cup \{ x \} \end{eqnarray*}$

Gesucht ist nun $\begin{eqnarray*} | \mathcal{P}(M) | \end{eqnarray*}$ , wobei nach Induktionsannahme eine Menge mit $\begin{eqnarray*} n \end{eqnarray*}$ Elementen $\begin{eqnarray*} 2^n \end{eqnarray*}$ Teilmengen besitzt.

Die Teilmengen von $\begin{eqnarray*} M \end{eqnarray*}$ zerfallen in zwei Kategorien, solche, die $\begin{eqnarray*} x \end{eqnarray*}$ nicht enthalten, sie bilden die I. Kategorie $\begin{eqnarray*} \mathcal{M}_{\text{I}} \end{eqnarray*}$ (das ist nichts anderes als $\begin{eqnarray*} \mathcal{P}(M') \end{eqnarray*}$ ), und solche, die $\begin{eqnarray*} x \end{eqnarray*}$ enthalten, sie bilden die II. Kategorie $\begin{eqnarray*} \mathcal{M}_{\text{II}} \end{eqnarray*}$ . Die Vereinigung

$\begin{eqnarray*} \mathcal{P}(M) = \mathcal{M}_{\text{I}} \cup \mathcal{M}_{\text{II}} \end{eqnarray*}$

ist eine disjunkte Vereinigung. Es gilt daher:

$\begin{eqnarray*} | \mathcal{P}(M) | = | \mathcal{M}_{\text{I}} | + | \mathcal{M}_{\text{II}} | \end{eqnarray*}$

Und jetzt wende auf die beiden Summanden die Induktionsvoraussetzung an. Beim zweiten Summanden mußt du zuvor noch eine Bijektion herstellen. Das geht genau so wie im Spezialfall $\begin{eqnarray*} 3 \mapsto 4 \end{eqnarray*}$ .

Und ganz wichtig: Mathematik besteht nicht aus Formeln, sondern aus Inhalten. Die Formeln müssen daher durch Text verbunden werden, sonst entstehen diese Inhalte nicht. Was ich oben an Text geschrieben habe, ist also kein hübsches, aber überflüssiges Beiwerk, sondern zum Verständnis notwendig.

02.11.2008, 11:19

Svenja1986

Auf diesen Beitrag antworten »

Ok, alles klar. DANKE Tanzen

Hat noch jmd einen Tipp für die (b)?

02.11.2008, 14:41

Leopold

Auf diesen Beitrag antworten »

Der Tip steht ja eigentlich schon bei der Aufgabe: Binomischer Lehrsatz.

$\begin{eqnarray*} (a+b)^m = \sum_{n=0}^m {m \choose n} a^n b^{m-n} \end{eqnarray*}$

Und jetzt spezialisiere hier $\begin{eqnarray*} a=b=1 \end{eqnarray*}$ . Und dann mußt du noch die Bedeutung der Binomialkoeffizienten für die Kombinatorik kennen. Aber das steht ja auch schon in der Aufgabe ...

02.11.2008, 18:42

Svenja1986

Auf diesen Beitrag antworten »

Ok, ich habe das jetzt mal für a=b=1 ausprobiert:

$\begin{eqnarray*} (1+1)^m = \sum_{n=0}^m {m \choose n} 1^n 1^{m-n} \end{eqnarray*}$
$\begin{eqnarray*} 2^m = \sum_{n=0}^m {m \choose n} \end{eqnarray*}$
So, dann habe ich mal m=1 gewählt:

$\begin{eqnarray*} 2^1 = \sum_{n=0}^1 {1 \choose 0} \end{eqnarray*}$

$\begin{eqnarray*} {1 \choose 0}=\frac{1!}{0!(1-0)!} \end{eqnarray*}$

$\begin{eqnarray*} =\frac{1}{1} \end{eqnarray*}$

$\begin{eqnarray*} =1 \end{eqnarray*}$

Was habe ich jetzt schon wieder falsch gemacht? unglücklich

14.11.2009, 17:22

saeff

Auf diesen Beitrag antworten »

weitere frage
wie stelle ich diese Bijektion für M II im Allgemeinfall her?

Neue Frage »

Antworten »

Kardinalität Potenzmenge

Verwandte Themen