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 that lesson, the quantifiers, and the direct and contrapositive 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$ . The set $A$ is the domain and $B$ is the codomain. 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}$ ".

"Rule" is informal, and the previous lesson supplies the formal version in one sentence: a function from $A$ to $B$ is the sets $A$ and $B$ together with a subset $f$ of $A \times B$ such that for every $a \in A$ there is exactly one $b \in B$ with $(a, b) \in f$ , and $f (a)$ names that $b$ . Nothing here asks for a formula, so a seating plan is as much a function as $3 x + 7$ is.

"Exactly one" makes two demands: every element of the domain receives a value, and none receives two. 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.

Two functions are equal when they have the same domain, the same codomain, and the same value at every element of the domain. So $x \mapsto (x + 1)^{2}$ and $x \mapsto x^{2} + 2 x + 1$ on $ℝ$ are one function written two ways.

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

Image and preimage

For $f : A \to B$ and $S \subseteq A$ , the image of $S$ is $f (S) = {f (x) : x \in S}$ , the values taken on $S$ . For $T \subseteq B$ , the preimage of $T$ is $f^{- 1} (T) = {x \in A : f (x) \in T}$ , the inputs that land in $T$ . The notation is a trap: $f^{- 1} (T)$ is a set, and it exists for every function, whether or not $f$ has an inverse.

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]$ . 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.

A round trip need not return where it started: the preimage of $T = [- 4, 4]$ 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))$ is exactly the part of $T$ that $f$ reaches, so equality holds for every $T$ precisely when every element of $B$ is a value.

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

Injective, surjective and bijective

A function $f : A \to B$ is injective, or one-to-one, when distinct inputs give distinct outputs. 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)$ .

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$ . 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, when it is both, so that each $b \in B$ is the value of exactly one $a \in A$ . The two 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$ is surjective and not injective.

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{2 b / (b - 2)}{b / (b - 2) - 1} = \frac{2 b / (b - 2)}{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.

Composition

Given $f : A \to B$ and $g : B \to C$ , the composite $g \circ f : A \to C$ is $(g \circ f) (a) = g (f (a))$ , read " $g$ after $f$ ": $f$ runs first. Order matters: with $f (x) = x + 1$ and $g (x) = x^{2}$ on $ℝ$ , $(g \circ f) (1) = 4$ while $(f \circ g) (1) = 2$ . Composition is associative, since $h \circ (g \circ f)$ and $(h \circ g) \circ f$ both send $a$ to $h (g (f (a)))$ , so brackets can be dropped.

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. A partial converse holds: if $g \circ f$ is injective then so is $f$ , since $f (a) = f (a^{'})$ gives $g (f (a)) = g (f (a^{'}))$ and so $a = a^{'}$ . But $g$ need not be: with $f : [0, \infty) \to ℝ$ , $f (x) = x$ , the composite $s \circ f$ is injective while $s$ is not.

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.

Inverses

The identity on $A$ is ${id}_{A} : A \to A$ , ${id}_{A} (a) = a$ . A function $g : B \to A$ is an inverse of $f : A \to B$ when $g \circ f = {id}_{A}$ and $f \circ g = {id}_{B}$ .

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

Suppose first that $g$ is an inverse. For injectivity, let $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)$ ; then $f (a) = f (g (b)) = b$ . Conversely, suppose $f$ is a bijection. For each $b \in B$ , surjectivity gives some $a$ with $f (a) = b$ and injectivity says there is only one, so letting $g (b)$ be that $a$ assigns exactly one element of $A$ to each $b$ , and $g : B \to A$ is a function. By construction $f (g (b)) = b$ . For $a \in A$ , $g (f (a))$ is the unique element sent to $f (a)$ , and $a$ is such an element, so $g (f (a)) = a$ . Hence $g$ is an inverse.

Each half of the definition did one job: $g \circ f = {id}_{A}$ forced injectivity and $f \circ g = {id}_{B}$ surjectivity. Neither alone is enough. For $d (n) = 2 n$ , the map $e$ sending an even $m$ to $\frac{m}{2}$ and an odd $m$ to $1$ satisfies $e \circ d = {id}_{ℕ}$ , yet $d (e (1)) = 2$ . An inverse is also unique: if $g$ and $h$ are both inverses, then $g = g \circ (f \circ h) = (g \circ f) \circ h = h$ by associativity. So it earns the name $f^{- 1}$ . For $f (x) = 3 x + 7$ it is $f^{- 1} (y) = \frac{y - 7}{3}$ , the formula the surjectivity proof already found.

Counting functions between finite sets

Let $| A | = m$ and $| B | = n$ , and list $A$ as $a_{1}, \dots, a_{m}$ . A function $f : A \to B$ is a free choice of $f (a_{1})$ , then $f (a_{2})$ , and so on, each from $B$ : an ordered list of $m$ elements of $B$ . By the product rule of the previous lesson, extended to $m$ factors by induction, there are $n^{m}$ functions from $A$ to $B$ .

For an injection each choice must avoid the earlier ones: $n$ options for $f (a_{1})$ , $n - 1$ for $f (a_{2})$ , down to $n - m + 1$ for $f (a_{m})$ . So there are $n (n - 1) \dots (n - m + 1)$ injections, a falling factorial. When $m > n$ some factor is $0$ and there are none, which is the pigeonhole principle. When $m = n$ , an injection takes $n$ distinct values in a set of $n$ elements, so it hits all of $B$ , and there are $n!$ bijections.

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, the injective fraction is $\frac{365 \cdot 364 \dots 343}{365^{23}} \approx 0.493$ , so a shared birthday is more likely than not.

For finite sets of equal size, then, injective and surjective coincide. The map $d$ on $ℕ$ , injective and not surjective, shows that this fails for infinite sets, a first sign that counting the infinite needs a different idea.

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. The next lesson takes such relations up, beginning with the ones that declare two things to be the same for present purposes.