Vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 20:00 Do 21.10.2010 | | Autor: | Blackpearl |
| Aufgabe | Aufgabe 1:
Beweisen Sie mit vollständiger Induktion, dass für endliche
Mengen M gilt
[mm]|P(M)| = 2^{|M|}[/mm].
(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. |
Hey Leute,
davon hab ich mal echt noch weniger als 0-Ahnung. Ich hatte noch nie vollständige Induktion! Wie soll ich bitte was beweisen? Was könnt ich jetzt machen? Hat einer Ansätze/Lösungen die mir weiterhelfen? Muss den stuss bis Montag abgeben hätte nie gedacht das er direkt son keks bringt!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:09 Do 21.10.2010 | | Autor: | ChopSuey |
Hi,
keine Ahnung wer "er" ist, aber wenn du von der vollst. Induktion wirklich keinen blassen Schimmer hast, warum dann nicht informieren?
Dazu gibt es unzählige Seiten die das ausführlich erklären. Oder man schaut in sein Skript.
Falls du konkrete Fragen hast, kann man dir auch helfen.
Viele Grüße
ChopSuey
|
|
|
| |
|
[mm]$ |P(M)| = 2^{|M|} $[/mm]
Was heißt das auf der rechten Seite eigentlich? Warum 2?
|
|
|
| |
|
Zu (i):
[mm]A (n) = 2^n[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:07 Do 21.10.2010 | | Autor: | M.Rex |
Hallo
Wenn du A(q) als Anzahl der Elemente der Potenzmenge einer q-elementigen Menge M definierst, stimmt das
Marius
|
|
|
| |
|
Die Aufgabe war ja:
(i) Formulieren Sie die Behauptung als eine von n abhängige Aussage A(n), wobei n = |M|
gilt.
Und du sagst, "wenn". Also ist meine Formulierung im jetzigen Zustand falsch?
Wie definiere ich denn A(q) als Anzahl der Elemente der Potenzmenge einer q-elementigen Menge M?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:22 Do 21.10.2010 | | Autor: | M.Rex |
Hallo
> Die Aufgabe war ja:
> (i) Formulieren Sie die Behauptung als eine von n
> abhängige Aussage A(n), wobei n = |M|
> gilt.
>
> Und du sagst, "wenn". Also ist meine Formulierung im
> jetzigen Zustand falsch?
Nein, das war alles korrekt, du solltest eben nur noch sagen, was A(n) in diesem Fall ist.
>
> Wie definiere ich denn A(q) als Anzahl der Elemente der
> Potenzmenge einer q-elementigen Menge M?
Einfach per Definition Hinschreiben. Also in etwa so:
Sei A(q) als Anzahl der Elemente der Potenzmenge einer q-elementigen Menge M. Dann gilt [mm] A(q)=2^{q}
[/mm]
Marius
|
|
|
| |
|
Zu (ii):
Nein, denn wenn M die leere Menge ist, dann haben wir auf der linken Seite 0 und [mm] 0 = 2^0[/mm] ist nicht gleich also eine falsche Aussage.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:13 Do 21.10.2010 | | Autor: | M.Rex |
Hallo
Hier musst du aufpassen.
Die Leere Menge $ [mm] \emptyset [/mm] $ hat n=0 Elemente, die Potenzmenge [mm] P(\emptyset) [/mm] hat aber wieviele Elemente?
Marius
|
|
|
| |
|
Also wenn [mm] M=\emptyset [/mm] ist ist [mm] P(\emptyset) [/mm] immernoch M UND [mm] \emptyset? [/mm] Oder wie war das?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:26 Do 21.10.2010 | | Autor: | M.Rex |
> Also wenn [mm]M=\emptyset[/mm] ist ist [mm]P(\emptyset)[/mm] immernoch M UND
> [mm]\emptyset?[/mm] Oder wie war das?
Nein. In der Potenzmenge einer Jeden Menge M ist sowohl M als auch die Menge M selber enthalten.
Schreib dir für deinen Fall [mm] M=\emptyset [/mm] mal P(M) auf. Das ist wirklich nicht viel 
Marius
|
|
|
| |
|
Das geht mir wieder nicht ganz in den Schädel.. die Frage ist:
"Gilt die Behauptung auch für M = [mm] \emptyset [/mm] ?"
Dann schreibe ich? >
> > Also wenn [mm]M=\emptyset[/mm] ist ist [mm]P(\emptyset)[/mm] immernoch M UND
> > [mm]\emptyset?[/mm] Oder wie war das?
> Schreib dir für deinen Fall [mm]M=\emptyset[/mm] mal P(M) auf. Das
> ist wirklich nicht viel
>
> Marius
Meinst du vielleicht:[mm]
P(M) := \{ \emptyset | \emptyset \subseteq M\} [/mm]??
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:09 Fr 22.10.2010 | | Autor: | M.Rex |
Hallo.
Wahrscheinlich meinst das richtige, hast dich aber durch einen Notationsfehler verwirren lassen. Innerhalb der Mengenklammern haben Mengenrelationen erstmal nichts zu suchen.
Es gilt: [mm] P(\emptyset)=\{\emptyset\}.
[/mm]
Also hat die Potenzmenge der leeren, also 0-elementigen Menge wieviele Elemente? Und gilt dann [mm] A(0)=2^{0} [/mm] ?
Marius
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:54 Fr 22.10.2010 | | Autor: | Blackpearl |
Also:
A(2)=2²
Zählt die leere Menge als ein Element? Davon geh ich ma aus.
Wenn nicht dann halt nur die Menge M also: [mm] A(1)=2^1
[/mm]
danke dir erstma marius :O ich mach mich erstma an die letzte aufgabe ran.. vielleicht packt mein kopf das heute nacht noch..^^
|
|
|
| |
|
Also müsste es vollständig heißen:
Nein, denn A(2)=2²
2=4 ist nicht wahr also ist die behauptung bei [mm] M=\emptyset [/mm] nicht richtig`?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:47 Fr 22.10.2010 | | Autor: | M.Rex |
Hallo
Wie kommst du auf die A(2) für die leere Menge?
[mm] \emptyset [/mm] ist leer, also 0-elementig.
[mm] |\emptyset|=|\{\}|=0
[/mm]
Also gilt für die Potenzmenge
[mm] |P(\emptyset)|=|\{\emptyset\}|=1=2^{0}
[/mm]
Marius
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:42 Fr 22.10.2010 | | Autor: | Blackpearl |
Ja, jetzt hab ichs begriffen.. man muss halt lange dahinter hängen..^^
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:34 Fr 22.10.2010 | | Autor: | Sax |
Hi,
ich war heute in meiner Lieblingspizzeria bei Alfredo und ich werde jetzt mal versuchen dir zu erklären, wieso mich seine Speisekarte an deine Aufgabe erinnert.
Alle seine Pizzen werden zunächst mit Tomaten und Käse belegt, das ist nichts besonderes. Dann hat Alfredo in seiner Küche eine Zutatenliste, aus der er gewisse Extrabeläge auswählen kann, um sie auf seine Pizzen zu legen. Je nach Auswahl erfindet er klangvolle Namen für seine Kreation und schreibt die in seine Speisekarte für die Gäste.
Hier ist ein Ausschnitt aus seiner Speisekarte :
Pizza Margerita : mit Tomaten und Käse und sonst nichts
Pizza Funghi : mit Tomaten, Käse und Pilzen
Pizza Salami : mit Tomaten, Käse und Salami
Pizza PrimaDonna : mit Tomaten, Käse und Pilzen und Schinken
Pizza Don Alfredo : mit Tomaten, Käse und Salami und Schinken und Gurke
...
(das und sonst nichts habe ich eingefügt)
Der Zusammenhang mit deiner Aufgabe ist nun folgender :
Die Zutatenliste entspricht der Menge M, die komplette Speisekarte entspricht der Potenzmenge P(M) (was "komplett" bedeuten soll erkläre ich gleich). Jede Pizza auf der Speisekarte entspricht einer bestimmten Auswahl an Extrabelägen, d.h. einer Teilmenge von M. Wenn man alle möglichen Teilmengen von M betrachtet, erhält man die "Menge aller Teilmengen", das ist die Potenzmenge von M. Dem entsprechen alle möglichen Kombinationen von Extrabelägen, also alle möglichen Pizzen, eben die in diesem Sinne komplette Speisekarte.
Die Anzahl möglicher Extrabeläge (also wie viele Zutaten Alfredo zur Verfügung stehen) ist die Anzahl der Elemente von M (man nennt das auch die "Mächtigkeit" von M) und dafür wird |M| geschrieben.
Die Aufgabe besteht nun darin, zu untersuchen, wie viele Pizzen auf einer kompletten Speisekarte stehen, wenn Alfredo 5 (oder 7 oder 0 oder allgemein |M|) Zutaten zur Auswahl hat, d.h. gesucht ist die Mächtigkeit der Potenzmenge, also |P(M)|.
Machen wir ein paar Beispiele :
Wenn Alfredo gar keinen Extrabelag mehr hat (d.h. M = [mm] \emptyset [/mm] , |M| = 0), so kann er doch immerhin noch Pizza Margerita anbieten (allerdings auch keine andere), die komplette Speisekarte hat einen Eintrag, |P(M)| = 1. Mathematiker schreiben dafür [mm] P(\emptyset) [/mm] = { [mm] \emptyset [/mm] }
Wenn Alfredo Artischocken hat (M = {a}), stehen auf seiner Speisekarte zwei Pizzen, nämlich Pizza Margerita und Pizza Berlusconi (die mit Artischocken) : P(M) = {Margerita, Berlusconi} = { [mm] \emptyset [/mm] , {a} }
Wenn Alfredo zwei Zutaten hat, Artischocken und Bananen ( M = {a , b} ), dann kann er jetzt schon vier Pizzen anbieten, nämlich Margerita, Berlusconi, Vesuvo (die mit Banane) und Cäsar (die mit Artischocken und Banane) P(M) = {Margerita, Berlusconi, Vesuvo, Cäsar} = { [mm] \emptyset [/mm] , {a} , {b} , {a,b} }
So hatte also Alfredo seine Zutatenliste, seine Gäste hatten die Speisekarte, alle waren glücklich und zufrieden. Da tauchte eines Tages ein Fremder auf, der eine exotische Zutat mitbrachte, von der keiner je zuvor etwas gehört hatte : Eisbein. Er verlangete, dass Eisbein auf die Zutatenliste gesetzt wird. Dadurch wurde [mm] |M_{alt}| \to |M_{neu}| [/mm] = [mm] |M_{alt}|+1 [/mm] . Wie veränderte sich der Umfang der Speisekarte also |P(M)| ? Die alten Pizzen konnten natürlich bleiben, aber zusätzlich konnten diese außerdem auch noch mit Eisbein belegt werden, es gab also jetzt doppelt so viele Pizzen wie vorher : [mm] |P(M_{alt})| \to |P(M_{neu})| [/mm] = [mm] 2*|P(M_{alt})|. [/mm] Jede neue Zutat verdoppelt den Umfang der Speisekarte, wenn M ein Element mehr erhält, verdoppelt sich die Mächtigkeit seiner Potenzmenge.
Mächtigkeit von M | 0 1 2 3 4 5 n
|
Mächtigkeit von P(M) | 1 2 4 8 16 32 [mm] 2^n [/mm]
So beweist man, dass |P(M)| = [mm] 2^{|M|} [/mm] ist.
Zusatz für Viertsemester : Eines Tages kam der Teufel in die Pizzeria und verlangte, dass auch Pizzen als Belag auf Pizzen zugelassen sein sollten.
Pizza Diavolo sollte die Pizza Diavolo als Belag enthalten ...
Da wandte sich Alfredo an seinen Freund Bertrand um Rat. Bertrand schlug ihm vor, doch zunächst mal nur solche Pizzen anzubieten, die sich selbst nicht als Belag enthalten, solche Pizzen seien doch harmlos . Als Belohnung für seinen Ratschlag sagte Bertrand : "Dafür machst du mir jetzt bitte eine "Pizza Ultima", das ist die Pizza, die alle harmlosen Pizzen als Belag enthält." Alfredo hat Bertrand nie wieder seinen Freund genannt.
Gruß Sax.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:41 Fr 22.10.2010 | | Autor: | Blackpearl |
Das Beispiel ist einfach hammer..^^ Danke. :D
Erst hab ich mir einen abgelacht. Aber absolut verständlich, danke dir für den Aufwand! :]]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:59 Fr 22.10.2010 | | Autor: | fred97 |
.
>
> Da wandte sich Alfredo an seinen Freund Bertrand um Rat.
> Bertrand schlug ihm vor, doch zunächst mal nur solche
> Pizzen anzubieten, die sich selbst nicht als Belag
> enthalten, solche Pizzen seien doch harmlos . Als Belohnung
> für seinen Ratschlag sagte Bertrand : "Dafür machst du
> mir jetzt bitte eine "Pizza Ultima", das ist die Pizza, die
> alle harmlosen Pizzen als Belag enthält." Alfredo hat
> Bertrand nie wieder seinen Freund genannt.
>
> Gruß Sax.
.......... und Bertrand hat sich dann mit anderen Dingen ![[]](/images/popup.gif) beschäftigt ...................
Hallo Sax,
Respekt, ein toller Artikel !
Gruß FRED
|
|
|
|
Potenzmenge![[]](http://upload.wikimedia.org/wikipedia/commons/d/da/Russellelection1907.jpg){kind=small}
beschäftigt