Prinzip der Induktion beweisen < Induktion < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 19:41 Di 07.11.2017 | | Autor: | magics |
| Aufgabe | Es sei $A(n)$ für $n [mm] \in \IN$ [/mm] eine unendliche Folge von Aussagen. Es gelte
(i) $A(1)$ ist wahr und
(ii) $A(k) [mm] \Rightarrow [/mm] A(k+1)$ für alle $k [mm] \in \IN$.
[/mm]
Dann ist $A(n)$ wahr für alle $n [mm] \in \IN$ [/mm] .
Führen Sie den Beweis durch Widerspruch. |
Der Beweis durch Widerspruch sieht wie folgt aus:
Ich treffe die Annahme, dass die Schlussfolgerung "Dann ist $A(n)$ wahr für alle $n [mm] \in \IN$ [/mm] " falsch ist. Dann muss es ein kleinstes $j [mm] \in \IN$ [/mm] geben für das $A(j)$ nicht erfüllt ist. Wegen der Voraussetzung (i) muss dieses $j > 1$ sein. $A(j-1)$ muss demnach wahr sein. Mit (ii) folgt, dass auch $A(j)$ wahr sein muss. Und das steht im Widerspruch zur Annahme.
Ich komme mit bis zu der Stelle, an der wir sagen, dass wegen (i) $j > 1$ sein muss, denn das können wir durch einsetzen nachprüfen.
Aber danach wird die zweite Aussage (ii) als Begründung herangezogen, dass die Aussage des Widerspruchbereises falsch ist. Wieso darf ich eine Aussage in meiner Beweisführung verwenden, die ich an sich nicht bewiesen habe?
Niemand garantiert mir, dass $A(k) [mm] \Rightarrow [/mm] A(k+1)$ für alle $k [mm] \in \IN$ [/mm] korrekt ist. Bei (i) konnte ich es wenigstens direkt durch einsetzen zeigen.
lg
Thomas
|
|
| |
|
Hallo,
(i) und (ii) nimmst du an. Dass daraus folgt, dass A(n) für alle n gilt, möchtest du beweisen. Die Annahmen dürfen dabei natürlich zur Anwendung kommen bzw. das müssen sie sogar streng genommen.
Der Widerspruch entsteht ja durch die Annahme, A(j) sei falsch und j die kleinste natürliche Zahl für die das der Fall ist. Und zwar eben dadurch, dass du auf die wahre Aussage A(j-1) den Induktionsschluss (ii) anwendest.
Das wichtigste an diesem Beweis ist aber IMO etwas ganz anderes: wieso darfst du annehmen, dass es ein kleinstes j mit [mm] \neg [/mm] A(j) gibt? Es ist die Eigenschaft der Wohlordnung der natürlichen Zahlen. Diese besagt eben, dass jede Teilmenge von [mm] \IN [/mm] ein kleinstes Element besitzt.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:24 Mi 08.11.2017 | | Autor: | fred97 |
> Hallo,
>
> (i) und (ii) nimmst du an. Dass daraus folgt, dass A(n)
> für alle n gilt, möchtest du beweisen. Die Annahmen
> dürfen dabei natürlich zur Anwendung kommen bzw. das
> müssen sie sogar streng genommen.
>
> Der Widerspruch entsteht ja durch die Annahme, A(j) sei
> falsch und j die kleinste natürliche Zahl für die das der
> Fall ist. Und zwar eben dadurch, dass du auf die wahre
> Aussage A(j-1) den Induktionsschluss (ii) anwendest.
>
> Das wichtigste an diesem Beweis ist aber IMO etwas ganz
> anderes: wieso darfst du annehmen, dass es ein kleinstes j
> mit [mm]\neg[/mm] A(j) gibt? Es ist die Eigenschaft der Wohlordnung
> der natürlichen Zahlen. Diese besagt eben, dass jede
> Teilmenge von [mm]\IN[/mm] ein kleinstes Element besitzt.
Hallo Diophant,
Das Induktionsprinzip ist äquivalent zum Satz vom kleinsten Element.
>
>
> Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:46 Mi 08.11.2017 | | Autor: | Diophant |
Hallo Fred,
> > Das wichtigste an diesem Beweis ist aber IMO etwas ganz
> > anderes: wieso darfst du annehmen, dass es ein kleinstes j
> > mit [mm]\neg[/mm] A(j) gibt? Es ist die Eigenschaft der Wohlordnung
> > der natürlichen Zahlen. Diese besagt eben, dass jede
> > Teilmenge von [mm]\IN[/mm] ein kleinstes Element besitzt.
>
> Hallo Diophant,
>
> Das Induktionsprinzip ist äquivalent zum Satz vom
> kleinsten Element.
>
Das macht Sinn. In S. Lang, Algebraische Strukturen ist die Begründung aber genau so, wie ich sie hier wiedergegegeben habe (zumindest in der deutschen Ausgabe). Und dieses Buch hatte ich im Hinterkopf.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:04 So 12.11.2017 | | Autor: | magics |
Hallo Diophant,
ich wollte mich nochmal bedanken. Mit deiner Antwort, über die ich ein paar Tage gegrübelt und die ich mit in die VL genomnen habe, konnte ich etwas anfangen.
In meiner bildlichen Vorstellung habe ich zumindest verstanden, dass das Prinzip im Wiederverwenden der Annahme ein Schlüssel darstellt.
lg
Thomas
|
|
|
| |
|
Hallo Thomas
Für diese Beweisaufgabe müsste im Voraus bekannt bzw.
vorgegeben sein, auf welche Grundannahmen (Axiome)
man sich für den Beweis stützen darf.
Leider liegt aber keine derartige Angabe vor. Oder war
bei euch z.B. im Vorfeld dieser Aufgabe vom Wohlordnungssatz
für die Menge der natürlichen Zahlen die Rede ?
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:52 Mi 08.11.2017 | | Autor: | Diophant |
Hallo,
> Für diese Beweisaufgabe müsste im Voraus bekannt bzw.
> vorgegeben sein, auf welche Grundannahmen (Axiome)
> man sich für den Beweis stützen darf.
Darum geht es dem Fragesteller aber nicht.
> Leider liegt aber keine derartige Angabe vor. Oder war
> bei euch z.B. im Vorfeld dieser Aufgabe vom
> Wohlordnungssatz
> für die Menge der natürlichen Zahlen die Rede ?
Es schadet nie, eine Frage komplett durchzulesen. Denn im Prinzip geht es dem Fragesteller darum, dass er eine gegebene Voraussetzung, nämlich dass [mm] A(k)\Rightarrow{A(k+1)} [/mm] gilt, verwenden soll und Zweifel daran äußert, ob bzw. wieso er das darf. Das kann man ohne jedes Axiom mit der Begründung klären, dass die Gültigkeit dieser Implikation angenommen werden soll (nach Aufgabenstellung).
Ganz nebenbei muss dann auch noch die Frage auf 'teilweise beantwortet' gestellt werden (was in der Zuständigkeit der Moderation läge), so dass man hier einmal mehr den Verdacht gewinnen muss, dass du hier nicht der Sache wegen mitmachst, sondern um Wirbel zu veranstalten oder dich wichtig zu machen.
Gruß, Diophant
|
|
|
| |
|
---> Diophant
Leider war ja irgendwie zu erwarten, dass du gleich wieder
was zu motzen hast, wenn ich hier wieder mal was melde.
Ehrlich verstehe ich aber einfach nicht, was du an mir oder
an meinem Beitrag (und auch früheren) auszusetzen hast.
Offenbar sollte es ja bei der Aufgabe darum gehen, "das Prinzip
der vollständigen Induktion zu beweisen".
Wie du bestimmt weißt und wie auch Fred mitgeteilt hat,
ist dies nicht möglich, denn das Prinzip der v.I. ist eines
der Axiome von Peano und lässt sich nicht auf "einfachere"
logische Grundlagen zurückführen. Die einzige Möglichkeit
ist es, das PdvI auf ein gleichwertiges Axiom (wie z.B. das
Prinzip der Wohlordnung) zurückzuführen. Deshalb wäre
dieses andere Axiom als Grundlage für einen "Beweis"
anzugeben. Genau darauf, und auf nichts anderes, wollte
ich hinweisen.
Al-Chw.
|
|
|
|
