Principe de récurrence et raisonnement par l'absurde

[anonyme89]

Bonjour, voilà j'ai un petit problème avec mon exercice de maths, j'aurais donc besoin d'aide! Mais comme personne n'a su m'aider sur le forum lycée je m'en remets à vous. :lol3:
On rappelle le principe de récurrence:
Théorème 1: Soit P(n) une propriété indéxée par les entiers. Si P(0) est vraie et si pour tout n appartenant à N, P(n) --> P(n+1) alors P(n) est vraie pour tout n appartenant à N .
Il s'agit de démontrer dans ce devoir que ce théorème et équivalent au théorème plus naturel suivant:
Théorème 2: Toute partie non vide de N admet un plus petit élément.

I/ th1 --> th2
L'hypothèse dans cette partie est donc que le théorème un est vrai autrement dit que le principe de récurrence est correct.
Considérons une partie A de N qui n'admet pas de plus petit élément.
1) Montrer par récurrence la propriété P(n): 0,1,2,...,n n'appartiennent pas à A
2) En déduire que A est vide puis le théorème 2.

II/ th2 --> th2
l'hypothèse dans cette partie est donc que le théorème 2 est vrai.
Considérons alors une propriété P(n) telle que P(0) soit vraie et telle que P(n) --> P(n+1) pour tout n appartient à N .
On raisonne par l'absurde. Supposons que P(n) ne soit pas vraie pour tout entier n et notons A l'ensemble des entiers naturels pour lesquels P(n) est fausse.
1) Considérer le plus petit élément d de A et mettre en évidence une contradiction.
2) En déduire le théorème 1

Pour la partie I) j'ai eu quelques idées mais je ne suis pas sur que cela suffise:
0 n'est pas dans A puisque si il était dans A il serait le plus petit élément.
Pour la partie II) je sais vraiment pas comment faire.
Je vous remercie d'avance pour votre aide :we:

[mrif]

Pour le 1) c'est ça l'idée avec l'argument, 0 est le plus petit élément de N donc s'il appartenait à A, il serait son plus petit élément. Supposons que pour tout i <= n, i n'appartient pas à A et montrons que n+1 n'appartient pas à A. En effet si n+1 appartenait à A il en serait son plus petit élément, ...

Pour le 2) Si A est non vide, soit p son plus petit élément. p est strictement positif puisque P(0) est vrai.
Pour tout i <= p-1 , P(i) est vraie, et P(p) est fausse cela contredit l'hypothèse de récurrence, donc A est vide.

[leon1789]

th1 --> th2 se fait de manière naturelle (par récurrence, sans raison par l'absurde)

Prouvons par récurrence H(n) : >

H(0) est évident.

Admettons H(n) pour un certain et prouvons H(n+1) : soit E une partie contenant n+1. Si elle contient un élément , alors H(n) s'applique à E et prouve que E a un plus petit élément. Sinon n+1 est le plus petit élément de E ! Ainsi H(n+1) est prouvé dans tous les cas.

H(n) étant vraie pour tout , on conclut que toute partie non vide (contenant un entier n) possède un plus petit élément.

[anonyme89]

Tout d'abord merci de vos réponses :we:
J'ai très bien compris comment expliquer ma partie I) grâce à vos deux réponses qui m'ont beaucoup aider!

Pour la partie II) je vous montre comment j'ai rédigé, j'aimerai savoir si ça convient merci

Soit P(n) une propriété telle que P(0) soit vraie et telle que si P(n) est vraie alors P(n+1) aussi.
On note A l'ensemble des entiers naturels pour lesquels P(n) est fausse. On suppose A non vide alors comme partie de N, il admet un plus petit élément qu'on note d. Alors P(d) est fausse. Mais c'est donc que P(d-1) est aussi fausse, puisque si elle etait vraie, P(d) le serait aussi pas définition de P. Donc d-1 appartient à A et est plus petit que d qui est supposé être le plus petit élément de A. Contradiction!
On en déduit que A est vide et donc que P(n) est vraie pour tout n.
voilà j'espère que c'est compréhensible :lol3:

[leon1789]

Soit P(n) une propriété telle que P(0) soit vraie et telle que si P(n) est vraie alors P(n+1) aussi.
On note A l'ensemble des entiers naturels pour lesquels P(n) est fausse. On suppose A non vide alors comme partie de N, il admet un plus petit élément qu'on note d. Alors P(d) est fausse. Mais c'est donc que P(d-1) est aussi fausse, puisque si elle etait vraie, P(d) le serait aussi pas définition de P. Donc d-1 appartient à A et est plus petit que d qui est supposé être le plus petit élément de A. Contradiction!
On en déduit que A est vide et donc que P(n) est vraie pour tout n.
voilà j'espère que c'est compréhensible :lol3:

C'est tout à fait compréhensible, mais il y a une petite imprécision dans ce que tu dis : peux-tu la trouver ?
1er indice : où te sers-tu du fait P(0) est vraie ?

2nd indice (à lire si le 1er indice ne t'a pas suffit) :
si d est un entier naturel, est-ce que d-1 est un entier naturel ?

[anonyme89]

Comme P(0) est vraie, 0 n'appartient pas à A.
donc le plus petit élément de A d>0 donc d-1 est un entier naturel ? :hein:
Je sais pas si c'est ça

[leon1789]

Comme P(0) est vraie, 0 n'appartient pas à A.
donc le plus petit élément de A d>0 donc d-1 est un entier naturel

Ben oui, c'est exactement cela !
Il faut insérer ces deux phrases dans ta démo.

[anonyme89]

d'accord je vais le faire! :lol3:

Je tiens à vous remercier pour le temps et l'aide que vous m'avez accordé, c'était très gentil et ça m'a bien aider :we: