Injective function

{{dark mode invert|}} Let f be a function whose domain is a set . The function f is said to be injective provided that for all a and b in X, if , then ; that is, f(a) = f(b) implies . Equivalently, if , then f(a) \neq f(b) in the contrapositive statement. Symbolically,\forall a,b \in X, \;\; f(a)=f(b) \Rightarrow a=b, which is logically equivalent to the contrapositive,\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, f:A\rightarrowtail B or ), although some authors specifically reserve ↪ for an inclusion map. == Examples ==

For visual examples, readers are directed to the gallery section. • For any set X and any subset , the inclusion map S \to X (which sends any element s \in S to itself) is injective. In particular, the identity function 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 f : \R \to \R defined by f(x) = 2 x + 1 is injective. • The function g : \R \to \R defined by g(x) = x^2 is injective, because (for example) g(1) = 1 = g(-1). However, if g is redefined so that its domain is the non-negative real numbers , then g is injective. • The exponential function \exp : \R \to \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, \infty) \to \R defined by x \mapsto \ln x is injective. • The function g : \R \to \R defined by g(x) = x^n - x is not injective, since, for example, . More generally, when X and Y are both the real line , then an injective function 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 . == Injections can be undone ==

Functions with left inverses are always injections. That is, given , if there is a function g : Y \to X such that for every , , then f is injective. The proof is that f(a) = f(b) \rightarrow g(f(a))=g(f(b)) \rightarrow a = b. In this case, g is called a retraction of . Conversely, f is called a section of . For example: f:\R\rightarrow\R^2,x\mapsto(1,m)^\intercal x is retracted by {{tmath| g:y\mapsto\frac{(1,m)}{1+m^2}y }}. Conversely, every injection f with a non-empty domain has a left inverse g. It can be defined by choosing an element a in the domain of f and setting g(y) to the unique element of the pre-image f^{-1}[y] (if it is non-empty) or to a (otherwise).{{refn|Unlike the corresponding statement that every surjective function has a right inverse, this does not require the axiom of choice, as the existence of 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 \{ 0, 1 \} \to \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}.}} The left inverse g is not necessarily an inverse of f, because the composition in the other order, , may differ from the identity on . 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 f : X \to Y into a bijective (hence invertible) function, it suffices to replace its codomain Y by its actual image J = f(X). That is, let g : X \to J such that g(x) = f(x) for all ; then g is bijective. Indeed, f can be factored as {{tmath| \operatorname{In}_{J,Y} \circ g }}, where \operatorname{In}_{J,Y} is the inclusion function from J into . More generally, injective partial functions are called partial bijections. == Other properties ==

• If f and g are both injective then f \circ g is injective. • If g \circ f is injective, then f is injective (but g need not be). • f : X \to Y is injective if and only if, given any functions , h : W \to X whenever , then . In other words, injective functions are precisely the monomorphisms in the category Set of sets. • If f : X \to Y is injective and A is a subset of , then {{tmath|1= f^{-1}(f(A)) = A }}. Thus, A can be recovered from its image . • If f : X \to Y is injective and A and B are both subsets of , then . • Every function h : W \to Y can be decomposed as h = f \circ g for a suitable injection f and surjection . 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 . • If f : X \to 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 to , 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 \to 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 . == Proving that functions are injective ==

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 , then . Here is an example: f(x) = 2 x + 3 Proof: Let . Suppose . So 2 x + 3 = 2 y + 3 implies , which implies . 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. == Gallery ==