Having read Chapter 11, you may see f in a new light. Its graph
R ⊆ R × R is a relation on the set R. In fact, as we shall see, functions
are just special kinds of relations. Before stating the exact definition, we
Functions
197
look at another example. Consider the function f (n) = |n| + 2 that converts
integers n into natural numbers |n| + 2. Its graph is R = ©(n, |n| + 2) : n ∈ Zª
⊆ Z × N.
N
6
5
4
3
2
1
Z
−4 −3 −2 −1 0
1
2
3
4
Figure 12.2. The function f : Z → N, where f (n) = |n| + 2
Figure 12.2 shows the graph R as darkened dots in the grid of points Z × N.
Notice that in this example R is not a relation on a single set. The set of
input values Z is different from the set N of output values, so the graph
R ⊆ Z × N is a relation from Z to N .
This example illustrates three things. First, a function can be viewed
as sending elements from one set A to another set B. (In the case of f ,
A = Z and B = N.) Second, such a function can be regarded as a relation
from A to B. Third, for every input value n, there is exactly one output
value f (n). In your high school algebra course, this was expressed by the
vertical line test: Any vertical line intersects a function’s graph at most
once. It means that for any input value x, the graph contains exactly one
point of form (x, f (x)). Our main definition, given below, incorporates all of
these ideas.
Definition 12.1
Suppose A and B are sets. A function f from A to B
(denoted as f : A → B) is a relation f ⊆ A × B from A to B, satisfying the
property that for each a ∈ A the relation f contains exactly one ordered
pair of form (a, b). The statement (a, b) ∈ f is abbreviated f (a) = b.
Example 12.1
Consider the function f graphed in Figure 12.2. According
to Definition 12.1, we regard f as the set of points in its graph, that is,
f = ©(n,|n| + 2) : n ∈ Zª ⊆ Z × N. This is a relation from Z to N, and indeed
given any a ∈ Z the set f contains exactly one ordered pair (a, |a| + 2) whose
first coordinate is a. Since (1, 3) ∈ f , we write f (1) = 3; and since (−3, 5) ∈ f
we write f (−3) = 5, etc. In general, (a, b) ∈ f means that f sends the input
198
Functions
value a to the output value b, and we express this as f (a) = b. This function
can be expressed by a formula: For each input value n, the output value
is |n| + 2, so we may write f (n) = |n| + 2. All this agrees with the way we
thought of functions in algebra and calculus; the only difference is that
now we also think of a function as a relation.
Definition 12.2
For a function f : A → B, the set A is called the domain
of f . (Think of the domain as the set of possible “input values” for f .) The
©
set B is called the codomain of f . The range of f is the set f (a) : a ∈ Aª =
©b : (a, b) ∈ f ª. (Think of the range as the set of all possible “output values”
for f . Think of the codomain as a sort of “target” for the outputs.)
Continuing Example 12.1, the domain of f is Z and its codomain is
N
©
. Its range is
f (a) : a ∈ Zª = ©|a| + 2 : a ∈ Zª = ©2,3,4,5,...ª. Notice that the
range is a subset of the codomain, but it does not (in this case) equal the
codomain.
In our examples so far, the domains and codomains are sets of numbers,
but this needn’t be the case in general, as the next example indicates.
Example 12.2
Let A = ©p, q, r, sª and B = ©0, 1, 2ª, and
f = ©(p,0),(q,1),(r,2),(s,2)ª ⊆ A × B.
This is a function f : A → B because each element of A occurs exactly once
as a first coordinate of an ordered pair in f . We have f (p) = 0, f (q) = 1,
f (r) = 2
©
and f (s) = 2. The domain of f is p, q, r, sª, and the codomain and
©
range are both 0, 1, 2ª.
B
A
B
0
(p, 0) (q, 0) (r, 0) (s, 0)
s
0
1
(p, 1) (q, 1) (r, 1) (s, 1)
r
1
q
2
(p, 2) (q, 2) (r, 2) (s, 2)
p
2
p
q
r
s
A
(a)
(b)
Figure 12.3. Two ways of drawing the function f = ©(p,0),(q,1),(r,2),(s,2)ª
Functions
199
If A and B are not both sets of numbers it can be difficult to draw
a graph of f : A → B in the traditional sense. Figure 12.3(a) shows an
attempt at a graph of f from Example 12.2. The sets A and B are aligned
roughly as x- and y-axes, and the Cartesian product A × B is filled in
accordingly. The subset f ⊆ A × B is indicated with dashed lines, and this
can be regarded as a “graph” of f . A more natural visual description of f
is shown in 12.3(b). The sets A and B are drawn side-by-side, and arrows
point from a to b whenever f (a) = b.
In general, if f : A → B is the kind of function you may have encountered
in algebra or calculus, then conventional graphing techniques offer the
best visual description of it. On the other hand, if A and B are finite or if
we are thinking of them as generic sets, then describing f with arrows is
often a more appropriate way of visualizing it.
We emphasize that, according to Definition 12.1, a function is really
just a special kind of set. Any function f : A → B is a subset of A × B. By
contrast, your calculus text probably defined a function as a certain kind of
“rule.” While that intuitive outlook is adequate for the first few semesters
of calculus, it does not hold up well to the rigorous mathematical standards
necessary for further progress. The problem is that words like “rule” are
too vague. Defining a function as a set removes the ambiguity. It makes a
function into a concrete mathematical object.
Still, in practice we tend to think of functions as rules. Given f : Z → N
where f (x) = |x| + 2, we think of this as a rule that associates any number
n ∈ Z to the number |n| + 2 in N, rather than a set containing ordered
pairs (n, |n| + 2). It is only when we have to understand or interpret the
theoretical nature of functions (as we do in this text) that Definition 12.1
comes to bear. The definition is a foundation that gives us license to think
about functions in a more informal way.
The next example brings up a point about notation. Consider a function
such as f : Z2 → Z, whose domain is a Cartesian product. This function
takes as input an ordered pair (m, n) ∈ Z2 and sends it to a number f ((m, n)) ∈
Z. To simplify the notation, it is common to write f (m, n) instead of f ((m, n)),
even though this is like writing f x instead of f (x). We also remark that
although we’ve been using the letters f , g
and h to denote functions, any
other reasonable symbol could be used. Greek letters such as ϕ and θ are
common.
Example 12.3
Say a function ϕ : Z2 → Z is defined as ϕ(m, n) = 6m − 9n.
Note that as a set, this function is ϕ = © ¡(m, n), 6m−9n¢ : (m, n) ∈ Z2ª ⊆ Z2 ×Z.
What is the range of ϕ?
200
Functions
To answer this, first observe that for any (m, n) ∈ Z2, the value f (m, n) =
6m − 9n = 3(2m − 3n) is a multiple of 3. Thus every number in the range is
a multiple of 3, so the range is a subset of the set of all multiples of 3. On
the other hand if b = 3k is a multiple of 3 we have ϕ(−k, −k) = 6(−k)−9(−k) =
3k = b, which means any multiple of 3 is in the range of ϕ. Therefore the
©
range of ϕ is the set 3k : k ∈ Zª of all multiples of 3.
To conclude this section, let’s use Definition 12.1 to help us understand
what it means for two functions f : A → B and g : C → D to be equal.
According to our definition, functions f and g are subsets f ⊆ A × B and
g ⊆ C × D. It makes sense to say that f and g are equal if f = g, that is, if
they are equal as sets.
Thus the two functions f = ©(1, a), (2, a), (3, b)ª and g = ©(3, b), (2, a), (1, a)ª
are equal because the sets f and g are equal. Notice that the domain of
both functions is A = ©1, 2, 3ª, the set of first elements x in the ordered pairs
(x, y) ∈ f = g. In general, equal functions must have equal domains.
Observe also that the equality f = g means f (x) = g(x) for every x ∈ A.
We repackage these ideas in the following definition.
Definition 12.3
Two functions f : A → B and g : A → D are equal if
f (x) = g(x) for every x ∈ A.
Observe that f and g can have different codomains and still be equal.
Consider the functions f : Z → N and g : Z → Z defined as f (x) = |x| + 2 and
g(x) = |x| + 2. Even though their codomains are different, the functions are
equal because f (x) = g(x) for every x in the domain.
Exercises for Section 12.1
1. Suppose A = ©0,1,2,3,4ª, B = ©2,3,4,5ª and f = ©(0,3),(1,3),(2,4),(3,2),(4,2)ª. State
the domain and range of f . Find f (2) and f (1).
2. Suppose A = ©a, b, c, dª, B = ©2,3,4,5,6ª and f = ©(a,2),(b,3),(c,4),(d,5)ª. State the
domain and range of f . Find f (b) and f (d).
3. There are four different functions f : ©a, bª → ©0,1ª. List them all. Diagrams
will suffice.
4. There are eight different functions f : ©a, b, cª → ©0,1ª. List them all. Diagrams
will suffice.
5.
©
©
Give an example of a relation from a, b, c, dª to d, eª that is not a function.
6. Suppose f : Z → Z is defined as f = ©(x,4x+5) : x ∈ Zª. State the domain, codomain
and range of f . Find f (10).
Injective and Surjective Functions
201
7. Consider the set f = ©(x, y) ∈ Z × Z : 3x + y = 4ª. Is this a function from Z to Z?
Explain.
8. Consider the set f = ©(x, y) ∈ Z × Z : x + 3y = 4ª. Is this a function from Z to Z?
Explain.
9. Consider the set f = ©(x2, x) : x ∈ Rª. Is this a function from R to R? Explain.
10. Consider the set f = ©(x3, x) : x ∈ Rª. Is this a function from R to R? Explain.
11.
ª
Is the set θ = ©(X , |X |) : X ⊆ Z5 a function? If so, what is its domain and range?
12. Is the set θ = ©¡(x, y),(3y,2x, x + y)¢ : x, y ∈ Rª a function? If so, what is its domain,
codomain and range?
12.2 Injective and Surjective Functions
You may recall from algebra and calculus that a function may be one-
to-one and onto, and these properties are related to whether or not the
function is invertible. We now review these important ideas. In advanced
mathematics, the word injective is often used instead of one-to-one, and
surjective is used instead of onto. Here are the exact definitions:
Definition 12.4
A function f : A → B is:
1. injective (or one-to-one) if for every x, y ∈ A, x 6= y implies f (x) 6= f ( y);
2. surjective (or onto) if for every b ∈ B there is an a ∈ A with f (a) = b;
3. bijective if f is both injective and surjective.
Below is a visual description of Definition 12.4. In essence, injective
means that unequal elements in A always get sent to unequal elements in
B. Surjective means that every element of B has an arrow pointing to it,
that is, it equals f (a) for some a in the domain of f .
A
B
A
B
x
x
Injective means that for any
...and not this:
two x, y ∈ A, this happens...
y
y
A
B
A
B
Surjective means that for
b
a
...this happens:
b
any b ∈ B...
202
Functions
For more concrete examples, consider the following functions from R
to R. The function f (x) = x2 is not injective because −2 6= 2, but f (−2) = f (2).
Nor is it surjective, for if b = −1 (or if b is any negative number), then
there is no a ∈ R with f (a) = b. On the other hand, g(x) = x3 is both injective
and surjective, so it is also bijective.
There are four possible injective/surjective combinations that a function
may possess.
This is illustrated in the following figure showing four
functions from A to B. Functions in the first column are injective, those
in the second column are not injective. Functions in the first row are
surjective, those in the second row are not.
Injective
Not injective
A
B
A
B
a
1
a
1
Surjective
b
2
b
2
c
3
c
(bijective)
A
B
A
B
a
1
a
1
Not surjective
b
2
b
2
3
c
3
We note in passing that, according to the definitions, a function is
surjective if and only if its codomain equals its range.
Often it is necessary to prove that a particular function f : A → B
is injective. For this we must prove that for any two elements x, y ∈ A,
the conditional statement (x 6= y) ⇒ ¡ f (x) 6= f ( y)¢ is true. The two main
approaches for this are summarized below.
How to show a function f : A → B is injective:
Direct approach:
Contrapositive approach:
Suppose x, y ∈ A and x 6= y.
Suppose x, y ∈ A and f (x) = f ( y).
..
.
.
..
Therefore f (x) 6= f ( y).
Therefore x = y.
Of these two approaches, the contrapositive is
often the easiest to use,
especially if f is defined by an algebraic formula. This is because the
contrapositive approach starts with the equation f (x) = f ( y) and proceeds
Injective and Surjective Functions
203
to the equation x = y. In algebra, as you know, it is usually easier to work
with equations than inequalities.
To prove that a function is not injective, you must disprove the statement
(x 6= y) ⇒ ¡f (x) 6= f (y)¢. For this it suffices to find example of two elements
x, y ∈ A for which x 6= y and f (x) = f (y).
Next we examine how to prove that f : A → B is surjective. According
to Definition 12.4, we must prove the statement ∀ b ∈ B, ∃ a ∈ A, f (a) = b. In
words, we must show that for any b ∈ B, there is at least one a ∈ A (which
may depend on b) having the property that f (a) = b. Here is an outline.
How to show a function f : A → B is surjective:
Suppose b ∈ B.
[Prove there exists a ∈ A for which f (a) = b.]
In the second step, we have to prove the existence of an a for which
f (a) = b. For this, just finding an example of such an a would suffice. (How
to find such an example depends on how f is defined. If f is given as a
formula, we may be able to find a by solving the equation f (a) = b for a.
Sometimes you can find a by just plain common sense.) To show f is not
surjective, we must prove the negation of ∀ b ∈ B, ∃ a ∈ A, f (a) = b, that is,
we must prove ∃ b ∈ B, ∀ a ∈ A, f (a) 6= b.
The following examples illustrate these ideas. (For the first example,
note that the set R − ©0ª is R with the number 0 removed.)
Example 12.4
Show that the function f : R−©0ª → R defined as f (x) = 1x +1
is injective but not surjective.
We will use the contrapositive approach to show that f is injective.
1
Suppose x, y ∈ R − ©0ª and f (x) = f ( y). This means x + 1 = 1y + 1. Subtracting
1 from both sides and inverting produces x = y. Therefore f is injective.
Function f is not surjective because there exists an element b = 1 ∈ R
for which f (x) = 1x + 1 6= 1 for every x ∈ R − ©0ª.
Example 12.5
Show that the function g : Z × Z → Z × Z defined by the
formula g(m, n) = (m + n, m + 2n), is both injective and surjective.
We will use the contrapositive approach to show that g is injective.
Thus we need to show that g(m, n) = g(k, `) implies (m, n) = (k, `). Suppose
(m, n), (k, `) ∈ Z×Z and g(m, n) = g(k, `). Then (m+n, m+2n) = (k+ `, k+2 `). It
follows that m + n = k + ` and m + 2n = k + 2 `. Subtracting the first equation
from the second gives n = `. Next, subtract n = ` from m + n = k + ` to get
Book of Proof Page 28
