# criterion of surjectivity

For surjectivity of a mapping$f\!:\,A\to B$,  it’s necessary and sufficient that

 $\displaystyle B\!\smallsetminus\!f(X)\,\subseteq\,f(A\!\smallsetminus\!X)\quad% \forall\,X\subseteq A.$ (1)

Proof.$1^{\underline{o}}$.  Suppose that  $f\!:\,A\to B$  is surjective.  Let $X$ be an arbitrary subset of $A$ and $y$ any element of the set $B\!\smallsetminus\!f(X)$.  By the surjectivity, there is an $x$ in $A$ such that  $f(x)=y$, and since  $y\notin f(X)$,  the element $x$ is not in $X$, i.e.  $x\in A\!\smallsetminus\!X$  and thus  $y=f(x)\in f(A\!\smallsetminus\!X)$.  One can conclude that  $B\!\smallsetminus\!f(X)\,\subseteq\,f(A\!\smallsetminus\!X)$  for all  $X\subseteq A$.

$2^{\underline{o}}$.  Conversely, suppose the condition (1).  Let again $X$ be an arbitrary subset of $A$ and $y$ any element of $B$.  We have two possibilities:
a) $y\notin f(X)$; then  $y\in B\!\smallsetminus\!f(X)$, and by (1), $y\in f(A\!\smallsetminus\!X)$.  This means that there exists an element $x$ of  $A\!\smallsetminus\!X\subseteq A$  such that  $f(x)=y$.
b) $y\in f(X)$; then there exists an $x\in X\subseteq A$  such that  $f(x)=y$.
The both cases show the surjectivity of $f$.

Title criterion of surjectivity CriterionOfSurjectivity 2013-03-22 18:04:56 2013-03-22 18:04:56 pahio (2872) pahio (2872) 4 pahio (2872) Theorem msc 03-00 surjectivity criterion Function Image Subset