Bijection
3942
225387202
2008-07-13T12:13:43Z
79.186.239.128
/* Examples and counterexamples */ ooops, error, sorry...
[[Image:Bijection.svg|thumb|200px|A bijective function.]]
In [[mathematics]], a '''bijection''', or a '''bijective function''' is a [[function (mathematics)|function]] ''f'' from a [[set (mathematics)|set]] ''X'' to a set ''Y'' with the property that, for every ''y'' in ''Y'', there is exactly one ''x'' in ''X'' such that <br> ''f''(''x'') = ''y''.
Alternatively, ''f'' is bijective if it is a '''one-to-one correspondence''' between those sets; [[id est|i.e.]], both '''one-to-one''' ([[injective function|injective]]) and '''onto''' ([[surjective function|surjective]]). (''One-to-one function'' means ''one-to-one correspondence'' (i.e., ''bijection'') to some authors, but ''injection'' to others.)
For example, consider the function succ, defined from the set of [[integer]]s <math>\Z</math> to <math>\Z</math>, that to each integer ''x'' associates the integer succ(''x'') = x + 1. For another example, consider the function sumdif that to each pair (''x'',''y'') of real numbers associates the pair sumdif(''x'',''y'') = (''x'' + ''y'', ''x'' − ''y'').
A bijective function from a set to itself is also called a '''[[permutation]]'''.
The set of all bijections from ''X'' to ''Y'' is denoted as ''X''<math>{}\leftrightarrow{}</math>''Y''.
Bijective functions play a fundamental role in many areas of mathematics, for instance in the definition of [[isomorphism]] (and related concepts such as [[homeomorphism]] and [[diffeomorphism]]), [[permutation group]], [[projective map]], and many others.
==Composition and inverses==
A function ''f'' is bijective [[if and only if]] its [[inverse relation]] ''f''<sup> −1</sup> is a function. In that case, ''f''<sup> −1</sup> is also a bijection.
The [[composition (mathematics)|composition]] ''g'' <small>o</small> ''f'' of two bijections ''f''<math>\;:\;</math> ''X''<math>{}\leftrightarrow{}</math>''Y'' and ''g''<math>\;:\;</math> ''Y''<math>{}\leftrightarrow{}</math>''Z'' is a bijection. The inverse of ''g'' <small>o</small> ''f'' is (''g'' <small>o</small> ''f'')<sup>−1</sup> = (''f''<sup> −1</sup>) <small>o</small> (''g''<sup>−1</sup>).
[[Image:Bijective_composition.svg|thumb|300px|A bijection composed of an injection and a surjection.]]
On the other hand, if the composition ''g'' <small>o</small> ''f'' of two functions is bijective, we can only say that ''f'' is injective and ''g'' is [[Surjective function|surjective]].
A relation ''f'' from ''X'' to ''Y'' is a bijective function if and only if there exists another relation ''g'' from ''Y'' to ''X'' such that ''g'' <small>o</small> ''f'' is the [[identity function]] on ''X'', and ''f'' <small>o</small> ''g'' is the [[identity function]] on ''Y''. Consequently, the sets have the same cardinality.
==Bijections and cardinality==
If ''X'' and ''Y'' are [[finite set|finite]] sets, then there exists a bijection between the two sets ''X'' and ''Y'' [[if and only if]] ''X'' and ''Y'' have the same number of elements. Indeed, in [[axiomatic set theory]], this is taken as the very ''definition'' of "same number of elements", and generalising this definition to [[infinite]] sets leads to the concept of [[cardinal number]], a way to distinguish the various sizes of [[infinite sets]].
==Examples and counterexamples==
* For any set ''X'', the [[identity function]] id<sub>''X''</sub> from ''X'' to ''X'', defined by id<sub>''X''</sub>(''x'') = ''x'', is bijective.
* The function ''f'' from the [[real line]] '''R''' to '''R''' defined by ''f''(''x'') = 2''x'' + 1 is bijective, since for each ''y'' there is a unique ''x'' = (''y'' − 1)/2 such that ''f''(''x'') = ''y''.
* The [[exponential function]] ''g'' : '''R''' <math>\rightarrow</math> '''R''', with ''g(x)'' = e<sup>''x''</sup>, is not bijective: for instance, there is no ''x'' in '''R''' such that ''g''(''x'') = −1, showing that ''g'' is not surjective. However if the codomain is changed to be the positive real numbers '''R'''<sup>+</sup> = (0,+∞), then ''g'' becomes bijective; its inverse is the [[natural logarithm]] function ln.
* The function ''h'' : '''R''' <math>\rightarrow</math> [0,+∞) with ''h(x)'' = ''x''² is not bijective: for instance, ''h''(−1) = ''h''(+1) = 1, showing that ''h'' is not injective. However, if the domain too is changed to <nowiki>[0,+∞)</nowiki>, then ''h'' becomes bijective; its inverse is the positive square root function.
* <math>\mathbb{R} \to \mathbb{R} : x \mapsto (x-1)x(x+1) = x^3 - x </math> is not a bijection because −1, 0, and +1 are all in the domain and all map to 0.
* <math>\mathbb{R} \to [-1,1] : x \mapsto \sin(x)</math> is not a bijection because π/3 and 2π/3 are both in the domain and both map to (√3)/2.
== Properties ==
* A function ''f'' from the [[real line]] '''R''' to '''R''' is bijective if and only if its plot is intersected by any horizontal line at exactly one point.
* If ''X'' is a set, then the bijective functions from ''X'' to itself, together with the operation of functional composition (<sup><small>o</small></sup>), form a [[group (algebra)|group]], the [[symmetric group]] of ''X'', which is denoted variously by S(''X''), ''S''<sub>''X''</sub>, or ''X''! (the last reads "''X'' [[factorial]]").
* For a subset ''A'' of the domain with [[cardinality]] |''A''| and subset ''B'' of the codomain with cardinality |''B''|, one has the following equalities:
:|''f''(''A'')| = |''A''| and |''f''<sup>−1</sup>(''B'')| = |''B''|.
*If ''X'' and ''Y'' are [[finite set|finite]] sets with the same cardinality, and ''f'': ''X'' → ''Y'', then the following are equivalent:
:# ''f'' is a bijection.
:# ''f'' is a surjection.
:# ''f'' is an injection.
*At least for a finite set ''S'', there is a bijection between the set of possible [[total ordering]]s of the elements and the set of bijections from ''S'' to ''S''. That is to say, the number of [[permutation]]s (another name for bijections) of elements of ''S'' is the same as the number of total orderings of that set -- namely, ''n!''.
==Bijections and category theory==
Formally, bijections are precisely the [[isomorphism]]s in the [[category theory|category]] [[Category of sets|'''Set''']] of [[set]]s and functions. However, the bijections are not always the isomorphisms. For example, in the category [[Category of topological spaces|'''Top''']] of [[topological space|topological spaces]] and [[continuous functions|continuous]] functions, the isomorphisms must be [[homeomorphism|homeomorphisms]] in addition to being bijections.
==See also ==
*[[injective function]]
*[[symmetric group]]
*[[surjection|surjective function]]
*[[Bijective numeration]]
*[[Bijective proof]]
[[Category:Functions and mappings]]
[[Category:Basic concepts in set theory]]
[[Category:Mathematical relations]]
[[ar:تقابل]]
[[bg:Биекция]]
[[ca:Funció bijectiva]]
[[cs:Bijekce]]
[[da:Bijektiv]]
[[de:Bijektivität]]
[[es:Función biyectiva]]
[[eo:Ensurĵeto]]
[[fr:Bijection]]
[[ko:전단사 함수]]
[[hr:Bijekcija]]
[[io:Bijektio]]
[[is:Gagntæk vörpun]]
[[it:Corrispondenza biunivoca]]
[[he:פונקציה חד-חד-ערכית ועל]]
[[lt:Bijekcija]]
[[lmo:Bigezziú]]
[[hu:Bijekció]]
[[nl:Bijectie]]
[[ja:全単射]]
[[no:Bijeksjon]]
[[nn:Bijeksjon]]
[[oc:Bijeccion]]
[[pl:Funkcja wzajemnie jednoznaczna]]
[[pt:Função bijectiva]]
[[ru:Биекция]]
[[sk:Bijektívne zobrazenie]]
[[sl:Bijektivna preslikava]]
[[sr:Бијекција]]
[[fi:Bijektio]]
[[sv:Bijektiv]]
[[uk:Бієкція]]
[[zh:双射]]