# Injective function

Short description: Function that preserves distinctness

In mathematics, an injective function (also known as injection, or one-to-one function) is a function f that maps distinct elements of its domain to distinct elements; that is, f(x1) = f(x2) implies x1 = x2. (Equivalently, x1x2 implies f(x1) Template:≠ 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. 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. 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.

## 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,$\displaystyle{ \forall a, b \in X, \;\; a \neq b \Rightarrow f(a) \neq f(b). }$

## Examples

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

• 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 : \R \to \R }$ defined by $\displaystyle{ f(x) = 2 x + 1 }$ is injective.
• The function $\displaystyle{ g : \R \to \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 : \R \to \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 \R }$ defined by $\displaystyle{ x \mapsto \ln x }$ is injective.
• The function $\displaystyle{ g : \R \to \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{ \R, }$ then an injective function $\displaystyle{ f : \R \to \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.

## 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 }$, 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.

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.
• 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. }$

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

Proof: Let $\displaystyle{ f : X \to Y. }$ Suppose $\displaystyle{ f(x) = f(y). }$ So $\displaystyle{ 2 x + 3 = 2 y + 3 }$ implies $\displaystyle{ 2 x = 2 y, }$ 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.