Function (mathematics)
Injective, surjective and bijective functions

Let f: X → Y {\displaystyle f:X\to Y} be a function.

The function f is injective (or one-to-one, or is an injection) if f (a) ≠ f (b) for every two different elements a and b of X. Equivalently, f is injective if and only if, for every y ∈ Y, {\displaystyle y\in Y,} the preimage f − 1 (y) {\displaystyle f^{-1}(y)} contains at most one element. An empty function is always injective. If X is not the empty set, then f is injective if and only if there exists a function g: Y → X {\displaystyle g:Y\to X} such that g ∘ f = id X, {\displaystyle g\circ f=\operatorname {id} _{X},} that is, if f has a left inverse. Proof: If f is injective, for defining g, one chooses an element x 0 {\displaystyle x_{0}} in X (which exists as X is supposed to be nonempty), and one defines g by g (y) = x {\displaystyle g(y)=x} if y = f (x) {\displaystyle y=f(x)} and g (y) = x 0 {\displaystyle g(y)=x_{0}} if y ∉ f (X). {\displaystyle y\not \in f(X).} Conversely, if g ∘ f = id X, {\displaystyle g\circ f=\operatorname {id} _{X},} and y = f (x), {\displaystyle y=f(x),} then x = g (y), {\displaystyle x=g(y),} and thus f − 1 (y) = { x }. {\displaystyle f^{-1}(y)=\{x\}.}

The function f is surjective (or onto, or is a surjection) if its range f (X) {\displaystyle f(X)} equals its codomain Y {\displaystyle Y}, that is, if, for each element y {\displaystyle y} of the codomain, there exists some element x {\displaystyle x} of the domain such that f (x) = y {\displaystyle f(x)=y} (in other words, the preimage f − 1 (y) {\displaystyle f^{-1}(y)} of every y ∈ Y {\displaystyle y\in Y} is nonempty). If, as usual in modern mathematics, the axiom of choice is assumed, then f is surjective if and only if there exists a function g: Y → X {\displaystyle g:Y\to X} such that f ∘ g = id Y, {\displaystyle f\circ g=\operatorname {id} _{Y},} that is, if f has a right inverse. The axiom of choice is needed, because, if f is surjective, one defines g by g (y) = x, {\displaystyle g(y)=x,} where x {\displaystyle x} is an arbitrarily chosen element of f − 1 (y). {\displaystyle f^{-1}(y).}

The function f is bijective (or is a bijection or a one-to-one correspondence) if it is both injective and surjective. That is, f is bijective if, for every y ∈ Y, {\displaystyle y\in Y,} the preimage f − 1 (y) {\displaystyle f^{-1}(y)} contains exactly one element. The function f is bijective if and only if it admits an inverse function, that is, a function g: Y → X {\displaystyle g:Y\to X} such that g ∘ f = id X {\displaystyle g\circ f=\operatorname {id} _{X}} and f ∘ g = id Y. {\displaystyle f\circ g=\operatorname {id} _{Y}.} (Contrarily to the case of surjections, this does not require the axiom of choice; the proof is straightforward).

Every function f: X → Y {\displaystyle f:X\to Y} may be factorized as the composition i ∘ s {\displaystyle i\circ s} of a surjection followed by an injection, where s is the canonical surjection of X onto f (X) and i is the canonical injection of f (X) into Y. This is the canonical factorization of f.

"One-to-one" and "onto" are terms that were more common in the older English language literature; "injective", "surjective", and "bijective" were originally coined as French words in the second quarter of the 20th century by the Bourbaki group and imported into English. As a word of caution, "a one-to-one function" is one that is injective, while a "one-to-one correspondence" refers to a bijective function. Also, the statement " f maps X onto Y " differs from " f maps X into B ", in that the former implies that f is surjective, while the latter makes no assertion about the nature of f. In a complicated reasoning, the one letter difference can easily be missed. Due to the confusing nature of this older terminology, these terms have declined in popularity relative to the Bourbakian terms, which have also the advantage of being more symmetrical.
length_constraints:number_words[223], detectable_format:title, keywords:forbidden_words