128 Chapter 11
One way to think about the reflexive-transitive closure of a relation R on a given domain
is that it is the “reachability” relation: a
¯
Rbjust in case there is a path from a to b through
R, a sequence a
0
,...,a
n
, starting with a
0
= a and ending with a
n
= b, such that at each
step we follow the relation R, so that a
i
Ra
i+1
. This is both reflexive and transitive.
Is it possible that different relations on a set have the same reflexive-transitive closure?
Yes, of course. If a relation R is not reflexive and transitive, then R is not equal to its
reflexive-transitive closure, but closing twice does not add anything more, and so there are
two different relations with the same reflexive transitive closure.
11.5 Functions
Let us conclude this chapter with a discussion of functions. What does it mean to have
a function f from A to B? Perhaps one is used to considering the graph of a function,
which in this case would be a certain subset of A × B, the set of pairs (a, b) for which
b = f (a). Indeed, all the essential information about the function f is contained in this
graph. Because of this, a function can be seen as a special type of binary relation. So let us
define that f is a function from A to B, written f : A → B,if f is a set of pairs f ⊆ A × B
exhibiting the function property: for every a ∈ A, there is a unique b ∈ B with (a, b) ∈ f .
This object b is denoted by f (a) and is called the value of the function at a. If you think
about it, the function property corresponds exactly to what is sometimes called the vertical
line test in precalculus, where every vertical line intersects the graph of the function in at
most one point; the vertical line test is exactly testing for the uniqueness of the object b.
We refer to A as the domain of the function, and some mathematicians like to count the
set B as an essential part of the function, called the target or the codomain. The range of
the function, in contrast, is the set of all b that arise as f (
a) for some a in the domain. This
may or may not be all of the target set B. For example, a constant function f : R → R has
a range with only one element in it.
not injective
not surjective
injective
not surjective
surjective
not injective
bijective
injective +
surjective
not a function
A function f : A → B is said to be onto or surjective if the range of f is all of B. The
function f : A → B is one-to-one or injective if, whenever a a
, then f (a) f (a
). In
other words, a function is injective when distinct inputs always lead to distinct outputs.