Functions

A function assigns to each element of one set exactly one element of another. Almost every mathematical construction uses them: sequences are functions, so are the operations of arithmetic, and the structure-preserving maps of algebra and geometry are functions with extra properties. Functions are also how sets are compared, since a function that pairs off the elements of two sets shows that they have the same size.

This topic gives the formal definition, the standard ways of building and combining functions, how functions act on subsets, and the properties of being injective, surjective and invertible.

Conventions

$f : A \to B$ means that $f$ is a function from $A$ to $B$ , and $a \mapsto f(a)$ describes what it does to an element, as in $x \mapsto x^2$ . “Map” and “mapping” are synonyms for “function”.
A function includes its codomain, so changing the codomain gives a different function. Some authors identify a function with its graph, and then a function has no definite codomain.
$f(S)$ is the image of a subset $S$ and $f^{-1}(T)$ is the preimage of a subset $T$ . The form $f[S]$ is a common alternative, especially in set theory, because it avoids an ambiguity.
The preimage $f^{-1}(T)$ is defined for every function, while the inverse function $f^{-1}$ exists only for bijections.
“Range” is avoided, because authors use it for either the codomain or the image. This topic says “codomain” or “image”.
Injective, surjective and bijective are also called one-to-one, onto and one-to-one correspondence. “One-to-one” is the risky term, since it is sometimes misread as “bijective”.
Composition is applied from right to left: $(g \circ f)(a) = g(f(a))$ . Some authors, particularly in algebra, write functions on the right and compose from left to right.
Composition $g \circ f$ requires the codomain of $f$ to be the domain of $g$ . Many authors only require $f(A)$ to be a subset of the domain of $g$ .
$B^A$ is the set of all functions from $A$ to $B$ .
Sets defines $A \times B$ and $A^n$ using tuples, while here $B^A$ and products of families are sets of functions. So $A^n$ and $A^{\{1, \dots, n\}}$ , and likewise $A_1 \times A_2$ and $\prod_{i \in \{1, 2\}} A_i$ , are identified rather than literally equal. In the same way, the notation $2^A$ that Sets mentions for $\mathcal{P}(A)$ is identified with $\{0, 1\}^A$ .
$0^0 = 1$ , which matches the number of functions $\emptyset \to \emptyset$ .
A characteristic function here is the indicator of a subset. In probability the term means something else, and “indicator function” is used for this one.
$\mathbb{N}$ , $\mathbb{N}_0$ and intervals are as in Sets, with $(a, \infty) = \{x \in \mathbb{R} : x > a\}$ and $(-\infty, b) = \{x \in \mathbb{R} : x < b\}$ in addition. Sets uses $\lvert A \rvert$ informally, and it is defined here. The indexed families described there as assignments are functions in the sense of this topic.

Builds on

Sets, in particular Cartesian products, double inclusion, indexed families and power sets. Informal familiarity with proof by induction.

What a function is

A function is often first met as a rule, such as “square the input”, or as a table listing an output for each input. What matters in both cases is the same: each allowed input has exactly one output. The set of pairs (input, output) records all of this, and gives a definition that does not depend on any rule being written down.

Definition 1 (Function)

A function $f$ from a set $A$ to a set $B$ , written $f : A \to B$ , consists of the sets $A$ and $B$ together with a subset $G \subseteq A \times B$ such that for every $a \in A$ there is exactly one $b \in B$ with $(a, b) \in G$ .

The set $A$ is the domain of $f$ , the set $B$ is its codomain, and $G$ is its graph. The unique $b$ with $(a, b) \in G$ is the value of $f$ at $a$ , written $f(a)$ .

Example 2

The function $f : \mathbb{R} \to \mathbb{R}$ given by $f(x) = x^2$ has as its graph the parabola $\{(x, x^2) : x \in \mathbb{R}\}$ .

For $A = \{1, 2, 3\}$ and $B = \{x, y, z\}$ , the table $f(1) = x$ , $f(2) = x$ , $f(3) = y$ describes the function with graph $\{(1, x), (2, x), (3, y)\}$ . Two inputs may share a value, and an element of the codomain, here $z$ , need not be a value at all.

Each input must have a value, and only one. Those are the two ways an attempted definition can fail.

Example 3

The rule $x \mapsto 1/x$ does not define a function $\mathbb{R} \to \mathbb{R}$ , since $0$ has no value. It does define a function $\mathbb{R} \setminus \{0\} \to \mathbb{R}$ .
The rule $n \mapsto n - 1$ does not define a function $\mathbb{N} \to \mathbb{N}$ . It sends $1$ to $0$ , which is not in the codomain, so $1$ has no value in $\mathbb{N}$ . It does define a function $\mathbb{N} \to \mathbb{N}_0$ .
“The $y$ with $y^2 = x$ ” does not define a function $[0, \infty) \to \mathbb{R}$ , since $4$ would have both $2$ and $-2$ as values.
The unit circle $\{(x, y) \in \mathbb{R}^2 : x^2 + y^2 = 1\}$ is not the graph of a function $\mathbb{R} \to \mathbb{R}$ . The input $0$ is paired with two values, and the input $2$ with none.

Remark 4

A rule that refers to a particular way of writing its input must give the same output for every way of writing that input. Such a rule is called well defined. For example, " $p/q \mapsto p$ " does not define a function $\mathbb{Q} \to \mathbb{Z}$ , because $1/2 = 2/4$ would have both $1$ and $2$ as values.

Since a graph is determined by the values, a function is determined by its domain, its codomain and its values.

Proposition 5 (Equality of functions)

Functions $f$ and $g$ are equal if and only if they have the same domain $A$ , the same codomain, and $f(a) = g(a)$ for every $a \in A$ .

Proof

A function consists of its domain, codomain and graph, so we must show that functions with the same domain and codomain have the same graph exactly when they have the same values. If the graphs are equal, then $(a, f(a))$ lies in the graph of $g$ , so $f(a) = g(a)$ by uniqueness of the value. If the values are equal, each graph is the set of pairs $(a, f(a))$ with $a \in A$ , so the graphs are equal.

So $x \mapsto x^2$ as a function $\mathbb{R} \to \mathbb{R}$ and as a function $\mathbb{R} \to [0, \infty)$ are different functions, even though they have the same values. The difference matters for surjectivity.

Remark 6

Some authors define a function to be just its graph, a set of pairs in which no two pairs have the same first entry. The domain can be recovered from such a set, but the codomain cannot. So with that definition, being surjective, which means that every element of the codomain is a value, only makes sense relative to a stated codomain.

Example 7 (The empty function)

For any set $B$ , the empty set is a subset of $\emptyset \times B = \emptyset$ that vacuously satisfies the condition, so there is exactly one function $\emptyset \to B$ . It is called the empty function, with the codomain $B$ understood from context. If $A \ne \emptyset$ , there is no function $A \to \emptyset$ , since an element of $A$ would need a value.

Several familiar objects are functions under other names.

Remark 8

A sequence $(a_n)_{n \in \mathbb{N}}$ in a set $B$ is a function $\mathbb{N} \to B$ , written with $a_n$ in place of $a(n)$ .
An $n$ -tuple in $B$ can be regarded as a function $\{1, \dots, n\} \to B$ .
A function $f : A_1 \times A_2 \to B$ on a product has a single input, the pair $(a_1, a_2)$ , but we write $f(a_1, a_2)$ instead of $f((a_1, a_2))$ and speak of a function of two variables. Addition of real numbers is a function $\mathbb{R} \times \mathbb{R} \to \mathbb{R}$ .

Remark 9

An indexed family $(A_i)_{i \in I}$ can be regarded as a function on $I$ whose value at $i$ is the set $A_i$ , for instance with codomain $\{A_i : i \in I\}$ . The choice of codomain plays no role for families, as long as every $A_i$ is an element of it. It cannot be “the set of all sets”, because there is no such set.

Definition 10 (Set of functions)

$B^A$ is the set of all functions from $A$ to $B$ .

This is a set, because for fixed $A$ and $B$ a function is determined by its graph, and the graphs are elements of $\mathcal{P}(A \times B)$ . The exponential notation is explained by the count of functions between finite sets.

Standard constructions

Some functions come up so often, in every part of mathematics, that they have names of their own.

Definition 11 (Identity and constant functions)

The identity function on $A$ is $\mathrm{id}_A : A \to A$ with $\mathrm{id}_A(a) = a$ . A function $f : A \to B$ is constant if there is some $b \in B$ with $f(a) = b$ for every $a \in A$ .

Definition 12 (Inclusion and restriction)

If $S \subseteq A$ , the inclusion of $S$ in $A$ is the function $S \to A$ given by $s \mapsto s$ . The restriction of $f : A \to B$ to $S$ is the function $f|_S : S \to B$ given by $f|_S(s) = f(s)$ . We also say that $f$ is an extension of $f|_S$ .

The inclusion of $S$ in $A$ is not the identity on $S$ unless $S = A$ , because the codomains differ.

Definition 13 (Projections)

The projections of $A \times B$ are the functions $\pi_1 : A \times B \to A$ with $\pi_1(a, b) = a$ and $\pi_2 : A \times B \to B$ with $\pi_2(a, b) = b$ .

An $n$ -tuple with $a_i \in A_i$ can be regarded as a function on $\{1, \dots, n\}$ whose value at $i$ lies in $A_i$ . Read this way, a product no longer needs its factors to be listed in order, so it can have any index set.

Definition 14 (Product of a family)

Let $(A_i)_{i \in I}$ be an indexed family of sets. Its product $\prod_{i \in I} A_i$ is the set of all functions $x : I \to \bigcup_{i \in I} A_i$ with $x(i) \in A_i$ for every $i \in I$ . We usually write $x_i$ for $x(i)$ . For each $j \in I$ , the projection $\pi_j : \prod_{i \in I} A_i \to A_j$ is given by $\pi_j(x) = x_j$ .

Example 15

For $I = \{1, 2\}$ , $A_1 = \{a, b\}$ and $A_2 = \{0, 1, 2\}$ , the product has six elements, one for each pair in $A_1 \times A_2$ . The product $\prod_{n \in \mathbb{N}} \{0, 1\}$ is the set of sequences of zeros and ones.

For $I = \{1, \dots, n\}$ , elements of the product correspond to $n$ -tuples, so it matches the Cartesian product of $A_1, \dots, A_n$ under this identification. When $I \ne \emptyset$ and every $A_i$ equals $A$ , the product is $A^I$ . If some $A_i$ is empty, the product is empty. The product of the empty family has exactly one element, the empty function.

Definition 16 (Characteristic function)

For $S \subseteq A$ , the characteristic function of $S$ is the function $\chi_S : A \to \{0, 1\}$ with $\chi_S(a) = 1$ if $a \in S$ and $\chi_S(a) = 0$ if $a \notin S$ . It is also called the indicator function, and is sometimes written $\mathbf{1}_S$ .

Composition

Applying one function after another gives a new function, provided that the codomain of the first is the domain of the second.

Definition 17 (Composition)

For $f : A \to B$ and $g : B \to C$ , the composition of $g$ and $f$ is the function $g \circ f : A \to C$ given by $(g \circ f)(a) = g(f(a))$ .

Note the order: $g \circ f$ applies $f$ first.

Example 18

Let $f, g : \mathbb{R} \to \mathbb{R}$ with $f(x) = x + 1$ and $g(x) = x^2$ . Then $(g \circ f)(x) = (x + 1)^2$ and $(f \circ g)(x) = x^2 + 1$ . These differ at $x = 1$ , with values $4$ and $2$ , so $g \circ f \ne f \circ g$ . For functions between different sets, one of the two compositions may not even be defined.

Proposition 19 (Composition laws)

For $f : A \to B$ , $g : B \to C$ and $h : C \to D$ :

$h \circ (g \circ f) = (h \circ g) \circ f$ ;
$f \circ \mathrm{id}_A = f$ and $\mathrm{id}_B \circ f = f$ .

Proof

For (1), both sides have domain $A$ and codomain $D$ , and for each $a \in A$ both have the value $h(g(f(a)))$ . So they are equal. For (2), each function has domain $A$ and codomain $B$ , and for each $a \in A$ each has the value $f(a)$ .

Because of (1), we can write $h \circ g \circ f$ without brackets.

Images and preimages

A function acts on single elements, but it also carries whole subsets of its domain to subsets of its codomain, and subsets of its codomain back to subsets of its domain.

Definition 20 (Image)

Let $f : A \to B$ and $S \subseteq A$ . The image of $S$ under $f$ is $f(S) = \{f(s) : s \in S\}$ , a subset of $B$ . The set $f(A)$ is the image of $f$ .

Definition 21 (Preimage)

Let $f : A \to B$ and $T \subseteq B$ . The preimage, or inverse image, of $T$ under $f$ is $f^{-1}(T) = \{a \in A : f(a) \in T\}$ , a subset of $A$ . The preimage $f^{-1}(\{b\})$ of a single element is called the fibre of $f$ over $b$ .

Example 22

Let $f : \mathbb{R} \to \mathbb{R}$ with $f(x) = x^2$ . Then

$f([-1, 2]) = [0, 4]$ ;
$f^{-1}([1, 4]) = [-2, -1] \cup [1, 2]$ ;
$f^{-1}(\{4\}) = \{-2, 2\}$ ;
$f^{-1}((-\infty, 0)) = \emptyset$ .

Remark 23

The notation $f(S)$ uses the same parentheses as the value $f(a)$ . This is ambiguous only when something is both an element and a subset of the domain. That is rare, but it can happen: if $A = \{1, \{1\}\}$ , then $\{1\} \in A$ and $\{1\} \subseteq A$ , so $f(\{1\})$ could mean the value at the element $\{1\}$ or the image of the subset $\{1\}$ . Writing $f[S]$ avoids the problem. The notation $f^{-1}(T)$ does not claim that an inverse function exists: it is defined for every $f$ .

Both operations respect inclusion.

Proposition 24 (Monotonicity of image and preimage)

Let $f : A \to B$ . If $S_1 \subseteq S_2 \subseteq A$ , then $f(S_1) \subseteq f(S_2)$ . If $T_1 \subseteq T_2 \subseteq B$ , then $f^{-1}(T_1) \subseteq f^{-1}(T_2)$ .

Proof

If $b \in f(S_1)$ , then $b = f(s)$ for some $s \in S_1 \subseteq S_2$ , so $b \in f(S_2)$ . If $a \in f^{-1}(T_1)$ , then $f(a) \in T_1 \subseteq T_2$ , so $a \in f^{-1}(T_2)$ .

Membership in a preimage is a statement about a single value $f(a)$ , so preimages interact perfectly with set operations.

Theorem 25 (Preimages and set operations)

Let $f : A \to B$ , let $(T_i)_{i \in I}$ be a family of subsets of $B$ , and let $T \subseteq B$ . Then:

$f^{-1}\bigl(\bigcup_{i \in I} T_i\bigr) = \bigcup_{i \in I} f^{-1}(T_i)$ ;
if $I \ne \emptyset$ , then $f^{-1}\bigl(\bigcap_{i \in I} T_i\bigr) = \bigcap_{i \in I} f^{-1}(T_i)$ ;
$f^{-1}(B \setminus T) = A \setminus f^{-1}(T)$ .

Proof

For $a \in A$ , each of the following is equivalent to the next: $a$ lies in the left side of (1); $f(a) \in T_i$ for some $i$ ; $a \in f^{-1}(T_i)$ for some $i$ ; $a$ lies in the right side of (1). Statement (2) is the same with “for every $i$ ” in place of “for some $i$ ”. For (3), $a \in f^{-1}(B \setminus T)$ if and only if $f(a) \notin T$ , which holds if and only if $a \notin f^{-1}(T)$ .

Images behave well with unions, but not with intersections, because different elements can have the same value.

Theorem 26 (Images and set operations)

Let $f : A \to B$ and let $(S_i)_{i \in I}$ be a family of subsets of $A$ . Then:

$f\bigl(\bigcup_{i \in I} S_i\bigr) = \bigcup_{i \in I} f(S_i)$ ;
if $I \ne \emptyset$ , then $f\bigl(\bigcap_{i \in I} S_i\bigr) \subseteq \bigcap_{i \in I} f(S_i)$ .

Proof

For (1), $b$ lies in the left side if and only if $b = f(a)$ for some $a$ lying in some $S_i$ , which says exactly that $b \in f(S_i)$ for some $i$ . For (2), if $b = f(a)$ with $a$ in every $S_i$ , then $b \in f(S_i)$ for every $i$ .

Example 27

The inclusion in (2) can be strict. For $f(x) = x^2$ on $\mathbb{R}$ , let $S_1 = [-1, 0]$ and $S_2 = [0, 1]$ . Then $f(S_1 \cap S_2) = f(\{0\}) = \{0\}$ , while $f(S_1) \cap f(S_2) = [0, 1]$ .

Images of complements are no better. For $S = [0, \infty)$ , we have $f(\mathbb{R} \setminus S) = (0, \infty)$ and $\mathbb{R} \setminus f(S) = (-\infty, 0)$ , and neither is a subset of the other.

Image and preimage are not inverse operations, though each comes close.

Proposition 28 (Image of preimage, preimage of image)

Let $f : A \to B$ , $S \subseteq A$ and $T \subseteq B$ . Then:

$S \subseteq f^{-1}(f(S))$ ;
$f(f^{-1}(T)) = T \cap f(A)$ , and in particular $f(f^{-1}(T)) \subseteq T$ .

Proof

For (1), if $s \in S$ then $f(s) \in f(S)$ , so $s \in f^{-1}(f(S))$ .

For (2), an element $b$ of $f(f^{-1}(T))$ has the form $f(a)$ with $f(a) \in T$ , so $b \in T \cap f(A)$ . Conversely, if $b \in T \cap f(A)$ , then $b = f(a)$ for some $a$ , and $a \in f^{-1}(T)$ because $f(a) = b \in T$ . So $b \in f(f^{-1}(T))$ .

Example 29

For $f(x) = x^2$ on $\mathbb{R}$ , the set $S = [0, 1]$ has $f^{-1}(f(S)) = [-1, 1] \ne S$ , and the set $T = [-1, 1]$ has $f(f^{-1}(T)) = [0, 1] \ne T$ .

For composites, images and preimages can be taken one function at a time.

Proposition 30

For $f : A \to B$ , $g : B \to C$ , $S \subseteq A$ and $U \subseteq C$ , we have $(g \circ f)(S) = g(f(S))$ and $(g \circ f)^{-1}(U) = f^{-1}(g^{-1}(U))$ .

Proof

An element of $C$ lies in $(g \circ f)(S)$ if and only if it equals $g(f(s))$ for some $s \in S$ , and that says exactly that it lies in $g(f(S))$ . For the second identity, $a \in (g \circ f)^{-1}(U)$ if and only if $g(f(a)) \in U$ , if and only if $f(a) \in g^{-1}(U)$ , if and only if $a \in f^{-1}(g^{-1}(U))$ .

Injective, surjective and bijective functions

The two features of a function that the definition leaves open are whether different inputs can share a value, and whether every element of the codomain is a value.

Definition 31 (Injective)

A function $f : A \to B$ is injective if for all $a, a' \in A$ , $f(a) = f(a')$ implies $a = a'$ . Equivalently, different elements have different values, or each fibre has at most one element.

Definition 32 (Surjective)

A function $f : A \to B$ is surjective if $f(A) = B$ . That is, for every $b \in B$ there is some $a \in A$ with $f(a) = b$ . Equivalently, each fibre has at least one element.

Definition 33 (Bijective)

A function is bijective, or a bijection, if it is both injective and surjective. Equivalently, each fibre has exactly one element.

The words “injection” and “surjection” are also used. Every identity function $\mathrm{id}_A$ is bijective, directly from these definitions.

Four arrow diagrams between sets A and B: a function that is neither injective nor surjective, one that is injective only, one that is surjective only, and a bijection

Remark 34

To prove that $f$ is injective, assume $f(a) = f(a')$ and deduce $a = a'$ . To prove that $f$ is surjective, take an arbitrary $b \in B$ and find an $a$ with $f(a) = b$ . For $f : \mathbb{R} \to \mathbb{R}$ with $f(x) = 2x + 3$ : if $2a + 3 = 2a' + 3$ then $a = a'$ , and for any $b$ the number $a = (b - 3)/2$ has $f(a) = b$ .

Both properties depend on the sets involved as well as on the rule.

Example 35 (The same rule on different sets)

The rule $x \mapsto x^2$ gives four different functions:

$\mathbb{R} \to \mathbb{R}$ is neither injective nor surjective;
$\mathbb{R} \to [0, \infty)$ is surjective but not injective;
$[0, \infty) \to \mathbb{R}$ is injective but not surjective;
$[0, \infty) \to [0, \infty)$ is bijective.

More generally, any function $f : A \to B$ becomes surjective when its codomain is replaced by $f(A)$ , and an injective function then becomes a bijection $A \to f(A)$ .

Theorem 36 (Composition and injectivity, surjectivity)

Let $f : A \to B$ and $g : B \to C$ .

If $f$ and $g$ are injective, then $g \circ f$ is injective.
If $f$ and $g$ are surjective, then $g \circ f$ is surjective.
If $f$ and $g$ are bijective, then $g \circ f$ is bijective.
If $g \circ f$ is injective, then $f$ is injective.
If $g \circ f$ is surjective, then $g$ is surjective.

Proof

For (1), if $g(f(a)) = g(f(a'))$ , then $f(a) = f(a')$ because $g$ is injective, and so $a = a'$ because $f$ is injective.

For (2), take $c \in C$ . Since $g$ is surjective, $c = g(b)$ for some $b \in B$ , and since $f$ is surjective, $b = f(a)$ for some $a \in A$ . Then $(g \circ f)(a) = c$ .

Statement (3) combines (1) and (2).

For (4), if $f(a) = f(a')$ , then $g(f(a)) = g(f(a'))$ , so $a = a'$ because $g \circ f$ is injective.

For (5), each $c \in C$ equals $g(f(a))$ for some $a \in A$ , which is a value of $g$ at the element $f(a)$ .

Example 37

In (4), $g$ need not be injective, and in (5), $f$ need not be surjective. Let $f : \{1\} \to \{1, 2\}$ be the inclusion and let $g : \{1, 2\} \to \{1\}$ be constant. Then $g \circ f$ is bijective, but $f$ is not surjective and $g$ is not injective.

The inclusions and failures found for images and preimages come exactly from functions not being injective or surjective.

Theorem 38 (Characterizations by images and preimages)

For $f : A \to B$ , the following are equivalent:

$f$ is injective;
$f^{-1}(f(S)) = S$ for every $S \subseteq A$ ;
$f(S_1 \cap S_2) = f(S_1) \cap f(S_2)$ for all $S_1, S_2 \subseteq A$ ;
$f(A \setminus S) \subseteq B \setminus f(S)$ for every $S \subseteq A$ .

Also, the following are equivalent:

$f$ is surjective;
$f(f^{-1}(T)) = T$ for every $T \subseteq B$ ;
$B \setminus f(S) \subseteq f(A \setminus S)$ for every $S \subseteq A$ .

Proof

(1) implies (2): by the earlier proposition it is enough to show $f^{-1}(f(S)) \subseteq S$ . If $f(a) \in f(S)$ , then $f(a) = f(s)$ for some $s \in S$ , and $a = s \in S$ by injectivity.

(2) implies (1): if $f(a) = f(a')$ , then $a' \in f^{-1}(f(\{a\})) = \{a\}$ , so $a' = a$ .

(1) implies (3): the inclusion $\subseteq$ holds in general. If $b \in f(S_1) \cap f(S_2)$ , then $b = f(s_1) = f(s_2)$ with $s_1 \in S_1$ and $s_2 \in S_2$ . By injectivity $s_1 = s_2$ , which then lies in $S_1 \cap S_2$ , so $b \in f(S_1 \cap S_2)$ .

(3) implies (1): if $a \ne a'$ but $f(a) = f(a')$ , then $S_1 = \{a\}$ and $S_2 = \{a'\}$ give $f(S_1 \cap S_2) = \emptyset$ and $f(S_1) \cap f(S_2) = \{f(a)\}$ , contradicting (3).

(1) implies (4): let $b \in f(A \setminus S)$ , so $b = f(a)$ with $a \notin S$ . If also $b = f(s)$ with $s \in S$ , then $a = s \in S$ by injectivity, a contradiction. So $b \notin f(S)$ .

(4) implies (1): if $a \ne a'$ but $f(a) = f(a')$ , take $S = \{a\}$ . Then $f(a') \in f(A \setminus S)$ , but $f(a') = f(a) \in f(S)$ , contradicting (4).

(5) and (6): $f(f^{-1}(T)) = T \cap f(A)$ by the earlier proposition. If $f(A) = B$ this equals $T$ . Conversely, taking $T = B$ gives $f(f^{-1}(B)) = f(A)$ , so if (6) holds then $f(A) = B$ .

(5) implies (7): let $b \in B \setminus f(S)$ . By surjectivity $b = f(a)$ for some $a \in A$ , and $a \notin S$ because $b \notin f(S)$ . So $b \in f(A \setminus S)$ .

(7) implies (5): taking $S = \emptyset$ gives $B \subseteq f(A)$ .

Inverses

An inverse undoes a function. Undoing can happen on one side only, and it is the one-sided versions that correspond to injectivity and surjectivity.

Definition 39 (Left, right and two-sided inverses)

Let $f : A \to B$ and $g : B \to A$ . Then $g$ is a left inverse of $f$ if $g \circ f = \mathrm{id}_A$ , and a right inverse of $f$ if $f \circ g = \mathrm{id}_B$ . It is a two-sided inverse, or simply an inverse, if it is both.

Theorem 40 (Left inverses and injectivity)

Let $f : A \to B$ . If $f$ has a left inverse, then $f$ is injective. Conversely, if $f$ is injective and $A \ne \emptyset$ , then $f$ has a left inverse.

Proof

If $g \circ f = \mathrm{id}_A$ , then $g \circ f$ is injective, so $f$ is injective by part (4) of the theorem on composition.

Conversely, let $f$ be injective and choose some $a_0 \in A$ . Define $g : B \to A$ as follows. If $b \in f(A)$ , let $g(b)$ be the element $a$ with $f(a) = b$ , which is unique by injectivity. If $b \notin f(A)$ , let $g(b) = a_0$ . Then $g(f(a)) = a$ for every $a \in A$ .

The condition $A \ne \emptyset$ is needed: the empty function $\emptyset \to B$ is injective, but if $B \ne \emptyset$ there is no function $B \to \emptyset$ at all.

Theorem 41 (Right inverses and surjectivity)

A function $f : A \to B$ is surjective if and only if it has a right inverse.

Proof

If $f \circ g = \mathrm{id}_B$ , then $f \circ g$ is surjective, so $f$ is surjective by part (5) of the theorem on composition.

Conversely, let $f$ be surjective. Each fibre $f^{-1}(\{b\})$ is nonempty, so we can choose one element $g(b)$ from it for each $b \in B$ . Then $f(g(b)) = b$ for every $b \in B$ .

Remark 42

The proof above makes one choice for each $b \in B$ , possibly infinitely many at once. Justifying that requires the axiom of choice, which states that for any family of nonempty sets one element can be chosen from each. In terms of products, it says that the product of any family of nonempty sets is nonempty, since an element of the product is exactly such a choice. In fact, the statement that every surjection has a right inverse is equivalent to the axiom of choice. No such axiom is needed when $B$ is finite, or when there is an explicit way to pick, such as taking the least element of each fibre when $A = \mathbb{N}$ .

Example 43

One-sided inverses are generally not unique. On $\mathbb{N}_0$ , let $f(n) = 2n$ , and let $g(n) = \lfloor n/2 \rfloor$ , where $\lfloor x \rfloor$ is the greatest integer at most $x$ . Then $g \circ f = \mathrm{id}_{\mathbb{N}_0}$ , so $g$ is a left inverse of $f$ , and $f$ is a right inverse of $g$ .

Here $f$ is injective but not surjective, and $g$ is surjective but not injective. The function $n \mapsto 2n + 1$ is another right inverse of $g$ . The function $g'$ with $g'(n) = n/2$ for even $n$ and $g'(n) = 0$ for odd $n$ is another left inverse of $f$ .

If a function has inverses on both sides, the choices disappear.

Theorem 44 (Bijections and inverses)

Let $f : A \to B$ .

If $g$ is a left inverse of $f$ and $h$ is a right inverse of $f$ , then $g = h$ .
$f$ is bijective if and only if it has a two-sided inverse.
A two-sided inverse of $f$ is unique when it exists. It is written $f^{-1}$ .

Proof

For (1), by the composition laws, $g = g \circ \mathrm{id}_B = g \circ (f \circ h) = (g \circ f) \circ h = \mathrm{id}_A \circ h = h.$

For (2), if $f$ is bijective, then each $b \in B$ has exactly one $a \in A$ with $f(a) = b$ . Define $g(b)$ to be this $a$ . Then $g(f(a)) = a$ and $f(g(b)) = b$ for all $a$ and $b$ , so $g$ is a two-sided inverse, with no appeal to the axiom of choice. Conversely, a two-sided inverse is both a left and a right inverse, so $f$ is injective and surjective by the previous two theorems.

For (3), if $g$ and $h$ are both two-sided inverses, then $g = h$ by (1).

Example 45

The function $f : \mathbb{R} \to \mathbb{R}$ with $f(x) = 2x + 3$ is bijective, and solving $y = 2x + 3$ for $x$ gives $f^{-1}(y) = (y - 3)/2$ . The exponential function $\mathbb{R} \to (0, \infty)$ is bijective with inverse $\ln$ . On $[0, \infty)$ , the function $x \mapsto x^2$ is bijective with inverse $x \mapsto \sqrt{x}$ .

Remark 46

When $f$ is bijective, the symbol $f^{-1}$ has two meanings, the inverse function and the preimage. They agree: the preimage of $T$ under $f$ equals the image of $T$ under the function $f^{-1}$ .

Corollary 47 (Inverse laws)

If $f : A \to B$ and $g : B \to C$ are bijective, then $f^{-1}$ and $g \circ f$ are bijective, with $(f^{-1})^{-1} = f$ and $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ .

Proof

The equations $f^{-1} \circ f = \mathrm{id}_A$ and $f \circ f^{-1} = \mathrm{id}_B$ say that $f$ is a two-sided inverse of $f^{-1}$ , so $f^{-1}$ is bijective with inverse $f$ . Next, $g \circ f$ is bijective by part (3) of the theorem on composition, and by the composition laws,

(f^{-1} \circ g^{-1}) \circ (g \circ f) = f^{-1} \circ (g^{-1} \circ g) \circ f = f^{-1} \circ f = \mathrm{id}_A,

and similarly $(g \circ f) \circ (f^{-1} \circ g^{-1}) = \mathrm{id}_C$ . So $f^{-1} \circ g^{-1}$ is the two-sided inverse of $g \circ f$ .

The order reverses for the same reason as with socks and shoes: the last thing done is the first thing undone.

Functions between finite sets

Counting a set means pairing off its elements with $1, 2, \dots, n$ , and such a pairing is a bijection. This makes precise the idea of size that Sets uses informally. Below, $m, n \in \mathbb{N}_0$ and $\{1, \dots, 0\} = \emptyset$ . The first step is to show that a set cannot be counted in two ways with different results.

Lemma 48 (Injections between initial segments)

If there is an injective function $\{1, \dots, m\} \to \{1, \dots, n\}$ , then $m \le n$ .

Proof

We use induction on $m$ , for all $n$ at once. The case $m = 0$ is immediate. Let $f : \{1, \dots, m + 1\} \to \{1, \dots, n\}$ be injective. Then $n \ge 1$ , since $m + 1$ must have a value. Let $\tau$ be the bijection of $\{1, \dots, n\}$ that exchanges $f(m + 1)$ and $n$ and fixes every other element (so $\tau$ is the identity if $f(m + 1) = n$ ). Then $\tau \circ f$ is injective and has value $n$ at $m + 1$ , so it never takes the value $n$ on $\{1, \dots, m\}$ . Restricting it to $\{1, \dots, m\}$ and replacing the codomain by $\{1, \dots, n - 1\}$ therefore gives an injective function $\{1, \dots, m\} \to \{1, \dots, n - 1\}$ . By the induction hypothesis $m \le n - 1$ , so $m + 1 \le n$ .

Definition 49 (Finite set and size)

A set $A$ is finite if there is a bijection $\{1, \dots, n\} \to A$ for some $n \in \mathbb{N}_0$ . This $n$ , which is unique, is the size of $A$ , written $\lvert A \rvert$ . A set that is not finite is infinite.

Proposition 50 (Size is well defined)

If there are bijections $\{1, \dots, m\} \to A$ and $\{1, \dots, n\} \to A$ , then $m = n$ .

Proof

If $f$ and $g$ are such bijections, then $g^{-1} \circ f$ and $f^{-1} \circ g$ are bijections between $\{1, \dots, m\}$ and $\{1, \dots, n\}$ , so the lemma gives $m \le n$ and $n \le m$ .

The following basic facts about size can be proved from this definition, by induction where needed, and are used freely below:

a subset of a finite set is finite;
if $\lvert A \rvert = m + 1$ and $a \in A$ , then $\lvert A \setminus \{a\} \rvert = m$ ;
if $A$ is finite and there is a bijection $A \to B$ , then $B$ is finite and $\lvert B \rvert = \lvert A \rvert$ ;
the size of a disjoint union of finitely many finite sets is the sum of their sizes.

For finite sets, functions can be counted, and the conditions of being injective and surjective become statements about sizes. The starting point is that the fibres of a function divide up its domain.

Proposition 51 (Sizes of fibres)

For a function $f : A \to B$ between finite sets,

\lvert A \rvert = \sum_{b \in B} \lvert f^{-1}(\{b\}) \rvert. \tag{$*$}

Proof

Each element of $A$ lies in exactly one fibre, so $A$ is the disjoint union of the fibres, and its size is the sum of theirs.

The next two theorems follow from this equation.

Theorem 52 (Pigeonhole principle)

Let $f : A \to B$ be a function between finite sets, and let $k \in \mathbb{N}$ . If $\lvert A \rvert > k \lvert B \rvert$ , then some fibre of $f$ has more than $k$ elements. In particular, if $\lvert A \rvert > \lvert B \rvert$ , then $f$ is not injective.

Proof

If every fibre had at most $k$ elements, then $(*)$ would give $\lvert A \rvert \le k \lvert B \rvert$ . The last statement is the case $k = 1$ .

Remark 53

There is a matching statement for surjections. If $f$ is surjective, every term of $(*)$ is at least 1, so $\lvert A \rvert \ge \lvert B \rvert$ . Hence if $\lvert A \rvert < \lvert B \rvert$ , then $f$ is not surjective.

Example 54

Among 13 people, two share a birth month. Among 100 people, at least 9 share a birth month, since $100 > 8 \cdot 12$ . For $n \in \mathbb{N}$ , among any $n + 1$ integers, two have the same remainder on division by $n$ , so their difference is divisible by $n$ .

Theorem 55 (Equal finite sizes)

Let $f : A \to B$ be a function between finite sets with $\lvert A \rvert = \lvert B \rvert$ . Then $f$ is injective if and only if $f$ is surjective, and so each of these is equivalent to $f$ being bijective.

Proof

In $(*)$ , the sum has $\lvert B \rvert$ terms and equals $\lvert B \rvert$ . If $f$ is injective, every term is at most 1, and if $f$ is surjective, every term is at least 1. In either case the total can only equal $\lvert B \rvert$ if every term is exactly 1, which means that $f$ is bijective.

This fails for infinite sets: the functions $n \mapsto 2n$ and $n \mapsto \lfloor n/2 \rfloor$ on $\mathbb{N}_0$ are respectively injective but not surjective, and surjective but not injective. The same equation shows that a bijection between finite sets forces them to have the same size. Extending that idea, so that two possibly infinite sets have the same size when there is a bijection between them, is the starting point of the theory of cardinality.

Proposition 56 (Counting functions)

Let $A$ and $B$ be finite with $\lvert A \rvert = m$ and $\lvert B \rvert = n$ .

There are $n^m$ functions $A \to B$ , so $\lvert B^A \rvert = \lvert B \rvert^{\lvert A \rvert}$ . Here $0^0 = 1$ .
If $m \le n$ , there are $n!/(n - m)!$ injective functions $A \to B$ , with $0! = 1$ . If $m > n$ , there are none.
If $m = n$ , there are $n!$ bijections $A \to B$ .

Proof

We use induction on $m$ for (1) and for the first claim of (2). For $m = 0$ , the only function is the empty function, which is injective, and $n^0 = n!/n! = 1$ .

Now let $\lvert A \rvert = m + 1$ , choose $a \in A$ and let $A' = A \setminus \{a\}$ . A function $f : A \to B$ is determined by its restriction to $A'$ and its value $f(a)$ , and these can be chosen independently. So there are $n^m \cdot n = n^{m+1}$ functions.

If also $m + 1 \le n$ , then $f$ is injective exactly when $f|_{A'}$ is injective and $f(a) \notin f(A')$ . Since $f|_{A'}$ is injective, $f(A')$ has $m$ elements, so there are $n - m$ possible values of $f(a)$ , for a total of $\frac{n!}{(n - m)!} (n - m) = \frac{n!}{(n - m - 1)!}$ injective functions.

The second claim of (2) is the pigeonhole principle. For (3), when $m = n$ the bijections are exactly the injections, and there are $n!/0! = n!$ of them.

Remark 57

Surjections are harder to count, because whether a function is surjective depends on all of its values together. The number of surjective functions from a set of size $m$ to a set of size $n$ is $\sum_{k=0}^{n} (-1)^k \binom{n}{k} (n - k)^m$ , with $0^0 = 1$ . This follows from the general form of the inclusion-exclusion principle, and is not proved here.

Characteristic functions connect functions with subsets. They also explain why $2^A$ is another notation for the power set, with $2$ read as the two-element set $\{0, 1\}$ .

Proposition 58 (Subsets and characteristic functions)

For any set $A$ , the function $\mathcal{P}(A) \to \{0, 1\}^A$ given by $S \mapsto \chi_S$ is a bijection, with inverse given by $h \mapsto h^{-1}(\{1\})$ .

Proof

For $S \subseteq A$ , the set $\chi_S^{-1}(\{1\})$ is exactly $S$ . For $h : A \to \{0, 1\}$ , let $S = h^{-1}(\{1\})$ . Then $\chi_S(a) = 1$ exactly when $h(a) = 1$ , and both functions take only the values $0$ and $1$ , so $\chi_S = h$ . The two functions are therefore inverses of each other.

Combined with the count of functions, this gives $\lvert \mathcal{P}(A) \rvert = 2^n$ for a set with $n$ elements, a result proved directly in Sets.

Summary

A function $f : A \to B$ consists of a domain, a codomain and a graph with exactly one pair for each element of the domain. Two functions are equal when these all agree.
The identity, inclusion and restriction, projections and characteristic functions are standard constructions, and $B^A$ is the set of functions from $A$ to $B$ .
The product of a family $(A_i)_{i \in I}$ consists of the functions on $I$ whose value at each $i$ lies in $A_i$ .
Composition $g \circ f$ applies $f$ first. It is associative with identities but not commutative.
The image is $f(S) = \{f(s) : s \in S\}$ and the preimage is $f^{-1}(T) = \{a \in A : f(a) \in T\}$ . Preimages preserve unions, intersections and complements. Images preserve unions, but only give an inclusion for intersections. The preimage $f^{-1}(\{b\})$ of a single element is the fibre over $b$ .
In general, $S \subseteq f^{-1}(f(S))$ and $f(f^{-1}(T)) = T \cap f(A)$ .
Injective means different inputs have different values, surjective means every element of the codomain is a value, and bijective means both. Injectivity and surjectivity can be read off from images and preimages.
Composites of injections are injective and of surjections are surjective. If $g \circ f$ is injective then $f$ is, and if $g \circ f$ is surjective then $g$ is.
A function with a nonempty domain is injective exactly when it has a left inverse, and a function is surjective exactly when it has a right inverse, which needs the axiom of choice in general.
A function is bijective exactly when it has a two-sided inverse, which is unique, and $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ .
A set is finite if there is a bijection from $\{1, \dots, n\}$ to it, and this $n$ is its size.
For a function between finite sets, the sizes of the fibres add up to the size of the domain. By the pigeonhole principle, if $\lvert A \rvert > k \lvert B \rvert$ then some fibre has more than $k$ elements, so there is no injection when $\lvert A \rvert > \lvert B \rvert$ . There is no surjection when $\lvert A \rvert < \lvert B \rvert$ . Between sets of equal finite size, injective, surjective and bijective are equivalent. From a set of size $m$ to a set of size $n$ there are $n^m$ functions, and $n!/(n-m)!$ injections if $m \le n$ (none if $m > n$ ).
Characteristic functions give a bijection between $\mathcal{P}(A)$ and $\{0, 1\}^A$ .

Conventions

Builds on

What a function is

Standard constructions

Composition

Images and preimages

Injective, surjective and bijective functions

Inverses

Functions between finite sets

Summary

Sources