Bijection

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 \N dans \R.

Sommaire

Définitions formelles

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 :

\forall\ y \in F ,\ \exist!\ x \in E /\ f ( x ) = y \,

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é :
    • \forall x, \forall y, \forall z [ ( Rxy et Rxz ) ⇒ y=z ]
    • Soit : il y a au plus une image
  • Applicativité :
    • \forall x, \exists y ( Rxy )
    • Soit : il y a au moins une image
  • Injectivité :
    • \forall x, \forall y, \forall z [ ( Rxz et Ryz ) ⇒ x=y ]
    • Soit : il y a au plus une pré-image
  • Surjectivité :
    • \forall x, \exists y ( 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 )

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 des touristes, X, vers l'ensemble des chambres, Y, (à 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.

Surjection Injection Bijection-fr.svg

Exemples et contre-exemples

Considérons la fonction f:\mathbb R \rightarrow \mathbb R 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 g:\mathbb R \rightarrow \mathbb R définie par g(x) = x2 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 x2 = −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 h:\mathbb R_+ \rightarrow \mathbb R_+ par la même relation que g, mais avec les ensembles de définition et d’arrivée restreints à \mathbb R_+, 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 = x2 qui est x = √y.

Propriétés

  • Une fonction f:X\rightarrow Y\, est bijective si et seulement s’il existe une fonction gY → X telle que g\circ f soit l’application identité sur X et f\circ g 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 \circ g est bijective, alors f est surjective et g est injective.
  • Si f et g sont toutes deux bijectives, alors f \circ 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 (\circ), un groupe, le groupe des permutations de X, qui est noté indifféremment S(X), SX, σ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 \mathbb R, une fonction bijective f:\mathbb R\rightarrow \mathbb R a un graphe qui intersecte toute droite horizontale en exactement un point.

Notes et références

  1. Dans l'édition de 1970 de la Théorie des Ensembles de Bourbaki, ch. II, § 3, n° 7, après la déf. 10, p. II. 17, on lit : « Au lieu de dire que f est injective, on dit aussi que f est biunivoque. (…) Si f [application de A dans B] est bijective, on dit aussi que f met A et B en correspondance biunivoque. » Mais dans le « fascicule de résultats », à la fin du même volume, p. E.R.9, "biunivoque" n'est employé que dans le second sens.

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Bijection de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • bijection — [ biʒɛksjɔ̃ ] n. f. • mil. XXe; de bi et (in)jection ♦ Math. Application qui, à tout élément de l ensemble de départ, associe un et un seul élément de l ensemble d arrivée. Bijection d un ensemble sur un autre (⇒ équipotent) . ● bijection nom… …   Encyclopédie Universelle

  • Bijection — A bijective function, f:X→Y, where set X is {1, 2, 3, 4} and set Y is {A, B, C, D}. For example, f(1) = D. A bijection (or bijective function or one to one correspondence) is a function giving an exact pairing of the elements of two… …   Wikipedia

  • Bijection de Joyal — La bijection de Joyal consiste à déplier , à l aide de la correspondance fondamentale de Foata, la partie cyclique d une application de dans pour en faire un arbre de Cayley. La bijection de Joyal permet de donner une démonstration élégante de la …   Wikipédia en Français

  • Bijection réciproque — Pour les articles homonymes, voir Réciproque (homonymie). En mathématiques, la bijection réciproque d une bijection f est l application qui associe à chaque élément de l ensemble d arrivée son unique antécédent par f. On l appelle parfois, par… …   Wikipédia en Français

  • Bijection, injection and surjection — In mathematics, injections, surjections and bijections are classes of functions distinguished by the manner in which arguments (input expressions from the domain) and images (output expressions from the codomain) are related or mapped to each… …   Wikipedia

  • bijection — noun Etymology: 1bi + jection (as in injection) Date: 1963 a mathematical function that is a one to one and onto mapping compare injection, surjection • bijective adjective …   New Collegiate Dictionary

  • bijection — /buy jek sheuhn/, n. Math. a map or function that is one to one and onto. [1965 70; BI 1 + jection, as in PROJECTION] * * * …   Universalium

  • bijection — noun /baɪ.dʒɛk.ʃən/ A function which is both a surjection and an injection. Syn: one to one correspondence …   Wiktionary

  • bijection — See function, logical …   Philosophy dictionary

  • bijection — n. function that is both an injection and surjection, function that is both a one to one function and an onto function (Mathematics) …   English contemporary dictionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”