Functions

Squaring a number, reflecting a point and seating each guest at a table are all processes that turn one thing into another, and a proof about any of them needs to know exactly what such a process is and when it can be undone.

The previous lesson made collections precise as sets, with subsets, the Cartesian product $A \times B$ of ordered pairs, and the habit of proving two sets equal by showing each contains the other. A set on its own does nothing, though. This lesson builds processes out of sets, assuming only the lesson on sets, the quantifiers, and the direct, contrapositive and inductive proofs before it. As throughout the course, $ℕ = {1, 2, 3, \dots}$ starts at $1$ .

What a function is

Let $A$ and $B$ be sets. A function $f : A \to B$ is a rule that assigns to each element $a$ of $A$ exactly one element of $B$ , written $f (a)$ and called the value of $f$ at $a$ , or the image of $a$ . The set $A$ is the domain of $f$ and $B$ is its codomain. The words map and mapping mean the same as function. A rule given by a formula is often written with a barred arrow, as in $x \mapsto x^{2}$ , read " $x$ goes to $x^{2}$ ", and the whole function as " $f : ℝ \to ℝ$ , $x \mapsto x^{2}$ ".

"Rule" is informal: it suggests a formula or a procedure, and neither is needed. The previous lesson supplies the formal version.

Definition. A function from $A$ to $B$ consists of the sets $A$ and $B$ together with a subset $G$ of $A \times B$ with the property that for every $a \in A$ there is exactly one $b \in B$ with $(a, b) \in G$ . The set $G$ is the graph of the function, and $f (a)$ names the unique $b$ with $(a, b) \in G$ .

So a function is its table of values, nothing more: a list of pairs (input, output) in which every input appears exactly once. A seating plan that puts each of five guests at one of two tables is a function from the set of guests to the set of tables, as much as $x \mapsto 3 x + 7$ is a function from $ℝ$ to $ℝ$ , and neither is "more" of a function for having a formula. Written out, the condition on $G$ is the conjunction of two quantified statements:

\forall a \in A \exists b \in B ((a, b) \in G) \forall a \in A \forall b, b' \in B (((a, b) \in G \land (a, b') \in G) \Rightarrow b = b')

The first says every element of the domain receives a value; the second says none receives two. A proposed function can fail either, and checking that a rule defines a function means checking both. The second is often called checking that $f$ is well defined, a phrase the next lesson meets again in a sharper form.

The rule "send $x$ to a real number whose square is $x$ " fails both as a function from $ℝ$ to $ℝ$ : at $x = - 1$ there is no such number, and at $x = 4$ there are two. The square root repairs both by shrinking the domain to $[0, \infty)$ and choosing the non-negative root, a convention rather than a discovery. A rule can also fail the second condition in disguise. "Send the fraction $\frac{a}{b}$ to $a$ " looks like a function from $ℚ$ to $ℤ$ , but $\frac{1}{2} = \frac{2}{4}$ , and the rule sends that one rational number to $1$ through one name and to $2$ through the other. Whenever an input can be named in more than one way and the rule reads the name, the second condition needs a proof.

Two functions are equal when they have the same domain, the same codomain, and the same value at every element of the domain; equivalently, the same domain, codomain and graph. So $x \mapsto (x + 1)^{2}$ and $x \mapsto x^{2} + 2 x + 1$ on $ℝ$ are one function written two ways, and to prove two functions $f, g : A \to B$ equal, let $a \in A$ be arbitrary and show $f (a) = g (a)$ .

A few functions appear so often that they have names. The identity on a set $A$ is ${id}_{A} : A \to A$ , ${id}_{A} (a) = a$ , whose graph is the diagonal ${(a, a) : a \in A}$ . If $S \subseteq A$ , the inclusion $ι : S \to A$ is $ι (s) = s$ ; it has the same graph as ${id}_{S}$ but a different codomain, and the next section explains why that makes it a different function. A constant function $A \to B$ sends every element to one fixed $b \in B$ . The projections $A \times B \to A$ , $(a, b) \mapsto a$ , and $A \times B \to B$ , $(a, b) \mapsto b$ , pick out a coordinate.

Two more are functions in disguise. A sequence of real numbers is a function $ℕ \to ℝ$ , with $a_{n}$ written for its value at $n$ , and the sequences of the course's last lesson, on limits, are functions in exactly this sense. For $S \subseteq A$ , the characteristic function $χ_{S} : A \to {0, 1}$ is $1$ on $S$ and $0$ off it. It records the subset $S$ as a function, and Problem 10 shows that subsets of $A$ and functions $A \to {0, 1}$ correspond exactly.

Functions of several variables need no new definition. Addition of real numbers is a function $ℝ \times ℝ \to ℝ$ , $(x, y) \mapsto x + y$ , whose domain happens to be a product, and $f (x, y)$ is shorthand for $f ((x, y))$ .

Is a function really just a set of pairs?

It took mathematics about a century to say yes. For Leonhard Euler, in his Introductio in analysin infinitorum of 1748, a function of a variable was an analytic expression built from the variable and constants: a formula. That view came under strain from Fourier series. Joseph Fourier claimed in the early nineteenth century that quite arbitrary functions, including ones given by different formulas on different intervals, could be written as sums of sines and cosines, and mathematicians had to decide whether such a sum, or a curve drawn freehand, was "one function".

Peter Gustav Lejeune Dirichlet settled the matter in the direction this lesson takes. In a paper of 1837 on Fourier series he said, in substance, that $y$ is a function of $x$ when to each $x$ in an interval there corresponds a definite $y$ , whether or not a single law connects them. His famous example, from 1829, is the function on $ℝ$ that is $1$ at every rational number and $0$ at every irrational one: it has no graph anyone can draw and no formula of the kind Euler meant, and it is a perfectly good function. The fully set-theoretic version, a function as a set of ordered pairs with the "exactly one" condition, became standard in the twentieth century along with the set theory of the previous lesson.

There is one wrinkle, and it is why the definition above says "the sets $A$ and $B$ together with" a graph rather than "a graph". The graph determines the domain, which is the set of first coordinates, but it does not determine the codomain: the graph of $x \mapsto x^{2}$ on $ℝ$ is the same set of pairs whether the codomain is $ℝ$ or $[0, \infty)$ . Some books define a function to be its graph alone and treat the codomain as extra information; most modern ones, and this course, make the codomain part of the function, because the property of being surjective depends on it. The two conventions describe the same mathematics and differ only in bookkeeping.

The ordered pair itself can be defined from sets. Kazimierz Kuratowski's definition of 1921, $(a, b) = {{a}, {a, b}}$ , has the one property pairs need, that $(a, b) = (c, d)$ exactly when $a = c$ and $b = d$ . With it, functions, relations and products are all sets, and set theory can serve as the foundation for the whole of mathematics.

Why the codomain is part of the function

Take the rule $x \mapsto x^{2}$ with two codomains: $s : ℝ \to ℝ$ and $t : ℝ \to [0, \infty)$ , with $s (x) = t (x) = x^{2}$ . They have the same set of pairs, yet they answer one question differently: is every element of the codomain a value? For $t$ it is, since each $y \geq 0$ equals $t (\sqrt{y})$ (square roots exist, as the lesson on the real numbers proves). For $s$ it is not, since no real number squares to $- 1$ .

That question decides, later in this lesson, whether a function can be undone: an inverse of $s$ would have to send $- 1$ somewhere, and there is nowhere to send it. That is why the codomain is recorded as part of the function, why $s$ and $t$ count as different, and why " $x \mapsto x^{2}$ is surjective" is neither true nor false until the codomain is named.

The values a function actually takes form its range, ${f (a) : a \in A}$ , a subset of the codomain. For $s$ and $t$ alike it is $[0, \infty)$ . The codomain is where values may land; the range is where they do. Many books call the range the image of $f$ and write it $f (A)$ , a notation the next section explains. Beware that some older books use "range" for the codomain; when a text's usage matters, check its definition.

The codomain can always be shrunk to the range, or to any set containing it, and the codomain can always be enlarged: if $f : A \to B$ and $B \subseteq C$ , the same graph defines a function $A \to C$ . Shrinking the codomain of $s$ to $[0, \infty)$ produced $t$ . Enlarging a codomain can destroy surjectivity but never create it, and it never changes whether the function is injective (both notions are defined below).

The domain is less flexible. A formula such as $\frac{1}{x}$ does not come with a domain, and "the function $\frac{1}{x}$ " is incomplete until one is chosen. Calculus usually takes the largest set of reals on which the formula makes sense, here $ℝ ∖ {0}$ , and calls it the natural domain, but that is a convention, and a proof must say which domain it means. A statement as simple as " $\frac{1}{x}$ is decreasing" is false on $ℝ ∖ {0}$ (since $- 1 < 1$ and $\frac{1}{- 1} < \frac{1}{1}$ ) and true on $(0, \infty)$ .

Image and preimage

A function acts on elements, and through them on sets of elements. For $f : A \to B$ and $S \subseteq A$ , the image of $S$ is

f (S) = {f (x) : x \in S} = {y \in B : y = f (x) for some x \in S}

the set of values taken on $S$ . For $T \subseteq B$ , the preimage (or inverse image) of $T$ is

f^{- 1} (T) = {x \in A : f (x) \in T}

the set of inputs that land in $T$ . The range is the image of the whole domain, $f (A)$ . The notation carries two traps. First, $f (S)$ uses the same brackets as $f (a)$ with a set in place of an element: $f ({2}) = {f (2)}$ is a set with one element, not the element $f (2)$ . Second, $f^{- 1} (T)$ is a set, and it exists for every function, whether or not $f$ has an inverse. The preimage of a single element is written $f^{- 1} (b)$ for $f^{- 1} ({b})$ and is called the fibre of $f$ over $b$ ; it may be empty, or have one element, or many.

Membership in each is a statement with a quantifier, and proofs use it in that form. For the image the quantifier is existential: $y \in f (S)$ exactly when there is $x \in S$ with $f (x) = y$ . For the preimage there is none: $x \in f^{- 1} (T)$ exactly when $x \in A$ and $f (x) \in T$ . That difference, an "exists" hidden in one definition and absent from the other, explains almost everything in the next section.

With $s (x) = x^{2}$ on $ℝ$ , the image of $[- 1, 2]$ is $[0, 4]$ . Squares of numbers in $[- 1, 2]$ lie between $0$ and $4$ , and each $y$ in $[0, 4]$ is the square of $\sqrt{y} \in [0, 2]$ , so both inclusions hold. The preimage of $[1, 4]$ is $[- 2, - 1] \cup [1, 2]$ , since negative inputs count too, and the preimage of $[- 4, - 1]$ is $\emptyset$ .

Two copies of the graph of y = x². On the left, the inputs from −1 to 2 on the x axis map onto the image from 0 to 4 on the y axis. On the right, the outputs from 1 to 4 pull back to a preimage in two pieces, from −2 to −1 and from 1 to 2, because a number and its negative have the same square.

Computing an image is a small existence proof, and it is easy to get half of it. The claim $s ([- 1, 2]) = [0, 4]$ is an equality of sets, so it needs double inclusion: that every value on $[- 1, 2]$ lies in $[0, 4]$ , and that every element of $[0, 4]$ is actually reached. The first half alone would equally "prove" $s ([- 1, 2]) = [0, 100]$ . A preimage computation is an "if and only if": $x \in s^{- 1} ([1, 4])$ exactly when $1 \leq x^{2} \leq 4$ , exactly when $1 \leq | x | \leq 2$ .

A round trip need not return where it started: the preimage of $T = [- 4, 4]$ under $s$ is $[- 2, 2]$ , whose image is $[0, 4]$ , strictly smaller than $T$ . One inclusion always holds, though.

Example. Let $f : A \to B$ and $T \subseteq B$ . Prove that $f (f^{- 1} (T)) \subseteq T$ .

Let $y \in f (f^{- 1} (T))$ . By the definition of image, $y = f (x)$ for some $x \in f^{- 1} (T)$ . By the definition of preimage, $x \in f^{- 1} (T)$ means $f (x) \in T$ . So $y = f (x) \in T$ , and since $y$ was arbitrary, the inclusion holds.

The reverse fails for $s$ because $- 4 \in T$ is not a value at all. In general $f (f^{- 1} (T)) = T \cap f (A)$ , exactly the part of $T$ that $f$ reaches, so equality holds for every $T$ precisely when every element of $B$ is a value (Problem 6).

Now you. Let $f : A \to B$ and $S \subseteq A$ . Prove that $S \subseteq f^{- 1} (f (S))$ , and find a set $S$ for which the inclusion is strict when $f = s$ .

Answer

Let $x \in S$ . Then $f (x)$ is the value of $f$ at an element of $S$ , so $f (x) \in f (S)$ by the definition of image. By the definition of preimage, an element of $A$ whose value lies in $f (S)$ belongs to $f^{- 1} (f (S))$ , so $x \in f^{- 1} (f (S))$ . Hence $S \subseteq f^{- 1} (f (S))$ . For strictness take $S = [0, 1]$ : then $s (S) = [0, 1]$ and $s^{- 1} ([0, 1]) = [- 1, 1]$ , which contains $- 1 \notin S$ . The round trip collects every input that shares a value with something in $S$ .

Images, preimages and the set operations

Unions, intersections and complements are the tools of the previous lesson, and a first question about any new operation on sets is which of them it respects. For preimages the answer is all of them. For images it is only some, and knowing which is part of knowing what a function is.

Theorem. Let $f : A \to B$ , let $S_{1}, S_{2} \subseteq A$ and let $T, T_{1}, T_{2} \subseteq B$ . Then:

(i) $f^{- 1} (T_{1} \cup T_{2}) = f^{- 1} (T_{1}) \cup f^{- 1} (T_{2})$ ;

(ii) $f^{- 1} (T_{1} \cap T_{2}) = f^{- 1} (T_{1}) \cap f^{- 1} (T_{2})$ ;

(iii) $f^{- 1} (B ∖ T) = A ∖ f^{- 1} (T)$ ;

(iv) $f (S_{1} \cup S_{2}) = f (S_{1}) \cup f (S_{2})$ ;

(v) $f (S_{1} \cap S_{2}) \subseteq f (S_{1}) \cap f (S_{2})$ , and the inclusion can be strict.

Proof. Parts (i) to (iii) are chains of equivalences, each step reversible, so each gives both inclusions at once. For (i), for every $x \in A$ :

x \in f^{- 1} (T_{1} \cup T_{2}) ⟺ f (x) \in T_{1} \cup T_{2} ⟺ f (x) \in T_{1} \lor f (x) \in T_{2} ⟺ x \in f^{- 1} (T_{1}) \cup f^{- 1} (T_{2})

using the definition of preimage, then of union, then of preimage and union again. Part (ii) is the same chain with $\land$ and $\cap$ in place of $\lor$ and $\cup$ . For (iii), for every $x \in A$ , $x \in f^{- 1} (B ∖ T)$ if and only if $f (x) \in B ∖ T$ , if and only if $f (x) \notin T$ (since $f (x) \in B$ automatically), if and only if $x \notin f^{- 1} (T)$ , which for $x \in A$ means $x \in A ∖ f^{- 1} (T)$ .

For (iv), double inclusion. Let $y \in f (S_{1} \cup S_{2})$ , so $y = f (x)$ for some $x \in S_{1} \cup S_{2}$ . If $x \in S_{1}$ then $y \in f (S_{1})$ , and if $x \in S_{2}$ then $y \in f (S_{2})$ ; either way $y \in f (S_{1}) \cup f (S_{2})$ . Conversely, let $y \in f (S_{1}) \cup f (S_{2})$ . If $y \in f (S_{1})$ , then $y = f (x)$ for some $x \in S_{1}$ , and $x \in S_{1} \cup S_{2}$ , so $y \in f (S_{1} \cup S_{2})$ ; the case $y \in f (S_{2})$ is the same with the indices exchanged.

Part (v) is the Example below. $□$

The proofs of (i) to (iii) never needed cases: " $x \in f^{- 1} (\dots)$ " translates directly into " $f (x) \in \dots$ ", and the set operation passes straight through. The same argument works for any family of sets, finite or not. If $T_{i} \subseteq B$ for each $i$ in an index set $I$ , then

f^{- 1} (⋃_{i \in I} T_{i}) = ⋃_{i \in I} f^{- 1} (T_{i}) f^{- 1} (⋂_{i \in I} T_{i}) = ⋂_{i \in I} f^{- 1} (T_{i})

and likewise the image of a union of any family is the union of the images. Both images and preimages also respect inclusion: if $S_{1} \subseteq S_{2}$ then $f (S_{1}) \subseteq f (S_{2})$ , and if $T_{1} \subseteq T_{2}$ then $f^{- 1} (T_{1}) \subseteq f^{- 1} (T_{2})$ . The proofs are one line each.

Example. Let $f : A \to B$ and $S_{1}, S_{2} \subseteq A$ . Prove that $f (S_{1} \cap S_{2}) \subseteq f (S_{1}) \cap f (S_{2})$ , and show that equality can fail.

Let $y \in f (S_{1} \cap S_{2})$ . Then $y = f (x)$ for some $x \in S_{1} \cap S_{2}$ . Since $x \in S_{1}$ , $y = f (x) \in f (S_{1})$ , and since $x \in S_{2}$ , $y \in f (S_{2})$ . So $y \in f (S_{1}) \cap f (S_{2})$ , and as $y$ was arbitrary the inclusion holds.

For the failure, take $s (x) = x^{2}$ on $ℝ$ , $S_{1} = {- 1}$ and $S_{2} = {1}$ . Then $S_{1} \cap S_{2} = \emptyset$ , so $s (S_{1} \cap S_{2}) = \emptyset$ , while $s (S_{1}) = s (S_{2}) = {1}$ and $s (S_{1}) \cap s (S_{2}) = {1}$ .

The attempted proof of the reverse inclusion shows exactly where it breaks. Let $y \in f (S_{1}) \cap f (S_{2})$ . Then $y = f (x_{1})$ for some $x_{1} \in S_{1}$ , and $y = f (x_{2})$ for some $x_{2} \in S_{2}$ . To finish we need one element of $S_{1} \cap S_{2}$ with value $y$ , and all we have is two elements, one in each set, with the same value. If $f$ never sends two different elements to the same value, then $x_{1} = x_{2}$ and the proof goes through; that property is injectivity, defined in the next section, and Problem 5 proves that it is exactly what equality in (v) for all $S_{1}$ and $S_{2}$ requires.

Now you. Let $f : A \to B$ and $S_{1}, S_{2} \subseteq A$ . Prove that $f (S_{1}) ∖ f (S_{2}) \subseteq f (S_{1} ∖ S_{2})$ , and give an example where the inclusion is strict.

Answer

Let $y \in f (S_{1}) ∖ f (S_{2})$ . Then $y \in f (S_{1})$ , so $y = f (x)$ for some $x \in S_{1}$ , and $y \notin f (S_{2})$ . If $x$ were in $S_{2}$ , then $y = f (x)$ would lie in $f (S_{2})$ , which it does not; so $x \notin S_{2}$ . Hence $x \in S_{1} ∖ S_{2}$ and $y = f (x) \in f (S_{1} ∖ S_{2})$ .

For strictness take $s (x) = x^{2}$ on $ℝ$ , $S_{1} = {- 1, 1}$ and $S_{2} = {1}$ . Then $S_{1} ∖ S_{2} = {- 1}$ and $s (S_{1} ∖ S_{2}) = {1}$ , while $s (S_{1}) ∖ s (S_{2}) = {1} ∖ {1} = \emptyset$ . The element $- 1$ survives the difference, but its value is shared with the removed element $1$ .

Taking $S_{1} = A$ in the Now you, and writing $S$ for $S_{2}$ , gives $f (A) ∖ f (S) \subseteq f (A ∖ S)$ : the image of a complement contains the part of the range outside $f (S)$ , and that is all that can be said in general. The image of a complement need not be inside the complement of the image either. With $s$ and $S = [0, \infty)$ , the image of $ℝ ∖ S = (- \infty, 0)$ is $(0, \infty)$ , while $ℝ ∖ s (S) = (- \infty, 0)$ , and these two sets are disjoint.

Why does the preimage respect every set operation when the image does not?

Look at the two definitions side by side. Membership in a preimage, $x \in f^{- 1} (T)$ , is the statement $f (x) \in T$ , with no quantifier. Membership in an image, $y \in f (S)$ , is the statement $\exists x (x \in S \land f (x) = y)$ , with an existential quantifier. Every set operation is a connective in disguise (union is "or", intersection is "and", complement is "not"), so the question is which connectives pass through each definition.

With no quantifier in the way, all of them pass through the preimage: " $f (x) \in T_{1} \cap T_{2}$ " is literally " $f (x) \in T_{1}$ and $f (x) \in T_{2}$ ". The image has to move the connective past "there exists", and the lesson on quantifiers showed which moves are allowed. The existential quantifier distributes over "or": $\exists x (P (x) \lor Q (x))$ is equivalent to $\exists x P (x) \lor \exists x Q (x)$ , and that is part (iv). It does not distribute over "and": $\exists x (P (x) \land Q (x))$ implies $\exists x P (x) \land \exists x Q (x)$ , but not conversely, since the two witnesses on the right may be different objects. That is part (v), and the counterexample with $- 1$ and $1$ is exactly two different witnesses. Negation fails worst of all, because "not exists" is "for all not", a different kind of statement.

This is more than bookkeeping. The preimage turns $f : A \to B$ into a function $P (B) \to P (A)$ , $T \mapsto f^{- 1} (T)$ , which runs backwards and preserves unions, intersections and complements: in the language of algebra it is a homomorphism of Boolean algebras. Much of later mathematics is built on it. In topology a function between spaces is defined to be continuous when the preimage of every open set is open, and in measure theory a function is measurable when preimages of measurable sets are measurable. Both definitions use preimages rather than images for the reason given here: conditions stated through preimages are automatically compatible with unions, intersections and complements, so they combine well. For functions on $ℝ$ , the preimage definition of continuity turns out to be equivalent to the $ε$ , $δ$ definition met in the course's last lesson.

Injective, surjective and bijective

A function $f : A \to B$ is injective, or one-to-one, when distinct inputs give distinct outputs: for all $a, a' \in A$ , if $a \neq a'$ then $f (a) \neq f (a')$ . The useful form is the contrapositive: for all $a, a' \in A$ , if $f (a) = f (a')$ then $a = a'$ . The proof template is "Let $a, a' \in A$ with $f (a) = f (a')$ ", then algebra, then "so $a = a'$ ". To disprove it, one pair suffices: $s (2) = s (- 2)$ and $2 \neq - 2$ .

A classic slip is to prove the converse, "if $a = a'$ then $f (a) = f (a')$ ". That is true of every function, since it is the "none receives two values" half of the definition, so a proof of it says nothing about injectivity.

It is surjective, or onto, when every element of the codomain is a value: for every $b \in B$ there exists $a \in A$ with $f (a) = b$ . Equivalently, the range $f (A)$ is all of $B$ . The template follows the quantifiers: "Let $b \in B$ . Put $a = \dots$ ", then check that $a \in A$ and $f (a) = b$ . The formula for $a$ comes from scratch work solving $f (a) = b$ , which is not part of the proof; the check that $a$ lies in the domain is, and it is the step most often forgotten. To disprove it, name one $b$ and prove that $f (a) = b$ has no solution in $A$ .

It is bijective, a bijection or a one-to-one correspondence, when it is both, so that each $b \in B$ is the value of exactly one $a \in A$ . The three properties have a compact description through fibres. For each $b \in B$ , the fibre $f^{- 1} (b)$ is the set of inputs with value $b$ . Then $f$ is injective when every fibre has at most one element, surjective when every fibre has at least one, and bijective when every fibre has exactly one. For a function on $ℝ$ drawn as a graph, the fibre over $b$ is where the horizontal line at height $b$ meets the graph, which is the "horizontal line test" of school.

The properties are independent. The map $d : ℕ \to ℕ$ , $d (n) = 2 n$ , is injective, since $2 m = 2 n$ gives $m = n$ , but not surjective, since $2 n = 1$ forces $n = \frac{1}{2} \notin ℕ$ . With the even natural numbers as codomain, the same rule is a bijection. The function $t : ℝ \to [0, \infty)$ , $x \mapsto x^{2}$ , is surjective and not injective, and $s$ is neither. The identity on any set is a bijection.

Example. Prove that $f : ℝ \to ℝ$ , $f (x) = 3 x + 7$ , is a bijection.

Injective: let $a, a' \in ℝ$ with $f (a) = f (a')$ . Then $3 a + 7 = 3 a' + 7$ , so $3 a = 3 a'$ , and dividing by $3$ gives $a = a'$ . Surjective: let $b \in ℝ$ and put $a = \frac{b - 7}{3}$ . This is a real number, and $f (a) = 3 \cdot \frac{b - 7}{3} + 7 = b$ . So $f$ is injective and surjective, hence a bijection.

On the integers the same rule, $n \mapsto 3 n + 7$ from $ℤ$ to $ℤ$ , is injective by the same argument but not surjective: $3 n + 7 = 0$ needs $n = - \frac{7}{3}$ , not an integer. The membership check is exactly where the two cases part.

Now you. Let $h : ℝ ∖ {1} \to ℝ ∖ {2}$ be given by $h (x) = \frac{2 x}{x - 1}$ . Show that $h$ never takes the value $2$ , so that it is a function into $ℝ ∖ {2}$ , and prove that it is a bijection.

Answer

Values: $\frac{2 x}{x - 1} = 2$ would give $2 x = 2 x - 2$ , which is false. Injective: let $a, a' \neq 1$ with $\frac{2 a}{a - 1} = \frac{2 a'}{a' - 1}$ . Clearing denominators, $2 a a' - 2 a = 2 a a' - 2 a'$ , so $a = a'$ . Surjective: let $b \neq 2$ and put $a = \frac{b}{b - 2}$ , defined since $b \neq 2$ . It is not $1$ , since $\frac{b}{b - 2} = 1$ would give $b = b - 2$ . And

h (a) = \frac{\frac{2 b}{b - 2}}{\frac{b}{b - 2} - 1} = \frac{\frac{2 b}{b - 2}}{\frac{2}{b - 2}} = b

So $h$ is a bijection. Both excluded points were forced: $1$ because the formula fails there, $2$ because it is never reached.

For functions between sets of real numbers, one sufficient condition for injectivity is used constantly. A function $f : A \to ℝ$ with $A \subseteq ℝ$ is strictly increasing if $x < y$ implies $f (x) < f (y)$ for all $x, y \in A$ , and strictly decreasing if $x < y$ implies $f (x) > f (y)$ .

Proposition. A strictly increasing or strictly decreasing function on a set of real numbers is injective.

Proof. Let $f$ be strictly increasing, and let $x \neq y$ be in its domain. The statement is symmetric in $x$ and $y$ , so without loss of generality $x < y$ . Then $f (x) < f (y)$ , so $f (x) \neq f (y)$ . The decreasing case is the same with the inequality reversed. $□$

So $x \mapsto x^{3}$ is injective on $ℝ$ : if $x < y$ then $y^{3} - x^{3} = (y - x) (y^{2} + x y + x^{2})$ , and the second factor is $(y + \frac{x}{2})^{2} + \frac{3 x^{2}}{4}$ , which is positive unless $x = y = 0$ , which cannot happen when $x < y$ . The converse of the proposition fails: $x \mapsto \frac{1}{x}$ on $ℝ ∖ {0}$ is injective, since $\frac{1}{x} = \frac{1}{y}$ gives $x = y$ , but it is neither increasing nor decreasing, as the section on the codomain showed. Proving that $x \mapsto x^{3}$ is also surjective on $ℝ$ , that every real number has a real cube root, needs the completeness of the real numbers, which the lesson on the real numbers uses to prove that $\sqrt{2}$ exists; the argument for cube roots is the same.

Composition

Given $f : A \to B$ and $g : B \to C$ , the composite $g \circ f : A \to C$ is defined by $(g \circ f) (a) = g (f (a))$ , read " $g$ after $f$ ": $f$ runs first. The composite exists only when the codomain of $f$ is the domain of $g$ (or, more loosely, when the range of $f$ lies inside the domain of $g$ ), so that every value of $f$ is something $g$ can act on.

Order matters. With $f (x) = x + 1$ and $g (x) = x^{2}$ on $ℝ$ , $(g \circ f) (x) = (x + 1)^{2}$ and $(f \circ g) (x) = x^{2} + 1$ , so $(g \circ f) (1) = 4$ while $(f \circ g) (1) = 2$ . When the sets differ, one composite may exist and the other not: with $f : ℕ \to ℤ$ and $g : ℤ \to {0, 1}$ , $g \circ f$ makes sense and $f \circ g$ does not.

Proposition. Let $f : A \to B$ , $g : B \to C$ and $h : C \to D$ . Then

(i) $h \circ (g \circ f) = (h \circ g) \circ f$ ;

(ii) $f \circ {id}_{A} = f$ and ${id}_{B} \circ f = f$ .

Proof. Both sides of (i) are functions from $A$ to $D$ , so it is enough to compare values. For $a \in A$ , $(h \circ (g \circ f)) (a) = h ((g \circ f) (a)) = h (g (f (a)))$ , and $((h \circ g) \circ f) (a) = (h \circ g) (f (a)) = h (g (f (a)))$ . For (ii), $(f \circ {id}_{A}) (a) = f (a)$ and $({id}_{B} \circ f) (a) = f (a)$ for every $a \in A$ . $□$

Associativity means brackets can be dropped, and $h \circ g \circ f$ has one meaning: apply $f$ , then $g$ , then $h$ . Composition behaves like a multiplication with identities but without commutativity, which is how it reappears in algebra, where matrices multiply because the linear maps they represent compose.

Example. Prove that if $f : A \to B$ and $g : B \to C$ are injective, then $g \circ f$ is injective.

Let $a, a' \in A$ with $g (f (a)) = g (f (a'))$ . The elements $f (a)$ and $f (a')$ of $B$ have the same value under $g$ , and $g$ is injective, so $f (a) = f (a')$ . Since $f$ is injective, $a = a'$ . So $g \circ f$ is injective.

The proof peels the functions off from the outside in.

Now you. Prove that if $f : A \to B$ and $g : B \to C$ are surjective, then $g \circ f$ is surjective.

Answer

Let $c \in C$ . Since $g$ is surjective, there is $b \in B$ with $g (b) = c$ . Since $f$ is surjective, there is $a \in A$ with $f (a) = b$ . Then $(g \circ f) (a) = g (f (a)) = g (b) = c$ , so $g \circ f$ is surjective. Again the proof works from the outside in, finding $b$ before $a$ .

Together the two results say that a composite of bijections is a bijection. The converses hold only in part, and each half is worth knowing exactly.

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

(i) If $g \circ f$ is injective, then $f$ is injective.

(ii) If $g \circ f$ is surjective, then $g$ is surjective.

Proof. (i) Let $a, a' \in A$ with $f (a) = f (a')$ . Applying $g$ gives $g (f (a)) = g (f (a'))$ , and since $g \circ f$ is injective, $a = a'$ .

(ii) Let $c \in C$ . Since $g \circ f$ is surjective, there is $a \in A$ with $g (f (a)) = c$ . Put $b = f (a)$ , an element of $B$ . Then $g (b) = c$ . $□$

The other halves fail. Let $f : [0, \infty) \to ℝ$ be the inclusion, $f (x) = x$ , and $g = s$ , squaring on $ℝ$ . Then $g \circ f$ is $x \mapsto x^{2}$ on $[0, \infty)$ , which is injective (it is strictly increasing there), yet $g$ is not injective. The fault is that $g$ is only ever applied to values of $f$ , and the values where $g$ misbehaves, the negative numbers, are never reached. Similarly, with $f : ℝ \to ℝ$ , $f (x) = x^{2}$ , and $g : ℝ \to [0, \infty)$ , $g (x) = | x |$ , the composite $x \mapsto x^{2}$ from $ℝ$ to $[0, \infty)$ is surjective, while $f$ is not. So if $g \circ f$ is a bijection, all that follows is that $f$ is injective and $g$ is surjective; Problem 8 shows that nothing more follows without further hypotheses.

Inverses

To undo $f : A \to B$ is to have a function going back that cancels it from both sides. A function $g : B \to A$ is an inverse of $f$ when

g \circ f = {id}_{A} and f \circ g = {id}_{B}

that is, $g (f (a)) = a$ for every $a \in A$ and $f (g (b)) = b$ for every $b \in B$ . A function with an inverse is called invertible. The two conditions do different jobs, and the theorem that says which functions have inverses shows exactly how.

Theorem. A function $f : A \to B$ has an inverse if and only if it is a bijection.

Proof. ( $\Rightarrow$ ) Suppose $g : B \to A$ is an inverse of $f$ . For injectivity, let $a, a' \in A$ with $f (a) = f (a')$ . Applying $g$ gives $a = g (f (a)) = g (f (a')) = a'$ . For surjectivity, let $b \in B$ and put $a = g (b)$ , an element of $A$ . Then $f (a) = f (g (b)) = b$ . So $f$ is a bijection.

( $\Leftarrow$ ) Suppose $f$ is a bijection. For each $b \in B$ , surjectivity gives some $a \in A$ with $f (a) = b$ , and injectivity says there is only one. Let $g (b)$ be that $a$ . This assigns exactly one element of $A$ to each $b \in B$ , so $g : B \to A$ is a function; in terms of graphs, the graph of $g$ is ${(b, a) : (a, b) \in G}$ , the graph of $f$ with each pair reversed, and bijectivity is precisely what makes this reversed set satisfy the "exactly one" condition. By construction $f (g (b)) = b$ for every $b \in B$ . For $a \in A$ , $g (f (a))$ is the unique element of $A$ with value $f (a)$ , and $a$ is such an element, so $g (f (a)) = a$ . Hence $g$ is an inverse of $f$ . $□$

In the forward direction, $g \circ f = {id}_{A}$ forced injectivity and $f \circ g = {id}_{B}$ forced surjectivity. Neither alone is enough, as the next section shows.

Proposition. Let $f : A \to B$ .

(i) If $f$ has an inverse, it has only one.

(ii) If $g$ is the inverse of $f$ , then $g$ is a bijection and $f$ is the inverse of $g$ .

(iii) If $f : A \to B$ and $h : B \to C$ are bijections, then $h \circ f$ is a bijection, and its inverse is $f^{- 1} \circ h^{- 1}$ .

Proof. (i) Let $g$ and $k$ both be inverses of $f$ . Using associativity and both halves of the definition,

g = g \circ {id}_{B} = g \circ (f \circ k) = (g \circ f) \circ k = {id}_{A} \circ k = k

(ii) The two equations $g \circ f = {id}_{A}$ and $f \circ g = {id}_{B}$ , read with the roles of $f$ and $g$ exchanged, say that $f$ is an inverse of $g$ . By the theorem, $g$ is then a bijection.

(iii) By the associativity of composition,

(f^{- 1} \circ h^{- 1}) \circ (h \circ f) = f^{- 1} \circ (h^{- 1} \circ h) \circ f = f^{- 1} \circ {id}_{B} \circ f = f^{- 1} \circ f = {id}_{A}

and in the same way $(h \circ f) \circ (f^{- 1} \circ h^{- 1}) = h \circ {id}_{B} \circ h^{- 1} = {id}_{C}$ . So $f^{- 1} \circ h^{- 1}$ is an inverse of $h \circ f$ , which is therefore a bijection by the theorem. $□$

By (i) the inverse earns a name, $f^{- 1}$ . For $f (x) = 3 x + 7$ on $ℝ$ it is $f^{- 1} (y) = \frac{y - 7}{3}$ , the formula the surjectivity proof already found. The order reversal in (iii) is the rule of socks and shoes: socks go on first and shoes second, so to undo the process the shoes come off first.

The symbol $f^{- 1}$ now has two meanings, the preimage of a set under any function and the inverse function of a bijection, and they agree wherever both make sense. If $f$ is a bijection and $T \subseteq B$ , then $x \in f^{- 1} (T)$ (preimage) means $f (x) \in T$ , which, applying the inverse, means $x = f^{- 1} (y)$ for some $y \in T$ , that is, $x$ lies in the image of $T$ under the function $f^{- 1}$ . So the clash is harmless, as long as the preimage is never mistaken for evidence that an inverse exists.

A bijection from a set to itself is also called a permutation of the set. The permutations of a set $A$ are closed under composition and inverses and include ${id}_{A}$ , which makes them the first example of a group; for a set of $n$ elements there are $n!$ of them, as the section on counting shows.

Left and right inverses

Splitting the definition of an inverse in two gives two weaker notions. Let $f : A \to B$ . A function $g : B \to A$ is a left inverse of $f$ if $g \circ f = {id}_{A}$ , and a right inverse of $f$ if $f \circ g = {id}_{B}$ . (The names follow the side on which $g$ is written in the composite.) A left inverse undoes $f$ : apply $f$ , then $g$ , and you are back where you started. A right inverse is undone by $f$ : $g$ picks, for each $b$ , an input that $f$ sends back to $b$ .

Theorem. Let $f : A \to B$ .

(i) If $A$ is not empty, then $f$ is injective if and only if it has a left inverse.

(ii) $f$ is surjective if and only if it has a right inverse.

(iii) If $f$ has a left inverse $g$ and a right inverse $h$ , then $g = h$ , and $f$ is a bijection with inverse $g$ .

Proof. (i) ( $\Leftarrow$ ) If $g \circ f = {id}_{A}$ and $f (a) = f (a')$ , then $a = g (f (a)) = g (f (a')) = a'$ , as in the proof of the previous theorem. ( $\Rightarrow$ ) Suppose $f$ is injective. Since $A$ is not empty, fix an element $a_{0} \in A$ . Define $g : B \to A$ by cases. If $b$ lies in the range $f (A)$ , there is an $a \in A$ with $f (a) = b$ , and by injectivity only one, so let $g (b)$ be that $a$ . If $b \notin f (A)$ , let $g (b) = a_{0}$ . Every $b \in B$ falls in exactly one case and receives exactly one value, so $g$ is a function. For $a \in A$ , the element $f (a)$ lies in the range, and $a$ is the unique element with value $f (a)$ , so $g (f (a)) = a$ . Hence $g \circ f = {id}_{A}$ .

(ii) ( $\Leftarrow$ ) If $f \circ g = {id}_{B}$ and $b \in B$ , put $a = g (b)$ ; then $f (a) = f (g (b)) = b$ . ( $\Rightarrow$ ) Suppose $f$ is surjective. For each $b \in B$ the fibre $f^{- 1} (b)$ is not empty; choose an element of it and call it $g (b)$ . Then $g : B \to A$ is a function, and $f (g (b)) = b$ for every $b$ , because $g (b)$ lies in the fibre over $b$ . Hence $f \circ g = {id}_{B}$ .

(iii) Using associativity, $g = g \circ {id}_{B} = g \circ (f \circ h) = (g \circ f) \circ h = {id}_{A} \circ h = h$ . So $g$ satisfies both $g \circ f = {id}_{A}$ and $f \circ g = {id}_{B}$ , and it is an inverse of $f$ ; by the previous theorem $f$ is a bijection. $□$

The hypothesis in (i) is needed only for a technical reason, and the reason is instructive. The empty function $\emptyset \to B$ is injective, because the condition "if $f (a) = f (a')$ then $a = a'$ " has no instances to fail. A left inverse would be a function $B \to \emptyset$ , and if $B$ has an element there is nowhere to send it. So the empty function into a non-empty set is injective with no left inverse, and the theorem has to exclude it.

Left and right inverses, unlike two-sided ones, are usually far from unique, and the Example shows how many there can be.

Example. Let $d : ℕ \to ℕ$ , $d (n) = 2 n$ , as before. Describe all left inverses of $d$ , and show that none of them is a right inverse.

A function $e : ℕ \to ℕ$ is a left inverse exactly when $e (d (n)) = n$ for every $n$ , that is, when $e (2 n) = n$ for every natural number $n$ . This fixes $e$ on the even numbers, where it must halve, and says nothing about the odd ones. So the left inverses of $d$ are exactly the functions

e (m) = {\begin{matrix} \frac{m}{2} & if m is even \\ φ (m) & if m is odd \end{matrix}

where $φ$ is any function from the odd natural numbers to $ℕ$ . For instance $φ (m) = 1$ and $φ (m) = m$ give two different left inverses. None of them is a right inverse: for every left inverse $e$ , the value $d (e (1)) = 2 e (1)$ is even, so it is not $1$ , and $d \circ e \neq {id}_{ℕ}$ . That agrees with the theorem, since $d$ is injective and not surjective.

Now you. Let $q : ℤ \to ℤ$ send $n$ to its quotient on division by $2$ , so that $n = 2 q (n) + r$ with $r \in {0, 1}$ . Show that $q$ is surjective, find two different right inverses of $q$ , and show that $q$ has no left inverse.

Answer

By the division algorithm, $q$ is a function: each integer has exactly one quotient. The fibre over $m \in ℤ$ is $q^{- 1} (m) = {2 m, 2 m + 1}$ , because $2 m = 2 m + 0$ and $2 m + 1 = 2 m + 1$ are divisions with remainder in range, so both have quotient $m$ , and any $n$ with quotient $m$ equals $2 m + r$ with $r \in {0, 1}$ . Every fibre is non-empty, so $q$ is surjective.

A right inverse must choose one element of each fibre. Let $g_{1} (m) = 2 m$ and $g_{2} (m) = 2 m + 1$ . Then $q (g_{1} (m)) = m$ and $q (g_{2} (m)) = m$ for every $m$ , so both are right inverses, and they differ, for instance $g_{1} (0) = 0 \neq 1 = g_{2} (0)$ . Mixing the choices, say $2 m$ for even $m$ and $2 m + 1$ for odd $m$ , gives infinitely many more.

A left inverse would make $q$ injective, by part (i) of the theorem. But $q (0) = q (1) = 0$ with $0 \neq 1$ , so $q$ is not injective and has no left inverse.

What does "choose an element of each fibre" rely on?

In the Now you nothing was really chosen: the fibres were written down, and "take the smaller element" is a rule. The same works for any surjection whose domain is $ℕ$ , since the well-ordering principle gives every non-empty fibre a least element, and "send $b$ to the least element of its fibre" defines a right inverse outright. The proof of part (ii) of the theorem, though, said "choose an element of each fibre" for an arbitrary surjection, possibly with infinitely many fibres and no rule to pick from any of them. That is an infinite number of arbitrary choices made at once, and none of the principles used so far licenses it.

The principle that does is the axiom of choice: for every family of non-empty sets, there is a function picking one element from each. Ernst Zermelo stated it explicitly in 1904, to prove that every set can be well-ordered, and it was controversial at once, precisely because it asserts that a function exists without describing it. Bertrand Russell's illustration is well known: from infinitely many pairs of shoes one can choose one shoe from each pair by a rule ("take the left one"), but from infinitely many pairs of socks, where the two members of a pair cannot be told apart, no rule is available, and the axiom is needed to say that a choice exists at all.

The statement "every surjection has a right inverse" is not merely a consequence of the axiom of choice; it is equivalent to it. Given a family of non-empty sets $X_{i}$ , the function sending each pair $(i, x)$ with $x \in X_{i}$ to its index $i$ is a surjection onto the index set, and a right inverse picks, for each $i$ , a pair $(i, x)$ with $x \in X_{i}$ , which is exactly a choice of one element from each set. So part (ii) of the theorem cannot be proved without the axiom.

Kurt Gödel showed in 1938 that adding the axiom of choice to the other axioms of set theory cannot produce a contradiction unless they already contain one, and Paul Cohen showed in 1963 that the same is true of adding its negation. So the axiom is independent of the others: they neither prove nor refute it. Almost all of mainstream mathematics accepts it, and much of analysis and algebra uses it, often in the form of Zorn's lemma, which the lesson on order states. The left-inverse half of the theorem needs no such axiom: there the only choice is the single element $a_{0}$ , and choosing one element from one non-empty set is ordinary logic.

Restriction

Many useful functions are not injective, and most of them become injective once part of the domain is discarded. Let $f : A \to B$ and $S \subseteq A$ . The restriction of $f$ to $S$ is the function $f |_{S} : S \to B$ given by $f |_{S} (x) = f (x)$ for $x \in S$ . Its graph is the part of the graph of $f$ lying over $S$ , and in terms of composition $f |_{S} = f \circ ι$ , where $ι : S \to A$ is the inclusion. Conversely, when $g = f |_{S}$ we call $f$ an extension of $g$ to $A$ .

Restriction keeps some properties and changes others. The range of $f |_{S}$ is $f (S)$ , the image of $S$ , which is how images and restrictions are tied together. If $f$ is injective, so is every restriction, since a pair of inputs in $S$ with the same value is a pair in $A$ with the same value; formally, $f \circ ι$ is a composite of injections. Surjectivity is usually lost, and injectivity is often gained: $s (x) = x^{2}$ is not injective on $ℝ$ , but $s |_{[0, \infty)}$ is, because $x^{2}$ is strictly increasing on $[0, \infty)$ .

Restricting the domain and shrinking the codomain to the range together turn a function into a bijection whenever the restriction is injective. If $f : A \to B$ is injective, then the same rule, viewed as a function $A \to f (A)$ , is surjective by the definition of the range and injective because $f$ is, so it is a bijection. This is how the classical inverse functions are made. The square root is the inverse of $x \mapsto x^{2}$ restricted to $[0, \infty)$ with codomain $[0, \infty)$ . The function $\arcsin$ is the inverse of $\sin$ restricted to $[- \frac{π}{2}, \frac{π}{2}]$ , with codomain $[- 1, 1]$ ; other intervals would have done, and the choice of that one is a convention, like the choice of the non-negative square root.

Example. Let $p : ℝ \to ℝ$ , $p (x) = x^{2} - 4 x + 1$ . Show that $p$ is not injective, and prove that its restriction to $[2, \infty)$ , with codomain $[- 3, \infty)$ , is a bijection. Find its inverse.

Completing the square, $p (x) = (x - 2)^{2} - 3$ . So $p (0) = 1 = p (4)$ , and $p$ is not injective on $ℝ$ : the graph is symmetric about the line $x = 2$ .

Let $P : [2, \infty) \to [- 3, \infty)$ be the restriction, with the smaller codomain. It is a function into $[- 3, \infty)$ , since $(x - 2)^{2} \geq 0$ gives $P (x) \geq - 3$ . Injective: let $a, a' \geq 2$ with $P (a) = P (a')$ . Then $(a - 2)^{2} = (a' - 2)^{2}$ , and both $a - 2$ and $a' - 2$ are non-negative. Two non-negative numbers with the same square are equal (if $u, v \geq 0$ and $u^{2} = v^{2}$ , then $(u - v) (u + v) = 0$ , so $u = v$ , or $u + v = 0$ , which forces $u = v = 0$ ). So $a - 2 = a' - 2$ and $a = a'$ . Surjective: let $y \geq - 3$ and put $a = 2 + \sqrt{y + 3}$ , defined because $y + 3 \geq 0$ . Then $a \geq 2$ , so $a$ is in the domain, and $P (a) = (\sqrt{y + 3})^{2} - 3 = y$ . So $P$ is a bijection, and the element with value $y$ is $2 + \sqrt{y + 3}$ , which gives $P^{- 1} (y) = 2 + \sqrt{y + 3}$ .

The restriction to $(- \infty, 2]$ would have worked as well, with inverse $y \mapsto 2 - \sqrt{y + 3}$ . Each half of the parabola carries its own inverse.

Now you. Let $f : ℝ \to ℝ$ , $f (x) = x^{2} + 2 x$ . Prove that the restriction of $f$ to $(- \infty, - 1]$ , with codomain $[- 1, \infty)$ , is a bijection, and find its inverse.

Answer

Completing the square, $f (x) = (x + 1)^{2} - 1$ , so every value is at least $- 1$ and the restriction $F : (- \infty, - 1] \to [- 1, \infty)$ is a function.

Injective: let $a, a' \leq - 1$ with $F (a) = F (a')$ . Then $(a + 1)^{2} = (a' + 1)^{2}$ . Here $a + 1 \leq 0$ and $a' + 1 \leq 0$ , so $- (a + 1)$ and $- (a' + 1)$ are non-negative numbers with the same square, hence equal, and $a = a'$ .

Surjective: let $y \geq - 1$ and put $a = - 1 - \sqrt{y + 1}$ , defined because $y + 1 \geq 0$ . Then $a \leq - 1$ , so $a$ is in the domain, and $F (a) = (- \sqrt{y + 1})^{2} - 1 = y$ .

So $F$ is a bijection with inverse $F^{- 1} (y) = - 1 - \sqrt{y + 1}$ . The minus sign in front of the root is forced by the choice of the left half of the parabola; the plus sign would give a number outside the domain whenever $y > - 1$ .

Going the other way, a function can be built on a set piece by piece and then glued. Suppose $A = S \cup T$ , and $g : S \to B$ and $h : T \to B$ agree on the overlap, meaning $g (x) = h (x)$ for every $x \in S \cap T$ . Then there is exactly one function $f : A \to B$ with $f |_{S} = g$ and $f |_{T} = h$ : its graph is the union of the graphs of $g$ and $h$ . Each $x \in A$ lies in $S$ or $T$ , so it receives a value; if it lies in both, the two values agree, so it receives only one. This is what justifies a definition by cases, such as $| x | = x$ for $x \geq 0$ and $| x | = - x$ for $x \leq 0$ : the pieces overlap at $0$ , and there they agree. Where pieces overlap and disagree, as in " $f (x) = 1$ for $x \geq 0$ and $f (x) = 2$ for $x \leq 0$ ", no function has been defined.

Counting functions between finite sets

For finite sets the three properties can be counted, and the counts explain a good deal. Write $| A |$ for the number of elements of a finite set $A$ .

Theorem. Let $| A | = m$ and $| B | = n$ .

(i) There are $n^{m}$ functions from $A$ to $B$ .

(ii) There are $n (n - 1) (n - 2) \dots (n - m + 1)$ injections from $A$ to $B$ , a product of $m$ factors; in particular there are none when $m > n$ .

(iii) There are $n!$ bijections from $A$ to $B$ when $m = n$ , and none otherwise.

Proof. (i) By induction on $m$ . When $m = 0$ , $A = \emptyset$ , and there is exactly one function from $\emptyset$ to $B$ , since its graph must be a subset of $\emptyset \times B = \emptyset$ , and the empty graph satisfies the "exactly one" condition vacuously; and $n^{0} = 1$ . Suppose the count is right for sets of $m$ elements, and let $| A | = m + 1$ . Fix $a \in A$ and put $A' = A ∖ {a}$ , with $m$ elements. A function $f : A \to B$ is determined by the pair $(f |_{A'}, f (a))$ , and every pair $(g, b)$ with $g : A' \to B$ and $b \in B$ arises from exactly one $f$ , by the gluing principle of the previous section. So the functions $A \to B$ correspond exactly to the elements of the product of the set of functions $A' \to B$ with $B$ , which by the product rule of the previous lesson has $n^{m} \cdot n = n^{m + 1}$ elements.

(ii) The same induction, with one change. An injection $f : A \to B$ is determined by the pair $(f |_{A'}, f (a))$ , where $f |_{A'}$ is an injection and $f (a)$ must avoid its $m$ values: $n - m$ choices for each of the $n (n - 1) \dots (n - m + 1)$ injections $A' \to B$ . That gives $n (n - 1) \dots (n - m + 1) (n - m)$ , the formula for $m + 1$ . When $m > n$ , the factor $n - n = 0$ appears in the product, so the count is $0$ .

(iii) If $m = n$ , the theorem below shows that the bijections are exactly the injections, and there are $n (n - 1) \dots 1 = n!$ of them. If $m \neq n$ , a bijection $A \to B$ would make the two sets the same size, which the counts of values forbid: an injection needs $m \leq n$ by (ii), and a surjection needs $m \geq n$ , since $m$ inputs take at most $m$ values. $□$

The product $n (n - 1) \dots (n - m + 1)$ is a falling factorial, and it counts ordered selections without repetition, the subject of the Discrete Mathematics lesson on arrangements. The statement that there is no injection from a set of $m$ elements into a set of $n < m$ elements is the pigeonhole principle: put more than $n$ letters into $n$ pigeonholes and some pigeonhole receives two. The lesson on contrapositive and contradiction uses it as a tool; here it has appeared as a count.

A computer listing every function on small sets agrees. From a 3-element set to a 4-element set there are $4^{3} = 64$ functions, of which $4 \cdot 3 \cdot 2 = 24$ are injective. From a 4-element set to itself there are $256$ , and exactly $24 = 4!$ are injective, the same $24$ that are surjective. The falling factorial also settles the birthday problem: of the $365^{23}$ ways to give 23 people birthdays, ignoring 29 February, the injective fraction is $\frac{365 \cdot 364 \dots 343}{365^{23}} \approx 0.493$ , so a shared birthday is more likely than not.

Counting surjections is harder, since there is no single running choice to count, and it needs inclusion and exclusion. For small sets it can be done by hand: a surjection from a 4-element set onto a 3-element set must send exactly two elements to one value and one element to each of the other two, and Problem 11 counts them.

What is a function from the empty set?

Exactly one, for every set $B$ , including $B = \emptyset$ : its graph is the empty set, and the condition on graphs holds vacuously, since there is no element of $\emptyset$ for it to fail at. It is called the empty function.

A function from a non-empty set $A$ to $\emptyset$ is another matter: an element $a \in A$ needs a value in $\emptyset$ , and there is none. So there are no functions from a non-empty set to the empty set.

These are exactly the values of $n^{m}$ that the counting formula needs. The number of functions $\emptyset \to B$ with $| B | = n$ is $n^{0} = 1$ , and the number of functions $A \to \emptyset$ with $| A | = m \geq 1$ is $0^{m} = 0$ . The single case $m = n = 0$ gives one function, the empty function from $\emptyset$ to itself, and this is one of the reasons mathematicians working with finite sets take $0^{0} = 1$ . Likewise $0! = 1$ counts the one bijection from $\emptyset$ to itself.

The empty function is injective, since there is no pair of inputs to collide, and surjective only onto $\emptyset$ ; it is why part (i) of the theorem on left inverses needs $A$ to be non-empty. Cases like this look like pedantry, but they are what let formulas such as $n^{m}$ and $2^{n}$ hold without exceptions.

For sets of the same finite size, the counts show that injective and surjective come together, and there is a direct proof.

Theorem. Let $A$ and $B$ be finite sets with $| A | = | B |$ , and let $f : A \to B$ . Then $f$ is injective if and only if it is surjective, and so if and only if it is a bijection.

Proof. Let $| A | = | B | = n$ .

( $\Rightarrow$ ) Suppose $f$ is injective. Its $n$ values at the $n$ elements of $A$ are all different, so the range $f (A)$ has $n$ elements. It is a subset of $B$ , and the elements of $B$ outside it number $n - n = 0$ . So $f (A) = B$ , and $f$ is surjective.

( $\Leftarrow$ ) Suppose $f$ is surjective but not injective. The fibres $f^{- 1} (b)$ , for $b \in B$ , are disjoint, since each element of $A$ has one value, and their union is $A$ , so their sizes add up to $n$ . Each of the $n$ fibres has at least one element, by surjectivity, and some fibre has at least two, since two different elements share a value. Then the sizes add up to at least $(n - 1) + 2 = n + 1$ , a contradiction. So $f$ is injective. $□$

The theorem is used constantly in a practical form: to show that a map between finite sets of the same size is a bijection, prove only one of the two properties, whichever is easier. It fails without both hypotheses. It needs the sizes equal, as the inclusion of ${1}$ in ${1, 2}$ shows, and it needs finiteness.

What goes wrong for infinite sets?

The map $d : ℕ \to ℕ$ , $d (n) = 2 n$ , is injective and not surjective, and the map $n \mapsto ⌈ \frac{n}{2} ⌉$ on $ℕ$ is surjective and not injective, since $1$ and $2$ both go to $1$ . So for maps from an infinite set to itself, the two properties separate completely, and the theorem above is special to finite sets. The proof shows where finiteness entered: it subtracted and added numbers of elements, and for infinite sets there are no such numbers to compare.

Galileo noticed the phenomenon in his Two New Sciences of 1638. The squares $1, 4, 9, 16, \dots$ are a small part of the natural numbers, becoming rarer the further one goes, yet $n \mapsto n^{2}$ pairs the natural numbers one to one with the squares. He concluded that "equal", "greater" and "less" do not apply to infinite quantities. Richard Dedekind turned the paradox into a definition in 1888: he called a set infinite when it can be put in bijection with a proper subset of itself, as $ℕ$ can with the even numbers or the squares. By the theorem above, no finite set has this property, since a bijection from a finite set $A$ onto a proper subset $S$ , composed with the inclusion of $S$ in $A$ , would be an injection $A \to A$ that is not surjective.

Georg Cantor took the other way out of Galileo's paradox. Rather than give up comparing infinite sets, define two sets to have the same size when there is a bijection between them, and accept that a set can have the same size as a part of itself. The lesson on counting the infinite develops this, with bijections and injections doing all the work, and finds that infinite sets come in more than one size.

When one output is not enough

A function relates each input to exactly one output, and that restriction is what made composition and inverses work. Many relations mathematics cares about break it. "Divides" on the positive integers links $3$ to $6$ , $9$ , $12$ and every other multiple. The equation $x^{2} + y^{2} = 1$ links $0$ to both $1$ and $- 1$ and links $2$ to nothing, so the circle is not the graph of a function from $ℝ$ to $ℝ$ . "Leaves the same remainder on division by $5$ " links $3$ to $8$ , $13$ and $- 2$ .

Each is still a set of ordered pairs, a subset of a product, with the "exactly one" condition dropped. Functions themselves produce such relations: every $f : A \to B$ gives the relation "has the same value under $f$ as" on $A$ , which links $a$ to $a'$ when $f (a) = f (a')$ , and whose linked groups are exactly the non-empty fibres. The next lesson takes such relations up, beginning with the ones that declare two things to be the same for present purposes, and shows that every one of them arises from a function in this way.

Problems

Work each problem on paper before opening anything; for Core and Challenge problems, try the hint before the solution.

Warm-up

1. Let $A = {1, 2, 3}$ and $B = {x, y}$ . Which of these subsets of $A \times B$ are graphs of functions $A \to B$ ? For each one that is, give its range and say whether it is injective and whether it is surjective. (a) ${(1, x), (2, x), (3, x)}$ ; (b) ${(1, x), (2, y)}$ ; (c) ${(1, x), (1, y), (2, x), (3, y)}$ ; (d) ${(1, y), (2, x), (3, y)}$ .

Solution

(a) A function: each of $1$ , $2$ , $3$ appears exactly once as a first coordinate. It is the constant function with value $x$ , its range is ${x}$ , it is not injective ( $1$ and $2$ share the value $x$ ) and not surjective ( $y$ is not a value).

(b) Not a function: $3$ does not appear as a first coordinate, so it receives no value.

(d) A function with range ${x, y} = B$ , so it is surjective. It is not injective, since $1$ and $3$ both have value $y$ . No function from a set of three elements to a set of two can be injective, by the pigeonhole principle.

2. Let $f : ℝ \to ℝ$ , $f (x) = | x |$ . Find $f ([- 3, 1])$ , $f^{- 1} ([1, 2])$ , $f^{- 1} ([- 2, - 1])$ , $f^{- 1} (f ([1, 2]))$ and $f (f^{- 1} ([- 1, 4]))$ , justifying the first by double inclusion.

Solution

$f ([- 3, 1]) = [0, 3]$ . If $- 3 \leq x \leq 1$ , then $0 \leq | x | \leq 3$ , so every value on $[- 3, 1]$ lies in $[0, 3]$ . Conversely, if $0 \leq y \leq 3$ , then $- y \in [- 3, 0] \subseteq [- 3, 1]$ and $f (- y) = y$ , so $y$ is a value on $[- 3, 1]$ .

$f^{- 1} ([1, 2]) = [- 2, - 1] \cup [1, 2]$ , since $1 \leq | x | \leq 2$ exactly when $1 \leq x \leq 2$ or $- 2 \leq x \leq - 1$ .

$f^{- 1} ([- 2, - 1]) = \emptyset$ , since $| x | \geq 0$ for every $x$ .

$f ([1, 2]) = [1, 2]$ , as $f$ is the identity on non-negative numbers, so $f^{- 1} (f ([1, 2])) = f^{- 1} ([1, 2]) = [- 2, - 1] \cup [1, 2]$ , strictly larger than $[1, 2]$ .

$f^{- 1} ([- 1, 4]) = [- 4, 4]$ , since $| x | \geq 0 > - 1$ always and $| x | \leq 4$ exactly when $- 4 \leq x \leq 4$ . Then $f ([- 4, 4]) = [0, 4]$ , strictly smaller than $[- 1, 4]$ . This is $[- 1, 4] \cap f (ℝ) = [- 1, 4] \cap [0, \infty)$ , as Problem 6 predicts.

3. Decide whether each function is injective and whether it is surjective, with proofs. (a) $ℤ \to ℤ$ , $n \mapsto n + 3$ . (b) $ℤ \to ℤ$ , $n \mapsto 3 n$ . (c) $ℤ \to {0, 1, 2, \dots}$ , $n \mapsto | n |$ . (d) $ℝ \times ℝ \to ℝ$ , $(x, y) \mapsto x + y$ .

Solution

(a) Injective: if $n + 3 = m + 3$ then $n = m$ . Surjective: let $b \in ℤ$ and put $n = b - 3$ , an integer, with $n + 3 = b$ . So it is a bijection.

(b) Injective: if $3 n = 3 m$ then $n = m$ . Not surjective: if $3 n = 1$ for an integer $n$ , then $3 ∣ 1$ , but a divisor of $1$ has absolute value at most $1$ . So $1$ is not a value.

(c) Surjective: let $m \geq 0$ be an integer; then $m \in ℤ$ and $| m | = m$ . Not injective: $| 1 | = | - 1 |$ and $1 \neq - 1$ .

(d) Surjective: let $b \in ℝ$ ; then $(b, 0) \in ℝ \times ℝ$ and $b + 0 = b$ . Not injective: $(1, 0)$ and $(0, 1)$ are different pairs with the same value $1$ . In fact every fibre is a whole line, ${(x, b - x) : x \in ℝ}$ .

4. Let $f, g : ℝ \to ℝ$ be given by $f (x) = 2 x + 1$ and $g (x) = x^{2} + 1$ . Find formulas for $g \circ f$ and $f \circ g$ and show that they are different functions. Find $f^{- 1}$ and check both of the equations that make it an inverse.

Solution

$(g \circ f) (x) = g (2 x + 1) = (2 x + 1)^{2} + 1 = 4 x^{2} + 4 x + 2$ , and $(f \circ g) (x) = f (x^{2} + 1) = 2 x^{2} + 3$ . At $x = 0$ the first is $2$ and the second is $3$ , so $g \circ f \neq f \circ g$ .

Solving $2 x + 1 = y$ for $x$ suggests $f^{- 1} (y) = \frac{y - 1}{2}$ . Check: for every real $x$ , $f^{- 1} (f (x)) = \frac{(2 x + 1) - 1}{2} = x$ , and for every real $y$ , $f (f^{- 1} (y)) = 2 \cdot \frac{y - 1}{2} + 1 = y$ . So both $f^{- 1} \circ f$ and $f \circ f^{- 1}$ are the identity on $ℝ$ .

Core

5. Let $f : A \to B$ . Prove that $f$ is injective if and only if $f (S_{1} \cap S_{2}) = f (S_{1}) \cap f (S_{2})$ for all subsets $S_{1}$ and $S_{2}$ of $A$ .

Hint

For the forward direction one inclusion is the Example in the lesson; the other is where the lesson's failed attempt got stuck. For the backward direction, use the contrapositive with one-element sets.

Solution

( $\Rightarrow$ ) Suppose $f$ is injective, and let $S_{1}, S_{2} \subseteq A$ . The inclusion $f (S_{1} \cap S_{2}) \subseteq f (S_{1}) \cap f (S_{2})$ holds for every function, by the Example in the section on set operations. For the reverse, let $y \in f (S_{1}) \cap f (S_{2})$ . Then $y = f (x_{1})$ for some $x_{1} \in S_{1}$ and $y = f (x_{2})$ for some $x_{2} \in S_{2}$ . So $f (x_{1}) = f (x_{2})$ , and by injectivity $x_{1} = x_{2}$ . This element lies in both $S_{1}$ and $S_{2}$ , so $y = f (x_{1}) \in f (S_{1} \cap S_{2})$ .

( $\Leftarrow$ ) We prove the contrapositive. Suppose $f$ is not injective, so there are $a \neq a'$ in $A$ with $f (a) = f (a')$ . Take $S_{1} = {a}$ and $S_{2} = {a'}$ . Then $S_{1} \cap S_{2} = \emptyset$ , so $f (S_{1} \cap S_{2}) = \emptyset$ , while $f (S_{1}) \cap f (S_{2}) = {f (a)} \cap {f (a')} = {f (a)}$ , which is not empty. So the equality fails for this pair of subsets.

6. Let $f : A \to B$ .

(a) Prove that $f (f^{- 1} (T)) = T \cap f (A)$ for every $T \subseteq B$ , and deduce that $f$ is surjective if and only if $f (f^{- 1} (T)) = T$ for every $T \subseteq B$ .

(b) Prove that $f$ is injective if and only if $f^{- 1} (f (S)) = S$ for every $S \subseteq A$ .

Hint

Each "if and only if" has one direction that needs a single well-chosen set: $T = B$ in (a), and a one-element set in (b).

Solution

(a) Let $T \subseteq B$ . By the Example in the section on image and preimage, $f (f^{- 1} (T)) \subseteq T$ , and every element of $f (f^{- 1} (T))$ is a value of $f$ , so lies in $f (A)$ ; hence $f (f^{- 1} (T)) \subseteq T \cap f (A)$ . Conversely, let $y \in T \cap f (A)$ . Then $y = f (x)$ for some $x \in A$ , and $f (x) = y \in T$ , so $x \in f^{- 1} (T)$ and $y = f (x) \in f (f^{- 1} (T))$ .

If $f$ is surjective, then $f (A) = B$ , and $T \cap B = T$ for every $T \subseteq B$ , so $f (f^{- 1} (T)) = T$ . Conversely, if $f (f^{- 1} (T)) = T$ for every $T$ , take $T = B$ : since $f^{- 1} (B) = A$ , this says $f (A) = B$ , so $f$ is surjective.

(b) ( $\Rightarrow$ ) Suppose $f$ is injective and let $S \subseteq A$ . The inclusion $S \subseteq f^{- 1} (f (S))$ holds for every function (the Now you in the section on image and preimage). For the reverse, let $x \in f^{- 1} (f (S))$ . Then $f (x) \in f (S)$ , so $f (x) = f (x')$ for some $x' \in S$ , and by injectivity $x = x' \in S$ .

( $\Leftarrow$ ) Suppose $f^{- 1} (f (S)) = S$ for every $S \subseteq A$ , and let $a, a' \in A$ with $f (a) = f (a')$ . Take $S = {a'}$ . Then $f (a) = f (a') \in f (S)$ , so $a \in f^{- 1} (f (S)) = {a'}$ , which gives $a = a'$ . So $f$ is injective.

7. Find the flaw in this proof, and show that the claim is false.

Claim. Let $f : A \to B$ and $g : B \to C$ . If $g \circ f$ is injective, then $g$ is injective.

Proof. Let $b, b' \in B$ with $g (b) = g (b')$ . Write $b = f (a)$ and $b' = f (a')$ with $a, a' \in A$ . Then $g (f (a)) = g (f (a'))$ , and since $g \circ f$ is injective, $a = a'$ . Hence $b = f (a) = f (a') = b'$ , so $g$ is injective.

Hint

The second sentence asserts that something exists. What property of $f$ would guarantee it?

Solution

The flaw is the second sentence. It assumes that $b$ and $b'$ are values of $f$ , which holds for all $b, b' \in B$ only when $f$ is surjective, and nothing in the hypothesis says so. The argument never considers elements of $B$ outside the range of $f$ , and those are exactly where $g$ may fail to be injective.

A counterexample: let $A = {1}$ , $B = {1, 2}$ , $C = {1}$ , with $f (1) = 1$ and $g (1) = g (2) = 1$ . Then $g \circ f : {1} \to {1}$ is injective, since its domain has only one element, but $g$ is not, since $g (1) = g (2)$ and $1 \neq 2$ .

The argument does prove a correct statement: if $g \circ f$ is injective and $f$ is surjective, then $g$ is injective. Then the second sentence is justified by surjectivity, and the rest goes through unchanged.

8. Let $f : A \to B$ and $g : B \to C$ . Prove or disprove each claim. (a) If $g \circ f$ is a bijection, then $f$ is surjective. (b) If $g \circ f$ is surjective and $g$ is injective, then $f$ is surjective. (c) If $f$ and $g \circ f$ are bijections, then $g$ is a bijection. (d) If $g \circ f$ is injective and $g$ is surjective, then $f$ is surjective.

Hint

Two are true. For the false ones, the smallest sets you can think of will do: the counterexample in Problem 7 is a good place to start. For (c), write $g$ as a composite.

Solution

(a) False. Take $A = {1}$ , $B = {1, 2}$ , $C = {1}$ , $f (1) = 1$ and $g (1) = g (2) = 1$ . Then $g \circ f : {1} \to {1}$ is a bijection, but $f$ is not surjective, since $2$ is not a value. Nor is $g$ injective, so a bijective composite says nothing about $f$ being surjective or $g$ being injective.

(b) True. Let $b \in B$ . Then $g (b) \in C$ , and $g \circ f$ is surjective, so there is $a \in A$ with $g (f (a)) = g (b)$ . Since $g$ is injective, $f (a) = b$ . So every $b \in B$ is a value of $f$ .

(c) True. Since $f$ is a bijection it has an inverse $f^{- 1} : B \to A$ , and $(g \circ f) \circ f^{- 1} = g \circ (f \circ f^{- 1}) = g \circ {id}_{B} = g$ by associativity. So $g$ is a composite of the bijections $f^{- 1}$ and $g \circ f$ , and a composite of bijections is a bijection.

(d) False. The example in (a) works again: $g \circ f$ is injective, $g : {1, 2} \to {1}$ is surjective, and $f$ is not surjective.

9. Prove that $f : ℝ \to (- 1, 1)$ , $f (x) = \frac{x}{1 + | x |}$ , is a bijection, and find a formula for $f^{- 1}$ .

Hint

First check that the values lie in $(- 1, 1)$ and that $f (x)$ has the same sign as $x$ . Then split injectivity and surjectivity into the cases of non-negative and negative inputs, where the absolute value can be removed.

Solution

Values. For every real $x$ , $1 + | x | > | x | \geq 0$ , so $| f (x) | = \frac{| x |}{1 + | x |} < 1$ and $f (x) \in (- 1, 1)$ . So $f$ is a function into $(- 1, 1)$ . Since the denominator is positive, $f (x) > 0$ when $x > 0$ , $f (x) = 0$ when $x = 0$ , and $f (x) < 0$ when $x < 0$ .

Injective. Let $a, a' \in ℝ$ with $f (a) = f (a')$ . By the sign observation, $a$ and $a'$ are both non-negative or both negative. If both are non-negative, then $\frac{a}{1 + a} = \frac{a'}{1 + a'}$ , so $a + a a' = a' + a a'$ and $a = a'$ . If both are negative, then $| a | = - a$ and $| a' | = - a'$ , so $\frac{a}{1 - a} = \frac{a'}{1 - a'}$ , which gives $a - a a' = a' - a a'$ and $a = a'$ .

Surjective. Let $y \in (- 1, 1)$ . If $0 \leq y < 1$ , put $x = \frac{y}{1 - y}$ , a real number since $y \neq 1$ , and non-negative. Then $1 + | x | = 1 + \frac{y}{1 - y} = \frac{1}{1 - y}$ , so $f (x) = \frac{y}{1 - y} \cdot (1 - y) = y$ . If $- 1 < y < 0$ , put $x = \frac{y}{1 + y}$ , a real number since $y \neq - 1$ , and negative since $y < 0 < 1 + y$ . Then $| x | = \frac{- y}{1 + y}$ and $1 + | x | = \frac{1}{1 + y}$ , so $f (x) = \frac{y}{1 + y} \cdot (1 + y) = y$ .

So $f$ is a bijection. The two cases of the surjectivity proof combine into one formula, since $1 - | y |$ is $1 - y$ for $y \geq 0$ and $1 + y$ for $y < 0$ :

f^{- 1} (y) = \frac{y}{1 - | y |} for - 1 < y < 1

A bijection between $ℝ$ and a bounded interval may be surprising. It shows that, in the sense of the lesson on counting the infinite, the whole line and a short piece of it have the same size.

10. Let $A$ be a set, and let $F$ be the set of all functions from $A$ to ${0, 1}$ . For $S \subseteq A$ , let $χ_{S}$ be the characteristic function of $S$ .

(a) Prove that $Φ : P (A) \to F$ , $Φ (S) = χ_{S}$ , is a bijection, by showing that $Ψ : F \to P (A)$ , $Ψ (g) = g^{- 1} ({1})$ , is its inverse.

(b) Prove that $χ_{S \cap T} = χ_{S} \cdot χ_{T}$ and $χ_{A ∖ S} = 1 - χ_{S}$ for all $S, T \subseteq A$ , where the operations on the right are taken value by value.

Hint

For (a), check $Ψ \circ Φ = {id}_{P (A)}$ and $Φ \circ Ψ = {id}_{F}$ ; the second is an equality of functions, proved by comparing values at an arbitrary $a \in A$ , in two cases. For (c), use the counting theorem.

Solution

(a) For $S \subseteq A$ , $Ψ (Φ (S)) = χ_{S}^{- 1} ({1}) = {a \in A : χ_{S} (a) = 1} = S$ , by the definition of $χ_{S}$ . So $Ψ \circ Φ = {id}_{P (A)}$ .

For $g \in F$ , let $S = g^{- 1} ({1})$ ; we show $χ_{S} = g$ by comparing values. Let $a \in A$ . If $g (a) = 1$ , then $a \in S$ , so $χ_{S} (a) = 1 = g (a)$ . If $g (a) = 0$ , then $a \notin S$ , so $χ_{S} (a) = 0 = g (a)$ . These cases are exhaustive, since $g$ takes values in ${0, 1}$ . So $Φ (Ψ (g)) = g$ , and $Φ \circ Ψ = {id}_{F}$ . Hence $Ψ$ is an inverse of $Φ$ , and $Φ$ is a bijection.

(b) Let $a \in A$ . If $a \in S \cap T$ , both sides of the first equation are $1$ at $a$ , since $1 \cdot 1 = 1$ . If $a \notin S \cap T$ , then $a \notin S$ or $a \notin T$ , so one of $χ_{S} (a)$ and $χ_{T} (a)$ is $0$ and the product is $0 = χ_{S \cap T} (a)$ . For the second, if $a \in S$ then $χ_{A ∖ S} (a) = 0 = 1 - 1$ , and if $a \notin S$ then $χ_{A ∖ S} (a) = 1 = 1 - 0$ .

(c) Let $| A | = n$ . By the counting theorem, there are $2^{n}$ functions from $A$ to the 2-element set ${0, 1}$ , so $| F | = 2^{n}$ . Since $Φ$ is a bijection from $P (A)$ to $F$ , and a bijection between finite sets exists only when they have the same number of elements (the same theorem, part (iii)), $| P (A) | = 2^{n}$ . This is the count the previous lesson proved by induction, now obtained by translating subsets into functions. Part (b) shows the translation also turns set operations into arithmetic, which is how computers store and combine sets, as strings of bits.

11. How many surjections are there from a set of $4$ elements onto a set of $3$ elements? Check your answer by counting the functions that are not surjective and adding.

Hint

The fibres of a surjection partition the domain into non-empty pieces, one for each element of the codomain. What sizes can they have?

Solution

Let $A = {1, 2, 3, 4}$ and $B = {x, y, z}$ . The three fibres of a surjection $f : A \to B$ are non-empty, disjoint, and together make up $A$ , so their sizes are positive integers adding to $4$ : one fibre has $2$ elements and the others $1$ each.

A surjection is therefore determined by three choices: which element $b$ of $B$ has the fibre of size $2$ ( $3$ ways); which two elements of $A$ form that fibre ( $6$ ways: ${1, 2}$ , ${1, 3}$ , ${1, 4}$ , ${2, 3}$ , ${2, 4}$ , ${3, 4}$ ); and how the remaining two elements of $A$ are sent to the remaining two elements of $B$ , one each ( $2$ ways). Different choices give different functions, and every surjection arises from one set of choices, namely its own. So there are $3 \times 6 \times 2 = 36$ surjections.

Check. A function that is not surjective has range of size $1$ or $2$ . Range of size $1$ : a constant function, $3$ of them. Range of size $2$ : choose the two values ( $3$ ways), then a function from $A$ onto that 2-element set; there are $2^{4} = 16$ functions from $A$ to a 2-element set, of which $2$ are constant, so $14$ are onto, giving $3 \times 14 = 42$ . In total $36 + 42 + 3 = 81 = 3^{4}$ , the number of all functions from $A$ to $B$ .

Challenge

12. Let $f : A \to B$ .

(a) Prove that $f$ is injective if and only if, for every set $C$ and all functions $h, k : C \to A$ , $f \circ h = f \circ k$ implies $h = k$ .

(b) Prove that $f$ is surjective if and only if, for every set $C$ and all functions $h, k : B \to C$ , $h \circ f = k \circ f$ implies $h = k$ .

Hint

The forward directions compare values. For the backward directions argue by contrapositive and build $h$ and $k$ on very small sets: a one-element $C$ in (a), and $C = {0, 1}$ in (b), with a characteristic function.

Solution

(a) ( $\Rightarrow$ ) Suppose $f$ is injective, and let $h, k : C \to A$ with $f \circ h = f \circ k$ . For every $c \in C$ , $f (h (c)) = f (k (c))$ , so $h (c) = k (c)$ by injectivity. The functions $h$ and $k$ have the same domain, codomain and values, so $h = k$ .

( $\Leftarrow$ ) Suppose the cancellation property holds, and let $a, a' \in A$ with $f (a) = f (a')$ . Let $C = {0}$ , and define $h, k : C \to A$ by $h (0) = a$ and $k (0) = a'$ . Then $(f \circ h) (0) = f (a) = f (a') = (f \circ k) (0)$ , so $f \circ h = f \circ k$ , and the property gives $h = k$ . Hence $a = h (0) = k (0) = a'$ , and $f$ is injective.

(b) ( $\Rightarrow$ ) Suppose $f$ is surjective, and let $h, k : B \to C$ with $h \circ f = k \circ f$ . Let $b \in B$ . There is $a \in A$ with $f (a) = b$ , and then $h (b) = h (f (a)) = k (f (a)) = k (b)$ . So $h = k$ .

( $\Leftarrow$ ) We prove the contrapositive. Suppose $f$ is not surjective, and choose $b_{0} \in B$ outside the range of $f$ . Let $C = {0, 1}$ , let $h : B \to C$ be the constant function $0$ , and let $k = χ_{{b_{0}}}$ , which is $1$ at $b_{0}$ and $0$ elsewhere. For every $a \in A$ , $f (a) \neq b_{0}$ , so $k (f (a)) = 0 = h (f (a))$ , and $h \circ f = k \circ f$ . But $h (b_{0}) = 0 \neq 1 = k (b_{0})$ , so $h \neq k$ , and the cancellation property fails.

The two properties describe injectivity and surjectivity purely by how $f$ composes with other functions, without mentioning elements. That is how category theory, which studies mathematical structures through the maps between them, defines its general notions of monomorphism and epimorphism. Note that no choice was needed in (b), unlike the right inverse of the lesson: cancellation is a weaker property than having a right inverse, and is available for every surjection outright.

13. Prove that there is no function $f : ℤ \to ℤ$ with $f (f (n)) = n + 1$ for every integer $n$ .

Hint

Compute $f (f (f (n)))$ in two ways: as $f$ applied to $f (f (n))$ , and as $f \circ f$ applied to $f (n)$ . That determines $f$ up to one constant.

Solution

Suppose, for a contradiction, that $f : ℤ \to ℤ$ satisfies $f (f (n)) = n + 1$ for every integer $n$ . Let $n \in ℤ$ . Applying the hypothesis to the integer $f (n)$ gives $f (f (f (n))) = f (n) + 1$ . Applying $f$ to both sides of $f (f (n)) = n + 1$ gives $f (f (f (n))) = f (n + 1)$ . Hence

f (n + 1) = f (n) + 1 for every integer n

Let $c = f (0)$ . We show $f (n) = n + c$ for every integer $n$ . For $n \geq 0$ this is an induction on $n$ : it holds at $n = 0$ , and if $f (n) = n + c$ then $f (n + 1) = f (n) + 1 = (n + 1) + c$ . For negative integers, rewrite the displayed equation as $f (n) = f (n + 1) - 1$ and induct on $k \geq 0$ for the statement $f (- k) = - k + c$ : it holds at $k = 0$ , and if $f (- k) = - k + c$ , then $f (- k - 1) = f (- k) - 1 = (- k - 1) + c$ .

Now apply the hypothesis at $n = 0$ : $1 = f (f (0)) = f (c) = c + c = 2 c$ . But $2 c$ is even and $1$ is odd, and no integer is both. This contradiction shows that no such $f$ exists.

The obstruction is arithmetic, not logical. On $ℝ$ the function $x \mapsto x + \frac{1}{2}$ satisfies $f (f (x)) = x + 1$ , and on $ℤ$ the equation $f (f (n)) = n + 2$ is satisfied by $n \mapsto n + 1$ ; the proof shows that on $ℤ$ every solution of $f (f (n)) = n + m$ is a translation by $\frac{m}{2}$ , which exists exactly when $m$ is even.

14. A function $f : A \to A$ is idempotent if $f \circ f = f$ .

(a) Prove that $f$ is idempotent if and only if $f (y) = y$ for every $y$ in the range $f (A)$ .

(b) Prove that an idempotent function that is injective, or surjective, is the identity.

Hint

For (c), use (a): an idempotent function is determined by its range $R$ and by where it sends the elements outside $R$ . Count by the size of $R$ .

Solution

(a) ( $\Rightarrow$ ) Let $f$ be idempotent and $y \in f (A)$ , say $y = f (x)$ . Then $f (y) = f (f (x)) = f (x) = y$ . ( $\Leftarrow$ ) Suppose $f$ fixes every element of its range, and let $x \in A$ . Then $f (x)$ is in the range, so $f (f (x)) = f (x)$ . Hence $f \circ f = f$ .

(b) Let $f$ be idempotent. If $f$ is injective, then for each $x \in A$ the equation $f (f (x)) = f (x)$ says that $f (x)$ and $x$ have the same value, so $f (x) = x$ . If $f$ is surjective, its range is $A$ , and by (a) it fixes every element of $A$ . In both cases $f = {id}_{A}$ .

(c) Let $A = {1, 2, 3, 4}$ . By (a), an idempotent $f$ fixes each element of its range $R = f (A)$ , which is non-empty because $A$ is, and sends each element of $A ∖ R$ into $R$ . So $f$ determines a pair $(R, g)$ , where $R$ is a non-empty subset of $A$ and $g = f |_{A ∖ R}$ is a function $A ∖ R \to R$ .

Conversely, every such pair comes from exactly one idempotent. Given a non-empty $R \subseteq A$ and $g : A ∖ R \to R$ , define $f$ to be the identity on $R$ and $g$ on $A ∖ R$ . Its range contains $R$ , since $f$ fixes $R$ , and is contained in $R$ , since every value lies in $R$ ; so the range is $R$ , $f$ fixes its range, and $f$ is idempotent by (a). Its pair is $(R, g)$ again, and different pairs give different functions. So the idempotents correspond exactly to the pairs.

For $| R | = k$ there are $k^{4 - k}$ functions $A ∖ R \to R$ , by the counting theorem. Summing over the subsets $R$ by size: $4$ subsets of size $1$ , each giving $1^{3} = 1$ ; $6$ of size $2$ , each giving $2^{2} = 4$ ; $4$ of size $3$ , each giving $3^{1} = 3$ ; and $1$ of size $4$ , giving $4^{0} = 1$ . The total is $4 + 24 + 12 + 1 = 41$ .