réunion est A ∪ B ; on a donc |A ∪ B| = |A| + |B \ (A ∩ B)|. Les parties A ∩ B et B \ (A ∩ B)
sont disjointes et leur réunion est B , donc on a |B \ (A ∩ B)| = |B| − |A ∩ B|, d’où la formule.
Proposition. Soient E et F des ensembles finis.
® Le nombre de couples (x,y) tels que x∈E et y∈F est |E||F | : on a donc |E ×F |=|E||F |.
® Le nombre d’applications de E dans F est |F |
|E| .
Démonstration. Posons n = |E| et p = |F |. Il y a n façons de choisir un élément de l’ensemble E et pour chacun de ces choix, il y a p façons de choisir un élément de l’ensemble F .
Il y a donc np couples (x, y) tels que x ∈ E et y ∈ F . Pour définir une application f : E → F ,
il faut, pour chaque élément x ∈ E , choisir son image f (x) parmi les éléments de F : pour
chaque élément de E , il y a donc p choix possibles. Puisque E possède n éléments, il y a
p × p × · · · × p
n facteurs
= p
n choix pour définir une application de E dans F .
Dans un ensemble fini, il y a évidemment un nombre fini de parties : par exemple,
l’ensemble {a, b, c} a pour parties ∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c} et {a, b, c}.
Corollaire. Dans un ensemble à n éléments, il y a 2
n parties.
Démonstration. Soit E un ensemble à n éléments et soit P l’ensemble des parties de E .
Nous allons établir une bijection entre P et l’ensemble F des applications de E dans {0, 1}.
Puisqu’il y a
{0, 1}
|E| = 2
n éléments dans l’ensemble F , cela démontrera le corollaire.
À toute partie A de E , associons la fonction c A : E → {0, 1} définie en posant c A (x) = 1 si
x ∈ A, c A (x) = 0 si x ∈ A. La fonction c A s’appelle la fonction caractéristique de la partie A.
À toute fonction f : E → {0, 1}, associons la partie X f de E formée des éléments x ∈ E tels
que f (x) = 1.
La fonction caractéristique de la partie X f est f et si A est une partie de E , alors la partie
associée à la fonction c A est A. L’application A → c A est donc une bijection de P dans F
et l’application f → X f est la bijection réciproque.
1.2 Applications entre ensembles finis
Soient E et F des ensembles finis et f : E → F une application.
Rappelons que l’image de l’application f est l’ensemble, noté f (E), des éléments
f (x), où x parcourt E . Les éléments f (x) ne sont pas nécessairement tous différents (si f est une application constante, ils sont tous égaux), mais en tous cas, leur
nombre est inférieur ou égal au nombre d’éléments de E . On a donc
f (E)
|E|.
De plus, f (E) étant une partie de F , on a
f (E)
|F |.
Résumons ces propriétés :
® Le nombre d’éléments dans l’image de f est inférieur ou égal à |E| et à |F |.
® On a f (E) = F si et seulement si
f (E)
= |F |.
En particulier, si E a strictement moins d’éléments que F , il existe au moins un
élément de F qui n’a pas d’antécédent par f .
58 – ENSEMBLES FINIS
sont disjointes et leur réunion est B , donc on a |B \ (A ∩ B)| = |B| − |A ∩ B|, d’où la formule.
Proposition. Soient E et F des ensembles finis.
® Le nombre de couples (x,y) tels que x∈E et y∈F est |E||F | : on a donc |E ×F |=|E||F |.
® Le nombre d’applications de E dans F est |F |
|E| .
Démonstration. Posons n = |E| et p = |F |. Il y a n façons de choisir un élément de l’ensemble E et pour chacun de ces choix, il y a p façons de choisir un élément de l’ensemble F .
Il y a donc np couples (x, y) tels que x ∈ E et y ∈ F . Pour définir une application f : E → F ,
il faut, pour chaque élément x ∈ E , choisir son image f (x) parmi les éléments de F : pour
chaque élément de E , il y a donc p choix possibles. Puisque E possède n éléments, il y a
p × p × · · · × p
n facteurs
= p
n choix pour définir une application de E dans F .
Dans un ensemble fini, il y a évidemment un nombre fini de parties : par exemple,
l’ensemble {a, b, c} a pour parties ∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c} et {a, b, c}.
Corollaire. Dans un ensemble à n éléments, il y a 2
n parties.
Démonstration. Soit E un ensemble à n éléments et soit P l’ensemble des parties de E .
Nous allons établir une bijection entre P et l’ensemble F des applications de E dans {0, 1}.
Puisqu’il y a
{0, 1}
|E| = 2
n éléments dans l’ensemble F , cela démontrera le corollaire.
À toute partie A de E , associons la fonction c A : E → {0, 1} définie en posant c A (x) = 1 si
x ∈ A, c A (x) = 0 si x ∈ A. La fonction c A s’appelle la fonction caractéristique de la partie A.
À toute fonction f : E → {0, 1}, associons la partie X f de E formée des éléments x ∈ E tels
que f (x) = 1.
La fonction caractéristique de la partie X f est f et si A est une partie de E , alors la partie
associée à la fonction c A est A. L’application A → c A est donc une bijection de P dans F
et l’application f → X f est la bijection réciproque.
1.2 Applications entre ensembles finis
Soient E et F des ensembles finis et f : E → F une application.
Rappelons que l’image de l’application f est l’ensemble, noté f (E), des éléments
f (x), où x parcourt E . Les éléments f (x) ne sont pas nécessairement tous différents (si f est une application constante, ils sont tous égaux), mais en tous cas, leur
nombre est inférieur ou égal au nombre d’éléments de E . On a donc
f (E)
|E|.
De plus, f (E) étant une partie de F , on a
f (E)
|F |.
Résumons ces propriétés :
® Le nombre d’éléments dans l’image de f est inférieur ou égal à |E| et à |F |.
® On a f (E) = F si et seulement si
f (E)
= |F |.
En particulier, si E a strictement moins d’éléments que F , il existe au moins un
élément de F qui n’a pas d’antécédent par f .
58 – ENSEMBLES FINIS