Encyclopedia > Injection (mathematics)

  Article Content

Injection (mathematics)

A function fX → Y is called injective or one-to-one or an injection 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 fR → 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 fR → 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 gR → R defined by g(x) = x2 is not injective, because (for example) g(1) = 1 = g(−1).

However, if we define the function hR+ → 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 fX → Y is injective if and only if X is the empty set or there exists a function gY → 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.
  • fX → Y is injective if and only if, given any functions g,hW → 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 fX → 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 fX → Y is injective and A and B are both subsets of X, then f(A ∩ B) = f(A) ∩ f(B).
  • Every function hW → 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



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Monty Woolley

... His most famous role is that of the cranky professor forced to stay immobile because of a broken leg in 1942's The Man Who Came to Dinner[?], which he had performed ...

 
 
 
This page was created in 23.4 ms