The function is injective, or one-to-one, if each element of the codomain is mapped to by at most one element of the domain, or equivalently, if distinct elements of the domain map to distinct elements in the codomain. An injective function is also called an injection. Notationally:
The function is surjective, or onto, if each element of the codomain is mapped to by at least one element of the domain. That is, the image and the codomain of the function are equal. A surjective function is a surjection. Notationally:
The function is bijective if each element of the codomain is mapped to by exactly one element of the domain. That is, the function is both injective and surjective. A bijective function is also called a bijection. That is, combining the definitions of injective and surjective,
In any case, the following holds:
An injective function need not be surjective, and a surjective function need not be injective. The four possible combinations of injective and surjective features are illustrated in the adjacent diagrams.
Injection
A function is injective if each possible element of the codomain is mapped to by at most one argument. Equivalently, a function is injective if it maps distinct arguments to distinct images. An injective function is an injection. The formal definition is the following. The following are some facts related to injections:
A function f : X → Y is injective if and only ifX is empty or f is left-invertible; that is, there is a function g : f → X such that g o f = identity function on X. Here, f is the image of f.
Since every function is surjective when its codomain is restricted to its image, every injection induces a bijection onto its image. More precisely, every injection f : X → Y can be factored as a bijection followed by an inclusion as follows. Let fR : X → f be f with codomain restricted to its image, and let i : f → Y be the inclusion map from f into Y. Then f = i o fR. A dual factorisation is given for surjections below.
The composition of two injections is again an injection, but if g o f is injective, then it can only be concluded that f is injective.
A function is surjective if each possible image is mapped to by at least one argument. In other words, each element in the codomain has non-empty preimage. Equivalently, a function is surjective if its image is equal to its codomain. A surjective function is a surjection. The formal definition is the following. The following are some facts related to surjections:
A function f : X → Y is surjective if and only if it is right-invertible, that is, if and only if there is a function g: Y → X such that f o g = identity function on Y.
By collapsing all arguments mapping to a given fixed image, every surjection induces a bijection defined on a quotient of its domain. More precisely, every surjection f : X → Y can be factored as a non-bijection followed by a bijection as follows. Let X/~ be the equivalence classes of X under the following equivalence relation: x ~ y if and only if f = f. Equivalently, X/~ is the set of all preimages under f. Let P : X → X/~ be the projection map which sends each x in X to its equivalence class~, and let fP : X/~ → Y be the well-defined function given by fP = f. Then f = fP o P. A dual factorisation is given for injections above.
The composition of two surjections is again a surjection, but if g o f is surjective, then it can only be concluded that g is surjective.
Bijection
A function is bijective if it is both injective and surjective. A bijective function is a bijection. A function is bijective if and only if every possible image is mapped to by exactly one argument. This equivalent condition is formally expressed as follow. The following are some facts related to bijections:
A function f : X → Y is bijective if and only if it is invertible, that is, there is a function g: Y → X such that g o f = identity function on X and f o g = identity function on Y. This function maps each image to its unique preimage.
The composition of two bijections is again a bijection, but if g o f is a bijection, then it can only be concluded that f is injective and g is surjective.
The bijections from a set to itself form a group under composition, called the symmetric group.
Cardinality
Suppose that one wants to define what it means for two sets to "have the same number of elements". One way to do this is to say that two sets "have the same number of elements", if and only if all the elements of one set can be paired with the elements of the other, in such a way that each element is paired with exactly one element. Accordingly, one can define two sets to "have the same number of elements"—if there is a bijection between them. In which case, the two sets are said to have the same cardinality. Likewise, one can say that set "has fewer than or the same number of elements" as set, if there is an injection from to ; one can also say that set "has fewer than the number of elements" in set, if there is an injection from to, but not a bijection between and.
Examples
It is important to specify the domain and codomain of each function, since by changing these, functions which appear to be the same may have different properties. ;Injective and surjective ;Injective and non-surjective ;Non-injective and surjective ;Non-injective and non-surjective
Properties
For every function, subset of the domain and subset of the codomain, and. If is injective, then, and if is surjective, then.
For every function, one can define a surjection and an injection. It follows that. This decomposition is unique up to isomorphism.
