Injective function

Template:Short description Template:Redirect Template:Functions

In mathematics, an injective function (also known as injection, or one-to-one function<ref>Sometimes one-one function, in Indian mathematical education. {{#invoke:citation/CS1|citation |CitationClass=web }}</ref> ) is a function Template:Math that maps distinct elements of its domain to distinct elements of its codomain; that is, Template:Math implies Template:Math (equivalently by contraposition, Template:Math implies Template:Math). In other words, every element of the function's codomain is the image of Template:Em one element of its domain.<ref name=":0">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> The term Template:Em must not be confused with Template:Em that refers to bijective functions, which are functions such that each element in the codomain is an image of exactly one element in the domain.

A homomorphism between algebraic structures is a function that is compatible with the operations of the structures. For all common algebraic structures, and, in particular for vector spaces, an Template:Em is also called a Template:Em. However, in the more general context of category theory, the definition of a monomorphism differs from that of an injective homomorphism.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> This is thus a theorem that they are equivalent for algebraic structures; see Template:Slink for more details.

A function <math>f</math> that is not injective is sometimes called many-to-one.<ref name=":0" />

DefinitionEdit

File:Injection.svg

An injective function, which is not also surjective.

Template:Further Let <math>f</math> be a function whose domain is a set <math>X.</math> The function <math>f</math> is said to be injective provided that for all <math>a</math> and <math>b</math> in <math>X,</math> if <math>f(a) = f(b),</math> then <math>a = b</math>; that is, <math>f(a) = f(b)</math> implies <math>a=b.</math> Equivalently, if <math>a \neq b,</math> then <math>f(a) \neq f(b)</math> in the contrapositive statement.

Symbolically,<math display="block">\forall a,b \in X, \;\; f(a)=f(b) \Rightarrow a=b,</math> which is logically equivalent to the contrapositive,<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref><math display="block">\forall a, b \in X, \;\; a \neq b \Rightarrow f(a) \neq f(b).</math>An injective function (or, more generally, a monomorphism) is often denoted by using the specialized arrows ↣ or ↪ (for example, <math>f:A\rightarrowtail B</math> or <math>f:A\hookrightarrow B</math>), although some authors specifically reserve ↪ for an inclusion map.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

ExamplesEdit

For visual examples, readers are directed to the gallery section.

For any set <math>X</math> and any subset <math>S \subseteq X,</math> the inclusion map <math>S \to X</math> (which sends any element <math>s \in S</math> to itself) is injective. In particular, the identity function <math>X \to X</math> is always injective (and in fact bijective).
If the domain of a function is the empty set, then the function is the empty function, which is injective.
If the domain of a function has one element (that is, it is a singleton set), then the function is always injective.
The function <math>f : \R \to \R</math> defined by <math>f(x) = 2 x + 1</math> is injective.
The function <math>g : \R \to \R</math> defined by <math>g(x) = x^2</math> is Template:Em injective, because (for example) <math>g(1) = 1 = g(-1).</math> However, if <math>g</math> is redefined so that its domain is the non-negative real numbers [0,+∞), then <math>g</math> is injective.
The exponential function <math>\exp : \R \to \R</math> defined by <math>\exp(x) = e^x</math> is injective (but not surjective, as no real value maps to a negative number).
The natural logarithm function <math>\ln : (0, \infty) \to \R</math> defined by <math>x \mapsto \ln x</math> is injective.
The function <math>g : \R \to \R</math> defined by <math>g(x) = x^n - x</math> is not injective, since, for example, <math>g(0) = g(1) = 0.</math>

More generally, when <math>X</math> and <math>Y</math> are both the real line <math>\R,</math> then an injective function <math>f : \R \to \R</math> is one whose graph is never intersected by any horizontal line more than once. This principle is referred to as the Template:Em.<ref name=":0" />

Injections can be undoneEdit

Functions with left inverses are always injections. That is, given <math>f : X \to Y,</math> if there is a function <math>g : Y \to X</math> such that for every <math>x \in X</math>, <math>g(f(x)) = x</math>, then <math>f</math> is injective. In this case, <math>g</math> is called a retraction of <math>f.</math> Conversely, <math>f</math> is called a section of <math>g.</math>

Conversely, every injection <math>f</math> with a non-empty domain has a left inverse <math>g</math>. It can be defined by choosing an element <math>a</math> in the domain of <math>f</math> and setting <math>g(y)</math> to the unique element of the pre-image <math>f^{-1}[y]</math> (if it is non-empty) or to <math>a</math> (otherwise).Template:Refn

The left inverse <math>g</math> is not necessarily an inverse of <math>f,</math> because the composition in the other order, <math>f \circ g,</math> may differ from the identity on <math>Y.</math> In other words, an injective function can be "reversed" by a left inverse, but is not necessarily invertible, which requires that the function is bijective.

Injections may be made invertibleEdit

In fact, to turn an injective function <math>f : X \to Y</math> into a bijective (hence invertible) function, it suffices to replace its codomain <math>Y</math> by its actual image <math>J = f(X).</math> That is, let <math>g : X \to J</math> such that <math>g(x) = f(x)</math> for all <math>x \in X</math>; then <math>g</math> is bijective. Indeed, <math>f</math> can be factored as <math>\operatorname{In}_{J,Y} \circ g,</math> where <math>\operatorname{In}_{J,Y}</math> is the inclusion function from <math>J</math> into <math>Y.</math>

More generally, injective partial functions are called partial bijections.

Other propertiesEdit

Template:See also

File:Injective composition2.svg

The composition of two injective functions is injective.

If <math>f</math> and <math>g</math> are both injective then <math>f \circ g</math> is injective.
If <math>g \circ f</math> is injective, then <math>f</math> is injective (but <math>g</math> need not be).
<math>f : X \to Y</math> is injective if and only if, given any functions <math>g,</math> <math>h : W \to X</math> whenever <math>f \circ g = f \circ h,</math> then <math>g = h.</math> In other words, injective functions are precisely the monomorphisms in the category Set of sets.
If <math>f : X \to Y</math> is injective and <math>A</math> is a subset of <math>X,</math> then <math>f^{-1}(f(A)) = A.</math> Thus, <math>A</math> can be recovered from its image <math>f(A).</math>
If <math>f : X \to Y</math> is injective and <math>A</math> and <math>B</math> are both subsets of <math>X,</math> then <math>f(A \cap B) = f(A) \cap f(B).</math>
Every function <math>h : W \to Y</math> can be decomposed as <math>h = f \circ g</math> for a suitable injection <math>f</math> and surjection <math>g.</math> This decomposition is unique up to isomorphism, and <math>f</math> may be thought of as the inclusion function of the range <math>h(W)</math> of <math>h</math> as a subset of the codomain <math>Y</math> of <math>h.</math>
If <math>f : X \to Y</math> is an injective function, then <math>Y</math> has at least as many elements as <math>X,</math> in the sense of cardinal numbers. In particular, if, in addition, there is an injection from <math>Y</math> to <math>X,</math> then <math>X</math> and <math>Y</math> have the same cardinal number. (This is known as the Cantor–Bernstein–Schroeder theorem.)
If both <math>X</math> and <math>Y</math> are finite with the same number of elements, then <math>f : X \to Y</math> is injective if and only if <math>f</math> is surjective (in which case <math>f</math> is bijective).
An injective function which is a homomorphism between two algebraic structures is an embedding.
Unlike surjectivity, which is a relation between the graph of a function and its codomain, injectivity is a property of the graph of the function alone; that is, whether a function <math>f</math> is injective can be decided by only considering the graph (and not the codomain) of <math>f.</math>

Proving that functions are injectiveEdit

A proof that a function <math>f</math> is injective depends on how the function is presented and what properties the function holds. For functions that are given by some formula there is a basic idea. We use the definition of injectivity, namely that if <math>f(x) = f(y),</math> then <math>x = y.</math><ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

Here is an example: <math display="block">f(x) = 2 x + 3</math>

Proof: Let <math>f : X \to Y.</math> Suppose <math>f(x) = f(y).</math> So <math>2 x + 3 = 2 y + 3</math> implies <math>2 x = 2 y,</math> which implies <math>x = y.</math> Therefore, it follows from the definition that <math>f</math> is injective.

There are multiple other methods of proving that a function is injective. For example, in calculus if <math>f</math> is a differentiable function defined on some interval, then it is sufficient to show that the derivative is always positive or always negative on that interval. In linear algebra, if <math>f</math> is a linear transformation it is sufficient to show that the kernel of <math>f</math> contains only the zero vector. If <math>f</math> is a function with finite domain it is sufficient to look through the list of images of each domain element and check that no image occurs twice on the list.

A graphical approach for a real-valued function <math>f</math> of a real variable <math>x</math> is the horizontal line test. If every horizontal line intersects the curve of <math>f(x)</math> in at most one point, then <math>f</math> is injective or one-to-one.