Functions

Chapter 5: Functions

Learning objectives

Define a function as a special kind of relation
Distinguish functions from general relations using totality and well-definedness
Identify the domain, codomain, and range of a function
Compose two functions and apply the identity function

What makes "function" different from "relation"? A function imposes exactly one output for each input. Drop that requirement and you get an arbitrary relation; impose it and you get the single most important structure in mathematics. Every program is a function (input bytes → output bytes). Every API call is a function. Every neural network, every audio filter, every database query — functions all the way down. This section gives the precise set-theoretic definition that underlies all of those examples, and the algebra of composition that lets you build big functions out of small ones.

Definition

A function from $A$ to $B$ , written $f: A \to B$ , is a relation $f \subseteq A \times B$ satisfying two extra requirements:

Total:

\forall a \in A,\, \exists b \in B,\, (a, b) \in f

— every input has at least one output.

Well-defined:

\forall a \in A,\, \forall b_1, b_2 \in B,\, ((a, b_1) \in f \wedge (a, b_2) \in f) \Rightarrow b_1 = b_2

— each input has at most one output.

Together: exactly one output. We write that unique output as $f(a)$ .

Domain, codomain, range

The domain is $A$ , the codomain is $B$ , and the range (or image) is $\text{Ran}(f) = {f(a) \mid a \in A} \subseteq B$ . The range is always a subset of the codomain but need not equal it. Example: $f: \mathbb{R} \to \mathbb{R},, f(x) = x^2$ has codomain $\mathbb{R}$ but range $[0, \infty)$ .

Equality of functions

Two functions $f, g$ are equal iff they have the same domain, the same codomain, and $f(a) = g(a)$ for every $a$ . All three conditions matter: $f: \mathbb{Z} \to \mathbb{Z},, f(n) = n$ and $g: \mathbb{Z} \to \mathbb{R},, g(n) = n$ are different functions because their codomains differ.

Composition and identity

Given $f: A \to B$ and $g: B \to C$ , the composition $g \circ f: A \to C$ is defined by $(g \circ f)(a) = g(f(a))$ . Composition is associative but generally not commutative. The identity function $\text{id}_A: A \to A,, \text{id}_A(a) = a$ satisfies $f \circ \text{id}_A = f$ and $\text{id}_B \circ f = f$ — it is the "do-nothing" function for composition.

Where this shows up

- **Every program:** Take input, produce output. Compilers, interpreters, web servers, REST endpoints — all functions (modulo state, which is itself a hidden input). Pure-functional languages (Haskell, Elm) make this identification explicit. - **Neural networks:** A neural net is a function

f_\theta: \mathbb{R}^d \to \mathbb{R}^k

parameterised by weights

\theta

. Composition of layers is literal function composition; backpropagation is the chain rule applied to that composition. - **Signal and image processing pipelines:** An audio filter is

f: \mathbb{R}^N \to \mathbb{R}^N

(or

\mathbb{C}^N \to \mathbb{C}^N

in the frequency domain). Chaining filters is composition. Photoshop’s adjustment layers are stacks of pixel functions. - **REST and RPC APIs:** Every endpoint is a function "request → response." API versioning is the discipline of preserving the function’s behaviour as the implementation evolves.

Pause and think: Why isn’t the relation $R = {(1, a), (1, b), (2, c)}$ a function from ${1, 2}$ to ${a, b, c}$ ? Which of the two function-defining properties fails? (Hint: input $1$ is paired with two different outputs.)

Try it

Decide whether $R = {(1, a), (2, a), (3, b)}$ is a function from ${1, 2, 3}$ to ${a, b}$ . Justify both properties.
For $f(x) = 2x + 1$ and $g(x) = x^2$ on $\mathbb{R}$ , compute $(g \circ f)(3)$ and $(f \circ g)(3)$ . Are they equal?
What is the range of $f: \mathbb{Z} \to \mathbb{Z},, f(n) = 2n$ ? Is the codomain equal to the range?
Prove: if $f: A \to B$ and $g: B \to C$ , then $g \circ f: A \to C$ is itself a function (verify both properties).
True or false: $(x + 1)^2 - 1$ and $x^2 + 2x$ define equal functions on $\mathbb{R}$ . Justify.

A trap to watch for

"Range" and "codomain" are not synonyms. The codomain is fixed by the function’s declared signature $f: A \to B$ ; it tells you the type of the output. The range is the set of outputs actually achieved. For $f(x) = x^2$ on $\mathbb{R} \to \mathbb{R}$ , the codomain is $\mathbb{R}$ but the range is only $[0, \infty)$ . Whether range equals codomain is the question we will study in §5.2 (it is called surjectivity).

What you now know

You can read off the data of any function (domain, codomain, range), distinguish a function from an arbitrary relation, compose functions correctly, and recognise the identity function as the do-nothing element for composition. Section 5.2 examines two special properties of functions — injectivity and surjectivity — that together make a function invertible.

References

Velleman, D. J. (2019). How to Prove It (3rd ed.). Cambridge University Press, §5.1.
Halmos, P. R. (1960). Naive Set Theory. Springer, §8.
Enderton, H. B. (1977). Elements of Set Theory. Academic Press, ch. 3.
Hammack, R. (2018). Book of Proof, ch. 12.
Bird, R., Wadler, P. (1988). Introduction to Functional Programming. Prentice Hall (functions as the basis of programming).