Surjection

Surjective is onto - for $$f:A\rightarrow B$$ every element of $$B$$ is mapped onto from at least one thing in $$A$$

Given a function $f:X\rightarrow Y$, we say $f$ is surjective if:

• $$\forall y\in Y\exists x\in X[f(x)=y]$$
• Equivalently $$\forall y\in Y$$ the set $$f^{-1}(y)$$ is non-empty. That is $$f^{-1}(y)\ne\emptyset$$

Theorems

[Expand]

The composition of surjective functions is surjective

---

Let $f:X\rightarrow Y$ and $g:Y\rightarrow Z$ be surjective maps, then their composition, $g\circ f=h:X\rightarrow Z$ is surjective.

We wish to show that $$\forall z\in Z\exists x\in X[h(x)=z]$$

Let $z\in Z$ be given

Then $\exists y\in Y$ such that $g(y)=z$

Of course also $\exists x\in X$ such that $f(x)=y$

We now know $\exists x\in X$ with $f(x)=y$ and $g(y)=g(f(x))=h(x)=z$

We have shown $\forall z\in Z\exists x\in X[h(x)=z]$ as required.

See also

• Injection
• Bijection
• Function