Ensembles finis. Bijections entre deux ensembles finis. Notion de cardinal.

Commençons par montrer quelques propriétés sur les ensembles finis. Ces propriétés sont intuitives, et découlent facilement de la propriété 0 ci-dessous. Néanmoins, la démonstration de celle-ci n'a rien de trivial. Pour le plaisir, je vous recommande de la démontrer vous-même avant de lire la démonstration.

Dans cet article, on notera 

$$E_n=\left\{ 1,2, \ldots , n\right\}$$

Propriété 0. Soient $n,m$ deux entiers naturels non-nuls. 

S'il existe une injection $E_n \longrightarrow E_m$, alors $n\leq m$.

Démonstration. 

Par récurrence sur $n$. 

On considère pour tout entier naturel $n$ la propriété 

$$\mathcal P_n : \ \ \ \ \exists \phi: P_n\longrightarrow P_m\ \textrm{injective} \Rightarrow n\leq m$$

(1) Initialisation. Si $n=1$, alors $\phi(1)\in E_m$, donc $1\leq \phi(1)\leq m$ et $1\leq m$.

(2) Hérédité. Supposons que $\mathcal P_k$ soit vraie pour un certain $k$. 

Montrons $\mathcal P_{k+1}$ : supposons que $\psi$ est une injection de $E_{k+1}$ dans $E_p$ et montrons que $k+1\leq p$. 

$\phi=\psi|_{E_k}$ est une injection de $E_k$ dans $E_p$. (En particulier $k\leq p$) 

Deux cas (a) et (b) sont possibles : 

(a) Si pour tout $x\in E_k$, $\phi(x)\in E_{p-1}$, alors $\phi$ est une injection de $E_k$ dans $E_{p-1}$ et par hypothèse de récurrence $\mathcal P_k$, on a $k\leq p-1$, d'où $k+1\leq p$.

(b) Sinon cela signifie qu'il existe un entier $j$, $1\leq j \leq k$ tel que $\psi(j)\not \in E_{p-1}$, donc $\psi(j)=p$. 

On note $i=\psi(k+1)$. Alors $1\leq i \leq p-1<p$.

Soit $\sigma$ la fonction $E_{k+1}\longrightarrow E_p$  définie par 

• $\sigma(j)=i$
• $\sigma(k+1)=p$
• $\sigma(x)=\psi(x)$ si $x\neq j$ et $x\neq k+1$.

Alors $\sigma$ est injective. En effet  

• $i\neq p$,  

• pour tout $x\neq j$ et $x\neq k+1$, $\sigma(x)=\psi(x)\neq i =\psi(k+1)$  par injectivité de $\psi$, 
• pour tout $x\neq j$ et $x\neq k+1$, $\sigma(x)=\psi(x)\neq \psi(j)$  par injectivité de $\psi$ 
• pour tous $x,y$ distincts de $j$  et de $k+1$, $\sigma(x)=\psi(x)\neq \psi(y)=\sigma(y)$  par injectivité de $\psi$

Ainsi il n'existe pas deux éléments de $E_{k+1}$ ayant la même image par $\sigma$. 

$\sigma$ ainsi construite est injective et $\sigma(k+1)=p$. D'après le cas (a), on en déduit que $k+1\leq p$.

Nous avons donc montré l'implication $\mathcal{P}_k \Rightarrow \mathcal P_{k+1}$.

(3) Conclusion. Par initialisation et récurrence, pour tout entier strictement positif $n$, l'existence d'une injection $E_n \longrightarrow E_m$ immlique $n\leq m$.

Propriété 1. S'il existe une bijection $E_n\longrightarrow E_m$, alors $n=m$.

Démonstration. Notons $\phi$ cette bijection. Alors $\phi$ est une injection, donc $n\leq m$.

De même $m\leq n$ car $\phi^{-1}$ est une injection de $E_m \longrightarrow E_n$.

 

Propriété 2. S'il existe deux bijections $E\longrightarrow E_n$ et $E\longrightarrow E_m$, alors $n=m$.

Démonstration. Soient $\phi$ et $\psi$ les bijections respectives $E\longrightarrow E_n$ et $E\longrightarrow E_m$. 

Alors $\phi \circ \psi^{-1}$ est une bijection $E_m \longrightarrow E_n$.

On dit qu'un ensemble $E$ est fini, s'il existe un entier $n$ et une bijection $E \longrightarrow E_n$. 

D'après la propriété 2, si un ensemble est fini, alors l'entier $n$ tel qu'il existe une bijection $E \longrightarrow E_n$ est unique. 

On appelle $n$ le cardinal de $E$. On le note $|E|$ ou $\sharp E$ ou $\mathrm{card}(E)$.

$n$ est le nombre d'éléments de $E$. 

Propriété 3. Soient $E$ et $F$ sont deux ensembles finis. 

$E$ et $F$ ont le même cardinal si et seulement s'il existe une bijection $E\longrightarrow F$. 

Démonstration. 

$(\Rightarrow)$ Supposons que $|E|=|F|$, et notons $n$ ce cardinal commun. Alors il existe deux bijections $\varphi:E\longrightarrow E_n$ et $\psi:F\longrightarrow E_n$. Alors $\psi^{-1}\circ \varphi : E\longrightarrow F$ est une bijection.   

$(\Leftarrow)$ Réciproquement, supposons qu'il existe une bijection $\alpha : E \longrightarrow F$. Soit $\varphi:E\longrightarrow E_n$ une bijection, $n$ étant le cardinal de $E$. Alors $\varphi\circ \alpha^{-1}$ est une bijection $F\longrightarrow E_n$, et donc d'après la propriété 2, $F$ aussi a pour cardinal $n$.