Injections, Surjections, and Bijections

Injections, Surjections, and Bijections

We will now look at some formal definitions for injections, surjections, and bijections, but first let us look at the definition of a function:

 Definition: A function $f$ is a rule that assigns every element in some set A to a corresponding element in some set B. Set A is known as the domain, and set B is known as the codomain.

Injections (One-to-one Functions)

 Definition: A function $f: A \to B$ is said to be an injective function (or one-to-one) if whenever $x, y \in A$ satisfy x ≠ y, then $f(x) ≠ f(y)$.

One way to tell if a function is injective (or one-to-one) is if the function can pass the horizontal line test. If there is a horizontal line $y = a$ that intersects two distinct points (or more) on the function, say $f(x) = f(y) = a$, then there exists two sets of coordinates $(x, a)$ and $(y, a)$ for which the function maps both x and y to a (and is not injective).

Surjections (Onto Functions)

 Definition: A function $f: A \to B$ is said to be a surjective function (or onto) if for each $y \in B$ there exists an element $x \in A$ where $f(x) = y$.

Bijections (One-to-one Correspondence Functions)

 Definition: A function $f: A \to B$ is said to be a bijective function if $f$ is both injective and surjective.

Neither Injective or Surjective

Of course, a function $f$ does not need to be injective or surjective (and would obviously not be bijective either):