Fiche 4 — Parties d'un ensemble

Vocabulaire et notations

Ensemble des parties. Soit $E$ un ensemble. L'ensemble formé de tous les sous-ensembles de $E$ s'appelle l'ensemble des parties de $E$ et se note $\mathcal{P}(E)$.

$\mathcal{P}(E)$ est lui-même un ensemble, dont les éléments sont eux-mêmes des ensembles.
$A \in \mathcal{P}(E)$ si et seulement si $A \subset E$. Le symbole $\in$ relie $A$ à $\mathcal{P}(E)$, alors que $\subset$ relie $A$ à $E$ : deux façons équivalentes de dire la même chose.

Cas particuliers. Pour tout ensemble $E$ :

$\emptyset \in \mathcal{P}(E)$ : l'ensemble vide est toujours une partie, car on a toujours $\emptyset \subset E$.
$E \in \mathcal{P}(E)$ : tout ensemble est une partie de lui-même, c'est-à-dire qu'on a toujours $E \subset E$.

Cardinal. Si $E$ a $n$ éléments, alors $\mathcal{P}(E)$ a $2^n$ éléments : $|\mathcal{P}(E)| = 2^{|E|}$.

Idée : pour chaque élément de $E$, on a deux choix indépendants — il est dans le sous-ensemble, ou il n'y est pas.

Notation et lecture. $\mathcal{P}(E)$ se lit « P de E » ou « ensemble des parties de E ».

Illustration

$\mathcal{P}(\{a, b, c\})$ : les $2^3 = 8$ sous-ensembles, organisés par taille. Les traits relient un sous-ensemble à un sous-ensemble plus grand qui le contient.

Exemples

$\mathcal{P}(\emptyset) = \{\,\emptyset\,\}$ : 1 élément (= $2^0$).
$\mathcal{P}(\{a\}) = \{\,\emptyset,\ \{a\}\,\}$ : 2 éléments (= $2^1$).
$\mathcal{P}(\{a, b\}) = \{\,\emptyset,\ \{a\},\ \{b\},\ \{a, b\}\,\}$ : 4 éléments (= $2^2$).
$|\mathcal{P}(\{1, 2, 3, 4\})| = 2^4 = 16$.

Pour s'entraîner

Liste tous les éléments de $\mathcal{P}(\{1, 2\})$.
Combien d'éléments dans $\mathcal{P}(\{1, 2, 3, 4, 5\})$ ?
Vrai ou faux ? (a) $\{1\} \in \mathcal{P}(\{1, 2\})$ (b) $1 \in \mathcal{P}(\{1, 2\})$.

Pour aller plus loin. Combien d'éléments dans $\mathcal{P}(\mathcal{P}(\{0\}))$ ? Et dans $\mathcal{P}(\mathcal{P}(\mathcal{P}(\{0\})))$ ? → voir l'exercice 6 (page suivante).

★Application directe

Donne $\mathcal{P}(E)$ en extension pour :
1. $E = \emptyset$
2. $E = \{0\}$
3. $E = \{a, b\}$
4. $E = \{1, 2, 3\}$
Soit $E = \{1, 2, 3\}$. Vrai ou faux ?
1. $\emptyset \in \mathcal{P}(E)$
2. $\emptyset \subset \mathcal{P}(E)$
3. $\{1\} \in \mathcal{P}(E)$
4. $\{1\} \subset \mathcal{P}(E)$
5. $\{\{1\}\} \in \mathcal{P}(E)$
6. $\{\{1\}\} \subset \mathcal{P}(E)$
7. $E \in \mathcal{P}(E)$
8. $\{E\} \subset \mathcal{P}(E)$

★★Comprendre et traduire

Sous-ensembles avec contrainte. Soit $E = \{1, 2, 3, 4, 5\}$.
1. Combien de sous-ensembles de $E$ contiennent l'élément $1$ ?
2. Combien ne contiennent pas $1$ ?
3. Vérifie que la somme vaut $|\mathcal{P}(E)|$. Pourquoi ?
4. Combien de sous-ensembles de $E$ contiennent à la fois $1$ et $2$ ?
Sous-ensembles par taille. Soit $E = \{a, b, c, d\}$.
1. Pour chaque $k \in \{0, 1, 2, 3, 4\}$, combien de sous-ensembles de $E$ ont exactement $k$ éléments ? Liste les sous-ensembles à 2 éléments.
2. Vérifie que la somme vaut $|\mathcal{P}(E)| = 2^4 = 16$.
Lien entre $\subset$ et $\in$. Pour chaque affirmation, vrai ou faux ?
1. Si $A \subset B$ alors $A \in \mathcal{P}(B)$.
2. Si $A \in \mathcal{P}(B)$ alors $A \subset B$.
3. $\{3\} \subset \{1, 2, 3\}$ équivaut à $\{3\} \in \mathcal{P}(\{1, 2, 3\})$.

★★★Pousser plus loin

$\mathcal{P}$ de $\mathcal{P}$. Donne $\mathcal{P}(\mathcal{P}(\{0\}))$ en extension. Vérifie que tu obtiens $2^{2^1} = 4$ éléments. Combien d'éléments compte $\mathcal{P}(\mathcal{P}(\mathcal{P}(\{0\})))$ ?
Pourquoi $2^n$ ? Imagine que $E = \{x_1, x_2, \ldots, x_n\}$. Pour décrire un sous-ensemble $A \subset E$, on indique pour chaque $x_i$ s'il est dans $A$ ou pas. Combien de choix au total ? Conclus.
Sous-ensembles à $k$ éléments. Combien y a-t-il de sous-ensembles à exactement 2 éléments dans un ensemble à 5 éléments ? À 3 éléments dans un ensemble à 5 ? Et à $k$ éléments dans un ensemble à $n$ ($n$ et $k$ donnés) ? On note ce nombre $\binom{n}{k}$ (lire « k parmi n »). Vérifie que $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ pour $n = 4$.