le cardinal de l'ensemble des parties d'un ensemble

[invite9a651d79]

bonjour ,

dans une partie du cours de dénombrement j'ai vu la proposition suivante :

Si card (E) = n , alors car(P(E)) = 2^n avec P(E) : l'ensemble des parties de E

et lors de la démonstration j'ai pas compris un passage

Démonstration

La démonstration repose sur une récurrence sur le cardinal n.

L'ensemble vide a un seul sous-ensemble : lui-même.

(ce qui établit la propriété pour n=0, on a bien 2^0=1)
Supposons que nous avons établi la propriété pour un ensemble de m éléments. Soit E un ensemble ayant n=m+1 éléments, il est donc non vide, soit a un élément de E. Les sous-ensembles de E se divisent en deux parties disjointes :

celles des sous-ensembles auxquels a n'appartient pas, et celle des sous-ensembles auxquels a appartient.

Par hypothèse de récurrence, la première partie a 2m éléments. C'est le cas pour la seconde également, . Nous avons donc au total, 2*2^m=2^{m+1}=2^n sous-ensembles. Par conséquent, la propriété établie pour n=m+1 éléments.


le problème c'est que j'ai arriver à comprendre pourquoi la seconde va avoir le meme cardinal , car d'aprés ce que j'ai compris la seconde partie va etre l'ensemble des parties d'un ensemble de cardinal " n " car on a rajouter le "a" .

Merci bien pour votre aide
-----

[Médiat]

Bonjour,

On fabrique un sous-ensemble contenant a en construisant un sous-ensemble avec les m éléments différents de a (soit ) et en lui ajoutant l'élément a.

[invite9a651d79]

merci Médiat pour votre aide ;

Si je bien compris votre idée c'est que je vais diviser E en une partie ne contenant pas "a" et une autre qui ne contient que le singleton "a" , c à d que E est l'union des deux , pour la première il est de cardinal m donc l'ensemble de ses parties est de 2^m elements

et pour le singleton "a" l'ensemble de ses parties est 2^1 = 2 et par conséquent l'ensemble de tous les parties de E est 2*2^m , n'est ce pas !??

[invite179e6258]

non ce n'est pas ça, c'est P(E) qu'on divise en deux parties A et B. Les éléments de A ne contiennent pas a. C'est donc des parties d'un ensemble à n éléments, et même toutes les parties, donc il en a 2^n. Les éléments de B (i.e. les éléments de E qui contiennent a), tu peux les mettre en correspondance biuivoque avec ceux de A (il suffit de leur enlever a) et donc B a même cardinal que A : 2^n et donc le cardinal de E est 2^(n+1)

[A voir en vidéo sur Futura]

[invite179e6258]

ah pardon, j'avais mal compris. En fait l'idée de projects_simo n'est pas mauvaise, elle revient à dire que si E est la réunion disjointe de A et B, alors le bombre parties de E est le produit du nombre de parties de A par le nombre de parties de B. C'est un résultat qu'on utilise couramment quand on étudie la combinatoire.

[invited3a27037]

bonjour

Juste pour ton info, on démontre aussi ce résultat en comptant les parties à 0, 1, 2, ... n éléments d'un ensemble E à n éléments.

ce qui donne

la partie vide est comptabilisée

[invite9a651d79]

merci bcp toothpick-charlie pour l'illustration ; aprés un petit effort et quelques schématisations j'ai arrivé à comprendre ton idée , c'est vraiment une idée très intelligente

la seule chose dot je veux m'assurer : correspondance biuivoque c à d une bijection n'est ce pas ??

[invite9a651d79]

bonjour

Juste pour ton info, on démontre aussi ce résultat en comptant les parties à 0, 1, 2, ... n éléments d'un ensemble E à n éléments.

ce qui donne

la partie vide est comptabilisée

c'est très interresant joel_5632 , merci bcp pour l'info

les parties à 0, 1, 2, ... n éléments d'un ensemble E ont n+1 éléments si je ne me trompe pas n'est ce pas ??

Svp pourquoi card (P(E)) = la somme des combinaisons dans ce cas !!!

[invited3a27037]

Non, dans un ensemble de n éléments:

il y a partie à 0 éléments (la partie vide)
il y a parties à 1 élément (tous les singletons)
il y a parties à 2 éléments
...
il y a partie à n éléments (l'ensemble E tout entier)

total

[invite9a651d79]

aaah oui vous avez tout à fait raison , mercii bcp pour cette illustration

pour montrer que la somme des combinaisons = 2^n la formule du binome me servira bien , c vrai ??

merci aussi pour tous les autres membres

[invite179e6258]

merci bcp toothpick-charlie pour l'illustration ; aprés un petit effort et quelques schématisations j'ai arrivé à comprendre ton idée , c'est vraiment une idée très intelligente

mais pas de moi....

la seule chose dot je veux m'assurer : correspondance biuivoque c à d une bijection n'est ce pas ??

pardon, il fallait lire "biunivoque" oui c'est une bijection.