Functions as Special Relations

The relational definition of function is the silent backbone of essentially all of modern mathematics and its applications, precisely because it is the only definition precise enough to survive contact with infinite, arbitrary, or algorithmically inexpressible correspondences.

• Set theory and cardinality. Comparing the sizes of infinite sets — the subject this chapter is heading toward — is done entirely via functions between them: injections and surjections are defined as extra properties layered on top of the single-valuedness condition developed here, and cardinal arithmetic is built from bijections, which are functions that are simultaneously injective and surjective.
• Computer science. In functional programming and formal semantics, a program's meaning is often modeled as a (possibly partial) function from inputs to outputs; the totality/partiality distinction traces directly back to whether clause (1) above holds on the stated domain, and type systems are designed precisely to catch "undefined at some inputs" errors at compile time.
• Database theory. A relational database table enforces "functional dependencies" — constraints stating that one column's value determines another's — which are exactly instances of the single-valuedness clause applied to projections of a relation.
• Cryptography. Hash functions, encryption maps, and pseudorandom generators are all functions in this exact sense: total, single-valued maps between finite sets (bit-strings of fixed length), and security proofs frequently hinge on properties like injectivity (collision-resistance) built on top of this base definition.
• Probability and statistics. Random variables are defined as measurable functions from a sample space to $\mathbb{R}$; the single-valuedness clause is what guarantees a random variable assigns one, not several, numerical outcomes to each sample point.
• Physics and engineering. Physical laws expressed as functions of state (e.g., pressure as a function of volume and temperature) implicitly rely on this same single-valuedness: a genuine state function cannot take two different values for one and the same state, which is exactly the mathematical content of clause (2).

Ask the tutor: How does the definition of function as a relation change when we move to partial functions, and why do computer scientists care about that distinction?

Think of a relation $R \subseteq A \times B$ as a bipartite "wiring diagram": draw the elements of $A$ on the left, elements of $B$ on the right, and an edge from $a$ to $b$ whenever $(a,b) \in R$. An arbitrary relation allows any pattern of wires whatsoever — an element of $A$ might have no wires, one wire, or five wires leaving it. A function is the special case where the wiring is tidy on the left: every element of $A$ has exactly one wire coming out of it. There is no restriction at all on the right-hand side — an element of $B$ may have zero incoming wires (it lies outside the range), one incoming wire, or many incoming wires (several elements of $A$ can share the same output). This is precisely what "single-valued and total" is encoding, and it is worth internalizing as a picture: totality forbids missing wires from the left, single-valuedness forbids forked wires from the left. Neither condition says anything about the right side of the diagram — that asymmetry is exactly what later gets named and studied as injectivity (no two left-elements share a wire) and surjectivity (every right-element receives a wire).

Example 1 (a genuinely finite, asymmetric function). Let $A = \{1, 2, 3, 4\}$ and $B = \{p, q, r, s, t\}$. Define

Check totality: every element of $A$ — namely $1,2,3,4$ — appears as a first coordinate in some pair of $G$. Indeed $1$ appears in $(1,q)$, $2$ in $(2,q)$, $3$ in $(3,t)$, $4$ in $(4,p)$. Totality holds. Check single-valuedness: we must confirm no first coordinate appears twice with different second coordinates. Scanning $G$, the first coordinates used are $1,2,3,4$, each occurring exactly once. So there is no possibility of a conflict; single-valuedness holds vacuously well (there is simply nothing to conflict). Hence $G$ is (the graph of) a function $f : A \to B$, with $f(1) = q$, $f(2) = q$, $f(3) = t$, $f(4) = p$. Now examine domain, codomain, range carefully, since this is where the asymmetry of the example matters:

• $\operatorname{dom}(f) = A = \{1,2,3,4\}$.
• Codomain is the declared target $B = \{p,q,r,s,t\}$, a set of size $5$.
• $\operatorname{ran}(f) = \{q, t, p\}$, a set of size $3$.

Note $r, s \in B$ are never hit: $\operatorname{ran}(f) \subsetneq B$. Note also $q$ is hit twice (by both $1$ and $2$) — this is completely permitted, since single-valuedness constrains only the left side of the wiring diagram. This example shows concretely that codomain and range are different objects in general: a codomain is a choice made when the function is declared, while the range is computed after the fact from the graph.

Example 2 (when a "formula" fails to define a function on a stated domain, and how to fix it). Let $A = \mathbb{Z}$, $B = \mathbb{Q}$, and consider the candidate rule

Set $G = \{(n, h(n)) : n \in \mathbb{Z},\ n \neq \pm 2\}$, i.e. we attempt to make $G \subseteq \mathbb{Z} \times \mathbb{Q}$ by including a pair for every integer $n$ where the formula is defined. Test totality on $A = \mathbb{Z}$: does every $n \in \mathbb{Z}$ appear as a first coordinate? Take $n = 2$: the formula gives $\frac{2}{4-4} = \frac{2}{0}$, undefined, so there is no pair $(2, b) \in G$ for any $b$. Totality on $A = \mathbb{Z}$ fails. Hence, strictly, $G$ is not a function from $\mathbb{Z}$ to $\mathbb{Q}$ — the formula does not deserve to be called "$h : \mathbb{Z} \to \mathbb{Q}$" as declared, and a homework answer asserting this without comment is an error of exactly the kind this article is built to catch. The fix: restrict the domain to $A' = \mathbb{Z} \setminus \{2, -2\}$ and declare $h : A' \to \mathbb{Q}$. Now recheck both clauses.

• Totality on $A'$: for every $n \in A'$ (so $n \neq \pm 2$), $n^2 - 4 \neq 0$, so $h(n) = n/(n^2-4)$ is a well-defined rational number; a pair $(n, h(n))$ exists in $G$. Totality holds.
• Single-valuedness: for fixed $n$, the expression $n/(n^2-4)$ names one specific rational number (division of specific integers by a specific nonzero integer produces one rational number, by the definition of $\mathbb{Q}$ as equivalence classes of pairs, per Quotient Sets and Well-Definedness). So there cannot be two different $b_1 \neq b_2$ both equal to $h(n)$. Single-valuedness holds.

So $h : \mathbb{Z}\setminus\{2,-2\} \to \mathbb{Q}$ is a function. Let's compute a few values to see the range is a proper, and rather sparse, subset of $\mathbb{Q}$:

Notice $h(-n) = -h(n)$ for all $n$ in the domain — a genuine algebraic fact about this particular function, not something guaranteed by the definition of "function" itself; it is a special feature (oddness) of this graph, illustrating that the bare definition of function says nothing about such symmetries — they must be proved separately from the formula.