est ce encore l'axiome de récurrence ?

[mike.p]

Bonjour,

L'axiome de récurrence dit de ce que j'en ai compris
Pour une suite d'énoncés S indexée par des entiers,
si S(p) est vrai
et que pour tout k > p , S(k) => S(k+1) ,
alors S est vrai pour tout k >= p

Peut on, en démontrant S(k) => S(k+1) , supposer que S est vrai de p à k ???

En d'autres termes si on remplace l'énoncé plus haut par celui ci, serait ce un théorême à démontrer ou un axiome différent :
Pour une suite S ,
si S(p) est vrai
et que pour tout k > p , ( S(p) && S(p+1) && ... && S(k-1) && S(k) ) => S(k+1) ,
alors S est vrai pour tout k >= p

Je ne trouve pas la démo de l'équivalence sans supposer que S(k) => S(k-1) quand il faut démontrer que S(k) => S(k+1). Ce n'est pas exactement ce que dit l'axiome.

Ce raisonnement est implicitement utilisé dans quelques commentaires ou analyses mineurs.
je me demande si , avec les idées claires , on ne peut pas le démontrer par récurrence

merci de vos éclaircissements et de votre gentillesse si c'est archi simple.
-----

[Amanuensis]

et que pour tout k > p , S(k) => S(k+1) ,

pour tout k>p-1 sinon il y a un petit problème...

[mike.p]

Bonjour !

en effet c'est k >= p

merci !

mais que pensez vous de la différence entre les 2 énoncés ? Est ce un classique ?

[Amanuensis]

En d'autres termes si on remplace l'énoncé plus haut par celui ci, serait ce un théorême à démontrer ou un axiome différent :

Il me semble que c'est la seconde forme qui est l'axiome. À savoir



Par ailleurs, oui, c'est classique.

[A voir en vidéo sur Futura]

[Médiat]

Bonjour,

L'axiome que vous citez est habituellement (mal) nommé "Récurrence forte", ce nom ne me plait pas du tout car cet axiome est strictement équivalent à l'axiome de récurrence "simple", il n'est en aucun cas plus fort.

Pour reprendre votre exemple et en commençant par un petit changement : en posant , on est ramené à une récurrence qui commence en 0 et non en , il n'est plus nécessaire de préciser les valeurs de .

L'hérédité revient à démontrer :



En posant : , la récurrence "forte" sur n'est plus qu'une récurrence "simple" sur .

[mike.p]

Bonjour,

j'ai compris !

La récurrence "forte" est donc valide car dérivant de la standard. C'est un théorême.
Une substitution ? ... faudra relire le fil adjacent sur les subst et les rep et ses liens pour en être sûr.

Je me permettrais de reprendre à l'exact vos lignes dans une note.

Cette question est donc résolue.
grand grand merci !

bon dimanche