Diskussion:Vollständige Induktion

Häufige Fehler

Bei "Häufige Fehler" wird eine schöne Formel gezeigt. Durch mein "Vorwissen" habe ich in der rechten Formel "+7" erkannt.

Zitat: Falls diese Behauptung für ein n gelten würde, dann würde sie auch für n + 1 gelten! Da sie aber für kein n gilt, ist sie falsch! Zitat-Ende

Und woher WEIß ich das, das sie für kein n gilt?

Danke für die Erklärung. LG Lisa

Ich habe es ein wenig umformuliert. Der Induktionsbeweis ist falsch, wenn man kein n für den Induktionsanfang angibt. Die Aussage könnte trotzdem richtig sein, auch wenn der Beweis falsch ist. Dass die Aussage im konkreten Fall tatsächlich falsch ist, muss man aber tatsächlich mit anderen Mitteln zeigen (beispielsweise indem man die korrekte Formel angibt und zeigt, dass sie niemals gleich der angegebenen falschen Formel ist). --NeoUrfahraner 21:46, 2. Sep 2006 (CEST)

Was ist eine "unvollständige" Induktion?

Habe das bisher noch nicht gehört und kann mir nichts darunter vorstellen. Was wäre dann der Unterschied einer unvollständigen Induktion und einer vollständigen Induktion?

Wo steht denn was von "unvollständiger" Induktion? --NeoUrfahraner 22:41, 23. Aug 2006 (CEST)

Habe ich auch schon gehört, aber verstehe es nicht. LG Lisa

Hilft http://www.phillex.de/u-indukt.htm weiter? --NeoUrfahraner 21:50, 2. Sep 2006 (CEST)

Was ist den nun die korrekte Form?

Hier wird angegeben:

  1. Induktionsanfang
  2. Induktionsvoraussetzung
  3. Induktionsschritt

In der Schule habe ich:

  1. Induktionsanfang
  2. Induktionsvoraussetzung
  3. Induktionsschluss

Im Duden-Schülerhilfe-Aufbau des Zahlensystems, vollständige Induktion finde ich:

  1. Induktionsanfang
  2. Induktionsschluss
  2a. Induktionsvoraussetzung
  2b. Induktionsbehauptung
  2c. Induktionsschritt

Der Beginn heißt normalerweise Induktionsverankerung, weil am ersten Schritt die ganze Sache wie an einem Anker hängt. Den Begriff der Induktionsvoraussetzung kenne ich nicht, wundert mich auch, da es keine Voraussetzung sondern eine Annahme ist. Wenn ich annehme, dass die Sache für n gilt, gilt sie dann auch für n+1? Voraussetzungen können wahr oder falsch sein, Annahmen werden als wahr unterstellt, mit dem Ziel den Wahrheitsgehalt später im Beweisverfahren zu verifizieren oder zu falsifizieren.

--Dompfaf 22:14, 6. Jun 2006 (CEST)

"Verankerung" klingt für mich nach Kuschelpädagogik.--Gunther 22:19, 6. Jun 2006 (CEST)

--Soviel dazu, das Mathe eindeutig ist, nun gibt es schon vier verschiedene Bezeichnungen für das Selbe. *kopfschüttel* --Warum muss jeder sein eigenes Brötchen backen bzw. das Rad neuerfinden??? *verwundertschau*

--Ich schlage vor, Bezeichnungen ähnlich derer aus dem Duden-Schülerhilfe zu verwenden. Die Voraussetzung/Behauptung (Hier sehe ich keinen Unterschied, sodass meiner Meinung nach einer von beiden Punkten ausreicht. Ich empfehle "Voraussetzung", da die Aussage (für ein gewisses n) mit dem Induktionsanfang schon bewiesen ist.) macht als eigenständigen Punkt keinen Sinn. Erst zusammen mit dem Schritt/Schluss erhält er Bedeutung. Da die Begriffe I-Schritt und I-Schluss häufig das selbe meinen, denke ich, man sollte nur einen angeben oder beide synonym verwenden. Etwa so:

  1. Induktionsanfang
  2. a) Induktionsvoraussetzung
     b) Induktionsschluss/-schritt

Zumindest besser als die aktulle Bezeichnung ist die Duden-Version ohne Schritt 2b.

Bedingungen genauer mit Beispiel erklären

Hallo, ist es möglich, die Bedingungen der VI genauer zu erklären? Hier sollte man den genauen Unterschied einer "mangelhaften" Induktion und der vollständigen Induktion erkennen. In dem Bereich werden auch viele Denkfehler gemacht. Ich zum Beispiel. Danke, LG Kirsten.

Ich denke ein einfaches Beispiel wie z.B. die Summe der natürlichen Zahlen von 1 bis n sollte genügen. Die Summe der ungeraden Zahlen als weiteres Beispiel trägt nach meiner Meinung wenig zum Verständnis bei. Es fragt sich was mit diesem Beispiel eigentlich ausgesagt werden sollte. Der Beweis durch Induktion erscheint mir in diesem Fall nicht besonders elegant. Ich würde in diesem Beispiel die Berechnung unter Verwendung der Formel für die Summe der Zahlen 1 bis N vorziehen. Auch die Summenformel für die ersten N natürlichen Zahlen lässt sich auch einfach ohne Verwendung der vollständigen Induktion beweisen. Die Summe der Zahlen von 1 bis 100 ist (1+100) + (2+99) + ... + (50+49) = 51*50 = N*(N+1)/2. Bei einer geraden Zahl an Summanden kann entsprechendend dieses Prinzips immer die größste und die kleinste Zahl zusammengefasst werden. Bei einer ungeraden Anzahl kann die Null als weiterer Summand aufgenommen werden. Die Induktion ist also meist nicht die einzig möglich Beweismethode.

Die Gaußsche Herleitung ist sicher intuitiv, aber ist sie auch mathematisch rigoros als Beweis zu verstehen, oder muß ihre allgemeine Gültigkeit nicht selber (durch Induktion!) bewiesen werden?

Die jetzt gemachte Ergänzung erläutert zwar, warum es funktioniert, ist aber kein Nachweis, dass es sich um einen mathematisch rigorosen Beweis handelt (sprich, um eine Argumentationskette, die nur (möglicherweise indirekt) auf den Axiomen der natürlichen Zahlen beruht).

Genauer: Für jeden einzelnen Fall ist es unmittelbar einsichtig, daß diese Umordnung der Summanden durchgeführt werden kann und dieses Ergebnis liefert. Aber kann man die allgemeine Aussage (diese Umordnung zu konstanten Summanden ist für jedes n möglich) auch streng mathematisch ohne Induktion beweisen? --Ce 19:04, 30. Nov 2003 (CET)

Ich denke, diese Umordnung ist kein mathematisch strenger Beweis. Die Begründung des Satzes durch die Umordnung ist ein Fall von Induktion im logischen Sinne, d.h. der Schluss vom speziellen aufs allgemeine. Innerhalb unserer Mathematik ist das aber kein Beweis. Ein Beweisverfahren ist dagegen die deduktive (!) Methode der vollständigen Induktion (auf diese Namensverwirrung sollte man vllt. auch mal eingehen).

In diesem Sinne wäre also ein Nachweis, dass die Umordnung stets möglich ist, wiederum nur durch vollständige Induktion möglich. --SirJective 19:17, 30. Nov 2003 (CET)

Also, die Frage ist hier letztlich, wo man die Trennlinie zu dem zieht, was man als bekannt voraussetzen darf. Es geht bei 1 + ... + n nicht um eine Reihensumme mit unendlich vielen Gliedern, wo das Umordnen von Gliedern in der Tat mit Vorsicht angegangen werden müßte. Daß man hingegen endlich viele Summanden der Zahlenreihe 1 + ... + n ohne Änderung des Ergebnisses beliebig umordnen und zusammenfassen kann, egal, welchen konkreten Wert n gerade hat, ergibt sich aus den Axiomen der Addition (Kommutativität und Assoziativität). Diese sind zwar nur für zwei bzw. drei Summanden formuliert. Ich meine, daß es fast schon komisch ist, hier die beliebige Vertauschbarkeit und Zusammenfaßbarkeit von endlich vielen Summanden in der Form eines exakten Beweises aufzuschreiben, obwohl dies möglich ist. Ich meine, wer Spaß daran hat, kann es für sich einmal beweisen und dabei vollständige Induktion anwenden. Da die Axiome für die natürlichen Zahlen eigentlich nur so praktische Erfahrungen wie die beliebige Vertauschbarkeit und Zusammenfaßbarkeit von endlich vielen Summanden in eine einfache Form bringen sollen, würde man an der Stelle genau genommen nur beweisen, daß die Axiome eine gelungene Vereinfachung der Beschreibung dessen sind, was man nur beobachten, aber nicht beweisen kann. Zusammengefaßt meine ich also, daß man Gauß' Herleitung der Summenformel für die natürlichen Zahlen bis 100 analog als strengen gültigen Beweis für die Summe bis n ohne vollständige Induktion akzeptieren kann und muß. Die beliebige Kommutativität und Assoziativität von endlich vielen Summanden wird bei diesem Beweis meiner Meinung nach zu recht vorausgesetzt. Ich stimme zu, daß ein Beweis, der für eine konkrete Zahl (hier: 100) erbracht wurde, nicht ohne weiteres auf beliebige Zahlen n verallgemeinert werden kann. In diesem Fall ist es aber so, daß die allgemeine Betrachtung für n genauso wie für die konkrete Zahl 100 angestellt werden kann, da es sich bei n immer um eine endlich große Zahl handelt. Da der Beweis so für ein allgemeines n geführt werden kann, gilt er auch für jedes n. - 212.202.53.9 - 05.12.2003

Die Gausssche Begruendung ist eine schoene, einfache und gut verstaendliche. Jedoch sehe ich gerade nicht, wie z.B. die Aussage "Die Summe der Zahlenpaare wird zu n+1 und die Anzahl der Zahlenpaare [wird] zu n/2" rein logisch gefolgert werden koennte. Dies ist mMn jedoch noetig, um von einem mathematischen Beweis sprechen zu koennen. Denn der hat bitteschoen innerhalb des Axiomensystems zu bleiben. Die Vertauschbarkeit endlich vieler Summanden kann man selbstverstaendlich als bekannt voraussetzen, da liegt auch nicht mein Problem. Mir bereitet die Stelle Kopfzerbrechen, an der auf die Summe und die Anzahl der Zahlenpaare geschlossen wird, nicht die Existenz der Umordnung und Gleichwertigkeit zur urspruenglichen Reihenfolge. Da hab ich den Satz im Artikel wohl falsch geschrieben:

...wenn sichergestellt ist, dass die beschriebene Umordnung der Zahlen und Addition der Paare für jede natürliche Zahl n möglich ist und das angegebene Ergebnis liefert

Die Umordnung und Addition ist natuerlich moeglich, fraglich ist nur, warum das angegebene Ergebnis herauskommt. --SirJective 10:29, 5. Dez 2003 (CET)

Der Satz soll doch nur ein (etwas langatmiges) Beispiel für die Beweistechnik der vollständigen Induktion sein. Daher gehört die nette Geschichte vom kleinen Gauss IMHO nicht in diesen Artikel. Der axiomatische Aufbau des Zahlensystems wurde ja erst später entwickelt. Heizer 23:04, 5. Dez 2003 (CET)

Gauss hat die Summanden keineswegs umgeordnet. Seine Idee: Er hat die Summe 2 mal untereinander geschrieben, zuerst vorwärts, dann rückwärts. Danach hat er die beiden Zeilen spaltenweise addiert:

s(n)      =   1   +   2   + ... + (n-1) +  n         vorwärts
s(n)      =   n   + (n-1) + ... +   2   +  1         rückwärts
-----------------------------------------------
s(n)+s(n) = (n+1) + (n+1) + ... + (n+1) + (n+1)      Addition

Daraus ergibt sich sofort 2·s(n) = n (n+1) und daraus dann die Summenformel.
Das ist in dem Artikel m.E. etwas unglücklich dargestellt. -- tsor 23:41, 5. Dez 2003 (CET)

Sehr schön. Auf diese Weise ist das Verfahren viel klarer.

Es ist auch klarer zu sehen, an welcher Stelle es "haken" könnte:

Wie beweist man ohne Induktion, dass in der unteren Summe unabhängig von n alle Summanden gleich (n+1) sind? --Ce 19:59, 6. Dez 2003 (CET)

Es handelt sich jeweils um endlich viele Summanden, und es gibt eine eineindeutige Zuordnung zwischen den Summanden der oberen und der unteren Reihe.

Der i-te Summand der oberen Reihe ist i; der i-te Summand der unteren Reihe ist (n+1)-i. Dies folgt direkt aus der Aufgabenstellung und aus der zulässigen beliebigen Umordnung endlich vieler Summanden aus den natürlichen Zahlen (das Rückwärtsaufschreiben der Summe ist ja auch eine Umordnung). Die Summe ist jeweils i + (n+1)-i = n+1.

Dies ist nicht mehr und nicht weniger einsichtig, als die Beweiskraft des Verfahrens der vollständigen Induktion.

Meines Erachtens ist es nicht so, dass durch die Aufstellung der Axiome für die natürlichen Zahlen und durch die Konzeption des Beweisverfahrens der vollständigen Induktion andere Beweisverfahren nicht mehr gültig sind, die auf den gleichen Grundlagen beruhen (Eigenschaften der natürlichen Zahlen), nur weil sie nicht genau dem Algorithmus dieser Methode entsprechen. Hier muss man wohl grundsätzlich darauf achten, dass Fortschritte in den Methoden und bei den Begriffsbildungen nicht zu einer Verengung der Sicht und Vereinnahmung dessen führen, was vorher schon richtig und gültig war. Die Anekdote mit Gauß kam in den Beitrag, weil in einer vorhergehenden Version behauptet worden war, die Summenformel für 1 + .... + n könne ohne vollständige Induktion nicht bewiesen werden. Dies ist sicherlich falsch. 07.12.2003 (212.202.52.146)

Um es klar zu sagen: Man kann die Summenformel auf (mindestens) 2 Arten beweisen: Einmal mit der "direkten" Methode , so wie es Gauss tat. Andrerseits kann man die Formel auch mit dem Verfahren der vollständigen Induktion beweisen. Beide Beweise sind gültig und gleichwertig.
Um die Gauss-Methode noch ein wenig zu präzisieren: Man wählt zunächst eine beliebiges n > 0 und hält dieses dann fest. Für dieses feste n führt man obigen Beweis (Summe vorwärts und rückwarts schreiben und dann addieren) durch. Und weil n beliebig gewählt wurde gilt der Beweis für alle n > 0. -- tsor 16:43, 7. Dez 2003 (CET)

1. Der Artikel handelt nicht von den verschiedenen Beweismöglichkeiten der Summenformel, sondern von der vollständigen Induktion.
   unstrittig -- tsor 22:21, 10. Dez 2003 (CET)
2. Nach heutigen Massstäben muss ein mathematischer Beweis formalisierbar sein. Natürlich gab und gibt man sich oft damit zufrieden, ihn plausibel zu machen. Was man dazu "braucht", ist eine didaktische, soziologische und psychologische Frage (meist genügt die Autorität des Mathe-Lehrers ;-)).
   ???? -- tsor 22:21, 10. Dez 2003 (CET)
3. Im modernen axiomatischen Aufbau des Zahlensystems (das auf Sparsamkeit der Axiome ausgelegt ist) braucht (im Sinne eines formalen Beweises) man bereits für den Beweis der Kommutativität der Addition die vollständige Induktion (siehe [1]), und also auch für beide Beweise der Summenformel. Selbst bei einem anderen axiomatischen Aufbau kann man den induktiv definierten Summenausdruck nur mittels vollständiger Induktion allquantifizieren. Heizer 12:51, 10. Dez 2003 (CET)
   Was bedeutet das in diesem Zusammenhang? Die Kommutativität der Addition kann man als bewiesen voraussetzen wenn man schon bei Folgen angelangt ist. -- tsor 22:21, 10. Dez 2003 (CET)

Ich würde sagen, die Schlussregeln, die man benötigt, um von den Axiomen zur Konklusio zu kommen, sind Bestandteil des Beweises. Aber lassen wir das mal beiseite. Was genau ist Dir denn unklar? Formalisierbarkeit? Allquantor oder Induktive Definition? Heizer 01:46, 11. Dez 2003 (CET)

Nobel geht die Welt zugrunde. 10.12.2003 (212.202.185.99)
ja. -- tsor 22:21, 10. Dez 2003 (CET)

Nein, das wird ein Heulen und Zähneklappern! Heizer 01:46, 11. Dez 2003 (CET)

---

Hallo SirJective,

Ich muß sagen, für so eine "Induktion" habe ich in einer Klausur schon 0 Punkte bekommen.

Ich mache sie mal neu (und ausführlicher).

arbol01 19:15, 10. März 2004

Deine Ergänzung sieht auf den ersten Blick sinnvoll aus, leider gibt es nun eine Doppelung in dem Abschnitt. Wenn mir keiner zuvorkommt, werde ich diese in den nächsten Tagen auflösen. --SirJective 22:04, 10. Mär 2004 (CET)

Ich muß sagen, daß es mir sehr schwer fällt, meine Ergänzung einzusetzen. Ausserdem habe ich die Induktion auf eine andere Formel angewendet.

Hier noch mal die andere vollständige Induktion:

Angewandt auf obiges Beispiel sieht das so aus:

Wir wollen eine Formel finden die die Summe aller ungeraden Zahlen von 1 bis n vereinfacht und, was wichtiger ist, wir wollen diese Formel beweisen:

1 = 1 ; 1 + 2 = 3 ; 1 + 2 + 3 = 6 ; 1 + 2 + 3 + 4 = 10

Vermutung: Die Summe aller natürlichen Zahlen von 1 bis n ergibt:

• $\sum _{i=1}^{n}i={\frac {n*(n+1)}{2}}$

Das ist zu zeigen. Wenn die Formel stimmt, dann müssen verschiedene Dinge zutreffen:

• $\sum _{i=1}^{n}i+(n+1)=\sum _{i=1}^{n+1}i$

• $\sum _{i=1}^{n}i+(n+1)={\frac {n*(n+1)}{2}}+(n+1)$

• $\sum _{i=1}^{n+1}i={\frac {(n+1)*(n+2)}{2}}$

• ${\frac {n*(n+1)}{2}}+n+1={\frac {(n+1)*(n+2)}{2}}$ /* Die Perle */

Das letzte ist die Perle, die jetzt bewiesen werden muß. Nur die Perle hinzuschreiben, reicht als Beweis nicht aus.

• ${\frac {n*(n+1)}{2}}+n+1={\frac {(n+1)*(n+2)}{2}}$

• ${\frac {n*(n+1)}{2}}+{\frac {2n+2}{2}}={\frac {(n+1)*(n+2)}{2}}$

• ${\frac {n*(n+1)+2n+2}{2}}={\frac {(n+1)*(n+2)}{2}}$

• ${\frac {n^{2}+n+2n+2}{2}}={\frac {n^{2}+3n+2}{2}}$

• ${\frac {n^{2}+3n+2}{2}}={\frac {n^{2}+3n+2}{2}}$

Damit ist die vollständige Induktion für $\sum _{i=1}^{n}i={\frac {n(n+1)}{2}}$ abgeschlossen und bewiesen.

Warum muss die "Perle" so umständlich "Bewiesen" werden? Das sind einfache Äquivalenzumformungen, welche "gesehen werden können. Wenn nicht kann man das ganze auch ohne diesen ganzen Umstand zeigen:

• ${\frac {n*(n+1)}{2}}+n+1={\frac {(n+1)*(n+2)}{2}}$

• ${\frac {n*(n+1)}{2}}+{\frac {2*(n+1)}{2}}={\frac {(n+1)*(n+2)}{2}}$

• ${\frac {n*(n+1)+2*(n+1)}{2}}={\frac {(n+1)*(n+2)}{2}}$

• ${\frac {(2+n)*(n+1)}{2}}={\frac {(n+1)*(n+2)}{2}}$

• ${\frac {(n+1)*(n+2)}{2}}={\frac {(n+1)*(n+2)}{2}}$

--Felbion 20:34, 19. Mai 2009 (CEST)

Ich werde das Ganze auch noch mal mit n über k und 0.9p = 1 machen.

arbol01 23:22, 10. März 2004

strukturelle Induktion

Im Abschnitt "Verallgemeinerungen" sollte noch ein Link zur strukturellen Induktion gesetzt werden, leider bin ich mir nicht ganz sicher, wie sich diese zur transfiniten Induktion verhält, jemand mit mehr Ahnung vielleicht...? --Esperantisto 11:47, 28. Sep 2004 (CEST)

Ich kenne keine Details, aber so wie ich strukturelle Induktion verstehe, geht es dort nicht wie bei den natürlichen Zahlen um eine totale, sodern um eine allgemeinere Halbordnung; es sind also nicht wie bei den natürlichen Zahlen zwei Elemente direkt vergleichbar. Im Gegensatz zur transfiniten Induktion werden aber bei struktureller Induktion nur höchstens abzählbar viele Elemente betrachtet; insbesondere wird das Auswahlaxiom nicht benötigt. Vielleicht kann noch jemand mehr Information dazu geben.

Verallgemeinerungen

Kann jemand einige schöne Beispiele zu den Verallgemeinerungen beitragen? So, wie es jetzt steht, wirkt es noch zu theoretisch. --NeoUrfahraner 05:16, 27. Feb 2005 (CET)

Stolperfallen mit aufnemhen ?

Hallo! Bei der vollst. Induktion gibt es ja eine Reihe von Stolperfallen in die man treten kann. Hier ein lustiges Beispiel:

Behauptung Alle Katzen haben die selbe Farbe.

Beweis:

1. In einer einelementigen Menge (n = 1) von Katzen haben alle Katzen die selbe Farbe
2. Angenommen, alle Katzen einer n-elementigen Menge haben die selbe Farbe.
3. Gegeben sei nun eine n+1-elementige Menge von Katzen. Entfernt man eine Katze A aus dieser Menge, so haben alle Katzen der Restmenge die selbe Farbe (folgt aus Indunktionsannahme). Fügt man Katze A wieder hinzu und entfernt eine andere Katze B, so haben wieder alle Katzen der Restmenge die selbe Farbe
4. Also haben A und B die selbe Farbe und damit alle Katzen der n+1-elementigen Menge

Wo liegt der Fehler? :-) Damit A und B überhaupt unterschiedliche Katzen sein können muss die Menge mindestens 2 Elemente haben. Die Behauptung müsste also für n = 2 statt für n = 1 explizit gezeigt werden, daher rührt der Fehler!

Sollte man an irgend einer Stelle des Artikels auf die typischen Stolperfallen hinweisen? Wenn ja, wo? Und was für Stolperfallen gibt es sonst noch? -- Prometeus 14:31, 9. Apr 2005 (CEST)

Aus meiner Sicht spricht nichts dagegen, möglicherweise sehen aber andere das kritischer. Einbauen kann man das beispielsweise als neues Kapitel ganz am Ende (nach Verallgemeinerungen). Andere Stolperfallen sind beispielsweise solche, die für "viele" n gelten (z.B. n*n + n + 41 ist prim) oder solche, wo der Induktionsschritt klappt, aber der Anfang nicht gilt (also irgendeine Summenformel, wo man einfach eine Konstante abzieht). --NeoUrfahraner 17:46, 9. Apr 2005 (CEST)

Hab den Spaß mal unter "Tipps zur Anwendung - Häufige Fehler" eingefügt. Ein ernsthafteres Beispiel ist mir für den 2. Fall auf die Schnelle nicht eingefallen. Andererseits bleien Kuriosa ja besser im Gedächtnis ;-)

--Prometeus 18:43, 9. Apr 2005 (CEST)

ad Die Idee

Ich habe mir erlaubt die Einleitung dieses Abschnitts wiederherzustellen, da die ursprüngliche Textqualität weitaus besser ist und eine einfache, gut strukturierte Sichtweise bietet. Ich bitte weiters zu berücksichtigen, dass WP kein Lehrbuch ist und eine vereinfachte Textwahl auch zu Qualitätabstichen führen kann. Grüße Tom1200 12:15, 10. Jul 2005 (CEST)

Wer hat die qualität abgestochen, Tom1200? ;)) --212.100.47.161 02:19, 14. Okt 2005 (CEST)

Unlogisch...?

Kann mir mal jemand sagen wieso laut artikel $(k+1)\cdot {\frac {k+2}{2}}$ gleich ${\frac {(k+1)\cdot ((k+1)+1)}{2}}$ ist??

Ich meine wenn man davon ausgeht dass $k+2=((k+1)+1)$ ist, dann erscheint mit das heraufheben von $(k+1)$ auf den bruch durch 2 doch als ungültig da $(k+1)$ nicht gleich ${\frac {(k+1)}{2}}$ ist. Oder?

-- Hurricane (212.100.47.161 02:30, 14. Okt 2005 (CEST))

${\frac {(k+2)}{2}}$=${\frac {(k+1)+1}{2}}$, multipliziere beide Seiten mit $k+1$, dann steht genau das Gewünschte dort. Wo ist das Problem? --NeoUrfahraner 06:10, 14. Okt 2005 (CEST)

Das Heraufheben auf den Bruch ist völlig korrekt. Beispiel: $5\cdot {\frac {6}{2}}=5\cdot 3=15={\frac {30}{2}}={\frac {5\cdot 6}{2}}$.--Gunther 09:40, 14. Okt 2005 (CEST)

Unlogisch 2 aka zuwenig Zeilenabstand

wahrscheinlich hab ich irgendwo einen denkfehler gemacht, aber wie kommt dieser Ausdruck zustande ??

$=(k+1)\cdot \left({\frac {k}{2}}+1\right)$

wenn ich

$1+2+3+\dots +k+(k+1)$

nach

$1+2+...+n={\frac {n(n+1)}{2}}$

anwende kommt bei mir

$1+2+3+\dots +k+(k+1)={\frac {(k+1)(k+1+1)}{2}}$ raus

--Sam vimes 15:04, 9. Dez 2005 (CET)

Ja, und

${\frac {(k+1)(k+2)}{2}}=(k+1)\cdot {\frac {k+2}{2}}=(k+1)\cdot {\Big (}{\frac {k}{2}}+1{\Big )}.$

--Gunther 12:49, 9. Dez 2005 (CET)

Ich hatte Probleme mit

$=(k+1)\cdot {\frac {k+2}{2}}$

$={\frac {(k+1)\cdot (k+2)}{2}}$

$={\frac {(k+1)\cdot ((k+1)+1)}{2}}$

weil ich beim lesen der zeilen fälschlicherweise den Divisor der oberen Zeile zusätlich noch als Exponent gelesen habe... mein fehler

--Sam vimes 15:04, 9. Dez 2005 (CET)

Lesenswert-Diskussion

Vollständige Induktion oder der "Schluss von n auf n + 1" ist eine Beweismethode, die üblicherweise eine Aussage für alle natürlichen Zahlen beweist. Sie funktioniert aber auch für allgemeinere Fälle (siehe unten).

•  Pro Antifaschist 666 16:41, 10. Okt 2005 (CEST)

•  Pro Gefällt mir sehr gut. Am Anfang wird ein einigermaßen allgemeinverständlicher Einstieg geboten, trotzdem ist der Artikel mathematisch fundiert. -- mkill - ノート 12:05, 12. Okt 2005 (CEST)

• Momentan wirkt der Artikel auf mich noch ein wenig durcheinander (was die Gliederung angeht) und an manchen Stellen noch etwas unpräzise. Und letzteres sollte gerade bei einem mathematischen Artikel keinesfalls sein, denn in der Mathematik kann "unpräzise" oft einfach nur "falsch" bedeuten. Ein sehr merkwürdiger Teil findet sich übrigens gleich zu Beginn: "Obwohl auch bei der vollständigen Induktion vom Speziellen auf das Allgemeine geschlossen wird, ist sie jedoch kein induktives, sondern ein deduktives Prinzip.". Wenn man unter dem Link nachsieht, liest sich der Satz dann so: "Obwohl auch bei der vollständigen Induktion vom Speziellen auf das Allgemeine geschlossen wird, schließt sie vom Allgemeinen aufs Spezielle". Ich weiß nicht, was mir das sagen soll. Also erstmal  Kontra --Sentry 12:20, 12. Okt 2005 (CEST)

•  Pro Vielleicht könnte man noch das vielzitierte Beispiel mit den Dominosteinen einbringen: Der erste wird angeschubst, schmeißt den zweiten um, der den dritten usw. Der holprige Satz "Obwohl auch bei der vollständigen Induktion vom Speziellen auf das Allgemeine geschlossen wird, ist sie jedoch kein induktives, sondern ein deduktives Prinzip." ist nicht falsch, sondern steht der Trennung zwischen logischer und mathematischer Induktion grammatisch etwas schwach entgegen: Alle Mathematik ist deduktiv, ergo auch die Vollständige Induktion. Der Name des Beweisverfahrens ist für Logiker also etwas unverständlich gewählt, beruht aber darauf, dass man von einem speziellen Fall (dem Induktionsanfang) auf die Allgemeinheit (alle natürlichen Zahlen) schließt. Innerhalb der deduktiven Mathematik liegt hier also ein (pseudo-)induktives Verfahren vor. --Thetawave 13:01, 15. Okt 2005 (CEST)

•  Pro --wizzar 19:59, 15. Okt 2005 (CEST)

"Man beruft sich auf den Fall n=2 ??"

In dem Artikel steht zu dem Beweis, dass alle Zahlen gleich sind:

"Beim Induktionsschritt beruft man sich auf einen Fall, der aber nicht explizit bewiesen wurde (z.B. den Fall n = 2)" und "Wir berufen uns also auf die Richtigkeit von n = 2, ohne es vorher bewiesen zu haben"

Damit kann ich mich gar nicht einfreunden:

Der Induktionsschluss hat ÜBERHAUPT NICHTS mit der tatsächlichen Richtigkeit der einzelnen Aussagen zu tun: Es wird nur gezeigt, dass die FOLGERUNG gilt. (Die Folgerung von n auf n+1 kann sogar richtig sein, ohne das A(n) gilt!!)

Der EINZIGE Fehler in dem Beweis ist hier, dass der Induktionsschluss NUR FÜR n>=2 möglich ist, aber für ausnahmslos ALLE n>=1 gültig sein müsste!!

Explizit bewiesen wird in diesem (Schein-)Beweis nur für n=1. Würde man bei 2 anfangen wäre es ein anderer Beweis mit anderer Verankerung, das ist aber viel zu kompliziert gedacht!

Man beruft sich also höchstens im allerweitesten Sinne auf die Richtigkeit von n=2:

"Wenn A(2) gelten würde, wäre der Satz bewiesen."

Wenn ich kein gutes Gegenargument höre, ersetze ich diese seltsame Erklärung durch die meiner Meinung nach trefferende Festmachung des Fehlers:

"Der Induktionsschritt ist nicht für alle n>=n0 gültig!, d.h. es gibt mindestens ein n>=n0, für das er nicht anwendbar ist. (Hier n=1)"

Zustimmung. Es ist aber unnötig, hier über irgendein n0 zu sprechen. Der Induktionsschritt von 1 auf 2 ist falsch, mehr muss man nicht sagen.--Gunther 20:58, 6. Nov 2005 (CET)

Genau. In dem Fall muss man nicht mehr sagen. Will man eine allgemeine Einordnung des Fehlers (unter "häufige fehler und stolperfallen") angeben, so ist eben dieser Satz (s.o.) zutreffend ("schluss nicht für alle n gültig")

"Häufige Fehler" sind in einem Enzyklopädieartikel ohnehin fragwürdig (vgl. WP:WWNI Punkt 8), aber ich denke, das Beispiel hat eine gewisse eigenständige Berühmtheit erlangt und dient auch dem Verständnis der Induktion.--Gunther 15:48, 8. Nov 2005 (CET)

Geschichtlich: frühere Verwendung der Induktion?

Im Artikel Franciscus Maurolicus findet sich ein Hinweis auf eine frühere Verwendung der Induktion. Ich kenn mich mit der Geschicht der Mathematik nicht so gut aus, dass ich sagen könnte, dass das stimmt. Vielleicht kann das jemand aufklären? Grüße --Trifi 23:46, 12. Apr 2006 (CEST)

Ist das Induktionsprinzip deduktiv?

Schon andere Kommentatoren vor mir sind über den folgenden Satz gestolpert: "Obwohl auch bei der vollständigen Induktion vom Speziellen auf das Allgemeine geschlossen wird, ist sie jedoch kein induktives, sondern ein deduktives Prinzip." Was absurd klingt wird an anderer Stelle gerechtfertigt mit dem Hinweis, dass die gesamte Mathematik deduktiv ist, also auch ihr Induktionsprinzip. Ich möchte vorschlagen einen Unterschied zwischen internen und externen Eigeschaften zu sehen. Das Induktionsprinzip ist induktiv, denn vom Speziellen wird auf das Allgemeine geschlossen -- eine interne Eigenschaft. In der mathematischen Praxis kenne ich es als Axiom. Dieses allgemeine Axiom wird auf den speziellen Fall angewendet -- eine externe Eigenschaft. Was man, diesen Gedanken folgend, anstelle des zitierten Satzes schreiben könnte, wäre meiner Meinung nach relativ uninteressant, etwa: "Das Induktionsprinzip erlaubt einen induktiven Schluss, d.h. einen Schluss vom Speziellen aufs Allgemeine. Es wird im deduktiven Argumentieren der Mathematik als allgemeines Axiom benutzt, das im speziellen Fall seine Anwendung findet." Wie gesagt, eher uninteressant. Sollte man den Satz vielleicht komplett weglassen? Gr., Bastian

Der Satz ist wichtig und richtig; die Unterscheidung "intern" und "extern" ist unnötig und findet sich meines Wissens auch nicht in der Literatur. Zunächst solltest Du Dir klar machen, dass Axiome in der Mathematik nicht induktiv begründet werden; sie werden als "wahr" vorausgesetzt, ohne sich um die "Wirklichkeit" zu kümmern. Ausgehend von diesen Axiomen wird deduktiv weitergearbeitet, auch bei der vollständigen Induktion. Lies am besten Induktionsschluss durch, dann sollte Dir klar werden, dass vollständige Induktion mit dem Induktionsschluss der Logik nichts zu tun hat. --NeoUrfahraner 07:12, 4. Mai 2006 (CEST)

Induktive vs. Rekursive Definition

Was ist der Unterschied? Gibt es einen?

--Christoph 17:31, 26. Sep 2006 (CEST)

Wie meinen??? *grübel* -- zOiDberg (δ·β) 17:54, 26. Sep 2006 (CEST)

Manchmal steht im Skript, dass eine Definition induktiv ist, manchmal rekursiv. Wie kann ich erkennen, wann was zutrifft. Werden rekursive Funktionen induktiv definiert? --Christoph 11:14, 27. Sep 2006 (CEST)

Hast Du Beispiele dazu? Was wird dort als induktiv, was als rekursiv bezeichnet? --NeoUrfahraner 11:33, 27. Sep 2006 (CEST)

Also ich habe den Begriff einer "induktiven Definition" bisher nocht nicht vernommen. Die Begriffe rekursiv und induktiv spielen jedoch zunächst einmal in einer ganz anderen Liga und bezeichnen unterschiedliche Dinge. Daher wären Beispiele zur Klärung Deiner Frage hilfrich. Gruß, -- zOiDberg (δ·β) 16:53, 27. Sep 2006 (CEST)

Also in der Algorithmik treten die zwei Begriffe durchaus (auch vergleichend) auf: Beispielsweise kann man die Fakultät induktiv, also von 1 bis n definieren, als auch rekursiv, von n bis 1. Ersteres ist eine einfache for-Schleife, wobei zweites als Fakultät(1)=1 und Fakultät(n)=n*Fakultät(n-1) definiert ist. --Felbion 20:49, 19. Mai 2009 (CEST)

Unterpunkt: Die Idee

Sollte der Unterpunkt "Die Idee" nicht besser dem Beispiel untergeordnet werden? Immerhin bezieht sich ja der Lösungsweg dann wieder auf das Beispiel. Hat mich beim Lesen etwas verwirrt...

Was spricht gegen das PDF?

http://de.wikipedia.org/w/index.php?title=Induktion_%28Mathematik%29&diff=22971718&oldid=22951141

• Aufgaben mit Beweisen zur Induktion (pdf)

spricht da irgendetwas gegen? Das erscheint mir doch eher hilfreich ...

Bei dem angegebenen Blatt wird auf Seite sind die natürlichen Zahlen ohne 0 definiert und auf Seite 7 wird mit n=0 verankert. Widersprüchlich, oder? (nicht signierter Beitrag von Felbion (Diskussion | Beiträge) 20:55, 19. Mai 2009 (CEST))

---

Scherzhafte vollständige Induktion

Hallo zusammen, hat jemand Quellen für scherzhafte Anwendungen der v.I., also aus völlig un-mathematischen Zusammenhängen oder witzige falsche Induktionen ? MfG Maex 15:39, 2. Jan. 2007 (CET)

k+1 oder Nachfolger?

Es wäre m. E. besser, wenn für die auf k unmittelbar folgende Zahl ein anderes Symbol als k+1 verwendet würde. Denn das +-Zeichen erweckt den Anschein, als sei von Addition die Rede. Aber diese kommt in den Axiomen ja gar nicht vor, sondern wird erst später mit Hilfe der Axiome, insbesondere des Induktiosaxioms, eingeführt. --Hanfried.lenz 09:34, 3. Sep. 2007 (CEST).

Bei den "normalen" Anwendungen der vollst. Induktion darf man meines Erachtens die Rechengesetze der natürlichen Zahlen und somit das "+" als bekannt/bereits bewiesen voraussetzen. Lediglich wenn man die Rechengesetze der natürlichen Zahlen aus den Peano-Axiomen ableitet (also bei dem was z.B. Edmund Landau in seinen Grundlagen der Analysis ausführlich beschreibt), gibt es natürlich noch kein "+", sodass ein anderes Symbol erforderlich ist. Im Artikel Natürliche Zahl wird diese Unterscheidung auch gemacht; hier im Artikel "Vollständige Induktion" genügt allerdings eine kurze Bemerkung in der Art, wie Du sie bereits eingefügt hast. Ich würde allerdings die Formulierung "Weil in den Peano-Axiomen die Addition noch nicht definiert ist, wird dort ein anderes Symbol benützt." statt "Weil die Addition noch nicht definiert ist, wäre es besser, ein anderes Symbol zu benützen." bevorzugen. --NeoUrfahraner 10:18, 3. Sep. 2007 (CEST)

OK! --Hanfried Lenz 11:54, 19. Nov. 2007 (CET).

Vollständige Induktion - ein Deduktives Verfahren: Erläuterung IM ARTIKEL notwendig

Diesen scheinbaren Widerspruch im Artikel anzumerken, aber nicht zu erläutern kommt ziemlich altklug daher. Vieleicht kann mal jemand die richtigen und wichtigen Gründe dafür im Artikel anmerken. Ebenso die hier in der Diskussion angemerkte Unterscheidung, warum es "klar" sei, das der Induktionsschluss der Logik etwas anderes ist. Mir wird das aus dem Artikel nicht klar. Eine Gegenüberstellung wäre angebracht. --source 17:51, 11. Jan. 2008 (CET)

Ich versuch's einmal hier zu erklären; wie weit das in den Artikel aufgenommen werden soll, können wir dann besprechen.

Induktion ist der Schluss vom Besonderen auf das Allgemeine, also von Einzelfällen auf die zugrunde liegende Gesetzmäßigkeit. Beobachte ich z.B., dass fünf verschiedene Steine, die ich in die Hand nehmen, zu Boden fallen, wenn ich sie los lasse, und schließe daraus, dass alle Steine zu Boden fallen, wenn man sie los lässt, so ist das ein induktiver Schluss: von fünf speziellen Beobachtungen auf ein allgemeines Gesetz. Deduktion hingegen schließt von einem allgemeinen Gesetz auf einen Spezialfall. Setze ich das allgemeine Gesetz, dass alle Steine zu Boden fallen, voraus, und nehme einen speziellen Stein her, kann ich als deduktiven Schluss erwarten, dass dieser Stein ebenfalls zu Boden fallen wird.

Nehme ich nun eine mathematische Formel her, z.B. die bekannte Formel $\sum _{n=1}^{N}n={\frac {N(N+1)}{2}}$, so kann ich spezielle Werte $N=1$, $N=2$, $N=42$, $N=1789$ etc. einsetzen. Setze ich genügend viele Werte ein, und die Formel stimmt, so kann ich induktiv aus diesen Spezialfällen schließen, dass die Formel allgemeingültig ist. Dieser Induktionsschluss ist aber unvollständig; ich habe nicht alle möglichen Weret für $N$ überprüft, es könnte sein, dass irgendwer ein $N$ findet, für welches diese Formel nicht stimmt. Egal wie viele spezielle $N$ ich untersuche, diese Untersuchung ist unvollständig; es bleiben imemr noch Werte für $N$ übrig, die noch nicht untersucht wurden. Der Clou besteht aber nun darin, dass es in der Mathematik möglich ist, tatsächlich alle natürlichen Zahlen zu erfassen, indem ich nämlich zeige, dass die Aussage für $N=1$ gilt und dass aus der Gültigkeit für $N=k$ die Gültigkeit für $N=k+1$ geschlossen werden kann. Damit habe ich dann alle Werte für $N$ erfasst; die Induktion aus diesen speziellen Werten ist dann vollständig.

Das Beweisverfahren der vollständigen Induktion ist damit ein deduktives Verfahren. Ich habe das allgemeine Induktionsprinzip Gilt eine Aussage $A(N)$ für $N=1$ und folgt aus der Gültigkeit von $A(k)$ die Gültigkeit von $A(k+1)$, so gilt $A(N)$ für alle natürlichen Zahlen $N$. das ich nun deduktiv für verschieden Aussagen $A(N)$ anwenden kann, im obigen Beispiel also für die Aussage $A(N)$: $\sum _{n=1}^{N}n={\frac {N(N+1)}{2}}$.

So weit klar? --NeoUrfahraner 16:07, 13. Jan. 2008 (CET)

das ist ne super erklärung, die für den artikel wohl etwas zu ausführlich ist, vielleicht kann man aber trotzdem 1,2 sätze dazu schreiben. gerade der hauptunterschied, daß man mit vollst. induktion tatsächlich deduktiv ableitet, während bei der logischen induktion von einigen beispielen die allgemeine gültigkeit _angenommen_ wird, muß klargestellt werden. das mindeste ist, daß der arktikel der "anderen" induktion verlinkt wird. eine typische oma-betrachterin des artikels hat nämlich keine ahnung davon ;) (von deduktion wohl auch nicht^^) --Xycolon 17:04, 1. Apr. 2008 (CEST)

Widerspruch bezueglich des Induktionsanfangs unter "Idee"

Hi,

unter Idee heisst es:

Ist bekannt,

   * dass eine bestimmte von n abhängige Aussage für n = 1 gilt und...

Daraus wuerde ich schliessen, dass hier n = 1 fuer den Induktionsanfang verwendet wird.

Jedoch heisst es ein paar Zeilen weiter:

   * Die Aussage ist wahr für 0 (Induktionsanfang)

Koennte jemand mit mehr Fach- und Wikipediawissen als ich das bitte richten?

Danke

Florian

--72.140.47.102 03:05, 21. Mär. 2008 (CET)

Im Prinzip ist das egal. Fängt man mit 1 an, muss man gegebenenfalls den Fall n=0 extra behandeln; fängt man mit 0 an, kann man sich gegebenenfalls die Sonderbehandlung der 0 ersparen. Es ist aber sicher sinnvoll, im Artikel einheitlich zu sein, und da die meisten Beispiele mit n=1 anfangen, habe ich auf Induktionsanfang n=1 geändert. --NeoUrfahraner 08:16, 21. Mär. 2008 (CET)

Definition, die keine ist...

Das, was hier im Artikel als Definition beschrieben wird, ist alle mal eine Plausibilätsterklärung. Die Definition der vollständigen Induktion, sollte doch anders aussehen. (nicht signierter Beitrag von 85.182.121.39 (Diskussion | Beiträge) 18:22, 16. Mai 2009 (CEST))

Indirekte Sichtweise

(Vorab: Ich bediene mich hier einer etwas anderen Semantik als in der Mathematik üblich (kein Neologismus!) – ist hier eben pragmatisch: Induktionsschritt = "Beweis für n" + "Beweis für n+1" Induktionsschluss = "deshalb für alle $n\in \mathbb {N}$")

In diesem Kapitel wird der Versuch gestartet - durch die Reductio ad absurdum - die Richtigkeit des Induktionsschlusses zu beweisen. Es ist – wie du (Ich darf doch „du“ sagen?!) schon sagtest – so definiert worden, dass der Induktionsschluss ein Algorithmenschritt innerhalb der vollständigen Induktion ist. Nun dient aber der Induktionsschritt bei dir dazu, die Negation der Prämisse ad absurdum zu führen, damit die Prämisse, und somit die Conclusio – sprich: der zu beweisende Induktionsschluss –, bewahrheitet wird. Ich kann doch aber nicht die Induktion durch sich selbst rechtfertigen! Man unterteilt die voll. Induktion in Induktionsanfang, Induktionsschritt und Induktionsschluss; aber das heißt nicht, dass jeder Teil separat für sich steht und bewiesen, bzw. als Axiom angenommen werden kann; ohne den Kontext der voll. Induktion sagen diese Sätze nichts, sie sind keine Aussagen (Jede mathematische Methode kann wie ein Spiel verstanden werden. Wenn du ein Kind vor ein Schachbrett setzt und es lediglich die Regeln zum Ziehen eines Bauern kennt, dann spielt das Kind nicht Schach, denn es kennt den Sinn und die übrigen Regeln des Schachspiels nicht; es führt Bewegungen aus, dessen Zwecke (wenn denn welche existieren) außerhalb des Schachspiels liegen.). Du beweist den Induktionsschluss aber durch den Induktionsschritt, das ist aber ein Widerspruch in sich. Bevor du die Aussage, es gebe eine kleinste natürliche Zahl ungleich eins, für die der durch die voll. Induktion zu beweisende Satz nicht gültig ist, negierst, solltest du dir im Klaren sein, mit welcher Aussage du die Negation „gültig“ machst! Suche nach einem anderen, gültigen Beweis (PS: mit dem indirekten Beweis geht es oft am besten)! --Hanswurst VII. (10:08, 5. Jul 2009 (CEST), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

Ich verlagere den problematischen Abschnitt "indirekte Sichtweise" aus dem bisherigen Artikel hierher:

Eine andere Sichtweise ist die eines indirekten Beweises: Angenommen, die Aussage gelte nicht für alle natürlichen Zahlen. Dann gibt es eine kleinste Zahl $n_{0}$, für die sie falsch ist. Es gibt nun zwei Fälle:

• $n_{0}=1$: Dies wird durch den Induktionsanfang ausgeschlossen.
• $n_{0}\neq 1$: Nach Voraussetzung ist $n_{0}$ die kleinste Zahl, für die die Aussage falsch ist, also ist sie für $n_{0}-1$ wahr. Wendet man nun den Induktionsschritt an, kann man daraus schließen, dass die Aussage auch für $(n_{0}-1)+1=n_{0}$ richtig ist. $n_{0}$ war aber definiert als die kleinste Zahl, für die die Aussage falsch ist: Widerspruch.

Beide Fälle können also ausgeschlossen werden. Damit ist die Aussage für alle natürlichen Zahlen wahr.

Kommentar dazu: Hier soll offenbar nicht, wie oben vermutet, der Induktionsschluss durch den Induktionsschritt bewiesen werden, sondern wohl der Induktionsschritt indirekt bewiesen werden über ein Minimimalitätsprinzip, das für eine nichtleere Menge natürlicher Zahlen ein minimales Element annimmt. Das wäre ein korrektes Verfahren. Man müsste dies aber auch als solches darstellen. Das wäre aber ein extra Abschnitt über äquivalente Axiome. Weil es auch andere Verfahren gibt, die Induktion zu beweisen, wäre zu überlegen, ob man so einen Abschnitt in den Artikel einbaut.--Wilfried Neumaier 16:38, 28. Jun. 2010 (CEST)

Beispiel

Ich finde das Beispiel $\sum _{k=1}^{n}k=1+2+\cdots +n={\frac {n(n+1)}{2}}$ zu beweisen recht ungeschickt gewählt. Diese Formel lässt sich viel einfacher beweisen:

$1+n=n+1$

$1+1+n-1=n+1$

$1+2+n-2=n+1$

$1+i+n-i=n+1$

Dies macht man n mal. Dann hat man $n(n+1)$. Außerdem sollte klar sein, dass auf der linken Seite vom Pluszeichen die Zahlen 1, 2, 3, ... n unter einander stehen, rechts absteigend. Die Summe der linken Seite ist also genauso groß wie die der rechten Seite. Und da man eben diese Summe haben will, teilt man durch 2. (es gibt eben zwei Summen, die zusummengefasst n(n+1) ergeben). Ergo: ${\frac {n(n+1)}{2}}$.

So etwas sollte viel einfacher zu verstehen sein. Daher finde ich das zweite Beispiel viel passender. Ich wäre dafür, dass man die Reihenfolge tauscht, das Prinzip also an dem jetzigen zweiten Beispiel erklärt wird und diese Formel als weiteres Beispiel angeführt wird. --KEBA 20:31, 14. Aug. 2009 (CEST)

Vollständige_Induktion#Begriff

Folgender Satz: Obwohl auch bei der vollständigen Induktion vom Speziellen auf das Allgemeine geschlossen wird, ist sie kein induktives, sondern ein deduktives Prinzip. sollte vllt. etwas genauer erklärt oder belegt werden. Wenn man das Prinzip verstanden hat, kann man den Satz nachvollziehen, aber da er gleich zu Beginn steht, finde ich es unkommentiert doch etwas komisch, dass die "Induktion" gar nicht induktiv sein soll. Grüße --WissensDürster 13:31, 13. Sep. 2009 (CEST)

Es ist nicht klar, auf was sich das "auch" (das zweite Wort) beziehen soll. --93.223.55.85 19:44, 21. Jan. 2010 (CET)

Änderung 14. Mär. 2010 95.117.171.116

Zu http://de.wikipedia.org/w/index.php?title=Vollst%C3%A4ndige_Induktion&diff=71888111&oldid=71008584 : Gibt es da auch ein passendes Beispiel? (Mir ist dieser Fall noch nicht untergekommen, und der Verzicht auf den Induktionsanfang ist wohl eher nur eine Ersparnis theoretischer Natur). --NeoUrfahraner 07:05, 15. Mär. 2010 (CET)

Ich habe es vorläufig zurückgesetzt, wir können das aber gerne hier diskutieren. --NeoUrfahraner 07:03, 16. Mär. 2010 (CET)

Das ist richtig. Mir ist aufgefallen, dass es die üblichen Induktionsbeweise der Schulmathematik unnötig verkompliziert. Daher ist der praktische Nutzen nicht offensichtlich. Es sind schon etwas verzwicktere Situtationen, in denen diese Variante von Vorteil ist. Ich habe in meiner Diplomarbeit einen Gruppentheoretischen Satz mittels Induktion über alle Primzahlen gemacht. In dieser Situation war der Beweis auf diese Weise leichter. Ich habe kein anderes Beispiel gefunden. Ich finde sie äußerst kontraintuitiv und war recht verblüfft, als mein Prof mir den Trick gezeigt hat. Ich habe diese Induktionsvariante auch nirgend dokumentiert gefunden. (nicht signierter Beitrag von 95.117.136.79 (Diskussion | Beiträge) 20:29, 2. Apr. 2010 (CEST))

Beachte WP:TF. Das klingt also sehr nach Theorieetablierung ("außerhalb der Wikipedia keine oder nur sehr geringe Resonanz "). Es ist zwar sicherlich eine ganz nette Verallgemeinerung, für den normalen Leser aber mehr verwirrend als hilfreich. --NeoUrfahraner 21:26, 2. Apr. 2010 (CEST)

Es handelt sich bei der gelöschten Änderung ganz einfach um eine Transfinite Induktion auf der Menge der natürlichen Zahlen mit ihrer natürlichen Ordnung (die eine Wohlordnung ist). Praktisch wird dieser Fall wohl eher selten benutzt, er ist aber trotzdem interessant, da es sich hierbei um die "richtige" Formulierung der vollständigen Induktion handelt, so dass diese auf alle Wohlordnungen verallgemeinert werden kann. Man könnte daher diese Variante mit entsprechendem Querverweis auf die transfinite Induktion wieder einbauen? Gruss -- Godfatherofpolka 23:30, 2. Apr. 2010 (CEST)

Wenn es ein passendes Beispiel oder einen weiterführenden Literaturverweis gibt, dann ja. Sonst (siehe oben) ist es mehr verwirrend als hilfreich. --NeoUrfahraner 10:13, 3. Apr. 2010 (CEST)

Ein erster Literaturverweis, der mir in den Sinn kommt ist Deisers Einführung in die Mengenlehre, siehe gerade die erste Seite von [2], es gibt noch mehr, aber das kann ich erst liefern, wenn ich wieder in der Nähe meiner Bücher bin. Gruss -- Godfatherofpolka 10:47, 3. Apr. 2010 (CEST)

OK. Ein Beleg wie dieser sollte reichen. --NeoUrfahraner 10:55, 3. Apr. 2010 (CEST)

Beweis für rationale Zahlen

Zu http://de.wikipedia.org/w/index.php?title=Vollst%C3%A4ndige_Induktion&diff=prev&oldid=49619666 : (Beweis für rationale Zahlen). Kennt da wer ein Beispiel oder ist das nur theoretische Spielerei? Sollen wir das behalten? --NeoUrfahraner 14:30, 16. Mär. 2010 (CET)

Ich habe jetzt den "Beweis für rationale Zahlen" entfernt. Wenn jemand einen passenden Anwendungsfall dafür liefern kann, kann man es von mir aus wieder einfügen. --NeoUrfahraner 10:22, 19. Mär. 2010 (CET)

Das Diagramm "Der Gegensatz zwischen Deduktion und Induktion" stammt von einem Geisteswissenschaftler!

Die Erklaerung natuerlich auch.

Mann! Mittels vollstaendiger Induktion kann ich (wenn es klappt!) meine Vermutung *beweisen*!! Das Thema ist dann endgueltig durch und geklaert! (nicht signierter Beitrag von 80.187.107.65 (Diskussion) 00:49, 5. Jun. 2010 (CEST))

Ich habe mich des mehrfach in der Diskussion angesprochenen Problems angenommen. Das Diagramm stammt aus dem philosophischen Induktionsartikel. Ein Link dorthin genügt. Die Graphik hat nichts mit der vollständigen Induktion zu tun. --Wilfried Neumaier 08:48, 28. Jun. 2010 (CEST)

Zur Geschichte

Im Artikel steht: "Bis zum Jahr 1879 wurde sie jedoch nur für arithmetische Probleme benutzt. Erst als Gottlob Frege damit die Klasse der natürlichen Zahlen definierte, wurde sie zu einem allgemein gültigen Beweisverfahren in der Mathematik." Für solch eine präzise datierte Behauptung muss eine Quelle angegeben werden. Das Jahr 1879 bezieht sich offenbar auf Freges Begriffschrift. Sie enthält aber keine Arithmetik und Zahlendefinition. Freges Arithmetik von 1884 hat eine andere Zahlendefinition, die nichts mit der Induktion zu tun hat, sondern Zahlen als Klassen mit endlich vielen Elementen definiert. Dann kommt nur noch Freges Arithmetik-Kalkül von 1893 in Frage. Damals gab es aber längst die Arithmetik von Dedekind 1888 und Peano 1889 mit explizit formuliertem Induktionsprinzip. Das ist meines Erachtens der historische Wendepunkt.--Wilfried Neumaier 08:25, 28. Jun. 2010 (CEST) Die verallgemeinerte Induktion, die nicht auf die Arithmetik begrenzt ist, stammt auch nicht von Frege, sondern aus Cantors Mengenlehre. Die historische Information ist also insgesamt zweifelhaft.--Wilfried Neumaier 08:29, 28. Jun. 2010 (CEST).

Ich habe die zweifelhafte Information durch die historisch belegbare ersetzt. Für eine Rückgängigmachung muss ein Quellenbeleg bei Frege erbracht werden. Laut dem englischen Wikipedia-Artikel ist auch die Vorgeschichte vor Frege alles andere als gut recherchiert und belegt. Hier ändere ich aber erst etwas, wenn mir klare Quellen vorliegen.--Wilfried Neumaier 14:12, 28. Jun. 2010 (CEST) Dedekinds anschauliche und exakte Definition erübrigt die bisherigen diversen redundanden Veranschaulichungen. Eine Straffung tut hier dem Artikel gut. Kann jemand die Domino-Graphik besser in den Freiraum plazieren? Ich habe mich mit solchen Dingen bisher nicht befasst.--Wilfried Neumaier 14:46, 28. Jun. 2010 (CEST)

Fragen

Gibt es nicht auch andere Induktionsanfänge als eins? Hauptsache ist doch, dass man irgendwo einen Anfang hat, meinetwegen bei n=8 und aus n ===> n + 1 folgt.

Natürlich gibt es andere Induktionsanfänge (Dedekind-Orginalzitat in der Fußnote). Sie werden unter den "Verallgemeinerungen und Varianten" behandelt als "Beweis für fast alle natürlichen Zahlen".--Wilfried Neumaier 00:09, 29. Jun. 2010 (CEST)

Die Veranschlaulichung ist schlecht. Man hat nicht unendlich viele Induktionsschritte, da ueber unendlich in der Mathematik nichts ausgesagt wird. Man hat beliebig viele, wenn es n beliebig viele sind, geht es mit n + 1 weiter. Auch steht dort alle Dominosteine fallen um, es gibt aber nicht unendlich viele Dominosteine. -- Room 608 18:08, 28. Jun. 2010 (CEST)

Weil nicht endlich viele natürliche Zahlen vorliegen, was mit exakt definierten Endlichkeitsbegriffen gezeigt werden kann, liegen unendlich viele vor und daher auch unendlich viele konkretisierte Induktionsschritte mit eingesetzten natürlichen Zahlen. Gerade deswegen braucht man ja die vollständige Induktion; sonst könnte man auf sie verzichten. Bei den Dominosteinen sind es allerdings nur beliebig viele. Dieses Beispiel hinkt tatsächlich ein wenig. Ich wollte es aber nicht löschen, da es die trockene Mathematik etwas lebendiger macht. Es kann aber dazu dienen, den Unterschied zwischen "beliebig" und "unendlich" herauszuarbeiten. Ich versuche dies gleich.--Wilfried Neumaier 00:09, 29. Jun. 2010 (CEST)

In der Mathematik wird nichts ueber unendlich ausgesagt, jedenfalls bis Cauchy, es kommen nur Ausdruecke vor in denen es vorkommt. Der erste Beweis ist ein Widerspruchsbeiweis, wenn die natuerlichen Zahlen nicht endlich sind, sind sie unendlich. Das ist ein logischer Beweis. Vielleicht verstehe ich es falsch, aber der konkrete Zeitpunkt und Anlass der Uebernahme, dieses Themas in und durch die mathematische Logik, oder deren Etablierung, sollte als Zaesur (1888?) dargestellt werden, zum Beispiel mit Jahreszahlen im Absatz Anwendungen, Peano hat doch vor 1930 gearbeitet, wie Du es weiter schon durch Deine Verbesserungen getan hast (ich meine die Bezugnahme auf Arithmetik). -- Room 608 02:55, 29. Jun. 2010 (CEST)

Unendliche Induktion unten ist zu knapp. Ein Hinweis, dass Metamathemaitk, Mathematik mit Mathematik untersucht waere nett. Hat nicht Lorenzen, die auch etwas knappe transfinite Induktion eingefuehrt? Die Lesenswertkandidatur, muesste wiederholt werden, da inhaltlich einiges geschah. Sonst schon verstaendlich, der Artikel. --Room 608 02:55, 29. Jun. 2010 (CEST)

Die unteren Absätze sind alle noch unzulänglich. Bevor eine Lesenswertkandidatur anvisiert wird, würde (werde?) ich noch einiges verbessern. Transfinite Induktion stammt von Cantor spätestens 1895. Unendliche Induktion ist mir unbekannt und müsste bis zur Klärung und ordenlichen Verlinkung heraus. Peano hat selbst die Rechengesetze per Induktion bewiesen; das Buch von 1930 gehört allenfalls in die Fußnote. Auch das Historische ist - wie oben schon vermerkt - noch sehr unbefriedigend.--Wilfried Neumaier 08:29, 29. Jun. 2010 (CEST)

Den Passus zur "unendlichen Induktion" stelle ich bis zur Verbesserung hierher: In der Metamathematik verwendet man eine so genannte unendliche Induktion (auch $\omega$-Regel genannt). In halbformalen Systemen der Mathematik lassen sich damit Vollständigkeitsbeweise und Widerspruchsfreiheitsbeweise durchführen.