 |
 |
 |
 |
 |
 |
Startseite » Forum » Vollständige Induktion beruht auf Annahme?
Vollständige Induktion beruht auf Annahme?
Universität / Fachhochschule
Sonstiges
Tags: Analysis, Annahme, Vollständig Induktion
 
|
  |
|---|
|
Liebe Community, der Ablauf der vollständigen Induktion lautet ja wie folgt: I Induktionsanfang . B. II Bei dem zweiten Schritt wird zuvor unterstellt gelte und das nennt man dann Induktionsannahme. Ich verstehe nicht wieso ich das annehme. Nehme ich das etwa an weil ja gilt? Das finde ich allerdings seltsam, weil wenn ich sage gilt, habe ich doch eigentlich eh schon was ich wollte... Das verwirrt mich alles sehr, ich hoffe jemand kann mich was das angeht aufklären. Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Du nimmst an, dass für EIN gilt und nicht dass es für alle gilt. Du zeigst also erst, dass wahr ist und dann dass falls für ein gilt, auch schon gilt. Insgesamt haben wir dann folgendes: Dass wahr ist haben wir gezeigt. Da wahr ist, folgt mit dem Induktionsschritt, dass auch wahr ist. Da nun wiederum wahr ist folgt wieder mit dem Induktionsschritt dass auch wahr ist. Und das zieht sich jetzt so weiter (das wird gerne als Dominoeffekt bezeichnet). Dass Induktionsanfang und Induktionsschritt beide notwendig sind, kann man sich auch an einfachen Beispielen überlegen. Dazu sei die Aussage, dass ist. Der Induktionsschritt gelingt hier, denn falls für ein erfüllt ist so folgt durch Addition der 1 auf beiden Seiten also ist dann auch wahr. Allerdings gelingt hier der Induktionsanfang nicht, da es keine natürliche Zahl mit gibt. Umgekehrt reicht der Induktionsanfang alleine natürlich auch nicht aus, das sollte auch ohne Beispiel klar sein. |
 |
|
Ich verstehe weiterhin nicht wieso ich plötzlich annehme, dass wahr ist. Soll es die direkte Folge daraus sein, dass wahr ist und somit für EIN (nämlich 1?) die Aussage gilt? |
|
|
|
Im Induktionsschritt zeigen wir die Implikation " Falls für ein gilt dann gilt auch " Wie ich oben anhand des Beispiels aufgezeigt hatte, reicht das alleine aber noch nicht aus, um zu zeigen, dass für alle wahr ist. Dafür müssen wir erst noch nachweisen, dass wahr ist, denn erst dann folgt mit dem Induktionsschritt dass auch wahr ist und damit wiederum etc. Mit dem Induktionsschritt kommst du also immer von einem Element zum nächsten. Und da du das öfters hintereinander anwenden kannst folgt die Aussage dann für jede natürliche Zahl. |
|
|
|
Vielleicht hilft es dir auch, das ganze mal von einem anderen Standpunkt zu sehen: Eigentlich zeigst du im Induktionsschritt dass die Aussageform unabhängig von wahr ist. Von Anfängern wird das gerne verwechselt mit dem Wahrheitsgehalt der Aussage (für ein festes ). Das ist aber falsch. Die Aussage (wieder für ein festes ) kann vollkommen unabhängig davon, ob wahr ist oder nicht wahr oder falsch sein. Um zu beweisen, dass unabhängig von wahr ist, zeigt man . Man kann also quasi zwei Fälle unterscheiden. Ist falsch, so ist sowieso wahr. Es bleibt also nur noch der Fall abzuhaken, wenn wahr ist. In diesem Fall muss dann noch gezeigt werden, dass wahr ist, was dann die einzige Möglichkeit ist, damit trotzdem noch wahr ist. Das "man nimmt an, dass gilt und zeigt dann, dass gilt", ist also weniger dass man denkt, man wisse, dass gilt, als mehr, dass man die Fälle " gilt" und " gilt nicht", beide überprüft und für beide Fälle den Wahrheitsgehalt der Aussage zeigen möchte. Für letzteren Fall ist nur ziemlich trivial, weswegen man diesen garnicht erst hinschreibt. |
|
|
|
Bei der vollständigen Induktion zeigt man, dass gilt und dass die Implikation gilt, daraus folgt dann, dass gilt. Es genügt also nebst lediglich zu zeigen, dass die Implikation gilt, das ist eventuell einfacher als direkt zu zeigen, dass gilt. Und die Implikation bedeutet: Wenn der Fall ist, dann ist der Fall man zeigt also nur, dass, wenn der Fall ist, dass dann der Fall ist, und nicht direkt, dass der Fall ist. |
|
|
|
Mir ist klar, dass wenn gilt, dann heißt das, dass prinzipiell jede natürliche Zahl geht. Was ich nicht verstehe ist, dass das eben nur stimmt wenn denn auch mein gilt. Das gilt nehme ich ja an, aber warum denn? Ich verstehe nicht wieso das ganze etwas beweisen kann, wenn es doch nur auf der Annahme fußt, dass richtig ist. |
|
|
|
Bei der vollständigen Induktion zeigt man nicht direkt, dass gilt, sonst hätte man ja bereits bewiesen, was man beweisen will - man will ja beweisen Man zeigt nebst nur, dass die Implikation gilt |
|
|
|
Ist das nicht das was ich sagte? Ok man zeigt das war ist, klar, verstehe. Man zeigt auch das falls denn die Aussage gilt, das die Aussage für jede natürliche Zahl gelten würde. Aber damit habe ich nicht die Aussage bewiesen, sondern nur gezeigt, dass falls sie denn stimmt, dass sie dann für alle natürlichen Zahlen gelten würde. Das heißt aber nicht, dass die Aussage wahr ist.. oder? |
|
|
|
Ja, man versucht nebst Folgendes zu zeigen: Falls denn stimmen würde, dann würde auch stimmen Ob oder tatsächlich stimmen, interessiert bei diesem Schritt nicht. |
|
|
|
Okay, aber ich dachte es ginge darum zu zeigen, dass eben stimmt... Folgt das irgednwie noch oder geht es bei der Induktion gar nicht darum zu zeigen, dass die Aussage stimmt. Das würde mich aber wundern weil die Aufgabenstellung doch immer ist, zu zeigen, dass stimmt, oder? Danke für die Hilfe soweit. |
|
|
|
Nö, da hast du mich jetzt falsch verstanden Wenn man zeigt, dass gilt, so "interessiert" man sich bei diesem Schritt nicht, ob oder gelten Insgesamt geht es bei der vollst. Ind. natürlich darum, zu zeigen, dass gilt, das ist natürlich Gegenstand des Interesses :-) |
|
|
|
Ja, das muss ich wohl falsch verstanden haben, es wird mir allerdings nicht klar, mit welchem Schritt ich die Aussage dann beweise. Wenn ich bei der Implikation zeige, dass ist, weiß ich nun, dass es eben falls gilt, auch für alle anderen gilt. Meine Aufgabenstellung heißt ja nun: Beweise, dass für alle gilt. Jetzt fehlt also noch der Beweis, dass überhaupt gilt. Wo kommt denn dann das? Ohne diesen Schritt wäre der Beweis ja unvollständig.. Sorry, dass ich das so kleinschrittig brauche, aber ich kapiere es einfach noch nicht :-D) Gebe mir aber größte Mühe |
|
|
|
nehmen wir an, wir haben nun gezeigt dass gilt, und dass die Implikation gilt Zu zeigen ist aber natürlich, dass gilt: also: gilt gilt aber auch, weil, da ja gilt, gilt auch und aber auch gilt, weil, da ja gilt, gilt auch und usw. somit gelten sie alle :-) |
|
|
|
Du sagst, dass usw. alle gelten und der Grund dafür liegt darin, dass die Implikation gilt. Die Implikation beruht aber nur auf der Annahme, dass (was ja zu beweisen ist!!) ja überhaupt so gilt. Wir drehen uns also irgendwie im Kreis. Ich beweise das ganze somit dadurch, dass ich bereits zuvor annehme, dass es stimmt. |
|
|
|
Die Implikation beruht nur darauf, dass gilt und das haben wir ja im Induktionsschritt gezeigt. Also gilt . Die Implikation beruht nun darauf, dass gilt und dass letzteres der Fall ist hatten wir uns ja gerade überlegt. Das Spiel kannst du nun ewig so weitertreiben und erschlägst alle natürlichen Zahlen. |
|
|
|
"Ich beweise das ganze somit dadurch, dass ich bereits zuvor annehme, dass es stimmt." Richtig, aber zuvor hast du es nur angenommen, dann aber bewiesen :-) und der Beweis ist wasserdicht :-) vielleicht dient auch das zur Veranschaulichung: de.wikipedia.org/wiki/Vollständige_Induktion |
|
|
|
@ Shipwater: "A(1) beruht nur darauf, dass gilt" nicht nur darauf, sondern auch darauf dass gilt . muss mich aber jetzt ausloggen . |
|
|
|
Aber ich kann doch keine Implikation einer nur als wahr angenommenen Aussage auf eine spezielle Aussage übertragen. Wenn ich nicht weiß ob die Aussage stimmt, weiß ich hintehrer auch nicht ob ihre Implikation stimmt.. und somit kann ich die Implikation nicht auf anwenden. Sagt mir meine innere Logik zumindest. |
|
|
|
@ Aurel: So war das nicht gemeint. Sondern wenn ich weiß dass wahr ist kann ich dann quasi folgern. Also was ich damit ausdrücken wollte: Um zu folgern, dass gilt reicht es zu wissen, dass gilt und man braucht eben nicht, dass für alle gilt. @ Pella: Aber du weißt doch, dass wahr ist! Du scheinst eine ziemliche Denkblockade zu haben. |
|
|
|
Eine Implikation wird - mathematisch unexakt - meist mit "aus A folgt B" beschrieben. Dem ist aber nicht so. läßt sich als wahr beweisen ( oder widerlegen ) UNABHÄNGIG davon, ob nun wahr oder falsch ist. Es gilt ja ( salopp hingeschrieben ist ist ist ist Da wir nun aber als wahr erkannt ( bewiesen, abgeleitet ) haben, fällt der 4. Fall weg. Es können also nur noch die Fälle und auftreten. Ist nun . falsch, dann kann ich über KEINE Aussage machen ( Fall und . Entweder war dann meine Vermutung falsch oder ich muss mir einen anderen "Startwert" suchen. Ist aber wahr, dann gilt NUR der Fall es muss dann auch wahr sein und das Spiel läßt sich fortsetzen. ( In den Vorlesungen wird meist folgendes Gleichnis gebracht: Wie kann ich eine Leiter hinaufklettern? Ich muss wissen, wie ich auf die ERSTE Sprosse gelange, und ich muss wissen, wie ich von JEDER BELIEBIGEN Sprosse auf die NACHFOLGENDE gelange. ) |
|
|
|
Ich verstehe leider noch nicht so ganz was du mit usw. sagen willst. Ich bin mir auch nicht sicher ob meine eigentliche Frage angekommen ist, deswegen versuch ich das nochmal deutlich klarzustellen: Die Induktion hat folgende Schritte: I. Induktionsanfang hier zeige ich, dass die Aussage für den kleinsten Wert der Menge stimmt II. Induktionsvoraussetzung ist wahr - ich gehe einfach davon aus das wahr ist Induktionsbehauptung ist auch wahr - bedarf keiner Erklärung Beweis der Behauptung - ich zeige, dass auch impliziert Falls es so ist, das impliziert, dann ist es klar, dass die Aussage für jedes gilt, eben nach dem Dominoprinzip. Mir ist auch klar, dass ich zeigen kann das impliziert OHNE, dass für den speziellen Fall überhaupt wahr sein muss. Aber genau da sehe ich auch das Problem. Wenn ich zeige das die Implikation gilt, wende ich sie einfach auf die Induktionsanfang an. Woher weiß ich aber, dass ich das tun darf? Denn impliziert zwar aber eben nur wenn wahr ist. Der Induktionsanfang ist ja ein spezialfall von und wenn ich nicht weiß ob gilt, was ich ja nicht bewiesen habe, sondern nur, dass es impliziert, dann weiß ich nicht ob die Implikation auch für einen Spezialfall von gilt. Oder gilt es deshalb weil das bei EIN spezielles ist und für ein spezielles kann man zeigen, dass unabhänging davon ob es wahr ist), impliziert.. und letztendlich sagt man dann, dass 1 ja ein spezielles ist und das ganze deshalb aufgeht? Fragen über Fragen... Sorry |
|
|
|
"Oder gilt es deshalb weil das n bei A(n) EIN spezielles n ist" Genau so ist es. Mir fällt aber auch gerade keine andere Interprätation ein. Wie hattest du das denn vorher gesehen? |
 |
|
Also jetzt im Nachhinein denke ich, dass das Problem der Formalismus ist mit dem das ganze definiert ist... Wenn ich jetzt sowas lese wie: I. Induktionsanfang II. gelte . usw Dann liegt schozn hier das Problem.. Weil es mir den wirklichen Inhalt, nämlich, dass es ja wahr ist, dass für EIN gilt (was ja wegen der Fall ist) vorenthält und wie aus dem nichts einfach behauptet, dass gilt. Wenn da jetzt also einfach nur steht: "A(n) gilt", bekommt man das Gefühl, dass es sich tatsächlich nur um eine aus der Luft gegriffene Behauptung handelt, die man einfach macht, damit das Prinzip aufgeht. Wenn man aber wörtlich sagt: "A(n) gilt für ein weil gilt und 1 ist ja ein spezielles n", dann ist das ganze glasklar.. Danke an jeden der geantwortet hat, Witzigerweise habe ich es am Ende durch die erste Antwort von Shipwater verstanden :-D) Dennoch waren alle anderen Antworten auch wichtig für den Verstehensprozess, insofern danke nochnmal, war alles sehr hilfreich! |
|
|
|
Hallo, vielleicht hilft es auch, die Verwirrung zu vermeiden durch Wahl der Variablen. Wenn die Aussage für zu beweisen ist, dann schreibe ich den Induktionsschritt mit einer anderen Variable auf: Ist natürlich mathematisch gesehen egal. Gruß pwm |
|
|
|
2 Punkte noch: . "Denn impliziert zwar aber eben nur wenn wahr ist" nein, man zeigt, dass impliziert, unabhängig, davon ob wahr ist das hattest du aber eigentlich hier schon akzeptiert: "Mir ist auch klar, dass ich zeigen kann das impliziert OHNE, dass für den speziellen Fall überhaupt wahr sein muss." . "Wenn da jetzt also einfach nur steht: "A(n) gilt", bekommt man das Gefühl, dass es sich tatsächlich nur um eine aus der Luft gegriffene Behauptung handelt" Man sagt eigentlich nicht: "A(n) gilt" sondern sinngemäß: man nimmt an, dass gelte Aus der Aussage "man nimmt an, dass gelte" folgt ohne weitere gesetzesförmige Aussagen aber nicht, dass (tatsächlich) gilt. Dass (tatsächlich) gilt, folgt aber daraus, dass und gelten (und natürlich weitere logische/ mathematische Axiome, deren Gültigkeit man unbewiesen voraussetzt) |
|
|
|
Hierzu möchte ich nochmal was fragen: "Man sagt eigentlich nicht: "A(n) gilt" sondern sinngemäß: man nimmt an, dass gelte" Man nimmt es an? ich habe es jetzt so verstanden, dass für EIN gilt, weil ja funktioniert. Die Schlussfolgerung ist doch korrekt oder? In meinen Augen ist es dann ja keine Annahme mehr.. eine Annahme darf es doch eigentlich auch nicht sein, weil Beweise ja nunmal nicht auf Annahmen beruhen sollten? |
|
|
|
Ich glaube du verstehst es immernoch leicht falsch. Deswegen mal ganz anders. Bei einem Beweis einer Aussage nimmt man einfach an, dass die Voraussetzung erfüllt ist. Beispiel: Stetige reellwertige Funktionen nehmen auf kompakten Mengen ihr Maximum als Funktionswert an. Will ich diese Aussage beweisen, so fange ich so an: Sei eine stetige reellwertige Funktion auf einem Kompaktum. Dann gilt: ... Ich könnte das ganze auch so machen: Sei die Aussage: "f ist eine stetige reellwertige Funktion auf einem Kompaktum" und die Aussage: "f nimmt sein Maximum als Funktionswert an". Ich möchte jetzt zeigen, dass die Implikation gilt. Also sage ich "Sei eine stetige reellwertige Funktion auf einem Kompaktum." Dann gilt .... und es folgt "f nimmt sein Maximum als Funktionswert an". Dass man das im Beweis so macht, hast du hoffentlich schon verstanden. Das ist aber anderes, als anzunehmen, dass gilt und daraus zu folgern. Obwohl natürlich klar ist, dass hier definitiv für alle gilt, können wir einfach annehmen, wir hätten ein , für das gilt. Dennoch weiß ich nun, dass einfach nur die Implikation richtig ist, auch wenn vielleicht für sehr viele selbst garnicht wahr ist. ist die Implikation wahr. Daraus folgt dann der Satz. Bei der vollständigen Induktion ist das ganz analog. Ich zeige unabhängig davon, ob wahr ist. Jetzt steht aber noch aus, dass damit auch für alle n wirklich gilt. Also gut, gib mir ein beliebiges , sagen wir 5. Ich weiß . Daraus kann ich aber alleine noch nicht folgern, dass gilt. Wenn aber zusätzlich noch gilt, dann muss es das, da sonst die Implikationskette nicht wahr wäre. Ansonsten wüsste ich nicht, wie man das noch erklären könnte. Vielleicht brauchst du einfach etwas Zeit, es sacken zu lassen. Im Moment hast du da vielleicht eine Art Blockade ;-) |
|
|
|
"Jetzt steht aber noch aus, dass damit auch für alle wirklich gilt. Also gut, gib mir ein beliebiges sagen wir 5. Ich weiß A(1)⇒A(2)⇒A(3)⇒A(4)⇒A(5). Daraus kann ich aber alleine noch nicht folgern, dass gilt. Wenn aber zusätzlich noch gilt, dann muss es das, da sonst die Implikationskette nicht wahr wäre." Das ist doch aber genau das was ich sagte, mit der Antwort bin ich sehr zufrieden |
1112181
1111832