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'' : '''R''' → '''R''' defined by ''f''(''x'') = 2''x'' + 1 is injective.
*The function ''g'' : '''R''' → '''R''' defined by ''g''(''x'') = ''x''<sup>2</sup> is ''not'' injective, because (for example) ''g''(1) = 1 = ''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'' : '''R''' → '''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'' : '''R''' → '''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'' : ''X'' → ''Y'', if there is a function ''g'' : ''Y'' → ''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'' <small>o</small> ''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'' : ''X'' → ''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'' : ''X'' → ''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'' <small>o</small> ''g'' is injective.
[[Image:Injective_composition2.svg|thumb|300px|The composition of two injective functions is injective.]]
* If ''g'' <small>o</small> ''f'' is injective, then ''f'' is injective (but ''g'' need not be).
* ''f'' : ''X'' → ''Y'' is injective if and only if, given any functions ''g'', ''h'' : ''W'' → ''X'', whenever ''f'' <small>o</small> ''g'' = ''f'' <small>o</small> ''h'', then ''g'' = ''h''. In other words, injective functions are precisely the [[monomorphism]]s in the [[category theory|category]] [[Category of sets|'''Set''']] of sets.
* If ''f'' : ''X'' → ''Y'' is injective and ''A'' is a [[subset]] of ''X'', then ''f''<sup> −1</sup>(''f''(''A'')) = ''A''. Thus, ''A'' can be recovered from its [[image (function)|image]] ''f''(''A'').
* If ''f'' : ''X'' → ''Y'' is injective and ''A'' and ''B'' are both subsets of ''X'', then ''f''(''A'' ∩ ''B'') = ''f''(''A'') ∩ ''f''(''B'').
* Every function ''h'' : ''W'' → ''Y'' can be decomposed as ''h'' = ''f'' <small>o</small> ''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'' : ''X'' → ''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'' : ''X'' → ''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:单射]]