criterion of surjectivity

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

$B\setminus f(X)\subseteq f(A\setminus X)\mathit{\hspace{1em}}\forall X\subseteq A.$ (1)

Proof.  $1^{\underset{¯}{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\setminus 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\setminus X$  and thus  $y=f(x)\in f(A\setminus X)$.  One can conclude that  $B\setminus f(X)\subseteq f(A\setminus X)$  for all  $X\subseteq A$.

$2^{\underset{¯}{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\setminus f(X)$, and by (1), $y\in f(A\setminus X)$.  This means that there exists an element $x$ of  $A\setminus 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
Canonical name	CriterionOfSurjectivity
Date of creation	2013-03-22 18:04:56
Last modified on	2013-03-22 18:04:56
Owner	pahio (2872)
Last modified by	pahio (2872)
Numerical id	4
Author	pahio (2872)
Entry type	Theorem
Classification	msc 03-00
Synonym	surjectivity criterion
Related topic	Function
Related topic	Image
Related topic	Subset