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)$.
Screen%20Shot%202014-06-05%20at%2010.00.56%20AM.png

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).

Screen%20Shot%202014-06-05%20at%209.46.40%20AM.png

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$.
Screen%20Shot%202014-06-05%20at%2010.02.25%20AM%281%29.png

Bijections (One-to-one Correspondence Functions)

Screen%20Shot%202014-06-05%20at%2010.04.15%20AM.png
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):

Screen%20Shot%202014-06-05%20at%2010.06.17%20AM.png
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License