Injectivity and Surjectivity

Definitions §

Injectivity §

For a function $f:S⟶T$, $f$ is injective iff $\forall s,s\prime \in S$, $fs=fs\prime ⟹s=s\prime$. More simply, if there is only one element of the source set that produces a given output in the target set, then the function is an injection.

A#proof of injectivity derives that $x=x\prime$ from $fx=fx\prime$. To prove that a function is not injective, it is sufficient to provide a single counter-example.

Surjectivity §

For a function $f:S⟶T$, $f$ is surjective iff $\forall t\in T$, there exists $s\in S$ with $fs=t$. More simply, if every element of the target set can be produced with an element of the source set, then the function is a surjection.

A#proof of surjectivity derives an expression for $x\in S$ from the equation $fn=x$, ($n\in T$). As with injectivity, providing a single counter-example is a sufficient proof that a function is not surjective.

Bijectivity §

A function that is both injective and surjective is said to be bijective, or a biject.

Exercise Sheet §