1.3Functions of Sets

Updated 19 Aug 2026Chapter (PDF)

[1.3.1]Definition(Function, Graph of Function)#

A function $f: A \to B$ is a map between sets in which each element $a \in A$ is mapped to exactly one $f(a) \in B$ . The graph of a function is defined by

\Gamma_f = \{(a, b) \in A \times B : b = f(a)\} = \{(a, f(a)) : a\in A\}.

As notation, note $a \mapsto f(a)$ means a “maps to” $f(a)$ , and

diagrammatically notes $A$ is mapped to $B$ by the function $f$ .

Suppose $f: A \to B$ and $g: B \to C$ . The composition $(g \circ f): A \to C$ can be drawn by a commutative diagram.

[1.3.2]Definition(Commutative Diagram)#

A diagram is said to commute if, when going through any path prescribed by the diagram between two endpoints, the result is the same.

Suppose $f: A \to B, g: B \to C, h: C \to D$ .

Note the diagram is commutative, and accordingly, $h \circ (g \circ f) = (h \circ g) \circ f$ . The associativity of function compositions is trivial and left without proof.

[1.3.3]Definition(Injectivity and Surjectivity)#

A function $f: A \to B$ is:

injective if, for every $a, a' \in A$ such that $a \ne a'$ , it follows that $f(a) \ne f(a')$ . Equivalently, for every $a, a' \in A$ such that $f(a) = f(a')$ , it follows that $a = a'$ .
surjective if, for every $b \in B$ , there exists some $a \in A$ such that $f(a) = b$ . Equivalently, if $\im(f) = B$ .

Injections and surjections are noted by $\hookrightarrow$ and $\twoheadrightarrow$ respectively, a homage to the notation of monomorphisms and epimorphisms (an equivalent categorization in the category of sets, $\Set$ ).

If $f: A \to B$ is both injective and surjective, it is indeed bijective, and accordingly $A$ and $B$ are isomorphic as sets. We say $f: A \stackrel{\sim}{\to} B$ , or $A \cong B$ .

Suppose $f: A \to B$ is bijective. Then, we are justified in “flipping” the diagram that defines $f$ to produce $g: B \to A$ such that $a = g(b)$ whenever $b = f(a)$ . Diagrammatically,

commutes, so $g \circ f = \id_A$ and $f \circ g = \id_B$ . The first diagram says $g$ is a left-inverse of $f$ (as reference to $g$ being left to $f$ in composition notation, which is read right-to-left), and conversely the second diagram says $g$ is a right-inverse of $f$ . Indeed, we simply say $g$ is the inverse of $f$ , for which we write $g = f^{-1}$ since two-sided inverses are unique (this is trivial and left without proof).

[1.3.4]Theorem(Injectivity, Surjectivity, Bijectivity Characterized by Invertibility)#

Suppose $f: A \to B$ with $A \ne \emptyset$ . Then

$f$ has a left-inverse if and only if it is injective.
$f$ has a right-inverse if and only if it is surjective.
$f$ has a (unique) two-sided inverse if and only if it is bijective.

Proof.

This is trivial and left without proof.