Injective function

From Wikipedia, the free encyclopedia

(Redirected from Injective)

Jump to: navigation, search

"One-to-one" redirects here. For other uses, see One-to-one (disambiguation).

"Injective" redirects here. For injective modules, see Injective module.

An injective function.

Another injective function.

A non-injective function.

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 it maps distinct x in the domain to distinct y in the codomain, such that f(x) = y.

Put another way, f is injective if f(a) = f(b) implies a = b (or a ≠ b implies f(a) ≠ f(b)), for any a, b in the domain.

An injective function is called an injection, and is also said to be an information-preserving or one-to-one function (however, the latter 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.

1 Examples and counter-examples
2 Injections can be undone
3 Injections may be made invertible
4 Other properties
5 Category theory view
6 See also

[edit] 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) = x² 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 : \mathbf{R} \to \mathbf{R} : x \mapsto \mathrm{e}^x$ is injective (but not surjective as no value maps to a negative number).
The natural logarithm function $\ln : (0,+\infty) \to \mathbf{R} : x \mapsto \ln{x}$ is injective.
The function g : R → R defined by $g (x) = x n - x$ is not injective, since, for example, 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.

[edit] Injections can be undone

Functions with left inverses (often called sections) are always injections. That is to say, for f : X → Y, if there exists a function g : Y → X such that, for every $x \in X$

$g(f(x)) = x \,$ (f can be undone by g)

then f is injective. Conversely, it is usually assumed that every injection with non-empty domain has a left inverse.

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 other words, a function that can be undone or "reversed", such as f, is not necessarily invertible (bijective). Injections are "reversible" but not always invertible.

Although it is impossible to reverse a non-injective (and therefore information-losing) function, you can at least obtain a "quasi-inverse" of it, that is a multiple-valued function.

[edit] Injections may be made invertible

In fact, to turn an injective function f : X → Y into a bijective (hence invertible) function, it suffices to replace its codomain Y by 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 incl_J,Yog, where incl_J,Yis the inclusion function from J into Y.

[edit] Other properties

If f and g are both injective, then f o g is injective.

The composition of two injective functions 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⁻¹(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.