Langage de la logique et des ensembles

Nombre de parties d'un ensemble fini - Exercice 1

30 min
50
Voici un résultat important.
Question 1
Soit nn un nombre entier naturel. Soit EE un ensemble dont l'ensemble des parties est notée P(E)\mathscr{P}(E). On admet que EE est dénombrable (c'est-à-dire fini) tel que card(E)=n\mathrm{card}(E) = n.

Dénombrer, en fonction de nn, les parties de EE.

Correction
Analysons les premières situations possibles. Souvenons nous que l'ensemble vide \emptyset est une partie de tout ensemble EE, donc {}P(E)\{ \emptyset \} \in \mathscr{P}(E).
Casn=0:{\color{blue}{\bullet \,\, Cas \,\, n=0 :}}
Dans ce cas l'ensemble EE s'identifie à l'ensemble vide \emptyset.
Donc E={}E = \{ \emptyset \}.
Dans ce cas, il n'y a qu'une seule partie {}\{ \emptyset \}.
Casn=1:{\color{blue}{\bullet \bullet \,\, Cas \,\, n=1 :}}
Dans ce cas l'ensemble EE est constitué d'un élément aa.
Donc E={a}E = \{ a \}.
Dans ce cas, il y a deux parties possibles {}\{ \emptyset \} et {a}\{ a \}.
Casn=2:{\color{blue}{\bullet \bullet \bullet \,\, Cas \,\, n=2 :}}
Dans ce cas l'ensemble EE est constitué de deux éléments aa et bb.
Donc E={a;b}E = \{ a \,;\, b \}.
Dans ce cas, il y a quatre parties possibles {}\{ \emptyset \}, {a}\{ a \}, {b}\{ b \} et {a;b}\{ a \,;\, b \}.
Casn=3:{\color{blue}{\bullet \bullet \bullet \bullet \,\, Cas \,\, n=3 :}}
Dans ce cas l'ensemble EE est constitué de trois éléments aa, bb et cc.
Donc E={a;b;c}E = \{ a \,;\, b \,;\, c \}.
Dans ce cas, il y a huit parties possibles {}\{ \emptyset \}, {a}\{ a \}, {b}\{ b \}, {c}\{ c \}, {a;b}\{ a \,;\, b \}, {a;c}\{ a \,;\, c \}, {b;c}\{ b \,;\, c \}, et {a;b;c}\{ a \,;\, b \,;\, c \}.
Casn=4:{\color{blue}{\bullet \bullet \bullet \bullet \bullet \,\, Cas \,\, n=4 :}}
Dans ce cas l'ensemble EE est constitué de quatre éléments aa, bb, cc et dd.
Donc E={a;b;c;d}E = \{ a \,;\, b \,;\, c \,;\, d\}.
Dans ce cas, il y a seize parties possibles {}\{ \emptyset \}, {a}\{ a \}, {b}\{ b \}, {c}\{ c \}, {d}\{ d \}, {a;b}\{ a \,;\, b \}, {a;c}\{ a \,;\, c \}, {a;d}\{ a \,;\, d \}, {b;c}\{ b \,;\, c \}, {b;d}\{ b \,;\, d \}, {c;d}\{ c \,;\, d \}, {a;b;c}\{ a \,;\, b \,;\, c \}, {a;b;d}\{ a \,;\, b \,;\, d \}, {a;c;d}\{ a \,;\, c \,;\, d \}, {b;c;d}\{ b \,;\, c \,;\, d \} et {a;b;c;d}\{ a \,;\, b \,;\, c \,;\, d \}.
On constate alors que :
Sin=0{\color{red}{\bullet \,\, Si \,\, n=0}} alors il y a 20=1{\color{red}{2^0 = 1}} partie dans P(E)\mathscr{P}(E) ;
Sin=1{\color{red}{\bullet \bullet \,\, Si \,\, n=1}} alors il y a 21=2{\color{red}{2^1 = 2}} parties dans P(E)\mathscr{P}(E) ;
Sin=2{\color{red}{\bullet \bullet \bullet \,\, Si \,\, n=2}} alors il y a 22=4{\color{red}{2^2 = 4}} parties dans P(E)\mathscr{P}(E) ;
Sin=3{\color{red}{\bullet \bullet \bullet \bullet \,\, Si \,\, n=3}} alors il y a 23=8{\color{red}{2^3 = 8}} parties dans P(E)\mathscr{P}(E) ;
Sin=4{\color{red}{\bullet \bullet \bullet \bullet \,\, Si \,\, n=4}} alors il y a 24=16{\color{red}{2^4 = 16}} parties dans P(E)\mathscr{P}(E).
On constate alors qu'il semble que le nombre de parties différentes issues de l'ensemble EE, tel que card(E)=n\mathrm{card}(E) = n, soit donné par le nombre entier naturel 2n2^n. Ainsi, la question est la suivante : connaissant le nombre de partie d'un ensemble EE, à nn éléments distincts, quel est le nombre de parties possible d'un autre ensemble E\mathcal{E} qui construit à partir de EE auquel on a rajouter un seul élément, noté α\alpha ?
Ainsi E={{E};α}\mathcal{E} = \{ \{ E \} \,;\, \alpha\}.
Donc P(E)\mathscr{P}(\mathcal{E}) est constitué des parties P(E)\mathscr{P}(E), donc ne faisant pas apparaître l'élément α\alpha, auxquelles il faut ajouter toutes celles faisant apparaître l'élément α\alpha. Or, à chaque parties de P(E)\mathscr{P}(E) on peut venir greffer l'élément α\alpha (comme dans un arbre, pour lequel à chaque fois il y a deux choix pour une partie de P(E)\mathscr{P}(E) : on rajoute ou pas α\alpha). Donc, à partir de P(E)\mathscr{P}(E), on multiplie par 22 afin d'obtenir P(E)\mathscr{P}(\mathcal{E}). Comme card(E)=n\mathrm{card}(E) = n alors card(E)=n+1\mathrm{card}(\mathcal{E}) = n+1, et donc P(E)\mathscr{P}(\mathcal{E}) contient 2×2n=2n+12\times 2^n = 2^{n+1} parties différentes.
On peut donc conclure que :
Sicard(E)=nalorsP(E)contient2npartiesdiffeˊrentes.{\color{red}{\boxed{{\bf{Si}} \,\, \mathrm{card}(E) = n \,\, {\bf{alors}} \,\, \mathscr{P}(E) \,\, {\bf{contient}} \,\, 2^n \,\, {\bf{parties \,\, différentes}}.}}}
Autrement écrit :
card(P(E))=2card(E){\color{red}{\boxed{ \mathrm{card}\big(\mathscr{P}(E) \big) = 2^{\,\mathrm{card}(E)} }}}