Ensemble et récurrence

[log86]

Bonsoir je pense que c'est une démonstration qu'on voit souvent et je ne savais d'ailleurs pas si je devais poster ce message dans supérieur ou lycée.Je ne l'ai pas trouvé dans la recherche.
Je voudrais montrer par récurrence la propriété P(n):" Si E contient n éléments , P(E) contient 2^n éléments"
Voilà le début de la démonstration
Pour n=0 pas de problème

On suppose P(n) vraie pour un entier n >= 0 et on veut montrer P(n+1)
Soit E contenant n+1 éléments.Soit x un élément de E.
Une partie A de E contient x ou ne contient pas x
Soit X={A inclus ds E | xEA}
Soit A appartenant à X, A\{x} est composé d'éléments choisis dans E\{x}
Par hypothèse de récurrence X contient 2^n parties

Je ne comprends pas cette dernière phrase. Pourquoi le fait que A\{x} soit composé d'éléments choisis dans E\{x} (qui a n élément) çà implique que X contient 2^n parties?
Merci d'avance pour vos explications

[nuage]

Salut,
je n'arrive pas bien à comprendre ce que tu écrit, toutes mes excuses.
Je ferais comme suis :
Soit l'ensemble à éléments.
Par hypothèse de récurrence l'ensemble a parties.
À chacune de ces parties, disons , on associe la partie .
On a alors une bijection (ce qu'il faut démonter, mais c'est assez facile) entre l'ensemble des parties de et ensemble des parties de qui contiennent
etc...

En espérant être assez clair,
amicalement
nuage :

[log86]

Bonjour nuage, merci de ton aide.

je n'arrive pas bien à comprendre ce que tu écrit, toutes mes excuses.

Ce n'est pas la peine de t'excuser , çà doit être normal !
Je dois donc montrer que l'application
({}) ->

est une bijection, avec qui contiennent forcément .

Si , ={ensemble vide} ou {} ou {} ou {}
={} ou {,}ou {,} ou {,}
donc je vois bien qu'il y a une bijection mais je ne vois pas comment je peux le démontrer. Est ce que je dois le démontrer par récurrence?
Merci

[abcd22]

Bonjour,
On peut construire la bijection réciproque pour montrer que c'est bien une bijection.

[log86]

Bonjour abcd22 merci pour l'indication !
Est ce que vous pourriez me dire si ce que je fais est bon s'il vous plait? Merci
Soit f: ({}) ->X tel que = }
soit g:X ->({}) tel que = \{}
on a
(fog)(A)=f(g(A))=f(\{})=\{}=A
et
(gof)(A)=g(f(A))=g()=\{}=A
donc fog=gof=Id donc f est bijective de bijection réciproque g

Est ce que c'est correct? Merci

désolé j'ai un peu de mal avec latex à chaque fois c'est {}

[Flodelarab]

Je voudrais montrer par récurrence la propriété P(n):" Si E contient n éléments , P(E) contient 2^n éléments"
Voilà le début de la démonstration
Pour n=0 pas de problème

.... Ben, si. Problème. Pour n=0, tu affirmes donc qu'il existe une partition ? L'ensemble vide n'a pas de partition. Pour n=1 ? Il y a une partition possible. Pas deux.

Je crois plutôt que: Si E contient n éléments , P(E) contient 2^n - 1 éléments (en considérant P(E) comme l'ensemble des partitions de E)

[nuage]

Salut Flodelarab,
si alors qui a bien 1 élément.

[log86]

Salut Flodelarab, comme toi au début j'ai cru que c'était faux mais en cherchant j'ai trouvé ce que nuage a dit.
Si je peux me permettre , est ce que pour la bijection c'est bon?
merci

[Flodelarab]

Une partition d'un ensemble X est un ensemble P de sous-ensembles non vides de X deux à deux disjoints et qui forment un recouvrement de X. Autrement dit P est une partition de X si et seulement si les parties de P sont non vides et tout élément x de X se trouve dans l'une exactement de ces parties.

http://www.techno-science.net/?onglet=glossaire&definition=6459
http://encyclopedie.snyke.com/articles/partition_mathematiques.html
http://www.maths-express.com/BAC-EXO/BAC-S/cour-S/cours-proba/partition.htm

On nous ment sur internet ?

[abcd22]

Je crois plutôt que: Si E contient n éléments, P(E) contient 2^n - 1 éléments (en considérant P(E) comme l'ensemble des partitions de E)

Mais P(E) est l'ensemble des parties de E, pas l'ensemble des partitions de E.

[Flodelarab]

;-) ok merci.

[Flodelarab]

;-) ok merci.

Ce qui m'amène à la première chose que je voulais dire: Je trouve la récurrence maladroite.

Pour former une partie de E, on détermine pour chaque élément s'il est (ou non) dans la partie.
On a donc une 2-liste de n éléments. Il y a donc 2^n parties possibles.

[charlol]

Bonjour ,
Moi la première chose qui me vient a l'esprit qd je veux ce cardinal , c'est la somme pour k allant de 0 (je pensais que la partie vide appartenait aux partitions mais donc mettons 1 ) a n des k parmi n .
Une égalité de lycée est : (a+b)^n=somme pour k allant de 0 a n des k parmi n *(a^k)*b^(n-k)
pour a=b=1 on a ma somme qui vaut 2^n -1
(dsl il faudra un jour que je télécharge les symboles :hum: )
Vous êtes sur que {0} est a exclure? :doh:

[Flodelarab]

Bonjour ,
Moi la première chose qui me vient a l'esprit qd je veux ce cardinal , c'est la somme pour k allant de 0 (je pensais que la partie vide appartenait aux partitions mais donc mettons 1 ) a n des k parmi n .
Une égalité de lycée est : (a+b)^n=somme pour k allant de 0 a n des k parmi n *(a^k)*b^(n-k)
pour a=b=1 on a ma somme qui vaut 2^n -1
(dsl il faudra un jour que je télécharge les symboles :hum: )
Vous êtes sur que {0} est a exclure? :doh:

pour a=b=1 on a ta somme qui vaut 2^n et pas 2^n-1 comme tu le dis
Je ne vois pas d'où sort le -1 et je ne vois pas pourquoi tu parles de cette formule.....

[log86]

En utilisant la méthode de charlol
Soit E un ensemble à n éléments. On cherche à compter toutes les parties de E. On fait donc la somme des parties à 0 éléments, 1 élément, 2éléments...jusqu'à n éléments.
On a partie de E à 0 éléments , parties à 1 éléments ,..., parties de E à n éléments.
Donc le cardinal de P(E)=++...+=
mais d'après la formule du binôme de Newton =
Donc P(E) contient éléments soit

Mais mon but ici est de le démontrer par récurrence sur n.

[log86]

Bonjour ,au risque d'être un peu gonflant, mais est ce que vous pourriez me dire si la démonstration, pour montrer la bijection, que j'ai fait dans le message 5 est bonne s'il vous plait?
Est ce que mes fonctions f et g sont bien "écrites", par rapport aux ensembles de départ et d'arrivée , c'est bon?
Je vous remercie.

[nuage]

Salut

Bonjour ,au risque d'être un peu gonflant, mais est ce que vous pourriez me dire si la démonstration, pour montrer la bijection, que j'ai fait dans le message 5 est bonne s'il vous plait?
Est ce que mes fonctions f et g sont bien "écrites", par rapport aux ensembles de départ et d'arrivée , c'est bon?
Je vous remercie.

J'ai l'impression que c'est bon.

[log86]

Salut nuage; merci pour ta réponse et surtout pour ton explication au début du sujet! J'ai compris!