Surjection

Grade: A*

This page requires some work to be carried out

Some aspect of this page is incomplete and work is required to finish it
The message provided is:

See Injection's requires-work box permalink Alec (talk) 21:56, 8 May 2018 (UTC)

Also:

• Factor out composition theorem into own page. Alec (talk) 21:56, 8 May 2018 (UTC)
• Apply this to the Bijection page too Alec (talk) 21:56, 8 May 2018 (UTC)

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

Definition

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$

Thus it is shown that:

• $\forall z\in Z\exists x\in X[h(x)=z]$

as required.

See also

• Injection
• Bijection
• Function