Verallgemeinerte vollständige Induktion

23.04.2012, 19:19	Master Of Puppets	Auf diesen Beitrag antworten »
Verallgemeinerte vollständige Induktion Meine Frage: Hey, ich hoffe das ist das richtige Unterforum dafür. Ich habe zur Zeit ein Problem mit der vollständigen Induktion. Die "normale" vollständige Induktion, wie man sie in der Schule kennenlernt, verstehe ich. Also man zeigt, dass die Aussage für ein n gilt, beweist, dass A(n) -> A(n+1) gilt und schon hat man's. Wir haben im Fach Logik aber nun eine allgemeinere Version kennengelernt: $\begin{eqnarray} \forall n \in \mathbb N (\forall k\in \mathbb N: (k < n \Rightarrow p(k) \Rightarrow p(n)) \end{eqnarray}$ Ich habe aber die Begründung nicht ganz verstanden, warum das so ist. Diese Form der Induktion gilt nur wohlgeordnete Mengen, soweit ich das verstanden habe. Aber N wäre ja eine solche Menge. Allerdings reicht es doch nicht, zu zeigen, dass alle Elemente < n eine Eigenschaft erfüllen, um damit auf auf alle Zahlen schließen zu können, oder? Wahrscheinlich vermische ich da ein paar Sachen ... Es ging mal um partiell geordnete Mengen, wohlfundierte (noerthersche) Induktion, "normale" Induktion, usw und ich bin zur Zeit ein wenig Verwirrt, wie das jetzt alles im Zusammenhang steht Danke schon mal für eure Hilfe Meine Ideen: -
23.04.2012, 20:25	pseudo-nym	Auf diesen Beitrag antworten »
Jede wohlgeordnete Menge ist wohlfundiert und somit sind die natürlichen Zahlen mit der gewöhnlichen Ordnung eine wohlfundierte Relation auf der sich noethersche Induktion durchführen lässt. Der Induktionsbegriff, den du angeführt hast, ist genau der der noetherschen Induktion auf $\begin{eqnarray} \mathbb N \end{eqnarray}$ .
23.04.2012, 20:43	Master Of Puppets	Auf diesen Beitrag antworten »
Okay, danke für die Klarstellung Allerdings verstehe ich dann immer noch nicht ganz genau, wie das funktionieren soll. Wenn man beispielsweise ganz klassisch beweisen will, dass n² gleich der summe der ungeraden Zahlen ist, wie würde man dann mit der noetherschen Induktion vorgehen? Man kann doch nicht sagen: Es gilt für das minimale Element (also 1) und man sucht sich ein n aus, zB 3 und sagt dann, da es für n = 1 und 2 gilt, gilt es für alle N. Da fehlt doch sowas wie ein Induktionsschritt, dass man von A(n) auf A(n+1) schließen kann. Ich glaub ich hab irgendwas elementares an der ganzen Sache nicht verstanden.
24.04.2012, 02:25	pseudo-nym	Auf diesen Beitrag antworten »
Ich denke es ist am besten du versuchst den Beweis mit noetherscher Induktion zu führen. Wenn du spezifische Probleme hast, kannst du sie dann posten.
24.04.2012, 09:11	Master Of Puppets	Auf diesen Beitrag antworten »
Hm ja, das Problem ist, dass ich mir gar nicht vorstellen kann, wie ich da vorgehen muss, weil mir die noerthersche Induktion nicht logisch vorkommt. Mit der "normalen" vollständigen Induktion hab ich kein Problem und so könnte ich es lösen.
24.04.2012, 21:24	pseudo-nym	Auf diesen Beitrag antworten »
Nun bei einer "gewöhnlichen" Induktion zeigt man für eine Aussage $\begin{eqnarray} \Phi(n) \end{eqnarray}$ : $\begin{eqnarray} \Phi(0) \end{eqnarray}$ und $\begin{eqnarray} \Phi(n) \rightarrow \Phi(n+1) \end{eqnarray}$ . Bei deinem Induktionstyp zeigt man $\begin{eqnarray} \Phi(0) \end{eqnarray}$ und $\begin{eqnarray} \forall k \leq n : \Phi(k) \rightarrow \Phi(n+1) \end{eqnarray}$ . Wenn du also einen gewöhnlichen Induktionsbeweis hast, ist dieser auch ein noetherscher Induktionsbeweis. Von dem her kann ich nicht ganz nachvollziehen was dir Probleme bereitet.
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »