Editing Injective function

{{Short description|Function that preserves distinctness}}
{{Redirect|Injective|other uses|Injective module|and|Injective object}}
{{Functions}}

In [[mathematics]], an '''injective function''' (also known as '''injection''', or '''one-to-one function'''<ref>Sometimes ''one-one function'', in Indian mathematical education. {{Cite web |title=Chapter 1:Relations and functions |url=https://ncert.nic.in/ncerts/l/lemh101.pdf |via=NCERT |url-status=live |archive-url=https://web.archive.org/web/20231226194119/https://ncert.nic.in/ncerts/l/lemh101.pdf |archive-date= Dec 26, 2023 }}</ref> )  is a [[function (mathematics)|function]] {{math|''f''}} that maps [[Distinct (mathematics)|distinct]] elements of its domain to distinct elements of its codomain; that is, {{math|1=''x''<sub>1</sub> ≠ ''x''<sub>2</sub>}} implies {{math|''f''(''x''<sub>1</sub>) {{≠}} ''f''(''x''<sub>2</sub>)}} (equivalently by [[contraposition]], {{math|''f''(''x''<sub>1</sub>) {{=}} ''f''(''x''<sub>2</sub>)}} implies {{math|1=''x''<sub>1</sub> = ''x''<sub>2</sub>}}). In other words, every element of the function's [[codomain]] is the [[Image (mathematics)|image]] of {{em|at most}} one element of its [[Domain of a function|domain]].<ref name=":0">{{Cite web|url=https://www.mathsisfun.com/sets/injective-surjective-bijective.html|title=Injective, Surjective and Bijective|website=Math is Fun |access-date=2019-12-07}}</ref> The term {{em|one-to-one function}} must not be confused with {{em|one-to-one correspondence}} that refers to [[bijective function]]s, which are functions such that each element in the codomain is an image of exactly one element in the domain. 

A [[homomorphism]] between [[algebraic structure]]s is a function that is compatible with the operations of the structures. For all common algebraic structures, and, in particular for [[vector space]]s, an {{em|injective homomorphism}} is also called a {{em|[[monomorphism]]}}. However, in the more general context of [[category theory]], the definition of a monomorphism differs from that of an injective homomorphism.<ref>{{Cite web|url=https://stacks.math.columbia.edu/tag/00V5|title=Section 7.3 (00V5): Injective and surjective maps of presheaves |website=The Stacks project |access-date=2019-12-07}}</ref> This is thus a theorem that they are equivalent for algebraic structures; see {{slink|Homomorphism|Monomorphism}} for more details.

A function <math>f</math> that is not injective is sometimes called many-to-one.<ref name=":0" />

== Definition ==
[[file:Injection.svg|thumb|An injective function, which is not also [[Surjective function|surjective]].]]
{{Further|topic=notation|Function (mathematics)#Notation}}
Let <math>f</math> be a function whose domain is a set <math>X.</math> The function <math>f</math> is said to be '''injective''' provided that for all <math>a</math> and <math>b</math> in <math>X,</math> if <math>f(a) = f(b),</math> then <math>a = b</math>; that is, <math>f(a) = f(b)</math> implies <math>a=b.</math> Equivalently, if <math>a \neq b,</math> then <math>f(a) \neq f(b)</math> in the [[Contraposition|contrapositive]] statement.

Symbolically,<math display="block">\forall a,b \in X, \;\; f(a)=f(b) \Rightarrow a=b,</math>
which is logically equivalent to the [[Contraposition|contrapositive]],<ref>{{Cite web|url=http://www.math.umaine.edu/~farlow/sec42.pdf|title=Section 4.2 Injections, Surjections, and Bijections |last=Farlow|first=S. J.|author-link= Stanley Farlow |website=Mathematics & Statistics - University of Maine |access-date=2019-12-06 |url-status=dead |archive-url= https://web.archive.org/web/20191207035302/http://www.math.umaine.edu/~farlow/sec42.pdf |archive-date= Dec 7, 2019 }}</ref><math display="block">\forall a, b \in X, \;\; a \neq b \Rightarrow f(a) \neq f(b).</math>An injective function (or, more generally, a monomorphism) is often denoted by using the specialized arrows ↣ or ↪ (for example, <math>f:A\rightarrowtail B</math> or  <math>f:A\hookrightarrow B</math>), although some authors specifically reserve ↪ for an [[inclusion map]].<ref>{{Cite web |title=What are usual notations for surjective, injective and bijective functions? |url=https://math.stackexchange.com/questions/46678/what-are-usual-notations-for-surjective-injective-and-bijective-functions |access-date=2024-11-24 |website=Mathematics Stack Exchange |language=en}}</ref> 

== Examples ==
''For visual examples, readers are directed to the [[#Gallery|gallery section.]]''
* For any set <math>X</math> and any subset <math>S \subseteq X,</math> the [[inclusion map]] <math>S \to X</math> (which sends any element <math>s \in S</math> to itself) is injective. In particular, the [[identity function]] <math>X \to X</math> is always injective (and in fact bijective).
* If the domain of a function is  the [[empty set]], then the function is the [[empty function]], which is injective.
* If the domain of a function has one element (that is, it is a [[singleton set]]), then the function is always injective.
* The function <math>f : \R \to \R</math> defined by <math>f(x) = 2 x + 1</math> is injective.
* The function <math>g : \R \to \R</math> defined by <math>g(x) = x^2</math> is {{em|not}} injective, because (for example) <math>g(1) = 1 = g(-1).</math> However, if <math>g</math> is redefined so that its domain is the non-negative real numbers <nowiki>[0,+∞)</nowiki>, then <math>g</math> is injective.
* The [[exponential function]] <math>\exp : \R \to \R</math> defined by <math>\exp(x) = e^x</math> is injective (but not [[Surjective function|surjective]], as no real value maps to a negative number).
* The [[natural logarithm]] function <math>\ln : (0, \infty) \to \R</math> defined by <math>x \mapsto \ln x</math> is injective.
* The function <math>g : \R \to \R</math> defined by <math>g(x) = x^n - x</math> is not injective, since, for example, <math>g(0) = g(1) = 0.</math>

More generally, when <math>X</math> and <math>Y</math> are both the [[real line]] <math>\R,</math> then an injective function <math>f : \R \to \R</math> is one whose graph is never intersected by any horizontal line more than once. This principle is referred to as the {{em|[[horizontal line test]]}}.<ref name=":0" />

== Injections can be undone ==

Functions with [[Inverse function#Left and right inverses|left inverses]] are always injections. That is, given <math>f : X \to Y,</math> if there is a function <math>g : Y \to X</math> such that for every <math>x \in X</math>, <math>g(f(x)) = x</math>, then <math>f</math> is injective. In this case, <math>g</math> is called a [[Retract (category theory)|retraction]] of <math>f.</math> Conversely, <math>f</math> is called a [[Retract (category theory)|section]] of <math>g.</math>

Conversely, every injection <math>f</math> with a non-empty domain has a left inverse <math>g</math>. It can be defined by choosing an element <math>a</math> in the domain of <math>f</math> and setting <math>g(y)</math> to the unique element of the pre-image <math>f^{-1}[y]</math> (if it is non-empty) or to <math>a</math> (otherwise).{{refn|Unlike the corresponding statement that every surjective function has a right inverse, this does not require the [[axiom of choice]], as the existence of <math>a</math> is implied by the non-emptiness of the domain. However, this statement may fail in less conventional mathematics such as [[constructive mathematics]]. In constructive mathematics, the inclusion <math>\{ 0, 1 \} \to \R</math> of the two-element set in the reals cannot have a left inverse, as it would violate [[Indecomposability (constructive mathematics)|indecomposability]], by giving a [[Retract (category theory)|retraction]] of the real line to the set {0,1}.}}

The left inverse <math>g</math> is not necessarily an [[Inverse function|inverse]] of <math>f,</math> because the composition in the other order, <math>f \circ g,</math> may differ from the identity on <math>Y.</math> In other words, an injective function can be  "reversed" by a left inverse, but is not necessarily [[Inverse function|invertible]], which requires that the function is bijective.

== Injections may be made invertible ==

In fact, to turn an injective function <math>f : X \to Y</math> into a bijective (hence invertible) function, it suffices to replace its codomain <math>Y</math> by its actual image <math>J = f(X).</math> That is, let <math>g : X \to J</math> such that <math>g(x) = f(x)</math> for all <math>x \in X</math>; then <math>g</math> is bijective. Indeed, <math>f</math> can be factored as <math>\operatorname{In}_{J,Y} \circ g,</math> where <math>\operatorname{In}_{J,Y}</math> is the [[inclusion function]] from <math>J</math> into <math>Y.</math>

More generally, injective [[partial function]]s are called [[partial bijection]]s.

== Other properties ==
{{See also|List of set identities and relations#Functions and sets}}
[[Image:Injective composition2.svg|thumb|300px|The composition of two injective functions is injective.]]
* If <math>f</math> and <math>g</math> are both injective then <math>f \circ g</math> is injective.
* If <math>g \circ f</math> is injective, then <math>f</math> is injective (but <math>g</math> need not be).
* <math>f : X \to Y</math> is injective if and only if, given any functions <math>g,</math> <math>h : W \to X</math> whenever <math>f \circ g = f \circ h,</math> then <math>g = h.</math> In other words, injective functions are precisely the [[monomorphism]]s in the [[category theory|category]] '''[[Category of sets|Set]]''' of sets.
* If <math>f : X \to Y</math> is injective and <math>A</math> is a [[subset]] of <math>X,</math> then <math>f^{-1}(f(A)) = A.</math> Thus, <math>A</math> can be recovered from its [[Image (function)|image]] <math>f(A).</math>
* If <math>f : X \to Y</math> is injective and <math>A</math> and <math>B</math> are both subsets of <math>X,</math> then <math>f(A \cap B) = f(A) \cap f(B).</math>
* Every function <math>h : W \to Y</math> can be decomposed as <math>h = f \circ g</math> for a suitable injection <math>f</math> and surjection <math>g.</math> This decomposition is unique [[up to isomorphism]], and <math>f</math> may be thought of as the [[inclusion function]] of the range <math>h(W)</math> of <math>h</math> as a subset of the codomain <math>Y</math> of <math>h.</math>
* If <math>f : X \to Y</math> is an injective function, then <math>Y</math> has at least as many elements as <math>X,</math> in the sense of [[cardinal number]]s. In particular, if, in addition, there is an injection from <math>Y</math> to <math>X,</math> then <math>X</math> and <math>Y</math> have the same cardinal number. (This is known as the [[Cantor–Bernstein–Schroeder theorem]].)
* If both <math>X</math> and <math>Y</math> are [[Finite set|finite]] with the same number of elements, then <math>f : X \to Y</math> is injective if and only if <math>f</math> is surjective (in which case <math>f</math> is bijective).
* An injective function which is a homomorphism between two algebraic structures is an [[embedding]].
* Unlike surjectivity, which is a relation between the graph of a function and its codomain, injectivity is a property of the graph of the function alone; that is, whether a function <math>f</math> is injective can be decided by only considering the graph (and not the codomain) of <math>f.</math>

== Proving that functions are injective ==

A proof that a function <math>f</math> is injective depends on how the function is presented and what properties the function holds.
For functions that are given by some formula there is a basic idea.
We use the definition of injectivity, namely that if <math>f(x) = f(y),</math> then <math>x = y.</math><ref>{{cite web|last=Williams|first=Peter|title=Proving Functions One-to-One|url=http://www.math.csusb.edu/notes/proofs/bpf/node4.html |date=Aug 21, 1996 |website=Department of Mathematics at CSU San Bernardino Reference Notes Page |archive-date= 4 June 2017|archive-url=https://web.archive.org/web/20170604162511/http://www.math.csusb.edu/notes/proofs/bpf/node4.html}}</ref>

Here is an example: 
<math display="block">f(x) = 2 x + 3</math>

Proof: Let <math>f : X \to Y.</math>  Suppose <math>f(x) = f(y).</math>  So <math>2 x + 3 = 2 y + 3</math> implies <math>2 x = 2 y,</math> which implies <math>x = y.</math>  Therefore, it follows from the definition that <math>f</math> is injective.

There are multiple other methods of proving that a function is injective.  For example, in calculus if <math>f</math> is a differentiable function defined on some interval, then it is sufficient to show that the derivative is always positive or always negative on that interval.  In linear algebra, if <math>f</math> is a linear transformation it is sufficient to show that the kernel of <math>f</math> contains only the zero vector.  If <math>f</math> is a function with finite domain it is sufficient to look through the list of images of each domain element and check that no image occurs twice on the list.

A graphical approach for a real-valued function <math>f</math> of a real variable <math>x</math> is the [[horizontal line test]]. If every horizontal line intersects the curve of <math>f(x)</math> in at most one point, then <math>f</math> is injective or one-to-one.

==Gallery==
{{Gallery
|perrow=4
|align=center
|Image:Injection.svg|An '''injective''' non-surjective function (injection, not a bijection)
|Image:Bijection.svg|An '''injective''' surjective function (bijection)
|Image:Surjection.svg|A non-injective surjective function (surjection, not a bijection)
|Image:Not-Injection-Surjection.svg|A non-injective non-surjective function (also not a bijection)
}}

{{Gallery
|perrow=3
|align=center
|Image:Non-injective function1.svg|Not an injective function. Here <math>X_1</math> and <math>X_2</math> are subsets of <math>X, Y_1</math> and <math>Y_2</math> are subsets of <math>Y</math>: for two regions where the function is not injective because more than one domain [[Element (mathematics)|element]] can map to a single range element. That is, it is possible for {{em|more than one}} <math>x</math> in <math>X</math> to map to the {{em|same}} <math>y</math> in <math>Y.</math>
|Image:Non-injective function2.svg|Making functions injective. The previous function <math>f : X \to Y</math> can be reduced to one or more injective functions (say) <math>f : X_1 \to Y_1</math> and <math>f : X_2 \to Y_2,</math> shown by solid curves (long-dash parts of initial curve are not mapped to anymore). Notice how the rule <math>f</math> has not changed – only the domain and range. <math>X_1</math> and <math>X_2</math> are subsets of <math>X, Y_1</math> and <math>Y_2</math> are subsets of <math>Y</math>: for two regions where the initial function can be made injective so that one domain element can map to a single range element. That is, only one <math>x</math> in <math>X</math> maps to one <math>y</math> in <math>Y.</math>
|Image:Injective function.svg|Injective functions. Diagramatic interpretation in the [[Cartesian plane]], defined by the [[Map (mathematics)|mapping]] <math>f : X \to Y,</math> where <math>y = f(x),</math> {{nowrap|<math>X =</math> domain of function}}, {{nowrap|<math>Y = </math> [[range of a function|range of function]]}}, and <math>\operatorname{im}(f)</math> denotes image of <math>f.</math> Every one <math>x</math> in <math>X</math> maps to exactly one unique <math>y</math> in <math>Y.</math> The circled parts of the axes represent domain and range sets— in accordance with the standard diagrams above
}}

== See also ==

* {{Annotated link|Bijection, injection and surjection}}
* {{Annotated link|Injective metric space}}
* {{Annotated link|Monotonic function}}
* {{Annotated link|Univalent function}}

== Notes ==

{{Reflist|group=note}}
{{Reflist}}

== 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.&nbsp;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|publisher=Springer|location=New York}}, p.&nbsp;38 ''ff''.

== External links ==

{{Commons category|Injectivity}}
{{Wiktionary|injective}}
* [http://jeff560.tripod.com/i.html Earliest Uses of Some of the Words of Mathematics: entry on Injection, Surjection and Bijection has the history of Injection and related terms.]
* [http://www.khanacademy.org/math/linear-algebra/v/surjective--onto--and-injective--one-to-one--functions Khan Academy – Surjective (onto) and Injective (one-to-one) functions: Introduction to surjective and injective functions]

{{Mathematical logic}}

{{Authority control}}

[[Category:Functions and mappings]]
[[Category:Basic concepts in set theory]]
[[Category:Types of functions]]