Dénombrement des ensembles finis [C1.II.3]

Dans le chapitre précédent (Le nombre d’éléments), nous avons appris à comparer le nombre d’éléments de deux ensembles sans avoir à les « compter », grâce aux notions d’injection, de surjection et de bijection.

Dans cette section, nous allons appliquer ces connaissances à la définition rigoureuse des ensembles finis, au dénombrement, c’est-à-dire au comptage « théorique » de certains d’entre eux, et plus largement à la combinatoire, c’est-à-dire à une théorie des ensembles finis.

1. Le nombre d’éléments d’un ensemble fini

1.1. Ensembles finis

Grâce à la notion de bijection, nous pouvons désormais définir rigoureusement ce qu’est un ensemble fini. Une fois n’est pas coutume, il suffit ici d’adopter la définition la plus intuitive qui soit : un ensemble est fini lorsqu’on peut en compter les éléments.

Définition 1.1
Un ensemble $E$ est dit fini si il existe une bijection entre $E$ et un sous-ensemble de $\mathbb N$ de la forme $[[1,n]]=\{m\in \mathbb N : 1\leq m\leq n\}$. Un ensemble $E$ est dit infini si il n’est pas fini.

Remarque 1.2
i) « Fini » et « infini » sont deux concepts « complémentaires » : si on a une définition de l’un, on a une définition de l’autre par la propriété opposée. La définition présente de l’infini peut paraître décevante.
ii) On pourrait définir autrement la notion d’ensemble infini et définir à partir de là la notion d’ensemble fini, mais cela serait assez maladroit. Nous donnerons dans le chapitre suivant deux caractérisations intéressantes des ensembles infinis, qui ne mentionnent pas explicitement les ensembles finis.
iii) La relation $\leq$ est pour l’instant entendue au sens intuitif, à moins de la définir à partir de l’addition grâce aux axiomes de Peano, que nous aborderons dans le chapitre sur l’ensemble des entiers naturels.
iv) Pour établir de nombreux résultats sur les ensembles finis, nous devrons utiliser le principe de récurrence (introduit dans le chapitre sur le raisonnement mathématique du Chapitre 1).

1.2. Compter les ensembles finis

Il semble évident qu’un ensemble fini possède un nombre bien déterminé d’éléments, lequel est un entier naturel. Cela n’est toutefois pas immédiatement visible à partir de la définition : si $E$ est un ensemble fini, il existe une bijection entre $E$ et un ensemble de la forme $[[1,n]]$, mais rien ne garantit a priori qu’il n’existe pas une bijection entre $E$ et un autre ensemble $[[1,m]]$ avec $m\neq n$ !

Il peut paraître étrange d’envisager une telle situation, mais gardons à l’esprit que nous théorisons rigoureusement la notion d’ensemble fini, et l’univocité du « nombre d’éléments » d’un tel ensemble ne fait pas partie explicitement de la définition.

Nous devons le vérifier pour obtenir une définition sensée d’un ensemble fini, et du nombre d’éléments d’un tel ensemble.

On se ramène pour commencer aux bijections entre ensembles de la forme $[[1,n]]$.

Lemme 1.3
Si $f:[[1,n]\hookrightarrow [[1,m]]$ est une injection, alors on a $n\leq m$.

Démonstration
Eliminons le cas où $m=0$ : on a alors $[[1,m]]=\{x\in\mathbb N : 1\leq m\leq 0\}=\emptyset$, puisqu’aucun entier supérieur à $1$ n’est nul, si bien que $[[1,n]]=\emptyset$ également, donc $n=0$, d’où $n\leq m$. Supposons désormais que $m>0$ et raisonnons par récurrence sur $n$. Si $n=0$, on a bien sûr $n\leq m$, et la propriété est vérifiée. Supposons que la propriété soit vérifiée pour l’entier $n$, et soit $f:[[1,n+1]]\hookrightarrow [[1,m]]$ une application injective; nous distinguons deux cas. Si $f(n+1)=m$, alors l’application $g:[[1,n]]\to [[1,m-1]]$, $i\mapsto f(i)$ (et qui est la co-restriction à $[[1,m-1]]$ de la restriction de $f$ à $[[1,n]]$) est injective, puisque $f$ est injective, et par hypothèse de récurrence, on a $n\leq m-1$, d’où $n+1\leq m$, ce qui est la propriété au rang $n+1$. Dans l’autre cas, c’est-à-dire si $f(n+1)\neq m$, soit $g:[[1,m]]\to [[1,m]]$ l’application définie par $g(f(n+1))=m$, $g(m)=f(n+1)$ et $g(i)=i$ pour tout $i\neq m,f(n+1)$ ($g$ « échange » $m$ et $n+1$); on vérifie facilement que $g$ est injective (en fait, $g$ est bijective), donc la fonction composée $g\circ f:[[1,n+1]]\hookrightarrow [[1,m]]\hookrightarrow [[1,m]]$ est injective, et $g\circ f(n+1)=m$ par définition de $g$. Par le premier cas, on en déduit cette fois encore que $n+1\leq m$, ce qui est la propriété au rang $n+1$. Par le principe de récurrence, le lemme est démontré. $\square$

Proposition 1.4
Si $E$ est un ensemble fini, il existe un unique entier naturel $n$ tel qu’il existe une bijection entre $E$ et $[[1,n]]$.

Démonstration
Par définition, il existe un entier natural $n$ et une bijection $f:E\to [[1,n]]$. Supposons que $m$ soit un entier naturel avec cette propriété, c’est-à-dire qu’il existe une bijection $g:E\cong [[1,m]]$. L’application composée $g\circ f^{-1}:[[1,n]]\to [[1,m]]$ est une bijection par [C1.II.2, proposition 2.5], et par le lemme 1.3 on a donc $n\leq m$. En considérant la bijection inverse $f\circ g^{-1}:[[1,m]]\to [[1,n]]$, pour la même raison on conclut que $m\leq n$, et finalement on a $n=m$, et $n$ est unique. $\square$

La figure suivante représente le dénombrement d’un ensemble $E$ possédant $5$ éléments.

Nous sommes désormais en mesure de définir proprement le nombre d’éléments d’un ensemble fini :

Définition 1.5
L’unique entier naturel $n$ tel que l’ensemble fini $E$ est en bijection avec l’ensemble $[[1,n]]$ s’appelle le cardinal de $E$ ou nombre d’éléments de $E$. On note $|E|$ le cardinal de $E$.

Remarque 1.6
Rappelons que nous avons défini le concept d’équipotence (« avoir le même nombre d’éléments ») avant d’avoir défini le nombre d’éléments d’un ensemble fini. En ce qui concerne les ensembles infinis, il n’est pas possible à ce stade de définir en théorie naïve des ensembles leur cardinal ou nombre d’éléments, même si on peut dire quand deux tels ensembles ont le même nombre d’éléments. Pour compter le nombre d’éléments d’un ensemble infini, il faut des cardinaux infinis, qui doivent être introduits à l’intérieur d’un « univers ensembliste ».

Proposition 1.7
Si $E$ est un ensemble fini à $n+1$ éléments, alors pour tout $x\in E$, l’ensemble $E-\{x\}$ est fini et possède $n$ éléments.

Démonstration
Par définition, il existe une bijection $f:E\cong[[1,n+1]]$; si $x\in E$, soit $F=E-\{x\}$, et soit $k=f(x)$. L’application $g:F\to [[1,n+1]]-\{k\}$, $y\in F\mapsto f(y)$, est évidemment une bijection (l’étudiant(e) est invité(e) à le vérifier), et il suffit par composition des bijections de démontrer maintenant la proposition pour $E=[[1,n+1]]$. En effet, si le résultat est démontrer pour ce type d’ensemble, alors $F$ et $[[1,n+1]]-\{k\}$ ont alors le même nombre d’éléments, soit $n$. Soient donc $k\in E=[[1,n+1]]$ et $f:E-\{k\}\to [[1,n]]$ définie comme suit : on pose $f(i)=i$ si $i<k$ (si $k=1$, ce cas n’existe pas) et $f(i)=i-1$ si $k<i$. Montrons que $f$ est injective : si $i,j\in E$ et $f(i)=f(j)$, soit $i,j<k$ et alors $i=f(i)=f(j)=j$, soit $i<k$ et $j>k$ et alors $i=f(i)=f(j)=j-1\geq k$, ce qui est impossible, soit $i,j>k$ et alors $i-1=f(i)=f(j)=j-1$, donc $i=j$ : dans tous les cas, on a $i=j$, donc $f$ est injective. Montrons que $f$ est surjective : si $j\in [[1,n]]$, soit $j<k$ et alors $f(j)=j$, soit $j>k$ et alors $f(j+1)=j$, donc $f$ est surjective. On conclut que $f$ est bijective, donc $[[1,n+1]]-\{k\}$ possède $n$ éléments, et la proposition est démontrée. $\square$

A partir de là, on peut démontrer la finitude de la réunion de deux ensembles finis :

Corollaire 1.8
La réunion de deux ensembles finis $E$ et $F$ est un ensemble fini.

Démonstration
On raisonne par récurrence sur le cardinal $m$ de $F-E$. Si $n=0$, on a $F-E=\emptyset$, donc $E\cup F=E$, ensemble fini par hypothèse. Supposons que la propriété soit vérifiée au rang $n$ et que $F-E$ possède $n+1$ éléments : en particulier, il existe $x\in F-E$, si bien que $(F-\{x\})-E=(F-E)-\{x\}$ est fini et possède $n$ éléments par la proposition 1.7. Par hypothèse de récurrence, l’ensemble $(E\cup F)-\{x\}=E\cup (F-\{x\})$ est fini, si bien qu’il existe une bijection $f:(E\cup F)-\{x\}\to [[1,m]]$ pour un certain entier $m$. Définissons une application $g:E\cup F\to [[1,m+1]]$ de la manière suivante : pour tout $y\in (E\cup F)-\{x\}$, on pose $g(y)=f(y)$, et on pose $g(x)=m+1$. On vérifie aisément que $g$ est une bijection, si bien que $E\cup F$ est fini. $\square$

Remarque 1.9
Il paraît « évident » que la réunion de deux ensembles finis est un ensemble fini. Cependant, en choisissant de traduire l’intuition de ce qu’est un ensemble fini par la définition que nous avons adoptée, il devient nécessaire d’établir rigoureusement ce qui relève de l’intuition originelle.

1.3. Exercices

Exercice 1.10
i) Démontrer que pour tout entier naturel $n$, l’ensemble $[[0,n]]=\{k\in\mathbb N : 0\leq k\leq n\}$ est fini, de cardinal $n+1$.
ii) Si $E$ et $F$ sont deux ensembles finis, de cardinaux respectifs $m$ et $n$, montrer par récurrence sur $n$ que le cardinal de $E\cup F$ est inférieur ou égal à $m+n$.

2. Les sous-ensembles d’un ensemble fini