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

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

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:

$$f(x) y$$

$$4x-7 =y$$

$$4x = y+7$$

$$x = \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$