]> Functions

2. Functions

Functions play a central role in probability and statistics, as they do in every other branch of mathematics.

Definitions and Properties

Suppose that $S$ and $T$ are sets. Technically, a function $f$ from $S$ into $T$ is a subset of the product set $S T$ with the property that for each element $x S$, there exists a unique element $y T$ such that $x y f$. We then 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 S$ a unique element $f x T$. The definition of a function as a set of ordered pairs, is due to Kazamierz Kuratowski. When $f$ is a function from $S$ into $T$, we write $f S T$ The set $S$ is the domain of $f$ and the set $T$ is the range space or co-domain of $f$. The actual range of $f$ is the set of function values:

$range f y T x S y f x$

If the range of $f$ is $T$, then $f$ is said to map $S$ onto $T$ (instead of just into). Thus, if $f$ maps $S$ onto $T$, then for each $y T$ there exists $x S$ such that $f x y$. By definition, any function maps its domain onto its range.

A function $f$ is said to be one-to-one if distinct elements in the domain are mapped to distinct elements in the range.

$f u f v u v , u S , v S$

If $f$ is a one-to-one function from $S$ onto $T$, we can define the inverse of $f$ as the function $f$ from $T$ onto $S$ given by

$f y x if and only if f x y$

If you like to think of a function as a set of ordered pairs, then $f y x x y f$. The fact that $f$ is one-to-one and onto ensures that $f$ 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.

Composition

Suppose that $g R S$ and $f S T$. The composition of $f$ with $g$ is the function $f g R T$ defined by

$f g x f g x , x R$

Show that composition is not commutative:

1. Give an example of functions $f$ and $g$ where $f g$ is defined but $g f$ is not.
2. Give an example of functions $f$ and $g$ where $f g$ and $g f$ are defined, but the compositions have different domains and co-domains.
3. Give an example of functions $f$ and $g$ where $f g$ and $g f$ are defined, have the same domain and co-domain, but are still different.

Suppose that $h R S$, $g S T$, and $f T U$. Show that composition is associative:

$f g h f g h$

Thus we can write $f g h$ without ambiguity.

Suppose that $g R S$ and $f S T$.

1. Show that if $f$ and $g$ are one-to-one then $f g$ is one-to-one.
2. Show that if $f$ and $g$ are onto then $f g$ is onto.

The identity function on a set $S$ is the function $S$ from $S$ onto $S$ defined by $S x x , x S$

Show that the identity function acts like an identity with respect to the operation of composition. If $f S T$ then

1. $f S f$
2. $T f f$

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$. Show that

1. $f f S$.
2. $f f T$

An element $s S n$ can be thought of as a function from $1 2 n$ into $S$. Similarly, an element $s S$ can be thought of as a function from $1 2$ into $S$. For such a sequence $s$, of course, we usually write $s i$ instead of $s i$. More generally, if $S$ and $T$ are sets, then the set of all functions from $S$ into $T$ is denoted by $T S$.

Suppose that $g$ is a one-to-one function from $R$ onto $S$ and that $f$ is a one-to-one function form $S$ onto $T$. Show that $f g g f$.

Inverse Images

Suppose that $f$ is a function from a set $S$ into a set $T$. If $A T$, the inverse image of $A$ under $f$ is the subset of $S$ consisting of those elements that map into $B$:

$f A x S f x A$ Technically, the inverse images define a new function from $T$ into $S$. We use the same notation as for the inverse function, which is defined when $f$ is one-to-one and onto. Usually, no confusion results. The following important exercise shows that inverse images preserve all set operations.

Suppose that $f$ is a function from $S$ into $T$, and $A$ and $B$ are subsets of $T$. Show that

1. $f A B f A f B$
2. $f A B f A f B$
3. $f B A f B f A$
4. $A B f A f B$
5. If $A$ and $B$ are disjoint, so are $f A$ and $f B$

The result in part (a) hold for arbitrary unions, and the results in part (b) hold for arbitrary intersections. No new ideas are involved; only the notation is more complicated.

Forward Images

Suppose again that $f$ is a function from a set $S$ into a set $T$. If $A S$, the forward image of $A$ under $f$ is the subset of $T$ given by

$f A f x x A$ Technically, the forward images define a new function from $S$ into $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. 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 and measure theory). 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$ is a function from $S$ into $T$, and $A$ and $B$ are subsets of $S$. Show that

1. $f A B f A f B$
2. $f A B f A f B$
3. $f B f A f B A$
4. $A B f A f B$
5. Equality holds in parts (b) and (c) if $f$ is one-to-one.

The result in part (a) hold for arbitrary unions, and the results in part (b) hold for arbitrary intersections. No new ideas are involved; only the notation is more complicated.

Suppose again that $f S T$, As noted earlier, the forward images of $f$ define a function from $S$ into $T$ and the inverse images define a function from $T$ into $S$ One might hope that these functions are inverses of one-another, but alas no.

Suppose that $f S T$.

1. Show that $A f f A$ for $A S$
2. Show that equality holds in (a) if $f$ is one-to-one, and give a counterexample to show that equality does not hold generally.
3. Show that $f f A A$ for $A T$
4. Show that equality holds in (c) if $f$ is onto, and give a counterexample to show that equality does not hold generally.

Indicator Functions

Suppose that $A$ is a subset of a universal set $S$. The indicator function of $A$ is the function $A S 0 1$ defined as follows: $A x 1 x A 0 x A$

Conversely, show that any function $f S 0 1$ is the indicator function of the set

$A f 1 x S f x 1$

Thus, there is a one-to-one correspondence between $S$, the power set of $S$, and the collection of indicator functions $0 1 S$. The next exercise shows how the set algebra of subsets corresponds to the arithmetic algebra of the indicator functions.

Suppose that $A$ and $B$ are subsets of $S$. Show that

1. $A B A B A B$
2. $A B 1 1 A 1 B A B$
3. $B A B 1 A$
4. $A 1 A$
5. $A B$ if and only if $A B$

The results in part (a) extends to arbitrary intersections and the results in part (b) extends to arbitrary unions.

Suppose that $A$ and $B$ are subsets of $S$. Express, in terms of $A$ and $B$, the indicator function of each of the 16 sets that can be constructed from $A$ and $B$. Use the Venn diagram applet to help.

Functions into Product Spaces

Suppose that $S$ and $T$ are sets and that $f S T n$ where $n 2 3$. For $i 1 2 n$, we define the $i$ coordinate function $f i S T$ by the rule that $f i x$ is the $i$ coordinate of $f x$ for each $x S$. Conversely, a sequence of functions $f 1 f 2 f n$, each mapping $S$ into $T$, defines a function $f S T n$ by the rule $f x f 1 x f 2 x f n x$ for $x S$.

Operations

Suppose that $S$ is a set. A function $f S S$ is sometimes called an unary operation on $S$. As the name suggests, $f$ operates on an element $x S$ to produce a new element $f x S$. Similarly, a function $g S S S$ is sometimes called an binary operation on $S$. As the name suggests, $g$ operates on a pair of elements $x y S S$ to produce a new element $g x y S$.

The arithmetic operations are quintessential examples:

• $minus x x$ is a unary operation on 
• $plus x y x y$ is a binary operation on 
• $times x y x y$ is a binary operation on 
• $difference x y x y$ is a binary operation on 
• $reciprocal x 1 x$ is a unary operation on $0$

The set operations on $S$ were studied in the section on Sets:

• $complement A A$ is a unary operation.
• $union A B A B$ is a binary operation.
• $intersect A B A B$ is a binary operation.
• $difference A B A B$ is a binary operation.

Suppose now that $f$ is a unary operation on $S$, $g$ is a binary operation on $S$, and that $A S$. Then $A$ is said to be closed under $f$ if $x A f x A$. Thus, $f$ restricted to $A$ is a unary operation on $A$. Similarly, $A$ is said to be closed under $g$ if $x y A A g x y A$. Thus, $g$ restricted to $A A$ is a binary operation on $A$. Returning to our basic examples, note that

•  is closed under plus and times, but not under minus and difference.
•  is closed under plus, times, minus, and difference.

Many properties that you are familiar with for special operations (such as the arithmetic and set operations) can now be formulated generally. Suppose that $f$ and $g$ are binary operations on $S$. In the following definitions, $x$, $y$, and $z$ are arbitrary elements of $S$.

• $f$ is commutative if $f x y f y x$
• $f$ is associative if $f x f y z f f x y z$
• $g$ distributes over $f$ (on the left) if $g x f y z f g x y g x z$

The Axiom of Choice

Suppose that $S$ is a collection of nonempty subsets of a set $S$. The axiom of choice states that there exists a function $f S S$ with the property that $f A A$ for each $A 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 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$. Show that there exists a one-to-one function $g$ from $T$ into $S$.

1. For each $y T$, the set $f y$ is non-empty, since $f$ is onto.
2. Use the axiom of choice to select an element $g y$ from $f y$ for each $y T$.
3. Show that 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$. Show that there exists a function $g$ from $T$ onto $S$.

1. Fix a special element $s S$.
2. If $y range f$, there exists a unique $x S$ with $f x y$. Define $g y x$.
3. If $y range f$, define $g y s$.
4. Show that the function $g$ is onto.

Computational Exercises

Some Elementary Functions

Each of the following rules defines a function from  into .

• $f x x 2$
• $g x x$
• $h x x$
• $F x x 1 x$

Find the range of the function and determine if the function is one-to-one in each of the following cases:

1. $f$
2. $g$
3. $h$
4. $F$

Find the following inverse images:

1. $f 4 9$
2. $g 0$
3. $h 2 3 4$

You showed that the function $F$ is one-to-one. Find (that is, give the domain and rule for) the inverse function $F$.

Give the rule and find the range for each of the following functions:

1. $f g$
2. $g f$
3. $h g f$

Dice

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$, and $h$ be the functions from $S$ into  defined by the following rules:

• $f x y x y$
• $u x y x y$
• $v x y x y$

Find the range of each of the following functions:

1. $f$
2. $u$
3. $v$
4. $g u v$

Give each of the following in list form:

1. $f 6$
2. $u 3$
3. $v 4$
4. $g 3 4$