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 $E$ et $F$ des ensembles. On dit que $E$ et $F$ ont le même cardinal s'il existe une bijection de $E$ sur $F$.

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

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

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

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

alors $m\leqslant n$.

Démonstration : On raisonne par récurrence sur $m$. Si $m=0$, la conclusion est vérifiée. Supposons le résultat vrai pour $m-1$. Soit

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

une application injective. Comme $f$ est injective, on a

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

On peut donc définir

$$\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}$$

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 $m$ et $n$ des entiers. S'il existe une bijection de $\{1,\dots,m\}$ sur $\{1,\dots,n\}$, alors $m=n$.

Démonstration : Notons $f$ une telle bijection. Alors $f$ et $f^{-1}$ sont injectives et on applique la proposition précédente.$\square$

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

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

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

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

En effet l'application

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

est bijective.

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

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

Démonstration : Soit $n$ le cardinal de $E$. Il existe donc une bijection $\Phi$ de $E$ sur $\{1,\dots,n\}$. L'application obtenue par restriction à $X$ :

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

est également bijective. Quitte à remplacer $X$ par $\Phi(X)$, il suffit de traiter le cas où $E=\{1,\dots,n\}$.

On raisonne alors par récurrence sur le cardinal de $E$. Si $n=0$, alors $E=X=\emptyset$ et le résultat est valide. Supposons le résultat démontré pour les ensembles de cardinal $n-1$, et montrons le pour $E=\{1,\dots,n\}$. Si $X=E$, 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 $X$ est fini de cardinal inférieur ou égal à $n-1$. Mais dans ce cas, il existe $i\in\{1,\dots,n\}$ tel que $i\not\in X$. On considère alors l'application

$$\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}$$

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

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

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

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

Si $F$ est fini et si $f$ est injective, alors

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

Si $E$ est fini et si $f$ est surjective, alors

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

Démonstration : Si $f$ est injective, on considère l'application

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

$g$ est bijective. Donc $E$ et $f(E)$ ont même cardinal. Donc $\mathrm{Card}(E)=\mathrm{Card}(f(E))\leqslant \mathrm{Card}(F)$. L'application $f$ est bijective si et seulement si $f(E)=F$ ce qui est équivalent à $\mathrm{Card}(E)=\mathrm{Card}(F)$ par ce qui précède.

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

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

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

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

La composée $f\circ g$ est l'application identique de $F$, donc $g$ est injective. On applique alors le cas injectif à $g$.$\square$

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

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

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

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

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

Démonstration : Par la proposition 5, on sait que $B$ et $A\setminus B$ sont finis. Notons $p$ le cardinal de $B$ et $q$ le cardinal de $A\setminus B$. Il existe donc des bijections

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

et

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

L'application

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

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

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

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

Alors

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

Démonstration : On raisonne par récurrence sur $r$.

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

$$\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

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

ce qui prouve le résultat pour $r$.$\square$

Définition 7   Soit $E$ 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

$$\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 $E$ un ensemble fini et $F$ un ensemble. Soit $f:E\to F$ une application, alors $f(E)$ est fini et :

$$\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 $g(x)=f(x)$ pour tout $x$ de $E$ est surjective. Par conséquent, $f(E)$ est fini. Soit $m=\mathrm{Card}(f(E))$. On fixe donc une bijection

$$\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 $E$.$\square$

Proposition 8   Soient $E$ et $F$ des ensembles finis, alors :

1. $\mathrm{Card}(E\times F)=\mathrm{Card}(E)\mathrm{Card}(F)$;
2. $\mathrm{Card}(E^F)=\mathrm{Card}(E)^{\mathrm{Card}(F)}$;
3. $\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 $(x,y)$ sur $y$ et on applique la proposition précédente, en notant que pour tout $y$ de $F$, l'application

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

est bijective.

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

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

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

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

est bijective.$\square$