Ensembles finis, ensembles dénombrables
Définition
Soit \(E\) un ensemble. On dit que :
\(E\) est fini s’il est vide ou s’il existe un entier naturel \(n\) non nul et une application bijective de \(E\) sur \(\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\). Un tel entier \(n\), s’il existe, est unique et appelé cardinal de \(E\), et noté \(\mathrm{Card}\,(E)\). Par convention, on pose : \(\mathrm{Card}\,(\varnothing)=0\).
\(E\) est dénombrable s’il existe une application bijective de \(E\) sur \(\mathbb{N}^\ast\).
Remarques
Si \(E\) est fini, \(\mathrm{Card}\,(E)\) est donc égal au nombre d’éléments de \(E\).
Pour faire simple, un ensemble est dit dénombrable si l’on peut numéroter ses éléments.
Dénombrer un ensemble, c’est déterminer son cardinal.
\(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{Q}\) sont des ensembles dénombrables. \(\mathbb{R}\) et les intervalles de \(\mathbb{R}\) non réduits à un point ne sont pas dénombrables.
Proposition
Soient \(E\) et \(F\) deux ensembles. Si \(E\) est fini et s’il existe une bijection de \(E\) sur \(F\) et si \(E\) est fini, alors \(F\) est fini et : \(\mathrm{Card}\,(E)=\mathrm{Card}\,(F)\).
Remarque
Ce résultat est un résultat essentiel en dénombrement. Ainsi, pour dénombrer un ensemble \(F\), on peut chercher un ensemble \(E\) dont le cardinal est simple à déterminer, en bijection avec \(F\).
Théorème
partiefinie
Si \(E\) est un ensemble fini et si \(F\) est une partie de \(E\), alors :
\(F\) est fini et : \(\mathrm{Card}\,(F)\leqslant \mathrm{Card}\,(E)\)
si \(\mathrm{Card}\,(F)=\mathrm{Card}\,(E)\), alors : \(F=E\)
Proposition
Si \(E\) et \(F\) sont deux ensembles finis et disjoints, alors \(E\cup F\) est fini et : \[\mathrm{Card}\,(E\cup F) =\mathrm{Card}\,(E)+\mathrm{Card}\,(F)\]
Plus généralement, si \(E_1,\dots,E_n\) sont \(n\) ensembles deux à deux disjoints (\(n\) désignant un entier naturel non nul), alors \(E_1\cup \dots\cup E_n\) est fini et : \[\mathrm{Card}\,\left(\bigcup_{i=1}^n E_i\right)=\sum_{i=1}^n \mathrm{Card}\,(E_i)\]
Proposition
Si \(E\) est un ensemble fini et si \(F\) est une partie de \(E\), alors : \(\mathrm{Card}\,(\overline{F})=\mathrm{Card}\,(E)-\mathrm{Card}\,(F)\).
Comme \(F\) et \(\overline{F}\) sont disjoints et comme \(F\cup \overline{F}=E\), on a : \[\mathrm{Card}(F)+\mathrm{Card}(\overline{F})=\mathrm{Card}(E)\] ce qui prouve le résultat attendu.
Proposition
Si \(E\) et \(F\) sont deux ensembles finis, alors \(E\cup F\) et \(E\cap F\) sont des ensembles finis et : \[\mathrm{Card}\,(E\cup F)=\mathrm{Card}\,(E)+\mathrm{Card}\,(F)-\mathrm{Card}\,(E\cap F)\]
Exercice
Démontrer la proposition. On pourra commencer par écrire \(E\cup F\) comme la réunion de trois ensembles deux à deux disjoints.
Solution
\(E\cap F\) est un sous-ensemble de \(E\), donc il est fini. De plus, on remarque que : \[E\cup F=(E\setminus F)\cup (F\setminus E)\cup (E\cap F)\]
Or les ensembles \(E\setminus F\), \(F\setminus E\) et \(E\cap F\) sont deux à deux disjoints donc, \(E\cup F\) est fini et : \[\mathrm{Card}(E\cup F)= \mathrm{Card}(E\setminus F) + \mathrm{Card}(F\setminus E) + \mathrm{Card}(E\cap F)\]
De plus on a : \[\mathrm{Card}(E\setminus F)=\mathrm{Card}(E)-\mathrm{Card}(E\cap F) \] et \[ \mathrm{Card}(F\setminus E)=\mathrm{Card}(F)-\mathrm{Card}(E\cap F)\]
et donc : \[\mathrm{Card}\,(E\cup F)=\mathrm{Card}\,(E)+\mathrm{Card}\,(F)-\mathrm{Card}\,(E\cap F)\]
Proposition – >Lemme des bergers
Soient \(E\) et \(F\) deux ensembles finis \(f\) une application surjective de \(E\) sur \(F\). Si, pour tout élément \(y\) de \(F\), \(f^{-1}(\{y\})\) est de cardinal \(p\) (\(p\) étant un entier naturel), alors : \(\mathrm{Card}\,(E)=p\times \mathrm{Card}\,(F)\).
Remarque
Cette proposition est intuitivement simple, surtout si l’on se souvient de sa traduction pastorale : si l’on admet que tous les moutons d’un troupeau ont quatre pattes, alors pour compter le nombre de pattes dans le troupeau, il suffit de compter le nombre de mouton puis de multiplier par \(4\) .
Exemple
Une jeu de carte usuel est composé de \(4\) couleurs (carreau, cœur, pique et trèfle) et chaque couleur comporte \(13\) cartes : \(As,2,3,\dots,10\), valet, dame et roi. Un jeu complet comporte donc \(4\times 13=52\) cartes.
Proposition
Si \(E\) et \(F\) sont deux ensembles finis, alors : \(\mathrm{Card}\,(E\times F)=\mathrm{Card}\,(E)\times \mathrm{Card}\,(F)\).
Preuve
On note \(n=\mathrm{Card}(E)\), \(p=\mathrm{Card}(F)\) et : \[E=\{e_i,i\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\} \quad\text{et}\quad\forall i\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]F_i=\{e_i\} \times F\] On a alors : \[E\times F=\bigcup_{i=1}^n F_i\] et alors, les ensembles \(F_1,\dots,F_n\) étant deux à deux disjoints : \[\begin{aligned} \mathrm{Card}(E\times F)&=\sum_{i=1}^n \mathrm{Card}(F_i) =\sum_{i=1}^n \mathrm{Card}(F)=np \end{aligned}\]