Difference between revisions of "Surjection"
From Maths
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> | ||
| − | {{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}} | ||
Revision as of 17:07, 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]
Contents
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
Obvious results
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
- ↑ Alec Teal's (own) work
