Induktionsbeweis - Verständnisfrage

23.02.2020, 12:51

tweek

Auf diesen Beitrag antworten »

Induktionsbeweis - Verständnisfrage

Hallo Leute!

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

Zitat:

Original von tweek

Ich verstehe, dass man im Induktionsanfang einmal grundsätzlich die Richtigkeit für ein paar Fälle bestätigt.

Für einen einzigen reicht aus.

Zitat:

Original von tweek
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.

Dass aus der Richtigkeit von $\begin{eqnarray*} A_n \end{eqnarray*}$ auch die von $\begin{eqnarray*} A_{n+1} \end{eqnarray*}$ folgt, musst du ja gerade beweisen.
Wenn du die Aussage für $\begin{eqnarray*} A_1 \end{eqnarray*}$ gezeigt hast, dann folgt daraus auch dass sie für $\begin{eqnarray*} A_2 \end{eqnarray*}$ gilt und dann auch für $\begin{eqnarray*} A_3 \end{eqnarray*}$ 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!

Zitat:

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.

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

Zitat:

Original von sixty-fourDass aus der Richtigkeit von $\begin{eqnarray*} A_n \end{eqnarray*}$ auch die von $\begin{eqnarray*} A_{n+1} \end{eqnarray*}$ folgt, musst du ja gerade beweisen.

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

Zitat:

Original von tobitGezeigt 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.

OK, das macht Sinn. Dachte es wäre "perfekter". smile

smile

Danke für die Erklärung!

23.02.2020, 14:50

tobit

Auf diesen Beitrag antworten »

Hallo Elvis!

Zitat:

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.

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 »

Zitat:

Original von tobit
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

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!

Zitat:

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).

Ich denke, du meinst hier das richtige - aber es fehlt der "rekursive" Schritt in der Begründung, wie man von der Aussage $\begin{eqnarray*} A(1) \end{eqnarray*}$ auf alle anderen $\begin{eqnarray*} A(n) \end{eqnarray*}$ 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:

Zitat:

Wir haben bewiesen

Induktionsanfang: $\begin{eqnarray*} A(n_0) \end{eqnarray*}$ ist wahr für ein $\begin{eqnarray*} n_0\in\mathbb{N} \end{eqnarray*}$
Induktionsschritt: $\begin{eqnarray*} A(n)\Rightarrow A(n+1) \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq n_0 \end{eqnarray*}$

Beim Beweis des Induktionsschritts wissen wir noch nicht, ob $\begin{eqnarray*} A(n) \end{eqnarray*}$ wirklich wahr ist - wir müssen die Folgerung nur unter der Annahme hinbekommen, dass $\begin{eqnarray*} A(n) \end{eqnarray*}$ wahr ist!

Sobald wir aber beide Teile bewiesen haben, kann man $\begin{eqnarray*} n_0 \end{eqnarray*}$ in den Induktionsschritt einsetzen und danach den Induktionsschritt immer wieder für das nächstgrößere $\begin{eqnarray*} n \end{eqnarray*}$ anwenden - wir erhalten so die Aussagenkette

$\begin{eqnarray*} A(n_0)\Rightarrow A(n_0+1)\Rightarrow A(n_0+2)\Rightarrow A(n_0+3)\Rightarrow\ldots \end{eqnarray*}$

Damit ist die Aussage $\begin{eqnarray*} A(n) \end{eqnarray*}$ effektiv für alle $\begin{eqnarray*} n\geq n_0 \end{eqnarray*}$ bewiesen!

23.02.2020, 16:04

CrazyL

Auf diesen Beitrag antworten »

Zitat:

Im I-Anfang haben wir lediglich für einen Fall (oder mehreren, wie man lustig ist) deren Korrektheit geprüft

Mehrere Fälle beim Induktionsanfang (IA) braucht man nur, wenn der Induktionsschritt (IS) von "länger zurückliegenden" Aussagen $\begin{eqnarray*} A(n-k) \end{eqnarray*}$ 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
$\begin{eqnarray*} <br /> \text{Induktionsschritt:}\quad\bigl(A(n)\wedge A(n-2)\wedge A(n-3)\bigr)\quad\Rightarrow\quad A(n+1) \end{eqnarray*}$

Die am weitesten zurückliegende Aussage im IS ist $\begin{eqnarray*} A(n-3) \end{eqnarray*}$ , also muss man den IA für vier aufeinander folgende $\begin{eqnarray*} n_0-3,\ldots,n_0 \end{eqnarray*}$ 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 »

Zitat:

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,... wahr ist.

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 $\begin{eqnarray*} n\in\mathbb{N} \end{eqnarray*}$ schreibt, weil "..." schließlich alles bedeuten kann.

Die Darstellung von $\begin{eqnarray*} \mathbb{N} \end{eqnarray*}$ als Grenzwert endlicher Mengen $\begin{eqnarray*} \mathbb{N}=\lim_{N=1}^\infty\bigcup_{n=1}^N\{1;\ldots;N\}, \end{eqnarray*}$
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 $\begin{eqnarray*} \mathbb{N}=\lim_{N=1}^\infty\bigcup_{n=1}^N\{1;\ldots;\color{red}n\color{black}\} \end{eqnarray*}$

Überbertragen auf die Induktion: Diese Darstellung liefert, dass für jede natürliche Zahl $\begin{eqnarray*} n \end{eqnarray*}$ die Aussage $\begin{eqnarray*} A(n) \end{eqnarray*}$ durch endliche Anwendung des Induktionsschritts auf $\begin{eqnarray*} A(1) \end{eqnarray*}$ zurückgeführt werden kann. Jede Aussage der abzählbar unendliche Aussagenmenge $\begin{eqnarray*} \{A(n),\:n \in \mathbb{N}\} \end{eqnarray*}$ 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 $\begin{eqnarray*} A(n_0) \end{eqnarray*}$ .

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.

Zitat:

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.

Natürlich ist dieses Plausibel-Machen kein Beweis! Es sollte nur eine Erklärung sein, wieso das Induktionsaxiom sinnvoll ist.

Zitat:

Die vollständige Induktion macht einen Beweis für die unendliche Menge der natürlichen Zahlen möglich, und das in nur 2 Schritten.

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!!!)

Zitat:

diese Darstellung liefert, dass jede natürliche Zahl durch endliche Anwendung des Nachfolgeoperators auf 1 entsteht

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 $\begin{eqnarray*} 1\in \mathbb N \end{eqnarray*}$ im Bild der Nachfolgerfunktion $\begin{eqnarray*} S \end{eqnarray*}$ liegen. Beweis: $\begin{eqnarray*} (2=S(1), n+1=S(n))\Rightarrow \forall n\in \mathbb N\backslash \{1\}:n\in S(\mathbb N) \end{eqnarray*}$ 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. $\begin{eqnarray*} \forall n\in \mathbb N:n\in \mathbb N \end{eqnarray*}$ , $\begin{eqnarray*} \forall n\in \mathbb N:n=n \end{eqnarray*}$ ist trivial, da braucht man sie nicht.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »