Difference between revisions of "Surjection"

Revision as of 17:42, 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 2: / Line 2: @@
 ==Definition==
-Given a [[Function|function]] {{M|f:X\rightarrow Y}}, we say {{M|f}} is ''surjective'' if:
+{{:Surjection/Definition}}
-* <math>\forall y\in Y\exists x\in X[f(x)=y]</math>
-* 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==