Unterschied: Es existiert ein n,... und Annahme die Behauptung gilt für alle n? Vollständige Induktion

Question

mich verwirrt etwas bei der Formulierung der Induktionsvoraussetzung bei der vollständigen Induktion.

Anhand folgenden Beispiels: http://mathedia.com/analysis/vollstaendige-induktion/die-potenzmenge-einer-n-elementigen-menge-enthaelt-2n-elemente/

Ich würde gerne Wissen, ob beiden Formulierungen der Induktionsvoraussetzung anwendbar sind: ∃n,n≥0: P(M)=2^n und der Annahme: P(M)=2^n gilt für alle n?

Für mich macht beides Sinn, jedoch scheint mir die erste Variante etwas kritisch zu sein, wenn es darum geht, die Induktionsvoraussetzung innerhalb des Beweise zu benutzen.

Im Beispiel: P(M_n) hat nach Voraussetzung 2^n Elemente.

Das gilt doch nur dann, wenn man davon ausgeht, dass die Behauptung für alle n gilt. Oder gilt es auch für die IV ∃n,n≥0: P(M)=2^n ?

Habe jetzt öfters bei Induktionsbeweisen beide Varianten genutzt, war das ein Fehler?

Comments

Sry, habe in Gedanke eine völlig falsche Formulierung gemacht :(

verbesserte Induktionsvoraussetzung folgt gleich:

---

Frage(neu formuliert):

mich verwirrt etwas bei der Formulierung der Induktionsvoraussetzung bei der vollständigen Induktion.

Anhand folgenden Beispiels: http://mathedia.com/analysis/vollstaendige-induktion/die-potenzmenge-einer-n-elementigen-menge-enthaelt-2n-elemente/

Ich würde gerne Wissen, ob beiden Formulierungen der Induktionsvoraussetzung anwendbar sind: Es existiert ein n, mit n≥0 für das gilt: P(M) hat 2^n Elemente und der Annahme: Für alle n, mit n≥0 hat P(M) 2^n Elemente?

Für mich macht beides Sinn, jedoch scheint mir die erste Variante etwas kritisch zu sein, wenn es darum geht, die Induktionsvoraussetzung innerhalb des Beweise zu benutzen.

Im Beispiel: P(M_n) hat nach Voraussetzung 2ⁿ Elemente.

Das gilt doch nur dann, wenn man davon ausgeht, dass die Behauptung für alle n gilt. Oder gilt es auch für die IV:

Es existiert ein n, mit n≥0 für das gilt: P(M) hat 2^n Elemente

?

Habe jetzt öfters bei Induktionsbeweisen beide Varianten genutzt, war das ein Fehler?

Answer 1

Wenn man formuliert: "P(M)=2ⁿ gilt für alle n", ist ja nichts mehr zu beweisen.

Comments

hi, habe das bereits verbessert, die IV ist natürlich falsch formuliert

---

Liebes Möchtegern-Genie. Ich kann dir leider nicht mehr folgen. Deshalb schreibe ich jetzt etwas Grundsätzliches. Ein Induktionsbeweis folgert aus der Gültigkeit der Induktionsvoraussetzung für ein bestimmtes n, dass die Aussage auch für die nächsthöhere natütliche Zahl gilt.

Dass die Aussage dann für alle n gilt, folgt aus einer Überlegung, die man meistens nicht mehr aufschreibt: Die Aussage gilt für einen Induktionsanfang, sagen wir für n = 1. Da sie auch für den Nachfolger von 1 gilt, gilt sie auch für 2. Da die Aussage nun für n=2 gilt und auch für den Nachfolger von 2, gilt die Aussage jetzt für n = 3. Und so weiter und so weiter.

---

Danke, für die Antwort.

Ich meinte das P(M)=2^n nicht der Aussage "es gibt 2^n Teilmenge" entspricht. Sry, ich habe alles etwas hektisch verfasst und dabei kam es offensichtlich etwas wirr rüber.

Um die Frage definitiv zu klären folgendes Beispiel:Beh.: $$ \sum_{k=1}^{n}{k}=\frac { n(n+1) }{ 2 } $$

IA:...

IV₁: ∃n∈ℕ, n≥1:

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

oder

IV₂: Es gelte :

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

IS: A(n)⇒A(n+1)...

Sind beide Induktionsvoraussetzungen okay?

---

Du muesstest schon genau sagen, was Deiner Meinung nach der Unterschied zwischen IV₁ und IV₂ sein soll.

So oder so: Man gewinnt den Eindruck, Du hast das Prinzip der vollstaendigen Induktion nicht verstanden.

IV₁ funktioniert nicht, wie Du denkst. Das n ist durch den Existenzquantor gebunden. Es ist nicht so, dass mit einer Aussage ∃n ... dem n ein Wert zugewiesen wuerde, mit dem man dann weitermachen kann.

IV₂ ist einfach eine Wiederholung der zu zeigenden Aussage, allerdings ganz ohne Quantor. Da ist das n jetzt frei, aber Du sagst nicht, welchen Wert es haben soll.

Beide Versuche entsprechen dem Motto: Er haette besser geschwiegen ...

---

Hi, danke für die Antwort... Die IV₂ kann man 1 zu 1 auf einer pdf über die Induktion nachlesen.

https://www2.math.uni-paderborn.de/fileadmin/Mathematik/AG-Krause/teachings/ws0607_mif1/induktion.pdf

IV₁ habe ich von hier kopiert: https://www.mathelounge.de/385699/ist-die-induktionsVoraussetzung-korrekt

, wobei es hier zwei verschiedene Meinungen gibt...eine von Roland und eine von mathef

Bitte prüfe die Links, denen zufolge beide Versionen richtig sind...

---

weitere Quelle:

bei 4:33 min

---

Richtig im Sinne von vollstaendig und korrekt die Intention beschreibend ist keine der beiden Varianten, auch wenn es von anderen so geschrieben wurde.

Eine korrekte Formulierung für die IV waere z.B.: Es gelte ... für ein (bestimmtes, fixiertes) n.

Da man da aber nur die zu zeigende Formel ohne Quantor noch mal abschreibt, laesst man die Formulierung der Induktionsvoraussetzung ausser in Anfaengeruebungen normalerweise weg. Wenn man aber doch was schreiben will, sollte man dabei nicht so nebenbei offenbaren, dass man gar nicht recht durchblickt. In diesem Sinne darfst Du meinen Kommentar verstehen.