Mathematische Induktion und Implikation

Sep 17 2020

Vorwort : (überspringen Sie diesen Teil , wenn Sie gerade auf meine Frage hinwollen Ich schreibe dies so hoffentlich nicht ein Duplikat bekommt , da ich keine befriedigende Antwort auf mathstackexchange finden konnte noch.) . Hallo, ich möchte fragen, warum ich nicht verstehe, dass die mathematische Induktion immer gültig ist. Ich bin mir bewusst, dass dies eine sehr häufige Frage ist, und ich weiß, dass es viele Versuche gibt, zu erklären, warum, aber ich habe diese Frage schon lange (eigentlich komme ich hierher zurück, um sie zu stellen, da ich monatelang keinen Erfolg hatte). Vertrauen Sie mir, ich habe viele Beiträge und Antworten zu diesem Thema auf den verschiedenen Websites gelesen und keiner von ihnen hat mein Verständnis (einschließlich Mathstackexchange) befriedigt. Ich werde versuchen klar zu erklären, wo ich verwirrt bin, damit mir hoffentlich jemand helfen kann.

Soweit ich weiß, beweist die mathematische Induktion, dass dies eine Aussage ist $P(n)$ gilt für alle natürlichen Zahlen, wenn:

$P(0)$ ist wahr.

(Mein Verständnis: Mathematische Aussage ist wahr, wenn $n = 0$.)

Vorausgesetzt $P(n)$ gilt für alle natürlichen Zahlen und wenn ich zeigen kann, dass die Implikation $P(n) \rightarrow P(n+1)$ ist wahr.

(Mein Verständnis: Das heißt, wir wissen nicht, ob die Aussage P (n) wahr oder falsch ist. Aber wenn wir zeigen, dass die Implikation $P(n) \rightarrow P(n+1)$ gilt dann reicht das für die mathematische Induktion, um zu halten, ob die Aussage $P(n)$ ist tatsächlich wahr oder nicht).

Wenn diese Bedingungen (1) und (2) gelten, dann beweist dies, dass die Aussage $P(n)$ gilt für alle natürlichen Zahlen.

Hier finde ich die mathematische Induktion faul.

Ich bin mit dieser Logik der mathematischen Induktion einverstanden, wann immer die Aussage $P(n)$ist tatsächlich wahr und die Bedingungen (1) und (2) erfüllen. Dann kann ich den allgemeinen Antworten zustimmen, die ich gesehen habe: Wenn$P(0)$ ist wahr und seit $P(n) \rightarrow P(n+1)$ ist wahr, $P(1)$ist wahr. Schon seit$P(1)$ ist wahr mit der gleichen Logik $P(2)$ ist wahr und so weiter ...

Aber soweit ich weiß, hat die logische Implikation eine Wahrheitstabelle einer Form:

Es heißt also, dass die Implikation nur dann falsch ist, wenn die Aussage wahr ist, aber das Ergebnis falsch ist. Das heißt, es ist auch möglich, dass die Implikation wahr ist, wenn die Startanweisung$P$ist falsch. Wenn ich die Implikation richtig verstehe (Bitte korrigieren Sie mich, wenn ich falsch liege), wenn die Aussage$P \rightarrow Q$ist wahr , es bedeutet, nachdem gültige logische Schritte auf die ursprüngliche Anweisung angewendet wurden$P$ (ob die Aussage $P$ ist wahr oder nicht), können Sie zu der resultierenden Aussage gelangen $Q$.

Ich war damit einverstanden, dass eine falsche Aussage impliziert, dass ein falsches Ergebnis wahr ist, und eine falsche Aussage, dass eine wahre Aussage wahr ist, anhand der folgenden Beispiele:

ex1) Falsche Aussage impliziert Falsche Aussage kann wahr sein :

Lassen Sie die Aussage $P$ Sein $-1 = 1$ und Ergebnis $Q$ Sein $0 = 2$. ich nehme an$P$ und $Q$sind beide aus offensichtlichen Gründen falsch. Jetzt, da die Implikation logische Schritte anwendet, kann ich hinzufügen$1$ zu beiden Seiten der Erklärung $P$. Das führt zu$-1 + (1) = 1 + 1 \rightarrow 0 = 2$ Welches ist die Aussage $Q$. Daher ist die Implikation wahr.

ex2) Falsche Aussage impliziert, dass wahre Aussage wahr sein kann :

Lassen Sie die Aussage $P$ Sein $-1 = 1$ und Ergebnis $Q$ Sein $1 = 1$. ich nehme an$P$ ist aber aus offensichtlichen Gründen falsch $Q$ist wahr. Da die Implikation logische Schritte anwendet, kann ich beide Seiten der Anweisung quadrieren$P$. Das führt zu$(-1)^2 = (1)^2 \rightarrow 1 = 1$ Welches ist die Aussage $Q$. Daher ist die Implikation wahr.

Nun zurück zur mathematischen Induktion $P(0)$ Da dies wahr ist, nehmen wir die Aussage an $P(n)$ gilt für alle natürlichen Zahlen nicht nur $0$ (was bedeutet, dass es auch für einige Zahlen größer als falsch sein kann $0$, aber wir wissen es nicht) und wir zeigen, dass die Implikation $P(n) \rightarrow P(n+1)$ist wahr. Aber nach der Logik, die ich gerade gesagt habe:$P(n)$ könnte falsch sein und immer noch implizieren $P(n) \rightarrow P(n+1)$ist wahr. Wenn$P(n)$ ist eine wahre Aussage, logische Schritte sollten mich dazu bringen $P(n+1)$denn so wird Mathematik aufgebaut (um logische Antworten aus logischen Schritten zu erhalten). Aber wenn wir nicht wissen, ob die Aussage$P(n)$ist falsch und die Implikation stellt sich als wahr heraus, was dann? Es scheint immer noch die Logik von If$P(0)$ ist wahr und seit $P(n) \rightarrow P(n+1)$ ist wahr, $P(1)$ist wahr. Schon seit$P(1)$ ist wahr mit der gleichen Logik $P(2)$ist wahr und so weiter ... sollte funktionieren. Aber wie gesagt, wenn sich das herausstellt$P(n)$ ist nicht für alle natürlichen Zahlen wahr, dies sollte nicht der Fall sein und ich kann mir nicht vorstellen, was das Ergebnis sein würde.

Ich gehe davon aus, dass es eine Aussage geben sollte $P(n)$ falsch sein für eine natürliche Zahl (wahr für $P(0)$) aber immer noch wahr für $P(n) \rightarrow P(n+1)$ da die Logik sagt, dass es möglich ist, dass eine falsche Aussage eine wahre Aussage impliziert, und es gibt unendlich viele Aussagen, die dies erfüllen können (ich gehe davon aus ...).

Ich habe versucht, ein eigenes Beispiel dafür zu finden, und ich konnte es nicht, aber falls dies den Lesern hilft, besser zu verstehen, wo ich falsch liege, werde ich es trotzdem sagen:

Lassen Sie die Aussage $P(n)$ auf natürliche Zahl sein $$\sum_{n=0}^k (n+1)^{3n} = k!3^k$$.

Wir können den Basisfall zeigen $P(0)$ ist wahr.

Unter der Annahme, dass diese Aussage für alle natürlichen Zahlen gilt und logische Schritte angewendet werden, erhalte ich einen Widerspruch und kann nicht zeigen, dass die Implikation falsch ist. (Vielleicht kann man durch clevere Tricks zeigen, dass die Implikation wahr ist?). In diesem Fall schlägt das Beispiel fehl, aber ich glaube, es sollte eine solche Aussage geben$P(n)$ das würde meine Argumentation befriedigen.

Wo irre ich mich also? Warum denke ich, dass so ein$P(n)$ sollte existieren und warum sollte es nicht existieren?

Ich hoffe, ich war klar und wenn es Unklarheiten oder Fragen gibt, bitte fragen.

Antworten

2 DanChristensen Sep 18 2020 at 12:08

Das Prinzip der mathematischen Induktion

Für jedes unäre Prädikat $P$ wir haben:

$$P(0) \land \forall a\in N:[P(a) \implies P(a+1)] \implies \forall b\in N: P(b)~~~~(1)$$

Oder gleichwertig:

$$\exists b\in N: \neg P(b) \implies [P(0) \implies \exists a\in N:[P(a) \land \neg P(a+1)]]~~~~(2)$$

Angenommen, Sie möchten die Hypothese beweisen, dass $\forall b\in N: P(b)$ und dass du das schon gezeigt hast $P(0)$ ist wahr.

Lassen $k$ sei ein beliebiges Element von $N$.

Das können wir beweisen $P(k)\implies P(k+1)$ auf die übliche Weise, indem man zuerst davon ausgeht $P(k)$ ist wahr und dann beweisen, dass $P(k+1)$ muss auch wahr sein.

Technisch könnten wir auch eine der folgenden Aktionen ausführen (nicht unbedingt dasselbe für jeden Wert von $k$):

Beweisen Sie beides $P(k)$ und $P(k+1)$ sind wahr (entsprechend Zeile 1 der Wahrheitstabelle)
Annehmen $P(k)$ ist wahr und $P(k+1)$ist falsch. Dann erhalten Sie einen Widerspruch (entsprechend Zeile 2 der Wahrheitstabelle)

Was ist mit einfach zu beweisen $P(k)$ist falsch, wie Sie vorgeschlagen haben (entspricht den Zeilen 3 und 4 der Wahrheitstabelle)? Wie wir aus (2) oben sehen, würde dies die ursprüngliche Hypothese verfälschen.

1 MauroALLEGRANZA Sep 17 2020 at 15:59

Langer Kommentar

Schritt 2), der sogenannte induktive Schritt ist etwas anders ...

Nehmen wir das an $P(n)$ ist wahr und beweisen $P(n+1)$, das läuft darauf hinaus, die Bedingung zu beweisen: $P(n) → P(n+1)$.

Als Beweis gehen wir davon aus $P(n)$ gilt für eine "nicht spezifizierte" $n$ und wir beweisen $P(n) \to P(n+1)$. Aufgrund der Tatsache, dass$n$ist , was können wir „verallgemeinern“ es$\forall n (P(n) \to P(n+1)$.