Movatterモバイル変換

Bijection

Un article de Wikipédia, l'encyclopédie libre.

L'ensemble de départX (dit la source) et l'ensemble d'arrivéeY. Nous pouvons ici mieux remarquer les relations« un-à-un » entre les deux ensembles.

Enmathématiques, unebijection ouapplication bijective (parfois appeléecorrespondance biunivoque^[1]) est uneapplication qui est à la foisinjective etsurjective, autrement dit pour laquelle tout élément de sonensemble d'arrivée possède un et un seulantécédent^{[Note 1]}. En effet, si elle est en même temps injective et surjective, elle impose non seulementau maximum un antécédent parf, mais elle impose aussiau minimum un antécédent parf, restreignant par conséquent à un seul antécédent pour chaque élément de l'ensemble d'arrivée.

Une propriété des bijections est que s'il existe une bijectionf d'unensembleE dans un ensembleF alors il existe unebijection réciproque deF dansE qui à chaque élément deF associe son antécédent parf. Les deux ensembles sont dits en bijection, ouéquipotents.

Cantor a le premier démontré que s'il existe une injection deE versF et une injection deF versE (non nécessairement surjectives), alorsE etF sont équipotents (c'est lethéorème de Cantor-Bernstein).

Si deuxensembles finis sontéquipotents alors ils ont le même nombre d'éléments. L'extension de cette équivalence auxensemblesinfinis a mené à la notion decardinal 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 desentiers naturels est de même taille que l'ensemble desrationnels, mais de taille strictement inférieure à l'ensemble desréels. En effet, de $\mathbb {N}$ dans $\mathbb {R} ,$ il existe des injections mais pas de surjection.

Définitions formelles

[modifier |modifier le code]

Définition fonctionnelle

[modifier |modifier le code]

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

\forall y\in F,\ \exists !\ x\in E,\quad f(x)=y

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

g\circ f=\operatorname {id} _{E}

et

f\circ g=\operatorname {id} _{F}

,

c'est-à-dire:

\forall x\in E,\ \forall y\in F,\quad f(x)=y\Longleftrightarrow g(y)=x

.

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

Définition relationnelle

[modifier |modifier le code]

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

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

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

;

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

\forall x\in E,\ \exists y\in F,\quad xRy

;

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

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

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

\forall y\in F,\ \exists x\in E,\quad xRy

.

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

Il est usuel de représenter unerelation binairefonctionnelle $R {\displaystyle R}$ par unefonction $f {\displaystyle f}$ en posant

\forall x\in E,\ \forall y\in F,\quad f(x)=y\Longleftrightarrow xRy

.

Si l'on précise que $f {\displaystyle f}$ est uneapplication, on suppose que $R {\displaystyle R}$ est fonctionnelleet applicative (voirApplication_(mathématiques)#Fonction_et_application pour les différences entreapplication etfonction, 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 $R {\displaystyle R}$ est une relation bijective alors $R^{-1}$ l'est aussi.

Exemple concret

[modifier |modifier le code]

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 {\displaystyle X}$ des touristes vers l'ensemble $Y {\displaystyle Y}$ des chambres (à chaque touriste est associée une chambre).

L'hôtelier souhaite que l'application soitsurjective, c'est-à-dire quechaque 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 soitinjective, c'est-à-dire quechacun 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 estbijective.