Injective function 45196 225165914 2008-07-12T06:31:46Z 81.98.251.134 /* Definition */ {{redirect|One-to-one|other uses|One-to-one (disambiguation)}} {{redirect|Injective|injective modules|Injective module}} [[Image:Injection.svg|thumb|200px|An injective function (injection)]] [[Image:Bijection.svg|thumb|200px|Another injective function (this one is a [[bijection]])]] [[Image:Surjection.svg|thumb|200px|A '''non'''-injective function (this one happens to be a [[surjection]])]] In [[mathematics]], an '''injective function''' is a [[function (mathematics)|function]] which associates distinct arguments with distinct values. An injective function is called an '''injection''', and is also said to be an '''information-preserving''' or '''one-to-one function''' (the latter is not to be confused with ''one-to-one correspondence'', i.e. a [[bijective function]]). A function ''f'' that is not injective is sometimes called many-to-one. (However, this terminology is also sometimes used to mean "single-valued", i.e. each argument is mapped to at most one value.) == Definition == Let ''f'' be a [[Function (mathematics)|function]] whose [[Domain (mathematics)|domain]] is a set ''A''. The function ''f'' is '''injective''' if, for all ''a'' and ''b'' in ''A'', if ''f''(''a'')=''f''(''b'') then ''a'' = ''b''. == Examples and counter-examples == *For any set ''X'', the [[identity function]] on ''X'' is injective. *The function ''f''&nbsp;:&nbsp;'''R'''&nbsp;→&nbsp;'''R''' defined by ''f''(''x'')&nbsp;= 2''x''&nbsp;+&nbsp;1 is injective. *The function ''g''&nbsp;:&nbsp;'''R'''&nbsp;→&nbsp;'''R''' defined by ''g''(''x'')&nbsp;= ''x''<sup>2</sup> is ''not'' injective, because (for example) ''g''(1)&nbsp;= 1&nbsp;= ''g''(−1). However, if ''g'' is redefined so that its domain is the non-negative real numbers <nowiki>[0,+∞)</nowiki>, then ''g'' is injective. *The [[exponential function]] <math>\exp : \mathbb{R} \to \mathbb{R} : x \mapsto \mathrm{e}^x</math> is injective (but not [[surjective]] as no value maps to a negative number). *The [[natural logarithm]] function <math>\ln : (0,+\infty) \to \mathbb{R} : x \mapsto \ln{x}</math> is injective. *The function ''g''&nbsp;:&nbsp;'''R'''&nbsp;→&nbsp;'''R''' defined by <math>g(x) = x^n - x </math> is not injective, since, for example, ''g''(0) = ''g''(1). More generally, when ''X'' and ''Y'' are both the [[real line]] '''R''', then an injective function ''f''&nbsp;:&nbsp;'''R'''&nbsp;→&nbsp;'''R''' is one whose graph is never intersected by any horizontal line more than once. == Injections can be undone == Functions with [[Inverse_function#Left_and_right_inverses|left inverses]] are always injections. That is, given ''f''&nbsp;:&nbsp;''X''&nbsp;→&nbsp;''Y'', if there is a function ''g''&nbsp;:&nbsp;''Y''&nbsp;→&nbsp;''X'' such that, for every <math>x \in X</math> :<math>g(f(x)) = x \,</math> (''f'' can be undone by ''g'') then ''f'' is injective. In this case, ''f'' is called a [[Retract (category theory)|section]] of ''g'' and ''g'' is called a [[Retract (category theory)|retraction]] of ''f''. Conversely, every injection ''f'' with non-empty domain has a left inverse ''g'' (in conventional mathematics<ref>This principle is valid in conventional mathematics, but may fail in [[constructive mathematics]]. For instance, a left inverse of the inclusion {0,1} → '''R''' of the two-element set in the reals violates [[indecomposability]] by giving a [[Retract (category theory)|retraction]] of the real line to the set {0,1}.</ref>). Note that ''g'' may not be a complete [[inverse function|inverse]] of ''f'' because the composition in the other order, ''f''&nbsp;<small>o</small>&nbsp;''g'', may not be the identity on ''Y''. In other words, a function that can be undone or "''reversed''", such as ''f'', is not necessarily [[inverse function|invertible]] ([[bijective]]). Injections are "''reversible''" but not always invertible. Although it is impossible to reverse a non-injective (and therefore information-losing) function, you can at least obtain a "quasi-inverse" of it, that is a [[multivalued function|multiple-valued]] function. == Injections may be made invertible == In fact, to turn an injective function ''f''&nbsp;:&nbsp;''X''&nbsp;→&nbsp;''Y'' into a [[bijective function|bijective]] (hence [[Inverse function|invertible]]) function, it suffices to replace its codomain ''Y'' by its actual range ''J'' = ''f''(''X''). That is, let ''g''&nbsp;:&nbsp;''X''&nbsp;→&nbsp;''J'' such that ''g''(''x'') = ''f''(''x'') for all ''x'' in ''X''; then ''g'' is bijective. Indeed, ''f'' can be factored as incl<sub>''J'',''Y''</sub><small>o</small>''g'', where incl<sub>''J'',''Y''</sub>is the [[inclusion function]] from ''J'' into ''Y''. == Other properties == * If ''f'' and ''g'' are both injective, then ''f''&nbsp;<small>o</small>&nbsp;''g'' is injective. [[Image:Injective_composition2.svg|thumb|300px|The composition of two injective functions is injective.]] * If ''g''&nbsp;<small>o</small>&nbsp;''f'' is injective, then ''f'' is injective (but ''g'' need not be). * ''f''&nbsp;:&nbsp;''X''&nbsp;→&nbsp;''Y'' is injective if and only if, given any functions ''g'', ''h''&nbsp;:&nbsp;''W''&nbsp;→&nbsp;''X'', whenever ''f''&nbsp;<small>o</small>&nbsp;''g''&nbsp;= ''f''&nbsp;<small>o</small>&nbsp;''h'', then ''g''&nbsp;=&nbsp;''h''. In other words, injective functions are precisely the [[monomorphism]]s in the [[category theory|category]] [[Category of sets|'''Set''']] of sets. * If ''f''&nbsp;:&nbsp;''X''&nbsp;→&nbsp;''Y'' is injective and ''A'' is a [[subset]] of ''X'', then ''f''<sup>&nbsp;−1</sup>(''f''(''A''))&nbsp;=&nbsp;''A''. Thus, ''A'' can be recovered from its [[image (function)|image]] ''f''(''A''). * If ''f''&nbsp;:&nbsp;''X''&nbsp;→&nbsp;''Y'' is injective and ''A'' and ''B'' are both subsets of ''X'', then ''f''(''A''&nbsp;∩&nbsp;''B'')&nbsp;= ''f''(''A'')&nbsp;∩&nbsp;''f''(''B''). * Every function ''h''&nbsp;:&nbsp;''W''&nbsp;→&nbsp;''Y'' can be decomposed as ''h''&nbsp;= ''f''&nbsp;<small>o</small>&nbsp;''g'' for a suitable injection ''f'' and surjection ''g''. This decomposition is unique [[up to isomorphism]], and ''f'' may be thought of as the [[inclusion function]] of the range ''h''(''W'') of ''h'' as a subset of the codomain ''Y'' of ''h''. * If ''f''&nbsp;:&nbsp;''X''&nbsp;→&nbsp;''Y'' is an injective function, then ''Y'' has at least as many elements as ''X'', in the sense of [[cardinal number]]s. * If both ''X'' and ''Y'' are [[finite set|finite]] with the same number of elements, then ''f''&nbsp;:&nbsp;''X''&nbsp;→&nbsp;''Y'' is injective if and only if ''f'' is [[surjective]]. *Every [[embedding]] is injective. == See also == {{Wiktionarypar|injective}} *[[surjection|surjective function]] *[[injective module]] *[[monomorphism]] *[[Horizontal line test]] *[[Injective metric space]] == Notes == <references/> == References == * {{Citation | last1=Bartle | first1=Robert G. | title=The Elements of Real Analysis | publisher=[[John Wiley & Sons]] | location=New York | edition=2nd | isbn=978-0-471-05464-1 | year=1976}}, p. 17 ''ff''. * {{Citation | last1=Halmos | first1=Paul R. | author1-link=Paul R. Halmos | title=[[Naive Set Theory (book)|Naive Set Theory]] | isbn=978-0-387-90092-6 | year=1974}}, p. 38 ''ff''. [[Category:Functions and mappings]] [[Category:Basic concepts in set theory]] [[bg:Инекция]] [[ca:Funció injectiva]] [[cs:Prosté zobrazení]] [[da:Injektiv]] [[de:Injektivität]] [[es:Función inyectiva]] [[eo:Enĵeto]] [[fr:Injection (mathématiques)]] [[ko:단사 함수]] [[hr:Injektivna funkcija]] [[io:Injektio]] [[it:Funzione iniettiva]] [[he:פונקציה חד-חד-ערכית]] [[la:Functio iniectiva]] [[lt:Injekcija (matematika)]] [[hu:Injektív leképezés]] [[nl:Injectie (wiskunde)]] [[ja:単射]] [[oc:Injeccion (matematicas)]] [[pl:Funkcja różnowartościowa]] [[pt:Função injectiva]] [[ro:Funcţie injectivă]] [[ru:Инъекция (математика)]] [[sk:Prosté zobrazenie]] [[sl:Injektivna preslikava]] [[sr:Инјективно пресликавање]] [[fi:Injektio]] [[sv:Injektiv]] [[zh:单射]]