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''&nbsp;+&nbsp;''y'', ''x''&nbsp;&minus;&nbsp;''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> &minus;1</sup> is a function. In that case, ''f''<sup> &minus;1</sup> is also a bijection. The [[composition (mathematics)|composition]] ''g''&nbsp;<small>o</small>&nbsp;''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''&nbsp;<small>o</small>&nbsp;''f'' is (''g''&nbsp;<small>o</small>&nbsp;''f'')<sup>&minus;1</sup> = (''f''<sup> &minus;1</sup>)&nbsp;<small>o</small>&nbsp;(''g''<sup>&minus;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''&nbsp;<small>o</small>&nbsp;''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''&nbsp;<small>o</small>&nbsp;''f'' is the [[identity function]] on ''X'', and ''f''&nbsp;<small>o</small>&nbsp;''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''&nbsp;&minus;&nbsp;1)/2 such that ''f''(''x'') = ''y''. * The [[exponential function]] ''g''&nbsp;:&nbsp;'''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'') = &minus;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''&nbsp;:&nbsp;'''R''' <math>\rightarrow</math> [0,+∞) with ''h(x)'' = ''x''² is not bijective: for instance, ''h''(&minus;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 &minus;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>&minus;1</sup>(''B'')| = |''B''|. *If ''X'' and ''Y'' are [[finite set|finite]] sets with the same cardinality, and ''f'':&nbsp;''X''&nbsp;→&nbsp;''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:双射]]