Beweis Potenzmenge

28.10.2013, 20:45

Lynn2

Auf diesen Beitrag antworten »

Beweis Potenzmenge

Meine Frage:
Huhu.

Aufgabe: M sei eine nicht-leere Menge. Zeigen Sie, dass die Potenzmenge P(M) genau so viele Elemente gerader Mächtigkeit wie ungerader Mächtigkeit enthält.

Meine Ideen:
Vorab erstmal mein Verständnis der Aufgabe: Ich soll beweisen, dass es in der M genauso viele ungerade als auch gerade Zahlen gibt. Ist das richtig?
Wenn ja, wie kann ich das am besten beweisen? Vielleicht mit einem Beispiel?

28.10.2013, 21:20

Math1986

Auf diesen Beitrag antworten »

RE: Beweis Potenzmenge

Zitat:

Original von Lynn2
Meine Ideen:
Vorab erstmal mein Verständnis der Aufgabe: Ich soll beweisen, dass es in der M genauso viele ungerade als auch gerade Zahlen gibt. Ist das richtig?

Nein. Es geht um die Mächtigkeit der Elemete der Potenzmenge P(M) von M. Diese besteht also aus allen Teilmengen von M. Zu zeigen ist also, dass es davon genausoviele Teilmengen gerader wie ungerader Ordnung gibt.

28.10.2013, 21:21

jimmyt

Auf diesen Beitrag antworten »

RE: Beweis Potenzmenge
Huhu Augenzwinkern

Augenzwinkern

Zitat:

Original von Lynn2
...
Meine Ideen:
Vorab erstmal mein Verständnis der Aufgabe: Ich soll beweisen, dass es in der M genauso viele ungerade als auch gerade Zahlen gibt. Ist das richtig?

Die Potenzmenge von M enthält genauso viele Teilmengen mit gerader Anzahl an Elementen wie Teilmengen mit ungerader Anzahl an Elementen.
Bspw. M={a,b}, dann ist P(M)={{}, {a}, {b}, {a,b}}. 2 Teilmengen mit gerader, und 2 Teilmengen mit ungerader Anzahl an Elementen.

Zitat:

Original von Lynn2
Wenn ja, wie kann ich das am besten beweisen? Vielleicht mit einem Beispiel?

Weißt du wieviele Elemente eine Potenzmenge hat?
Wenn ja, kennst du den Beweis mit vollständiger Induktion der Formel für die Anzahl der Elemente einer Potenzmenge?

28.10.2013, 21:22

jimmyt

Auf diesen Beitrag antworten »

@Math1986 :

Sorry, du warst eine Minute schneller als ich. Augenzwinkern

Augenzwinkern

28.10.2013, 21:29

Lynn2

Auf diesen Beitrag antworten »

Vielen Dank für eure schnellen Antworten.

Was verstehe ich denn unter Mächtigkeit?

@ jimmyt: Ich weiß leider nicht mehr über die Potenzmenge, nur das was oben beschrieben ist. Also, dass M eine nicht-leere und endliche Menge ist.

Soweit ich es rauslesen konnte, kann ich das einfach anhand eines Beispiels beweisen?

28.10.2013, 21:38

jimmyt

Auf diesen Beitrag antworten »

Math1986 war schneller als ich. Ich lasse ihm den Vortritt.
Aber wenn du nur ein Beispiel möchtest ... das habe ich dir schon gepostet. Augenzwinkern

Augenzwinkern

Anzeige

28.10.2013, 21:43

Lynn2

Auf diesen Beitrag antworten »

Ich weiß, dass du schon ein Bsp. gepostet hast. Danke dafür. smile

smile

Nun war jedoch meine Frage, ob dies als Beweis ausreicht bzw. ob dies ausreichend ist für die Aufgabe!?

28.10.2013, 21:49

jimmyt

Auf diesen Beitrag antworten »

Wie gesagt, Math1986 war schneller als ich,
aber ein einiziges Beispiel ist generell in den meisten Fällen kein echter Beweis. Augenzwinkern

Augenzwinkern

28.10.2013, 21:54

Lynn2

Auf diesen Beitrag antworten »

Dann hoffe ich mal, dass Math1986 mir weiter hilft. Augenzwinkern

Augenzwinkern

28.10.2013, 22:00

Math1986

Auf diesen Beitrag antworten »

Die Mächtigkeit einer Menge ist die Anzahl ihrer Elemente, soviel sollte schon bekannt sein unglücklich

unglücklich

Es ist also mit anderen Worten zu zeigen, dass M genausoviele Teilmengen gerader wie ungerader Mächtigkeit hat.

Beweis durch Beispiel bringts nicht, es muss ja gezeigt werden, dass es eben für alle Mengen gilt.

Induktion ist hier schon ein Stichwort, aber eben nicht über die Mächtigkeit der Potenzmenge P(M), sondern über die Mächtigkeit der Menge M selbst:
Man nimmt an, $\begin{eqnarray*} M \end{eqnarray*}$ sei eine Menge mit n Elementen. Nun nimmt man ein festes $\begin{eqnarray*} x\in M \end{eqnarray*}$ und betrachtet $\begin{eqnarray*} M':=M\setminus\left\{x\right\} \end{eqnarray*}$
Nach Induktionsvoraussetzung hat nun $\begin{eqnarray*} M' \end{eqnarray*}$ genausoviel Teilmengen gerader wie ungerader Mächtigkeit.
Nun kommt der Induktionsschluss, und den zeigst du nun mal bitte mit etwas mehr Eigeninitiative. Ich bin hier für heute erstmal raus und schaue mir morgen deine Ergebnisse an.

28.10.2013, 22:22

Lynn2

Auf diesen Beitrag antworten »

Warum lasse ich bei M' {x} weg?

Mein Vorschlag: $\begin{eqnarray*} 2^{n} \end{eqnarray*}$ = Mächtigkeit der Potenzmenge

Induktionsanfang: n=1
$\begin{eqnarray*} 2^{1}=2 \end{eqnarray*}$ -> 1mal ungerade Mächtigkeit und 1mal gerade

Induktionsbehauptung:
$\begin{eqnarray*} 2^{n} \end{eqnarray*}$

Induktionsbeweis:
$\begin{eqnarray*} 2^{n+1}=2^{n} \cdot 2 \end{eqnarray*}$ -> hat genauso viel ungerade, als auch gerade, da durch 2 teilbar

29.10.2013, 08:19

Math1986

Auf diesen Beitrag antworten »

1) M hat n Elemente, also hat M' n-1 Elemente und wir können die Induktionsannahme anwenden.

2) Warum folgt daraus, dass die Potenzmenge eine gerade Anzahl Elemente hat, auf einmal, dass es genausoviele Elemente gerader wie ungerader Ordnung gibt?

29.10.2013, 12:43

Lynn2

Auf diesen Beitrag antworten »

Die Potenzmenge hat eine gerade Anzahl von Elementen, da $\begin{eqnarray*} 2^{n} \cdot 2 \end{eqnarray*}$ eine gerade Anzahl ergibt. Und wenn ich diese durch 2 Teile habe ich x ungerade Elemente und x gerade Elemente.

29.10.2013, 15:54

Math1986

Auf diesen Beitrag antworten »

Nein. Dir ist schon klar,was mit "ungeraden" und "geraden" Elementen gemeint ist?

Es geht darum, ob diese Elemente der Potenzmenge eine gerade oder ungerade Anzahl Elemente enthalten., mit der Mächtigkeit der Potenzmenge selbst hat das gar nichts zu tun.

29.10.2013, 16:21

Lynn2

Auf diesen Beitrag antworten »

Ja, ich soll zeigen, dass die Potenzmenge genauso viele Teilmengen mit einer ungeraden Anzahl von Elementen besitzt wie mit einer geraden Anzahl von Elementen.

29.10.2013, 16:33

Math1986

Auf diesen Beitrag antworten »

Ja genau, mit der Anzahl Elementen in der Potenzmenge hat das erstmal nichts zu tun. Deine Argumentation bringt dich da nicht weiter.

29.10.2013, 17:50

Lynn2

Auf diesen Beitrag antworten »

Dann weiß ich leider nicht weiter. unglücklich

unglücklich

29.10.2013, 17:54

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von Lynn2
Dann weiß ich leider nicht weiter. unglücklich

unglücklich

Na, du könntest dir ja mal meinen Ansatz anschauen, den ich gepostet habe, und da auch mal länger drüber nachdenken. Sonst kommen wir hier wirklich nicht weiter.

29.10.2013, 17:57

Sturmgepard

Auf diesen Beitrag antworten »

Also nehmen wir für den Beweis einfach an, dass eine Potezmenge genau so viele Teilmengen gerader Mächtigkeit wie ungerader Mächtigkeit hat. Zu zeigen ist nun, dass dies für jede Menge gilt. um dies zu zeigen erzeugen wir also eine Menge M' die ein Element weniger hat, nämlich x.

29.10.2013, 18:00

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von Sturmgepard
Also nehmen wir für den Beweis einfach an, dass eine Potezmenge genau so viele Teilmengen gerader Mächtigkeit wie ungerader Mächtigkeit hat. Zu zeigen ist nun, dass dies für jede Menge gilt. um dies zu zeigen erzeugen wir also eine Menge M' die ein Element weniger hat, nämlich x.

Nicht ganz. Wir machen eine Induktion, d.h. wir nehmen an, die Aussage gelte für (n-1)-elementige Mengen und zeigen die Aussage für n-elementige Mengen, indem wir ein Element x entfernen und so eine (n-1)-elementige Menge erhalten. Man zeigt dann, dass es auch für n-elementige Mengen gilt.

29.10.2013, 18:11

Math1986

Auf diesen Beitrag antworten »

@Sturmgepard: Gerade und ungerade Mächtigkeit
Habe das Thema wieder geöffnet, nachdem ich etwas mehr über seinen Ansatz nachgedacht habe. Scheint zu funktionieren. wenn ich da nichts übersehen habe.

29.10.2013, 18:17

Sturmgepard

Auf diesen Beitrag antworten »

Bist du dir sicher, dass die Aufgabe es so verlangt?

29.10.2013, 18:21

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von Sturmgepard
Bist du dir sicher, dass die Aufgabe es so verlangt?

Die Aufgabe verlangt nur einen Beweis smile

smile

Wie genau der auszusehen hat ist nicht weiter angegeben. Man kann es entweder mit Induktion machen (mein Ansatz hier) oder man kann deinen Ansatz im anderen Thema verfolgen. Beides scheint zielführend zu sein. Habe das andere Thema daher wieder geöffnet.

29.10.2013, 18:46

Lynn2

Auf diesen Beitrag antworten »

Okay.

M hat n-Elemente
M' hat (n-1)-Elemente

Induktionsvoraussetzung: M' hat genauso viel ungerade Teilmengen wie auch gerade Teilmengen
Induktionsbehauptung: M hat genauso viel ungerade Teilmengen wie auch gerade Teilmengen
Beweis: M = M' + {x}

Habe ich das soweit richtig verstanden?

29.10.2013, 18:46

Sturmgepard

Auf diesen Beitrag antworten »

Top, habe es verstanden. Danke
Wie hängst du mit Mathe denn so zusammen?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »