Peano et récurrence forte

Je pense que ce sujet a été plusieurs fois abordés sur le forum mais je me pose des questions par rapport à la récurrence forte.

Je me place dans la théorie de Peano où l'axiome de récurrence (sans les paramètres pour aller plus vite) est : $$(P(0) \wedge \forall j (P(j) \Rightarrow P(j+1))) \Rightarrow \forall n P(n).$$ Je m'intéresse ensuite à la formule dite "de récurrence forte" qui est $$\forall j (\forall k (k< j \wedge P(k)) \Rightarrow P(j)) \Rightarrow \forall n P(n).$$ J'entends souvent dire que la récurrence forte se déduit de la récurrence traditionnelle mais est-ce bien vrai ? Bien sûr, si on travaille avec des ensembles on peut sans problème démontrer le principe de récurrence forte mais je souhaite me restreindre à Peano, pas à une théorie plus forte. D'où ma question "La récurrence forte se déduit-elle syntaxiquement des axiomes de Peano ?"

J'ai l'impression que non, car ça dépend du modèle considéré. Mais si c'est bien le cas, pourquoi n'est-ce pas le principe de récurrence forte qui est mis dans les axiomes de Peano ? Après tout, on l'utilise constamment.
Merci pour vos éclaircissements. :)

Réponses

  • On pose $Q(n):= \forall k, k<n \Rightarrow P(k)$ et on prouve $\forall n Q(n)$ par récurrence sur $n$, puis on en déduit $\forall n P(n)$.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Il y a un implique à la place du "et" dans ta formule de récurrence forte @Cyrano .
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Ah bien vu Foys, j'avais eu la même idée mais c'est pour ça que ça ne fonctionnait pas. :D 
    Merci.
Connectez-vous ou Inscrivez-vous pour répondre.