Difference between revisions of "Surjection"

Revision as of 17:19, 10 May 2015

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$

[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.^[1]

@@ Line 6: / Line 6: @@
 * Equivalently <math>\forall y\in Y</math> the set <math>f^{-1}(y)</math> is non-empty. That is <math>f^{-1}(y)\ne\emptyset</math>
 ==Theorems==
-===Obvious results===
 {{Begin Theorem}}
-====The composition of surjective functions is surjective====
+The composition of surjective functions is surjective
 {{Begin Proof}}
 Let {{M|f:X\rightarrow Y}} and {{M|g:Y\rightarrow Z}} be surjective maps, then their composition, {{M|1=g\circ f=h:X\rightarrow Z}} is surjective.