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$.
.png)
.png)
