Function Types

Surjection

When not all elements in the codomain are mapped to by the domain, we say the function is onto or surjective.

Let $f:A\to B$, then $f$ is surjective if and only if $\forall b\in B,\exists a\in A$ such that $f(a)=b$.

Injection

When no two elements in the domain map to the same element in the codomain, we say the function is one-to-one or injective.

Let $f:A\to B$, then $f$ is injective if and only if $\forall a_1,a_2\in A,f(a_1)=f(a_2)\Rightarrow a_1=a_2$. Conversely, if $a_1\ne a_2$, then $f(a_1)\ne f(a_2)$.

Bijection

A function that is both injective and surjective is called a bijection.

Let $f:A\to B$, then $f$ is a bijection if and only if $f$ is both injective and surjective.

Examples

Question

Determine if each function is injective, surjective, or bijective.

1. $f:\mathbb{Z}\to \mathbb{Z}$ defined by $f(n)=3n$.

Answer

$f$ is not surjective because the range is only the set of integer multiples of 3, but it is injective because no two integers map to the same integer multiple of 3.

2. $g:\{1,2,3\}\to \{a,b,c\}$ defined by $g(1)=c,g(2)=a$ and $g(3)=a$.

Answer

$g$ is not injective because $g(2)$ and $g(3)$ are the same element of the codomain. This is okay since each element in the domain still has only one output. It is also not surjective because not all elements in the codomain are mapped to by the domain.

3. $h:\{1,2,3\}\to \{a,b,c\}$ defined by $h(1)=a,h(2)=b$ and $h(3)=c$.

Answer

$h$ is a bijection because it is both injective and surjective. No two elements in the domain map to the same element in the codomain and every element in the codomain is mapped to by the domain.