# Injective function

In mathematics, an **injective function** or **injection** or **one-to-one 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 the image of *at most* one element of its domain. The term *one-to-one function* must not be confused with *one-to-one correspondence* (a.k.a. bijective function), which uniquely maps all elements in both domain and codomain to each other (see figures).

An injective non-surjective function (injection, not a bijection)

An injective surjective function (bijection)

A non-injective surjective function (surjection, not a bijection)

A non-injective non-surjective function (also not a bijection)

Occasionally, an injective function from *X* to *Y* is denoted *f* : *X* ↣ *Y*, using an arrow with a barbed tail (U+21A3 ↣ RIGHTWARDS ARROW WITH TAIL).^{[1]} The set of injective functions from *X* to *Y* may be denoted *Y*^{X} using a notation derived from that used for falling factorial powers, since if *X* and *Y* are finite sets with respectively *m* and *n* elements, the number of injections from *X* to *Y* is *n*^{m} (see the twelvefold way).

A function *f* that is not injective is sometimes called many-to-one. However, the injective terminology is also sometimes used to mean "single-valued", i.e., each argument is mapped to at most one value.

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

## Contents

## DefinitionEdit

Let *f* be a function whose domain is a set *X*. The function *f* is said to be **injective** provided that for all *a* and *b* in *X*, whenever *f*(*a*) = *f*(*b*), then *a* = *b*; that is, *f*(*a*) = *f*(*b*) implies *a* = *b*. Equivalently, if *a* ≠ *b*, then *f*(*a*) ≠ *f*(*b*).

Symbolically,

which is logically equivalent to the contrapositive,

## ExamplesEdit

- For any set
*X*and any subset*S*of*X*the inclusion map*S*→*X*(which sends any element*s*of*S*to itself) is injective. In particular the identity function*X*→*X*is always injective (and in fact bijective). - If the domain
*X*= ∅ or*X*has only one element, the function*X*→*Y*is always injective. - The function
*f*:**R**→**R**defined by*f*(*x*) = 2*x*+ 1 is injective. - The function
*g*:**R**→**R**defined by*g*(*x*) =*x*^{2}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 :
**R**→**R**defined by exp(*x*) =*e*^{x}is injective (but not surjective as no real 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*) =*x*^{n}−*x*is not injective, since, for example,*g*(0) =*g*(1) = 0.

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. This principle is referred to as the *horizontal line test*.

## Injections can be undoneEdit

Functions with left inverses are always injections. That is, given *f* : *X* → *Y*, if there is a function *g* : *Y* → *X* such that, for every *x* ∈ *X*,

*g*(*f*(*x*)) =*x*(*f*can be undone by*g*)

then *f* is injective. In this case, *g* is called a retraction of *f*. Conversely, *f* is called a section of *g*.

Conversely, every injection *f* with non-empty domain has a left inverse *g*, which can be defined by fixing an element *a* in the domain of *f* so that *g*(*x*) equals the unique preimage of *x* under *f* if it exists and *g*(*x*) = *a* otherwise.^{[2]}

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

## Injections may be made invertibleEdit

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,Y} ∘ *g*, where incl_{J,Y} is the inclusion function from *J* into *Y*.

More generally, injective partial functions are called partial bijections.

## Other propertiesEdit

- If
*f*and*g*are both injective, then*f*∘*g*is injective.

- If
*g*∘*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*∘*g*=*f*∘*h*, then*g*=*h*. In other words, injective functions are precisely the monomorphisms in the category**Set**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*∘*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. In particular, if, in addition, there is an injection from*Y<*to*X*, then*X*and*Y*have the same cardinal number. (This is known as the Cantor–Bernstein–Schroeder theorem.) - 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 (in which case*f*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
*f*is injective can be decided by only considering the graph (and not the codomain) of*f*.

## Proving that functions are injectiveEdit

A proof that a function *f* 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 contrapositive of the definition of injectivity, namely that if *f*(*x*) = *f*(*y*), then *x* = *y*.^{[3]}

Here is an example:

*f*= 2*x*+ 3

Proof: Let *f* : *X* → *Y*. Suppose *f*(*x*) = *f*(*y*). So 2*x* + 3 = 2*y* + 3 ⇒ 2*x* = 2*y* ⇒ *x* = *y*. Therefore, it follows from the definition that *f* is injective.

There are multiple other methods of proving that a function is injective. For example, in calculus if *f* 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 *f* is a linear transformation it is sufficient to show that the kernel of *f* contains only the zero vector. If *f* 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.

## See alsoEdit

## NotesEdit

**^**"Unicode" (PDF). Retrieved 2013-05-11.**^**Unlike the corresponding statement that every surjective function has a right inverse, this does not require the axiom of choice, as the existence of*a*is implied by the non-emptiness of the domain. However, this statement may fail in less conventional mathematics such as constructive mathematics. In constructive mathematics, the inclusion {0,1} →**R**of the two-element set in the reals cannot have a left inverse, as it would violate indecomposability, by giving a retraction of the real line to the set {0,1}.**^**Williams, Peter. "Proving Functions One-to-One". Archived from the original on 4 June 2017.

## ReferencesEdit

- Bartle, Robert G. (1976),
*The Elements of Real Analysis*(2nd ed.), New York: John Wiley & Sons, ISBN 978-0-471-05464-1, p. 17*ff*. - Halmos, Paul R. (1974),
*Naive Set Theory*, New York: Springer, ISBN 978-0-387-90092-6, p. 38*ff*.

## External linksEdit

Wikimedia Commons has media related to .Injectivity |

Look up in Wiktionary, the free dictionary.injective |