Difference between revisions of "Surjection"

From Maths
Jump to: navigation, search
(Created page with "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>")
 
m (Linking to surjection's problem, making note to apply to bijection - finishing proof that really should be in its own page.)
 
(6 intermediate revisions by the same user not shown)
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>
+
{{Requires work|grade=A*|msg=See [[Injection]]'s requires-work box [https://wiki.unifiedmathematics.com/index.php?title=Injection&oldid=9337 permalink] [[User:Alec|Alec]] ([[User talk:Alec|talk]]) 21:56, 8 May 2018 (UTC)
 +
 
 +
Also:
 +
* Factor out composition theorem into own page. [[User:Alec|Alec]] ([[User talk:Alec|talk]]) 21:56, 8 May 2018 (UTC)
 +
* Apply this to the [[Bijection]] page too [[User:Alec|Alec]] ([[User talk:Alec|talk]]) 21:56, 8 May 2018 (UTC)}}
 +
 
 +
:: 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>
 +
__TOC__
 +
==Definition==
 +
{{:Surjection/Definition}}
 +
 
 +
==Theorems==
 +
{{Begin Inline Theorem}}<!-- TODO: MOVE TO OWN SUBPAGE ! -->
 +
The composition of surjective functions is surjective
 +
{{Begin Inline 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}}
 +
 
 +
: Thus it is shown that:
 +
:* {{M|1=\forall z\in Z\exists x\in X[h(x)=z]}}
 +
: as required.<ref>[[User:Alec|Alec's]] work - the proof speaks for itself</ref>
 +
{{End Proof}}
 +
{{End Theorem}}
 +
 
 +
==See also==
 +
* [[Injection]]
 +
* [[Bijection]]
 +
* [[Function]]
 +
 
 +
==References==
 +
<references/>
 +
 
 +
{{Definition|Set Theory}}

Latest revision as of 21:56, 8 May 2018

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 [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

Given a function [ilmath]f:X\rightarrow Y[/ilmath], we say [ilmath]f[/ilmath] 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

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 [math]\forall z\in Z\exists x\in X[h(x)=z][/math]


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


See also

References

  1. Alec's work - the proof speaks for itself