# Surjective function

A surjective function; X is the definition set and Y the target set.

A surjective function is a mathematical function that takes each element of the target set at least once as a function value. That is, each element of the target set has at least one archetype . A function is always surjective with regard to its number of images .

A surjective function is also known as surjection . If it is also injective , it is called bijective . In the language of relations one speaks of right total functions.

## definition

Let there be and sets, as well as a mapping. ${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle f \ colon X \ to Y}$

The mapping is called surjective if there is (at least) one from with for each of them . Such a map is also listed as follows: . ${\ displaystyle f}$${\ displaystyle y}$${\ displaystyle Y}$${\ displaystyle x}$${\ displaystyle X}$${\ displaystyle f (x) = y}$${\ displaystyle f \ colon X \ twoheadrightarrow Y}$

Formal: (see existential and universal quantifier ). ${\ displaystyle \ forall y \ in Y \ \ exists x \ in X \ colon f (x) = y}$

## Examples and counterexamples

• The empty function in a one-element set is probably the simplest example of a nonsurjective function.${\ displaystyle \ emptyset \ to \ {\ bullet \}}$
• The function with is surjective, because there is a prototype for every real number . From the equation one obtains the equation by means of equivalence conversion with which a prototype can be calculated for each .${\ displaystyle f \ colon \ mathbb {R} \ to \ mathbb {R}}$${\ displaystyle f (x) = 2x + 1}$ ${\ displaystyle y}$${\ displaystyle y = 2x + 1}$${\ displaystyle x = (y-1) / 2,}$${\ displaystyle y}$${\ displaystyle x}$
• The sine function is surjective. Each horizontal line with cuts the graph of the sine function at least once (even indefinitely).${\ displaystyle \ sin \ colon \ mathbb {R} \ to [-1,1]}$${\ displaystyle y = c}$${\ displaystyle -1 \ leq c \ leq 1}$
• However, the sine function is not surjective, since z. B. the straight line has no intersection with the graph, so the value 2 is not assumed as a function value.${\ displaystyle \ sin \ colon \ mathbb {R} \ to \ mathbb {R}}$${\ displaystyle y = 2}$
• ${\ displaystyle \ mathbb {C}}$denote the set of complex numbers .
${\ displaystyle f_ {1} \ colon \ mathbb {R} \ to \ mathbb {R}, \, x \ mapsto x ^ {2}}$is not surjective, since z. B. has no archetype.${\ displaystyle -1}$
${\ displaystyle f_ {2} \ colon \ mathbb {C} \ to \ mathbb {C}, \, x \ mapsto x ^ {2}}$ is surjective.

## properties

• Note that the surjectivity of a function does not only depend on the function graph but also on the target set (in contrast to injectivity , the presence of which can be seen on the function graph).${\ displaystyle f \ colon A \ to B}$ ${\ displaystyle \ {(x, f (x)) \ mid x \ in A \},}$${\ displaystyle B}$
• A function is surjective if and only if holds for all .${\ displaystyle f \ colon A \ to B}$${\ displaystyle f \ left (f ^ {- 1} (Y) \ right) = Y}$${\ displaystyle Y \ subset B}$
• If the functions and are surjective, then this also applies to the composition (concatenation)${\ displaystyle f \ colon A \ to B}$${\ displaystyle g \ colon B \ to C}$${\ displaystyle g \ circ f \ colon A \ to C.}$
• It follows from the surjectivity of that is surjective.${\ displaystyle g \ circ f}$${\ displaystyle g}$
• A function is then exactly onto, when a right inverse , has thus a function with (where the identity mapping to hereinafter). This statement is equivalent to the axiom of choice in set theory.${\ displaystyle f \ colon A \ to B}$${\ displaystyle f}$${\ displaystyle g \ colon B \ to A}$${\ displaystyle f \ circ g = \ operatorname {id} _ {B}}$${\ displaystyle \ operatorname {id} _ {B}}$${\ displaystyle B}$
• A function is exactly then surjective if rechtskürzbar is, so if for any functions with already follows. (This property motivates the term epimorphism used in category theory .)${\ displaystyle f \ colon A \ to B}$${\ displaystyle f}$ ${\ displaystyle g, h \ colon B \ to C}$${\ displaystyle g \ circ f = h \ circ f}$${\ displaystyle g = h}$
• Any function can be represented as a concatenation , with the function being surjective and injective.${\ displaystyle f \ colon A \ to B}$${\ displaystyle f = h \ circ g}$${\ displaystyle C: = \ {f ^ {- 1} (y) \ mid y \ in \ operatorname {im} f \}}$${\ displaystyle g \ colon A \ to C, \; x \ mapsto f ^ {- 1} (f (x))}$${\ displaystyle h \ colon C \ to B, \; f ^ {- 1} (y) \ mapsto y}$

## Cardinalities of sets

For a finite set , the cardinality is simply the number of elements of . If now is a surjective function between finite sets, then at most there can be as many elements as , so it is true${\ displaystyle A}$ ${\ displaystyle | A |}$${\ displaystyle A}$${\ displaystyle f \ colon A \ to B}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle | B | \ leq | A |.}$

For infinite quantities , the size comparison of thicknesses is defined with the help of the term injection , but here, too, the following applies: If surjective, then the thickness of is not greater than the thickness of here too${\ displaystyle f \ colon A \ to B}$${\ displaystyle B}$${\ displaystyle A,}$${\ displaystyle | B | \ leq | A |.}$