Induktionsbeweis < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beweisen Sie mit vollständiger Induktion, dass für endliche
Mengen M gilt
|P(M)| = 2|M|.
(i) Formulieren Sie die Behauptung als eine von n abhängige Aussage A(n), wobei n = |M|
gilt.
(ii) Gilt die Behauptung auch für M = [mm] \emptyset [/mm] ?
(iii) Zeigen Sie, dass A(n) gilt, wenn A(n − 1) wahr ist.
Tipp: Für jedes a [mm] \in [/mm] M gilt: Es gibt in P(M) genausoviele Mengen, die a enthalten, wie solche,
die a nicht enthalten. |
Zu (i) hab ich:
[mm]A(n)=2^n[/mm]
Zu (ii):
Ja, denn wenn M die leere Menge enthält, ist P(M) = 1.
Also [mm]1=2^0[/mm] ist gleich also ist die Behauptung auch für M = [mm] \emptyset [/mm] gültig!
Zu (iii):
Mir ist zu (iii) leider noch nichts eingefallen könnte mir da einer weiterhelfen beim Ansatz?
Zum Tip:
Kann mir einer sagen was der Tipp genau fürn Tipp ist und inwiefern mir der Tipp weiterhelfen soll? Irgendwie begreif ich nicht was das sagen soll!
|
|
| |
|
Hallo Blackpearl,
> Beweisen Sie mit vollständiger Induktion, dass für
> endliche
> Mengen M gilt
> |P(M)| = 2|M|.
> (i) Formulieren Sie die Behauptung als eine von n
> abhängige Aussage A(n), wobei n = |M|
> gilt.
> (ii) Gilt die Behauptung auch für M = [mm]\emptyset[/mm] ?
> (iii) Zeigen Sie, dass A(n) gilt, wenn A(n − 1) wahr
> ist.
> Tipp: Für jedes a [mm]\in[/mm] M gilt: Es gibt in P(M)
> genausoviele Mengen, die a enthalten, wie solche,
> die a nicht enthalten.
>
> Zu (i) hab ich:
>
> [mm]A(n)=2^n[/mm] ![[ok]](/images/smileys/ok.gif "[ok]")
>
> Zu (ii):
>
> Ja, denn wenn M die leere Menge enthält, ist P(M) = 1. ![[notok]](/images/smileys/notok.gif "[notok]")
Wenn [mm]M[/mm] die leere Menge enthält, ist [mm]P(M)[/mm] mindestens 2
Was du meinst, ist: "wenn M die leere Menge ist", also [mm]M=\emptyset[/mm]
> Also [mm]1=2^0[/mm] ist gleich also ist die Behauptung auch für M = [mm]\emptyset[/mm] gültig!
Aha, hier steht's richtig, wieso schreibst du dann oben solch einen Käse?
>
> Zu (iii):
>
> Mir ist zu (iii) leider noch nichts eingefallen könnte mir
> da einer weiterhelfen beim Ansatz?
Hier sollst du den Induktionsschritt [mm]n-1\to n[/mm] zeigen, dass also unter der Voraussetzng, dass die Potenzmenge einer [mm](n-1)[/mm]-element. Menge [mm]2^{n-1}[/mm] Elemente hat, zeigen, dass die Potenzmenge einer [mm]n[/mm]-element. Menge bitteschön auch [mm]2^n[/mm] Elemente enthält.
Nimm dir mal eine bel. Menge M mit n Elementen her, also [mm]|M|=n[/mm]
Etwa [mm]M=\{a_1,a_2,\ldots,a_{n-1},a_{n}\}[/mm]
Das kannst du schreiben als [mm]\{a_1,a_2,\ldots,a_{n-1}\}\cup\{a_{n}\}[/mm]
Nun hat die erste Menge n-1 Elemente, was sagt die Induktionsvoraussetzung dazu?
>
> Zum Tip:
>
> Kann mir einer sagen was der Tipp genau fürn Tipp ist und
> inwiefern mir der Tipp weiterhelfen soll?
Das sollte nun mit dem oben Gesagten in klarerem Licht erscheinen ...
> Irgendwie begreif
> ich nicht was das sagen soll!
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:03 So 24.10.2010 | | Autor: | Sax |
Hi,
die Aufgabe haben wir hier doch schon ausführlich diskutiert.
Gruß Sax.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:25 So 24.10.2010 | | Autor: | Blackpearl |
Da haben wir aber (iii) nicht.. :]
|
|
|
| |
|
Zunächst mal:
Was meint man mit "Wenn A(n-1) wahr ist." ??
Wahr heißt wenn auf beiden Seiten das gleiche Ergebnis kommt?
z.B.:
A(3)=2³ ; 9 = 9 ????
|
|
|
| |
|
Hallo nochmal,
> Zunächst mal:
> Was meint man mit "Wenn A(n-1) wahr ist." ??
> Wahr heißt wenn auf beiden Seiten das gleiche Ergebnis
> kommt?
Ja, man meint, dass die Aussage für n-1 gilt!
Das ist die Induktionsvaraussetzung und besagt, dass du für den Induktionsschritt [mm] $n-1\to [/mm] n$ voraussetzen kannst, dass für eine beliebige Menge $M$ mit $n-1$ Elementen gilt [mm] $|P(M)|=2^{n-1}$
[/mm]
Damit sollst du folgern, dass für eine bel. $n$-elementige Menge $M'$ die Potenzmenge $P(M')$ halt [mm] $2^n$ [/mm] Elemente hat, also [mm] $|P(M')|=2^n$
[/mm]
Einen Ansatz dazu habe ich oben hingeschrieben.
> z.B.:
> A(3)=2³ ; 9 = 9 ????
Gruß
schachuzipus
|
|
|
|
