Qu’est-ce qu’une bijection, au juste ?

1 – Description informelle de la notion de bijection

C’est décidé, je fais expertiser ma collection de livres anciens !

Pour préparer le terrain, il faut étiqueter chaque bouquin et lui attribuer ainsi un numéro d’ordre.

Comme je dispose justement d’un ensemble d’étiquettes (avec un numéro inscrit sur chacune d’elles), ça va être un jeu d’enfant. Mais attention, cet étiquetage doit être « parfait » au sens suivant :

  • condition 1 : deux livres distincts ne doivent pas correspondre au même numéro
  • condition 2 : chaque numéro doit correspondre à un livre

Dans le jargon des mathématiciens, on exprime cela en disant que :

L’application de l’ensemble X des livres vers l’ensemble Y des numéros qui, à chaque livre associe son numéro, doit être bijective.

Expliquons un peu cette étrange terminologie…

En associant, à chaque livre \ell de ma collection, un numéro n bien déterminé, je définis une application f de X vers Y.

Afin d’expliciter ce lien, on peut noter : n=f\left(\ell\right). On dit que n est l’image de \ell par f ou (de manière équivalente) que \ell est un antécédent de n par f.

En clair, f\left(\ell\right) désigne le numéro inscrit sur l’étiquette portée par le livre \ell.

  • Si la condition 1 ci-dessus est remplie, on dit que l’application f est injective.
  • Si la condition 2 est satisfaite, on dit que f est surjective.

Et si f est à la fois injective et surjective, on dit qu’elle est bijective (ou que c’est une bijection) : cela signifie que chaque numéro possède un unique antécédent par f, autrement dit, chaque numéro identifie un livre et un seul.

Evidemment, ce qui précède peut être généralisé à des ensembles X et Y absolument quelconques (le terme ensemble désigne une collection d’objets, sans plus de précision : c’est un peu naïf mais on s’en contentera).

Etablir une bijection de X vers Y consiste donc à associer, à chaque élément de X, un élément bien déterminé de Y, de telle sorte que :

Tout élément de Y possède un unique antécédent dans X

Il peut être commode de représenter les ensembles par des « patates » et de dessiner une flèche joignant chaque élément de X à son image dans Y.

Le diagramme ci-dessous représente une bijection de l’ensemble

{« chien », « chat », « cheval », « lion », « lapin »}

vers l’ensemble

{« chienne », « chatte », « jument », « lionne », « hase »}

Cette bijection paraît naturelle : à chaque nom de mâle est associé le nom de la femelle correspondante.

Mais on pourrait imaginer autre chose… par exemple :

Moins naturel n’est-ce pas ? Et pourtant : j’ai simplement décidé de respecter l’ordre alphabétique ! Parmi les mots appartenant à l’ensemble de gauche, le premier dans l’ordre alphabétique est « chat »; pour cette raison, je décide de lui associer le mot « chatte » qui est, parmi les mots appartenant à l’ensemble de droite, le premier dans l’ordre alphabétique. De même pour le second (« cheval »), auquel j’associe le second (« chienne »). De même pour le troisième (« chien »), auquel j’associe le troisième (« jument »), etc… Vous avez compris.

Il n’y aucune raison de renoncer aux autres possibilités, sans d’ailleurs chercher à leur attribuer une quelconque logique (mâle → femelle, ordre alphabétique, ou autre…). On peut vérifier qu’il existe en tout 120 bijections entre ces deux ensembles. Pourquoi 120 ? Parce que c’est la « factorielle » de 5, c’est-à-dire le produit des entiers de 1 à 5. On peut en effet montrer, de façon générale, qu’étant donnés deux ensembles comportant chacun n éléments, il existe en tout et pour tout n! bijections de l’un vers l’autre.

Pour en savoir davantage au sujet de la factorielle d’un entier naturel, vous pouvez jeter un coup d’œil à cet autre article de vulgarisation.

Observons ce nouvel exemple :

On a considéré ici un ensemble V de cinq noms de capitales européennes :

V = {« Paris », « Berlin », « Madrid », « Londres », « Rome »}

ainsi qu’un ensemble P de six pays européens :

P = {« France », « Allemagne », « Espagne », « Angleterre », « Italie », « Suède »}

A chaque ville, on a associé le pays dont elle est la capitale. Mais la capitale de la Suède n’apparaît pas dans V, et donc l’élément « Suède » ne possède aucun antécédent. En d’entre termes, notre application n’est pas surjective (et, en particulier, pas bijective).

Voyons autre chose …

• A ma gauche, l’ensemble G=\left\{ 16,\:12,\:27,\:31,\:5\right\}

• A ma droite, l’ensemble D=\left\{ 0,1,2\right\}

Si l’on associe à chaque élément de G le reste de sa division par 3, on obtient ceci :

Ainsi, par exemple :

    \[31=3\times10+1\]

et donc 31 admet 1 pour image. De même pour les autres éléments de G.

Cette fois, tous les éléments de l’ensemble de droite sont atteints, mais certains le sont plusieurs fois ! Il s’agit donc d’une application non injective; en particulier, ce n’est pas une bijection.

Pour une présentation plus formelle de ces notions (applications, injections, surjections et bijections), je vous propose de consulter les deux vidéos suivantes de la chaîne Math-OS :

2 – Composer des bijections

Il existe un moyen naturel permettant, à partir de deux applications quelconques, d’en fabriquer une troisième : c’est ce qu’on appelle la composition. De quoi s’agit-il ?

Imaginons l’ensemble V des habitants d’un village et considérons l’application u qui, à chacune de ces personnes, associe le couple \left(g,f\right)g désigne le nombre de ses garçons et f le nombre de ses filles.

Si par exemple Mr Tartempion appartient à V et s’il a trois garçons et une fille, alors son image par u sera le couple \left(3,1\right).

Considérons ensuite l’application v qui, à tout couple \left(m,n\right) d’entiers naturels associe m+n.

Il est alors possible de composer u par v : cela consiste, pour chaque habitant du village, à lui associer l’image par v de son image par u. Autrement dit, à chaque personne est associé le nombre de ses enfants.

Cette nouvelle application est notée v\circ u (ce qui se lit « v rond u »).

Pour formaliser un peu, disons que si u:X\rightarrow Y et v:Y\rightarrow Z sont deux applications quelconques, alors v\circ u:X\rightarrow Z est définie par :

    \[\forall x\in X,\:\left(v\circ u\right)\left(x\right)=v\left(u\left(x\right)\right)\]

Signalons une propriété à la fois simple et très utile :

Proposition

Si u et v sont des bijections, alors c’est aussi le cas de v\circ u.

3 – Des bijections … d’accord, mais pour quoi faire ?

Vous l’aurez deviné en lisant la section 1 : étant donnés deux ensembles finis X et Y, une condition nécessaire et suffisante pour qu’il soit possible d’établir une bijection (un « fléchage parfait ») de X vers Y est que ces deux ensembles possèdent le même nombre d’éléments (on dit aussi : le même cardinal).

Cette simple observation constitue l’une des principales clefs de la « combinatoire », domaine des mathématiques où l’on tâche de répondre à des questions du genre « combien tel ensemble fini possède-t-il d’éléments ? ». Donnons-en quelques illustrations.

Exemple 1 : nombre de parties d’un ensemble

Etant donné un ensemble de cardinal n, une question naturelle consiste à déterminer le nombre de ses sous-ensembles. Ainsi, l’ensemble X=\left\{ 1,2,3\right\} possède huit sous-ensembles, à savoir :

  • l’ensemble vide, noté \emptyset
  • les singletons \left\{ 1\right\} , \left\{ 2\right\} et \left\{ 3\right\} (ce sont les sous-ensembles de cardinal 1)
  • les paires \left\{ 1,2\right\} , \left\{ 1,3\right\} et \left\{ 2,3\right\} (ce sont les sous-ensembles de cardinal 2)
  • l’ensemble X lui-même

D’une manière générale, si X est de cardinal n alors X possède exactement 2^{n} sous-ensembles. Trois preuves rigoureuses de cette affirmation sont rassemblées dans l’article « Combien un ensemble fini possède-t-il de parties ? ».

Sans détailler ici ces preuves un peu techniques, disons simplement que l’une d’elles consiste à établir une bijection entre l’ensemble des sous-ensembles de X et un autre ensemble dont le cardinal est connu (et égal à 2^{n}).

Exemple 2 : nombre de chemins dans un réseau carré

La figure 1 ci-dessous représente un système de coordonnées et un « chemin » joignant l’origine au point de coordonnées (entières positives) p et q. On s’impose la règle du jeu suivante : en partant de l’origine, on ne peut se déplacer que vers la droite ou vers le haut, d’une unité dans les deux cas.

La figure 2 montre un autre chemin possible :

Le nombre de tels chemins dépend bien évidemment de p et q. On peut le noter N\left(p,q\right) afin de souligner cette dépendance. Mais par quelle formule peut-on calculer N\left(p,q\right) ?

Une manière de répondre consiste à associer à chaque chemin un mot de p+q lettres, écrit dans un alphabet comportant seulement deux symboles : la lettre ‘D’ (pour indiquer un déplacement vers la droite d’une unité) et la lettre ‘H’ (pour indiquer un déplacement vers le haut d’une unité).

Ainsi, le chemin représenté à la figure 1 est associé au mot :

D H D D D H D H D H H D D H D

tandis que celui représenté à la figure 2 est associé au mot :

D H H D H D H D D D H D H D D

La connaissance d’un chemin particulier de \left(0,0\right) vers \left(p,q\right) détermine un mot de longueur p + q, comportant p fois la lettre ‘D’ et q fois la lettre ‘H’.

Réciproquement, chaque mot de ce type détermine un unique chemin : on voit ainsi apparaître une bijection entre l’ensemble des chemins et celui des mots ayant les caractéristiques précitées. Pour connaître le nombre de chemins, il suffit donc de calculer le nombre de mots.

Or il s’agit là d’une opération de routine : on peut imaginer un casier comportant p + q cases et compter le nombre de manières de choisir p cases parmi p + q (celles où l’on placera une lettre ‘D’). Une fois ce choix effectué, les cases restantes seront fatalement occupées par des lettres ‘H’.

Le nombre de façons de choisir k objets parmi n (sans répétition ni considération d’ordre) est classiquement donné par la formule suivante (le membre de gauche se lit k parmi n) :

    \[\binom{n}{k}=\frac{n!}{k!\thinspace\left(n-k\right)!}\]

Par conséquent, le nombre de chemins est :

    \[\fcolorbox{black}{myBlue}{$N\left(p,q\right)=\frac{\left(p+q\right)!}{p!\thinspace q!}$}\]

Par exemple, si p = 3 et q = 2, le nombre de chemins est :

    \[N\left(3,2\right)=\frac{5!}{3!\thinspace2!}=10\]


ce qu’on peut confirmer en énumérant « à la main » les différentes possibilités.

Et si p = 9 et q = 6, ce nombre passe à :

    \[N\left(9,6\right)=\frac{15!}{9!\thinspace6!}=5\thinspace005\]

mais là, on abandonne très vite l’idée de dresser la liste exhaustive des possibilités !…

Au passage, il est intéressant de constater la puissance des méthodes combinatoires : elles donnent accès au calcul du cardinal d’un ensemble, tout en évitant l’énumération explicite de ses éléments (chose impossible à réaliser si ces éléments sont trop nombreux).

Exemple 3 : nombre d’opérations binaires transitives

Il arrive aussi que l’on peine à trouver une bijection entre l’ensemble fini dont on cherche le cardinal et un ensemble de cardinal connu. C’est ainsi que certaines questions de combinatoire, simples en apparence, restent à ce jour non résolues.

Etant donné un ensemble E, on est parfois conduit à munir cet ensemble d’une relation binaire, ce qui veut simplement dire que chaque élément de E est en relation avec zéro, un ou plusieurs autre(s). On peut visualiser une relation binaire en dessinant une flèche de x vers y lorsque x est en relation avec y. Le diagramme ci-dessous représente une relation binaire sur un ensemble de cardinal 11. On y voit notamment que :

  • c est en relation avec d,
  • g est en relation avec lui-même et avec f et avec h,
  • e n’est en relation avec aucun élément.

Une relation binaire est dite transitive si, pour tout triplet \left(x,y,z\right) d’éléments de E, le fait que x soit en relation avec y et que y soit en relation avec z entraîne que x est en relation avec z.

Par exemple, dans l’ensemble A=\left\{ 1,2,3,4,5,6,7,8,9,10,11,12\right\}, on peut définir la relation de divisibilité : étant donnés deux entiers m et n appartenant à A, on dit que « m divise n » lorsqu’il existe un entier naturel k tel que n=km (on dit aussi que « n est multiple de m »). En voici une représentation graphique (afin de ne pas surcharger la figure, les pointes des flèches n’ont pas été représentées, mais il n’y a aucun doute quant à leur orientation) :

Cette relation est transitive : si m divise n et si n divise p, alors il existe des entiers naturels k et \ell tels que n=km et p=\ell n, d’où p=k\ell m et donc m divise p.

Il n’est très pas difficile de dénombrer les relations binaires sur un ensemble E de cardinal n : il en existe 2^{n^{2}} (2 à la puissance n^{2}). Disons, sans rentrer dans les détails, que ceci résulte de l’existence d’une bijection de l’ensemble des relations binaires sur E vers l’ensemble des applications de E^{2} dans \left\{ 0,1\right\}.

On en vient à la question qui tue …

Question : combien de relations binaires transitives peut-on définir sur un ensemble de cardinal n ?

Réponse : un entier T_{n} pour lequel aucune formule sympathique n’a été trouvée à ce jour…

Tout au plus peut-on (avec l’aide d’un ordinateur) calculer la valeur de T_{n} pour de petites valeurs de n, mais guère plus. Voici, compilés dans une table, les 10 premiers termes de cette suite de nombres :

Un bon exercice consiste à dessiner (patates et flèches…) les graphes des 2^{2^{2}}=16 relations binaires possibles sur un ensemble à deux éléments, puis de recenser celles d’entre-elles qui sont transitives (on en trouve 13).

4 – Ensembles infinis en bijection

Nous avons dit, au début de la section précédente, qu’étant donnés deux ensembles finis X et Y, les conditions :

  • il existe une bijection de X vers Y
  • X et Y possèdent le même nombre d’éléments

sont équivalentes. Mais pour des ensembles infinis (c’est-à-dire comportant une infinité d’éléments), l’expression « posséder le même nombre d’éléments » n’a plus grand sens…

D’ailleurs, les choses deviennent dans ce contexte nettement moins intuitive : dans certains cas, on observe l’existence de bijections entre deux ensembles pour lesquels on a bien l’impression que l’un est plus « gros » que l’autre… (par exemple parce qu’il le contient strictement).

Cela provient du fait que notre esprit élabore, en raison d’une terminologie inadaptée, une représentation incorrecte de la situation.

Lorsqu’il existe une bijection entre un ensemble E et l’ensemble \mathbb{N} des entiers naturels, l’ensemble E est dit dénombrable.

Voici deux exemples très classiques, mais qui peuvent paraître contre-intuitifs au premier abord :

Dénombrabilité de \mathbb{Z}

Les entiers naturels 0, 1, 2, etc… forment un ensemble noté \mathbb{N}.

Si l’on rajoute les entiers négatifs -1,-2, etc… on obtient un ensemble « plus gros » noté \mathbb{Z} (initiale du mot allemand « Zahl » qui signifie nombre). Les éléments de \mathbb{Z} sont les « entiers relatifs ».

Intuitivement, on a envie de dire « qu’il y a deux fois plus d’éléments dans \mathbb{Z} que dans \mathbb{N} » ! Nous pourrions donc penser qu’il n’existe aucune bijection de \mathbb{N} vers \mathbb{Z}.

Pourtant, c’est exactement le contraire qui se passe : on peut énumérer les entiers relatifs de manière à ce que chacun d’eux soit pris en compte et que l’on ne prenne jamais deux fois le même.

Pour cela, il est hors de question de commencer par les entiers positifs, en se disant que « dès qu’on en aura fini avec eux », on pourra passer aux négatifs… et pour cause : on n’aura jamais fini !

En revanche, on peut envisager une « énumération alternée » : un coup positif, un coup négatif, et on recommence…

Le diagramme ci-dessous permet de visualiser les premières étapes de cette énumération :

Plus formellement, à chaque entier naturel n, on associe un entier relatif noté f\left(n\right) défini par :

    \[\fcolorbox{black}{myBlue}{$f\left(n\right)=\left\{ \begin{array}{cc}{\displaystyle \frac{n}{2}} & \text{si }n\text{ est pair}\\\\{\displaystyle -\frac{n+1}{2}} & \text{si }n\text{ est impair}\end{array}\right.$}\]

et il est facile de montrer que f est une bijection de \mathbb{N} vers \mathbb{Z}.

Ainsi, l’ensemble \mathbb{Z} des entiers relatifs est donc dénombrable.

Dénombrabilité de \mathbb{N}^2

On peut montrer que l’ensemble noté \mathbb{N}^{2} des couples d’entiers naturels est aussi dénombrable. Une bijection naturelle de \mathbb{N} vers \mathbb{N}^{2} est d’ailleurs suggérée par la figure suivante : on énumère les couples d’entiers naturels en partant de \left(0,0\right) et en parcourant les “ diagonales ” successives, c’est-à-dire les ensembles E_{s}=\left\{ \left(p,q\right)\in\mathbb{N}^{2};\,p+q=s\right\}, pour s=0,1,2,3,\cdots

Les ensembles E_{0}, E_{1}, E_{2}, etc… sont deux à deux disjoints et leur union est \mathbb{N}^{2} tout entier. Mais le point important, c’est que ces ensembles sont tous finis, ce qui garantit que, peu importe le couple \left(p,q\right)\in\mathbb{N}^{2} considéré, on arrivera jusqu’à lui en un nombre fini d’étapes, après avoir parcouru un certain nombre de diagonales. On retrouve là, sous une forme plus élaborée, l’idée qui a permis plus haut de mettre \mathbb{N} et \mathbb{Z} en bijection.

Dans la figure ci-dessous, les points qui composent l’ensemble E_{p+q-1} sont alignés sur le segment rouge :

5 – Une bijection de \mathbb{R} vers \left[0,1\right[

Ce qui suit sera un peu technique et fera intervenir des connaissances généralement enseignées en première année de licence de maths ou de classe préparatoire scientifique.

Pour les besoins d’un explication ultérieure (la non-dénombrabilité de \mathbb{R}, cf. section 6), nous allons établir une bijection de \mathbb{R} vers \left[0,1\right[.

Dans un premier temps, modifions légèrement l’objectif et construisons plutôt une bijection de \mathbb{R} vers \left]0,1\right[. Le simple fait de supprimer l’extrémité gauche de l’intervalle \left[0,1\right[ va en effet nous faciliter les choses…

Considérons l’application

    \[\fcolorbox{black}{myBlue}{$u:\mathbb{R}\rightarrow\left]0,1\right[,\:x\mapsto\frac{1}{1+e^{-x}}$}\]

On observe que u est l’inverse d’une fonction strictement positive et décroissante : u est donc strictement croissante. De plus u continue car c’est l’inverse d’une fonction continue qui ne s’annule pas. Comme de plus les limites de u en -\infty et en +\infty sont respectivement 0 et 1, on peut affirmer que u est une bijection. Voici son graphe :

Afin d’obtenir une bijection de \mathbb{R} vers \left[0,1\right[, il suffit de construire une bijection v de \left]0,1\right[ vers \left[0,1\right[ et de considérer la composée de v par u (cf. section 2).

Posons donc :

    \[\fcolorbox{black}{myBlue}{$v:\left]0,1\right[\rightarrow\left]0,1\right],\thinspace x\mapsto\left\{ \begin{array}{cc}2x & \text{si }x\in\left\{ 2^{-n};\thinspace n\in\mathbb{N}^{\star}\right\} \\\\x & \text{sinon}\end{array}\right.$}\]

Voici le graphe de v (les points représentés par un petit disque rouge font partie du graphe, et ceux représentés par un petit cercle n’en font pas partie) :

Enfin, l’application

    \[\fcolorbox{black}{myBlue}{$w\thinspace:\thinspace\left]0,1\right]\rightarrow\left[0,1\right[,\thinspace x\mapsto1-x$}\]

étant clairement bijective, il suffit de considérer la composée w\circ v\circ u.

Nous tenons notre bijection de \mathbb{R} vers \left[0,1\right[.

6 – La diagonale de Cantor

On doit au mathématicien allemand Georg Cantor (1845 – 1918) le résultat suivant :

Théorème

L’ensemble \mathbb{R} n’est pas dénombrable.

Comme nous disposons (cf. section 5) d’une bijection de \mathbb{R} vers \left[0,1\right[, l’existence d’une bijection de \mathbb{N} vers \mathbb{R} entraînerait (par composition) l’existence d’une bijection de \mathbb{N} vers \left[0,1\right[. Il est donc suffisant de montrer qu’une telle bijection n’existe pas, ce qui se fait bien sûr par l’absurde.

Tout nombre réel x appartenant à l’intervalle \left[0,1\right[ peut s’écrire, de manière unique, sous la forme d’un développement décimal propre (en abrégé : DDP), c’est-à-dire quelque chose du style :

    \[\fcolorbox{black}{myBlue}{$x=0,c_{0}c_{1}c_{2}\cdots c_{n}\cdots$}\]

où les c_{i} sont des entiers compris entre 0 et 9 (les chiffres du DDP de x) avec la contrainte particulière que ce développement ne soit pas exclusivement constitué du chiffre 9 à partir d’un certain rang.

Exemple : développement décimal de 1/2

Le nombre \frac{1}{2} peut s’écrire, au choix :

0,500000… avec une infinité de 0 après le 5, ce que tout le monde note simplement 0,5

➡ ou bien 0,499999… avec une infinité de 9 après le 4

Vous avez un doute ? Vous pensez que le second est légèrement inférieur au premier ?

Ok, détaillons …

De façon incontestable :

    \[0,499999\cdots=0,4+0,099999\cdots\]

or :

    \begin{eqnarray*}0,099999\cdots & = & 0,99999\cdots\times10^{-1}\\& = & 0,11111\cdots\times9\times10^{-1}\\& = & \frac{1}{9}\times9\times10^{-1}\\& = & 10^{-1}\\& = & 0,1\end{eqnarray*}

et donc :

    \[0,499999\cdots=0,4+0,1=0,5\]

Convaincu(e), à présent ? 🙂

De ces deux écritures, on retiendra donc la première, qui constitue le DDP de \frac{1}{2}.

Supposons maintenant l’existence d’une bijection f:\mathbb{N}\rightarrow\left[0,1\right[. Pour chaque entier naturel n, le DDP de f\left(n\right) peut s’écrire :

    \[f\left(n\right)=0,a_{0,n}a_{1,n}a_{2,n}\cdots\]

Il faut bien comprendre cette notation à deux indices : a_{i,n} désigne le i-ème chiffre (la numérotation commençant à i=0) du DDP de f\left(n\right).

C’est là qu’intervient l’idée géniale idée-géniale de Cantor. Il considère un nombre réel \beta\in\left[0,1\right[ dont le DDP est

    \[\beta=0,b_{0}b_{1}b_{2}\cdots\]

avec la condition : pour tout n\in\mathbb{N}, b_{n}\neq a_{n,n}.

On peut imaginer un tableau comportant, ligne par ligne, les DDP de f\left(0\right), f\left(1\right), f\left(2\right), etc…

Ce tableau comporte donc une infinité de lignes et chaque ligne comporte une infinité de colonnes ! L’idée de Cantor consiste donc à choisir une séquence de chiffres b_{0}, b_{1}, b_{2},\cdots de telle sorte que, pour tout n\in\mathbb{N}, le chiffre b_{n} soit distinct du n-ème terme de la diagonale.

Comme b_{0}\neq a_{0,0} et vue l’unicité du DDP, il est certain que \beta\neq f\left(0\right).

De même, comme b_{1}\neq a_{1,1} et vue l’unicité du DDP, il est certain que \beta\neq f\left(1\right).

L’argument se généralise : quel que soit l’entier naturel n, on est certain que \beta\neq f\left(n\right).

Ainsi, \beta ne possède aucun antécédent par f, ce qui est absurde puisque f est supposée bijective !


Vos questions ou remarques seront toujours les bienvenues. Vous pouvez laisser un commentaire ci-dessous ou bien passer par le formulaire de contact.

Partager cet article

Laisser un commentaire