1.4  Functions, Composition, Injections and Surjections

Section 1.3 made “the pairs a description picks out” into a set: a relation from $A$ to $B$ is a subset of $A\times B$. Among its examples, the graph of squaring relates each real number to exactly one number, and the unit circle relates $0$ to two numbers and $2$ to none. This section gives the first kind its name, function, and builds the rest on it: we restrict functions, use them to make families, sequences and the set $Y^X$ precise, compose them, and ask the two questions that the rest of the chapter turns on: does a function send different inputs to different outputs, and does it reach every point of its target?

1.4.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.3 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.

The whole definition is the quantifier pattern $\mathrm{\forall }\mathrm{\exists }!$. By Logic and Proof, Definition 5.8.1, “$\mathrm{\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^{\prime }\in Y$, if $(x,y)\in G$ and $(x,y^{\prime })\in G$, then $y=y^{\prime }$: 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:\mathrm{\exists }x\in Xf(x)=y\},$$ which Section 1.6 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: $$\begin{array}{}\text{(}\ast \ast \text{)}& (x,y)\in f⟺y=f(x)(x\in X,y\in Y).\end{array}$$ 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:\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^{\prime }=x^2$, then $y=y^{\prime }$. 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:\mathbb{R}\to \mathbb{R}$, $f(x)=1/x$” the formula makes no sense at $x=0$, and (Fn1) fails there; for “$f:\mathbb{R}\to [0,\mathrm{\infty })$, $f(x)=x^2$” the value must be checked to lie in $[0,\mathrm{\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.

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

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(\frac{1}{2})$ 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.1.1), whatever target was declared. The graph of $x\mapsto x^2$ as a function $[0,\mathrm{\infty })\to \mathbb{R}$ is the same set as its graph as a function $[0,\mathrm{\infty })\to [0,\mathrm{\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 below, and an example later in this section 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.

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

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.

Restriction. A function can be cut down to a smaller domain. For $f:X\to Y$ and $A\subseteq X$, the restriction of $f$ to $A$ is the function $$f{|}_A:A\to Y,f{|}_A(a):=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,\mathrm{\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.

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

Section 1.2 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.1.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:=\{f\in \mathcal{P}(X\times Y)\times \{Y\}:f\text{ is a function from }X\text{ to }Y\}.$$ It is a set by the working rules of Section 1.1: every function $X\to Y$ is a pair $(G,Y)$ with $G\in \mathcal{P}(X\times Y)$, so $Y^X$ is the subset of $\mathcal{P}(X\times Y)\times \{Y\}$ cut out by the condition of Definition 1.4.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 Chapter 3’s business. The set $\{0,1{\}}^{\mathbb{N}}$ of all sequences of zeros and ones, indexed from $0$, plays a leading role in Chapter 3.

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 Chapter 3 solves.

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

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

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

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.

Composition can also fail to be defined in one order only. For $f:\{1,2\}\to \mathbb{R}$ and $g:\mathbb{R}\to \mathbb{R}$, the composite $g\circ f:\{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.

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

1.4.5. Injective, surjective, bijective

Two questions can be asked of any function $f:X\to Y$, and much of mathematics turns on them. First: can we recover the input from the output, or can two different inputs give the same output? Second: is every point of the codomain an output? The first question is about how $f$ treats $X$; the second is about how it covers $Y$.

Injective functions

An injective function never sends two different inputs to the same output.

In words: if two inputs give the same output, they were the same input. By Logic and Proof, Proposition 2.3.2, the definition gives the contrapositive form $$\mathrm{\forall }{x}_1\in X\mathrm{\forall }{x}_2\in X(x_1\ne x_2\to f(x_1)\ne f(x_2)):$$ different inputs give different outputs. The two forms are equivalent; the way back, from the contrapositive form to the definition, is Logic and Proof, Proposition 2.5.2, which uses $\mathrm{RAA}$. A proof of injectivity usually uses the form of the definition, because an equation $f(x_1)=f(x_2)$ is something to compute with, while an inequation $x_1\ne x_2$ is not.

The negation is found by the laws of Logic and Proof, Chapter 6 for negating bounded quantifiers and implications: “$f$ is not injective” is $$\mathrm{\exists }{x}_1\in X\mathrm{\exists }{x}_2\in X(f(x_1)=f(x_2)\wedge x_1\ne x_2).$$ So a failure of injectivity is shown by two witnesses: two different inputs with the same output.

Surjective functions

A surjective function reaches every point of its codomain.

In words: every point of the codomain is an output; equivalently, the range of $f$ is all of $Y$. An $x$ with $f(x)=y$ is called a preimage of $y$. The definition does not ask for the preimage to be unique. Negating as before, “$f$ is not surjective” is $$\mathrm{\exists }y\in Y\mathrm{\forall }x\in Xf(x)\ne y,$$ so a failure of surjectivity is shown by one witness: a point of the codomain that no input reaches.

Surjectivity depends on the codomain, which is why Definition 1.4.1 records it: $s_1$ and $s_2$ of Example (Equal and unequal functions) have the same graph, and we shall see that $s_2$ is surjective and $s_1$ is not.

Bijective functions

A bijection is a function in which every point of the codomain is reached exactly once: for every $y\in Y$ there is exactly one $x\in X$ with $f(x)=y$. This is the $\mathrm{\exists }!$ of Definition 1.4.1 again, now read from the codomain side, and its two halves are the two properties. Existence of such an $x$, for every $y$, is surjectivity. Uniqueness is injectivity: if $f(x_1)=y=f(x_2)$, injectivity gives $x_1=x_2$; and conversely, if every $y$ has at most one preimage, then $f(x_1)=f(x_2)$ makes $x_1$ and $x_2$ two preimages of the same point $y:=f(x_1)$, so $x_1=x_2$.

Worked examples

Proofs of these properties have a fixed shape, read off the definitions.

• To prove $f$ injective: “Let $x_1,x_2\in X$ with $f(x_1)=f(x_2)$.” Compute until you reach $x_1=x_2$.
• To prove $f$ surjective: “Let $y\in Y$.” Then produce an $x$, say what it is, check that it lies in $X$, and check that $f(x)=y$. The $x$ is usually found by solving $f(x)=y$ for $x$ on scrap paper; the proof then states the solution first and checks it, as every existence proof does.
• To prove $f$ not injective: name $x_1\ne x_2$ with $f(x_1)=f(x_2)$. Not surjective: name $y\in Y$ and show that $f(x)=y$ has no solution $x\in X$.

Parts (c) and (d) show two more things. A function from a three-element set to a two-element set cannot be injective, and one from a two-element set to a three-element set cannot be surjective: there are too many inputs in the first case and too few in the second. Chapter 3 proves facts of this kind in general, starting from the pigeonhole principle. And the finite pictures are worth drawing: two columns of dots, with an arrow from each input to its output. Injective means no dot on the right receives two arrows; surjective means every dot on the right receives at least one.

The key example of the section is one formula read as three different functions.

1.4.6. Composites of injections and surjections

Both properties survive composition. This is the first theorem about functions whose proof uses the definitions and nothing else, and it shows the two proof shapes of the last subsection working together.

Part (a) is short enough to see whole at level 0 of Logic and Proof, Section 8.3, a full derivation. Here is its derivation, with the quantifiers bounded and handled by the bounded rules (Logic and Proof, Proposition 6.1.1), and $(g\circ f)(u)$ already unwound to $g(f(u))$ by Definition 1.4.2. Premises 1 and 2 are the injectivity of $f$ and of $g$; premise 3 says that $f$ maps $X$ into $Y$, which the prose used in the clause “the points $f(x_1)$ and $f(x_2)$ lie in $Y$”.