Le cardinal de $\mathcal{P}(E)$

La réponse est $\mathrm{Card}\mathcal{P}(E)=2^n$.

Initialisation. Si $n=0$, alors $E=\varnothing$ et $\mathcal{P}(E)=\{\varnothing \}$ : un élément, et $2^0=1$. Attention, $\varnothing$ et $\{\varnothing \}$ ne sont pas la même chose.

Hérédité. Soit $E$ à $n+1$ éléments. Fixons $a\in E$ et posons $E^{\prime }=E\setminus \{a\}$, qui a $n$ éléments. Les parties de $E$ se répartissent sans recouvrement en deux familles :

• celles qui ne contiennent pas $a$ : ce sont exactement les parties de $E^{\prime }$, il y en a $2^n$ ;
• celles qui contiennent $a$ : chacune s'écrit $B\cup \{a\}$ avec $B\subset E^{\prime }$, et cette écriture est unique — il y en a donc $2^n$ aussi.

Au total $2^n+2^n=2^{n+1}$.

C'est le même comptage que « choisir, pour chaque élément, s'il est dans la partie ou non » : $n$ choix binaires indépendants, d'où $2^n$.