BREAKING NEWS
Injective function

## Summary

In mathematics, an injective function (also known as injection, or one-to-one function) is a function f that maps distinct elements to distinct elements; that is, f(x1) = f(x2) implies x1 = x2. (Equivalently, x1x2 implies f(x1) ≠ f(x2) in the equivalent contrapositive statement.) In other words, every element of the function's codomain is the image of at most one element of its domain.[1] 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.[2] This is thus a theorem that they are equivalent for algebraic structures; see Homomorphism § Monomorphism for more details.

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

## Definition

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

Symbolically,

${\displaystyle \forall a,b\in X,\;\;f(a)=f(b)\Rightarrow a=b,}$

which is logically equivalent to the contrapositive,[3]
${\displaystyle \forall a,b\in X,\;\;a\neq b\Rightarrow f(a)\neq f(b).}$

## Examples

Injective functions. Diagramatic interpretation in the Cartesian plane, defined by the mapping ${\displaystyle f:X\to Y,}$  where ${\displaystyle y=f(x),}$  ${\displaystyle X=}$  domain of function, ${\displaystyle Y=}$  range of function, and ${\displaystyle \operatorname {im} (f)}$  denotes image of ${\displaystyle f.}$  Every one ${\displaystyle x}$  in ${\displaystyle X}$  maps to exactly one unique ${\displaystyle y}$  in ${\displaystyle Y.}$  The circled parts of the axes represent domain and range sets— in accordance with the standard diagrams above.
• For any set ${\displaystyle X}$  and any subset ${\displaystyle S\subseteq X,}$  the inclusion map ${\displaystyle S\to X}$  (which sends any element ${\displaystyle s\in S}$  to itself) is injective. In particular, the identity function ${\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} }$  defined by ${\displaystyle f(x)=2x+1}$  is injective.
• The function ${\displaystyle g:\mathbb {R} \to \mathbb {R} }$  defined by ${\displaystyle g(x)=x^{2}}$  is not injective, because (for example) ${\displaystyle g(1)=1=g(-1).}$  However, if ${\displaystyle g}$  is redefined so that its domain is the non-negative real numbers [0,+∞), then ${\displaystyle g}$  is injective.
• The exponential function ${\displaystyle \exp :\mathbb {R} \to \mathbb {R} }$  defined by ${\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} }$  defined by ${\displaystyle x\mapsto \ln x}$  is injective.
• The function ${\displaystyle g:\mathbb {R} \to \mathbb {R} }$  defined by ${\displaystyle g(x)=x^{n}-x}$  is not injective, since, for example, ${\displaystyle g(0)=g(1)=0.}$

More generally, when ${\displaystyle X}$  and ${\displaystyle Y}$  are both the real line ${\displaystyle \mathbb {R} ,}$  then an injective function ${\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.[1]

Not an injective function. Here ${\displaystyle X_{1}}$  and ${\displaystyle X_{2}}$  are subsets of ${\displaystyle X,Y_{1}}$  and ${\displaystyle Y_{2}}$  are subsets of ${\displaystyle 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 more than one ${\displaystyle x}$  in ${\displaystyle X}$  to map to the same ${\displaystyle y}$  in ${\displaystyle Y.}$

Making functions injective. The previous function ${\displaystyle f:X\to Y}$  can be reduced to one or more injective functions (say) ${\displaystyle f:X_{1}\to Y_{1}}$  and ${\displaystyle 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 ${\displaystyle f}$  has not changed – only the domain and range. ${\displaystyle X_{1}}$  and ${\displaystyle X_{2}}$  are subsets of ${\displaystyle X,Y_{1}}$  and ${\displaystyle Y_{2}}$  are subsets of ${\displaystyle 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 ${\displaystyle x}$  in ${\displaystyle X}$  maps to one ${\displaystyle y}$  in ${\displaystyle Y.}$

## Injections can be undone

Functions with left inverses are always injections. That is, given ${\displaystyle f:X\to Y,}$  if there is a function ${\displaystyle g:Y\to X}$  such that for every ${\displaystyle x\in X,}$

${\displaystyle g(f(x))=x}$  (${\displaystyle f}$  can be undone by ${\displaystyle g}$ ), then ${\displaystyle f}$  is injective. In this case, ${\displaystyle g}$  is called a retraction of ${\displaystyle f.}$  Conversely, ${\displaystyle f}$  is called a section of ${\displaystyle g.}$

Conversely, every injection ${\displaystyle f}$  with non-empty domain has a left inverse ${\displaystyle g,}$  which can be defined by fixing an element ${\displaystyle a}$  in the domain of ${\displaystyle f}$  so that ${\displaystyle g(x)}$  equals the unique pre-image of ${\displaystyle x}$  under ${\displaystyle f}$  if it exists and ${\displaystyle g(x)=1}$  otherwise.[4]

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

## Injections may be made invertible

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

More generally, injective partial functions are called partial bijections.

## Other properties

• If ${\displaystyle f}$  and ${\displaystyle g}$  are both injective then ${\displaystyle f\circ g}$  is injective.

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

## Proving that functions are injective

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

Here is an example:

${\displaystyle f(x)=2x+3}$

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

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

4. ^ Unlike the corresponding statement that every surjective function has a right inverse, this does not require the axiom of choice, as the existence of ${\displaystyle a}$  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 ${\displaystyle \{0,1\}\to \mathbb {R} }$  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}.