# Surjection

(Redirected from Surjective)
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 [ilmath]f:X\rightarrow Y[/ilmath], we say [ilmath]f[/ilmath] 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

The composition of surjective functions is surjective

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

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

Let [ilmath]z\in Z[/ilmath] be given
Then [ilmath]\exists y\in Y[/ilmath] such that [ilmath]g(y)=z[/ilmath]
Of course also [ilmath]\exists x\in X[/ilmath] such that [ilmath]f(x)=y[/ilmath]
We now know [ilmath]\exists x\in X[/ilmath] with [ilmath]f(x)=y[/ilmath] and [ilmath]g(y)=g(f(x))=h(x)=z[/ilmath]
Thus it is shown that:
• [ilmath]\forall z\in Z\exists x\in X[h(x)=z][/ilmath]
as required.