4.3: Functions

Domains and Images

A function assigns an element of one set, called the domain, to an element of another set, called the codomain. The notation

\[\nonumber f: A \rightarrow B\]

indicates that \(f\) is a function with domain, \(A\), and codomain, \(B\). The familiar notation “\(f(a) = b\)” indicates that \(f\) assigns the element \(b \in B\) to \(a\). Here \(b\) would be called the value of \(f\) at argument \(a\).

Functions are often defined by formulas, as in:

\[\nonumber f_1(x) ::= \frac{1}{x^2}\]

where \(x\) is a real-valued variable, or

\[\nonumber f_2(y, z) ::= y10yz\]

where \(y\) and \(z\) range over binary strings, or

\[\nonumber f_3(x, n) ::= \text{the length } n \text{ sequence } \underbrace{(x, \ldots , x)}_{n \text{ } x \text{'s}}\]

where \(n\) ranges over the nonnegative integers.

A function with a finite domain could be specified by a table that shows the value of the function at each element of the domain. For example, a function \(f_4(P, Q)\) where \(P\) and \(Q\) are propositional variables is specified by:

\[\nonumber \begin{array}{|cc|c|}
\hline P & Q & f_{4}(P, Q) \\
\hline \mathbf{T} & \mathbf{T} & \mathbf{T} \\
\hline \mathbf{T} & \mathbf{F} & \mathbf{F} \\
\hline \mathbf{F} & \mathbf{T} & \mathbf{T} \\
\hline \mathbf{F} & \mathbf{F} & \mathbf{T} \\
\hline
\end{array}\]

Notice that \(f_4\) could also have been described by a formula:

\[\nonumber f_4(P, Q) ::= [P \text{ IMPLIES } Q].\]

A function might also be defined by a procedure for computing its value at any element of its domain, or by some other kind of specification. For example, define \(f_5(y)\) to be the length of a left to right search of the bits in the binary string \(y\) until a 1 appears, so

\[\begin{aligned} f_5(0010) &= 3, \\ f_5(100) &= 1, \\ f_5(0000) &\text{ is undefined.} \end{aligned}\]

Notice that \(f_5\) does not assign a value to any string of just 0’s. This illustrates an important fact about functions: they need not assign a value to every element in the domain. In fact this came up in our first example \(f_1(x) = 1 / x^2\), which does not assign a value to 0. So in general, functions may be partial functions, meaning that there may be domain elements for which the function is not defined. If a function is defined on every element of its domain, it is called a total function.

It’s often useful to find the set of values a function takes when applied to the elements in a set of arguments. So if \(f: A \rightarrow B\), and \(S\) is a subset of \(A\), we define \(f(S)\) to be the set of all the values that \(f\) takes when it is applied to elements of \(S\). That is,

\[\nonumber f(S) ::= \{b \in B \mid f(s) = b \text{ for some } s \in S\}\]

For example, if we let \([r, s]\) denote set of numbers in the interval from \(r\) to \(s\) on the real line, then \(f_1([1, 2]) = [1/4, 1].\)

For another example, let’s take the “search for a 1” function, \(f_5\). If we let \(X\) be the set of binary words which start with an even number of 0’s followed by a 1, then \(f_5(X)\) would be the odd nonnegative integers.

Applying \(f\) to a set, \(S\), of arguments is referred to as “applying \(f\) pointwise to \(S\)”, and the set \(f(S)\) is referred to as the image of \(S\) under \(f\).⁴ The set of values that arise from applying \(f\) to all possible arguments is called the range of \(f\). That is,

\[\nonumber\text{range}(f) ::= f(\text{domain}(f)).\]

Some authors refer to the codomain as the range of a function, but they shouldn’t. The distinction between the range and codomain will be important later in Sections 4.5 when we relate sizes of sets to properties of functions between them.

Function Composition

Doing things step by step is a universal idea. Taking a walk is a literal example, but so is cooking from a recipe, executing a computer program, evaluating a formula, and recovering from substance abuse.

Abstractly, taking a step amounts to applying a function, and going step by step corresponds to applying functions one after the other. This is captured by the operation of composing functions. Composing the functions \(f\) and \(g\) means that first \(f\) is applied to some argument, \(x\), to produce \(f(x)\), and then \(g\) is applied to that result to produce \(g(f(x))\).

Definition \(\PageIndex{1}\)

For functions \(f : A \rightarrow B\) and \(g : B \rightarrow C\), the composition, \(g \circ f\), of \(g\) with \(f\) is defined to be the function from \(A\) to \(C\) defined by the rule:

\[\nonumber (g \circ f)(x) ::= g(f(x)),\]

for all \(x \in A.\)

Function composition is familiar as a basic concept from elementary calculus, and it plays an equally basic role in discrete mathematics.

 

⁴There is a picky distinction between the function \(f\) which applies to elements of \(A\) and the function which applies \(f\) pointwise to subsets of \(A\), because the domain of \(f\) is \(A\), while the domain of pointwise-\(f\) is pow\((A)\). It is usually clear from context whether \(f\) or pointwise-\(f\) is meant, so there is no harm in overloading the symbol \(f\) in this way.