Difference between revisions of "Surjection"

From Maths
Jump to: navigation, search
m
m
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>
 
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>
  
{{:Surjection/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==
 
==Theorems==
 
{{Begin Theorem}}
 
{{Begin Theorem}}

Revision as of 17:40, 10 May 2015

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]
We have shown [ilmath]\forall z\in Z\exists x\in X[h(x)=z][/ilmath] as required.[1]


See also

References

  1. Alec Teal's (own) work