2.1 Functions and Composition

Chapter 1 made sets, pairs and relations precise. A relation from $A$ to $B$ is a subset of $A \times B$ (Definition 1.4.3), and among the examples of Section 1.4 the graph of squaring relates each real number to exactly one number, while the unit circle relates $0$ to two numbers and $2$ to none. This chapter is about the first kind of relation. This section gives it its name, function, says when two functions are equal, uses functions to make families, sequences and the set $Y^X$ precise, and composes them. The rest of the chapter asks what a function does to its inputs and to its codomain (Section 2.2), builds functions from pieces (Section 2.3), undoes them (Section 2.4), and applies them to whole sets (Section 2.5).

2.1.1. What is a function?

Everyone has used functions since school, and the everyday definition is “a rule that assigns to each input one output”. Look at the word “rule”. The rules $x \mapsto x^2$ and $x \mapsto (x + 1)^2 - 2x - 1$ are different: one squares, the other adds, squares, subtracts, and subtracts again. Yet on every real number they give the same answer, and nobody would call them different functions. Other functions have no rule at all that one could write down. A table of measured temperatures, one per day, assigns to each day one number, and no formula produces it.

So the rule is not what matters. What matters is which output goes with which input: the set of input–output pairs. That set is a relation, and Section 1.4 said exactly when two relations are the same, namely when they contain the same pairs. So we forget the rule and keep the pairs. One more piece of data is needed, the set in which the outputs are declared to lie; the reason is given after the definition.

A function is its graph, with a declared target.

Definition 2.1.1 (Function)

Let $X$ and $Y$ be sets. A function from $X$ to $Y$ , written $f \colon X \to Y$ , is given by a relation $G \subseteq X \times Y$ , the graph of $f$ , such that $\text{for every } x \in X \text{ there is exactly one } y \in Y \text{ with } (x, y) \in G ,$ together with the set $Y$ , the codomain of $f$ . Formally, $f$ is the pair $(G, Y)$ . The set $X$ is the domain of $f$ . For $x \in X$ , the unique $y$ with $(x, y) \in G$ is written $f(x)$ , the value of $f$ at $x$ . We write $(x, y) \in f$ for $(x, y) \in G$ , and $x \mapsto f(x)$ for the whole function when its domain and codomain are clear.

In symbols, the condition on the graph is $\forall x \in X \ \ \exists! \, y \in Y \ \ (x, y) \in G ,$ where, as with the bounded quantifiers of Logic and Proof, Definition 5.1.1, $\exists! \, y \in Y \ \psi$ abbreviates $\exists! \, y \, (y \in Y \wedge \psi)$ .

The whole definition is the quantifier pattern $\forall \exists!$ . By Logic and Proof, Definition 5.8.1, “ $\exists! \, y$ ” is an existence claim and a uniqueness claim, and by Logic and Proof, Proposition 5.8.1 the uniqueness claim may be stated without reference to the witness; so the condition on the graph is two clauses:

(Fn1) (existence) for every $x \in X$ there is at least one $y \in Y$ with $(x, y) \in G$ : every input has an output;
(Fn2) (uniqueness) for every $x \in X$ and all $y, y' \in Y$ , if $(x, y) \in G$ and $(x, y') \in G$ , then $y = y'$ : no input has two outputs.

In words: the graph is a set of input–output pairs, with inputs from $X$ and outputs from $Y$ ; (Fn1) says no input is left without an output, and (Fn2) says no input is given two. The codomain $Y$ is where outputs are allowed to lie. It need not consist of outputs: $x \mapsto x^2$ can be declared as a function from $\mathbb{R}$ to $\mathbb{R}$ , although no output is negative. The set of outputs that actually occur is the range of $f$ , $\{ y \in Y : \exists x \in X \ \ f(x) = y \} ,$ which Section 2.5 will call the image of $X$ and write $f(X)$ . The domain needs no slot of its own in the pair $(G, Y)$ : by (Fn1) every $x \in X$ occurs as a first coordinate in $G$ , and since $G \subseteq X \times Y$ , nothing else does. So the graph determines the domain.

The notation $f(x)$ is well defined. Writing “the $y$ with $(x, y) \in f$ ” is legitimate only if there is one, and only one. Clause (Fn1) supplies one, and clause (Fn2) says that any two are equal; together they license the article “the”. This gives the equivalence that every argument with functions uses: $(x, y) \in f \iff y = f(x) \qquad (x \in X, \ y \in Y). \tag{$\ast\ast$}$ For $(\Leftarrow)$ : $(x, f(x)) \in f$ by the choice of $f(x)$ , and if $y = f(x)$ then $(x, y) \in f$ by substituting equals ( $\mathrm{=E}$ , Logic and Proof, Definition 5.7.1). For $(\Rightarrow)$ : both $(x, y)$ and $(x, f(x))$ lie in $f$ , so $y = f(x)$ by (Fn2). Two consequences follow at once. Equal inputs give equal outputs: if $x_1 = x_2$ , then $f(x_1) = f(x_2)$ . And every value lies in the codomain: $f(x) \in Y$ for every $x \in X$ .

Functions given by formulas. Most functions in this book are introduced by a formula: “let $f \colon \mathbb{R} \to \mathbb{R}$ , $f(x) = x^2$ ”. This means the function whose graph is $\{ (x, y) \in \mathbb{R}^2 : y = x^2 \}$ . Clause (Fn2) holds for any such graph: if $y = x^2$ and $y' = x^2$ , then $y = y'$ . So for a formula only (Fn1) needs checking, and it says: for each $x$ in the domain, the formula makes sense and its value lies in the codomain. For $x^2$ on $\mathbb{R}$ both are clear. For “ $f \colon \mathbb{R} \to \mathbb{R}$ , $f(x) = 1/x$ ” the formula makes no sense at $x = 0$ , and (Fn1) fails there; for “ $f \colon \mathbb{R} \to [0, \infty)$ , $f(x) = x^2$ ” the value must be checked to lie in $[0, \infty)$ , which it does, since squares are nonnegative.

A function whose domain is a product $A \times B$ is a function of two variables. Its inputs are pairs, and we write $f(a, b)$ rather than $f((a, b))$ . Addition $(m, n) \mapsto m + n$ from $\mathbb{N} \times \mathbb{N}$ to $\mathbb{N}$ is an example.

Example (First functions)

Check (Fn1) and (Fn2), and find the range, for each of the following.

(a) $f \colon \{1, 2, 3\} \to \{a, b\}$ with graph $\{ (1, a), (2, b), (3, a) \}$ .
(b) The identity function $\operatorname{id}_X \colon X \to X$ , $\operatorname{id}_X(x) = x$ , for a set $X$ .
(c) A constant function $X \to Y$ , $x \mapsto c$ , for a fixed $c \in Y$ .
(d) The indicator function $\mathbf{1}_A \colon X \to \{0, 1\}$ of a subset $A \subseteq X$ : $\mathbf{1}_A(x) = \begin{cases} 1 & \text{if } x \in A, \\ 0 & \text{if } x \in X \setminus A. \end{cases}$

Solution.

(a) The graph is a subset of $\{1, 2, 3\} \times \{a, b\}$ . Each of $1$ , $2$ , $3$ occurs as a first coordinate (Fn1), and each occurs exactly once, so no input has two outputs (Fn2). So $f$ is a function, with $f(1) = a$ , $f(2) = b$ , $f(3) = a$ . Its range is $\{a, b\}$ , the whole codomain. A function on a small finite set is often given this way, by listing its values; no formula is needed.
(b) The graph is the diagonal $\{ (x, x) : x \in X \}$ . For each $x$ , the pair $(x, x)$ is in it (Fn1); and if $(x, y)$ is in it, then $(x, y) = (z, z)$ for some $z \in X$ , and the characteristic property (Definition 1.4.1) gives $x = z = y$ (Fn2). The range is $X$ .
(c) The graph is $X \times \{c\}$ . For each $x \in X$ , $(x, c)$ is in it (Fn1); if $(x, y)$ is in it, then $y \in \{c\}$ by the membership test $(\ast)$ for pairs in a product (Definition 1.4.2), so $y = c$ (Fn2). If $X$ has an element, the range is $\{c\}$ . If $X = \emptyset$ , the range is $\emptyset$ .
(d) The graph is $\bigl(A \times \{1\}\bigr) \cup \bigl((X \setminus A) \times \{0\}\bigr)$ . For (Fn1), let $x \in X$ . By excluded middle (Logic and Proof, Proposition 2.5.3), $x \in A$ or $x \notin A$ ; in the first case $(x, 1)$ is in the graph, in the second $x \in X \setminus A$ and $(x, 0)$ is. For (Fn2), the two cases cannot both hold, so $x$ never receives both $0$ and $1$ , and each case gives only one pair with first coordinate $x$ . The range is $\{0, 1\}$ if $A$ has an element and $X \setminus A$ has an element; it is $\{0\}$ if $A = \emptyset$ and $X$ has an element, $\{1\}$ if $A = X$ and $X$ has an element, and $\emptyset$ if $X = \emptyset$ . This is the first function of the chapter whose existence clause needs excluded middle: the definition by cases is a function only because every $x$ falls into one of the cases.

The next example collects relations that fail to be functions. Each failure is one clause, and it pays to say which.

Example (Relations that are not functions)

(a) Is the unit circle $S = \{ (x, y) \in \mathbb{R}^2 : x^2 + y^2 = 1 \}$ the graph of a function $\mathbb{R} \to \mathbb{R}$ ?
(b) “Send a fraction $p/q$ to its numerator $p$ .” Is this a function from $\mathbb{Q}$ to $\mathbb{Z}$ ? As a relation it is $N \mathrel{:=} \{ (r, p) \in \mathbb{Q} \times \mathbb{Z} : \exists q \in \mathbb{Z}_{>0} \ \ r = p/q \} .$

Solution.

(a) No, and both clauses fail, at different points. Clause (Fn2) fails at $x = 0$ : both $(0, 1)$ and $(0, -1)$ lie in $S$ , and $1 \ne -1$ . Clause (Fn1) fails at $x = 2$ : a pair $(2, y) \in S$ would need $y^2 = 1 - 4 = -3$ , and no real square is negative. Restricting the inputs to $[-1, 1]$ repairs (Fn1) but not (Fn2); keeping only the upper half, $y \ge 0$ , repairs (Fn2) as well, and gives the function $[-1, 1] \to \mathbb{R}$ , $x \mapsto \sqrt{1 - x^2}$ .
(b) No. Clause (Fn1) holds: every rational number is $p/q$ for some $p \in \mathbb{Z}$ and $q \in \mathbb{Z}_{>0}$ . But (Fn2) fails, because a rational number has many ways of being written as a fraction. Since $\tfrac{1}{2} = \tfrac{2}{4}$ , both $(\tfrac12, 1)$ and $(\tfrac12, 2)$ lie in $N$ , and $1 \ne 2$ . The “rule” gives an output that depends on how the input is written, not on the input. A function may not do that, since its value is attached to the input itself. This is why definitions of the form “write $x$ as …, then send it to …” must be checked for well-definedness, a check that returns in Chapter 5 for functions defined on classes. Here the repair is to fix the way of writing: let $q_0$ be the least $q \in \mathbb{Z}_{>0}$ with $rq \in \mathbb{Z}$ (such $q$ exist, by the first sentence, so there is a least one by well-ordering, proved in Chapter 3; a least element is unique), and send $r$ to $r q_0$ . This is a function.

Second readingWhy each clause, and why a codomain

Why this definition. Each clause has a job, and dropping one lets in the failures of Example (Relations that are not functions). Without (Fn1), a “function” could be undefined at some inputs, like $1/x$ at $0$ ; then $f(x)$ would not name anything, and statements “for every $x \in X$ ” about $f(x)$ would lose their meaning. Without (Fn2), $f(x)$ would not name one thing, and $f(\tfrac12)$ in part (b) would be both $1$ and $2$ . The graph replaces the rule because two rules can describe one function, and sets are compared by their elements.

Why is the codomain part of the data? A relation is a set, so if a function were only its graph, two functions with the same graph would be equal (Definition 1.2.1), whatever target was declared. The graph of $x \mapsto x^2$ as a function $[0, \infty) \to \mathbb{R}$ is the same set as its graph as a function $[0, \infty) \to [0, \infty)$ . But these should be different functions, because the second reaches every point of its target and the first does not: this is the property called surjectivity in Section 2.2, and Example (Squaring, three ways) there shows it changing with the codomain. Recording the codomain in the pair $(G, Y)$ keeps the two apart. Many books take the same convention, some without saying so.

Warning. A formula is not yet a function. “The function $1/x$ ” names no function until a domain and a codomain are given, and the domain must be chosen so that (Fn1) holds: $x \mapsto 1/x$ is a function $\mathbb{R} \setminus \{0\} \to \mathbb{R}$ , and there is no function $\mathbb{R} \to \mathbb{R}$ given by this formula. Likewise $\sqrt{x}$ makes sense on $[0, \infty)$ and not on $\mathbb{R}$ . When you meet “let $f(x) = \dots$ ”, ask first where $x$ lives and where $f(x)$ is meant to lie.

Quick check. Which of these relations on $\{1, 2, 3\}$ are graphs of functions $\{1, 2, 3\} \to \{1, 2, 3\}$ : $\{ (1, 2), (2, 2), (3, 2) \}$ , $\{ (1, 1), (2, 2) \}$ , $\{ (1, 3), (2, 1), (3, 2), (2, 3) \}$ ? For each that is not, name the clause that fails.

Solution. The first is a function: the constant function with value $2$ . The second fails (Fn1) at $3$ , which has no output. The third fails (Fn2) at $2$ , which has the two outputs $1$ and $3$ .

2.1.2. When are two functions equal?

A function is a pair $(G, Y)$ , so two functions are equal when their graphs are equal and their codomains are equal. In practice we compare functions by their values, and the next result says that this is the same test.

Proposition 2.1.1 (Equality of Functions)

Let $f \colon X \to Y$ and $g \colon X' \to Y'$ be functions. Then $f = g$ if and only if $X = X'$ , $Y = Y'$ , and $f(x) = g(x)$ for every $x \in X$ .

Idea. Write $f = (G, Y)$ and $g = (G', Y')$ . The characteristic property of pairs splits $f = g$ into “same graph” and “same codomain”. Two graphs are equal when they have the same elements, and by $(\ast\ast)$ an element of a graph is a pair $(x, f(x))$ ; so “same graph” is “same inputs, same outputs”.

Proof. Write $f = (G, Y)$ and $g = (G', Y')$ , as in Definition 2.1.1.

$(\Rightarrow)$ Suppose $f = g$ . By the characteristic property of pairs (Definition 1.4.1), $G = G'$ and $Y = Y'$ . The domain is determined by the graph, as the set of first coordinates of its elements, so $X = X'$ . Let $x \in X$ . By $(\ast\ast)$ , $(x, f(x)) \in G = G'$ , so $(x, f(x)) \in g$ , and $(\ast\ast)$ for $g$ gives $f(x) = g(x)$ .

$(\Leftarrow)$ Suppose $X = X'$ , $Y = Y'$ , and $f(x) = g(x)$ for every $x \in X$ . We show $G \subseteq G'$ . Let $p \in G$ . Since $G \subseteq X \times Y$ , $p = (x, y)$ with $x \in X$ and $y \in Y$ . By $(\ast\ast)$ , $y = f(x)$ , so $y = g(x)$ by the hypothesis, and then $p = (x, y) \in G'$ by $(\ast\ast)$ for $g$ . The same argument with $f$ and $g$ exchanged gives $G' \subseteq G$ , so $G = G'$ by Proposition 1.2.1. Since also $Y = Y'$ , the characteristic property gives $(G, Y) = (G', Y')$ , that is, $f = g$ .

So to show two functions equal, check three things: the same domain, the same codomain, and the same value at an arbitrary point. To show them different, one witness suffices: a point where the values differ, or a difference in domain or codomain.

Example (Equal and unequal functions)

Decide which of these functions are equal.

(a) $f, g \colon \mathbb{R} \to \mathbb{R}$ , $f(x) = (x + 1)^2 - 2x - 1$ and $g(x) = x^2$ .
(b) $h, k \colon \mathbb{R} \to \mathbb{R}$ , $h(x) = \left| x \right|$ and $k(x) = \sqrt{x^2}$ .
(c) $s_1 \colon [0, \infty) \to \mathbb{R}$ and $s_2 \colon [0, \infty) \to [0, \infty)$ , both given by $x \mapsto x^2$ .

Solution.

(a) Equal. The domains are both $\mathbb{R}$ and the codomains both $\mathbb{R}$ . For every real $x$ , $(x + 1)^2 - 2x - 1 = x^2 + 2x + 1 - 2x - 1 = x^2$ . By Proposition 2.1.1, $f = g$ : two rules, one function.
(b) Equal. Same domain and codomain, and for every real $x$ , $\sqrt{x^2} = \left| x \right|$ : the number $\left| x \right|$ is nonnegative and its square is $x^2$ , and $\sqrt{x^2}$ is by definition the nonnegative number with square $x^2$ , which is unique by Logic and Proof, Theorem 2.4.5.
(c) Not equal. They have the same domain, the same values, and even the same graph; but their codomains $\mathbb{R}$ and $[0, \infty)$ are different sets ( $-1$ is in one and not the other), so by Proposition 2.1.1 $s_1 \ne s_2$ .

Restriction. A function can be cut down to a smaller domain. For $f \colon X \to Y$ and $A \subseteq X$ , the restriction of $f$ to $A$ is the function $f|_A \colon A \to Y, \qquad f|_A(a) \mathrel{:=} f(a) ,$ whose graph is $G \cap (A \times Y)$ : the pairs of $f$ whose input lies in $A$ . The squaring function $\mathbb{R} \to \mathbb{R}$ restricted to $[0, \infty)$ is $s_1$ of part (c). The bar in $f|_A$ is one of the uses of a vertical bar that the book’s colon-for-set-builder convention keeps free.

2.1.3. Families, sequences, and the set of all functions

Section 1.3 used families of sets $(A_i)_{i \in I}$ and described them informally, as “a set $A_i$ for each index $i \in I$ ”. We can now say exactly what a family is, once its members are known to lie in some set. A family of subsets of $X$ indexed by $I$ is a function $I \to \mathcal{P}\left( X \right)$ , $i \mapsto A_i$ , with the power set $\mathcal{P}\left( X \right)$ as the codomain the definition asks for. More generally, if $S$ is a set whose elements are sets, a family of members of $S$ indexed by $I$ is a function $I \to S$ . A codomain must be named, because there is no set of all sets (Theorem 1.2.4). The value of a family at $i$ is written $A_i$ rather than $A(i)$ , and the family is written $(A_i)_{i \in I}$ , in parentheses because it is indexed. A family is not the same thing as its set of values $\{ A_i : i \in I \}$ : the family $(A_i)_{i \in \{1, 2\}}$ with $A_1 = A_2 = \{0\}$ has two indices and one value.

In the same way, a sequence of real numbers $(a_n)_{n \ge 1}$ is a function $\mathbb{Z}_{>0} \to \mathbb{R}$ , $n \mapsto a_n$ , with the value at $n$ written $a_n$ . The sequence $(1/n)$ is the function $n \mapsto 1/n$ , and its set of values is $\{ 1/n : n \ge 1 \}$ . Sequences are the main object of Analysis on the Real Line.

Finally, all functions from $X$ to $Y$ form a set, written $Y^X \mathrel{:=} \{ f \in \mathcal{P}\left( X \times Y \right) \times \{Y\} : f \text{ is a function from } X \text{ to } Y \} .$

Second readingWhere

Y^X

comes from

It is a set by the working rules of Section 1.2: every function $X \to Y$ is a pair $(G, Y)$ with $G \in \mathcal{P}\left( X \times Y \right)$ , so $Y^X$ is the subset of $\mathcal{P}\left( X \times Y \right) \times \{Y\}$ cut out by the condition of Definition 2.1.1, and this product is a set by (W2), (W4), and (W5), so $Y^X$ is a set by specification (W1).

The letters are in this order because, for finite sets, $Y^X$ has $m^n$ elements when $Y$ has $m$ and $X$ has $n$ , as the next example suggests; counting is the business of Section 4.1. The set $\{0, 1\}^{\mathbb{N}}$ of all sequences of zeros and ones, indexed from $0$ , plays a leading role in Chapter 4.

Example (All functions between two small sets)

List the elements of $\{0, 1\}^{\{1, 2\}}$ , and say which are indicator functions of subsets of $\{1, 2\}$ .

Solution. A function $f \colon \{1, 2\} \to \{0, 1\}$ is determined by its two values $f(1)$ and $f(2)$ (Proposition 2.1.1), and each may be $0$ or $1$ . So there are four:

$f(1)$	$f(2)$	graph	indicator of
$0$	$0$	$\{ (1, 0), (2, 0) \}$	$\emptyset$
$0$	$1$	$\{ (1, 0), (2, 1) \}$	$\{2\}$
$1$	$0$	$\{ (1, 1), (2, 0) \}$	$\{1\}$
$1$	$1$	$\{ (1, 1), (2, 1) \}$	$\{1, 2\}$

Every one of them is an indicator function: $f = \mathbf{1}_A$ for $A = \{ x \in \{1, 2\} : f(x) = 1 \}$ . The four subsets of $\{1, 2\}$ and the four functions correspond one to one.

The correspondence at the end of the example, between subsets of $X$ and functions $X \to \{0, 1\}$ , holds for every set $X$ : send $f$ to $\{ x \in X : f(x) = 1 \}$ and $A$ to $\mathbf{1}_A$ . So counting the subsets of a finite set and counting the functions from it to $\{0, 1\}$ are one problem, which Section 4.1 solves.

A game with five strings. A string of five symbols $0$ or $1$ , such as $01101$ , is a function $\{1, \dots, 5\} \to \{0, 1\}$ : its value at $k$ is its $k$ -th symbol. One player lists five strings, say $00000$ , $11111$ , $01010$ , $10101$ , $00111$ ; the other must write a string not on the list. Searching all $32$ always works, but is there a rule that builds a missing string from any list of five in five steps? Try one. Chapter 4 comes back to this game.

Quick check. Which string is the indicator function of $\{1, 4\} \subseteq \{1, \dots, 5\}$ ? What is the value at $2$ of the string $01100$ ?

Solution. The indicator of $\{1, 4\}$ has value $1$ at $1$ and $4$ and value $0$ elsewhere, so it is the string $10010$ . The value of $01100$ at $2$ is its second symbol, $1$ .

The empty set gives the degenerate cases, and they are worth settling now, since they are the test cases of many later statements.

Proposition 2.1.2 (Functions and the Empty Set)

(a) For every set $Y$ there is exactly one function from $\emptyset$ to $Y$ : the pair $(\emptyset, Y)$ , called the empty function.
(b) If $X$ is nonempty (it has an element), there is no function from $X$ to $\emptyset$ .

Second readingThe empty function, proved

Proof.

(a) Existence. The empty relation satisfies $\emptyset \subseteq \emptyset \times Y$ , since $\emptyset$ is a subset of every set (Section 1.2). The condition of Definition 2.1.1 reads “for every $x$ , if $x \in \emptyset$ , then there is exactly one $y \in Y$ with $(x, y) \in \emptyset$ ”. For each $x$ the hypothesis $x \in \emptyset$ is false, so the implication holds (Logic and Proof, Proposition 2.1.2). So $(\emptyset, Y)$ is a function from $\emptyset$ to $Y$ .
Uniqueness. Let $(G, Y)$ be any function from $\emptyset$ to $Y$ . Its graph satisfies $G \subseteq \emptyset \times Y = \emptyset$ , by the mirror-image $\emptyset$ law of Proposition 1.4.1. So an element of $G$ would be an element of $\emptyset$ ; $G$ has no elements, and $G = \emptyset$ by Proposition 1.2.3. Hence $(G, Y) = (\emptyset, Y)$ .
(b) Let $x_0 \in X$ , and suppose $f \colon X \to \emptyset$ were a function. By (Fn1) there would be $y \in \emptyset$ with $(x_0, y) \in f$ ; but $\emptyset$ has no elements. So there is no such function $[\mathrm{\neg I}]$ .

In the notation $Y^X$ : the set $Y^{\emptyset}$ has exactly one element for every $Y$ , including $Y = \emptyset$ ; and $\emptyset^X = \emptyset$ whenever $X$ is nonempty. The empty function $\emptyset \to Y$ returns in Section 2.4 as the witness that a hypothesis there cannot be dropped.

Quick check. How many elements do $\{0, 1\}^{\emptyset}$ and $\emptyset^{\{0\}}$ have?

Solution. The set $\{0, 1\}^{\emptyset}$ has exactly one element, the empty function $(\emptyset, \{0, 1\})$ , by Proposition 2.1.2 (a). The set $\emptyset^{\{0\}}$ has none, by Proposition 2.1.2 (b), since $\{0\}$ has the element $0$ .

2.1.4. Composition

Two functions can be applied one after the other when the outputs of the first are inputs of the second. Temperature in degrees Celsius, as a function of the day, followed by the conversion to degrees Fahrenheit, gives temperature in Fahrenheit as a function of the day.

Definition 2.1.2 (Composition)

Let $f \colon X \to Y$ and $g \colon Y \to Z$ be functions, the codomain of $f$ being the domain of $g$ . Their composite is the function $g \circ f \colon X \to Z, \qquad (g \circ f)(x) \mathrel{:=} g(f(x)) ,$ read “ $g$ after $f$ ”.

This is a function by the remark on formulas: for $x \in X$ , the value $f(x)$ lies in $Y$ , the domain of $g$ , so $g(f(x))$ makes sense, and it lies in $Z$ . Its graph is $\{ (x, z) \in X \times Z : z = g(f(x)) \}$ . The order of the letters is the order of the formula $g(f(x))$ , which is the reverse of the order in which the functions act: $f$ acts first.

Example (The order of composition matters)

Let $f, g \colon \mathbb{R} \to \mathbb{R}$ , $f(x) = x + 1$ and $g(x) = 2x$ . Compute $g \circ f$ and $f \circ g$ , and decide whether they are equal.

Solution. By Definition 2.1.2, $(g \circ f)(x) = g(x + 1) = 2x + 2$ and $(f \circ g)(x) = f(2x) = 2x + 1$ . At $x = 0$ the values are $2$ and $1$ , so by Proposition 2.1.1 $g \circ f \ne f \circ g$ . In words: “add one, then double” is not “double, then add one”. (In fact the two composites differ at every $x$ , since $2x + 2 \ne 2x + 1$ ; one point already suffices.)

The next example composes two functions that look as if they cancel each other, and finds that they do so in one order only.

Example (Square root after squaring, and squaring after square root)

Let $q \colon \mathbb{R} \to [0, \infty)$ , $q(x) = x^2$ , and $r \colon [0, \infty) \to \mathbb{R}$ , $r(t) = \sqrt{t}$ . Which of $r \circ q$ and $q \circ r$ are defined? Compute them, and compare each with an identity function.

Solution. The composite $r \circ q$ . It is defined, since the codomain $[0, \infty)$ of $q$ is the domain of $r$ (Definition 2.1.2). It is a function $\mathbb{R} \to \mathbb{R}$ with $(r \circ q)(x) = \sqrt{x^2} = \left| x \right| ,$ by Example (Equal and unequal functions) (b). It is not $\operatorname{id}_{\mathbb{R}}$ : its value at $-1$ is $1$ , and $\operatorname{id}_{\mathbb{R}}(-1) = -1$ .

The composite $q \circ r$ . It is defined as well, since the codomain $\mathbb{R}$ of $r$ is the domain of $q$ . It is a function $[0, \infty) \to [0, \infty)$ with $(q \circ r)(t) = \bigl(\sqrt{t}\bigr)^2 = t \qquad (t \ge 0) ,$ because $\sqrt{t}$ is by definition a number whose square is $t$ . The functions $q \circ r$ and $\operatorname{id}_{[0, \infty)}$ have the same domain, the same codomain and the same value at every point, so $q \circ r = \operatorname{id}_{[0, \infty)}$ by Proposition 2.1.1.

So one order gives an identity function and the other does not. Applying $r$ and then $q$ returns every input; applying $q$ and then $r$ loses the sign. So $q$ undoes $r$ , but $r$ does not undo $q$ .

Second readingComposites defined in one order only

Composition can also fail to be defined in one order only. For $f \colon \{1, 2\} \to \mathbb{R}$ and $g \colon \mathbb{R} \to \mathbb{R}$ , the composite $g \circ f \colon \{1, 2\} \to \mathbb{R}$ is defined, and $f \circ g$ is not: $g$ ’s outputs are real numbers, and $f$ accepts only $1$ and $2$ .

Composition is not commutative, but it is associative, and the identity functions do nothing.

Proposition 2.1.3 (Composition Is Associative)

Let $f \colon X \to Y$ , $g \colon Y \to Z$ , and $h \colon Z \to W$ be functions. Then $h \circ (g \circ f) = (h \circ g) \circ f ,$ and $f \circ \operatorname{id}_X = f = \operatorname{id}_Y \circ f$ .

Proof. Both sides of the first equation are functions from $X$ to $W$ , by Definition 2.1.2. For $x \in X$ , applying Definition 2.1.2 twice on each side gives $\bigl(h \circ (g \circ f)\bigr)(x) = h\bigl((g \circ f)(x)\bigr) = h(g(f(x))) = (h \circ g)(f(x)) = \bigl((h \circ g) \circ f\bigr)(x) .$ So the two functions agree at every point, and they are equal by Proposition 2.1.1. Likewise $f \circ \operatorname{id}_X$ and $\operatorname{id}_Y \circ f$ are functions from $X$ to $Y$ with values $f(\operatorname{id}_X(x)) = f(x)$ and $\operatorname{id}_Y(f(x)) = f(x)$ , so both equal $f$ .

Because of associativity, we write $h \circ g \circ f$ without brackets: every way of bracketing gives the same function, $x \mapsto h(g(f(x)))$ .

The identity functions play for composition the part that the number $1$ plays for multiplication: by the second statement of Proposition 2.1.3, composing with an identity changes nothing. The analogy stops at division. A number $a \ne 0$ can be cancelled from $ab = ac$ ; a function $f$ can be cancelled from $f \circ g = f \circ h$ only under a condition on $f$ . And in Example (Square root after squaring, and squaring after square root), $q \circ r = \operatorname{id}_{[0, \infty)}$ although $r \circ q \ne \operatorname{id}_{\mathbb{R}}$ : one composite of two functions can be an identity while the other is not.

Quick check. Find $h \colon \mathbb{R} \to \mathbb{R}$ with $h \circ g = f$ , for $f(x) = 2x + 3$ and $g(x) = x + 1$ .

Solution. The function $g$ turns $x$ into $y = x + 1$ , and $x$ is recovered as $y - 1$ . So put $h(y) \mathrel{:=} 2(y - 1) + 3 = 2y + 1$ . Check: $h(g(x)) = 2(x + 1) + 1 = 2x + 3 = f(x)$ for every $x$ , so $h \circ g = f$ by Proposition 2.1.1.

Quick check. For $f, g \colon \mathbb{R} \to \mathbb{R}$ , $f(x) = x^2$ and $g(x) = x - 3$ , compute $(g \circ f)(2)$ and $(f \circ g)(2)$ .

Solution. $(g \circ f)(2) = g(4) = 1$ and $(f \circ g)(2) = f(-1) = 1$ . The values agree at this point, but the functions are different: at $x = 0$ , $(g \circ f)(0) = -3$ and $(f \circ g)(0) = 9$ . Agreement at one point proves nothing about equality; disagreement at one point proves inequality.

2.1.5. Exercises

A. Check your understanding

Exercise (A1)

(a) Let $X = \{1, 2, 3\}$ and let $f \colon X \to X$ be given by $f(1) = 2$ , $f(2) = 3$ , $f(3) = 3$ . Write the graph of $f$ , and list the values of $f \circ f$ and $f \circ f \circ f$ .
(b) Which of the formulas $1/(x^2 + 1)$ , $\sqrt{x - 1}$ , $1/(x^2 - 1)$ define a function $\mathbb{R} \to \mathbb{R}$ ? For each that does not, name a point where (Fn1) fails.
(c) Are $f, g \colon \mathbb{Z} \to \mathbb{Z}$ , $f(n) = n^2 - n$ and $g(n) = n(n - 1)$ , equal? Are $h, k \colon \{0, 1\} \to \mathbb{Z}$ , $h(x) = x^2$ and $k(x) = x$ , equal?
(d) How many elements do $\{0\}^{\{1, 2, 3\}}$ and $\emptyset^{\{1\}}$ have? Name them.

Solution.

(a) The graph is $\{ (1, 2), (2, 3), (3, 3) \}$ . For $f \circ f$ : $f(f(1)) = f(2) = 3$ , $f(f(2)) = f(3) = 3$ , $f(f(3)) = f(3) = 3$ , so $f \circ f$ sends every point to $3$ . Then $f \circ f \circ f = f \circ (f \circ f)$ sends every point to $f(3) = 3$ : it is the constant function with value $3$ , and equal to $f \circ f$ .
(b) The formula $1/(x^2 + 1)$ defines a function $\mathbb{R} \to \mathbb{R}$ : $x^2 + 1 \ge 1$ , so the denominator is never $0$ . The formula $\sqrt{x - 1}$ does not: at $x = 0$ it asks for $\sqrt{-1}$ , and no real number has square $-1$ (it fails at every $x < 1$ ). The formula $1/(x^2 - 1)$ does not: it fails at $1$ and at $-1$ , where the denominator is $0$ .
(c) Yes: both have domain and codomain $\mathbb{Z}$ , and $n^2 - n = n(n - 1)$ for every integer $n$ , so $f = g$ by Proposition 2.1.1. Yes again: $h(0) = 0 = k(0)$ and $h(1) = 1 = k(1)$ , so $h$ and $k$ agree at both points of their common domain; two rules, one function.
(d) The set $\{0\}^{\{1, 2, 3\}}$ has exactly one element, the constant function with value $0$ (Example (First functions) (c)). A function $\{1, 2, 3\} \to \{0\}$ must send each of $1$ , $2$ , $3$ to $0$ , so any two such functions agree at every point and are equal by Proposition 2.1.1. The set $\emptyset^{\{1\}}$ has no element: a function $\{1\} \to \emptyset$ would need a value at $1$ (Proposition 2.1.2 (b)).

B. Practice

Exercise (B1: Composites of real functions)

Let $f, g \colon \mathbb{R} \to \mathbb{R}$ , $f(x) = x^2 + 1$ and $g(x) = 2x - 3$ .

(a) Compute $g \circ f$ and $f \circ g$ .
(b) Find every $x \in \mathbb{R}$ with $(g \circ f)(x) = (f \circ g)(x)$ .
(c) Find a function $h \colon \mathbb{R} \to \mathbb{R}$ with $h \circ g = f$ , and check it.

Solution.

(a) By Definition 2.1.2, $(g \circ f)(x) = 2(x^2 + 1) - 3 = 2x^2 - 1$ and $(f \circ g)(x) = (2x - 3)^2 + 1 = 4x^2 - 12x + 10$ .
(b) The equation $2x^2 - 1 = 4x^2 - 12x + 10$ is equivalent to $2x^2 - 12x + 11 = 0$ . Its discriminant is $144 - 88 = 56 = 4 \cdot 14$ , so by the quadratic formula $x = \frac{12 \pm 2\sqrt{14}}{4} = 3 \pm \tfrac12 \sqrt{14} .$ These two numbers are the only points where the composites agree.
(c) The function $g$ turns $x$ into $y = 2x - 3$ , and $x$ is recovered as $(y + 3)/2$ . So put $h(y) \mathrel{:=} \Bigl(\frac{y + 3}{2}\Bigr)^2 + 1 = \frac{y^2 + 6y + 13}{4} .$ Check: for every $x \in \mathbb{R}$ , $h(g(x)) = \Bigl(\frac{(2x - 3) + 3}{2}\Bigr)^2 + 1 = x^2 + 1 = f(x) ,$ and $h \circ g$ and $f$ both go from $\mathbb{R}$ to $\mathbb{R}$ , so $h \circ g = f$ by Proposition 2.1.1.

Exercise (B2: A map of the plane)

Let $s \colon \mathbb{R}^2 \to \mathbb{R}^2$ , $s(x, y) = (x + y, x - y)$ .

(a) Show that $(s \circ s)(x, y) = (2x, 2y)$ for all $x, y \in \mathbb{R}$ .
(b) Find a function $t \colon \mathbb{R}^2 \to \mathbb{R}^2$ with $t \circ s = \operatorname{id}_{\mathbb{R}^2}$ , and check that also $s \circ t = \operatorname{id}_{\mathbb{R}^2}$ . (Hint: solve $u = x + y$ , $v = x - y$ for $x$ and $y$ .)

Solution.

(a) $(s \circ s)(x, y) = s(x + y, x - y) = \bigl((x + y) + (x - y), (x + y) - (x - y)\bigr) = (2x, 2y)$ .
(b) Part (a) suggests halving after applying $s$ . Put $t(u, v) \mathrel{:=} \Bigl(\frac{u + v}{2}, \frac{u - v}{2}\Bigr) .$ Then $t(s(x, y)) = t(x + y, x - y) = (2x/2, 2y/2) = (x, y)$ , and $s(t(u, v)) = \Bigl(\frac{u + v}{2} + \frac{u - v}{2}, \frac{u + v}{2} - \frac{u - v}{2}\Bigr) = (u, v) .$ Each computation compares two pairs coordinate by coordinate (Definition 1.4.1). All four functions go from $\mathbb{R}^2$ to $\mathbb{R}^2$ , so $t \circ s = \operatorname{id}_{\mathbb{R}^2}$ and $s \circ t = \operatorname{id}_{\mathbb{R}^2}$ by Proposition 2.1.1.

Exercise (B3: Families and their values)

(a) Write the family $A_n = [-1/n, 1/n]$ , $n \in \mathbb{Z}_{>0}$ , as a function, naming a codomain.
(b) Give two different families $(A_i)_{i \in \mathbb{N}}$ and $(B_i)_{i \in \mathbb{N}}$ of subsets of $\mathbb{N}$ with the same set of values $\{ \emptyset, \mathbb{N} \}$ .
(c) Is $i \mapsto \{i\}$ a function $\mathbb{N} \to \mathcal{P}\left( \mathbb{N} \right)$ ? A function $\mathbb{N} \to \mathbb{N}$ ?

Solution.

(a) The function $\mathbb{Z}_{>0} \to \mathcal{P}\left( \mathbb{R} \right)$ , $n \mapsto [-1/n, 1/n]$ . Each value is a subset of $\mathbb{R}$ , so it lies in $\mathcal{P}\left( \mathbb{R} \right)$ .
(b) Let $A_i = \emptyset$ for even $i$ and $A_i = \mathbb{N}$ for odd $i$ . Every $i \in \mathbb{N}$ is even or odd, and not both (Theorem 1.1.2), so each $i$ receives exactly one value and (Fn1), (Fn2) hold. Let $B_0 = \emptyset$ and $B_i = \mathbb{N}$ for $i \ge 1$ . Both families have the set of values $\{ \emptyset, \mathbb{N} \}$ . They differ at the index $2$ : $A_2 = \emptyset$ and $B_2 = \mathbb{N}$ . So they are different functions (Proposition 2.1.1) with the same values.
(c) Yes: for each $i \in \mathbb{N}$ , $\{i\} \subseteq \mathbb{N}$ , so $\{i\} \in \mathcal{P}\left( \mathbb{N} \right)$ . No: $\{i\} \notin \mathbb{N}$ , since the elements of $\mathbb{N}$ are numbers and no number is a set (the working convention of Section 1.2). So (Fn1) fails for the codomain $\mathbb{N}$ : the only candidate value at $i$ does not lie in it.

C. Going deeper

Exercise (C1: Functions equal to their own square)

In this exercise, a function $f \colon X \to X$ with $f \circ f = f$ is called idempotent.

(a) Let $f \colon X \to X$ be idempotent. Show that $f(y) = y$ for every $y$ in the range of $f$ .
(b) Show that $x \mapsto \left| x \right|$ on $\mathbb{R}$ is idempotent, and that $x \mapsto -x$ is not.
(c) Find all idempotent functions $\{1, 2\} \to \{1, 2\}$ .

Solution.

(a) Let $y$ be in the range of $f$ : $y = f(x)$ for some $x \in X$ . Then $f(y) = f(f(x)) = (f \circ f)(x) = f(x) = y .$
(b) For every real $x$ , $\left| x \right| \ge 0$ , so $\bigl\lvert \left| x \right| \bigr\rvert = \left| x \right|$ ; the two functions $x \mapsto \bigl\lvert \left| x \right| \bigr\rvert$ and $x \mapsto \left| x \right|$ agree everywhere and are equal by Proposition 2.1.1. For $m(x) = -x$ : $m(m(1)) = -(-1) = 1$ , while $m(1) = -1$ , so $m \circ m \ne m$ .
(c) A function $\{1, 2\} \to \{1, 2\}$ is determined by its two values (Proposition 2.1.1), so there are four: the identity, the constant function with value $1$ , the constant function with value $2$ , and the swap $\sigma$ with $\sigma(1) = 2$ , $\sigma(2) = 1$ . The identity is idempotent by Proposition 2.1.3. A constant function $c$ with value $a$ gives $c(c(x)) = c(a) = a = c(x)$ . The swap is not: $\sigma(\sigma(1)) = \sigma(2) = 1$ , and $\sigma(1) = 2$ . So there are three idempotent functions.

Exercise (C2: Find the error)

“Claim: if $f, g \colon \mathbb{R} \to \mathbb{R}$ and $g \circ f = f \circ g$ , then $f = g$ . Proof: Let $x \in \mathbb{R}$ . Then $g(f(x)) = f(g(x))$ . Cancelling the outer functions on both sides, $f(x) = g(x)$ . So $f = g$ .”

Find the first wrong step, and show that the claim is false.

Solution. The first two steps are correct: $g(f(x)) = f(g(x))$ is the hypothesis $g \circ f = f \circ g$ at the point $x$ . The wrong step is “cancelling the outer functions”. The two sides apply different outer functions, $g$ on the left and $f$ on the right, and nothing licenses passing from an equation $g(a) = f(b)$ to $a = b$ .

The claim is false. Let $f(x) = x + 1$ and $g(x) = x + 2$ . Then $(g \circ f)(x) = (x + 1) + 2 = x + 3$ and $(f \circ g)(x) = (x + 2) + 1 = x + 3$ , so $g \circ f = f \circ g$ by Proposition 2.1.1. But $f(0) = 1 \ne 2 = g(0)$ , so $f \ne g$ .

Marking scheme. (10 points) - 3: locates the step “cancelling the outer functions” as the first wrong one. - 3: says why it fails: the outer functions on the two sides are different, so from $g(a) = f(b)$ one cannot conclude $a = b$ . - 4: a counterexample with both claims checked: the two composites are equal, and $f$ and $g$ differ at a named point.

Fatal errors (0 for the step): blaming the step $g(f(x)) = f(g(x))$ ; a counterexample in which $f \circ g \ne g \circ f$ .