Induktionsbeweis - Verständnisfrage |
23.02.2020, 12:51 | tweek | Auf diesen Beitrag antworten » | ||||||
Induktionsbeweis - Verständnisfrage Ich bin mit dem Induktionsbeweis an sich vertraut, allerdings hab ich noch eine grundlegende Unsicherheit beim Verständnis bzgl der Induktionsannahme. Nehmen wir diese einfache Erklärung als Grundlage: https://www.mathe-online.at/mathint/zahlen/i_ind.html Im Speziellen diese Aussage: Damit ist die Richtigkeit von An+1 - unter der Voraussetzung jener von An - gezeigt. Aus der (probeweise angenommenen) Richtigkeit einer der Aussagen folgt die Richtigkeit der nächsten! Ich verstehe, dass man im Induktionsanfang einmal grundsätzlich die Richtigkeit für ein paar Fälle bestätigt. Aber wie kann man in der Induktionsannahme diese Richtigkeit für An annehmen? n sind doch beliebige Zahlen! Diese Sicherheit hat man doch nicht. Und folgedessen kann man aus dieser fehlenden Sicherheit doch auch nicht auf die Richtigkeit von A(n+1) schließen. Wäre schön, wenn mir wer meinen Denkfehler aufzeigen könnte! Danke für Eure Mühen im Voraus! |
||||||||
23.02.2020, 13:13 | sixty-four | Auf diesen Beitrag antworten » | ||||||
RE: Induktionsbeweis - Verständnisfrage
Für einen einzigen reicht aus.
Dass aus der Richtigkeit von auch die von folgt, musst du ja gerade beweisen. Wenn du die Aussage für gezeigt hast, dann folgt daraus auch dass sie für gilt und dann auch für und immer so weiter. |
||||||||
23.02.2020, 13:17 | Elvis | Auf diesen Beitrag antworten » | ||||||
Das Prinzip der vollständigen Induktion ist ein Axiom für die natürlichen Zahlen. Man kann es benutzen, um Dinge rekursiv zu definieren und um Aussagen für alle natürlichen Zahlen zu beweisen. Richard Dedekind hat die vollständige Induktion auf eine universelle Eigenschaft der natürlichen Zahlen zurückgeführt, nämlich auf den Rekursionssatz, den er bewiesen hat. |
||||||||
23.02.2020, 14:09 | tobit | Auf diesen Beitrag antworten » | ||||||
RE: Induktionsbeweis - Verständnisfrage Hallo tweek!
Gezeigt werden soll im Induktionsschritt nur: Für jede natürliche Zahl n gilt: WENN A(n) gilt, dann gilt auch A(n+1). (*) Es wird also gar nicht behauptet, dass man sich hier über den Wahrheitswert von irgendwelchen A(n) sicher sein könne oder man aus dem erfolgreich bewiesenen Induktionsschritt A(n+1) für irgendwelche natürlichen Zahlen n folgern könne. Beispiel: Sei A(n) jeweils die (natürlich in diesem Fall falsche) Aussage n>n. Nun können wir (*) zeigen: Sei n dazu eine natürliche Zahl. Wir müssen zeigen: Wenn A(n) gilt, gilt auch A(n+1). Wenn A(n) gilt, dann haben wir n>n gilt und es folgt durch Addition von 1 auf beiden Seiten der Ungleichung n+1>n+1, also A(n+1). Damit ist (*) für dieses Beispiel völlig korrekt bewiesen. Natürlich ist trotzdem für keine natürliche Zahl n die Ungleichung n>n richtig. Und der Versuch einer vollständigen Induktion würde hier am Induktionsanfang scheitern. Wenn man eine Aussage der Form "Wenn B gilt, dann gilt auch C." beweisen möchte, tut man dies typischerweise dadurch, dass man B als wahr annimmt und unter dieser Annahme C zeigt. Dies funktioniert unabhängig davon, ob B tatsächlich wahr oder falsch ist. Diese Beweisstrategie nutzt man üblicherweise auch zum Nachweis von (*) im Rahmen der vollständigen Induktion (mit B:=A(n) und C:=A(n+1)). Ich freue mich über Feedback und Rückfragen! :-) Viele Grüße Tobias |
||||||||
23.02.2020, 14:24 | Elvis | Auf diesen Beitrag antworten » | ||||||
Die vollständige Induktion auf eine falsche Aussage anzuwenden, ist sinnlos. Man beweist damit nicht die Wahrheit der Aussage, und dass sie falsch ist, ist sowieso klar. |
||||||||
23.02.2020, 14:35 | tweek | Auf diesen Beitrag antworten » | ||||||
RE: Induktionsbeweis - Verständnisfrage
Das ist mir klar. Die Verwirrung herrscht, warum An - in ihrer Form als unbewiesene Formel - dafür heranzuziehen ist. Klar, A1 stimmt. Aber An steht ja nicht nur für n=1, sondern für quasi alle natürlichen Zahlen. In meiner momentanen Denkweise, benutze ich also einen unbewiesene Formel (An) um damit deren Korrektheit zu beweisen. |
||||||||
Anzeige | ||||||||
|
||||||||
23.02.2020, 14:36 | tweek | Auf diesen Beitrag antworten » | ||||||
RE: Induktionsbeweis - Verständnisfrage
OK, das macht Sinn. Dachte es wäre "perfekter". Danke für die Erklärung! |
||||||||
23.02.2020, 14:50 | tobit | Auf diesen Beitrag antworten » | ||||||
Hallo Elvis!
Mein Anliegen war keineswegs, "vollständige Induktion auf eine falsche Aussage anzuwenden" (was auch immer du damit genau meinst) als hilfreiches Mittel zur Lösung mathematischer Probleme darzustellen. Viele Grüße Tobias |
||||||||
23.02.2020, 14:57 | tobit | Auf diesen Beitrag antworten » | ||||||
Hallo tweek, nur zur Klarstellung: Die Kombination aus Induktionsschritt, Induktionsanfang und Induktionsaxiom der natürlichen Zahlen lässt natürlich schon auf die Gültigkeit von A(n) für alle natürlichen Zahlen n schließen. (Und genau dieser Schluss ist ja der Sinn eines Induktionsbeweises.) Lediglich der Induktionsschritt für sich genommen ist davon relativ unabhängig, ob A(n) für alle natürlichen Zahlen n gilt oder nicht. Viele Grüße Tobias |
||||||||
23.02.2020, 15:00 | tweek | Auf diesen Beitrag antworten » | ||||||
Ich glaub ich hatte das trotzdem noch immer falsch verstanden, denke aber nun tatsächlich eine Lösung gefunden zu haben. Könntest du mal drüberlesen und mich ggf korrigieren? Mein Problem war es, eine allgemeine Aussage wie An (die es ja erst zu beweisen gilt) als Grundlage für den Beweis zu akzeptieren. Im I-Anfang haben wir lediglich für einen Fall (oder mehreren, wie man lustig ist) deren Korrektheit geprüft. Dass man An nun trotzdem verwenden darf, liegt in dem Argument, dass An ja genauso gut für A1 stehen kann! (?) Wenn es dann in genereller Form (also mit n und n+1) für die nächste Zahl bewiesen werden kann, stimmt es für alle Zahlen (da es ja auch für 1 (n) und 2 (n+1) gilt). Bisschen schwer nachzuvollziehen, aber ich hoffe ich hab es verständlich rübergebracht. |
||||||||
23.02.2020, 15:21 | tobit | Auf diesen Beitrag antworten » | ||||||
Hallo tweek, ich bin nicht ganz sicher, ob du das richtige meinst, könnte aber gut sein. Ich formuliere es nochmal in meinen Worten: Nehmen wir an, wir haben gezeigt: A(1) gilt. (Induktionsanfang) Für alle natürlichen Zahlen n gilt: Wenn A(n) gilt, dann auch A(n+1). (Induktionsschritt) Dann gilt A(1) nach Induktionsanfang. Gemäß Induktionsschritt angewandt auf n=1 erhalten wir: Wenn A(1) gilt, dann auch A(2). Also gilt A(2). Gemäß Induktionsschritt angewandt auf n=2 erhalten wir: Wenn A(2) gilt, dann auch A(3). Also gilt A(3). Gemäß Induktionsschritt angewandt auf n=3 erhalten wir: Wenn A(3) gilt, dann auch A(4). Also gilt A(4). Gemäß Induktionsschritt angewandt auf n=4 erhalten wir: Wenn A(4) gilt, dann auch A(5). Also gilt A(5). Usw. Deshalb sagt das Induktionsaxiom der natürlichen Zahlen: Wir können auf A(n) für alle natürlichen Zahlen n schließen. Ich finde es übrigens sehr gut, dass du die Logik verstehen willst und hinterfragst, anstatt blind ein Schema zu befolgen. :-) Viele Grüße Tobias |
||||||||
23.02.2020, 15:36 | CrazyL | Auf diesen Beitrag antworten » | ||||||
Edit: Tut mir leid, tobit war schneller!
Ich denke, du meinst hier das richtige - aber es fehlt der "rekursive" Schritt in der Begründung, wie man von der Aussage auf alle anderen kommt. Die vollständige Induktion ist eigentlich eine Aussagenkette - am Besten kann man sich das graphisch klar machen. Um ganz sicher zu gehen, nochmal die Voraussetzungen:
Sobald wir aber beide Teile bewiesen haben, kann man in den Induktionsschritt einsetzen und danach den Induktionsschritt immer wieder für das nächstgrößere anwenden - wir erhalten so die Aussagenkette Damit ist die Aussage effektiv für alle bewiesen! |
||||||||
23.02.2020, 16:04 | CrazyL | Auf diesen Beitrag antworten » | ||||||
Mehrere Fälle beim Induktionsanfang (IA) braucht man nur, wenn der Induktionsschritt (IS) von "länger zurückliegenden" Aussagen abhängt. Das Problem hat man manchmal bei rekursiven Folgen höherer Ordnung, wie der Fibonacci-Folge. Dann kann der IS z.B. so aussehen Die am weitesten zurückliegende Aussage im IS ist , also muss man den IA für vier aufeinander folgende durchführen. Gute Übung: Versuche, die Aussagenkette für das Beispiel aufzuzeichnen! |
||||||||
24.02.2020, 07:23 | Elvis | Auf diesen Beitrag antworten » | ||||||
Es genügt nicht, dass eine Aussage A(n) für n=1,2,3,... wahr ist. Es genügt nicht, dass eine Aussage A(n) für n=1,2,3 usw. wahr ist. Es genügt nicht, die Wahrheit einer Aussage A(n) anhand eines endlichen Abschnitts der natürlichen Zahlen oder eines (endlichen) Bildes plausibel zu machen. Die vollständige Induktion macht einen Beweis für die unendliche Menge der natürlichen Zahlen möglich, und das in nur 2 Schritten. Unendlich ist unendlich viel mehr als endlich, erst wenn man das verstanden hat, weiß man die vollständige Induktion zu schätzen und kann verstehen, wie sie funktioniert und warum sie notwendig ist. |
||||||||
24.02.2020, 09:14 | CrazyL | Auf diesen Beitrag antworten » | ||||||
Ist das nicht gerade die Aufgabe, die man mit der vollständigen Induktion erledigen will - zumindest laut "Analysis 1, Königsberger, 6. Edition, S.1"? Auch wenn man statt "n=1,2,3,..." natürlich besser schreibt, weil "..." schließlich alles bedeuten kann. Die Darstellung von als Grenzwert endlicher Mengen folgt doch direkt aus den Peano-Axiomen - und diese Darstellung liefert, dass jede natürliche Zahl durch endliche Anwendung des Nachfolgeoperators auf 1 entsteht - oder liege ich auch hier falsch? |
||||||||
24.02.2020, 09:42 | CrazyL | Auf diesen Beitrag antworten » | ||||||
Edit: Ich meinte natürlich Überbertragen auf die Induktion: Diese Darstellung liefert, dass für jede natürliche Zahl die Aussage durch endliche Anwendung des Induktionsschritts auf zurückgeführt werden kann. Jede Aussage der abzählbar unendliche Aussagenmenge kann also durch eine Aussagenkette endlicher Länge bewiesen werden - wir müssen also eine abzählbar unendliche Menge von Aussagenketten endlicher Länge beweisen (und diesen komplizierten Satz versteht man meiner Meinung nach besser durch die Graphik mit den Folgepfeilen). Durch "globalen Shift aller Indizes" erhält man die Form mit dem Induktionsanfang . Falls mit dieser Erklärung ebenfalls etwas falsch ist, dann löscht bitte alle Posts von mir zu dem Thema - ich will hier schließlich niemanden verwirren! Oder noch besser - erklärt dem OP/mir, warum die Erkärung falsch/nicht präzise genug ist! |
||||||||
24.02.2020, 10:46 | tobit | Auf diesen Beitrag antworten » | ||||||
@Elvis: Ich scheine dein Anliegen noch nicht richtig verstanden zu haben.
Natürlich ist dieses Plausibel-Machen kein Beweis! Es sollte nur eine Erklärung sein, wieso das Induktionsaxiom sinnvoll ist.
Hier habe ich einzuwenden, dass die vollständige Induktion keineswegs die einzige Methode ist, eine Aussage über alle natürlichen Zahlen zu zeigen. Beispielsweise ist der Induktionsschritt auch eine Aussage über alle natürlichen Zahlen, die üblicherweise ohne vollständige Induktion gezeigt wird. @CrazyL: (ACHTUNG: Dieser Abschnitt ist NICHT für Anfänger gedacht!!!)
Entgegen landläufiger Meinung muss im Rahmen der Mengenlehre ZFC für eine Menge natürlicher Zahlen gemäß der Peano-Axiome keineswegs gelten, dass jede natürliche Zahl dieser Menge durch im intuitiven Sinne endliche Anwendung des Nachfolgeoperators auf 0 bzw. 1 entsteht. Es kann durchaus "Nichtstandardzahlen" geben, also "natürliche" Zahlen, die größer sind als als jede "intuitive" natürliche Zahl. |
||||||||
24.02.2020, 11:40 | Elvis | Auf diesen Beitrag antworten » | ||||||
@CrazyL Das Axiom der vollständigen Induktion ist ein Axiom der Dedekind-Peano-Axiome für die natürlichen Zahlen. Ja, daraus folgt, dass alle natürlichen Zahlen ausser der im Bild der Nachfolgerfunktion liegen. Beweis: qed @tobit Vollständige Induktion ist ein wesentliches Hilfsmittel, um Beweise zu führen, in denen Aussagen über natürliche Zahlen vorkommen. Sicher ist es nicht das einzige Beweismittel, um Aussagen über natürliche Zahlen zu beweisen. , ist trivial, da braucht man sie nicht. |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
Die Neuesten » |
|