Surjection
From Maths
Revision as of 21:56, 8 May 2018 by Alec (Talk | contribs) (Linking to surjection's problem, making note to apply to bijection - finishing proof that really should be in its own page.)
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:
The message provided is:
- 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
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]