A Rule That Gives One Output for Every Input
The previous tutorial described partitions as collections of blocks that divide a set. We now turn from grouping elements to assigning outputs to inputs. A function is not merely a formula: it is a mapping between specified sets, with a requirement about what happens to each input. The familiar expression \(x^2\), for example, can describe different functions depending on which inputs and outputs are allowed.
Let \(A\) and \(B\) be sets. A function from \(A\) to \(B\) assigns to each element \(a\in A\) one and only one element \(b\in B\). We write $$ f:A\to B $$ to indicate that \(f\) is a function with input set \(A\) and output set \(B\). For each \(a\in A\), its assigned output is denoted by \(f(a)\). Thus \(f(a)=b\) means that \(f\) sends \(a\) to \(b\).
The phrase “one and only one” has two separate requirements. Existence means every input has an output. Uniqueness means the same input is not assigned two different outputs. Both requirements apply to every element of \(A\), including inputs that might otherwise be overlooked.
Functions as Relations
A relation from \(A\) to \(B\) is a subset of the Cartesian product \(A\times B\), so its members are ordered pairs \((a,b)\) with \(a\in A\) and \(b\in B\). This gives a precise set-based way to represent a mapping: include the pair \((a,b)\) exactly when the function sends \(a\) to \(b\). The resulting set of ordered pairs is called the graph of the function: $$ \Gamma_f=\{(a,f(a)):a\in A\}. $$ In particular, the graph records all input-output assignments, not just a selection of examples.
The defining condition can be stated entirely in terms of ordered pairs. A relation \(R\subseteq A\times B\) represents a function from \(A\) to \(B\) precisely when, for every \(a\in A\), there is exactly one \(b\in B\) such that \((a,b)\in R\). The next theorem makes this criterion explicit.
Theorem (Relation Criterion for a Function). Let \(A\) and \(B\) be sets, and let \(R\subseteq A\times B\). Then \(R\) is the graph of a function from \(A\) to \(B\) if and only if $$ \text{for every }a\in A,\text{ there exists exactly one }b\in B \text{ such that }(a,b)\in R. $$
Proof. First suppose \(R\) is the graph of a function \(f:A\to B\). Let \(a\in A\). Because \(f\) assigns an output to \(a\), the element \(b=f(a)\) belongs to \(B\), and \((a,b)\in R\). Thus at least one such \(b\) exists. Now suppose \(c\in B\) also satisfies \((a,c)\in R\). Since \(R=\Gamma_f\), there is some \(a'\in A\) such that \((a,c)=(a',f(a'))\). Equality of ordered pairs gives \(a=a'\) and \(c=f(a')=f(a)=b\). Therefore the output is unique.
Conversely, suppose that for every \(a\in A\) there exists exactly one \(b\in B\) such that \((a,b)\in R\). For each \(a\in A\), assign that unique \(b\) as the output \(f(a)\). The assumption ensures that this assignment is defined for every input and gives exactly one value in \(B\). Hence it defines a function \(f:A\to B\). Its graph consists exactly of the pairs in \(R\): each pair in \(R\) has a first coordinate in \(A\), and its second coordinate must be the unique assigned output for that input; conversely each assigned output was selected from a pair in \(R\). Thus \(R=\Gamma_f\), proving the criterion. \(\square\)
Worked Example: A Finite Mapping Given by Its Graph
Let \(A=\{p,q,r\}\), \(B=\{1,2\}\), and $$ R=\{(p,1),(q,2),(r,1)\}. $$ Every first coordinate in \(A\) appears in exactly one pair of \(R\). Specifically, \(p\) is paired with \(1\), \(q\) with \(2\), and \(r\) with \(1\). There are no other pairs in \(R\), so none of these inputs receives a second output. The relation criterion shows that \(R\) is the graph of a function \(f:A\to B\), given by $$ f(p)=1,\qquad f(q)=2,\qquad f(r)=1. $$ The fact that both \(p\) and \(r\) have output \(1\) does not violate the definition: uniqueness concerns the output for each fixed input, not the number of inputs that may share an output.
Checking Both Requirements
A proposed rule can fail to be a function in two different ways. It may fail to assign any output to an input in its stated input set, or it may assign more than one output to the same input. These failures are independent: a relation can meet one requirement while failing the other. When the input set is finite, checking each input directly is often the clearest method.
Worked Example: A Relation with a Missing Output
Let \(A=\{u,v,w\}\), \(B=\{0,1\}\), and $$ R=\{(u,0),(w,1)\}. $$ Every pair listed is in \(A\times B\), and neither \(u\) nor \(w\) is paired with more than one output. However, there is no pair in \(R\) whose first coordinate is \(v\). Thus no \(b\in B\) satisfies \((v,b)\in R\). Existence fails for the input \(v\), so \(R\) is not the graph of a function from \(A\) to \(B\). The fact that all the pairs which do appear are unambiguous does not repair the missing assignment.
Worked Example: A Relation with Conflicting Outputs
Let \(A=\{s,t\}\), \(B=\{4,5,6\}\), and $$ S=\{(s,4),(s,5),(t,6)\}. $$ Every input appears: \(s\) has at least one output, and \(t\) has an output. But \(s\) is paired with both \(4\) and \(5\), and \(4\ne5\). The output for \(s\) is therefore not unique. The relation criterion fails, so \(S\) is not the graph of a function from \(A\) to \(B\). Removing \((s,5)\), for instance, would leave each input with exactly one output and would produce a function graph.
For a rule given by a formula, the same test still applies. The formula must produce a defined value in the target set for every permitted input, and the rule must determine only one value for each input. A formula may be perfectly clear while its domain is not: without knowing which inputs are permitted, it is not yet a fully specified mapping.
Worked Example: Squaring on the Integers
Consider the mapping \(g:\mathbb Z\to\mathbb Z\) defined by \(g(n)=n^2\). For any integer \(n\), its square \(n^2\) is an integer, so the output belongs to the target set. The usual multiplication of \(n\) by itself determines exactly one integer, so each input has exactly one output. Therefore this rule defines a function. For example, \(g(-4)=(-4)^2=16\) and \(g(3)=3^2=9\). The two different inputs \(-4\) and \(4\) both have output \(16\); that is permitted. In contrast, saying only “take the square root” would need further specification to determine whether one output or more than one is intended.
What Specifies a Function?
A mapping is determined by more than a computational instruction. One must state the input set, the target set, and the assignment rule. For example, the squaring formula can be used to define \(g:\mathbb Z\to\mathbb Z\) by \(g(n)=n^2\), or a mapping on a smaller input set by restricting which inputs are allowed. Those descriptions can have different collections of inputs even though the calculation rule is the same.
The target set matters too. A value produced by the rule must belong to it. The formula \(h(x)=x+1\), for example, defines a mapping \(\mathbb Z\to\mathbb Z\), since adding \(1\) to an integer gives an integer. It also defines a mapping \(\mathbb Z\to\mathbb R\), since every integer is a real number. These are mappings with different specified target sets, even though the output assigned to each integer is the same. The next tutorial will examine the domain, codomain, and range terminology in detail.
Equality of Functions
Once two functions have the same input set and target set, equality means that they assign the same output to every input. This is a practical way to prove that two mappings are equal: take an arbitrary input and compare the values assigned by each function. The graph viewpoint explains why this pointwise test is enough.
Theorem (Pointwise Equality Criterion). Let \(f,g:A\to B\). Then $$ f=g \quad\Longleftrightarrow\quad f(a)=g(a)\text{ for every }a\in A. $$
Proof. Suppose first that \(f=g\). Since equal functions have the same assignments, for each \(a\in A\) the output \(f(a)\) equals \(g(a)\). Thus the values agree for every input.
Conversely, suppose \(f(a)=g(a)\) for every \(a\in A\). We show that their graphs are equal. Let \((a,b)\in\Gamma_f\). By the definition of the graph, \(a\in A\) and \(b=f(a)\). The assumed pointwise equality gives \(b=f(a)=g(a)\), so \((a,b)=(a,g(a))\in\Gamma_g\). Hence \(\Gamma_f\subseteq\Gamma_g\). Reversing the roles of \(f\) and \(g\) gives \(\Gamma_g\subseteq\Gamma_f\). Equality by double inclusion yields \(\Gamma_f=\Gamma_g\), and therefore \(f=g\). \(\square\)
The requirement that the two mappings have the same specified input and target sets is part of the theorem’s setup. Comparing just a few input-output pairs is not enough; the condition requires agreement at every input. If \(A\) is empty, the statement still holds: both functions have no input values to compare, and there is exactly one graph, the empty set, for a function from the empty set to \(B\).
Worked Example: Proving Two Descriptions Agree
Let \(A=\{0,1,2\}\), let \(B=\{0,1,4\}\), and define \(f,g:A\to B\) by $$ f(x)=x^2,\qquad g(x)= \begin{cases} 0,&x=0,\\ 1,&x=1,\\ 4,&x=2. \end{cases} $$ For an arbitrary \(x\in A\), one of the three cases \(x=0\), \(x=1\), or \(x=2\) holds. If \(x=0\), then \(f(x)=0=g(x)\). If \(x=1\), then \(f(x)=1=g(x)\). If \(x=2\), then \(f(x)=4=g(x)\). Thus \(f(x)=g(x)\) for every \(x\in A\). Since both mappings have the same input and target sets, the pointwise equality criterion gives \(f=g\).
The mapping viewpoint will be used throughout the study of functions: specify the sets, verify that every input receives exactly one allowed output, and reason about values through the notation \(f(a)\). This makes it possible to distinguish a genuine function from an incomplete or ambiguous rule before studying more detailed properties.
Check Your Understanding
- State the two requirements that every input must satisfy for a relation \(R\subseteq A\times B\) to be a function graph from \(A\) to \(B\).
- Can two distinct inputs of a function have the same output? Explain why.
- Let \(A=\{1,2\}\) and \(R=\{(1,a),(1,b),(2,c)\}\), where \(a\ne b\). Which function requirement fails?
- Why must the target set be specified along with an assignment rule?
- For \(f,g:A\to B\), what condition on their values is equivalent to \(f=g\)?