Bijection

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

En mathématiques, une bijection ou application bijective (parfois appelée correspondance biunivoque) 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. En effet, si elle est en même temps injective et surjective, elle impose non seulement au maximum un antécédent par f, mais elle impose aussi au minimum un antécédent par f, 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 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 ℕ dans ℝ, il existe des injections mais pas de surjection.

Définitions formelles

Définition fonctionnelle

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

∀y∈F, ∃! x∈E,f(x)=y

ou, ce qui est équivalent, s'il existe une application g:F→E qui, composée à gauche ou à droite par f, donne l'application identité :

g∘f=idE et f∘g=idF,

c'est-à-dire:

∀x∈E, ∀y∈F,f(x)=y⟺g(y)=x.

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

Définition relationnelle

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

  • Fonctionnalité : tout élément de E a au plus une image par R, c'est-à-dire
∀x∈E, ∀y,y′∈F,[(xRy et xRy′)⇒y=y′] ;
  • Applicativité : tout élément de E a au moins une image par R, c'est-à-dire
∀x∈E, ∃y∈F,xRy ;
  • Injectivité : tout élément de F a au plus un antécédent par R, c'est-à-dire
∀x,x′∈E, ∀y∈F,[(xRy et x′Ry)⇒x=x′]
  • Surjectivité : tout élément de F a au moins un antécédent par R, c'est-à-dire
∀y∈F, ∃x∈E,xRy.

L'injectivité de R équivaut à la fonctionnalité de R−1 et la surjectivité de R équivaut à l'applicativité de R−1.

Il est usuel de représenter une relation binaire fonctionnelle R par une fonction f en posant

∀x∈E, ∀y∈F,f(x)=y⟺xRy.

Si l'on précise que f est une application, on suppose que 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 R est une relation bijective alors R−1 l'est aussi.

Exemple concret

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

Exemples et contre-exemples

Propriétés

Articles connexes

Théorème de la bijection