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

Graphic illustrations

• 

  The principle of surjectivity: every point in the target set (Y) is hit at least once.

• 

  Graphs of three surjective functions between real intervals

• 

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

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

literature

• OA Ivanova: Surjection . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).

Web links

Wikibooks: Evidence archive: set theory  - learning and teaching materials