Diskussion:Vollständige Induktion/Archiv/1

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:Vollständige Induktion/Archiv/1#Thema 1]]

oder als Weblink zur Verlinkung außerhalb der Wikipedia

https://de.wikipedia.org/wiki/Diskussion:Vollst%C3%A4ndige_Induktion/Archiv/1#Thema_1

Ä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 [1], 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)

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)

Inzwischen habe ich mich mit Frege befasst und es ist mir klar geworden, was der Hintergrund für obige Aussage über Frege ist. Sie schießt weit über das hinaus, was bei Frege tatsächlich zu finden ist, aber hat eine eingeschränkte Berechtigung. Frege bemerkt in der Begriffsschrift 1879 S. 64 in einer Fußnotenzeile zu seinem Satz Nr. 81, dass auf ihm die Bernoullische Induktion beruht. Das ist alles. Hier liegt also eine knappste Ideenskizze zur Induktionsableitung vor, die aber nicht die historischen Folgen hatte, wie oben behauptet. In seinen Grundlagen der Arithmetik von 1884, die keine große historische Wirkung hatten, kommt er auf diese Idee zurück in §79 und §80 und führt sie langatmige philosophisch weiter aus. Sie ist hier Teil seiner Zahlendefinition, die er in seinem Kalkül von 1893 dann formalisierte; beides, die Defintion und der Kalkül ist mit Inkonsistenzen behaftet. Wenn man im Artikel etwas über Frege aussagen will, muss also der Stellenwert und die Problematik sachgemäß bewertet werden. Es ist die Frage, ob dazu hier der geeignete Raum ist.--Wilfried Neumaier 15:30, 5. Jul. 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 unklaren Passus zur "unendlichen Induktion" und die nicht in einen Enzyklopädie-Artikel gehörenden "Tipps zur Anwendung" 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.

Es kann sich beim Beweis von Summenformeln mitunter als sehr mühsam erweisen, beim Induktionsschritt von $n$ zu $n+1$ durch Umformungen die Struktur der Ausgangsformel neu zu konstruieren. Dies ist jedoch zur Beweisführung unerlässlich. Da ist es dann manchmal hilfreich, das Pferd von hinten aufzuzäumen. Beispielsweise ist das Ausmultiplizieren und Zusammenfassen von Gliedern oftmals leichter zu bewerkstelligen als das phantasievolle Aufspalten und Umordnen von Gliedern, um etwas ausklammern zu können. Um diesen Umstand zu nutzen, setzt man in die zu beweisende Formel $n+1$ für $n$ ein und versucht, durch äquivalente Umformungen die Ausgangsformel für $n$ zu isolieren. Da die Formel für $n$ laut Voraussetzung gilt, ist der Beweis geführt, sobald das, was bei den äquivalenten Umformungen außer der isolierten Formel z. B. als Summand oder als zusätzlicher Faktor entsteht, dem entspricht, was beim Induktionsschritt hinzugefügt wird.

Damit dürfte der Artikel weitgehend bereinigt und optimiert sein, wenigstens bis auf den Abschnitt "Historisches"--Wilfried Neumaier 22:13, 29. Jun. 2010 (CEST). Auch in diesem Abschnitt habe ich inzwischen einiges verbessert und fundiert. In der UB Tübingen will ich noch den De-Morgan-Artikel nachschlagen und genauere Quellenangaben machen.--Wilfried Neumaier 19:07, 1. Jul. 2010 (CEST)

Varianten

Ab dem Abschnitt Induktion für ganze Zahlen (positiv und negativ) ist es nicht mehr OMAtauglich, das kann es von der Sache nicht sein. Der Abschnitt Varianten vertruege eine Einleitung, wie der letzte Satz ganz unten. Die letzten drei Absaetze finde ich auch eher kryptisch. Vielleicht zu Anfang eine kleine Aufzaehlung von Varianten, insbesondere solcher die einen eigenen Namen haben, falls es das gibt.

Das Beispiel zur Summenformel ist auch sehr schlicht, da es ja noch weitere interessantere Summenformeln gibt. Ich erinnere mich an eine mit einer sechs im Nenner.

In der Integralrechnung gibt es immer wieder Beweise mit raffinierten Umstellungen der Glieder eines Satzes eines Beweises.

Weiter oben zur Menge der Ordinalzahlen habe ich einen Erklaerungsbedarf in der Diskussion des velinkten Artikels angemerkt.

Das Fehlerbeispiel bleibt seltsam, weil Fehler nicht irgendwie allgemeingueltig zu behandeln sind.

-- Room 608 13:58, 5. Jul. 2010 (CEST)

Ja Fehler sind nicht allgemeingültig. Das sind auch keine typischen Fehler, wie der ursprüngliche Untertitel "Häufige Fehler" nahelegte, sondern an den Haaren herbeigezogene, konstruierte Fehler. Ich habe mich zwar bemüht, diesen Punkt etwas zu verbessern und zu glätten, ich halte ihn aber für deplaziert in einem Enzyklopädie-Artikel. Ich verlagere daher den Fehlerabschnitt, der auch in der Bewertungsdiskussion kritisiert wurde, hier in die Diskussion:--Wilfried Neumaier 15:39, 5. Jul. 2010 (CEST)

Naja, die Überschrift ist wohl ein wenig irreführend. Der Sinn dieses Abschnittes soll wohl sein, zu zeigen, dass sowohl Induktionsanfang als auch Induktionsschritt notwendig sind. Die Frage, ob man den Beweis durch Weglassen eines Schrittes vereinfachen könnte, ist ja durchaus berechtigt. --NeoUrfahraner 15:48, 5. Jul. 2010 (CEST)

OK, das soll wohl der Sinn sein, mindestestens beim ersten Beispiel. Beim zweiten aber nicht, denn der enthält ja sowohl einen Induktionsanfang wie einen Induktionsschritt, der halt unerlaubte Argumente (Scheinargumente) benützt. Wenn Dir die Sache wichtig ist, mach doch einfach einen Verbesserungsvorschlag. Wenn er überzeugt, kann man ihn in den Artikel wieder einbauen. Den zur Debatte stehenden Artikeltext rücke ich etwas ein:--Wilfried Neumaier 15:59, 5. Jul. 2010 (CEST)

Unter der Überschrift == Fehlerhafte Induktionen == stand bisher im Artikel:

Der Induktionsschritt, der Schluss von n auf n+1, kann durchaus funktionieren, ist aber nicht beweiskräfig ohne Induktionsanfang. Das zeigt folgendes Beispiel:

Gilt die Formel $1+2+3+\cdots +n={\frac {n(n+1)}{2}}+7$ für eine natürliche Zahl $\,n$, dann gilt sie auch für $\,n+1$, wie eine leichte Rechnung zeigt. Wegen der Gaußschen Summenformel gibt es aber keinen Induktionsanfang, weshalb diese Rechnung keine vollständige Induktion ist!

Ein lückenhafter Induktionsschritt, der nicht für alle natürlichen Zahlen gilt, macht die Argumentation nichtig. Das belegt folgendes Beispiel:

Die Behauptung "Alle Zahlen sind gleich" scheint folgender Induktionsgang über $\,n$-elementige Zahlenmengen zu beweisen: In einer 1-elementigen Menge sind alle Zahlen gleich, da es nur eine gibt (Induktionsanfang). Sind alle Zahlen einer $\,n$-elementigen Menge gleich, dann sind auch alle Zahlen einer $\,n+1$-elementigen Menge $\,M$ gleich (Induktionsschritt), denn wird aus $\,M$ eine Zahl $\,x$ entfernt, dann entsteht eine $\,n$-elementige Menge, in der nach Voraussetzung alle Zahlen gleich sind. Wird $\,x$ wieder hinzugefügt und eine andere Zahl $\,y$ entfernt, dann sind wieder alle Zahlen der Restmenge gleich. Es muss daher $\,x=y$ gelten; also sind alle Zahlen der Menge gleich.

Der Argumentationsfehler liegt darin, dass man nur dann verschiedene Zahlen $\,x$ und $\,y$ entfernen kann, wenn die Menge mindestens 2 Elemente hat. Der Induktionsschritt gilt also tatsächlich nur für $n\geq 2$. Der bewiesene Induktionsanfang nützt nichts, da der Induktionsschritt nicht auf $\,n=1$ anwendbar ist.

Bei der Frage, ob's wichtig ist, enthalte ich mich der Stimme. --NeoUrfahraner 16:51, 5. Jul. 2010 (CEST)

Eine Rückfrage an Room 608: Was ist im Artikel genau kryptisch? Komplett alle drei letzten Varianten oder nur gewisse Dinge darin?--Wilfried Neumaier 23:34, 5. Jul. 2010 (CEST)

Die Absaetze gehen so in das Spezielle, dass ein unbedarfter Leser (Laie) sie fuer unverstaendlich halten muss. Es wird ja in einer Enzyklopaedie wegen ihrer vermeintlichen Allgemeinverstaendlichkeit nirgendwo explizit gesagt, dass man ein spezielles Thema erst zu schaetzen beginnen kann, wenn man einen ersten Versuch damit umzugehen, gestartet hat. -- Room 608 00:08, 6. Jul. 2010 (CEST)

Eben habe ich die kryptischen Varianten anschaulicher formuliert und die Spezialdaten in die Fußnote verbannt. Kann man's so lassen?--Wilfried Neumaier 08:17, 6. Jul. 2010 (CEST)

Die holprige Induktion mit mehreren Anfangswerten ist mir auch gerade aufgefallen. Ich finde es ja viel wichtiger, dass sie mit Zwischenschritten arbeitet, als dass man zwei Induktionsanfaenge braucht. -- Room 608 09:02, 6. Jul. 2010 (CEST)

Sachlich stimmt es schon. Ich habe etwas umformuliert. Ist die jetzige Formulierung besser? Gibt es nach dieser Bereinigung noch etwas Kryptisches?--Wilfried Neumaier 09:28, 6. Jul. 2010 (CEST)

Ich finde jetzt alles einwandfrei lesbar und ich behalte den Ueberblick dabei. -- Room 608 09:46, 6. Jul. 2010 (CEST)

Zur Änderung [2] und der angeblich besseren expliziten Quantifizierung

Gehen wir von

$A(m){,}\quad n\in \mathbb {N} \land n\geq m\land A(n)\Rightarrow A(n+1)\ \vdash \forall n\in \mathbb {N} \colon (n\geq m\Rightarrow A(n))$

aus.

$m$ ist hier genauso frei wie das $n$ in $\mathbb {N} \land n\geq m\land A(n)\Rightarrow A(n+1)$.

Man muss sich also eine Regelung überlegen, unter welchen Umständen ungebundene Variablen wie gebunden werden. Eine Möglichkeit ist: Nimm den umgebenden Text. Wenn der nichts liefert, pro Aussage top-level all-quantifizieren.

Das funktioniert hier, aber wenn obige Formel in andere Kontexte übertragen wird, dann nicht mehr. Beispiel: In einem Kontext, wo $A(n)=n<10$, $m=0$, $n=7$ könnte man beweisen, dass alle natürlichen Zahlen kleiner als 10 sind. Das kann man ja nicht wollen.

Hingegen, mit expliziter Quantifizierung ist die Gesamtformel $A(m){,}\quad \forall n\in \mathbb {N} \colon (n\geq m\land A(n)\Rightarrow A(n+1))\ \vdash \forall n\in \mathbb {N} \colon (n\geq m\Rightarrow A(n))$ immer wahr oder (bei nicht gebundenem $m$ oder $A$) bedeutungslos. --Daniel5Ko 02:10, 30. Sep. 2011 (CEST)

Wenn eine Formel mit freier Variable vor dem Ableitungsoperator steht, dann muss diese Formel auch für eine freie Variable bewiesen sein, man kann ja nicht einfach irgend einen Kontext dazu-fantasieren. Man kann ja in der Prädikatenlogik, die als Rahmen natürlich vorausgesetzt ist, eine bewiesene Formel mit freier Variable per Für-Alle-Einführung stets quantifizieren. Also ergibt sich automatisch die kompliziertere Voraussetzung. Die kompliziertere Formel ist streng formal betrachtet unnötig. Daher bin ich für die einfachere Form.--Wilfried Neumaier 17:28, 30. Sep. 2011 (CEST)

Wie bereits gesagt: wenn man nur die Schlussregel betrachtet, ist $m$ ist auch frei. Nach dem, was du schriebst, könnte ich sagen: Die Schlussregel lautet eigentlich

$\forall m\in \mathbb {N} \colon A(m){,}\quad \forall n\in \mathbb {N} \colon \forall m\in \mathbb {N} \colon (n\geq m\land A(n)\Rightarrow A(n+1))\ \vdash \forall n\in \mathbb {N} \colon (n\geq m\Rightarrow A(n))$,

wir haben zur "Vereinfachung" nur ein paar Quantoren weggelassen. Diese Schlussregel ist aber ein wenig unsinnig, weil die zweite Voraussetzung gar nicht benötigt wird. --Daniel5Ko 17:59, 30. Sep. 2011 (CEST)

Man kann natürlich einen Kontext auch nicht weg-fantasieren. Im Kontext ist ja die Schlussregel erklärt und m als eine bestimmte natürliche Zahl vorgegeben, dagegen A(n) als Aussage mit unbestimmten n.--Wilfried Neumaier 23:58, 30. Sep. 2011 (CEST)

Die Schlussregel für sich allein sollte Sinn ergeben. Das tut sie jetzt (jedenfalls, wenn man $\mathbb {N}$, $\geq$, $+$ und $1$ nicht auch als frei ansieht). Für die unter diesen Umständen noch freien $m$ und $A$ (und eben nicht $n$) ist die Schlussregel allgemeingültig. Wo ist das Problem? Und was soll zu kompliziert sein? --Daniel5Ko 00:51, 1. Okt. 2011 (CEST)

Das von Dir aufgestellte Prinzip "Die Schlussregel für sich allein sollte Sinn ergeben" würde das Aus für die gängigsten Kalküle bedeuten, etwa die Prädikatenlogik oder Gentzen-Kalküle, die alle durch den Kontext bestimmte Schlussregeln haben.--Wilfried Neumaier 20:16, 2. Okt. 2011 (CEST)

Ich meinte mit "Sinn ergeben": in jedem Kontext korrekt und anwendbar und die intendierte Bedeutung habend, oder bedeutungslos; der regeldefinierende Kontext wird nicht benötigt. (Im konkreten Beispiel kann aufgrund der Benutzung innerhalb der Regel über die freien Bestandteile bereits inferiert werden, dass $A$ ein Prädikat über $\mathbb {N}$ ist, und dass $m\in \mathbb {N}$ sein muss; beide sind aber unter diesen Einschränkungen völlig beliebig) Das funktioniert aber eben nur ohne komplizierte weitere Regelungen, wenn man die Variable im Schritt bindet, wie oben schon dargelegt. --Daniel5Ko 21:02, 2. Okt. 2011 (CEST)

Aus welchem Kontext soll das $n$ denn implizit quantifiziert sein, etwa aus der Definition von Dedekind? Im Kontext könnte man noch fälschlicher Weise $A(n)$ als Bindung des $n$ entdecken. Ich verstehe die Formel als Alternative zur sprachlichen Definition. Wenn die Definition aber zur Deutung einer anders notierten Definition nötig ist, ist das unlogisch. Zudem finde ich es sogar einfacher, wenn das $n$ explizit quantifiziert wird, denn das kann man strukturell gut mit der sprachlichen Beschreibung abgleichen. --Zahnradzacken 22:41, 2. Okt. 2011 (CEST)

Ja, es ist einfacher, sicherer und allgemeiner. Vielleicht kann man sich auch noch auf eine andere Syntax einigen. Man kann im vorliegenden Fall ein paar Klammern sparen, wenn man festlegt, dass Quantoren nicht ähnlich wie Präfixoperatoren recht eng binden, sondern ihr Körper ein allgemeiner logischer Ausdruck ist und also "soweit wie möglich nach rechts" geht. In kontemporären Typentheoretikerkreisen (also meist Informatiker) ist das einigermaßen verbreitet. Auch ist die Verwendung von . statt : dort recht üblich. Das sähe dann so aus ($\vdash$ ist kein Bestandteil von logischen Ausdrücken, "soweit wie möglich nach rechts" endet dort zwangsläufig):

$A(m){,}\quad \forall n\in \mathbb {N} .\ n\geq m\land A(n)\Rightarrow A(n+1)\ \vdash \ \forall n\in \mathbb {N} .\ n\geq m\Rightarrow A(n)$

Wilfried: Nimmt das vielleicht etwas von der wahrgenommenen Kompliziertheit weg?

Wie dem auch sei, unabhängig von der Syntax halte ich die explizite Quantifizierung auch aus didaktischen Gründen für sinnvoll: Es soll insgesamt bewiesen werden, dass ein Prädikat für jede natürliche Zahl gilt. Eine der Voraussetzungen, die das ermöglichen, ist ebenfalls ein Prädikat, das für jede natürliche Zahl gelten soll. Das nimmt erstens den Eindruck weg, dass wir hier Magie betreiben, und zweitens ist es so ein ganz normaler Fall, und nicht irgend etwas seltsames, wenn zum Beweis der zweiten Voraussetzung ebenfalls Induktion benötigt wird. --Daniel5Ko 00:50, 3. Okt. 2011 (CEST)

Die Vollständige Induktion - zweischrittig, dreischrittig, vierschrittig?

1. Induktionsanfang
2. Induktionsvoraussetzung (-Behauptung)
3. Induktionsschluss

In manchen Lehrbüchern wird nur in zwei Schritte eingeteilt. Doch die bloße Unterscheidung in Induktionsanfang und Induktionsschritt wird der Beweisführung nicht gerecht, da der sogenannte Induktionsschritt grundsätzlich die Induktionsvoraussetzung für n und (n+1) erfordert (was meist schnell behauptet werden kann) aber am mühevollen Induktionsschluss scheitern kann. --Walmei (Diskussion) 12:50, 25. Aug. 2018 (CEST)

@Walmei: Da es bei dieser Diskussion über die Vollständige Induktion um sprachliche Feinheiten geht, möchte ich Dich gerne bitten, die Literaturstelle, die Du anziehst, einzuscannen oder einzutippen.
M.E. sicherlich falsch ist, dass »der sogenannte Induktionsschritt grundsätzlich die Induktionsvoraussetzung für n und (n+1) erfordert«, wie Du schreibst. Induktionsvoraussetzung ist immer nur die Aussage bezogen auf den oder die Vorgänger, hier also Aussage(n). Und Induktionsbehauptung die Aussage bezogen auf den Nachfolger, hier also Aussage(n+1). M.a.W.: geht es bei dem Beweis mittels Vollständiger Induktion um die zwei Zahlen n und (n+1), dann nimmt die Aussage(n) die Rolle der Voraussetzung ein und die Aussage(n+1) die Rolle der Behauptung. [Als lesbarer Text unterscheiden sich die beiden nur im n und (n+1), also aussagemäßig eigentlich überhaupt nicht, so dass man vielleicht sogar auf die Idee kommen könnte: Induktionsvoraussetzung = Induktionsbehauptung.]
Über weitere Details gerne nach Deinem wörtlichen Zitat. --Nomen4Omen (Diskussion) 15:58, 25. Aug. 2018 (CEST)

Danke für die prompte Antwort.

Hier ein Auszug aus: Mathematik, Lehrbuch für Klasse 11, 4. Auflage, Volk und Wissen, Volkseigener Verlag Berlin.- 1985, S.  32-33

"Beweist man eine Aussage der Form "Für alle natürlichen Zahlen n gilt H(n)" durch vollständige Induktion, so geschieht dies ... in zwei Schritten:

1. Induktionsanfang

Bilden vo H(n₀) für eine möglichst kleine natürliche Zahl n₀ ; ...

2. Induktionsschritt

Zeigen, dass für alle k gilt: Wenn H(k), so H(k+1) Im Induktionsschritt ist also eine Wenn-so-Aussage zu beweisen, am übersichtlichsten in der uns bekannten Weise:

• Bilden von H(k) als Induktionsvoraussetzung;
• Bilden von H(k+1) als Induktionsbehauptung;
• Nachweis, dass H(k+1) aus H(k) folgt (Induktionsbeweis)."

Ich finde die Einteilung in: 1. Induktionsanfang und 2. Induktionsschritt weniger wichtig als die Dreischritttigkeit des Induktionsschrittes! Erst durch Letzteres kommt der Beweis zur Geltung. --Walmei (Diskussion) 20:27, 25. Aug. 2018 (CEST)

@Walmei: Willst Du darauf hinaus, dass wir in der Schule die 3 Schritte:
  1. Voraussetzung: H(k)
  2. Behauptung: H(k+1)
  3. Beweis: H(k) ==> X1 ==> X2 ==> ... ==> H(k+1)
gelernt haben? Nun, da gibt es doch die vielen, vielen Stellen in der math. Literatur, wo einfach,
    wenn Behauptung zutrifft,
    dann gilt Aussage.
hingeschrieben wird. Evtl mit einem Nachklapp, weil »==> X1 ==> X2 ==> ... ==>«. Dein zweiter Schritt, das »Bilden (oder Hinschreiben) von H(k+1) als Induktionsbehauptung« ist doch gar keine geistige Leistung, es ist doch ein pures Ersetzen von k durch (k+1) !
Was meinst Du mit Letzteres genau: den »Nachweis, dass H(k+1) aus H(k) folgt (Induktionsbeweis)« oder »die Dreischritttigkeit des Induktionsschrittes« ? --Nomen4Omen (Diskussion) 22:48, 25. Aug. 2018 (CEST)

Mit Letzteres meine ich die Dreischritttigkeit des Induktionsschrittes. Und ich bin ja deiner Meinung, dass die Induktionsbehauptung (für n+1) keine geistige Leitung ist. --Walmei (Diskussion) 22:58, 25. Aug. 2018 (CEST)

Dann is ja gut. --Nomen4Omen (Diskussion) 23:01, 25. Aug. 2018 (CEST)

Starke Induktion

1. Ich finde das Thema wichtig. Insbesondere bei Rekursionsformeln kommt es vor, dass auf mehr Indizes als nur den einen direkten Vorgänger zugegriffen wird.
2. Der neue Titel (Name?) „Starke Induktion“ suggeriert, dass er von einem wichtigen Menschen vergeben wurde. Wenn dem so ist, dann bitte im Artikel auch belegen. Wenn aber nicht, dann ist mir der alte Titel „Vollständige Induktion mit stärkeren Voraussetzungen“ oder „Vollständige Induktion mit mächtigerer Induktionsannahme“ od.ä. lieber.
3. Es ist trivial, mit diesem (stärkeren) Induktionsprinzip Theoreme abzuleiten, die mit $\operatorname {A} (n)\implies \operatorname {A} (n+1)$ auskommen.
4. Kann man aber auch aus $\forall n\in \mathbb {N} :\operatorname {A} (n)\implies \operatorname {A} (n+1)$ das stärkere $\forall i\in \mathbb {N} :{\bigl (}\forall j\in \mathbb {N} :j\geq i_{0}\wedge j<i\wedge \operatorname {A} (j){\bigr )}\implies \operatorname {A} (i)$ herleiten ?
   Wenn das einfach geht, dann würde ich es im Artikel willkommen heißen. Ansonsten wäre eine Literaturstelle angenehm.

--Nomen4Omen (Diskussion) 09:53, 1. Sep. 2018 (CEST)

@Daniel5Ko: Nachtrag zu Obigem:
Die Aussage $\operatorname {A} (0)$ muss schon bewiesen werden. Ihr Nachweis hat auch eine ganz andere Begründung, da es bei ihr keine „Induktionsvoraussetzung“ gibt (Beispiel: Vollständige Induktion). [In Klausel-Normalform lese ich, dass die leere Konjunktion den Wahrheitswert WAHR (TRUE) ergibt. Damit kann ja wohl $\operatorname {A} (0)$ nicht schon bewiesen sein.] --Nomen4Omen (Diskussion) 17:20, 3. Sep. 2018 (CEST)

@Nomen4Omen Auch ich bin der Meinung, dass der Beweis der "starken Induktion" übersichtlicher wird, wenn man ihm einen Induktionsanfang hinzufügt. Siehe die Diskussion auf der Diskussionsseite von Daniel5K --Joachim Mohr (Diskussion) 11:19, 6. Sep. 2018 (CEST)

Hallo Nomen4Omen! Die Bemerkung "ggf. in einer Fallunterscheidung" halte ich für überflüssig. Warum sollte man A(0) durch Fallunterscheidung beweisen? --Joachim Mohr (Diskussion) 15:27, 6. Sep. 2018 (CEST)

@Joachim Mohr: Also so großartig wichtig ist das nicht. Aber nimm den Fall der Fibonacci-Folge: Da musst Du bei Index 1 und 2, bei denen man direkt beweist, ganz anders vorgehen als bei den Indizes ≥2, wo man auf die Rekursionsgleichung zurückgreift. Ich dachte, der Leser sieht diesen Bedarf sofort. (Im der direkt davor stehenden Fußnote [19] ist der Fall $n=n_{0}$ auch gewissermaßen extra behandelt.) Außerdem habe ich das bei Deiser auf S. 268 und im Informatik-Kontext gesehen. [Letzteres kriege ich aber im Moment nicht hin.] Wenn Du meinst, kann man das Fibonacci-Beispiel näher in den Abschnitt starke Induktion holen und dort die 2 Induktionsanfänge (ín Rekursion und Formel von Moivre/Binet) vorführen oder umgekehrt dort leicht ändern und gezielt auf die starke Induktion verweisen.
Richtig gut finde ich bei der starken Induktion, dass der Induktionsanfang im Schema gar nicht vorkommt und man sich so auf die Zahl der Anfänge überhaupt nicht festlegen muss. --Nomen4Omen (Diskussion) 19:18, 6. Sep. 2018 (CEST)

So wie Du es formuliert hast ...

"Der Induktionsanfang, d. i. $A(n_{0})$, ist im Induktionsschritt mit der für $n=n_{0}$ leeren Induktionsvoraussetzung nachzuweisen – ggf. in einer Fallunterscheidung."

... meint man, man müsse für $A(n_{0})$ schon gegebenenfalls eine Fallunterscheidung machen.

Du meinst aber sicher: Man muss als Induktionsanfang $A(n_{0})$ und gegenenfalls weitere Angfangsaussagen $A(n_{0}+1)$, $A(n_{0}+2)$ ... nachweisen.

Gruß --Joachim Mohr (Diskussion) 09:27, 7. Sep. 2018 (CEST)

Nun ja, einen als Induktionsanfang deklarierten (starken) Induktionsanfang gibt es hier (in der starken Induktion) nicht (mehr). Es gibt nur den Induktionsschritt. Der umfasst Beides: das, was früher im »gewöhnlichen« Teil des Artikels als Induktionsanfang bezeichnet wurde, und eben auch das, was früher im Artikel als Induktionsschritt bezeichnet wurde. Der starke Induktionsschritt zerfällt also, (zumindest, wenn es einen echten nicht-leeren (gewöhnlichen) Induktionsanfang im alten Sinn gibt) in zwei Teile, die sich durch eine Fallunterscheidung trennen lassen. (Letztlich muss man, wie Du sagst, diese Induktionsanfänge $A(n_{0})$ etc. in genau derselben Weise wie bei der gewöhnlichen V.I. nachweisen – egal wie man sie etikettiert.) Wenn Du das klarer formulieren kannst, dann bitte ich Dich darum. --Nomen4Omen (Diskussion) 14:03, 7. Sep. 2018 (CEST)

Noch eine kleine Frage. Was ist eigentlich eine "leere Aussage". Kannst Du mir eine hinschreiben? --Joachim Mohr (Diskussion) 16:17, 7. Sep. 2018 (CEST)

Im hiesigen Kontext meine ich mit leerer Aussage: $\bigwedge _{m=n_{0}}^{n_{0}-1}\operatorname {A} (m)=\bigwedge _{m\in \emptyset }\operatorname {A} (m)$. Vielleicht sollte man besser von einer leeren verallgemeinerten Konjunktion sprechen? (Das ist ja immer eine Aussage! Es gibt aber auch die leere verallgemeinerte Disjunktion, die dagegen als FALSCH auswertet.) Dass sie als WAHR auszuwerten ist, steht in Klausel-Normalform. [FALSCH ist das neutrale Element der Disjunktion und WAHR das der Konjunktion.] Dass die Implikation ${\bigl (}{\mathsf {WAHR}}\implies \operatorname {A} (n_{0}){\bigr )}$ genau dann zutrifft, wenn $\operatorname {A} (n_{0})$ zutrifft, steht in Subjunktion#Klassische Subjunktion. --Nomen4Omen (Diskussion) 20:09, 7. Sep. 2018 (CEST)

Danke für die Erläuterungen ... Wie es bezüglich Produkt und Summe die neutralen die Elemente 1 und 0 sind. Trotz Studium der Logik (Non-Standard Anaylysis) ist mir das neutrale Element der Konjunktion und Disjunktion nie begegnet. Insofern halte ich bei der starken Induktion einen Hinweis darauf für unverzichtbar. Vor dem Unterricht der vollständige Induktion sollte m.E. so wie so auch immer ein Stück weit formale Logik unterrichtet werden. Siehe https://kilchb.de/vollstind.php --Joachim Mohr (Diskussion) 08:57, 8. Sep. 2018 (CEST)

Nur pädagogisches Hilfsmittel?

Das soll wohl die Bewertung "meiner vierschrittigen" Vollständigen Induktion sein. Ich schreibe von gleichrangigen Schritten. Gleichrangig bedeutet hier unentbehrlichen (notwendigen und nicht pädagogischen oder gar beliebigen) Schritten. Dein letzter Abschnitt folgt sogar genau dieser Vierschrittigkeit. Zufällig? Ich muss dir danken. Vielleicht finden sich noch andere, die ich für diese Logik gewinnen kann.--Walmei (Diskussion) 21:50, 28. Aug. 2018 (CEST)

Ein Beweis über die vollständigen Induktion erfordert zwei Schritte. Dies folgt aus dem Induktionsaxiom:

Gilt A(1) und folgt aus A(n) für jede Zahl n>=1 die Gültigkeit von A(n+1), dann gilt die Formel A(n) für jede natürliche Zahl n>=1. 

Betrachten wir mal das Beispiel A(n): 1+2+3+...+n =n*(n+1)/2 (n>=1)

I Induktionswanfang: Für n=1 ist A(1): 1=1*2/2 eine wahre Aussage

II Induktionsschritt: Für n>=1 gilt die Folgerung A(n)=>A(n+1), denn 1+2+3+...+n+n+1=(1+2+3+...+n)+n+1=n*(n+1)/2+n+1=...=(n+1)*(n+2)/2 q.e.d.

Du würdest gerne den Induktionschritt aufteilen in:

II. Induktionsschluss

IIa. Induktionsvoraussetzung A(n): 1+2+3+...+n =n*(n+1)/2

IIb. Induktionsbehauptung A(n+1): 1+2+3+...+n+n+1=(n+1)*(n+2)/2

IIc. Induktionsschritt: A(n+1): 1+2+3+...+n+n+1=(1+2+3+...+n)+n+1=n*(n+1)/2+n+1=...=(n+1)*(n+2)/2

Das hat den Vorteil, dass der Schüler zunächst A(n+1) formulieren muss als Ziel eines nachfolgenden Beweises. Das nenne ich pädagogisch. --Joachim Mohr (Diskussion) 11:35, 29. Aug. 2018 (CEST)

Schade, dass du nicht auf meine Argumentation eingehst.

Dein Hinwies auf das sogenannte "Induktionsaxiom" ist nicht stichhaltig und steht auch nicht im Widerspruch zur Vierschritttigkeit.

Mein Vorschlag für den Artikel:

Gilt A(1) und folgt aus A(n) für jede Zahl n>=1 die Gültigkeit von A(n+1), dann gilt die Formel A(n) für jede natürliche Zahl n>=1. Der Beweis, dass die Aussage (Behauptung) $\operatorname {A} (n)$ für alle $n\geq n_{0}$ ($n_{0}$ meist 1 oder 0) gilt, wird in 4 unentbehrlichen (notwendigen) Schritten durchgeführt:

1. Im Induktionsanfang wird die Aussage $\operatorname {A} (n_{0})$ für eine kleinste Zahl $n_{0}$ formuliert.
2. In der Induktionsbehauptung wird die Aussage $\operatorname {A} (n)$ als Gleichung mit n formuliert.
3. In der Induktionsvorausetzung wird die Aussage $\operatorname {A} (n+1)$ als Gleichung mit (n+1) formuliert.
4. Im Induktionsbeweis wird die Gleichung mit n (Induktionsbehauptung) mit einem geeigneten Übergangsterm in die Gleichung mit (n+1) (Induktionsvoraussetzung) überführt.

--Walmei (Diskussion) 11:55, 29. Aug. 2018 (CEST)

Ich bin ganz klar eher auf der Seite von Joachim Mohr. Walmei hat mal 3, dann mal 4 unentbehrliche (notwendige) Schritte (und kann deshalb? auch keine echte Literaturstelle bringen).
Wirklich entscheidend ist IMHO das Theorem, bspw.

$\sum _{k=1}^{n}k={\frac {n(n+1)}{2}}$

Ob und wie man das beweist, ist Darstellungssache (von mir aus auch "pädagogisch"). Normalerweise werden in einer Enzyklopädie die Beweise nicht gebracht. Man will facts, facts, facts. Und selten Argumentation. In einer Enzyklopädie ist Argumentation ein Extra, das der Autor nach seinem Gusto ausgestalten darf. (Beim Vierfarbensatz würde dewiki gesprengt. Ohne Beweis reichen 16.533 Bytes.) Das darf dann mit deutlich und schulmäßig herausgehobenen 2, 3 oder 4 Schritten geschehen oder, wenn es gelingt, auch in einem Nebensatz, ganz ohne Vollständige Induktion. Die Argumentation sollte leicht zu lesen und zu verstehen ("nach.zu.vollziehen") sein, evtl. für den Fachmann; aber ich meine in Wikipedia sollte man auch einen interessierten Laien in die mathematische Denkweise hineinzulocken versuchen. Ob man das mit deutlich markierten 2, 3 oder 4 Schritten kann, scheint mir eher fraglich.
Abgesehen davon ist der Unterschied zwischen Theorem, Induktionsvoraussetzung und Induktionsbehauptung ohnehin marginal. Vielleicht nicht funktionell, aber zumindest in dem, was der Leser sieht, nämlich textlich. Und langweilen wollen wir ihn auch wieder nicht, den Leser. Dies gilt für die Anwendung der V.I. (als Hilfsmittel) in einem Artikel.
Im hiesigen Artikel dürfen die Komponenten (oben oft Schritte genannt) schon deutlich benannt werden und herauskommen, wobei ihre funktionelle Rolle IMHO das Wichtigste ist – und nicht unbedingt die Anzahl und Reihenfolge. --Nomen4Omen (Diskussion) 14:19, 29. Aug. 2018 (CEST)

Schade, dass ihr nicht auf meine Argumentation eingeht. Joachim hat doch selbst die Vierschrittigkeit genutzt. --Walmei (Diskussion) 19:11, 29. Aug. 2018 (CEST)

---

Meines Erachtens genügt als erste Einführung in die vollstandige Induktion:

"Der Beweis, dass die Aussage $\operatorname {A} (n)$ für alle $n\geq n_{0}$ ($n_{0}$ meist 1 oder 0) gilt, wird daher in zwei Etappen durchgeführt:

1. Im Induktionsanfang wird die Aussage $\operatorname {A} (n_{0})$ für eine kleinste Zahl $n_{0}$ hergeleitet.
2. Im Induktionsschritt wird die Aussage $\operatorname {A} (n+1)$ aus der Aussage $\operatorname {A} (n)$ für $n\geq n_{0}$ hergeleitet."

Wie der Induktionsschritt dann noch weiter aufgebröselt wird, ist dem Geschick des Autors überlassen: Meine Methode möchte ich am folgenden Beispiel erläutern (und da muss ich Walmai nun zustimmen, dass der Induktionsschritt hier aus drei Etappen besteht). Behauptung:

A(n) 1 + 2 + 4 + 8 + ... + 2^n = 2^(n-1) - 1 ("^" steht für "hoch")

Beweis:

Induktionsanfang:

A(1): 1 + 2^1 = 2^2 - 1 (wahr, Probe stimmt)

Induktionsschritt:

Sei 1 + 2 + 4 + 8 + ... + 2^n = 2^(n+1) - 1. Das ist die Aussage A(n)

Daraus ist herzuleiten:

1 + 2 + 4 + 8 + ... + 2^n + 2^(n+1) = 2^(n+2) - 1. Das ist die Aussage A(n+1)

Herleitung:

Aus 1 + 2 + 4 + 8 + ... + 2^n = 2^(n+1) - 1 folgt:

1 + 2 + 4 + 8 + ... + 2^n + 2^(n+1) = 2^(n+1) - 1 + 2^(n+1) = 2·2^(n+1) - 1 = 2^(n+2) - 1

q.e.d --Joachim Mohr (Diskussion) 15:51, 30. Aug. 2018 (CEST)

Danke Joachim, du bestätigst die Vierschritttigkeit: Induktonsanfang + "Induktionsschritt hier aus drei Etappen" (deine Worte, von oben)

Jetzt nur noch "...ist dem Geschick des Autors überlassen..." durch "notwendig" ersetzen. --Walmei (Diskussion) 16:53, 30. Aug. 2018 (CEST)

---

Wir sind uns doch einig, dass man es wie Benutzer:Walmei machen kann.
Nur meint er, dass man es wie er machen muss.

Beispiele von Vollständiger Induktion in dewiki, die es NICHT mit dem Schema von Benutzer:Walmei halten:

1. Bernoullische Ungleichung#Beweis über vollständige Induktion
2. Josephus-Problem#Lösung
3. Tschebyscheff-Ungleichung (Arithmetik)#Beweis mit vollständiger Induktion
4. Taylorreihe#Eigenschaften
5. Jensensche Ungleichung#Beweis per Induktion
6. Fibonacci-Folge#Induktiver Beweis
7. Taylor-Formel#Annäherung durch Polynome vom Grad n

Biespiele, die ein Beweisschema nach der Art von Benutzer:Walmei bringen:

1. Wikibooks Beweisarchiv: Algebra: Ringe: Binomischer Lehrsatz

Das sind ein paar Stichproben in der Reihenfolge, wie ich sie per wiki-Recherche angetroffen habe. In der echten dewiki soweit kein Beispiel für ihn. --Nomen4Omen (Diskussion) 19:29, 30. Aug. 2018 (CEST)

Danke Nomen, ich meine an der Vierschritttigkeit kommt keiner vorbei. Schon # Bernoullische Ungleichung#Beweis über vollständige Induktion zeigt das. --Walmei (Diskussion) 21:51, 30. Aug. 2018 (CEST)

---

@Walmei: Das rührt mich jetzt doch zutiefst, dass Du Deine Vierschritttigkeit im von mir angeführten Beispiel Bernoullische Ungleichung#Beweis über vollständige Induktion wiedererkannt hast. Wir haben Dich ganz zu Unrecht für einen Sturling gehalten. Dabei hast Du schon in Deinem Post vom 11:55, 29. Aug. 2018 (CEST) zu erkennen gegeben, dass Du es so genau nicht nimmst, indem Du schreibst [Zitat]:

1. Im Induktionsanfang wird die Aussage $\operatorname {A} (n_{0})$ für eine kleinste Zahl $n_{0}$ formuliert.
2. In der Induktionsbehauptung wird die Aussage $\operatorname {A} (n)$ als Gleichung mit n formuliert.
3. In der Induktionsvorausetzung wird die Aussage $\operatorname {A} (n+1)$ als Gleichung mit (n+1) formuliert.
4. Im Induktionsbeweis wird die Gleichung mit n (Induktionsbehauptung) mit einem geeigneten Übergangsterm in die Gleichung mit (n+1) (Induktionsvoraussetzung) überführt. [Zitatende]

Hier hast Du großzügig Induktionsbehauptung und Induktionsvorausetzung vertauscht (verwechselt ??), denn einem wirklich Strenggläubigen muss klar sein, dass IMMER die Induktionsvoraussetzung VOR der Induktionsbehauptung kommen muss.

Im von mir herangezogenen Beispiel Bernoullische Ungleichung#Beweis über vollständige Induktion ist es noch ein bisschen anders: Da kommt in Standard-Reihenfolge als erstes der Induktionsanfang und als zweites die Induktionsvoraussetzung (hier wunderbar konjunktivisch formuliert [»gelte«] als „Induktionsannahme“). Dann kommen einige Rechnungen in Form von Ungleichungen (am besten aufzufassen als Dein Schritt Nummer 4 ? Oder 3 bis 7 oder was ?) und ganz zum Schluss die damit bewiesene Induktionsbehauptung. Frage an Dich: Ist das jetzt der Schritt Nummer 3 oder 4 oder gar Schritt Nummer 8 ? Bitte wirklich dort nachsehen!

Es tut richtig gut, dass Du einräumst, dass von den »unentbehrlichen und notwendigen« Schritten mal einer auch fehlen oder in der falschen Reihenfolge sitzen kann. Wenn Du das früher und vor allem deutlicher gesagt hättest, hättest Du uns viel Zeit und einige Kilobyte Dialog erspart. [Denn da wären wir uns von vorn herein einig gewesen.] --Nomen4Omen (Diskussion) 16:40, 31. Aug. 2018 (CEST)

Hallo Nomen, die Notwendigkeit der Vierschritttigkeit ist doch gut zu erkennen an der Abfolge A(0)→A(n)→A(n+1)→Beweis. Bei den Bezeichnungen der einzelnen Schritte, insbesondere des 2. und 3. Schrittes gibt es Unstimmigkeiten. Und wenn in Darstellungen mal vereinfacht wird oder wie du zu erkennen glaubst sogar Schritt Nummer 8 gesehen werden kann, dann wäre zu prüfen, ob tatsächlich auf die Logik der Abfolge A(0)→A(n)→A(n+1)→Beweis verzichtet werden konnte. Ich kenne kein Beispiel für die Vollständige Induktion, dass auf die Logik der Abfolge A(0)→A(n)→A(n+1)→Beweis verzichten kann.--Walmei (Diskussion) 22:16, 4. Sep. 2018 (CEST)

Die Abfolge A(0)→A(n)→A(n+1)→Beweis ist absolut nicht zwingend. Man muss nur zeigen:

• A(0) und
• Aus A(n) folgt A(n+1) (n>=0) Basta!

--Joachim Mohr (Diskussion) 18:47, 4. Nov. 2018 (CET)

Hallo Joachim, Basta ist keine Quelle! Die Abfolge A(0)→A(n)→A(n+1)→Beweis ist absolut zwingend! Dein "Basta" wird daran wohl nichts ändern. Schau dir "deine" obigen Beispiele an! Walmei (Diskussion) 10:21, 5. Nov. 2018 (CET)

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 (nicht signierter Beitrag von 84.58.231.186 (Diskussion) 17:22, 2. Sep. 2006 (CEST))

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)

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. (nicht signierter Beitrag von 84.58.210.166 (Diskussion) 21:05, 21. Feb. 2006 (CET))

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. (nicht signierter Beitrag von 84.169.242.156 (Diskussion) 12:34, 25. Jun. 2006 (CEST))

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. (nicht signierter Beitrag von NeoUrfahraner (Diskussion | Beiträge) 14:21, 24. Feb. 2005 (CET))

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)

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)

Eingefügt: AF666 20:47, 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 (nicht signierter Beitrag von Bastian1981 (Diskussion | Beiträge) 23:47, 3. Mai 2006 (CEST))

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)

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... (nicht signierter Beitrag von 85.178.83.163 (Diskussion) 22:58, 16. Okt. 2006 (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)

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? (nicht signierter Beitrag von 84.58.220.29 (Diskussion) 22:52, 22. Aug. 2006 (CEST))

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 (nicht signierter Beitrag von 84.58.231.186 (Diskussion) 17:22, 2. Sep. 2006 (CEST))

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

Der Link ist leider nicht mehr erreichbar und unter http://web.archive.org nicht archiviert. Schade. ThomasPusch (Diskussion) 16:11, 15. Mai 2017 (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

(nicht signierter Beitrag von 84.58.204.64 (Diskussion) 20:08, 22. Feb. 2006 (CET))

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.

Zwischen Induktionsschritt und Induktionsschluss muss sehr wohl unterschieden werden. Ein Beweis mittels vollständiger Induktion verläuft nämlich so:

1. Man zeigt die Gültigkeit von $A(1)$ (das ist der Induktionsanfang);

2. Man zeigt die Gültigkeit von $\bigwedge _{n\in \mathbb {N} }(A(n)\Longrightarrow A(n+1))$ (das ist der Induktionsschritt);

  Damit hat man bis jetzt die Gültigkeit von $A(1)\wedge \bigwedge _{n\in \mathbb {N} }(A(n)\Longrightarrow A(n+1))$ gezeigt.

3. Gemäß dem 5. Peano-Axiom (dessen Gültigkeit vorausgesetzt wird) hat man ${\Big (}A(1)\wedge \bigwedge _{n\in \mathbb {N} }(A(n)\Longrightarrow A(n+1)){\Big )}\Longrightarrow \bigwedge _{n\in \mathbb {N} }A(n)$;

4. Nach dem logischen Gesetz modus ponens schließt man nun, dass jetzt $\bigwedge _{n\in \mathbb {N} }A(n)$ gilt, und dies ist der Induktionsschluss, der allerdings in Beweisen oft nicht mehr ausdrücklich erwähnt wird. Analyx (Diskussion) 12:26, 30. Aug. 2014 (CEST)

Hallo Analyx! Diese Sprechweise habe ich so noch nie bewusst gesehen. Hast du eine Quelle dafür? Ich kenne das nur so, dass der 2. Schritt entweder Induktionsschritt genannt wird (z.B. Forster: Analysis I) oder Induktionsschluss (z.B. Königsberger: Analysis I). Aber beides zusammen für unterschiedlicher Schritte kenne ich nicht. Auch eine Google-Books-Suche [3] gibt Induktionsschluss nur als Bezeichnung für den 2. Schritt. Grüße -- HilberTraum ⟨d, m⟩ 18:05, 30. Aug. 2014 (CEST)

Hallo HilberTraum, als Quelle kann ich Ihnen das exzellent geschriebene Buch Einführung in die mathematische Logik von Hans Hermes, B. G. Teubner Stuttgart, 2. Aufl. 1969, Verlags-Nr.2201, Seiten 13 u. 149, anbieten (ich habe bei H. Hermes Logik studiert), des Weiteren das Buch von Justus Diller / A. Breitkopf Differential- und Integralrechnung I , TR-Verlagsunion München 1972, ISBN 3-8058-0372-9, Seite 16 (J. Diller war einer der Nachfolger von H. Hermes an der Univ. Münster); dieses Buch übertrifft das von Ihnen erwähnte Forster-Buch bei Weitem, was Verständlichkeit, formale und logische Sauberkeit angeht. Analyx (Diskussion) 20:38, 30. Aug. 2014 (CEST)

Danke für die genauen Literaturangaben, da schau ich morgen mal rein. -- HilberTraum ⟨d, m⟩ 09:39, 31. Aug. 2014 (CEST)

Gültigkeit der Gaußschen Herleitung

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? (nicht signierter Beitrag von Ce2 (Diskussion | Beiträge) 23:46, 28. Nov. 2003 (CET))

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 (nicht signierter Beitrag von 212.202.53.9 (Diskussion) 02:13, 5. Dez. 2003 (CET))

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 [4]), 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är. 2004 (CET)

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är. 2004 (CET)

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)

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 ... (nicht signierter Beitrag von 17:49, 26. Okt. 2006 (CEST) (Diskussion | Beiträge) )

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

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)

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)

Kann das mal jemand verständlich für Hauptschüler erklären?

"Schließlich der Induktionsschluss: Damit ist die Aussage A ⁡ ( n ) {\displaystyle \operatorname {A} (n)} {\displaystyle \operatorname {A} (n)} für alle n ≥ 1 {\displaystyle n\geq 1} n\geq 1 bewiesen"

Wie? was?

Was ich bisher verstanden habe: - ich habe eine Formel, deren Richtigkeit ich beweisen soll - in der Formel gibt es nur 1 Unbekannte: n - wenn ich beweise, daß die Formel bei n=1 stimmt, dann prüfe ich noch, ob sie auch bei n=2 stimmt - wenn ja, stimmt sie auch für N=3, N04, usw. ...

Frage: warum kann man einfach so annehmen, daß die Formel auch bei N=3 stimmt? Gibt es keine Formeln, die irgendwann irgendwie "unregelmäßig" werden ... hm... schwer zu beschrieben.

Irgendwie stelle ich mir das so vor: eine Gerade hat eine kontinuierliche Steigung. Aber eine Exponentialfunktion nicht mehr. Eine Hyperbel / Parabel ist dann ganz sonderbar .... wieso kann ich aber bei dieser vollständigen Induktion quasi von einer Geraden ausgehen - davon ausgehen, daß wenn es bei N=1 und N=2 stimmt, auch bei N=3264455 stimmen wird..... ??? --91.48.77.50 00:09, 11. Jun. 2020 (CEST)

Hallo! Die vollständige Induktion war mal ein Thema in der Oberstufe des Gymnasiums. Man hat sie wieder herausgenommen, weil sie doch ein tieferes Verständnis der Aussagenlogik voraussetzt. Ich erinnere mich noch gut an mein erstes oder zweites Semester des Studiums der Mathematik, wo ich zunächst das Prinzip nicht verstand (naja; die Aufgaben löste ich nach vorgegebenem Schema). Schau Dir mal den folgenden Aufsatz an: https://kilchb.de/vollstind.php. An einer Rückmeldung wäre ich interessiert. Gruß --Joachim Mohr (Diskussion) 08:40, 11. Jun. 2020 (CEST)

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)

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)

kompliziertes Beispiel

Das Beweisbeispiel für die Ungleichung ist kompliziert und unwichtig und belastet nur den Artikel. Im verlinkten Artikel, wo die Ungleichung benötigt werden könnte, gibt es mehre Beweise, die völlig ausreichen, zum Beispiel ein Beweis mit der bernoullischen Ungleichung. Letztere ist im Artikel erwähnt, aber nicht durchführt, was stört (frustriert). Besser wäre es dieses einfachere Beispiel hier zu bringen.--Wilfried Neumaier 21:58, 1. Jul. 2010 (CEST)

Der ist nicht kompliziert sondern nur verwirrend, und man fragt sich, wozu brauch ich das. Die Summe von (allen) Zahlen und ihren Kehrwerten? -- Room 608 05:12, 2. Jul. 2010 (CEST)

Zur Frage, wozu man das braucht: es ist im Prinzip genau die Ungleichung vom arithmetischen und geometrischen Mittel, aber so "normiert", dass man sie (relativ) einfach mit Induktion beweisen kann. --NeoUrfahraner 15:40, 5. Jul. 2010 (CEST)

Dass man es für diese Spezialfrage brauchen kann, ist klar. Dann sollte aber der Beweis auch dorthin verlagert werden.--Wilfried Neumaier 15:53, 5. Jul. 2010 (CEST)

Ich ersetze demnächst die verwirrende Induktion durch das einfachere Beispiel und setze deshalb den alten Passus hierher:

Vollständige Induktion kann auch zum Beweis von Ungleichungen verwendet werden. Diese Beweise sind aber häufig schwieriger als die Beweise von Gleichungen, da sie Abschätzungen erfordern, die nicht immer offensichtlich sind. Die bernoullische Ungleichung ist ein einfaches Beispiel einer Ungleichung, die sich mit vollständiger Induktion beweisen lässt. Etwas anspruchsvoller ist der Beweis folgender Ungleichung:

Für reelle $x_{i}>0\!$, $i=1,\dots ,n$ mit $\prod _{i=1}^{n}x_{i}=1$ folgt, dass $\sum _{i=1}^{n}x_{i}\geq n$.

Die Bedeutung dieser Ungleichung liegt darin, dass sie in weiterer Folge für den Beweis der Ungleichung vom arithmetischen und geometrischen Mittel verwendet werden kann.

Der Induktionsanfang für den Fall $n=1$ ist offensichtlich. Gilt im Fall $n=2$, dass $x_{1}=x_{2}=1$, so gilt offensichtlich $x_{1}+x_{2}=2\geq 2$. $x_{1}$ und $x_{2}$ können nicht beide größer oder beide kleiner als 1 sein. Nimmt man an, dass $x_{1}\leq 1$ und $x_{2}\geq 1$ gilt, so folgt

$0\leq (1-x_{1})(x_{2}-1)=x_{1}+x_{2}-x_{1}\cdot x_{2}-1=x_{1}+x_{2}-2$ wegen $x_{1}\cdot x_{2}=1$, also

$2\leq x_{1}+x_{2}$. Der Fall $x_{1}\geq 1$ und $x_{2}\leq 1$ ist vollkommen analog zu behandeln.

Für den Induktionsschritt sei nun $n\geq 2$. Zu zeigen ist, dass für beliebige $n+1$ positive $x_{i}\!$ mit $\prod _{i=1}^{n+1}x_{i}=1$ folgt, dass $\sum _{i=1}^{n+1}x_{i}\geq n+1$. Als Induktionsvoraussetzung darf angenommen werden, dass für $n$ andere beliebige Zahlen (zur einfacheren Unterscheidung nennen wir sie $y_{i}$) aus $\prod _{i=1}^{n}y_{i}=1$ die Ungleichung $\sum _{i=1}^{n}y_{i}\geq n$ folgt.

Sind alle $x_{i}=1$, so gilt $\sum _{i=1}^{n+1}x_{i}=n+1$, und der Beweis ist fertig. Andernfalls gibt es mindestens ein $x_{i}>1$, sonst wäre das Produkt $\prod _{i=1}^{n+1}x_{i}<1$; ebenso gibt es ein anderes $x_{i}<1$. Ohne Beschränkung der Allgemeinheit sei also $x_{n}<1$ und $x_{n+1}>1$. Die Bedeutung dieser Wahl wird erst später klar.

Setzt man nun $y_{i}=x_{i}$ für $i=1,\dots ,n-1$ und $y_{n}=x_{n}\cdot x_{n+1}$, so gilt

$\prod _{i=1}^{n}y_{i}=\prod _{i=1}^{n+1}x_{i}=1$.

Somit kann die Induktionsvoraussetzung angewendet werden, und es folgt

$n\leq \sum _{i=1}^{n}y_{i}=\sum _{i=1}^{n-1}x_{i}+x_{n}\cdot x_{n+1}$.

Nun kommt ins Spiel, dass die Indizes $n$ und $n+1$ so gewählt wurden, dass $x_{n}<1$ und $x_{n+1}>1$ gilt. Daraus folgt nämlich

$0\leq \left(1-x_{n}\right)\left(x_{n+1}-1\right)=x_{n}+x_{n+1}-x_{n}\cdot x_{n+1}-1$. Addiert man die beiden Ungleichungen, so erhält man

$n\leq \sum _{i=1}^{n-1}x_{i}+x_{n}+x_{n+1}-1=\sum _{i=1}^{n+1}x_{i}-1$, also genau die Behauptung $n+1\leq \sum _{i=1}^{n+1}x_{i}$.

(nicht signierter Beitrag von Wilfried Neumaier (Diskussion | Beiträge) 08:25, 2. Jul. 2010 (CEST))

Kandidatur vom 2. Juli bis 15. Juli 2010 (behält Lesenswert)

Vollständige Induktion ist eine mathematische Beweismethode, nach der eine Aussage für alle natürlichen Zahlen bewiesen wird. Da es sich um unendlich viele Zahlen handelt, kann der Beweis nicht für alle Einzelfälle durchgeführt werden. Er wird daher in zwei Etappen durchgeführt: als Induktionsanfang für die kleinste Zahl (1 oder 0) und als Induktionschritt, der aus der Aussage für eine variable Zahl n die entsprechende Aussage für die nächste Zahl n+1 logisch ableitet.

Hat schon ein lesenswert, ich stelle ihn hier ein, weil Wilfried Neumaier ihn runderneuert hat. Ich habe schon einige sehr schoene Stellen gelesen, der Artikel hat auf jeden Fall gewonnen, nicht nur an Praezision. -- Room 608 13:57, 2. Jul. 2010 (CEST)

Vorsicht Missverstaendlichkeit: Der Artikel hatte in der anders gelagerten Vorgaengerversion ein lesenswert, so dass die Frage jetzt lautet:

Abwahl oder Verbesserung? -- Room 608 19:14, 2. Jul. 2010 (CEST)

• Die Einleitung ist klar zu kurz. Sie soll, besonders bei Exzellenten, ein Abstract sein, der mit der Definition des Lemmas beginnt. Zumindest ersteres ist hier nicht erfüllt. Selbst für Lesenswert wird inzwischen eine längere Einleitung als ein Satz erwartet. Der Rest des Artikels ist hingegen durchaus auszeichnungswürdig, mit Tendenz zu Exzellent. Wegen nicht ausreichendem Eintrittspunkt in den Artikel zur Zeit leider  keine Auszeichnung, bitte überarbeiten. --Morten Haan Wikipedia ist für Leser da 14:27, 2. Jul. 2010 (CEST)

Die Definition ist nun auf anschaulich lesbare Weise eingearbeitet.--Wilfried Neumaier 15:09, 2. Jul. 2010 (CEST)

Die Einleitung ist nun  Ok. Noch zwei Anmerkungen: Wäre es nicht sinnvoller, die Grafik aus dem anschaulichen Abschnitt in die Einleitung zu setzen? Würde der Verständlichkeit sicher helfen. Außerdem sind weiter unten Überschriften gleichzeitig Links. Das ist in Artikeln eher unüblich, normalerweise wird im darauffolgenden Fließtext oder durch {{Hauptartikel|Lemma}} verlinkt. Der Artikel ist aber wirklich gut, ich geb mal  Exzellent  Lesenswert. --Morten Haan Wikipedia ist für Leser da 15:18, 2. Jul. 2010 (CEST) geändet, war doch etwas übertrieben. --Morten Haan Wikipedia ist für Leser da 15:46, 5. Jul. 2010 (CEST)

Die Bilder sind nicht so anschaulich und koennen getrost unten bleiben. Ich habe selten so eine anschauliche Einleitung zu einem mathematischen Thema gelesen, wie oben. Es ist meine Meinung, dass man in der Mathematik mit Bildern einiges schlimmer machen kann, zum Beispiel Vektoren, die sind nicht anschaulich. Lieber ein Bild von Dedekind oder de Morgan, den Freaks. Wenns sein muss: Domino. -- Room 608 15:34, 2. Jul. 2010 (CEST) P.S.: Lagrange, Kumpel vom alten Fritz, war stolz drauf eine Geometrie ohne ein einziges Bild geschrieben zu haben.

Kompromissvorschlag: Man könnte die Veranschaulichung vor die Etymologie und Geschichte stellen. Wäre das akzeptabel?--Wilfried Neumaier 15:59, 2. Jul. 2010 (CEST)

Nach Überfliegen  keine Auszeichnung. Folgendes, mE Grundlegendes, Fehlt:

• Verallgemeinerung auf Aussagen über induktive Mengen.
• Sprachliche Genauigkeit: „Unendlich viel[e Schritte]“ gibt es nicht. Das macht keinen Sinn. Gemeint ist „beliebig viel“. Um das zu verdeutlichen vlt ein Beispiel bringen, wo Induktion nicht ausreicht. Etwa allgemeine Existenz von Vektorraumbasen.
• Formuierung von VI als Prinzip der kleinsten VerbrecherInnen (minimales Gegenbeispiel)
• Das „fast alle“ finde ich misverständlich zu der fast überall-Formel.
• Einordnung in die Axiomensystem fehlt mir irgendwie. Überhaupt müsste man OMA erst mal erklären was sowas eigentlich ist, bevor man ihnen mit dem Peano-System kommt. Ebenso fehlt eine metamathematische Rechtfertigung des Axioms der VI vollständigen Induktion.--goiken 15:42, 2. Jul. 2010 (CEST)
• Dass konstruktiv gezeigte Induktionsschritte rekursive Algorithmen liefern und dass anders herum Korrektheitsbeweise von solchen Algorithmen Induktionsarumente sind, kann man noch erwähnen. Innerhalb funktionaler Programmierparadigmen ist das ein grundlegendes Vorgehen.--goiken 10:45, 3. Jul. 2010 (CEST)

Deine Wünsche habe ich weitgehend erfüllt. Der Abschnitt "Ableitung der Induktion" enthielt schon die Einordnung in Axiomensysteme, unter anderem in System der Peano-Axiome und auch schon die induktiven Mengen, aber ohne Fachbegriff, der jetzt verlinkt ist. Statt "fast alle", jetzt der Untertitel "Induktion mit beliebigen Anfang". Was meinst Du mit der VI.??--Wilfried Neumaier 16:30, 2. Jul. 2010 (CEST)

Die Änderungen sind soweit Schick. Gefallen tut mir der Artikel aber immer noch nicht so richtig. Die (für mich) interessanten Stellen bleiben ziemlich vage und wenig konkret. Kann mir aber vorstellen, dass der Artikel für Leute omA anschaulich und hilfreich ist. Fehler seh ich auch keine: Also von mir aus keine Einwände und  Neutral.--goiken 17:27, 13. Jul. 2010 (CEST)

Naja, der Artikel hat mich nicht gerade umgehauen. Da wären:

• Die Einleitung ist zu kurz, vgl. WP:WSIGA#Begriffsdefinition und Einleitung.
• Induktionsanfang muss nicht zwangsläufig 0 oder 1 sein, manche Beiweise werden bewusst für natürliche Zahlen > x geführt.
• Der Geschichtsteil ist stark verkürzt. Es bliebt z.B. im Dunkeln, wie sich die Vorgängerversionen vom Artikelthema unterscheiden. Außerdem könnte man herausarbeiten, was Franciscus Maurolicus' Beweis betraf, ob er sich dem Prinzip widmete oder es nur angewendet hat. Wie das Prinzip im Laufe der Jahre (z.B. aussagenlogisch) erschlossen wurde, wird ebenfalls nicht geklärt.

Soweit ich weiss, gibt es mehrere sich teils widerstrebende Ansaetze, Gerhard Gentzen und Paul Lorenzen, mit so in Art Strichliste, lieferten recht feine Umsetzungen von Arithmtik und zweiter von Analysis ab. -- Room 608 00:38, 6. Jul. 2010 (CEST)

• Die Veranschaulichung ist unpräzise: Es genügt nicht, dass „durch jeden fallenden Dominostein ein weiterer umgestoßen wird“, es muss der nächste in der Reihe umfallen, ohne dass z.B. einer übersprungen wird, und es müssen alle in dieser Reihe stehen, also z.B. keiner daneben. Das ist im Alltag selbstverständlich, da es hier aber um ein mathematisches Thema geht, wäre mehr Präzision wünschenswert. (Grundsätzlich finde ich das aber eine gute Veranschaulichung!)
• Der Abschnitt Veranschaulichung hat 'nen Haufen Whitespace.
• Das Prinzip wird nur in der Einleitung erklärt, und da relativ kurz. Meine OMA versteht das nicht. (Und das ist kein so komplexes Thema, als dass man es ihr nicht näher bringen könnte!)
• Links in Überschriften gehen gar nicht. Bitte entfernen und z.B. die Vorlage:Hauptartikel verwenden.
• Bei den Beispielen vermissen ich ordentlichen Schreibstil. Da bekommt man Brocken wie "Behauptung: ... Beweis: ..." an den Kopf geworfen. Das liest sich wie die Mathearbeit eines Mittel- bis Oberstüflers, aber nicht wie ein gut geschriebener Artikel.
• Was unter „Ableitung“ im Sinne von Ableitung der Induktion zu verstehen ist, bleibt offen.
• Angesichts von nur zwölf Google-Treffern frage ich mich, ob "Vorwärts-rückwärts-Induktion" vll. ein hier geprägter Begriff ist?
• Der Artikel bringt "Beispiele für fehlerhafte Induktionen", ohne auch nur ansatzweise zu erklären, was das überhaupt ist. Der Fehlgriff zur Listenformatierung macht die Sache leider nur rund, als "Quellen" getarnte Einzelnachweise wundern dann auch nicht mehr.
• Geht das nur mir so, oder verhalten sich die Türme von Hanoi zur vollständigen Induktion so wie Hallo Welt zu Programmiersprachen? Warum fehlen die komplett im Artikel?

Fazit: Der Artikel hat derzeit imho  keine Auszeichnung verdient, auch die nicht, die er bereits hat. Als Leseempfehlung gebe ich gerne, so auch hier WP:WSIGA und WP:WGAA. Für Exzellenz hat der Text deutlich zu wenig Substanz, da fehlen Passagen über die Bedeutung des Beweisprinzips, seine wissenschaftliche Erforschung und Anwendung (jenseits der plakativen Beispiele, etwa im Rahmen für die Disziplin historisch bedeutender Beweise) und mit Sicherheit – das kann ich als Laie nur vermuten – Aussagen, die das Lemma in Bezug zu anderen mathematischen Themen setzen. Grüße, Wikiroe 16:44, 2. Jul. 2010 (CEST)

Der Artikel steht hier primaer, weil der Vorgaenger ein Lesenswert hatte, was ich nicht nachvollziehen kann, wie das moeglich war. Wilfried hat den Artikel jetzt erstmal fundiert. Ob er an einem OMA exzellent interessiert ist, wage ich zu bezweifeln. Was hier kritisiert wird, stammt aus der Vorgaengerkonzeption des Artikels, die wirklich holprig ist, also bitte konstruktiv mithelfen und nicht niederstimmen. Es waere dann naemlich nur ein Abwahlkandidat. -- Room 608 19:01, 2. Jul. 2010 (CEST)

Warum steht der Artikel dann hier, wenn der Autor nicht an exzellent interessiert ist und man andererseits auch nicht für Abwahl stimmen darf, ohne mitzuhelfen? Review? --79.230.75.67 10:46, 4. Jul. 2010 (CEST)

Natuerlich kannst Du fuer Exzellent stimmen. Helfe mit, wer will, und der Artikel steht hier gegebenfalls auch zur Abwahl. So sind doch die Regeln? -- Room 608 01:53, 5. Jul. 2010 (CEST)

 Info: Ausgewertet wird nach Ablauf des Kandidaturzeitraumes die jeweils aktuellste Version, sofern diese nicht offensichtlich vandalisiert ist. Für den Personenkreis, die Artikelauswahl, Kandidaturvorbereitung, Kriterien, Auswertung, Nachbereitung usw. steht das wesentliche in der aktuellen Version im einleitenden Kasten oben auf dieser Seite, einbunden über die aktuelle Intro-Vorlage, sowie auf den Seiten der weiterführenden Links. Bitte einfach einmal durchlesen und beachten. --Vux 16:49, 4. Jul. 2010 (CEST)

 Lesenswert Nach den letzten Korrekturen ist der Artikel informativ, gut lesbar, strukturiert und uebersichtlich. -- Room 608 09:51, 6. Jul. 2010 (CEST)

 Lesenswert, aber nicht exzellent. Ich möchte anregen, mehrere Leserzielgruppen ins Auge zu fassen. Der Abschnitt "Beispiele" richtet sich offenbar an Schüler und interessierte Laien. Ihnen kann man das Lesen und das Verständnis erleichtern, indem man die Rechenschritte verbalisiert und ein paar mehr Worte zu den zu beweisenden Sätzen verliert. Fachleute interessieren sich dagegen vermutlich mehr für die Geschichte und die Zusammenhänge zu Axiomensystemen und mathematischer Logik. Hier macht der Artikel viele knappe Andeutungen; er würde gewinnen, wenn er diese ausführen würde. --Zipferlak 10:36, 6. Jul. 2010 (CEST)

Die aufgezeigten Schwachstellen wurden vom Hauptautor behoben, sodass zwei der drei Keine Auszeichungs-Stimmen geändert wurden. Bei einem Abstimmungsstand von 3 Lesenswert zu 1 Keine Auszeichnung zu 1 Neutral wäre dem Artikel den Regeln gemäß die Auszeichnung ab zu erkennen. Die Kritikpunkte der verbliebenen Contra-Stimme beziehen sich jedoch auf eine alte Version, nach der Überarbeitung durch den Hauptautor wurden diese Mängel jedoch beseitigt. Widerspruch kann gerne hier und dann bitte auch auf meiner Diskussionsseite eingelegt werden. --Fecchi nieder mit den hellblauen! 11:47, 15. Jul. 2010 (CEST)

Wann verlasse ich die Induktion

Liest man manche Beweise mit Induktion bzw. versucht diese selbstständig nachzubauen stößt man schnell auf das Problem "wann verlasse ich die Induktion und verirre mich in vollständiger 'Spekulation'"? Ein Beispiel ist bereits der Beweis des Lemmas der Ackermannfunktion: y<A(x,y). (nicht signierter Beitrag von 93.232.218.232 (Diskussion) 12:18, 10. Mai 2011 (CEST))

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)) Steht doch im Artikel: Das Prinzip der vollständigen Induktion ist die Anwendung eines der Axiome, die bei der Definition der Naürlichen Zahlen erfüllt sein müssen, um zu beweisen, daß gewisse Aussagen für alle Natürlichen Zahlen gelten.--Luftzug (Diskussion) 10:50, 31. Mär. 2012 (CEST)

Komma oder "und"

Wäre es nich besser ...

$A(m)\land \forall n\in \mathbb {N} ((n\geq m\land A(n))\Rightarrow A(n+1))\ \vdash \forall n\in \mathbb {N} \colon (n\geq m\Rightarrow A(n))$

... zu schreiben statt:

$A(m){,}\quad n\in \mathbb {N} \land n\geq m\land A(n)\Rightarrow A(n+1)\ \vdash \forall n\in \mathbb {N} \colon (n\geq m\Rightarrow A(n))$

Das Komma nach "A(m)" bedeutet doch "und". --Joachim Mohr 09:23, 1. Jul. 2011 (CEST)

Das wäre theoretisch gleichwertig, entspricht aber nicht der üblichen Beweisstrategie mit zwei separaten Beweisschritten. Beim Ableitungsoperator werden nämlich üblicherweise alle separat bewiesenen Aussagen in einer Liste aufgelistet. Sie beschreibt die Menge der zu zeigenden Voraussetzungen. In einem extra Beweisschritt könnte man dann die Verknüpfung mit "und" auch beweisen, aber das will man ja hier gerade nicht. Daher ist die jetzige Version adäquater.--Wilfried Neumaier 10:09, 1. Jul. 2011 (CEST)

Hallo Wilfried Neumaier - so trifft man sich wieder -, das war mir so nicht klar. Ich habe bisher die Logik nur mit "klarem Menschenverstand", also mehr unter didaktischen Gesichtpunkten, betrachtet. Danke für die Erläuterungen. Gruß --Joachim Mohr 20:29, 1. Jul. 2011 (CEST)

Hallo zurück! In Sachen Formalisierung bin inzwischen bewandert, weil seit einigen Jahre intensiv Logik betreibe. Ich bin der Hauptautor des Artikels in jetziger Form und habe die Riesen-Überarbeitungswelle gemacht, die oben in der Diskussion um das Lesbarkeitsprädikat etwas kommentiert ist. Ich versuche den nicht ganz einfachen Spagat zwischen Logik mit Niveau und Didaktik und greife alle sinnvollen Anregungen auf und baue sie dann an der besten Stelle ein, so auch den didaktischen Formulierungsvorschlag.--Wilfried Neumaier 20:49, 1. Jul. 2011 (CEST)

Wer hat sich dieses Domino-Beispiel ausgedacht?

Nur so eine kleine Frage am Rande. Vielleicht ist es nicht so wichtig. Aber wenn das mir als Mathe-Laien schon auffällt^^ Hat schon mal einer Dominoday gesehen und gezählt wieviele verdammte Steine da nicht umfallen??? Das ist ein Widerspruch in sich. Einen vollständigen Beweis mit einem fehlerhaften Beispiel zu beschreiben. Ziemlich unmathematisch. (nicht signierter Beitrag von 37.49.105.188 (Diskussion) 01:16, 24. Feb. 2013 (CET))

Wie heißt es so schön unter dem Dominobeispiel? "Stoße den ersten Stein um und sorge dafür, dass der n-te Stein (dieser Reihe) auch den (n+1)-ten Stein umwirft (n>=0)." Dominoday ist etwas anderes. So wie es aufgemalt ist, hat es wenig mit Dominoday zu tun. Ich finde die Veranschaulichung treffend. --Joachim Mohr (Diskussion) 17:39, 24. Feb. 2013 (CET)

Löschung des Abschnitts "Konstruktive Benutzung der vollständigen Induktion"

Ich habe diesen Abschnitt ersatzlos gelöscht. Es handelt sich keineswegs um eine 'konstruktive' Benutzung eines Beweisverfahrens, derart, dass eine wahre Aussage sozusagen 'errechnet' wird.

Ich habe wirklich wunder was gedacht und deshalb den genannten Artikel aus den Semesterberichten im Zeitschriftenmagazin aufgesucht und gelesen. Es wird dem Autor dieses Artikels sicher nicht recht sein, hier noch Jahrzehnte später so prominent an ziemlich unpassender Stelle erwähnt zu werden, zumal die Idee nicht einmal von ihm ist (wie im Artikel selbst angemerkt). Der Autor benutzt lediglich das Verfahren der vollständiger Induktion quasi in retrograder Weise (und genau genommen, selbst das nicht), um eine Aussageform A(k) geschickt zu erraten(!), die dann hoffentlich mit ('vorwärts' durchgeführter) vollständiger Induktion für alle natürlichen Zahlen bewiesen werden kann. Das Ganze gehört in den Bereich 'systematisches Raten', wie es wohl die meisten Theoretiker in ihren Arbeitsstuben machen, und ist in keinem Fall etwas 'Konstruktives'. --Stefan Neumeier (Diskussion) 20:06, 10. Feb. 2015 (CET)

Stolperfallen mit aufnehmen ?

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!

Ich glaube der Induktionsanfang ist ok. Ich hätte eher gesagt für den Spezialfall A(1)=>A(2) ist der Induktionsschritt nicht korrekt.

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)

Ist zwar schon zehn Jahre alt und längst aus dem Artikel verschwunden, aber falls sich jemand hierhin verirrt: Der Induktionsanfang n=2 ist deshalb erforderlich, weil Gleichfarbigkeit eine (mindestens) zweistellige Relation und in einer einelementigen Menge nicht definiert ist. Der Fehler liegt hier also nicht in einer falschen Anwendung des Induktionsverfahrens. (Die Begründung oben ist unzutreffend, denn A und B werden aus der n+1-elementigen Menge genommen, und die hat durchaus mindestens zwei Elemente.) -- 87.145.237.75 00:38, 7. Sep. 2015 (CEST)

Zur Induktionsvoraussetzung

Im Text: ... Oder weniger formal formuliert:

1. Induktionsanfang: Es wird bewiesen, dass die Aussage für die kleinste Zahl, den Startwert, gilt.
2. Induktionsschritt: Folgendes wird bewiesen: Gilt die Aussage für eine beliebige Zahl, so gilt sie auch für deren Nachfolger

Meine Frage: Woher wissen wir, dass die Aussage A(n) für eine beliebige Zahl gilt? Ist für beliebig auch der Anfang A(1) zulässig? Wenn ja, dann muss doch nur gezeigt werden, dass die nächste Aussage A(2) sich aus dem Anfang A(1) ergibt?! So ist dem Nachfolger doch genüge getan?! Also meine Frage anders formuliert: Ist der beliebigen Zahl auch mit einer konkreten bereits genüge getan? Wenn aber mit beliebig notwendiger Weise jede Aussage A(n) gemeint ist, dann bleibt die obige Frage nach der Gültigkeit von A(n). Vielleicht ist einem das nicht zu dumm gefragt, danke --Walmei (Diskussion) 12:29, 20. Dez. 2023 (CET)

ist vielleicht etwas unglücklich formuliert, natürlich gilt die Aussage nicht für beliebige A(n). Sondern man zeigt bzw. beweist wenn sie für A(n) gilt, dann gilt sie für auch für A(n+1). Ob sie aber für überhaupt irgendein n gilt weiß man zunächst nicht. Genau dafür braucht man den Induktionsanfang, denn mit diesem hat man ein n gefunden für das die Aussage gilt und wenn man den Induktionsschritt bewiesen hat, muss dann auch A(n+1) gelten und damit dann auch A((n+1)+1) und dann A([(n+1)+1] +1) usw. --Kmhkmh (Diskussion) 14:07, 20. Dez. 2023 (CET)

Mit eigenen Worten: Die Induktionsvoraussetzung ist zumindest mit A(0) wahr, so dass sich zwar A(1) möglicherweise leicht als wahr beweisen lässt, die der folgenden A(n) aber nur mit einem allgemeinen (vollständigen) Induktionsbeweis. Ist das korrekt? --Walmei (Diskussion) 22:45, 20. Dez. 2023 (CET)

Um zu zeigen, dass die Aussageform A(n) allgemeingültig ist, d.h. A(0) ist eine wahre Aussage , A(1) ist ist eine wahre Aussage, A(2) ist eine wahre Aussage usw., bedient man sich des Axioms der vollständigen Induktion. Das lautet:

Ist A(0) eine wahre Aussage und gilt die Folgerung A(n)⇒A(n+1) für alle n≥0, dann gilt

A(n) für alle n≥0.

Es handelt sich also um Aussagen, die wahr oder falsch sind und Aussageformen, die allgemeingültig sind oder eben nicht.

Hier ist A(n)⇒A(n+1) eine Aussageform, von der zu zeigen ist, dass sie allgemeingültig ist.

--Joachim Mohr (Diskussion) 09:40, 21. Dez. 2023 (CET)

Und nun zu meinem Satz, Ist er korrekt? --2A0A:2782:3F2:E500:307D:4B26:E090:E0B9 16:26, 21. Dez. 2023 (CET)

Welchen satz meinst Du. Kannst Du ihn nochmals wiederholen? --Joachim Mohr (Diskussion) 18:11, 21. Dez. 2023 (CET)

Hallo Joachim, der Satz steht oben: "Die Induktionsvoraussetzung ist zumindest mit A(0) wahr, so dass sich zwar A(1) möglicherweise leicht als wahr beweisen lässt, die der folgenden A(n) aber nur mit einem allgemeinen (vollständigen) Induktionsbeweis." Ist das korrekt? --2A0A:2782:3F2:E500:307D:4B26:E090:E0B9 09:18, 22. Dez. 2023 (CET)

Als korrekt würde ich das nicht bezeichnen. Im Induktionsbeweis muss man zeigen.

Induktionsanfang: A(0) ist wahr

Induktionsschritt: Aus A(n) folgt A(n+1) für für alle n≥0.

Fertig!

Dass mit A(0), dann auch A(1) wahr ist, folgt aus dem Insuktionsschritt und muss nicht extra erwähnt werden. --Joachim Mohr (Diskussion) 11:56, 22. Dez. 2023 (CET)

Danke! --2A0A:2782:3F2:E500:AD69:28E5:CF7E:934B 22:29, 22. Dez. 2023 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: --Joachim Mohr (Diskussion) 15:55, 23. Dez. 2023 (CET) --Joachim Mohr (Diskussion) 15:55, 23. Dez. 2023 (CET)