Vollständige Induktion

[Toadesstern]

Realtiv kurze Frage, will nur wissen, ob das, was ich mache auch erlaubt ist. Ich vermute, dass es das nicht ist aber an der Aufgabe zerbeiße ich mir grad irgendwie die Zähne weil ich keine Gescheite Induktionshypothese formuliert kriege... (den Rest krieg ich dafür aber hin, auch die anderen Induktionsbeweise )

Aufgabe: Beweise, dass die Anzahl A(n) aller Teilmengen einer Menge mit n elementen = 2^n ist

Problem hier ist, dass ich wie gesagt keine gescheite Induktionshypothese formuliert kriege. Im Normallfall habe ich ja links ne Formel/Hypothese, dann rechts ne Formel, mache den Induktionsanfang, dann den schritt, dann setze ich die hypothese ein und komme über umformungen auf das richtige Ergebnis.
Soviel zur theorie.
Was ich nun hier stehen habe ist folgendes:
I.H.: A(n) = 2^n
I.A.: 2^0 = 1 (M1:={} hat keine elemente + leere Menge, also 1 Element)
I.S.: 2A(n) = 2^(n+1) (weil die Anzahl elemente sih ja verdoppelt hat)
=> 2^n * 2, mit I.A. einsetzen und ich habe => A(n) * 2 => 2A(n)=2A(n)

Problem hier wie gesagt, dass ich keine (imo?) ordentliche Hypothese habe sondern A(n) eben auch hier verändern muss. Schaut irgendwie so aus als ob ich hier bewiesen habe, dass wenn man die linke hälfte mit 2 multipliziert und die rechte auch, dass es dann immernoch das selbe ist
Wenn ich aber nicht mit A(n) als I.H. arbeite habe ich ka was die I.H. sonst sein sollte, bzw komme eben auf 2 A(n) da es ja auch logischerweiße doppelt so viel Elemente wie "vorher" gab

€: Was mir gerade eingefallen ist, ich könnte als I.H. natürlich schreiben A(n+1) = 2*2^2 = 2^(n+1) aber das ist ja letztendlich das selbe, nur dass ich versuche meinen trivialen beweis von "man kann auf beiden seiten mit 2 multiplizieren" zu verschleiern

 

[mfb]

Du willst die Induktion sicher über n machen.

Für n ist also die Aussage A(n)=2^n.
Wie ist die gleiche Aussage für (n+1)? Kannst du sie mit Hilfe der Aussage der Zeile darüber beweisen?
Das ist nicht alleine mit Rechnen möglich, du brauchst die Definition von A(n) und musst mit Mengen rumarbeiten.


>> 2A(n) = 2^(n+1)
Das ist nur eine triviale Folgerung aus A(n) = 2^n.

 

[Brusko651]

Hoi,

das hier ist halt eine Mengentheoretische Aussage. Dementsprechend kommst du beim Induktionsbeweis auch nicht nur mit algebraischen Umformungen von irgendwelchen Gleichungen aus, sondern musst auch Mengen betrachen.

Die Induktionsbehauptung ist schon gut.
A(n) = 2^n
Also, eine Menge mit n Elementen besitzt 2^n Teilmengen.

Und jetzt musst du dir halt überlegen: Wenn ich zu dieser n-elementigen Menge, noch ein Element dazu gebe, was für Teilmengen kann ich dann bilden?
kleiner Tipp:
Die ganzen Teilmengen von der n-elementigen Menge sind natürlich auch noch immer Teilmengen von der n+1 elementigen Menge. Neu dazu kommen also die Teilmengen, wo das neue n+1-te Element dabei ist.

Nützlich ist auch, die Sache erstmal anhand von einem konkreten Beispiel zu betrachten:
Wenn n=2 ist, dann hätten wir zB die Menge {1,2}, die 2 Elemente hat.
Und die Teilmengen sind:
{} , {1} , {2} , {1,2} (das sind 2²=4 Teilmengen)
Eine Menge mit n=3 Elementen wäre zB die Menge {1,2,3}.
Die hat die Teilmengen:
{} , {1} , {2} , {1,2}, {3} , {1,3} , {2,3} , {1,2,3}

 

[Toadesstern]

Du willst die Induktion sicher über n machen.

Für n ist also die Aussage A(n)=2^n.
Wie ist die gleiche Aussage für (n+1)? Kannst du sie mit Hilfe der Aussage der Zeile darüber beweisen?
Das ist nicht alleine mit Rechnen möglich, du brauchst die Definition von A(n) und musst mit Mengen rumarbeiten.


>> 2A(n) = 2^(n+1)
Das ist nur eine triviale Folgerung aus A(n) = 2^n.

Das mein "Ergebnis" nur eine triviale Folgerung ist ist mir bewusst. Ist halt Ana-1 und Rechenregeln aus Axiomen beweisen, von daher denkt man bei vielem, dass es eigentlich trivial ist und ich war mir nicht sicher ob es trivial trivial ist oder trivial nicht so trivial
Problem ist halt, dass ich keine Definition von A(n) habe. Mir ists bewusst, dass für n die Aussage A(n) = 2^n lautet und für n+1 die Aussage 2A(n) = 2^(n+1) [rein vom Ergebnis her]. Mir ist aber nicht bewusst wieso.
Ich habe atm (glaube ich?) keine Definition. Würde mal vermuten, dass es irgendwo bei Potenzmengen eventuell was passendes gibt? Das würde ich dann eventuell in LA finden. Also für einfache Zahlen (0,1,2) ist mir die Lösung bewusst aber wenns mehr gibt und ich "testen" will ob 2^n denn auch stimmt muss ich da mim stift und nem papier hingehen und es ausprobieren, was ja wohl nicht Sinn der Sache ist

€: Gerade die ersten paar Zeilen von Brusko gelesen... darauf hätte man selbst kommen können
€2: Also würde mal sagen, wenn ich nen n habe (scheiß egal was) kann ich die Teilmengen von n+1 bilden indem ich n (formal n+1 - 1 weil ich n+1 habe aber die leere menge in beiden vorkommt wodurch ich auf n komme?) neue Teilmengen mache. Eben zu jeder Teilmenge vom "alten" n mit dem element n+1 kombinieren, right?

 

[Brusko651]

€2: Also würde mal sagen, wenn ich nen n habe (scheiß egal was) kann ich die Teilmengen von n+1 bilden indem ich n (formal n+1 - 1 weil ich n+1 habe aber die leere menge in beiden vorkommt wodurch ich auf n komme?) neue Teilmengen mache. Eben zu jeder Teilmenge vom "alten" n mit dem element n+1 kombinieren, right?

jo, nicht ganz. Also du fügst zu jeder Teilmenge einer n-elementigen Menge noch das neue Element hinzu und erhältst dadurch 2^n Teilmengen.
Dabei wird durchaus auch die leere Menge verwendet, weil wenn du zur leeren Menge das neue Element hinzufügst, dann erhältst du ja auch eine neue Teilmenge, nämlich die, die nur das neue Element enthält.
(dazu am besten nochmal das Beispiel mit n=2 und n=3 anschaun ^^)
Insgesamt ergeben sich also für eine n+1-elementige Menge 2^n + 2^n Teilmengen.

Den Satz kann man übrigens auch ohne vollständige Induktion sehr anschaulich verstehen:
Wenn du eine Teilmenge von einer n-elementigen Menge M bildest, dann musst du ja zu jedem einzelnen Element von M entscheiden, ob es in der Teilmenge enthalten sein soll, oder nicht.
Du triffst also n "ja/nein"-Entscheidungen. Und dadurch ergeben sich 2^n Möglichkeiten, eine Teilmenge zu bilden.

 

[Toadesstern]

ok habe es denke ich verstanden, Problem an der Sache ist nun, dass es mehr nen Aufsatz ist als sonst was. Wie gesagt, ist Ana-1 und NICHT La-1. Folglich ist dieser Beweis für 2^n+2^n eigentlich was was ich wohl irgendwann demnächst in LA machen werde (oder auch nicht...). Allerdings brauche ich ihn als Vorraussetzung für die Aufgabe.

Ich würde da jetzt hingehen und das, was ich jetzt verstanden habe da hin schreiben. Sprich ich hab meine Induktion à la:
A(n) + A(n) = 2(n+1) => 2^n * 2 => A(n) *2 => A(n) + A(n)
(wobei ich mir nicht sicher bin ob wir 2^n = 2*2^(n-1) als Rechenregel schon bewiesen haben, das muss ich eventuell dann auch noch beweisen, sollte aber np sein)

und würde mit nem etwas längeren Satz erklären wie sich die Teilmengen zusammensetzen und dass ich für n+1 eben auf A(n) + A(n) komme da A(n+1) ja eben die "alten" Elemente + die Vereinigung der alten (jedes einzeln) mit dem "neustem" Element ist und da man eben in M(n) A(n) Elemente hat gibt es nur A(n) neue Kombinationen.
Zählt sowas? Oder muss / kann ich das irgendwie formal mit Vereinigungsdreck mathematisch hinschreiben, obwohl ich in Ana sitze und nicht in LA?
€: Wobei vergiss es, wenn es machbar ist das "richtig" zu zeigen und es mit meinem Wissensstand schon möglich ist krieg ichs auch alleine hin. Wenn nicht geh ich zur Sprechstunde und frag ob das nötig ist

 

[Brusko651]

(wobei ich mir nicht sicher bin ob wir 2^n = 2*2^(n-1) als Rechenregel schon bewiesen haben, das muss ich eventuell dann auch noch beweisen, sollte aber np sein)

das gilt eigentlich direkt nach der Definition von "2^n" so.
Also a^n wird normalerweise so rekursiv definiert:
* a^0 = 1
* und a^n = a^(n-1) * a für alle n € N.

Dass dein Beweis mehr Text als mathematische Symbole und so zeugs ist, sollte kein Problem sein. Es ist durchaus üblich, dass mathematische Beweise nicht nur aus "=>" und "+" usw. bestehen, sondern dass man viele Dinge einfach als Sätze ausschreiben muss.

Das ganze wirklich formal stichfest aufzuschreiben ist natürlich ein bisschen mühsam. Es geht wahrscheinlich eh nur um die "general idea"

Aber du solltest nicht einfach irgendwelche Gleichungen hinschreiben, und dann erst danach erklären, wie du darauf kommst, sondern alles schön der Reihe nach aufschreiben.

Also ich würds so in der Art aufschreiben:

[....]
Induktionsschritt:
Sei M={a_1, a_2, .... , a_n, a_n+1 } eine n+1 elementige Menge. Dann ist M\{a_n+1} eine n-elementige Menge, und hat also nach Induktionsbehauptung 2^n Teilmengen. Diese sind natürlich auch Teilmengen von M. Zusätzlich ergeben sich noch 2^n Teilmengen von M indem man zu jeder Teilmenge von M\{a_n+1} noch das Element a_n+1 hinzufügt.
Insgesamt hat M also 2^n + 2^n = 2* 2^n = 2^(n+1) Teilmengen., fertig.

Das ist natürlich kein 100% stichfester Beweis, weil ich habe ja nicht wirklich bewiesen, dass das auch wirklich ALLE Teilmengen von M sind. Vielleicht gibt es ja noch mehr. Aber gefühlsmäßig wissen wir, dass das alle sind, und ich wüsste jetzt nicht, wie man das besser machen soll, ohne wirklich in einen Roman auszuufern.

 

[Toadesstern]

jo eben.

Zum a^n Teil: Ich meine mich zu erinnern, dass es ne Rechenregel ausm Forster sei, die irgendwie bewiesen sei und aus Axiomen hergeleitet wird, aber wenn das von dir geschriebene echt die Definition ist, dann wird die ja wohl auch so im Forster stehen und ich kann zumindest "=> (nach M.*Nummerierung* Forster)" schreiben und es belegen

Und ja. Auf meinem Block sieht es so aus, dass ich erst die Induktion habe, dann den Text, dann um den Text nen rießen block gemacht habe und ihn via Pfeil über die Induktion geschoben habe. Habe einfach wiedergegeben, was ich mir zusammengekritzelt habe, natürlich geb ichs so nicht ab und bring es in die richtige Reihenfolge

Aber danke dann für die schnelle Hilfe. Wie schon gesagt, normalerweiße würde ich nicht so früh nach Hilfe fragen, haben die Aufgaben erst heute gekriegt, aber wenn ich schon die Hypothese in Frage stelle und meine Lösung damit in Frage stelle macht es recht wenig Sinn darüber nachzudenken ob der Rest überhaupt richtig ist von daher wollte ich da einfach kurz nachhaken wie man da grundsätzlich rangehen soll.

 

[sesslor]

War vielleicht schon da, aber die Induktionshypothese ist einfach
A(n+1) = 2 A(n).

Du hast alle Telmengen von M(n), jetzt nimmst du ein Element dazu. Da die Teilmengen nur dadurch definiert sind, welche Elemente sie enthalten, gibt es zwei Moeglichkeiten, neue Teilmengen von M(n+1) zu konstruieren, entweder das neue Element ist drin oder nicht.

 

[SvenGlueckspilz]

War vielleicht schon da, aber die Induktionshypothese ist einfach
A(n+1) = 2 A(n).

Nein, das ist der Teil, der im Induktionsschluß zu zeigen ist.
Die Induktionshypothese ist A(n) = 2^n

 

[sesslor]

Nein, das ist der Teil, der im Induktionsschluß zu zeigen ist.

Ach so, ich dachte man bezeichnet das als Induktionshypothese. Der zu beweisende Satz hat ja mit der Induktion nichts mehr zu tun.