Injective function

In mathematics, an injective function (also known as injection, or one-to-one function^[1] ) is a function f that maps distinct elements of its domain to distinct elements of its codomain; that is, x₁ ≠ x₂ implies f(x₁) ≠ f(x₂) (equivalently by contraposition, f(x₁) = f(x₂) implies x₁ = x₂). In other words, every element of the function's codomain is the image of at most one element of its domain.^[2] The term one-to-one function must not be confused with 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 injective homomorphism is also called a monomorphism . However, in the more general context of category theory, the definition of a monomorphism differs from that of an injective homomorphism.^[3] This is thus a theorem that they are equivalent for algebraic structures; see Homomorphism § Monomorphism for more details.

A function ${\displaystyle f}${\displaystyle f} that is not injective is sometimes called many-to-one.^[2]

Let ${\displaystyle f}${\displaystyle f} be a function whose domain is a set ${\displaystyle X.}${\displaystyle X.} The function ${\displaystyle f}${\displaystyle f} is said to be injective provided that for all ${\displaystyle a}${\displaystyle a} and ${\displaystyle b}${\displaystyle b} in ${\displaystyle X,}${\displaystyle X,} if ${\displaystyle f(a)=f(b),}${\displaystyle f(a)=f(b),} then ${\displaystyle a=b}${\displaystyle a=b}; that is, ${\displaystyle f(a)=f(b)}${\displaystyle f(a)=f(b)} implies ${\displaystyle a=b.}${\displaystyle a=b.} Equivalently, if ${\displaystyle a\neq b,}${\displaystyle a\neq b,} then ${\displaystyle f(a)\neq f(b)}${\displaystyle f(a)\neq f(b)} in the contrapositive statement.

Symbolically,$${\displaystyle \forall a,b\in X,\;\;f(a)=f(b)\Rightarrow a=b,}$${\displaystyle \forall a,b\in X,\;\;f(a)=f(b)\Rightarrow a=b,} which is logically equivalent to the contrapositive,^[4] $${\displaystyle \forall a,b\in X,\;\;a\neq b\Rightarrow f(a)\neq f(b).}$${\displaystyle \forall a,b\in X,\;\;a\neq b\Rightarrow f(a)\neq f(b).}An injective function (or, more generally, a monomorphism) is often denoted by using the specialized arrows ↣ or ↪ (for example, ${\displaystyle f:A\rightarrowtail B}${\displaystyle f:A\rightarrowtail B} or ${\displaystyle f:A\hookrightarrow B}${\displaystyle f:A\hookrightarrow B}), although some authors specifically reserve ↪ for an inclusion map.^[5]

For visual examples, readers are directed to the gallery section.

• For any set ${\displaystyle X}${\displaystyle X} and any subset ${\displaystyle S\subseteq X,}${\displaystyle S\subseteq X,} the inclusion map ${\displaystyle S\to X}${\displaystyle S\to X} (which sends any element ${\displaystyle s\in S}${\displaystyle s\in S} to itself) is injective. In particular, the identity function ${\displaystyle X\to X}${\displaystyle X\to X} 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 ${\displaystyle f:\mathbb {R} \to \mathbb {R} }${\displaystyle f:\mathbb {R} \to \mathbb {R} } defined by ${\displaystyle f(x)=2x+1}${\displaystyle f(x)=2x+1} is injective.
• The function ${\displaystyle g:\mathbb {R} \to \mathbb {R} }${\displaystyle g:\mathbb {R} \to \mathbb {R} } defined by ${\displaystyle g(x)=x^{2}}${\displaystyle g(x)=x^{2}} is not injective, because (for example) ${\displaystyle g(1)=1=g(-1).}${\displaystyle g(1)=1=g(-1).} However, if ${\displaystyle g}${\displaystyle g} is redefined so that its domain is the non-negative real numbers [0,+∞), then ${\displaystyle g}${\displaystyle g} is injective.
• The exponential function ${\displaystyle \exp :\mathbb {R} \to \mathbb {R} }${\displaystyle \exp :\mathbb {R} \to \mathbb {R} } defined by ${\displaystyle \exp(x)=e^{x}}${\displaystyle \exp(x)=e^{x}} is injective (but not surjective, as no real value maps to a negative number).
• The natural logarithm function ${\displaystyle \ln :(0,\infty )\to \mathbb {R} }${\displaystyle \ln :(0,\infty )\to \mathbb {R} } defined by ${\displaystyle x\mapsto \ln x}${\displaystyle x\mapsto \ln x} is injective.
• The function ${\displaystyle g:\mathbb {R} \to \mathbb {R} }${\displaystyle g:\mathbb {R} \to \mathbb {R} } defined by ${\displaystyle g(x)=x^{n}-x}${\displaystyle g(x)=x^{n}-x} is not injective, since, for example, ${\displaystyle g(0)=g(1)=0.}${\displaystyle g(0)=g(1)=0.}

More generally, when ${\displaystyle X}${\displaystyle X} and ${\displaystyle Y}${\displaystyle Y} are both the real line ${\displaystyle \mathbb {R} ,}${\displaystyle \mathbb {R} ,} then an injective function ${\displaystyle f:\mathbb {R} \to \mathbb {R} }${\displaystyle f:\mathbb {R} \to \mathbb {R} } is one whose graph is never intersected by any horizontal line more than once. This principle is referred to as the horizontal line test .^[2]

Functions with left inverses are always injections. That is, given ${\displaystyle f:X\to Y,}${\displaystyle f:X\to Y,} if there is a function ${\displaystyle g:Y\to X}${\displaystyle g:Y\to X} such that for every ${\displaystyle x\in X}${\displaystyle x\in X}, ${\displaystyle g(f(x))=x}${\displaystyle g(f(x))=x}, then ${\displaystyle f}${\displaystyle f} is injective. In this case, ${\displaystyle g}${\displaystyle g} is called a retraction of ${\displaystyle f.}${\displaystyle f.} Conversely, ${\displaystyle f}${\displaystyle f} is called a section of ${\displaystyle g.}${\displaystyle g.}

Conversely, every injection ${\displaystyle f}${\displaystyle f} with a non-empty domain has a left inverse ${\displaystyle g}${\displaystyle g}. It can be defined by choosing an element ${\displaystyle a}${\displaystyle a} in the domain of ${\displaystyle f}${\displaystyle f} and setting ${\displaystyle g(y)}${\displaystyle g(y)} to the unique element of the pre-image ${\displaystyle f^{-1}[y]}${\displaystyle f^{-1}[y]} (if it is non-empty) or to ${\displaystyle a}${\displaystyle a} (otherwise).^[6]

The left inverse ${\displaystyle g}${\displaystyle g} is not necessarily an inverse of ${\displaystyle f,}${\displaystyle f,} because the composition in the other order, ${\displaystyle f\circ g,}${\displaystyle f\circ g,} may differ from the identity on ${\displaystyle Y.}${\displaystyle 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.

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

More generally, injective partial functions are called partial bijections.

• If ${\displaystyle f}${\displaystyle f} and ${\displaystyle g}${\displaystyle g} are both injective then ${\displaystyle f\circ g}${\displaystyle f\circ g} is injective.
• If ${\displaystyle g\circ f}${\displaystyle g\circ f} is injective, then ${\displaystyle f}${\displaystyle f} is injective (but ${\displaystyle g}${\displaystyle g} need not be).
• ${\displaystyle f:X\to Y}${\displaystyle f:X\to Y} is injective if and only if, given any functions ${\displaystyle g,}${\displaystyle g,} ${\displaystyle h:W\to X}${\displaystyle h:W\to X} whenever ${\displaystyle f\circ g=f\circ h,}${\displaystyle f\circ g=f\circ h,} then ${\displaystyle g=h.}${\displaystyle g=h.} In other words, injective functions are precisely the monomorphisms in the category Set of sets.
• If ${\displaystyle f:X\to Y}${\displaystyle f:X\to Y} is injective and ${\displaystyle A}${\displaystyle A} is a subset of ${\displaystyle X,}${\displaystyle X,} then ${\displaystyle f^{-1}(f(A))=A.}${\displaystyle f^{-1}(f(A))=A.} Thus, ${\displaystyle A}${\displaystyle A} can be recovered from its image ${\displaystyle f(A).}${\displaystyle f(A).}
• If ${\displaystyle f:X\to Y}${\displaystyle f:X\to Y} is injective and ${\displaystyle A}${\displaystyle A} and ${\displaystyle B}${\displaystyle B} are both subsets of ${\displaystyle X,}${\displaystyle X,} then ${\displaystyle f(A\cap B)=f(A)\cap f(B).}${\displaystyle f(A\cap B)=f(A)\cap f(B).}
• Every function ${\displaystyle h:W\to Y}${\displaystyle h:W\to Y} can be decomposed as ${\displaystyle h=f\circ g}${\displaystyle h=f\circ g} for a suitable injection ${\displaystyle f}${\displaystyle f} and surjection ${\displaystyle g.}${\displaystyle g.} This decomposition is unique up to isomorphism, and ${\displaystyle f}${\displaystyle f} may be thought of as the inclusion function of the range ${\displaystyle h(W)}${\displaystyle h(W)} of ${\displaystyle h}${\displaystyle h} as a subset of the codomain ${\displaystyle Y}${\displaystyle Y} of ${\displaystyle h.}${\displaystyle h.}
• If ${\displaystyle f:X\to Y}${\displaystyle f:X\to Y} is an injective function, then ${\displaystyle Y}${\displaystyle Y} has at least as many elements as ${\displaystyle X,}${\displaystyle X,} in the sense of cardinal numbers. In particular, if, in addition, there is an injection from ${\displaystyle Y}${\displaystyle Y} to ${\displaystyle X,}${\displaystyle X,} then ${\displaystyle X}${\displaystyle X} and ${\displaystyle Y}${\displaystyle Y} have the same cardinal number. (This is known as the Cantor–Bernstein–Schroeder theorem.)
• If both ${\displaystyle X}${\displaystyle X} and ${\displaystyle Y}${\displaystyle Y} are finite with the same number of elements, then ${\displaystyle f:X\to Y}${\displaystyle f:X\to Y} is injective if and only if ${\displaystyle f}${\displaystyle f} is surjective (in which case ${\displaystyle f}${\displaystyle f} 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 ${\displaystyle f}${\displaystyle f} is injective can be decided by only considering the graph (and not the codomain) of ${\displaystyle f.}${\displaystyle f.}

A proof that a function ${\displaystyle f}${\displaystyle f} 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 ${\displaystyle f(x)=f(y),}${\displaystyle f(x)=f(y),} then ${\displaystyle x=y.}${\displaystyle x=y.}^[7]

Here is an example: $${\displaystyle f(x)=2x+3}$${\displaystyle f(x)=2x+3}

Proof: Let ${\displaystyle f:X\to Y.}${\displaystyle f:X\to Y.} Suppose ${\displaystyle f(x)=f(y).}${\displaystyle f(x)=f(y).} So ${\displaystyle 2x+3=2y+3}${\displaystyle 2x+3=2y+3} implies ${\displaystyle 2x=2y,}${\displaystyle 2x=2y,} which implies ${\displaystyle x=y.}${\displaystyle x=y.} Therefore, it follows from the definition that ${\displaystyle f}${\displaystyle f} is injective.

There are multiple other methods of proving that a function is injective. For example, in calculus if ${\displaystyle f}${\displaystyle f} 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 ${\displaystyle f}${\displaystyle f} is a linear transformation it is sufficient to show that the kernel of ${\displaystyle f}${\displaystyle f} contains only the zero vector. If ${\displaystyle f}${\displaystyle f} 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 ${\displaystyle f}${\displaystyle f} of a real variable ${\displaystyle x}${\displaystyle x} is the horizontal line test. If every horizontal line intersects the curve of ${\displaystyle f(x)}${\displaystyle f(x)} in at most one point, then ${\displaystyle f}${\displaystyle f} is injective or one-to-one.

• Bijection, injection and surjection – Properties of mathematical functions
• Injective metric space – Type of metric space
• Monotonic function – Order-preserving mathematical function
• Univalent function – Mathematical concept

• Bartle, Robert G. (1976), The Elements of Real Analysis (2nd ed.), New York: John Wiley & Sons, ISBN 978-0-471-05464-1 , p. 17 ff.
• Halmos, Paul R. (1974), Naive Set Theory , New York: Springer, ISBN 978-0-387-90092-6 , p. 38 ff.

• Earliest Uses of Some of the Words of Mathematics: entry on Injection, Surjection and Bijection has the history of Injection and related terms.
• Khan Academy – Surjective (onto) and Injective (one-to-one) functions: Introduction to surjective and injective functions

• Functions and mappings
• Basic concepts in set theory
• Types of functions

• Articles with short description
• Short description is different from Wikidata
• Commons category link is on Wikidata