Cardinaux

Nous allons utiliser la notion de bijection pour définir le cardinal d'un ensemble fini. Intuitivement, deux ensembles ont le même nombre d'éléments si et seulement si on peut définir une bijection entre ces ensembles. Les définitions qui suivent formalisent cette intuition.

Définition 5 Soient et des ensembles. On dit que et ont le même cardinal s'il existe une bijection de sur .

Soient un ensemble et un entier. On dit que est de cardinal si et $\{1,\dots,n\}$ ont le même cardinal.

Soit un ensemble. On dit que est fini s'il existe un entier tel que soit de cardinal .

Proposition 4 Soient et des entiers. S'il existe une injection

$\displaystyle f:\{1,\dots,m\}\longrightarrow\{1,\dots,n\}\;,$

alors $m\leqslant n$ .

Démonstration : On raisonne par récurrence sur

. Si

, la conclusion est vérifiée. Supposons le résultat vrai pour

. Soit

$\displaystyle f:\{1,\dots,m\}\longrightarrow\{1,\dots,n\}\;,$

une application injective. Comme

est injective, on a

$\displaystyle \forall i\in\{1,\dots,m\},\quad i\neq m\Rightarrow f(i)\neq f(m)\;.$

On peut donc définir

$\begin{displaymath}\begin{array}{rcl} \displaystyle g:\{1,\dots,m-1\}&\longright... ...(i)<f(m),\\ f(i)-1\text{ si }f(i)>f(m). \end{cases}\end{array}\end{displaymath}$

L'application ainsi définie est injective. Donc, par hypothèse de récurrence, $m-1\leqslant n-1$ . D'où $m\leqslant n$ . $\square$

Corollaire 2 Soient et des entiers. S'il existe une bijection de $\{1,\dots,m\}$ sur $\{1,\dots,n\}$ , alors .

Démonstration : Notons

une telle bijection. Alors

et $f^{-1}$ sont injectives et on applique la proposition précédente. $\square$

Ce corollaire montre que si est un ensemble de cardinal et de cardinal , alors . En effet, dans ce cas il existe une bijection de sur $\{1,\dots,m\}$ et de sur $\{1,\dots,n\}$ et $g\circ f^{-1}$ fournit une bijection de $\{1,\dots,m\}$ sur $\{1,\dots,n\}$ .

Définition 6 Soit un ensemble fini. On appelle cardinal de et on note $\mathrm{Card}(E)$ l'unique entier tel que soit de cardinal . $\mathrm{Card}(E)$

Exemple 1 Si , $b\in \mathbb{Z}$ , avec $a\leqslant b$ , alors

$\displaystyle \mathrm{Card}(\{a,a+1,\dots,b-1,b\}=b-a+1\;.$

En effet l'application

$\begin{displaymath}\begin{array}{rcl} f:\{a,\dots,b\}&\longrightarrow&\{1,\dots,b-a+1\}\\ x&\longmapsto&x-a+1 \end{array}\end{displaymath}$

est bijective.

Proposition 5 Soit un ensemble fini et une partie de . Alors

L'ensemble est fini;
$\mathrm{Card}(X)\leq\mathrm{Card}(E)$ ;
Si $\mathrm{Card}(X)=\mathrm{Card}(E)$ , alors .

Démonstration : Soit

le cardinal de

. Il existe donc une bijection $\Phi$ de

sur $\{1,\dots,n\}$ . L'application obtenue par restriction à

$\begin{displaymath}\begin{array}{rcl} X&\longrightarrow&\displaystyle\Phi(X)\\ x&\longmapsto&\Phi(x)\;, \end{array}\end{displaymath}$

est également bijective. Quitte à remplacer

par $\Phi(X)$ , il suffit de traiter le cas où $E=\{1,\dots,n\}$ .

On raisonne alors par récurrence sur le cardinal de . Si , alors $E=X=\emptyset$ et le résultat est valide. Supposons le résultat démontré pour les ensembles de cardinal , et montrons le pour $E=\{1,\dots,n\}$ . Si , alors $\mathrm{Card}(X)=\mathrm{Card}(E)$ et les assertions a), b) et c) sont vérifiées. Si $X\neq E$ , il nous suffit de montrer que est fini de cardinal inférieur ou égal à . Mais dans ce cas, il existe $i\in\{1,\dots,n\}$ tel que $i\not\in X$ . On considère alors l'application

$\begin{displaymath}\begin{array}{rcl} \displaystyle f:\{x\in E\;;\quad x\neq i\}... ...} x\text{ si }x<i,\\ x-1\text{ si }x>i. \end{cases}\end{array}\end{displaymath}$

est bijective, donc $\mathrm{Card}(\{x\in E ;\; x\neq i\})=n-1$ et par hypothèse de récurrence

est fini et

$\displaystyle \mathrm{Card}(X)\leqslant n-1<\mathrm{Card}(E).$

ce qui montre les assertions dans ce cas. $\square$

Corollaire 3 Soient et des ensembles et $f:E\to F$ une application.

Si est fini et si est injective, alors

est fini;
$\mathrm{Card}(E)\leq\mathrm{Card}(F)$ ;
est bijective si et seulement si $\mathrm{Card}(E)=\mathrm{Card}(F)$ .

Si est fini et si est surjective, alors

est fini;
$\mathrm{Card}(F)\leq\mathrm{Card}(E)$ ;
est bijective si et seulement si $\mathrm{Card}(E)=\mathrm{Card}(F)$ .

Démonstration : Si

est injective, on considère l'application

$\begin{displaymath}\begin{array}{rcl} g:E&\longrightarrow&f(E)\\ x&\longmapsto&f(x) \end{array}\end{displaymath}$

est bijective. Donc

ont même cardinal. Donc $\mathrm{Card}(E)=\mathrm{Card}(f(E))\leqslant \mathrm{Card}(F)$ . L'application

est bijective si et seulement si

ce qui est équivalent à $\mathrm{Card}(E)=\mathrm{Card}(F)$ par ce qui précède.

Supposons surjective, c'est-à-dire telle que

$\displaystyle \forall y\in F,\>\exists x\in E,\quad f(x)=y.$

Donc il existe une application $g:F\to E$ telle que

$\displaystyle \forall y\in F,\quad f(g(y))=y.$

La composée $f\circ g$ est l'application identique de

, donc

est injective. On applique alors le cas injectif à

. $\square$

Rappelons la définition du complémentaire. Soient et deux ensembles. On note $A\setminus B$ l'ensemble des élements de qui n'appartiennent pas à .

$\displaystyle A\setminus B=\{ x\in A ;\; x\not\in B \}\;.$

Si $B\subset A$ , $A\setminus B$ est appelé le complémentaire de

dans

Proposition 6 Si est fini et $B\subset A$ , alors

$\displaystyle \mathrm{Card}(A)=\mathrm{Card}(B)+\mathrm{Card}(A\setminus B).$

Démonstration : Par la proposition 5, on sait que

et $A\setminus B$ sont finis. Notons

le cardinal de

le cardinal de $A\setminus B$ . Il existe donc des bijections

$\displaystyle \Phi_1:B\longrightarrow \{1,\dots,p\}$

$\displaystyle \Phi_2:A\setminus B\longrightarrow \{p+1,\dots,p+q\}$

L'application

$\begin{displaymath}\begin{array}{rcl} \Phi:A&\longrightarrow&\{1,\dots,p+q\}\\ ... ...\ \Phi_2(x)\text{ si }x\in A\setminus B \end{cases}\end{array}\end{displaymath}$

est bijective donc $\mathrm{Card}(A)=p+q$ . $\square$

Proposition 7 Soient un ensemble fini, un entier et $(A_i)_{i\in\{1,\dots,r\}}$ une famille de parties de telle que

$A=A_1\cup\cdots\cup A_r$ ;
$\forall i,j\in\{1,\dots,r\},\quad i\neq j \Rightarrow A_i\cap A_j=\emptyset$

Alors

$\displaystyle \mathrm{Card}(A)=\sum_{i=1}^r\mathrm{Card}(A_i).$

Démonstration : On raisonne par récurrence sur

Si , et le résultat est vrai. Si c'est vrai pour , par hypothèse de récurrence, appliquée à l'ensemble $A_1\cup\dots\cup A_{r-1}$ , on a

$\displaystyle \mathrm{Card}(A_1\cup\dots\cup A_{r-1})=\sum_{i=1}^{r-1}\mathrm{Card}(A_i).$

Mais $A_r=A\setminus (A_1\cup\dots\cup A_{r-1})$ . Donc

$\displaystyle \mathrm{Card}(A)=\mathrm{Card}(A_r)+\sum_{i=1}^{r-1}\mathrm{Card}(A_i)$

ce qui prouve le résultat pour

. $\square$

Définition 7 Soit un ensemble fini et soit $(\lambda_e)_{e\in E}$ une famille de nombres réels (ou complexes) Soit $\Phi:\{1,\dots,n\}\to E$ une bijection. La somme

$\displaystyle \sum_{i=1}^n\lambda_{\Phi(i)}$

ne dépend pas du choix de $\Phi$ , on la note $\sum_{e\in E}\lambda_e$ . $\sum_{e\in E}\lambda_e$

Exemple 2 Ainsi $\mathrm{Card}(E)=\sum_{e\in E}1$ .

On peut définir de même le produit $\prod_{e\in E}\lambda_e$ . $\prod_{e\in E}\lambda_e$

Corollaire 4 (Principe des bergers) Soient un ensemble fini et un ensemble. Soit $f:E\to F$ une application, alors est fini et :

$\displaystyle \mathrm{Card}(E)=\sum_{y\in f(E)}\mathrm{Card}(f^{-1}(\{y\}))\;.$

Démonstration : L'application $g:E\to f(E)$ définie par

pour tout

est surjective. Par conséquent,

est fini. Soit $m=\mathrm{Card}(f(E))$ . On fixe donc une bijection

$\displaystyle \Phi:\{1,\dots,m\}\longrightarrow f(E).$

On applique alors la proposition à la famille $(f^{-1}(\{\Phi(i)\}))_{i\in\{1,\dots,m\}}$ de parties de

. $\square$

Proposition 8 Soient et des ensembles finis, alors :

$\mathrm{Card}(E\times F)=\mathrm{Card}(E)\mathrm{Card}(F)$ ;
$\mathrm{Card}(E^F)=\mathrm{Card}(E)^{\mathrm{Card}(F)}$ ;
$\mathrm{Card}({\cal P}(E))=2^{\mathrm{Card}(E)}$ .

Démonstration : Pour a), on considère l'application surjective $f:E\times F\to F$ qui applique

sur

et on applique la proposition précédente, en notant que pour tout

, l'application

$\begin{displaymath}\begin{array}{rcl} E&\longrightarrow&\displaystyle f^{-1}(\{y\})\\ x&\longmapsto&(x,y) \end{array}\end{displaymath}$

est bijective.

Pour b), on raisonne par récurrence sur $\mathrm{Card}(F)$ en considérant pour tout $x\in F$ l'application

$\begin{displaymath}\begin{array}{rcl} E^F&\longrightarrow&E^{F-\{x\}}\\ g&\longmapsto&g_{\mid F-\{x\}}. \end{array}\end{displaymath}$

Pour c), on vérifie que l'application de ${\cal P}(E)$ sur $\{0,1\}^E$ qui envoie une partie sur l'application

$\begin{displaymath}\begin{array}{rcl} \mathbb{I}_A:E&\longrightarrow&\{0,1\}\\ ... ...} 1\text{ si }x\in A,\\ 0\text{ sinon.} \end{cases}\end{array}\end{displaymath}$

est bijective. $\square$