Injective function
A mathematical function is called injective (or one-to-one or an injection) if the function maps no more than one possible input value to each possible output value. (This is in contrast to a "many to one" function, which maps two or more input values to some output values). If, additionally, every output value has some input value that maps to it, the function is sometimes called a one-to-one correspondence; see bijection.
More formally, a function f: X → Y is injective if for every y in the codomain Y there is at most one x in the domain X with f(x) = y.
Put another way, given x and x' in X, if f(x) = f(x'), then it follows that x = x'.
Surjective, not injective |
Injective, not surjective |
Bijective |
Not surjective, not injective |
When X and Y are both the real line R, then an injective function f: R → R can be visualized as one whose graph is never intersected by any horizontal line more than once.
(This is the horizontal line test.)
Examples and counterexamples
Consider the function f: R → R defined by f(x) = 2x + 1.
This function is injective, since given arbitrary real numbers x and x', if 2x + 1 = 2x' + 1, then 2x = 2x', so x = x'.
On the other hand, the function g: R → R defined by g(x) = x2 is not injective, because (for example) g(1) = 1 = g(−1).
However, if we define the function h: R+ → R by the same formula as g, but with the domain restricted to only the nonnegative real numbers, then the function h is injective.
This is because, given arbitrary nonnegative real numbers x and x', if x2 = x'2, then |x| = |x'|, so x = x'.
Properties
- A function f: X → Y is injective if and only if X is the empty set or there exists a function g: Y → X such that g o f equals the identity function on X.
- A function is bijective if and only if it is both injective and surjective.
- If g o f is injective, then f is injective.
- If f and g are both injective, then g o f is injective.
- 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. In other words, injective functions are precisely the monomorphisms in the category of sets.
- 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.
See also: Surjection, Bijection, Injective module
Referenced By
BiJection | Bijective | Bijective function | Bijective map | List of basic discrete mathematics topics | One-to-one correspondence | Surjection
|
