Surjective function

Surjectivity ( surjective ) or right- totality (right totally, in the language of relations) is a property of a mathematical function. It means that each element of the target set at least once accepted as the function value, so it has at least one preimage. A function is in terms of their image set always surjective. A surjective function is also called a surjection.

Definition

Let and quantities, as well as a picture.

Is called surjective if for all of at least one exists with.

Formal:

Graphical illustrations

Graphs of three surjective functions between real intervals.

A special case of surjectivity: The target quantity (Y) consists of only one element.

Examples and counter-examples

• The function is surjective, because for every real number, there is a pre-image. From the equation is the equation that is obtained by equivalence transformation which can be calculated for each one archetype.

• The sine function is surjective. Each horizontal line intersects with the graph of the sine function at least once ( even indefinitely ).

• However, the sine function is not surjective, since, for example, the straight line has no intersection with the graph, the value is 2, therefore, not be accepted as the function value.

• Denotes the set of complex numbers.

Properties

• Note that the surjectivity of a function not only of function graphs but also on the target amount depends (as opposed to injectivity, which can be read on function graphs ).

• A function is surjective if and only if for all.

• The functions and onto, then this is also true for the composition (concatenation)

• From the surjectivity of follows that is surjective.

• A function is surjective if and only if a right inverse has, therefore, a function with (the identity map referred to ). This statement is equivalent to the axiom of choice in set theory.

• A function is surjective if and only if is rechtskürzbar, so it follows for arbitrary functions with already. (This property motivates the term used epimorphism in the category theory. )

• Any function can be represented as concatenation, which is surjective and injective. has this image as a set of target amount and agrees otherwise in accordance with ( has the same function graphs ).

Widths of sets

For a finite set, the cardinality is simply the number of elements. Is now a surjective function between finite sets, then at most as many elements as have, it is therefore

For infinite sets of size comparison of widths is indeed defined using the concept of injection, but again: is surjective, then the cardinality of less than or equal to the cardinality is written by also as