Rédaction de l'hérédité dans une preuve par récurrence

Etienne91
Modifié (November 2023) dans Fondements et Logique
Bonjour
Je me posais une question concernant la manière de rédiger une récurrence. Est-ce que la rédaction de cette manière vous paraît juste ? J'ai l'impression qu'elle est fausse mais je ne suis pas sûr.

On cherche à démontrer une propriété $P(k)$ pour tout $k \in \mathbb{N}$.

Initialisation : $P(0)$ est vraie.

Hérédité : on suppose qu'il existe $k \in \mathbb{N}$ tel que $P(k)$ est vraie. On montre que $P(k+1)$ est vraie.

J'ai l'impression qu'en remplaçant une propriété universelle ("soit $k \in \mathbb{N}$) par une propriété d'existence, on pourrait par exemple avoir une propriété vraie pour $n$ entier inférieur ou égal à 10 mais fausse après (il suffirait de montrer qu'il existe bien $k$, par exemple $0$, tel que $P(k)$ est vraie, que $P(1)$ est vraie mais que $P(k)$ n'est pas vraie pour $k \ge 11$ entier.

Qu'en pensez-vous ? Merci pour votre aide !

Réponses

  • bonsoir,
    Oui la preuve en l'état est fausse.
    Considérons la propriété "Tout entier naturel est inférieur à 1".
    $P(0)$ est vraie car $0 \leqslant 1$.
    Supposons qu'il existe un entier $k = 0$ tel que $P(k)$ est vrai. Comme $1 \leqslant 1$, $P(k+1)$ est vrai.
    On aurait du mal à conclure...
    Une bonne phrase pour l'hérédité serait plutôt "Soit $k \in \N$ tel que $P(k)$." suivie d'une preuve de $P(k+1)$. Tu auras alors bien démontré la propriété d'hérédité $\forall k \in \N, P(k) \Rightarrow P(k+1)$.
  • Cette façon de rédiger l'hérédité est couramment pratiquée mais personnellement, je la trouve un peu dénuée de sens.

    La supposition faite revient à écrire "Supposons $1+1=2$" car l'initialisation a effectivement montrée que la propriété supposée "$\exists k\in \N, P(k)$" a la valeur de vérité "Vraie".
    Ensuite, dans la supposition, la  lettre $k$ a le statut de variable muette alors que dans la propriété $P(k+1)$ à démontrer, $k$ n'a pas du tout ce statut.
  • Héhéhé
    Modifié (November 2023)
    La rédaction n'est pas bonne. L'hérédité est
    $$\forall k \in \mathbb N,\quad \mathscr P(k) \implies \mathscr P(k+1).$$
    Quand tu écris "on suppose qu'il existe $k \in \mathbb N$ tel que $\mathscr P(k)$ est vraie. On montre que $\mathscr P(k+1)$" est vraie" en fait tu montres
    $$ \big(\exists k \in \mathbb N,\quad \mathscr P(k)\big) \implies \mathscr P(k+1)$$
    ce qui n'est pas la même chose.

    Une bonne façon de rédiger l'hérédité est d'écrire : "Soit $k \in \mathbb N$. Supposons $\mathscr P(k)$ et montrons $\mathscr P(k+1)$".

    On voit beaucoup de rédaction maladroite de la récurrence. Je vois notamment passer des "supposons $\mathscr P(k)$ pour un certain $k \in \mathbb N$" ou des choses de ce genre, ce qui n'est pas correct. Une propriété portant sur un $\forall$ se traite avec un "soit".
  • Thierry Poma
    Modifié (November 2023)
    Bonsoir
    Tout d'abord, ton raisonnement par récurrence s'inscrit dans un contexte $\Gamma$, éventuellement vide, constitué d'hypothèses, pour faire court. Si $\Gamma\ne\emptyset$, il faut veiller à utiliser un symbole de variable n'ayant aucune occurrence libre dans $\Gamma$. Choisissons $m$ comme symbole de variable supposé n'avoir aucune occurrence libre dans ledit contexte. Pour l'hérédité, lorsque tu déclares ou que tu écris : supposons que l'on ait\[m\in\N\text{ et }P(m)\]tu vas travailler temporairement dans le nouveau contexte $\Gamma_m=\Gamma\cup\{m\in\N\text{ et }P(m)\}$ (où le le symbole de variable $m$ possède au moins une occurrence libre), afin d'y établir $P(m+1)$. Ce faisant, la règle d'introduction de l'implication t'autorise à écrire que\[(m\in\N\text{ et }P(m))\Rightarrow{}P(m+1)\]réalisé dans le contexte $\Gamma$ (car nous avons quitté le contexte $\Gamma_m$). C'est la règle d'introduction du quantificateur universel qui va te permettre d'écrire\[(\forall\,m)((m\in\N\text{ et }P(m))\Rightarrow{}P(m+1))\]vu que le symbole de variable $m$ ne possède aucune occurrence libre dans $\Gamma$.
    Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
  • Merci beaucoup pour vos réponses qui confirment ce que je pensais ! Je ne connais pas assez de logique pour comprendre en première lecture le message de Thierry Poma, je vais me renseigner un peu sur le vocabulaire pour y voir plus clair.
  • Ce que dit en fait Thierry Poma, c'est qu'avec un raisonnement du genre
    "Soit $k$ tel que $P(k)$ ... bla bla ... Donc $Q(k)$" 
    où l'on ne suppose rien d'autre sur $k$ (de sorte que le raisonnement s'applique à n'importe quel $k$ vérifiant $P(k)$), on a en fait démontré la proposition
    "Pour tout $k$, si $P(k)$ alors $Q(k)$"
    Ça tombe sous le sens, n'est-ce pas ?
    Dans la démonstration de l'hérédité, $Q(k)$ est $P(k+1)$.
  • C’est limpide en effet !
Connectez-vous ou Inscrivez-vous pour répondre.