Surjective function

The term surjective and the related terms injective and bijective were introduced by Nicolas Bourbaki,[3][4] a group of mainly French 20th-century mathematicians who, under this pseudonym, wrote a series of books presenting an exposition of modern advanced mathematics, beginning in 1935.

The French word sur means over or above, and relates to the fact that the image of the domain of a surjective function completely covers the function's codomain.

Any function induces a surjection by restricting its codomain to the image of its domain.

Symbolically, A function is bijective if and only if it is both surjective and injective.

Unlike injectivity, surjectivity cannot be read off of the graph of the function alone.

In other words, g is a right inverse of f if the composition f o g of g and f in that order is the identity function on the domain Y of g. The function g need not be a complete inverse of f because the composition in the other order, g o f, may not be the identity function on the domain X of f. In other words, f can undo or "reverse" g, but cannot necessarily be reversed by it.

The proposition that every surjective function has a right inverse is equivalent to the axiom of choice.

Specifically, surjective functions are precisely the epimorphisms in the category of sets.

The prefix epi is derived from the Greek preposition ἐπί meaning over, above, on.

Any morphism with a right inverse is an epimorphism, but the converse is not true in general.

A surjective function with domain X and codomain Y is then a binary relation between X and Y that is right-unique and both left-total and right-total.

(The proof appeals to the axiom of choice to show that a function g : Y → X satisfying f(g(y)) = y for all y in Y exists.

g is easily seen to be injective, thus the formal definition of |Y| ≤ |X| is satisfied.)

Specifically, if both X and Y are finite with the same number of elements, then f : X → Y is surjective if and only if f is injective.

Using the axiom of choice one can show that X ≤* Y and Y ≤* X together imply that |Y| = |X|, a variant of the Schröder–Bernstein theorem.

Any function induces a surjection by restricting its codomain to its range.

Any surjective function induces a bijection defined on a quotient of its domain by collapsing all arguments mapping to a given fixed image.

Equivalently, A/~ is the set of all preimages under f. Let P(~) : A → A/~ be the projection map which sends each x in A to its equivalence class [x]~, and let fP : A/~ → B be the well-defined function given by fP([x]~) = f(x).

The cardinality of this set is one of the twelve aspects of Rota's Twelvefold way, and is given by

A non-surjective function from domain X to codomain Y . The smaller yellow oval inside Y is the image (also called range ) of f . This function is not surjective, because the image does not fill the whole codomain. In other words, Y is colored in a two-step process: First, for every x in X , the point f ( x ) is colored yellow; Second, all the rest of the points in Y , that are not yellow, are colored blue. The function f would be surjective only if there were no blue points.