Induction mathématique et implication

Sep 17 2020

Préface : (Sautez cette partie si vous voulez aller directement à ma question. J'écris ceci donc j'espère qu'il n'y aura pas de doublon car je n'ai pas encore trouvé de réponse satisfaisante sur mathstackexchange) . Bonjour, je voudrais demander pourquoi je ne comprends pas que l'induction mathématique est toujours valide. Je suis conscient que c'est une question très courante posée et je sais qu'il y a de nombreuses tentatives pour expliquer pourquoi, mais je me pose cette question depuis longtemps (en fait, je reviens ici pour demander car je n'ai pas réussi depuis des mois). Croyez-moi, j'ai lu de nombreux articles et réponses liés à ce sujet sur les différents sites Web et aucun d'entre eux n'a encore satisfait ma compréhension (y compris mathstackexchange). J'essaierai d'expliquer clairement où je suis confus, donc j'espère que quelqu'un pourra m'aider.

Donc d'après ce que je sais, l'induction mathématique prouve qu'une déclaration $P(n)$ est vrai pour tous les nombres naturels si:

$P(0)$ est vrai.

(Ma compréhension: l'énoncé mathématique est vrai lorsque $n = 0$.)

En supposant $P(n)$ est vrai pour tous les nombres naturels et si je peux montrer que l'implication $P(n) \rightarrow P(n+1)$ est vrai.

(Ma compréhension: ce qui signifie que nous ne savons pas si l'énoncé P (n) est vrai ou faux. Mais si nous montrons que l'implication $P(n) \rightarrow P(n+1)$ tient alors que cela suffit pour que l'induction mathématique contienne si l'énoncé $P(n)$ est en fait vrai ou non).

Si ces conditions (1) et (2) sont vérifiées, cela prouve que la déclaration $P(n)$ est vrai pour tous les nombres naturels.

C'est là que je trouve que l'induction mathématique est louche.

Je suis d'accord avec cette logique d'induction mathématique chaque fois que l'énoncé $P(n)$est en fait vrai et les conditions (1) et (2) satisfont. Ensuite, je peux être d'accord avec les réponses courantes que j'ai vues: si$P(0)$ est vrai et depuis $P(n) \rightarrow P(n+1)$ est vrai, $P(1)$est vrai. Depuis$P(1)$ est vrai avec la même logique $P(2)$ est vrai et ainsi de suite ...

Mais d'après ce que je sais, l'implication logique a une table de vérité d'une forme:

Cela signifie donc que l'implication n'est fausse que lorsque l'énoncé est vrai mais que le résultat est faux. Cela signifie qu'il est également possible que l'implication soit vraie lorsque l'instruction de départ$P$c'est faux. Si je comprends correctement l'implication (veuillez me corriger si je me trompe), lorsque la déclaration$P \rightarrow Q$est vrai , cela signifie qu'après avoir appliqué des étapes logiques valides à l'instruction initiale$P$ (si la déclaration $P$ est vrai ou non), vous pouvez accéder à l'instruction résultante $Q$.

J'étais d'accord avec une fausse déclaration impliquant un résultat faux étant vrai et une déclaration fausse impliquant une déclaration vraie étant vraie avec les exemples suivants:

ex1) Une fausse déclaration implique que la fausse déclaration peut être vraie :

Laissez la déclaration $P$ être $-1 = 1$ et résultat $Q$ être $0 = 2$. Je suppose$P$ et $Q$sont tous les deux faux pour une raison évidente. Maintenant que l'implication applique des étapes logiques, je peux ajouter$1$ des deux côtés de la déclaration $P$. Cela se traduit par$-1 + (1) = 1 + 1 \rightarrow 0 = 2$ qui est la déclaration $Q$. Par conséquent, l'implication est vraie.

ex2) Une fausse déclaration implique que la déclaration vraie peut être vraie :

Laissez la déclaration $P$ être $-1 = 1$ et résultat $Q$ être $1 = 1$. Je suppose$P$ est faux pour une raison évidente mais $Q$est vrai. Maintenant que l'implication applique des étapes logiques, je peux mettre les deux côtés de la déclaration au carré$P$. Cela se traduit par$(-1)^2 = (1)^2 \rightarrow 1 = 1$ qui est la déclaration $Q$. Par conséquent, l'implication est vraie.

Revenons maintenant à l'induction mathématique, nous avons $P(0)$ étant vrai, nous supposons la déclaration $P(n)$ est vrai pour tous les nombres naturels pas seulement $0$ (ce qui signifie qu'il peut également être faux pour certains nombres supérieurs à $0$, mais on ne sait pas) et on montre que l'implication $P(n) \rightarrow P(n+1)$est vrai. Mais d'après la logique que je viens de dire,$P(n)$ pourrait être faux et impliquer encore $P(n) \rightarrow P(n+1)$est vrai. Si$P(n)$ est une déclaration vraie, l'application d'étapes logiques devrait m'amener à $P(n+1)$parce que c'est ainsi que les mathématiques sont construites (pour obtenir une réponse logique à partir d'étapes logiques). Mais si nous ne savons pas si la déclaration$P(n)$est faux et l'implication s'avère être vraie alors quoi? Il semble toujours que la logique de If$P(0)$ est vrai et depuis $P(n) \rightarrow P(n+1)$ est vrai, $P(1)$est vrai. Depuis$P(1)$ est vrai avec la même logique $P(2)$est vrai et ainsi de suite ... devrait fonctionner. Mais comme je l'ai dit, s'il s'avère que$P(n)$ n'est pas vrai pour tous les nombres naturels, cela ne devrait pas être le cas et je ne peux pas imaginer quel serait le résultat.

Je suppose qu'il devrait exister une déclaration $P(n)$ étant faux pour un nombre naturel (Vrai pour $P(0)$) mais toujours vrai pour $P(n) \rightarrow P(n+1)$ puisque la logique dit qu'il est possible qu'une fausse déclaration implique une déclaration vraie et qu'il y a une infinité de déclarations qui peuvent satisfaire cela (je suppose ...).

J'ai essayé de trouver mon propre exemple de cela et je ne pouvais pas mais au cas où cela aiderait les gens qui liraient ceci à mieux comprendre où je me trompe, je le mettrai quand même:

Laissez la déclaration $P(n)$ sur un nombre naturel être $$\sum_{n=0}^k (n+1)^{3n} = k!3^k$$.

Nous pouvons montrer le cas de base $P(0)$ est vrai.

En supposant que cette déclaration est vraie pour tous les nombres naturels et en appliquant des étapes logiques, j'obtiens une contradiction et je ne parviens pas à montrer que l'implication est fausse. (Peut-être est-il possible de montrer que l'implication est vraie en faisant des astuces intelligentes?). Dans ce cas, l'exemple échoue, mais je pense qu'il devrait y avoir une telle déclaration$P(n)$ cela satisferait mon raisonnement.

Alors, où est-ce que je me trompe? Pourquoi est-ce que je pense qu'un tel$P(n)$ devrait exister et pourquoi ne devrait-il pas exister?

J'espère avoir été clair et s'il y a une ambiguïté ou des questions, veuillez les poser.

Réponses

2 DanChristensen Sep 18 2020 at 12:08

Le principe de l'induction mathématique

Pour tout prédicat unaire $P$ nous avons:

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

Ou équivalent:

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

Supposons que vous vouliez prouver l'hypothèse que $\forall b\in N: P(b)$ et que vous avez déjà montré que $P(0)$ est vrai.

Laisser $k$ être n'importe quel élément de $N$.

Nous pouvons prouver que $P(k)\implies P(k+1)$ de la manière habituelle en supposant d'abord que $P(k)$ est vrai et prouve que $P(k+1)$ doit également être vrai.

Techniquement, nous pourrions également faire l'une des opérations suivantes (pas nécessairement la même chose pour chaque valeur de $k$):

Prouvez les deux $P(k)$ et $P(k+1)$ sont vrais (correspondant à la ligne 1 de la table de vérité)
Présumer $P(k)$ est vrai et $P(k+1)$c'est faux. Obtenez ensuite une contradiction (correspondant à la ligne 2 de la table de vérité)

Qu'en est-il simplement de prouver $P(k)$est faux comme vous l'avez suggéré (correspondant aux lignes 3 et 4 de la table de vérité)? Comme nous le voyons à partir de (2) ci-dessus, cela fausserait l'hypothèse initiale.

1 MauroALLEGRANZA Sep 17 2020 at 15:59

Long commentaire

Étape 2), l' étape dite inductive est un peu différente ...

Supposons que $P(n)$ est vrai et prouve $P(n+1)$, cela revient à prouver le conditionnel: $P(n) → P(n+1)$.

En termes de preuve, nous supposons que $P(n)$ est valable pour un "non spécifié" $n$ et nous prouvons $P(n) \to P(n+1)$. À cause du fait que$n$est n'importe quoi, nous pouvons le «généraliser» à$\forall n (P(n) \to P(n+1)$.