next up previous contents
Next: Bijections Up: Mappings Previous: Injections   Contents

Surjections

Definition 5.3.1   The function $ f \colon A \mapsto B$ is surjective (or onto) if each $ b \in B$ has at least one preimage $ a \in A$.

$\displaystyle \forall y \in B, \; \exists \; x \in A , \; y=f(x).$    

The diagram in Figure 4(a) determines a surjection and the diagram in Figure 4(b) determines a non surjective mapping.

Figure 4: Surjection or not.
\begin{figure}
\centering
\mbox{\subfigure[a surjection]{\epsfig{file=Surject...
...t a surjection]{\epsfig{file=NotSurjection.eps, height=4cm}}
}
\end{figure}

Example 5.3.2   Let $ f: \mathbb{R}\longrightarrow \mathbb{R}$ such that $ f(x)=4x-7$. Take any real number $ y$ (in the range), and look for a pre-image by $ f$. We have:

$\displaystyle f(x)$ $\displaystyle y$    
$\displaystyle 4x-7$ $\displaystyle =y$    
$\displaystyle 4x$ $\displaystyle = y+7$    
$\displaystyle x$ $\displaystyle = \frac 14 (y+7).$    

The real number $ (y+7)/4$ is a pre-image of $ y$ by $ f$.

Example 5.3.3   The mapping $ f: \; \mathbb{R}\longrightarrow \mathbb{R}$ such that $ f(x)=x^2$ is not surjective, because a negative real number has no pre-image by $ f$.

Proposition 5.3.4   Let $ A$,$ B$,$ C$ be three sets and let $ f:A \rightarrow B$ and $ g: A \rightarrow C$ be two mappings. If $ f$ and $ g$ are surjective, then $ gof$ is an surjection.

Proof. Let $ z$ be any element in $ C$. As $ g$ is a surjection, there exists at least one element $ y$ in $ B$ such that $ z=g(y)$. As $ f$ is a surjection, this element $ y \in B$ has at least one pre-image $ x \in A$, and this element is a pre-image of $ z$ by $ gof$. This shows that every element of $ C$ has at least one pre-image in $ A$ by $ gof$, i.e. that $ gof$ is surjective. $ \qedsymbol$

Proposition 5.3.5   Let $ A$,$ B$,$ C$ be three sets and let $ f:A \rightarrow B$ and $ g: A \rightarrow C$ be two mappings. If $ gof$ is a surjection, then $ g$ is a surjection.

Proof. Let $ z$ be any element in $ C$. As $ gof$ is surjective, there exists at least one element $ x \in A$ such that $ z=(gof)(x)=g(f(x)$. Thus $ f(x)$ is a pre-image of $ z$ by $ g$. This shows that every element of $ C$ has a pre-image by $ g$, i.e. $ g$ is surjective. $ \qedsymbol$


next up previous contents
Next: Bijections Up: Mappings Previous: Injections   Contents
root 2002-06-10