imported>Mesocyclonic93: Reverted edit by Asmae BOUKDIR1 (talk) to last version by Lemondoge

2026-03-31T17:47:42Z

Reverted edit by Asmae BOUKDIR1 (talk) to last version by Lemondoge

New page

{{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= December 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''1 ≠ ''x''2}} implies {{math|''f''(''x''1) {{≠}} ''f''(''x''2)}} (equivalently by [[contraposition]], {{math|''f''(''x''1) {{=}} ''f''(''x''2)}} implies {{math|1=''x''1 = ''x''2}}). 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 ==
{{dark mode invert|[[file:Injection.svg|thumb|alt=The sets X = {1, 2, 3} and Y = {A, B, C, D}, and a function mapping 1 to D, 2 to B, and 3 to A.|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 {{tmath| X }}. 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 {{tmath|1= f(a) = f(b)}}, then {{tmath|1= a = b }}; that is, <math>f(a) = f(b)</math> implies {{tmath|1= a = b}}. Equivalently, if {{tmath| a \neq b }}, 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 {{tmath| f:A\hookrightarrow B}}), 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 {{tmath| S \subseteq X }}, 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 {{math|[0, +∞)}}, 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, {{tmath|1= g(0) = g(1) = 0}}.

More generally, when <math>X</math> and <math>Y</math> are both the [[real line]] {{tmath| \R }}, 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 {{tmath| f : X \to Y }}, if there is a function <math>g : Y \to X</math> such that for every {{tmath| x \in X }}, {{tmath|1= g(f(x)) = x }}, then <math>f</math> is injective. The proof is that
<math display="block">f(a) = f(b) \rightarrow g(f(a))=g(f(b)) \rightarrow a = b.</math>

In this case, <math>g</math> is called a [[Retract (category theory)|retraction]] of {{tmath| f }}. Conversely, <math>f</math> is called a [[Retract (category theory)|section]] of {{tmath| g }}.
For example: <math>f:\R\rightarrow\R^2,x\mapsto(1,m)^\intercal x</math> is retracted by {{tmath| g:y\mapsto\frac{(1,m)}{1+m^2}y }}.

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, {{tmath| f \circ g }}, may differ from the identity on {{tmath| Y }}. 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 {{tmath| x \in X }}; then <math>g</math> is bijective. Indeed, <math>f</math> can be factored as {{tmath| \operatorname{In}_{J,Y} \circ g }}, where <math>\operatorname{In}_{J,Y}</math> is the [[inclusion function]] from <math>J</math> into {{tmath| Y }}.

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

== Other properties ==
{{See also|List of set identities and relations#Functions and sets}}
{{Dark mode invert|[[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 {{tmath| g }}, <math>h : W \to X</math> whenever {{tmath|1= f \circ g = f \circ h }}, then {{tmath|1= g = h }}. 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 {{tmath| X }}, then {{tmath|1= f^{-1}(f(A)) = A }}. Thus, <math>A</math> can be recovered from its [[Image (function)|image]] {{tmath| f(A) }}.
* If <math>f : X \to Y</math> is injective and <math>A</math> and <math>B</math> are both subsets of {{tmath| X }}, then {{tmath|1= f(A \cap B) = f(A) \cap f(B) }}.
* 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 {{tmath| g }}. 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 {{tmath| h }}.
* 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 {{tmath| Y }} to {{tmath| X }}, 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 {{tmath| f }}.

== 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 {{tmath|1= f(x) = f(y) }}, then {{tmath|1= x = y }}.<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 {{tmath| f : X \to Y }}. Suppose {{tmath|1= f(x) = f(y) }}. So <math>2 x + 3 = 2 y + 3</math> implies {{tmath|1= 2 x = 2 y }}, which implies {{tmath|1= x = y }}. 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
|File:Injection.svg|alt1=The sets X = {1, 2, 3} and Y = {A, B, C, D}, and a function mapping 1 to D, 2 to B, and 3 to A.|An '''injective''' non-surjective function (injection, not a bijection)
|File:Bijection.svg|alt2=The sets X = {1, 2, 3, 4} and Y = {A, B, C, D}, and a function mapping 1 to D, 2 to B, 3 to C, and 4 to A.|An '''injective''' surjective function (bijection)
|File:Surjection.svg|alt3=The sets X = {1, 2, 3, 4} and Y = {B, C, D}, and a function mapping 1 to D, 2 to B, 3 to C, and 4 to C.|A non-injective surjective function (surjection, not a bijection)
|File:Not-Injection-Surjection.svg|alt4=The sets X = {1, 2, 3, 4} and Y = {A, B, C, D}, and a function mapping 1 to D, 2 to B, 3 to C, and 4 to C.|A non-injective non-surjective function (also not a bijection)
}}

{{gallery
|perrow=3
|align=center
|File: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 {{tmath| Y }}: 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 {{tmath| Y }}.
|File: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 {{tmath| f : X_2 \to Y_2 }}, 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 {{tmath| Y }}: 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 {{tmath| Y }}.
|File:Injective function.svg|Injective functions. Diagramatic interpretation in the [[Cartesian plane]], defined by the [[Map (mathematics)|mapping]] {{tmath| f : X \to Y }}, where {{tmath|1= y = f(x) }}, {{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 {{tmath| f }}. Every one <math>x</math> in <math>X</math> maps to exactly one unique <math>y</math> in {{tmath| Y }}. 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. 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. 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]]

Injective function - Revision history

imported>Mesocyclonic93: Reverted edit by Asmae BOUKDIR1 (talk) to last version by Lemondoge