# Surjective function

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 |.}$ 