Functions play a central role in probability and statistics, as they do in every other branch of mathematics. For the most part, the proofs in this section are straightforward, so be sure to try them yourself before reading the ones in the text.
We start with the formal, technical definition of a function. It's not very intuitive, but has the advantage that it only set theory.
A function \(f\) from a set \(S\) into a set \(T\) is a subset of the product set \(S \times T\) with the property that for each element \(x \in S\), there exists a unique element \(y \in T\) such that \((x, y) \in f\). If \(f\) is a function from \(S\) to \(T\) we write \(f: S \to T\). If \((x, y) \in f\) we write \(y = f(x)\).
Less formally, a function \(f\) from \(S\) into \(T\) is a rule
(or procedure
or algorithm
) that assigns to each \(x \in S\) a unique element \(f(x) \in T\). The definition of a function as a set of ordered pairs, is due to Kazimierz Kuratowski. The term map or mapping is also used in place of function, so we could say that \(f\) maps \(S\) into \(T\).
The sets \(S\) and \(T\) in the definition are clearly important.
Suppose that \(f: S \to T\).
The domain and range are completely specified by a function. That's not true of the co-domain: if \(f\) is a function from \(S\) into \(T\), and \(U\) is another set with \(T \subseteq U\), then we can also think of \(f\) as a function from \(S\) into \(U\). The following definitions are natural and important.
Suppose again that \(f: S \to T\).
Clearly a function always maps its domain onto its range. Note also that \(f\) is one-to-one if \( f(u) = f(v) \) implies \( u = v \) for \(u, \, v \in S\).
A funtion that is one-to-one and onto can be reversed
in a sense.
If \(f\) maps \(S\) one-to-one onto \(T\), the inverse of \(f\) is the function \(f^{-1}\) from \(T\) onto \(S\) given by \[ f^{-1}(y) = x \iff f(x) = y; \quad x \in S, \; y \in T \]
If you like to think of a function as a set of ordered pairs, then \(f^{-1} = \{(y, x) \in T \times S: (x, y) \in f\}\). The fact that \(f\) is one-to-one and onto ensures that \(f^{-1}\) is a valid function from \(T\) onto \(S\). Sets \(S\) and \(T\) are in one-to-one correspondence if there exists a one-to-one function from \(S\) onto \(T\). One-to-one correspondence plays an essential role in the study of cardinality. In addition, recall that a mathematical space consists of a set and various structures defined in terms of the set, such as relations, operators, or a collection of subsets. Loosely speaking, two mathematical spaces of the same type are isomorphic if there exists a one-to-one function from one of the sets onto the other that preserves the structures, and again, the function is called an isomorphism. The basic idea is that isomorphic spaces are mathematically identical, except for superficial matters of appearance. The word isomorphism is from the Greek and means equal shape.
The domain of a function can be restricted to create a new funtion.
Suppose that \(f: S \to T\) and that \(A \subseteq S\). The function \(f_A: A \to T\) defined by \(f_A(x) = f(x)\) for \( x \in A \) is the restriction of \(f\) to \(A\).
As a set of ordered pairs, note that \(f_A = \{(x, y) \in f: x \in A\}\).
Composition is perhaps the most important way to combine two functions to create another function.
Suppose that \(g: R \to S\) and \(f: S \to T\). The composition of \(f\) with \(g\) is the function \(f \circ g: R \to T\) defined by \[ \left(f \circ g\right)(x) = f\left(g(x)\right), \quad x \in R \]
Composition is associative:
Suppose that \(h: R \to S\), \(g: S \to T\), and \(f: T \to U\). Then \[ f \circ \left(g \circ h\right) = \left(f \circ g\right) \circ h \]
Note that both functions map \( R \) into \( U \). Using the definition of composition, the value of both functions at \( x \in R \) is \( f\left(g\left(h(x)\right)\right) \).
Thus we can write \(f \circ g \circ h\) without ambiguity. On the other hand, composition is not commutative. Indeed depending on the domains and co-domains, \( f \circ g \) might be defined when \( g \circ f \) is not. Even when both are defined, they may have different domains and co-domains, and so of course cannot be the same function. Even when both are defined and have the same domains and co-domains, the two compositions will not be the same in general. Examples of all of these cases are given in and
Suppose that \(g: R \to S\) and \(f: S \to T\).
The identity function on a set \(S\) is the function \(I_S\) from \(S\) onto \(S\) defined by \(I_S(x) = x\) for \(x \in S\)
The identity function acts like an identity with respect to the operation of composition.
If \(f: S \to T\) then
The inverse of a function is really the inverse with respect to composition.
Suppose that \(f\) is a one-to-one function from \(S\) onto \(T\). Then
An element \(x \in S^n\) can be thought of as a function from \(\{1, 2, \ldots, n\}\) into \(S\). Similarly, an element \(x \in S^\infty\) can be thought of as a function from \(\N_+\) into \(S\). For such a sequence \(x\), of course, we usually write \(x_i\) instead of \(x(i)\). More generally, if \(S\) and \(T\) are sets, then the set of all functions from \(S\) into \(T\) is denoted by \(T^S\). In particular, as we noted in the last section, \( S^\infty \) is also (and more accurately) written as \( S^{\N_+} \).
Suppose that \(g\) is a one-to-one function from \(R\) onto \(S\) and that \(f\) is a one-to-one function from \(S\) onto \(T\). Then \(\left(f \circ g\right)^{-1} = g^{-1} \circ f^{-1}\).
Note that \( (f \circ g)^{-1}: T \to R \) and \( g^{-1} \circ f^{-1}: T \to R \). For \( y \in T \), let \(x = \left(f \circ g\right)^{-1}(y) \). Then \( \left(f \circ g\right)(x) = y \) so that \( f\left(g(x)\right) = y \) and hence \( g(x) = f^{-1}(y) \) and finally \( x = g^{-1}\left(f^{-1}(y)\right) \).
Inverse images of a function play a fundamental role in probability, particularly in the context of random variables.
Suppose that \(f: S \to T\). If \(A \subseteq T\), the inverse image of \(A\) under \(f\) is the subset of \(S\) given by \[f^{-1}(A) = \{x \in S: f(x) \in A\}\]
So \(f^{-1}(A)\) is the subset of \(S\) consisting of those elements that map into \(A\).
Technically, the inverse images define a new function from \(\ms P(T)\) into \(\ms P(S)\). We use the same notation as for the inverse function, which is defined when \(f\) is one-to-one and onto. These are very different functions, but usually no confusion results. The following important result shows that inverse images preserve all set operations.
Suppose that \(f: S \to T\), and that \(A, \, B \subseteq T\). Then
Part (a) of holds for arbitrary unions, and part (b) holds for arbitrary intersections. No new ideas are involved; only the notation is more complicated.
Suppose that \( \{A_i: i \in I\} \) is a collection of subsets of \( T \), where \( I \) is a nonempty index set. Then
Forward images of a function are a naturally complement to inverse images.
Suppose again that \(f: S \to T\). If \(A \subseteq S\), the forward image of \(A\) under \(f\) is the subset of \(T\) given by \[ f(A) = \left\{f(x): x \in A\right\} \]
So \(f(A)\) is the range of \(f\) restricted to \(A\).
Technically, the forward images define a new function from \(\ms P(S)\) into \(\ms P(T)\), but we use the same symbol \(f\) for this new function as for the underlying function from \(S\) into \(T\) that we started with. Again, the two functions are very different, but usually no confusion results.
It might seem that forward images are more natural than inverse images, but in fact, the inverse images are much more important than the forward ones, at least in probability theory, measure theory, and topology. Fortunately, the inverse images are nicer as well—unlike the inverse images, the forward images do not preserve all of the set operations.
Suppose that \(f: S \to T\), and that \(A, \, B \subseteq S\). Then
Part (a) of hold for arbitrary unions, and part (b) hold for arbitrary intersections. No new ideas are involved; only the notation is more complicated.
Suppose that \( \{A_i: i \in I\} \) is a collection of subsets of \( S \), where \( I \) is a nonempty index set. Then
Suppose again that \(f: S \to T\). As noted earlier, the forward images of \(f\) define a function from \(\ms P(S)\) into \(\ms P(T)\) and the inverse images define a function from \(\ms P(T)\) into \(\ms P(S)\). One might hope that these functions are inverses of one another, but alas no.
Suppose that \(f: S \to T\).
Real-valued function on a given set \(S\) are of particular importance. The usual arithmetic operations on such functions are defined pointwise.
Suppose that\( f, \, g: S \to \R \) and \( c \in \R \), then \( f + g, \, f - g, \, f g, \, c f, \, f / g: S \to \R\) are defined as follows for all \( x \in S \).
Now let \(\ms V\) denote the collection of all functions from the given set \(S\) into \(\R\). A fact that is very important in probability as well as other branches of analysis is that \( \ms V \), with addition and scalar multiplication as defined above, is a vector space. The zero function \( \bs 0 \) is defined, of course, by \( \bs{0}(x) = 0 \) for all \( x \in S \).
\( (\ms V, +, \cdot) \) is a vector space over \( \R \). That is, for all \( f, \, g, \, h \in \ms V \) and \( a, \, b \in \R \)
Each of these properties follows from the corresponding property in \( \R \).
Various subspaces of \( \ms V \) are important in probability as well. We will return to the discussion of vector spaces of functions in a later section.
For our next discussion, suppose that \(S\) is the universal set, so that all other sets mentioned are subsets of \(S\).
Suppose that \(A \subseteq S\). The indicator function of \(A\) is the function \(\bs 1_A: S \to \{0, 1\}\) defined as follows: \[ \bs 1_A(x) = \begin{cases} 1, & x \in A \\ 0, & x \notin A \end{cases} \]
Thus, the indicator function of \( A \) simply indicates whether or not \( x \in A \) for each \( x \in S \). Conversely, any function on \(S\) that just takes the values 0 and 1 is an indicator function.
If \(f: S \to \{0, 1\}\) then \(f\) is the indicator function of the set \(A = f^{-1}\{1\} = \{x \in S: f(x) = 1\}\).
Thus, there is a one-to-one correspondence between \(\ms P(S)\), the power set of \(S\), and the collection of indicator functions \(\{0, 1\}^S\). The next result shows how the set algebra of subsets corresponds to the arithmetic algebra of the indicator functions.
Suppose that \(A, \, B \subseteq S\). Then
Part (a) of extends to arbitrary intersections and part (b) extends to arbitrary unions.
Suppose that \( \{A_i: i \in I\} \) is a collection of subsets of \( S \), where \( I \) is a nonempty index set. Then
In general, a product over an infinite index set may not make sense. But if all of the factors are either 0 or 1, as they are here, then we can simply define the product to be 1 if all of the factors are 1, and 0 otherwise.
A multiset is like an ordinary set, except that elements may be repeated. A multiset \( A \) (with elements from a universal set \( S \)) can be uniquely associated with its multiplicity function \( m_A: S \to \N \), where \( m_A(x) \) is the number of times that element \( x \) is in \( A \) for each \( x \in S \). So the multiplicity function of a multiset plays the same role that an indicator function does for an ordinary set. Multisets arise naturally when objects are sampled with replacement (but without regard to order) from a population. Various sampling models are explored in the section on combinatorial Structures. We will not go into detail about the operations on multisets, but the definitions are straightforward generalizations of those for ordinary sets.
Suppose that \( A \) and \( B \) are multisets with elements from the universal set \( S \). Then
Using functions, we can generalize Cartesian products. In this discussion, we suppose that \(S_i\) is a set for each \(i\) in a nonempty index set \(I\).
Define the product set \[ \prod_{i \in I} S_i = \left\{x: x \text{ is a function from } I \text{ into } \bigcup_{i \in I} S_i \text{ such that } x(i) \in S_i \text{ for each } i \in I\right\} \]
Note that except for being nonempty, there are no assumptions on the cardinality of the index set \( I \). Of course, if \( I = \{1, 2 \ldots, n\} \) for some \( n \in \N_+ \), or if \( I = \N_+ \) then this construction reduces to \( S_1 \times S_2 \times \cdots \times S_n \) and to \( S_1 \times S_2 \times \cdots \), respectively. Since we want to make the notation more closely resemble that of simple Cartesian products, we will write \( x_i \) instead of \( x(i) \) for the value of the function \( x \) at \( i \in I \), and we sometimes refer to this value as the \( i \)th coordinate of \( x \). Finally, note that if \( S_i = S \) for each \( i \in I \), then \( \prod_{i \in I} S_i \) is simply the set of all functions from \( I \) into \( S \), which we denoted by \( S^I \) above.
For \( j \in I \) define the projection \( p_j: \prod_{i \in I} S_i \to S_j \) by \( p_j(x) = x_j \) for \( x \in \prod_{i \in I} S_i \).
So \( p_j(x) \) is just the \( j \)th coordinate of \( x \). The projections are of basic importance for product spaces. In particular, we have a better way of looking at projections of a subset.
For \( A \subseteq \prod_{i \in I} S_i \) and \( j \in I \), the forward image \( p_j(A) \), as defined in , is the projection of \( A \) onto \( S_j \).
Note that \( p_j(A) = \{p_j(x): x \in A\} = \{x_j: x \in A\} \), the set of all \( j \)th coordinates of the points in \( A \).
So the properties of projection that we studied in the last section are just special cases of the properties of forward images. Projections also allow us to get coordinate functions in a simple way.
Suppose that \( R \) is a set, and that \( f: R \to \prod_{i \in I} S_i \). If \( j \in I \) then \( p_j \circ f : R \to S_j \) is the \( j \)th coordinate function of \( f \).
Note that for \( x \in R \), \( (p_j \circ f)(x) = p_j[f(x)] = f_j(x) \), the \( j \)th coordinate of \( f(x) \in \prod_{i \in I} S_i \).
This will look more familiar for a simple cartesian product. If \( f: R \to S_1 \times S_2 \times \cdots \times S_n \), then \( f = (f_1, f_2, \ldots, f_n) \) where \( f_j: R \to S_i \) is the \( j \)th coordinate function for \( j \in \{1, 2, \ldots, n\} \).
Cross sections of a subset of a product set can be expressed in terms of inverse images of a function as defined in . First we need some additional notation. Suppose that our index set \( I \) has at least two elements. For \( j \in I \) and \( u \in S_j \), define \( j_u : \prod_{i \in I - \{j\}} S_i \to \prod_{i \in I} S_i \) by \( j_u (x) = y \) where \( y_i = x_i \) for \( i \in I - \{j\} \) and \( y_j = u \). In words, \( j_u \) takes a point \( x \in \prod_{i \in I - \{j\}} S_i \) and assigns \( u \) to coordinate \( j \) to produce the point \( y \in \prod_{i \in I} S_i \).
In the setting above, if \( j \in I \), \( u \in S_j \) and \( A \subseteq \prod_{i \in I} S_i \) then \(j_u^{-1}(A)\) is the cross section of \( A \) in the \( j \)th coordinate at \( u \).
This follows from the definition of cross section: \( j_u^{-1}(A) \) is the set of all \(x \in \prod_{i \in I - \{j\}} S_i \) such that \( y \) defined above is in \( A \) and has \( j \)th coordinate \( u \).
Let's look at this for the product of two sets \( S \) and \( T \). For \( x \in S \), the function \( 1_x: T \to S \times T \) is given by \( 1_x(y) = (x, y) \). Similarly, for \( y \in T \), the function \( 2_y: S \to S \times T \) is given by \( 2_y(x) = (x, y) \). Suppose now that \( A \subseteq S \times T \). If \( x \in S \), then \( 1_x^{-1}(A) = \{y \in T: (x, y) \in A\} \), the very definition of the cross section of \( A \) in the first coordinate at \( x \). Similarly, if \( y \in T \), then \( 2_y^{-1}(A) = \{x \in S: (x, y) \in A\} \), the very definition of the cross section of \( A \) in the second coordinate at \( y \). This construction is not particularly important except to show that cross sections are inverse images. Thus the fact that cross sections preserve all of the set operations is a simple consequence of the fact that inverse images generally preserve set operations.
Sometimes functions have special interpretations in certain settings.
Suppose that \(S\) is a set.
As the names suggests, a unary operator \(f\) operates on an element \(x \in S\) to produce a new element \(f(x) \in S\). Similarly, a binary operator \(g\) operates on a pair of elements \((x, y) \in S \times S\) to produce a new element \(g(x, y) \in S\). The arithmetic operators are quintessential examples:
The following are operators on \(\R\):
For a fixed universal set \(S\), the set operators studied in the section on sets provide other examples.
For a given set \(S\), the following are operators on \(\ms P(S)\):
As these examples illustrate, a binary operator is often written as \( x \, f \, y \) rather than \( f(x, y) \). Still, it is useful to know that operators are simply functions of a special type.
Suppose that \(f\) is a unary operator on a set \(S\), \(g\) is a binary operator on \(S\), and that \(A \subseteq S\).
Thus if \(A\) is closed under the unary operator \(f\), then \(f\) restricted to \(A\) is unary operator on \(A\). Similary if \(A\) is closed under the binary operator \(g\), then \(g\) restricted to \(A \times A\) is a binary operator on \(A\). Let's return to our most basic example.
For the arithmetic operatoes on \(\R\),
Many properties that you are familiar with for special operators (such as the arithmetic and set operators) can now be formulated generally.
Suppose that \(f\) and \(g\) are binary operators on a set \(S\). In the following definitions, \(x\), \(y\), and \(z\) are arbitrary elements of \(S\).
Suppose that \(\ms{S}\) is a collection of nonempty subsets of a set \(S\). The axiom of choice states that there exists a function \(f: \ms{S} \to S\) with the property that \(f(A) \in A\) for each \(A \in \ms{S}\). The function \(f\) is known as a choice function.
Stripped of most of the mathematical jargon, the idea is very simple. Since each set \(A \in \ms{S}\) is nonempty, we can select an element of \(A\); we will call the element we select \(f(A)\) and thus our selections define a function. In fact, you may wonder why we need an axiom at all. The problem is that we have not given a rule (or procedure or algorithm) for selecting the elements of the sets in the collection. Indeed, we may not know enough about the sets in the collection to define a specific rule, so in such a case, the axiom of choice simply guarantees the existence of a choice function. Some mathematicians, known as constructionists do not accept the axiom of choice, and insist on well defined rules for constructing functions.
A nice consequence of the axiom of choice is a type of duality between one-to-one functions and onto functions.
Suppose that \(f\) is a function from a set \(S\) onto a set \(T\). There exists a one-to-one function \(g\) from \(T\) into \(S\).
For each \(y \in T\), the set \(f^{-1}\{y\}\) is non-empty, since \(f\) is onto. By the axiom of choice, we can select an element \(g(y)\) from \(f^{-1}\{y\}\) for each \(y \in T\). The resulting function \(g\) is one-to-one.
Suppose that \(f\) is a one-to-one function from a set \(S\) into a set \(T\). There exists a function \(g\) from \(T\) onto \(S\).
Fix a special element \(x_0 \in S\). If \(y \in \text{range}(f)\), there exists a unique \(x \in S\) with \(f(x) = y\). Define \(g(y) = x\). If \(y \notin \text{range}(f)\), define \(g(y) = x_0\). The function \(g\) is onto.
Each of the following rules defines a function from \(\R\) into \(\R\).
Find the range of the function and determine if the function is one-to-one in each of the following cases:
Find the following inverse images:
The function \(u\) is one-to-one. Find (that is, give the domain and rule for) the inverse function \(u^{-1}\).
\(u^{-1}(p) = \ln\left(\frac{p}{1-p}\right)\) for \(p \in (0, 1)\)
Give the rule and find the range for each of the following functions:
Note that \( f \circ g \) and \( g \circ f \) are well-defined functions from \( \R \) into \( \R \), but \( f \circ g \ne g \circ f \).
Let \(S = \{1, 2, 3, 4, 5, 6\}^2\). This is the set of possible outcomes when a pair of standard dice are thrown. Let \(f\), \(g\), \( u \), and \( v \) be the functions from \(S\) into \(\Z\) defined by the following rules:
In addition, let \( F \) and \( U \) be the functions defined by \( F = (f, g) \) and \( U = (u, v) \).
Find the range of each of the following functions:
Give each of the following inverse images in list form:
Find each of the following compositions:
Note that while \( f \circ U \) is well-defined, \( U \circ f \) is not. Note also that \( f \circ U = f \) even though \( U \) is not the identity function on \( S \).
Let \( n \in \N_+ \) and let \( S = \{0, 1\}^n \) and \( T = \{0, 1, \ldots, n\} \). Recall that the elements of \( S \) are bit strings of length \( n \), and could represent the possible outcomes of \( n \) tosses of a coin (where 1 means heads and 0 means tails). Let \( f: S \to T \) be the function defined by \( f(x_1, x_2, \ldots, x_n) = \sum_{i=1}^n x_i \). Note that \( f(\bs{x}) \) is just the number of 1s in the the bit string \( \bs{x} \). Let \( g: T \to S \) be the function defined by \( g(k) = \bs{x}_k \) where \( \bs{x}_k \) denotes the bit string with \( k \) 1s followed by \( n - k \) 0s.
Find each of the following
In , note that \( f \circ g \) and \( g \circ f \) are both well-defined, but have different domains, and so of course are not the same. Note also that \( f \circ g \) is the identity function on \( T \), but \( f \) is not the inverse of \( g \). Indeed \( f \) is not one-to-one, and so does not have an inverse. However, \( f \) restricted to \( \left\{\bs{x}_k: k \in T\right\} \) (the range of \( g \)) is one-to-one and is the inverse of \( g \).
Let \( n = 4 \). Give \( f^{-1}(\{k\}) \) in list form for each \( k \in T \).
Again let \( n = 4 \). Let \( A = \{1000, 1010\} \) and \( B = \{1000, 1100\} \). Give each of the following in list form:
In , note that \( f(A \cap B) \subset f(A) \cap f(B) \) and \(A \subset f^{-1}\left(f(A)\right) \).
Suppose that \(A\) and \(B\) are subsets of a universal set \(S\). Express, in terms of \(\bs 1_A\) and \(\bs 1_B\), the indicator function of each of the 14 non-trivial sets that can be constructed from \(A\) and \(B\). Use the Venn diagram app to help.
Suppose that \( A \), \( B \), and \( C \) are subsets of a universal set \( S \). Give the indicator function of each of the following, in terms of \( \bs 1_A \), \(\bs 1_B\), and \( \bs 1_C \) in sum-product form:
Recall the standard arithmetic operators on \( \R \) discussed above.
We all know that sum is commutative and associative, and that product distributes over sum.
Express the multiset \( A \) in list form that has the multiplicity function \( m: \{a, b, c, d, e\} \to \N \) given by \( m(a) = 2 \), \( m(b) = 3 \), \( m(c) = 1 \), \( m(d) = 0 \), \( m(e) = 4 \).
\( A = \{a, a, b, b, b, c, e, e, e, e\} \)
Express the prime factors of 360 as a multiset in list form.
\(\{2, 2, 2, 3, 3, 5\}\)