Injective function
From Free net encyclopedia
Image:Injective and non-surjective.png Image:Bijmap.png Image:Non-injective and surjective.png In mathematics, an injective function is a function which associates distinct arguments to distinct values. More precisely, a function f is said to be injective if and only if, for every y in the codomain, there is at most one x in the domain such that f(x) = y.
Put another way, f is injective if and only if f(a) = f(b) implies a = b (or a <math>\neq</math> b implies f(a) <math>\neq</math> f(b)), for any a, b in the domain.
An injective function is called an injection, and is also said to be information-preserving or, sometimes, one-to-one function. (However, this name is best avoided, since some authors understand it to mean a one-to-one correspondence, i.e. a bijective function.)
A function f that is not injective is sometimes called many-to-one. However, this name too is best avoided, since it is sometimes used to mean "single-valued" — i.e. each argument is mapped to at most one value.
Contents |
Examples and counter-examples
- For any set X, the identity function on X is injective.
- The function f : R → R defined by f(x) = 2x + 1 is injective.
- The function g : R → R defined by g(x) = x2 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 <math>\exp : \mathbf{R} \to \mathbf{R}^+ : x \mapsto \mathrm{e}^x</math> is injective.
- The natural logarithm function <math>\ln : (0,+\infty) \to \mathbf{R} : x \mapsto \ln{x}</math> is injective.
- The function g : R → R defined by <math>g(x) = x^3 - x </math> is not injective, since, for example, g(-1) = g(0) = g(+1).
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.
Injections are invertible
Another definition of injection is a function whose effect can be undone. More precisely, f : X → Y is injective if and only if there exists a function g : Y → X such that g(f(x)) = x for every x in ´ X; that is, g o f equals the identity function on X.
Note that g may not be a complete inverse of f because the composition in the other order, f o g, may not be the identity on Y.
In fact, to turn an injective function f : X → Y into a bijective (hence invertible) function, it suffices to replace its codomain Yby 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 inclJ,Yog, where inclJ,Yis the inclusion function from J into Y.
Other properties
- If f and g are both injective, then g o f is injective.
- If g o 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 o g = f o h, then g = h.
- If f : X → Y is injective and A is a subset of X, then f −1(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 o 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.
- 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.
- Every embedding is injective.
Category theory view
In the language of category theory, injective functions are precisely the monomorphisms in the category of sets.
See also
bg:Инекция da:Injektiv de:Injektivität es:Función inyectiva fr:Injection he:פונקציה חד חד ערכית io:Injektio it:Funzione iniettiva nl:Injectie (wiskunde) ja:単射 pl:Funkcja różnowartościowa ru:Инъективность fi:Injektio sv:Injektiv