Bijection

En mathématiques, une bijection ou application bijective (parfois appelée correspondance biunivoque^[1]) est une application qui est à la fois injective et surjective, autrement dit pour laquelle tout élément de son ensemble d'arrivée possède un et un seul antécédent^{[Note 1]}.

Une propriété des bijections est que s'il existe une bijection f d'un ensemble E dans un ensemble F alors il existe une bijection réciproque de F dans E qui à chaque élément de F associe son antécédent par f. Les deux ensembles sont dits en bijection, ou équipotents.

Cantor a le premier démontré que s'il existe une injection de E vers F et une injection de F vers E (non nécessairement surjectives), alors E et F sont équipotents (c'est le théorème de Cantor-Bernstein).

Si deux ensembles finis sont équipotents alors ils ont le même nombre d'éléments. L'extension de cette équivalence aux ensembles infinis a mené à la notion de cardinal d'un ensemble, et à distinguer différentes tailles d'ensembles infinis, qui sont des classes d'équipotence. Ainsi, on peut par exemple montrer que l'ensemble des entiers naturels est de même taille que l'ensemble des rationnels, mais de taille strictement inférieure à l'ensemble des réels. En effet, de ${\displaystyle \mathbb {N} }$ dans ${\displaystyle \mathbb {R} }$, il existe des injections mais pas de surjection.

Une application ${\displaystyle f:E\to F}$ est bijective si tout élément de l'ensemble d'arrivée ${\displaystyle F}$ a exactement un antécédent (dans ${\displaystyle E}$) par ${\displaystyle f}$, ce qui s'écrit formellement :

${\displaystyle \forall y\in F,\ \exists !\ x\in E,\quad f(x)=y}$

ou, ce qui est équivalent, s'il existe une application ${\displaystyle g:F\to E}$ qui, composée à gauche ou à droite par ${\displaystyle f}$, donne l'application identité :

${\displaystyle g\circ f=\operatorname {id} _{E}}$ et ${\displaystyle f\circ g=\operatorname {id} _{F}}$,

c'est-à-dire:

${\displaystyle \forall x\in E,\ \forall y\in F,\quad f(x)=y\Longleftrightarrow g(y)=x}$.

Une telle application ${\displaystyle g}$ est alors déterminée de manière unique par ${\displaystyle f}$. On l'appelle la bijection réciproque de ${\displaystyle f}$ et on la note ${\displaystyle f^{-1}}$. C'est aussi une bijection, et sa réciproque est ${\displaystyle f}$.

Une bijection de ${\displaystyle E}$ dans ${\displaystyle F}$ est une relation binaire ${\displaystyle R}$ de ${\displaystyle E}$ dans ${\displaystyle F}$ qui est une application et dont la relation réciproque ${\displaystyle R^{-1}}$ est aussi une application. De façon plus détaillée, ${\displaystyle R}$ doit posséder les quatre propriétés suivantes :

• Fonctionnalité : tout élément de ${\displaystyle E}$ a au plus une image par ${\displaystyle R}$, c'est-à-dire

${\displaystyle \forall x\in E,\ \forall y,y'\in F,\quad [(xRy{\text{ et }}xRy')\Rightarrow y=y']}$ ;

• Applicativité : tout élément de ${\displaystyle E}$ a au moins une image par ${\displaystyle R}$, c'est-à-dire

${\displaystyle \forall x\in E,\ \exists y\in F,\quad xRy}$ ;

• Injectivité : tout élément de ${\displaystyle F}$ a au plus un antécédent par ${\displaystyle R}$, c'est-à-dire

${\displaystyle \forall x,x'\in E,\ \forall y\in F,\quad [(xRy{\text{ et }}x'Ry)\Rightarrow x=x']}$

• Surjectivité : tout élément de ${\displaystyle F}$ a au moins un antécédent par ${\displaystyle R}$, c'est-à-dire

${\displaystyle \forall y\in F,\ \exists x\in E,\quad xRy}$.

L'injectivité de ${\displaystyle R}$ équivaut à la fonctionnalité de ${\displaystyle R^{-1}}$ et la surjectivité de ${\displaystyle R}$ équivaut à l'applicativité de ${\displaystyle R^{-1}}$.

Il est usuel de représenter une relation binaire fonctionnelle ${\displaystyle R}$ par une fonction ${\displaystyle f}$ en posant

${\displaystyle \forall x\in E,\ \forall y\in F,\quad f(x)=y\Longleftrightarrow xRy}$.

Si l'on précise que ${\displaystyle f}$ est une application, on suppose que ${\displaystyle R}$ est fonctionnelle et applicative (voir Application_(mathématiques)#Fonction_et_application pour les différences entre application et fonction, qui peuvent varier selon les auteurs).

La symétrie entre fonctionnalité et injectivité d'une part, et entre applicativité et surjectivité d'autre part, donne que si ${\displaystyle R}$ est une relation bijective alors ${\displaystyle R^{-1}}$ l'est aussi.

Prenons le cas d'une station de vacances où un groupe de touristes doit être logé dans un hôtel. Chaque façon de répartir ces touristes dans les chambres de l'hôtel peut être représentée par une application de l'ensemble X des touristes vers l'ensemble Y des chambres (à chaque touriste est associée une chambre).

• L'hôtelier souhaite que l'application soit surjective, c'est-à-dire que chaque chambre soit occupée. Cela n'est possible que s'il y a au moins autant de touristes que de chambres.
• Les touristes souhaitent que l'application soit injective, c'est-à-dire que chacun d'entre eux ait une chambre individuelle. Cela n'est possible que si le nombre de touristes ne dépasse pas le nombre de chambres.
• Ces souhaits sont incompatibles si le nombre de touristes est différent du nombre de chambres. Dans le cas contraire, il sera possible de répartir les touristes de telle sorte qu'il y en ait un seul par chambre, et que toutes les chambres soient occupées : on dira alors que l'application est à la fois injective et surjective ; elle est bijective.

• La fonction affine ${\displaystyle f:\mathbb {R} \to \mathbb {R} }$ définie par f(x) = 2x + 1 est bijective, puisque pour tout réel y, il existe exactement une solution réelle de l’équation y = 2x + 1 d'inconnue x, à savoir : x = (y − 1)/2.
• La fonction carré ${\displaystyle g:\mathbb {R} \to \mathbb {R} }$ définie par g(x) = x² n’est pas bijective, pour deux raisons. La première est que l'on a (par exemple) g(1) = 1 = g(−1), et donc g n’est pas injective ; la seconde est qu'il n'y a (par exemple) aucun réel x tel que x² = −1, et donc g n’est pas surjective non plus. L'une ou l'autre de ces constatations est suffisante pour affirmer que g n'est pas bijective.
  En revanche, l'application ${\displaystyle \mathbb {R} _{+}\to \mathbb {R} _{+},\,x\mapsto x^{2}}$ est bijective. L'explication est que pour tout réel positif y, il existe exactement une solution réelle positive de l’équation y = x², qui est x = √y. La fonction racine carrée est donc la bijection réciproque de la fonction carré sur ces ensembles.
• De même, la fonction sinus, vue comme une application de ${\displaystyle \mathbb {R} }$ dans ${\displaystyle \mathbb {R} }$, n'est ni injective, ni surjective, donc pas bijective ;
  • sa corestriction ${\displaystyle \sin :\mathbb {R} \to [-1,1]}$ est surjective mais pas injective (par exemple, ${\displaystyle 0}$ et ${\displaystyle \pi }$ ont la même image) donc pas bijective ;
  • sa restriction ${\displaystyle \sin :[-{\pi /2},{\pi /2}]\to \mathbb {R} }$ est injective mais pas surjective (par exemple, ${\displaystyle 2}$ n'est l'image d'aucune valeur) donc pas bijective ;
  • sa restriction-corestriction ${\displaystyle \sin :[-{\pi /2},{\pi /2}]\to [-1,1]}$ est bijective (comme aussi une infinité d'autres de ses restrictions-corestrictions) ;
  • sa bijection réciproque est alors arcsin : ${\displaystyle [-1,1]\to [-{\pi /2},{\pi /2}]}$ ;
  • cependant, la fonction arc sinus prenant les mêmes valeurs, mais vue comme une application de ${\displaystyle [-1,1]}$ dans ${\displaystyle \mathbb {R} }$, est injective mais pas surjective (par exemple, ${\displaystyle \pi }$ n'est l'image d'aucune valeur) donc pas bijective.
• La fonction sigmoïde ${\displaystyle f:\mathbb {R} \to ]0,1[}$ définie par ${\displaystyle f(x)={\frac {1}{1+e^{-x}}}}$ est bijective et est souvent utilisée en informatique, notamment dans les réseaux de neurones.

• Les bijections sont les isomorphismes dans la catégorie des ensembles.
• Soient ${\displaystyle f:E\to F}$ et ${\displaystyle h:F\to G}$.
  • Si ${\displaystyle f}$ et ${\displaystyle h}$ sont bijectives alors ${\displaystyle h\circ f}$ est bijective et ${\displaystyle (h\circ f)^{-1}=f^{-1}\circ h^{-1}}$.
  • Si ${\displaystyle h\circ f}$ est bijective alors ${\displaystyle f}$ est injective et ${\displaystyle h}$ est surjective.
• Pour tout ensemble E, les bijections de E sur lui-même s'appellent les permutations de E. Elles forment, avec l’opération ∘ de composition des applications, un groupe appelé le groupe symétrique de E et noté S(E) ou ${\displaystyle {\mathfrak {S}}(E)}$.
• Le nombre de bijections entre deux ensembles finis de même cardinal n est n!.
• Une application de ℝ dans ℝ est bijective si et seulement si son graphe intersecte toute droite horizontale en exactement un point.
• Pour qu'une application d'un ensemble fini dans lui-même soit bijective, il suffit qu'elle soit injective ou surjective (elle est alors les deux). On peut le voir comme une application du principe des tiroirs.

  NB : il peut exister une bijection entre deux ensembles infinis dont l'un est strictement inclus dans l'autre. On en trouve de nombreux exemples dans le cas dénombrable.

Théorème de la bijection

• Portail des mathématiques