Vollständige Induktion: Wieso kein Zirkelschluss?

07.02.2020, 21:08	nuriell	Auf diesen Beitrag antworten »
Vollständige Induktion: Wieso kein Zirkelschluss? Hallo, nachfolgend mein erster Beitrag: Mich beschäftigt die Frage, warum die vollständige Induktion nicht als Zirkelschluss gilt. Im Induktionsschritt wird die Induktionsbehauptung für n+1 ja aufgestellt unter Anwendung der Induktionsvoraussetzung. Die Induktionsvoraussetzung selbst ist aber doch garnicht bewiesen, so dass dann die Beweisführung für n+1 zirkulär sein müsste. Oder wo liegt mein Denkfehler? Danke für eure Hilfe.
07.02.2020, 22:23	Elvis	Auf diesen Beitrag antworten »
Die natürlichen Zahlen sind nach Dedekind eine Kette, d.h. sie fangen mit 1 an und werden dann durch die injektive Nachfolgerfunktion erzeugt. (A(1) und A(n) ==> A(n+1)) ==> A(n) für alle n ist kein Zirkelschluss. Die vollständige Induktion ist nach Dedekind eine Folge des Rekursionssatzes. In einfachen Worten : (A(1) und A(1)==>A(2))==>A(2),(A(2) und A(2)==>A(3))==>A(3),... Der logische Schluss von n auf n+1 ist offenbar jeweils der Modus ponens. Dieser ist seit der Antike nicht als zirkulaer verdächtig.
08.02.2020, 18:06	Antezedenz	Auf diesen Beitrag antworten »
RE: Vollständige Induktion: Wieso kein Zirkelschluss? Vielleicht verstehe ich dein Problem - ich versuche eine informelle Erklärung: Tatsächlich wird die Aussage für n im Induktionsschritt nicht bewiesen, sondern die Folgerung, dass sie auch für n+1 wahr ist unter der Annahme, dass sie für n wahr ist. Deshalb braucht man ja auch den Induktionsanfang - es muss tatsächlich gezeigt werden, dass es überhaupt eine natürliche Zahl gibt, für die die Aussage wahr ist. Hat man eine solche Zahl gefunden, dann gilt zusammen mit dem gültigen Induktionsschrift, dass die Aussage auch für die folgende natürliche Zahl wahr ist, und für die darauf folgende natürliche Zahl, usw. ad infinitum. Nur Induktionsanfang und Induktionsschritt zusammen ergeben eine gültige Beweisführung.
08.02.2020, 18:41	Leopold	Auf diesen Beitrag antworten »
Man kann den Beitrag von Antezedenz schön an einem Beispiel demonstrieren. Behauptung: $\begin{align} \sum_{k=1}^n k = \frac{1}{2} \left( n + \frac{1}{2} \right)^2 \end{align}$ für alle $\begin{align} n \geq 1 \end{align}$ Für $\begin{align} n+1 \end{align}$ statt $\begin{align} n \end{align}$ lautet die Behauptung: $\begin{align} \sum_{k=1}^{n+1} k = \frac{1}{2} \left( n + \frac{3}{2} \right)^2 \end{align}$ Wir führen den Induktionsschritt durch, nehmen also an, daß die Behauptung für $\begin{align} n \end{align}$ gilt: $\begin{align} \color{red} \sum_{k=1}^n k = \frac{1}{2} \left( n + \frac{1}{2} \right)^2 \end{align}$ Und unter dieser Annahme rechnen wir: $\begin{align} \sum_{k=1}^{n+1} k = \color{red} \left( \sum_{k=1}^n k \right) \color{black} + (n+1) = \color{red} \frac{1}{2} \left( n + \frac{1}{2} \right)^2 \color{black} + (n+1) = \frac{1}{2} n^2 + \frac{1}{2} n + \frac{1}{8} + n + 1 = \frac{1}{2} n^2 + \frac{3}{2} n + \frac{9}{8} \end{align}$ $\begin{align} = \frac{1}{2} \left( n^2 + 3n + \frac{9}{4} \right) = \frac{1}{2} \left( n + \frac{3}{2} \right)^2 \end{align}$ Der Induktionsschritt war damit erfolgreich. Dennoch ist die Behauptung falsch.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »