Difference between revisions of "Surjection"

Revision as of 17:07, 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 1: / Line 1: @@
 Surjective is onto - for <math>f:A\rightarrow B</math> every element of <math>B</math> is mapped onto from at least one thing in <math>A</math>
-{{Definition}}
+==Definition==
+Given a [[Function|function]] {{M|f:X\rightarrow Y}}, we say {{M|f}} is ''surjective'' if:
+* <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==
+===Obvious results===
+{{Begin Theorem}}
+====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.
+: We wish to show that <math>\forall z\in Z\exists x\in X[h(x)=z]</math>
+: Let {{M|z\in Z}} be given
+:: Then {{M|\exists y\in Y}} such that {{M|1=g(y)=z}}
+:: Of course also {{M|\exists x\in X}} such that {{M|1=f(x)=y}}
+:: We now know {{M|\exists x\in X}} with {{M|1=f(x)=y}} and {{M|1=g(y)=g(f(x))=h(x)=z}}
+: We have shown {{M|1=\forall z\in Z\exists x\in X[h(x)=z]}} as required.<ref>Alec Teal's (own) work</ref>
+{{End Proof}}
+{{End Theorem}}
+==See also==
+* [[Injection]]
+* [[Bijection]]
+* [[Function]]
+==References==
+<references/>
+{{Definition|Set Theory}}