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}$ that is not injective is sometimes called many-to-one.^[2]

Definition

An injective function, which is not also surjective

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,^[4]$${\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}$ or ⁠${\displaystyle f:A\hookrightarrow B}$ ⁠), although some authors specifically reserve ↪ for an inclusion map.^[5]

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:\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.^[2]

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. The proof is that $${\displaystyle f(a)=f(b)\rightarrow g(f(a))=g(f(b))\rightarrow a=b.}$$

In this case, ${\displaystyle g}$ is called a retraction of ⁠${\displaystyle f}$ ⁠. Conversely, ${\displaystyle f}$ is called a section of ⁠${\displaystyle g}$ ⁠. For example: ${\displaystyle f:\mathbb {R} \rightarrow \mathbb {R} ^{2},x\mapsto (1,m)^{\intercal }x}$ is retracted by ⁠${\displaystyle g:y\mapsto {\frac {(1,m)}{1+m^{2}}}y}$ ⁠.

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

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 image ${\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

The composition of two injective functions is injective.

• 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}$ ⁠.^[7]

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.

Gallery

• 
  An injective non-surjective function (injection, not a bijection)
• 
  An injective surjective function (bijection)
• 
  A non-injective surjective function (surjection, not a bijection)
• 
  A non-injective non-surjective function (also not a bijection)

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

See also

• 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

Notes

1. Sometimes one-one function in Indian mathematical education. "Chapter 1: Relations and functions" (PDF). Archived (PDF) from the original on December 26, 2023 – via NCERT.
2. "Injective, Surjective and Bijective". Math is Fun. Retrieved 2019-12-07.
3. "Section 7.3 (00V5): Injective and surjective maps of presheaves". The Stacks project. Retrieved 2019-12-07.
4. Farlow, S. J. "Section 4.2 Injections, Surjections, and Bijections" (PDF). Mathematics & Statistics - University of Maine. Archived from the original (PDF) on Dec 7, 2019. Retrieved 2019-12-06.
5. "What are usual notations for surjective, injective and bijective functions?". Mathematics Stack Exchange. Retrieved 2024-11-24.
6. 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}.
7. Williams, Peter (Aug 21, 1996). "Proving Functions One-to-One". Department of Mathematics at CSU San Bernardino Reference Notes Page. Archived from the original on 4 June 2017.

References

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

External links

• 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