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= December 26, 2023 }}</ref>) is a function {{math|''f''}} that maps 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 of {{em|at most}} one element of its 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 functions, which are functions such that each element in the codomain is an image of ''exactly one'' element in the domain.

A homomorphism between algebraic structures is a function that is compatible with the operations of the structures. For all common algebraic structures, and, in particular for vector spaces, 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]]}} {{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 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 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 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, 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 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 retraction of {{tmath| f }}. Conversely, <math>f</math> is called a 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, by giving a retraction of the real line to the set {0,1}.}}

The left inverse <math>g</math> is not necessarily an 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 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 functions are called partial bijections.

== Other properties == {{See also|List of set identities and relations#Functions and sets}} {{Dark mode invert|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 monomorphisms in the category '''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 {{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 numbers. 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 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 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 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 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 ==

== 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 |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]

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