La récurrence

[invite0c87486f]

C'est une question peut être très bête et que la réponse est sous mon nez mais tant pis je me lance. Après plusieurs nuits d'insomnie et de cassage de tête j'ai enfin décidé de poser la question :

La récurrence permet de démontrer un bon nombre de chose certes mais comment être sur de son efficacité ? Je reformule existe-t-il une démonstration qui démontre la récurrence elle même ou bien c'est un axiome ?

Je sais pas si je me suis fait bien comprendre ... mais merci d'avance pour vos réponses !
-----

[invite4abe9189]

la récurence n'est pas un axiome elle se suffit à elle même. Du moment qu'une propriété est vraie à partir d'un certain rang k(initialisation) et qu'elle se transmet de proches en proches (du rang k au rang n), elle est forcément vraie pour tout n

[invite0c87486f]

Ok c'est tout bah merci !

[Flyingsquirrel]

la récurence n'est pas un axiome elle se suffit à elle même.

On peut très bien considérer le principe de récurrence comme un axiome. C'est par exemple le cas si l'on définit avec les axiomes de Peano.

[A voir en vidéo sur Futura]

[invite4abe9189]

Un axiome c'est une propriété non démontrable mais vraie.
Mais la récurrence n'est pas tellement une propriété c'est plutot une methode non?

[invite07dd2471]

considérer la récurrence comme une méthode permettant de résoudre des exercices barbants, gâche toute la beauté de l'arithmétique et de la théorie des ensembles et des mathématiques.

ce n'est que mon avis

[invite4abe9189]

ok fitzounet je comprend ce que tu veux dire.

Mais, par exemple, la démontration par l'absurde c'est un type de démonstration pré-structurée qui peut s'appliquer à des problèmes divers et variés. Il en est de même pour la demo par récurrence. Pourtant on ne considere pas la demo par l'absurde comme un axiome non?

(prend plutot cela pour une question, je suis en terminale, j'ai 17 ans j'essai juste de me renseigner)

[Flyingsquirrel]

Un axiome c'est une propriété non démontrable mais vraie.
Mais la récurrence n'est pas tellement une propriété c'est plutot une methode non?

Pourquoi opposer méthode et propriété ? Pourquoi ne pas considérer le raisonnement par l'absurde comme une propriété ?

Mais, par exemple, la démontration par l'absurde c'est un type de démonstration pré-structurée qui peut s'appliquer à des problèmes divers et variés. Il en est de même pour la demo par récurrence. Pourtant on ne considere pas la demo par l'absurde comme un axiome non?

Non, on ne considère pas le raisonnement par l'absurde comme un axiome. (Et alors ?)

[invitec317278e]

Un axiome c'est une propriété non démontrable mais vraie.
Mais la récurrence n'est pas tellement une propriété c'est plutot une methode non?

Le fait que la "méthode" de la récurrence marche se démontre à partir du fait que toute partie non vide de l'ensemble des entiers naturels admet un plus petit élément.

[inviteec9de84d]

Le fait que la "méthode" de la récurrence marche se démontre à partir du fait que toute partie non vide de l'ensemble des entiers naturels admet un plus petit élément.

Mais pas de chance : pour conclure, il faut ajouter qu'il n'existe aucune suite infinie strictement décroissante d'entiers naturels (Fermat). Et ceci se montre justement par récurrence....
Le principe de récurrence est bien un axiome, que l'on ajoute d'ailleurs à l'axiomatique de Peano afin de construire N (comment ferait-on sans ?)

[Flyingsquirrel]

Pourquoi ne pas considérer le raisonnement par l'absurde comme une propriété ?

Il faut lire « par récurrence » et non « par l'absurde ».

[invitec317278e]

Soit une propriété.
On suppose qu'elle vérifie :
et .
On appelle l'ensemble .
Supposons qu'il ne soit pas vide.

Alors, comme partie de non vide, il admet un plus petit élément.

Soit cet élément, alors,
Or, si on a , on a alors (par contraposée de la deuxième hypothèse sur P).
Ainsi, .
Or, , ceci contredit le fait que soit le plus petit élément de

Donc est vide.

Où est la faute dans ce raisonnement ?

[inviteec9de84d]

Il n'y a pas d'erreur. C'est ce que j'ai essayé de dire :

Alors, comme partie de non vide, il admet un plus petit élément.

Seulement, comment montres-tu cette propriété ? (que j'appellerai "bon ordre").

La seule preuve que je connaisse utilise la propriété de Fermat que j'ai citée plus haut, et qui se montre , elle, par récurrence. En d'autre termes, de manière masquée, tu utilises la récurrence pour prouver la validité de la récurrence.

Néanmoins, mon raisonnement s'écroule si tu connais une autre preuve du "bon ordre" (et ce n'est pas dramatique car tu m'apprendras qqchose ).

[invitec317278e]

Ah, nan, c'est juste que dans dans la construction de N qui m'a été montrée en sup', c'est le bon ordre l'axiome, dans l'histoire ; donc je le démontre pas

(c'est ça : http://www.dma.ens.fr/culturemath/ma...ue/entiers.pdf )

[inviteec9de84d]

Je vois...
Pour moi, la récurrence est un axiome. Avec on peut montrer le bon ordre de N. Si par contre (comme tu l'as fait), tu choisis le bon ordre comme axiome, alors ok ton raisonnement permet de justifier la récurrence

Je pense que la récurrence est un axiome car il est possible de le rejeter : cf. Douglas Hofstader, dans son livre Gödel, Escher, Bach (InterEditions 1985) qui exhibe un prédicat stupéfiant P(n) tel que :
1) pour tout n, il existe une démonstration de P(n) :
2) il n'existe pas de démonstration de (∀ n, P(n) ) : non
En effet, la réunion de toutes les démonstrations n'est pas une démonstration de , car cette réunion est infinie, or une démonstration se doit d'être finie. En outre, il est possible de rejeter l'axiome de récurrence, débouchant ainsi sur une nouvelle théorie, celle de l'analyse non standard.