montrer que 2 ensembles sont égaux.

[worgui]

Bonjour, le but de l'exercice est de montrer que 2 ensembles sont égaux, je l'ai fait, cependant vu que j ai toujours eu du mal avec des démonstrations de ce type, je ne sais pas si ma rédaction est assez bonne et rigoureuse du coup j'aimerai que vous me disiez ce qui ne va pas svp.

Soit A une partie de N* contenant 1 et telle que:
i) ∀n∈A, 2n∈A et ii)∀n∈N*, n+1∈A ⇒ n∈A

1)Montrer: ∀m∈N, (2^m)∈A récurrence facile
2) A=N* (question qui me pose problème)

2) A=N* ⇔ AcN* et N*cA. Par hypothèse AcN*. On veut montrer que N*cA donc que ∀n∈N* n∈A
On raisonne par récurrence forte.

I n=1, 1∈A Initialisation acquise
H On suppose ∀k∈{1,...,n} k∈A.
Montrons que n+1∈A
On distingue 2 cas:
1) n+1 pair donc n+1=2a, a∈{1,...,n} donc a∈A donc d'après i) 2a∈A donc n+1∈A
2)n+1 impair donc n+1=2b+1=b+b+1, b<n donc b+1<n+1 donc b+1⩽n donc b+1∈A donc d'après i) 2b+2∈A, ainsi ∀k∈{1,...,2b+2} k∈A or 2b+1<2b+2 donc 2b+1∈A donc n+1∈A
Conclusion
On a montré ∀n∈N* n∈A donc N*cA. Ainsi A=N*

Merci d'avance pour votre aide.
-----

[gg0]

Bonjour.

Ton deuxième cas (n+1 impair) ne conclut rien sur n+1, et même "est faux puisque justement, tu n'as rien dit de 2b+1.
Alors que c'est tellement simple de voir que 2b est dans A, puis de conclure. Rappel : n+1 impair dit n pair.

Attention, il faut justifier dans le premier cas que a est non nul et dans le deuxième, que b est non nul.

Cordialement.

[worgui]

Merci de ta réponse gg0

En fait dans mon 2) je construis un nouvel ensemble {1,...,2b+2} dont tous les éléments sont dans A,en montrant que 2b+2 est dans A et en me servant de l'hypothèse de récurrence, ainsi 2b+1∈{1,...,2b+2} puisque 2b+1<2b+2 donc 2b+1∈A. Ici peux tu m'expliquez plus précisément pourquoi cela est faux je te prie, je n'ai pas bien compris.

Aussi pour ce que tu me conseilles:n=2b+1 donc n=2b avec b non nul donc 2b∈A, mais arrivé ici je ne vois pas comment montrer que 2b+1∈A juste avec cela, pourrais tu là encore me donner un autre indice stp?

PS: Merci pour le rappel qu'il faut montrer que b et a sont des entiers naturels non nuls et désolé de ne pas avoir compris ce que tu voulais dire et crois moi j'ai passé pas mal de temps sur cet exo qui paraît pourtant élémentaire.

Cordialement.

[gg0]

Effectivement, j'avais mal lu l'énoncé, et toi, tu rédiges mal. Tu n'utilises pas explicitement la deuxième hypothèse (ce qui fait que je n'ai pas pu relire l'énoncé et voir mon erreur)
En fait, partant de 2b+1 est dans A, on déduit b+1 est dans A (hypothèse de récurrence), puis 2b+2 est dans A (propriété i), puis2b+2-1=2b+2=n+1 est dans A (propriété ii).
le tout est de justifier chaque étape avec la règle ou définition utilisée. Et ça doit être visible par le lecteur. Si tu sais quelle règle tu utilises, tu peux le dire. Si tu ne sais pas comment justifier, c'est que tu baratines, pas que tu démontres.

En fait, ici, b peut être nul (si ta seule initialisation est "1 est dans A", tu n'as pas le choix), mais même avec b=0, b+1 est dans A par hypothèse; et sinon, b+1 est au moins égal à 1 et inférieur à 2b+1, donc est dans A.
Pour a c'est assez évident, car si n est pair, il vaut au moins 2.

Cordialement.

[A voir en vidéo sur Futura]

[ansset]

il y a peut être plus court aussi , avec :

i) ∀n∈A, 2n∈A et
ii)∀n∈N*, n+1∈A ⇒ n∈A
et
1)Montrer: ∀m∈N, (2^m)∈A récurrence facile

du 1)et ii) on déduit en récurrence simple que ∀m∈N, {1,....,2^m}cA
il suffit pour n non nul , de choisir m=E(ln(n)/ln(2))+1

Cdt

[gg0]

J'y avais pensé Ansset, et peut-être Worgui aussi. Mais il faut alors démontrer que si x est dans A, pour tout y tel que 1<=y<x, y est dans A. Ce qui fait une récurrence inversée, avant la récurrence principale.

Cordialement.

[ansset]

oui, mais je viens de le mentionner dans mon post.

du 1)et ii) on déduit en récurrence simple que ∀m∈N, {1,....,2^m}cA

j'ai peut être employé à tord ( sur la forme ) le mot "simple".
car il faut effectivement écrire cette récurrence inversée, même si elle se fait en deux lignes.

ps : et aussi du coup, on n'a pas de récurrence principale, dans cette approche, mais une validation directe.

[worgui]

Merci à tous les deux.
En fait gg0 depuis le départ j ai cherché à utiliser ii) mais je ne l avais pas vu comment faire (même si cela semblait évident), en fait j ai fait un truc inutile sans l'utiliser (ce que tu n'as pas compris c'est pourquoi tu me reproches de ne pas avoir cité ii)) alors qu'en montrant tout simplement que 2b+2 etait dans A on utilisait ii) pour conclure que 2b+1 était dans A. Pour ce qui est de l'astuce avec "∀m∈N, (2^m)∈A" je n'y avais pas pensé donc merci beaucoup du coup de main.

Cordialement.

[PlaneteF]

Bonsoir,

Autre façon de voir en utilisant :

Par l'absurde, supposons que :

Compte tenu de : et avec une récurrence évidente il vient :

Donc . Absurde, cela contredit le 1)


Cordialement