Demonstration de la demonstration par reccurence

[Professeur1618]

Bonjours amis mathophile :we:
J'ai depuis peux intégré une fac de maths car j'ai toujours était passionné par ça. Aujourd'hui mon professeur de découverte des maths nous a posé un exo (ou plutôt un défi pour moi et toute ma section)
Prouver la véracité de la démonstration par récurrence. Je m'explique.
Soit P(n) une propriété dépendant d'un entier nature n.
Soit n0€N tel que P(n0) est vrai
But: démontrer que P(n) est vrai pour tout entier n>=n0

Merci beaucoup pour avoir lu ceci et si quelqu'un ici à même juste une idée de piste je suis partant. J'arrive difficilement démontrer la récurrence sans faire de tautologie (je démontre la récurrence en utilisant ... la récurrence :mur: )

A bientôt

[nodjim]

La démo par récurrence procède en 2 étapes:
1) Vérifier que P0 est vrai.
2) Vérifier que pour n quelconque: P(n) vrai ====> P(n+1) vrai.
Conséquence:
P0 vrai d'après 1)
P1 vrai d'après 2)
P2 vrai d'après 2)
P3 vrai......

[Robot]

J'arrive difficilement démontrer la récurrence sans faire de tautologie (je démontre la récurrence en utilisant ... la récurrence :mur: )

C'est normal. Le "principe de récurrence" fait partie des axiomes de Peano. Le démontrer est donc une gageure. Ce qu'écrit nodjim ne démontre bien sûr pas le principe de récurrence : le diable se cache dans les points de suspension.
On peut, dans le cadre de la théorie des ensembles, construire un ensemble avec un élément et une fonction "successeur" injective et n'ayant pas dans son image tel que toute partie de qui vérifie et est égale à . Mais bon, je ne pense pas que ce soit ce qu'on attende de toi (et à vrai dire, je ne vois pas trop ce qu'on attend de toi).
Tu peux voir plus sur cette page wikipedia .

Edit : partie en italique ajoutée pour corriger un oubli.

[Professeur1618]

Merci à nodjim et Robot pour vos réponse, ça m'a permis d'avancer un peu et je penses savoir comment faire maintenant :lol3:

[nodjim]

Curieux, la remarque de l'auteur de l'article: "Le 5ème axiome de Peano vérifie le principe de récurrence". J'aurais dit l'inverse: le 5ème axiome est fondé sur la récurrence.
C'est dròle tout de même de se poser des questions sur un raisonnement aussi clair que le principe de récurrence.

[zygomatique]

salut

moi je dirais plutôt ::

le cinquième axiome est le principe de de récurrence

...

[Robot]

Curieux, la remarque de l'auteur de l'article: "Le 5ème axiome de Peano vérifie le principe de récurrence". J'aurais dit l'inverse: le 5ème axiome est fondé sur la récurrence.
C'est dròle tout de même de se poser des questions sur un raisonnement aussi clair que le principe de récurrence.

Nodjim, je crois que tu lis de travers !
Je cite le texte original :

Le premier axiome permet de poser que l'ensemble des entiers naturels n'est pas vide, le troisième qu'il possède un premier élément et le cinquième qu'il vérifie le principe de récurrence.

Ce n'est pas ce que tu écris.

[Monsieur23]

Aloha,

Ça dépend un peu de la définition de N que tu as. Par exemple, de l'axiome "Toute partie non vide de N contient un plus petit élément", tu peux démontrer le théorème de récurrence assez facilement.

[Robot]

Ça dépend un peu de la définition de N que tu as. Par exemple, de l'axiome "Toute partie non vide de N contient un plus petit élément", tu peux démontrer le théorème de récurrence assez facilement.

Comment ? (Tout bon ordre a cette propriété).

[beagle]

Les cinq axiomes de Péano sont combien?
5 ou 7?
le cinquième axiome de Péano est-il le mème que le cinquième axiome de Péano?

existe-t-il le principe de l'unicité de Péano?

l'arithmétique de Péano expliquée aux enfants sur wiki, ça pas facile...

[Robot]

A quoi sert de polluer le fil en écrivant n'importe quoi ?

[beagle]

A quoi sert de polluer le fil en écrivant n'importe quoi ?

J'ai tapé axiomes de Péano sur le web,
est-il par toi envisageable que je ne posséde pas les éditions originales des écrits de Péano

ensuite à partir du web j'ai eu du mal à trouver exposés les 5 axiomes,
tels que la phrase que tu cites
et à les rattacher au principe de récurrence,
excuse-moi!Et détends toi!

ne serait-ce que ceci:
https://fr.wikipedia.org/wiki/Discussion:Axiomes_de_Peano
les mecs sont des matheux, alors ai-je le droit avec mon faible niveau de dire que je ne m'y retrouve pas.Pourquoi es-tu perturbé par la forme de mon message.

PS: il aurait fallu que je tombe sur ceci: wikiversité
4.Tout sous-ensemble de \N contenant 0 et tous les successeurs de ses propres éléments est confondu avec \N. (Axiome de récurrence)
la parenthèse (axiome de récurrence) n'est pas dans la ref de wikipédia, et ici les axiomes vont de 1à4!!!

[Robot]

J'ai tapé axiomes de Péano sur le web,
est-il par toi envisageable que je ne posséde pas les éditions originales des écrits de Péano

Je ne les ai pas non plus, et alors ?

ensuite à partir du web j'ai eu du mal à trouver exposés les 5 axiomes,
tels que la phrase que tu cites
et à les rattacher au principe de récurrence

Il suffisait de cliquer sur le lien que j'ai mis plus haut (lien sur la page wikipedia). Très dur, en effet !

Finalement, c'est quoi ton problème ?

[beagle]

Je ne les ai pas non plus, et alors ?


Il suffisait de cliquer sur le lien que j'ai mis plus haut (lien sur la page wikipedia). Très dur, en effet !

Finalement, c'est quoi ton problème ?

mon problème c'est de lire ceci:"
A quoi sert de polluer le fil en écrivant n'importe quoi ?"

le reste va bien, merci!

[Robot]

Finalement, tu as trouvé la page wikipedia dont tout le monde parle dans ce fil ? :lol3:
M'est avis que tu as fait une fausse manip' pour te retrouver sur l'onglet "discussion" de cette page : pas le meilleur moyen d'y comprendre quelque chose.

[Monsieur23]

Comment ? (Tout bon ordre a cette propriété).

Prends , et suppose que .

Alors a un plus petit élément , qui n'est pas 0 (puisque P(0)) par hypothèse. Soit n=p-1. Par définition de p, on a P(n), et par hypothèse P(p) : contradiction.

[Robot]

Prends , et suppose que .

Alors a un plus petit élément , qui n'est pas 0 (puisque P(0)) par hypothèse. Soit n=p-1. Par définition de p, on a P(n), et par hypothèse P(p) : contradiction.

Bien sûr, mais qu'as-tu donc dans tes axiomes pour ? Et dans quel langage ? Tu as un ordre puisque tu parles de plus petit élément. Mais ça ne suffit pas. Tu as aussi un "p-1" ; d'où vient-il ? L'addition est supposée donnée ?
Tu devrais préciser tout ça.
Les axiomes de Peano, eux, sont formulés dans le langage qui ne comprend que la constante 0 et la fonction successeur.

[Monsieur23]

Disons que je définis N comme l'ensemble des ordinaux finis, muni du bon ordre .

[Robot]

Tu te places dans ZF ? Quelle est la définition de "fini" ? Pourquoi existe-t-il un ensemble des ordinaux finis ?
Et tu ne réponds pas sur "p-1".

[Monsieur23]

Dans l'ordre
— dans ZF, ou ZFC (on fait des maths quoi).
— un ordinal fini est un ordinal qui ne contient pas d'ordinal limite.
— l'existence de l'ensemble des ordinaux finis est donnée par l'axiome de l'infini.
— si p est un entier non vide, on définit le prédécesseur de p comme l'unique ordinal fini dont le successeur est p (on ne parle que d'ordinaux successeurs, puisqu'on parle d'entiers naturels). On peut aussi définir p-1 comme le maximum de p.