Injective function
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements of its codomain.^{[1]} In other words, every element of the function's codomain is the image of at most one element of its domain.^{[2]} The term one-to-one function must not be confused with one-to-one correspondence 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.
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)
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 injective homomorphism is also called a monomorphism. However, in the more general context of category theory, the definition of a monomorphism differs from that of an injective homomorphism.^{[3]} This is thus a theorem that they are equivalent for algebraic structures; see Homomorphism § Monomorphism for more details.
A function f that is not injective is sometimes called many-to-one.^{[2]}
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,
- ^{[4]}^{[5]}
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, then the function X → Y is always injective.
- The function f : R → R defined by f(x) = 2x + 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.^{[2]}
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.^{[6]}
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 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 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 definition of injectivity, namely that if f(x) = f(y), then x = y.^{[7]}
Here is an example:
- f = 2x + 3
Proof: Let f : X → Y. Suppose f(x) = f(y). So 2x + 3 = 2y + 3 ⇒ 2x = 2y ⇒ 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.
A graphical approach for a real-valued function f of a real variable x is the horizontal line test. If every horizontal line intersects the curve of f(x) in at most one point, then f is injective or one-to-one.
See alsoEdit
NotesEdit
- ^ "The Definitive Glossary of Higher Mathematical Jargon — One-to-One". Math Vault. 2019-08-01. Retrieved 2019-12-07.
- ^ ^{a} ^{b} ^{c} "Injective, Surjective and Bijective". www.mathsisfun.com. Retrieved 2019-12-07.
- ^ "Section 7.3 (00V5): Injective and surjective maps of presheaves—The Stacks project". stacks.math.columbia.edu. Retrieved 2019-12-07.
- ^ "Bijection, Injection, And Surjection | Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-12-07.
- ^ Farlow, S. J. "Injections, Surjections, and Bijections" (PDF). math.umaine.edu. Retrieved 2019-12-06.
- ^ 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 injective in Wiktionary, the free dictionary. |