Bijection

En mathématiques, une bijection est une application bijective. Une application est bijective si et seulement si tout élément de son ensemble d'arrivée a un et un seul antécédent, c'est-à-dire est image d'exactement un élément de son ensemble de départ, ou encore si elle est injective et surjective.

On peut remarquer que, dans cette définition, on n'impose pas de condition aux éléments de l'ensemble de départ.

De manière équivalente, une bijection est une injection surjective ou une surjection injective. Les bijections sont aussi appelées correspondances biunivoques^[1].

On peut aussi voir que s'il existe une bijection f d'un ensemble E dans un ensemble F alors il en existe une de F dans E : la bijection réciproque de f, qui à chaque élément de F associe son antécédent par f. On peut alors dire que ces ensembles sont en bijection.

Cantor a le premier démontré que, s'il existe une injection de X vers Y et une injection de Y vers X (pas nécessairement la réciproque de la précédente), alors il existe une bijection entre les deux ensembles (c'est le théorème de Cantor-Bernstein).

Il est facile de montrer que si deux ensembles finis sont en bijection alors ils ont le même nombre d'éléments. L'extension de cette équivalence aux ensembles infinis a mené au concept de cardinal d’un ensemble, et à distinguer différentes tailles d’ensembles infinis, qui sont des classes d'équivalence d'ensembles en bijection (on parle aussi d'équipotence). Ainsi, on peut par exemple montrer que l'ensemble des nombres entiers a la même taille que l'ensemble des rationnels, mais que ce dernier ensemble a une taille inférieure à l'ensemble des réels. En effet, on peut seulement créer des injections mais pas de surjections de dans .

[modifier] Définitions formelles

[modifier] Définition fonctionnelle

Soit f une application de E dans F. f est bijective si et seulement si tout élément de l'ensemble d'arrivée F a exactement un antécédent par f dans l'ensemble de départ E, c'est-à-dire si :

[modifier] Définition relationnelle

Formellement une bijection est une relation binaire Rxy, dont les variables prennent leurs valeurs dans un ensemble X, satisfaisant aux règles suivantes :

• Fonctionnalité :
  • [ ( Rxy et Rxz ) ⇒ y=z ]
  • Soit : il y a au plus une image
• Applicativité :
  • ( Rxy )
  • Soit : il y a au moins une image
• Injectivité :
  • [ ( Rxz et Ryz ) ⇒ x=y ]
  • Soit : il y a au plus une pré-image
• Surjectivité :
  • ( Ryx )
  • Soit : il y a au moins une pré-image

Est à remarquer la symétrie entre d'une part la fonctionnalité et l'injectivité et d'autre part entre l'applicativité et la surjectivité. En réalité ce sont les mêmes notions à l'ordre des arguments près.

Comme une fonction n-aire est un cas particulier de relation n+1-aire fonctionnelle il est usuel de représenter cette relation binaire R par une fonction unaire f en :

• Sous entendant que Rxy satisfait la fonctionnalité
• Et en posant : Rxy si et seulement si f(x) = y.

(Remarque : si on précise que f est une application on suppose et la fonctionnalité et l'applicativité de R.)

En exprimant cela en termes de fonction on a la possibilité, de dire simplement (sans alourdir ces formules ci-dessus de restriction ensemblistes) que dans "Rxy" ou dans "f(x) = y", x appartient à un ensemble A et y appartient à un ensemble B (avec bien sûr possibilité que A=B). En exprimant cela en langage purement relationnel (sans non plus alourdir ces formules par des restrictions ensemblistes) on considère que toutes nos variables prennent valeur dans un ensemble X = A U B ; ce qui est moins souple en utilisation.

En termes fonctionnels, la symétrie déjà exprimée en termes relationnels entre fonctionnalité et injectivité d'une part et entre applicativité et surjectivité d'autre part, donne que :

• S'il y a une bijection entre un ensemble A et un ensemble B, il y a forcément une bijection (mais il peut y en avoir d'autres), dite réciproque, entre B et A.
  • Ce qui en termes relationnels va s'exprimer par si Rxy est une relation bijective Ryx l'est aussi.
  • En termes fonctionnels on doit affirmer l'existence d'une autre fonction g pour dire :

s'il existe une bijection f de A vers B, il existe une bijection réciproque g de B vers A, avec pour exemple g = f ^−1 (c'est-à-dire : f(x) =y si et seulement si g(y) = x )

[modifier] 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).

• 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 desiderata 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.

[modifier] Exemples et contre-exemples

Considérons la fonction définie par f(x) = 2x + 1. Cette fonction est bijective, puisque pour tout nombre réel arbitraire donné y, nous pouvons trouver exactement une solution réelle de l’équation y = 2x + 1 d’inconnue x à savoir x = (y âˆ’ 1)/2.

D’un autre côté, la fonction définie par g(x) = x² n’est pas bijective, pour essentiellement deux raisons différentes. La première est que, nous avons (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 nombre 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 montrer que g n’est pas bijective.

D’autre part, si nous définissons la fonction par la même relation que g, mais avec les ensembles de définition et d’arrivée restreints à , alors la fonction h est bijective.

L’explication est que, pour un nombre réel positif donné y, nous pouvons trouver exactement une solution réelle positive de l’équation y = x² qui est x = √y.

[modifier] Propriétés

• Une fonction est bijective si et seulement s’il existe une fonction g: Y â†’ X telle que soit l’application identité sur X et soit l’application identité sur Y. Les bijections sont précisément les isomorphismes dans la catégorie des ensembles. Dans ce cas, g est déterminée de manière unique par f et nous appelons g la bijection réciproque de f et nous écrivons f ^−1 = g. De plus, g est aussi une bijection, et la réciproque de g est f à nouveau.
• Si f  g est bijective, alors f est surjective et g est injective.
• Si f et g sont toutes deux bijectives, alors f  g est aussi bijective.
• Si X est un ensemble, alors les fonctions bijectives de X sur lui-même, forment avec l’opération de composition des applications (), un groupe, le groupe des permutations de X, qui est noté indifféremment S(X), S_X, σ_X ou σ(X).
• Le nombre de bijections entre deux ensembles de cardinal n est n !
• Lorsque X et Y sont tous les deux égaux à la droite réelle , une fonction bijective a un graphe qui intersecte toute droite horizontale en exactement un point.

[modifier] Notes et références

[modifier] Voir aussi

• Surjection
• Injection
• Théorème de la bijection