Injective function

related topics
{math, number, function}

In mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain. If in addition all of the elements in the codomain are in fact mapped to by some element of the domain, then the function is said to be bijective (see figures).

An injective function is called an injection, and is also said to be a one-to-one function (not to be confused with one-to-one correspondence, i.e. a bijective function). Occasionally, an injective function from X to Y is denoted f: XY, using an arrow with a barbed tail. Alternately, it may be denoted YX using a notation derived from that used for falling factorial powers, since if X and Y are finite sets with respectively x and y elements, the number of injections XY is yx (see the twelvefold way).

A function f that is not injective is sometimes called many-to-one. (However, this terminology is also sometimes used to mean "single-valued", i.e., each argument is mapped to at most one value; this is the case for any function, but is used to stress the opposition with multi-valued functions, which are not true functions.)

A monomorphism is a generalization of an injective function in category theory.

Contents

Definition

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

Examples

  • For any set X and any subset S of X the inclusion map SX (which sends any element s of S to itself) is injective. In particular the identity function XX is always injective (and in fact bijective).
  • 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 exp : RR defined by exp(x) = ex is injective (but not surjective as no 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) = xnx is not injective, since, for example, g(0) = g(1).

Full article ▸

related documents
Unit interval
Disjunctive normal form
Parse tree
Elias gamma coding
Euler's identity
Linear function
Inverse transform sampling
Inner automorphism
Regular graph
Urysohn's lemma
Connectedness
Specification language
Row and column spaces
NP-equivalent
Identity matrix
Additive function
Random sequence
Complete graph
Inequation
Minkowski's theorem
Inverse functions and differentiation
Babylonian numerals
Noetherian ring
Sum rule in differentiation
Column vector
Bookmarklet
Euler number
Ceva's theorem
Hyperplane
Elias delta coding