3. ENSEMBLES FINIS
27
Si A est un ensemble fini, il ne peut ˆ etre mis en bijection, d’apr` es la
propri´ et´ e (i), qu’avec un seul intervalle de la forme [ n ]. Cet entier est donc
d´ etermin´ e de fa¸ con unique. On l’appelle le cardinal de A (ou la cardinalit´ e
de A). On le note card A ou |A| (si aucune confusion n’est `
a craindre). On dit
encore que A contient n ´ el´ ements, ou que le nombre des ´ el´ ements de A est n.
On convient que l’ensemble vide est fini et l’on pose |∅| = 0. La proposition
suivante est une cons´ equence imm´ ediate de la d´ efinition du cardinal et des
Propri´ et´ es 3.1.
Proposition 3.2
(i) Toute partie d’un ensemble fini est finie.
(ii) Deux ensembles finis A et B ont mˆ eme cardinal, si et seulement s’il
existe une bijection de A sur B.
Si l’on sait qu’un ensemble A est fini, on ne sait pas pour autant le
mettre explicitement en correspondance biunivoque avec un ensemble [ n ].
La construction de ces correspondances repose sur les propri´ et´ es alg´ ebriques
ou g´ eom´ etriques que peuvent avoir ces ensembles. Les formules de la somme
et du produit, donn´ ees ci-dessous, sont fondamentales. Ce sont, en fait, les
seules v´ eritables formules de d´ enombrement.
Proposition 3.3 (formule de la somme). — Si A et B sont deux
ensembles finis, disjoints, leur r´ eunion A + B est finie et l’on a :
(3.1)
|A + B| = |A| + |B| .
D´ emonstration. — Par hypoth` ese, on a deux bijections ϕ : [ n ] → A et
ψ : [ p ] → B. On d´ efinit une bijection θ : [ n+p ] → A+B de la fa¸ con suivante.
La restriction de θ ` a [ n ] est ϕ. Ensuite, la restriction de θ ` a [ n + 1, n + p ]
est le produit de composition d’une bijection de [ n + 1, n + p ] sur [ p ] (cf.
Propri´ et´ e 3.1 (iii)) avec ψ.
Par r´ ecurrence sur k, si A 1 , A 2 , . . . , A k sont des ensembles finis et disjoints
deux `
a deux, alors
(3.2)
|A 1 + · · · + A k | = |A 1 | + · · · + |A k |
(k ≥ 1).
Lorsque A et B sont finis, mais non n´ ecessairement disjoints, on a la formule
dite des quatre cardinaux :
(3.3)
|A ∪ B| + |A ∩ B| = |A| + |B| .
On retrouve une formule d´ ej` a obtenue pour les probabilit´ es et qui se d´ emontre
de la mˆ eme fa¸ con.
La formule pour les cardinaux qui correspond `
a la formule de Poincar´ e
pour les probabilit´ es porte le nom de formule du principe d’inclusionexclusion. Elle a la mˆ eme allure et se d´ emontre, ´ evidemment, de la mˆ eme
fa¸ con. En fait, si P d´ esigne l’´ equir´ epartition sur un ensemble fini Ω et si les
ensembles consid´ er´ es sont des sous-ensembles de Ω, on a |A| = P(A)|Ω|. Il
n’y a donc pas lieu de red´ emontrer cette formule. Citons-la pour r´ ef´ erence.
27
Si A est un ensemble fini, il ne peut ˆ etre mis en bijection, d’apr` es la
propri´ et´ e (i), qu’avec un seul intervalle de la forme [ n ]. Cet entier est donc
d´ etermin´ e de fa¸ con unique. On l’appelle le cardinal de A (ou la cardinalit´ e
de A). On le note card A ou |A| (si aucune confusion n’est `
a craindre). On dit
encore que A contient n ´ el´ ements, ou que le nombre des ´ el´ ements de A est n.
On convient que l’ensemble vide est fini et l’on pose |∅| = 0. La proposition
suivante est une cons´ equence imm´ ediate de la d´ efinition du cardinal et des
Propri´ et´ es 3.1.
Proposition 3.2
(i) Toute partie d’un ensemble fini est finie.
(ii) Deux ensembles finis A et B ont mˆ eme cardinal, si et seulement s’il
existe une bijection de A sur B.
Si l’on sait qu’un ensemble A est fini, on ne sait pas pour autant le
mettre explicitement en correspondance biunivoque avec un ensemble [ n ].
La construction de ces correspondances repose sur les propri´ et´ es alg´ ebriques
ou g´ eom´ etriques que peuvent avoir ces ensembles. Les formules de la somme
et du produit, donn´ ees ci-dessous, sont fondamentales. Ce sont, en fait, les
seules v´ eritables formules de d´ enombrement.
Proposition 3.3 (formule de la somme). — Si A et B sont deux
ensembles finis, disjoints, leur r´ eunion A + B est finie et l’on a :
(3.1)
|A + B| = |A| + |B| .
D´ emonstration. — Par hypoth` ese, on a deux bijections ϕ : [ n ] → A et
ψ : [ p ] → B. On d´ efinit une bijection θ : [ n+p ] → A+B de la fa¸ con suivante.
La restriction de θ ` a [ n ] est ϕ. Ensuite, la restriction de θ ` a [ n + 1, n + p ]
est le produit de composition d’une bijection de [ n + 1, n + p ] sur [ p ] (cf.
Propri´ et´ e 3.1 (iii)) avec ψ.
Par r´ ecurrence sur k, si A 1 , A 2 , . . . , A k sont des ensembles finis et disjoints
deux `
a deux, alors
(3.2)
|A 1 + · · · + A k | = |A 1 | + · · · + |A k |
(k ≥ 1).
Lorsque A et B sont finis, mais non n´ ecessairement disjoints, on a la formule
dite des quatre cardinaux :
(3.3)
|A ∪ B| + |A ∩ B| = |A| + |B| .
On retrouve une formule d´ ej` a obtenue pour les probabilit´ es et qui se d´ emontre
de la mˆ eme fa¸ con.
La formule pour les cardinaux qui correspond `
a la formule de Poincar´ e
pour les probabilit´ es porte le nom de formule du principe d’inclusionexclusion. Elle a la mˆ eme allure et se d´ emontre, ´ evidemment, de la mˆ eme
fa¸ con. En fait, si P d´ esigne l’´ equir´ epartition sur un ensemble fini Ω et si les
ensembles consid´ er´ es sont des sous-ensembles de Ω, on a |A| = P(A)|Ω|. Il
n’y a donc pas lieu de red´ emontrer cette formule. Citons-la pour r´ ef´ erence.