Principes de dénombrement - preuves (A)

Soient $E$ un ensemble fini et $F$ un sous-ensemble de $E$ tel que $|F|=|E|=n$.

Étape 1 : Hypothèse par l'absurde

Supposons, pour arriver à une contradiction, que $F \ne E$. Puisque $F \subseteq E$, cela signifie que $F$ est un sous-ensemble strict de $E$. Il existe donc au moins un élément dans $E$ qui n'est pas dans $F$.

Étape 2 : Utiliser le principe d'addition

L'ensemble $E$ peut être partitionné en deux sous-ensembles disjoints : $F$ et son complémentaire dans $E$, noté $E \setminus F$.

On peut donc écrire $E = F \cup (E \setminus F)$, avec $F \cap (E \setminus F) = \emptyset$.

D'après le principe d'addition pour les ensembles disjoints, le cardinal de $E$ est la somme des cardinaux de ces deux parties :

$|E| = |F| + |E \setminus F|$.

Étape 3 : Arriver à la contradiction

Nous savons par hypothèse que $|E|=|F|$. En substituant dans l'équation précédente, nous obtenons :

$|F| = |F| + |E \setminus F|$.

Cela implique que $|E \setminus F| = 0$.

Le seul ensemble ayant un cardinal de 0 est l'ensemble vide. Donc, $E \setminus F = \emptyset$.

Cela signifie qu'il n'y a aucun élément dans $E$ qui ne soit pas dans $F$. Autrement dit, tout élément de $E$ est aussi un élément de $F$. Combiné avec l'hypothèse $F \subseteq E$, cela nous mène à la conclusion que $F=E$.

Conclusion

Notre supposition initiale que $F \ne E$ conduit à la conclusion que $F=E$, ce qui est une contradiction. Par conséquent, l'hypothèse de départ doit être vraie : si $F \subseteq E$ et $|F|=|E|$, alors $F=E$.

Soit $E$ un ensemble fini de cardinal $n$. Par définition, $\binom{n}{k}$ est le cardinal de l'ensemble $P_k(E)$ de tous les sous-ensembles de $E$ ayant $k$ éléments. De même, $\binom{n}{n-k}$ est le cardinal de l'ensemble $P_{n-k}(E)$ de tous les sous-ensembles de $E$ ayant $n-k$ éléments.

Pour prouver l'égalité, nous allons construire une bijection entre $P_k(E)$ et $P_{n-k}(E)$.

Étape 1 : Définir l'application

Considérons l'application $\phi: P_k(E) \to P_{n-k}(E)$ qui, à chaque sous-ensemble $A \in P_k(E)$, associe son complémentaire dans $E$, noté $\bar{A} = E \setminus A$.

Étape 2 : Vérifier que l'application est bien définie

Si $A \in P_k(E)$, alors par définition, $|A|=k$. Le cardinal de son complémentaire $\bar{A}$ est donné par $|\bar{A}| = |E| - |A| = n - k$.

Donc, $\bar{A}$ est un sous-ensemble de $E$ avec $n-k$ éléments, ce qui signifie que $\bar{A} \in P_{n-k}(E)$. L'application $\phi$ est donc bien définie.

Étape 3 : Prouver que l'application est une bijection

Pour prouver que $\phi$ est une bijection, nous allons montrer qu'elle possède une application réciproque.

Soit l'application $\psi: P_{n-k}(E) \to P_k(E)$ qui, à un ensemble $B \in P_{n-k}(E)$, associe son complémentaire $\bar{B} = E \setminus B$.

Calculons la composition $\psi \circ \phi$. Pour tout $A \in P_k(E)$ :

$\psi(\phi(A)) = \psi(\bar{A}) = \overline{\bar{A}} = A$.

Donc, $\psi \circ \phi$ est l'application identité sur $P_k(E)$.

Calculons la composition $\phi \circ \psi$. Pour tout $B \in P_{n-k}(E)$ :

$\phi(\psi(B)) = \phi(\bar{B}) = \overline{\bar{B}} = B$.

Donc, $\phi \circ \psi$ est l'application identité sur $P_{n-k}(E)$.

Puisque $\phi$ a une application réciproque ($\psi = \phi^{-1}$), $\phi$ est une bijection.

Conclusion

Nous avons établi une bijection entre l'ensemble $P_k(E)$ (de cardinal $\binom{n}{k}$) et l'ensemble $P_{n-k}(E)$ (de cardinal $\binom{n}{n-k}$). D'après le principe de bijection, ces deux ensembles doivent avoir le même cardinal.

Par conséquent, $\binom{n}{k} = \binom{n}{n-k}$.

Étape 1 : Partition de l'union

L'union $A \cup B$ peut être vue comme la réunion de trois ensembles qui sont deux à deux disjoints :

1. Les éléments qui sont dans $A$ mais pas dans $B$ : $A \setminus B$
2. Les éléments qui sont dans $B$ mais pas dans $A$ : $B \setminus A$
3. Les éléments qui sont à la fois dans $A$ et dans $B$ : $A \cap B$

On a donc $A \cup B = (A \setminus B) \cup (B \setminus A) \cup (A \cap B)$.

Comme ces trois ensembles sont disjoints, le principe d'addition pour ensembles disjoints nous donne :

$|A \cup B| = |A \setminus B| + |B \setminus A| + |A \cap B|$. (Équation 1)

Étape 2 : Expression des cardinaux de A et B

L'ensemble $A$ peut être partitionné en $A \setminus B$ et $A \cap B$. Donc :

$|A| = |A \setminus B| + |A \cap B|$, ce qui implique $|A \setminus B| = |A| - |A \cap B|$. (Équation 2)

De même, l'ensemble $B$ peut être partitionné en $B \setminus A$ et $A \cap B$. Donc :

$|B| = |B \setminus A| + |A \cap B|$, ce qui implique $|B \setminus A| = |B| - |A \cap B|$. (Équation 3)

Étape 3 : Substitution et simplification

Substituons les expressions pour $|A \setminus B|$ (Équation 2) et $|B \setminus A|$ (Équation 3) dans l'Équation 1 :

$|A \cup B| = (|A| - |A \cap B|) + (|B| - |A \cap B|) + |A \cap B|$.

En simplifiant l'expression, on obtient :

$|A \cup B| = |A| + |B| - |A \cap B| - |A \cap B| + |A \cap B|$

$|A \cup B| = |A| + |B| - |A \cap B|$.

Conclusion

Nous avons prouvé la formule du principe d'addition (ou formule du crible de Poincaré pour deux ensembles) en décomposant les ensembles en parties disjointes et en utilisant le principe d'addition de base.

Soient $E$ et $F$ deux ensembles finis, avec $|E|=n$ et $|F|=m$. Nous voulons calculer $|E \times F|$.

Étape 1 : Définir les ensembles et l'application

• L'ensemble que nous voulons dénombrer est l'ensemble de départ : $E \times F$.
• Choisissons comme ensemble d'arrivée l'ensemble $F$, dont le cardinal est connu : $|F|=m$.
• Définissons une application $f: E \times F \to F$ par la projection sur la deuxième coordonnée : $f((x, y)) = y$ pour tout couple $(x, y) \in E \times F$.

Étape 2 : Appliquer le principe des bergers

Le principe des bergers stipule que si, pour tout élément $y_0$ de l'ensemble d'arrivée $F$, le nombre d'antécédents $|f^{-1}(\{y_0\})|$ est une constante $p$, alors $|E \times F| = p \cdot |F|$.

Étape 3 : Calculer le nombre d'antécédents

Fixons un élément quelconque $y_0 \in F$. Nous devons déterminer le cardinal de sa préimage, $f^{-1}(\{y_0\})$.

La préimage de $y_0$ est l'ensemble de tous les couples $(x, y) \in E \times F$ tels que $f((x, y)) = y_0$.

Par définition de $f$, cela signifie que $y=y_0$.

Donc, $f^{-1}(\{y_0\}) = \{(x, y_0) \mid x \in E\}$.

Les éléments de cet ensemble sont des couples où la deuxième coordonnée est fixée à $y_0$, et la première coordonnée $x$ peut être n'importe quel élément de $E$. Le nombre de choix pour $x$ est donc $|E|=n$.

Par conséquent, pour tout $y_0 \in F$, le cardinal de sa préimage est constant et vaut $n$.

$|f^{-1}(\{y_0\})| = |E| = n$.

Nous avons donc $p=n$.

Conclusion

Les conditions du principe des bergers sont satisfaites avec $p = |E|$. Nous pouvons donc conclure que :

$|E \times F| = p \cdot |F| = |E| \cdot |F|$.

Soit $E = \{e_1, e_2, \dots, e_n\}$ un ensemble de cardinal $n$. Nous voulons déterminer le cardinal de son ensemble des parties, $P(E)$.

Étape 1 : Modéliser la construction d'un sous-ensemble

Construire un sous-ensemble $A \subseteq E$ revient à effectuer une séquence de $n$ choix indépendants. Pour chaque élément $e_i \in E$ (avec $i$ allant de 1 à $n$), nous devons décider si cet élément appartient ou n'appartient pas au sous-ensemble $A$.

• Pour l'élément $e_1$, il y a 2 possibilités : soit $e_1 \in A$, soit $e_1 \notin A$.
• Pour l'élément $e_2$, il y a 2 possibilités : soit $e_2 \in A$, soit $e_2 \notin A$.
• ...
• Pour l'élément $e_n$, il y a 2 possibilités : soit $e_n \in A$, soit $e_n \notin A$.

Chaque séquence de $n$ décisions de ce type définit un unique sous-ensemble de $E$.

Étape 2 : Appliquer le principe de multiplication

Le nombre total de façons de faire cette séquence de choix est le produit du nombre de possibilités à chaque étape.

Il y a $n$ étapes, et à chaque étape il y a 2 possibilités.

Le nombre total de sous-ensembles est donc :

$\underbrace{2 \times 2 \times \cdots \times 2}_{n \text{ fois}} = 2^n$.

Conclusion

Le nombre total de sous-ensembles possibles d'un ensemble à $n$ éléments est $2^n$. Par conséquent, $|P(E)| = 2^n$.

Soit $A \subseteq \llbracket 2n \rrbracket$ un ensemble de $n+1$ nombres.

Étape 1 : Définir les objets, les tiroirs et l'application

• Les objets sont les $n+1$ nombres de l'ensemble $A$. Nous avons $|A|=n+1$.
• Les tiroirs : Tout entier $x > 0$ peut s'écrire de manière unique sous la forme $x = 2^k \cdot v$, où $k \ge 0$ est un entier et $v$ est un entier impair. Pour un nombre $x \in \llbracket 2n \rrbracket$, sa partie impaire $v$ doit être un nombre impair compris entre 1 et $2n-1$. Les nombres impairs possibles dans $\llbracket 2n \rrbracket$ sont $\{1, 3, 5, \dots, 2n-1\}$. Il y a exactement $n$ tels nombres. Nous définissons donc nos tiroirs comme cet ensemble de $n$ parties impaires.
• L'application $f: A \to \{1, 3, \dots, 2n-1\}$ est la fonction qui associe à chaque nombre $x \in A$ sa partie impaire $v$.

Étape 2 : Appliquer le principe des tiroirs

Nous avons $n+1$ objets (les nombres dans $A$) à ranger dans $n$ tiroirs (les parties impaires possibles).

Comme le nombre d'objets est strictement supérieur au nombre de tiroirs ($n+1 > n$), le principe des tiroirs de Dirichlet garantit qu'il existe au moins un tiroir contenant au moins deux objets.

Cela signifie qu'il existe au moins deux nombres distincts dans $A$, disons $a$ et $b$, qui ont la même partie impaire.

Étape 3 : Montrer la divisibilité

Soient $a, b \in A$ avec $a \ne b$, tels que $f(a) = f(b) = v$ pour un certain $v$ impair.

On peut écrire $a$ et $b$ sous la forme :

$a = 2^{k_1} \cdot v$

$b = 2^{k_2} \cdot v$

pour des entiers $k_1, k_2 \ge 0$.

Puisque $a \ne b$, on doit avoir $k_1 \ne k_2$.

Supposons, sans perte de généralité, que $k_1 < k_2$.

Alors on peut écrire $b$ en fonction de $a$ :

$b = 2^{k_2} \cdot v = 2^{k_2 - k_1} \cdot (2^{k_1} \cdot v) = 2^{k_2 - k_1} \cdot a$.

Comme $k_1 < k_2$, l'exposant $k_2-k_1$ est un entier strictement positif. L'entier $2^{k_2-k_1}$ est donc un entier supérieur ou égal à 2.

L'équation $b = (\text{entier}) \cdot a$ montre que $a$ divise $b$.

Conclusion

Par le principe des tiroirs, nous avons montré que dans tout sous-ensemble de $n+1$ éléments de $\llbracket 2n \rrbracket$, il existe nécessairement deux éléments distincts $a$ et $b$ tels que l'un divise l'autre.

Soit $A = \{a_1, a_2, \dots, a_{n+1}\}$ un ensemble de $n+1$ entiers.

Étape 1 : Définir les objets, les tiroirs et l'application

• Les objets sont les $n+1$ entiers de l'ensemble $A$.
• Les tiroirs : Lorsqu'on effectue la division euclidienne d'un entier par $n$, le reste est toujours un entier compris entre 0 et $n-1$. Il y a donc $n$ restes possibles : $\{0, 1, 2, \dots, n-1\}$. Ces restes seront nos tiroirs.
• L'application $f: A \to \{0, 1, \dots, n-1\}$ est la fonction qui associe à chaque entier $a_i \in A$ son reste dans la division par $n$, c'est-à-dire $a_i \pmod n$.

Étape 2 : Appliquer le principe des tiroirs

Nous avons $n+1$ objets (les entiers) et $n$ tiroirs (les restes possibles).

Puisque le nombre d'objets est strictement supérieur au nombre de tiroirs ($n+1 > n$), le principe des tiroirs garantit qu'au moins un tiroir contient au moins deux objets.

Cela signifie qu'il existe au moins deux entiers distincts dans $A$, disons $a_i$ et $a_j$ (avec $i \ne j$), qui ont le même reste dans la division par $n$.

$f(a_i) = f(a_j) \implies a_i \equiv a_j \pmod n$.

Étape 3 : Conclure sur la différence

Par définition de la congruence modulo $n$, $a_i \equiv a_j \pmod n$ signifie que la différence $a_i - a_j$ est un multiple de $n$.

Conclusion

En utilisant les restes de la division par $n$ comme tiroirs, le principe des tiroirs nous assure que parmi $n+1$ entiers, il y en a forcément deux qui ont le même reste. Leur différence est par conséquent un multiple de $n$.

Pour prouver que $\mathbb{Z}$ est dénombrable, nous devons trouver une bijection $f: \mathbb{N} \to \mathbb{Z}$.

Étape 1 : Construire l'application

Nous pouvons lister les éléments de $\mathbb{Z}$ de la manière suivante : $0, 1, -1, 2, -2, 3, -3, \dots$. Cette liste semble couvrir tous les entiers relatifs sans répétition. Formalisons cela avec une application.

Nous pouvons associer les entiers naturels pairs aux entiers positifs ou nuls, et les entiers naturels impairs aux entiers négatifs.

Définissons $f: \mathbb{N} \to \mathbb{Z}$ par :

$f(n) = \begin{cases} n/2 & \text{si } n \text{ est pair} \\ -(n+1)/2 & \text{si } n \text{ est impair} \end{cases}$

Vérifions les premières valeurs :

• $f(0) = 0/2 = 0$
• $f(1) = -(1+1)/2 = -1$
• $f(2) = 2/2 = 1$
• $f(3) = -(3+1)/2 = -2$
• $f(4) = 4/2 = 2$

Étape 2 : Prouver que l'application est injective

Soient $n_1, n_2 \in \mathbb{N}$ tels que $f(n_1)=f(n_2)$.

• Si $f(n_1)=f(n_2) \ge 0$, alors $n_1$ et $n_2$ doivent être pairs. On a $n_1/2 = n_2/2$, ce qui implique $n_1=n_2$.
• Si $f(n_1)=f(n_2) < 0$, alors $n_1$ et $n_2$ doivent être impairs. On a $-(n_1+1)/2 = -(n_2+1)/2$, ce qui implique $n_1+1=n_2+1$ et donc $n_1=n_2$.
• Un cas où $f(n_1) \ge 0$ et $f(n_2) < 0$ ne peut pas se produire.

Dans tous les cas, $f(n_1)=f(n_2)$ implique $n_1=n_2$. L'application est donc injective.

Étape 3 : Prouver que l'application est surjective

Soit $k \in \mathbb{Z}$ un entier relatif quelconque. Nous devons trouver un antécédent $n \in \mathbb{N}$ tel que $f(n)=k$.

• Si $k \ge 0$, cherchons un $n$ pair tel que $n/2 = k$. Le nombre $n=2k$ convient. Comme $k \ge 0$, $n$ est bien un entier naturel pair.
• Si $k < 0$, cherchons un $n$ impair tel que $-(n+1)/2 = k$. Cela donne $n+1 = -2k$, soit $n=-2k-1$. Comme $k < 0$ (donc $k \le -1$), $-2k \ge 2$, et donc $n = -2k-1 \ge 1$. $n$ est bien un entier naturel. De plus, $n=-2k-1$ est impair.

Chaque élément de $\mathbb{Z}$ a un antécédent dans $\mathbb{N}$. L'application est donc surjective.

Conclusion

L'application $f$ est à la fois injective et surjective, c'est donc une bijection. Puisqu'il existe une bijection entre $\mathbb{N}$ et $\mathbb{Z}$, l'ensemble $\mathbb{Z}$ est, par définition, dénombrable.

Pour prouver que $\mathbb{N} \times \mathbb{N}$ est dénombrable, nous devons construire une bijection entre $\mathbb{N}$ et $\mathbb{N} \times \mathbb{N}$.

Étape 1 : Stratégie d'énumération

On peut visualiser les éléments de $\mathbb{N} \times \mathbb{N}$ comme les points à coordonnées entières dans le premier quadrant d'un plan. Pour les énumérer, on peut les parcourir diagonale par diagonale.

• Diagonale 0 : $x+y=0 \implies (0,0)$
• Diagonale 1 : $x+y=1 \implies (0,1), (1,0)$
• Diagonale 2 : $x+y=2 \implies (0,2), (1,1), (2,0)$
• Diagonale $k$ : $x+y=k \implies (0,k), (1,k-1), \dots, (k,0)$

Cette méthode permet de lister tous les couples de manière systématique.

Étape 2 : Construction de la bijection

Définissons une application $g: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$. Pour un couple $(x,y)$, le nombre d'éléments dans toutes les diagonales précédant celle de $(x,y)$ (la diagonale $k=x+y$) est la somme des longueurs des diagonales de 0 à $x+y-1$. La diagonale $i$ a $i+1$ points.

Le nombre de points avant la diagonale de $(x,y)$ est $\sum_{i=0}^{x+y-1} (i+1) = \sum_{j=1}^{x+y} j = \frac{(x+y)(x+y+1)}{2}$.

Dans la diagonale $x+y$, les points sont listés par ordre croissant de la première coordonnée : $(0, x+y), (1, x+y-1), \dots, (x,y), \dots$. Le couple $(x,y)$ est le $(x+1)$-ème élément de sa diagonale (si on commence à compter à 1), ou l'élément d'indice $x$ (si on commence à 0).

L'application de "dénombrement" $g$ est donc :

$g(x, y) = \frac{(x+y)(x+y+1)}{2} + x$.

Vérifions les premières valeurs :

• $g(0,0) = \frac{0(1)}{2} + 0 = 0$
• $g(0,1) = \frac{1(2)}{2} + 0 = 1$
• $g(1,0) = \frac{1(2)}{2} + 1 = 2$
• $g(0,2) = \frac{2(3)}{2} + 0 = 3$
• $g(1,1) = \frac{2(3)}{2} + 1 = 4$
• $g(2,0) = \frac{2(3)}{2} + 2 = 5$

Étape 3 : Justification de la bijectivité

Cette fonction $g$ est connue sous le nom de fonction de couplage de Cantor. Il est possible de démontrer formellement qu'elle est injective et surjective, mais la construction par énumération systématique sans omission ni répétition est une justification suffisante au niveau "régulier". Chaque couple $(x,y)$ se voit assigner un unique numéro, et chaque numéro correspond à un unique couple.

Conclusion

Puisqu'il existe une bijection entre $\mathbb{N} \times \mathbb{N}$ et $\mathbb{N}$, l'ensemble $\mathbb{N} \times \mathbb{N}$ est dénombrable.

Étape 1 : Hypothèse par l'absurde

Supposons, pour arriver à une contradiction, qu'il existe une application surjective $f: E \to P(E)$.

Cela signifie que pour chaque sous-ensemble de $E$, il existe au moins un élément de $E$ qui lui est associé par $f$.

Étape 2 : Construction de l'ensemble diagonal

Considérons le sous-ensemble suivant de $E$, que nous nommerons $A$ :

$A = \{x \in E \mid x \notin f(x)\}$.

Cet ensemble $A$ est bien un sous-ensemble de $E$, donc $A \in P(E)$.

Étape 3 : Utiliser l'hypothèse de surjectivité

Puisque nous avons supposé que $f$ est surjective et que $A \in P(E)$, il doit exister un élément $y \in E$ qui est un antécédent de $A$. C'est-à-dire, il existe $y \in E$ tel que $f(y) = A$.

Étape 4 : Chercher la contradiction

Maintenant, demandons-nous si cet élément $y$ appartient à l'ensemble $A$. Il n'y a que deux possibilités, et nous allons montrer que les deux mènent à une contradiction.

• Cas 1 : Supposons que $y \in A$.

  Par la définition de l'ensemble $A$, si $y \in A$, alors $y$ doit satisfaire la condition $y \notin f(y)$.

  Mais nous savons que $f(y) = A$. Donc, la condition devient $y \notin A$.

  Ceci est une contradiction : nous avons supposé $y \in A$ et nous avons déduit $y \notin A$.

• Cas 2 : Supposons que $y \notin A$.

  Par la définition de l'ensemble $A$, si $y \notin A$, cela signifie que $y$ ne satisfait pas la condition pour être dans $A$. La condition étant $x \notin f(x)$, sa négation est $y \in f(y)$.

  Mais nous savons que $f(y) = A$. Donc, la condition devient $y \in A$.

  Ceci est aussi une contradiction : nous avons supposé $y \notin A$ et nous avons déduit $y \in A$.

Conclusion

Les deux cas possibles mènent à une contradiction. Par conséquent, notre hypothèse initiale selon laquelle il existe un élément $y$ tel que $f(y)=A$ doit être fausse.

Cela signifie que l'ensemble $A$ n'a pas d'antécédent par $f$. L'application $f$ n'est donc pas surjective.

Ceci contredit notre hypothèse de départ. Il est donc impossible qu'une telle surjection existe.

Comme une bijection est un cas particulier de surjection, il n'existe pas non plus de bijection de $E$ vers $P(E)$.

Soient $E$ et $F$ deux ensembles finis tels que $|E|=|F|=n$, et $f: E \to F$ une application.

Partie 1 : Prouver que si $f$ est injective, alors $f$ est surjective.

Étape 1 : Supposons que $f$ est injective.

Par définition, cela signifie que pour tous $x_1, x_2 \in E$, si $x_1 \ne x_2$, alors $f(x_1) \ne f(x_2)$.

Autrement dit, chaque élément de $E$ est envoyé sur une image distincte dans $F$.

Étape 2 : Considérons l'ensemble image de $f$, noté $f(E) = \{f(x) \mid x \in E\}$.

Puisque $f$ est injective, les $n$ éléments de $E$ sont envoyés sur $n$ images distinctes. Le cardinal de l'ensemble image est donc égal au cardinal de l'ensemble de départ : $|f(E)| = |E| = n$.

Étape 3 : Nous avons $f(E)$ qui est un sous-ensemble de $F$ ($f(E) \subseteq F$). Nous savons que $|f(E)| = n$ et que $|F|=n$.

Donc, nous avons un sous-ensemble $f(E)$ de $F$ qui a le même cardinal que $F$. D'après la propriété fondamentale des ensembles finis (prouvée plus haut), cela implique que $f(E) = F$.

Étape 4 : Par définition, $f$ est surjective si son ensemble image est égal à son ensemble d'arrivée, c'est-à-dire si $f(E)=F$.

Nous avons donc prouvé que $f$ est surjective.

Partie 2 : Prouver que si $f$ est surjective, alors $f$ est injective.

Étape 1 : Supposons que $f$ est surjective.

Par définition, cela signifie que pour tout $y \in F$, il existe au moins un $x \in E$ tel que $f(x)=y$.

Étape 2 : Raisonnons par l'absurde. Supposons que $f$ n'est pas injective.

Si $f$ n'est pas injective, cela signifie qu'il existe au moins deux éléments distincts dans $E$, disons $x_1$ et $x_2$, qui ont la même image : $f(x_1) = f(x_2)$.

Étape 3 : Considérons les $n$ éléments de $E$ comme des "objets" et les $n$ éléments de $F$ comme des "tiroirs". L'application $f$ range les objets dans les tiroirs.

Puisque $x_1$ et $x_2$ sont envoyés sur la même image, au moins un élément de $F$ reçoit au moins deux éléments de $E$.

Le nombre total d'éléments dans l'ensemble image $f(E)$ est donc au plus $n-1$, car deux éléments de $E$ "partagent" une image.

Formellement, $|f(E)| \le |E| - 1 = n-1$.

Étape 4 : Or, si $|f(E)| \le n-1$ et que $|F|=n$, alors $f(E)$ est un sous-ensemble strict de $F$. Cela signifie que $f(E) \ne F$.

Ceci contredit notre hypothèse de départ selon laquelle $f$ est surjective (qui implique $f(E)=F$).

Conclusion

Notre supposition que $f$ n'est pas injective mène à une contradiction. Par conséquent, si $f$ est surjective, elle doit être injective.

Nous avons montré les deux implications : (injective $\implies$ surjective) et (surjective $\implies$ injective). Par conséquent, pour des ensembles finis de même cardinal, l'injectivité est équivalente à la surjectivité.