Injective function

Let f be a function whose domain is a set X. The function f is said to be injective provided that for all a and b in X, whenever f(a) = f(b), then a = b; that is, f(a) = f(b) implies a = b.  Equivalently, if a ≠ b, then f(a) ≠ f(b).

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)}$[4][5]

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

More generally, when X and Y are both the real line R, then an injective function f : R → 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]

Injective functions. Diagramatic interpretation in the Cartesian plane, defined by the mapping f : X → Y, where y = f(x), X = domain of function, Y = range of function, and im(f) denotes image of f. Every one x in X maps to exactly one unique y in Y. The circled parts of the axes represent domain and range sets— in accordance with the standard diagrams above.

Not an injective function. Here X₁ and X₂ are subsets of X, Y₁ and Y₂ are subsets of 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 x in X to map to the same y in Y.

Making functions injective. The previous function f : X → Y can be reduced to one or more injective functions (say) f : X₁ → Y₁ and f : X₂ → Y₂, shown by solid curves (long-dash parts of initial curve are not mapped to anymore). Notice how the rule f has not changed – only the domain and range. X₁ and X₂ are subsets of X, Y₁ and Y₂ are subsets of 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 x in X maps to one y in Y.

Functions with left inverses are always injections. That is, given f : X → Y, if there is a function g : Y → X such that for every x ∈ X,

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

Conversely, every injection f with non-empty domain has a left inverse g, which can be defined by fixing an element a in the domain of f so that g(x) equals the unique preimage of x under f if it exists and g(x) = a otherwise.[6]

The left inverse g is not necessarily an inverse of f, because the composition in the other order, f ∘ g, may differ from the identity on 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 f : X → Y into a bijective (hence invertible) function, it suffices to replace its codomain Y by its actual range J = f(X). That is, let g : X → J such that g(x) = f(x) for all x in X; then g is bijective. Indeed, f can be factored as incl_J,Y ∘ g, where incl_J,Y is the inclusion function from J into Y.

More generally, injective partial functions are called partial bijections.

• If f and g are both injective, then f ∘ g is injective.

The composition of two injective functions is injective.

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

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

Here is an example:

f = 2x + 3

Proof: Let f : X → Y. Suppose f(x) = f(y). So 2x + 3 = 2y + 3 ⇒ 2x = 2y ⇒ x = y. Therefore, it follows from the definition that f is injective.

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

• Bijection, injection and surjection
• Injective metric space
• Monotonic function
• Univalent function

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

Wikimedia Commons has media related to Injectivity.

Look up injective in Wiktionary, the free dictionary.

• 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