1.

3 THE LANGUAG E OF RELATIONS AND FUNCTIONS 15

12. Let S = I 2, 4, 6I and T = I l , 3, 5I. Use the set- 14. Let R = {al, S = {x, yl, and T = {p, q, r}. Find
roster notation to write each of the following sets, and each of the following sets.
indicate the number of elements that are in each set. a. RX (S X T)
a. S X T b. (RXS)XT
b. TX S c. RX S X T
c. S XS
15. Let S = I 0, I I. List all the strings of length 4 over
d. T X T
S that contain three or more O's.
13. LetA = {l , 2,3} , B= {u} ,andC= {m,n }.Find
16. Let T = {x, y I. List all the strings of length 5 over
each of the following sets.
T that have exactly one y.
a. AX (BX C)
b. (AXB)XC
c.AXBXC

ANSWERS FOR TEST YOURSELF _ _ _ _ _ _ _ _ _ _ _ _ _ _ __

1. does not matter 2. the set of all real numbers 3. the set in B 1. the set of all ordered pairs (a. b) where a is in A and
of all integers 4. the set of all rational numbers 5. the set bis in B 8. the set of ordered triples of the form (a, b, c)
of all x such that P(x) 6. every element in A is an element where a EA. b EB. and c E C 9. parentheses; commas

II) The Language of Relations and Functions

Mathematics is a language. -Josiah Willard Gibbs (1839-1903)

There are many kinds of relationships in the world. For instance, we say that two people
are related by blood if they share a common ancestor and that they are related by marriage
if one shares a common ancestor with the spouse of the other. We also speak of the rela-
tionship between student and teacher, between people who work for the same employer,
and between people who share a common ethnic background.
Similarly, the objects of mathematics may be related in various ways. A set A may
be said to be related to a set B if A is a subset of B, or if A is not a subset of B, or if A
and B have at least one element in common. A number x may be said to be related to a
number y if x < y, or if x is a factor of y, or if x 2 + y' = I. Two identifiers in a computer
program may be said to be related if they have the same first eight characters, or if the
same memory location is used to store their values when the program is executed . And
the list could go on!
Let A = {O, I, 2} and B = { I, 2, 3} and let us say that an element x in A is related to an
element y in B if, and only if, x is less than y. Let us use the notation x Ry as a shorthand
for the sentence "x is related toy." Then
ORI since 0< I,
OR2 since 0<2,
OR3 since 0 < 3,
lR2 since I < 2,
lR3 since I < 3, and
2R3 since 2 < 3.

Copyright 2020 Cengage Learning. All Right s Reserved. May not be copied, scanned. or dupllcated . In whole or In part. WCN 02-200-203
16 CHAPTER! SPEA KI NG MATHEMATICA LLY

On the other hand, if the notation x/ty represents the sentence "xis not related toy," then

I It I since I </:. I,
2 It I since 2 </:. I, and
2 It 2 since 2 </:. 2.
Recall that the Cartesian product of A and B, A X B, consists of all ordered pairs whose
first element is in A and whose second element is in B:
A x B = I(x, y) Ix EA and y EB).
In this case,
A XB = ((0, I), (0, 2), (0, 3), (I , I), (I, 2), (I, 3), (2, I), (2, 2), (2, 3)}.
The elements of some ordered pairs in A X Rare related, whereas the elements of other
ordered pairs are not. Consider the set of all ordered pairs in A X B whose elements are
related
{(0, I), (0, 2), (0, 3), (I , 2), (I, 3), (2, 3)).
Observe that knowing which ordered pairs lie in this set is equivalent to knowing which
elements are related to which. The relation itself can therefore be thought of as the totality of
ordered pairs whose elements are related by the given condition. The formal mathematical
definition of relation, based on this idea, was introduced by the American mathematician
and logician C. S. Peirce in the nineteenth century.

Definition
Let A andB be sets. A relationR from A toB is a subset of A X B. Given an ordered
pair (x, y) in A X B, xis related toy by R, written x Ry, if, and only if, (x, y) is in R.
The set A is called the domain of R and the set B is called its co-domain.
The notation for a relation R may be written symbolically as follows:
x Ry means that (x,y) ER.

The notation x It y means that x is not related toy by R:

x/iy means that (x,y) R.

14£\,,j.jfiiil A Relation as a Subset

Let A = (I , 2} and B = (I, 2, 3} and define a relation R from A to Bas follows: Given any
(x,y) EA X B,
x-y. .
(x, y) ER means that - - ts an mteger.
2

a. State explicitly which ordered pairs are in A X Rand which are in R.

b. Is I R 3? Is 2 R 3? Is 2 R 2?
c. What are the domain and co-domain of R?
Solution
a. AX B = {(I , I), (I , 2), (I, 3), (2, I), (2, 2), (2, 3)). To determine explicitly the compo-
sition of R, examine each ordered pair in A X R to see whether its elements satisfy the
defining condition for R.

Copyright 2020 Cengage Leam ing . All Rights Reserve d. May not be copied, scanned, or duplicated. In whole or In part. WCN D2· 200 -203
 1.3 THE LA NGUAG E OF RE LAT IONS AND FUNC TIONS 17

(I, I) E R because 1i-1 = = 0, which is an integer.

2 = ::,f, which is not an integer.

1 2
(I, 2) rte R because
2 = f = - I, which is an integer.
3 1
(I, 3) E R because
2 1
(2, I) rte R because 2 = ½, which is not an integer.
2 2
(2, 2) E R because 2 = = 0, which is an integer.

(2, 3) rte R because 2 23 = ::,f, which is not an integer.

Thus

R = {(I, I), (I, 3), (2, 2)}

b. Yes, IR 3 because (I, 3) ER.

No, 2R3 because (2, 3) rte R.
Yes, 2 R 2 because (2, 2) E R.
c. The domain of R is {I, 2} and the co-domain is {I, 2, 3 }.

14£1,,j.jij@fj The Circle Relation

Define a relation C from R to R as follows: For any (x, y) E R X R,

(x, y) E C means that x

2
+ y2 = I.

a. Is (1,0) EC? Is (0, 0) E C?Is(-½, ~)EC? Is -2 CO? IsO C(-l)?Is IC I?

b. What are the domain and co-domain of C?
c. Draw a graph for C by plotting the points of C in the Cartesian plane.

Solution
a. Yes, (I , 0) EC because 12 +02 = I.
No, (0, 0) rte C because 02 + 0 2 = 0 * I.
Yes,(-½, 4)EC because(-½)' +(~) 2
= ¼+ ¾= I.
No, -2,e:'Obecause(-2) 2 +0 2 =4* I.
Yes, 0 C (-1) because 0 2 + (-1) 2 = I.
No, I .e:' I because 1 + 1 = 2 I.
2 2
*
b. The domain and co-domain of Care both R, the set of all real numbers.
C.

-I

Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated. In whole or In part. WCN 02-200-203
18 CHAPTERl SPEAKING MATHEMATICALLY

Arrow Diagram of a Relation

Suppose R is a relation from a set A to a set 8. The arrow diagram for R is obtained as
follows:
I. Represent the elements of A as points in one region and the elements of B as points in
another region.
2. For each x in A and yin B, draw an arrow from x toy if, and only if, xis related toy by
R. Symbolically:
Draw an arrow from x toy
if, and only if, x Ry
if, and only if, (x, y) E R.

lifi'IIUJ?lffj Arrow Diagrams of Relations

Let A = {I, 2, 3) and B = {I , 2, 3) and define relations Sand T from A to Bas follows:
For every (x, y) E A X 8 ,

(x, y) E S means that x <y Sis a "less than.. rela1ion .

T = {(2, I), (2, 5)}.

Draw arrow diagrams for S and T.

Solution

These example relations illustrate that it is possible to have several arrows coming out
of the same element of A pointing in different directions. Also, it is quite possible to have
an element of A that does not have an arrow coming out of it.

Functions
In Section 1.2 we showed that ordered pairs can be defined in terms of sets and we defined
Cartesian products in terms of ordered pairs. In this section we introduced relations as subsets
of Cartesian products. Thus we can now define functions in a way that depends only on the
concept of set. Although this definition is not obviously related to the way we usually work
with functions in mathematics, it is satisfying from a theoretical point of view, and computer
scientists like it because it is particularly well suited for operating with functions on a computer.

Definition

A function F from a set A to a set B is a relation with domain A and co-domain B

that satisfies the following two properties:
I. For every element x in A , there is an element y in B such that (x, y) E F.
2. For all elements x in A and y and z in B,
if (x, y) E F and (x, z) E F, then y = z.

Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned. or duplicated, In whol e or In par1. WCN 02-200 -203
 1.3 THE LANG UAGE OF RELATIONS AND FUNCT IONS 19

Properties (I) and (2) can be stated less formally as follows: A relation F from A to Bis
a function if, and only if:
1. Every element of A is the first element of an ordered pair of F.
2. No two distinct ordered pairs in F have the same first element.
In most mathematical situations we think of a function as sending elements from one
set, the domain, to elements of another set, the co-domain. Because of the definition of
function, each element in the domain corresponds to one and only one element of the
co-domain.
More precisely, if Fis a function from a set A to a set B, then given any element x in A,
property (I) from the function definition guarantees that there is at least one element of B
that is related to x by F and property (2) guarantees that there is at most one such element.
This makes it possible to give the element that corresponds to x a special name.

If A and B are sets and Fi s a function from A to B, then given any element x in A, the
unique element in B that is related to x by Fis denoted F(x), which is read "F of x ."

Functions and Relations on Finite Sets

Let A = {2, 4, 6} and B = {l , 3, 5}. Which of the relations R, S, and T defined below are
functions from A to B?
a. R = {(2, 5), (4, I), (4, 3), (6, 5)}
b. For every (x, y) EA x B, (x, y) E S means that y = x + l.
c. Tis defined by the arrow diagram

A B

Solution
a. R is not a function because it does not satisfy property (2). The ordered pairs (4, 1)
and (4, 3) have the same first element but different second elements. You can see this
graphically if you draw the arrow diagram for R. There are two arrows coming out of
4: One points to I and the other points to 3.

b. Sis not a function because it does not satisfy property (I). It is not true that every
element of A is the first element of an ordered pair in S. For example, 6 EA but there
is no yin B such that y = 6 + 1 = 7. You can also see this graphically by drawing the
arrow diagram for S.

Copyright 2020 Cengage Learning. All Rights Re served. May not be copied, scanned, or dupllc11ted, In whole or In part. WCN 02·200-203
20 CHAPTER ! SPEAK ING MATHEMAT ICALLY

Note In par! (c).

=
T(4) 7'(6). This illustrates
the fact that although no
element of the domain of a
func1ion can be related to
more than one element of
c. Tis a function: Each element in {2, 4, 6} is related to some element in {l, 3, 5}, and no
the co-domain. several ele- element in {2, 4, 6} is related to more than one element in {l , 3, 5}. When these proper-
ments in the domain can be ties are stated in terms of the arrow diagram, they become (I) there is an arrow coming
related to the same element out of each element of the domain, and (2) no element of the domain has more than one
in the co-domain. arrow coming out of it. So you can write T(2) = 5, T(4) = 1, and T(6) = 1.

1;;;,,;.;4111, Functions and Relations on Sets of Strings

Let A = {a, h) and let S be the set of all strings over A.
a. Define a relation L from S to Z"""'"' as follows: For every strings in Sand for every
nonnegative integer n,

(s, n) E L means that the length of s is n.

Observe that Lis a function because every string in S has one and only one length.
Find L(ahaaha) and L(hhh).
b. Define a relation C from S to Sas follows: For all strings sand tin S,

(s, t) E C means that r = as,

where as is the string obtained by appending a on the left of the characters ins. (C is
called concatenation by a on the left.) Observe that C is a function because every
string in S consists entirely of a 's and h's and adding an additional a on the left creates
a new strong that also consists of a 's and h's and thus is also in S. Find C(ahaaha) and
C(hbb).

Solution
a. L(abaaba) = 6 and L(hhh) = 3
b. C(ahaaha) = aahaaha and C(bhb) = ahhb

Function Machines
Anotheruseful way to think of a function is as a machine. Supposefis a function from X to
Yand an input x of Xis given. Imaginefto be a machine that processes x in a certain way
to produce the outputf(x). This is illustrated in Figure 1.3.1.

Input

function machine

f(x) Output
FIGURE 1.3.1

Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned. or dupllcated. In whole or In part. WCN 02-200-203
 1.3 THE LANGUAG E OF RELATI ONS AND FUNC TI ONS 21

lifi,,IIJtiiifi Functions Defined by Formulas

The squaring function f from R to R is defined by the formula J(x) = x 2 for every real
number x. This means that no matter what real number input is substituted for x, the output
of/will be the square of that number. This idea can be represented by 0 2.
In other words,Jsends each real number x to x 2, or, symbolically, f: x----+ x2. Note that the
variable x is a dummy variable; any other symbol could replace it, as long as the replace-
ment is made everywhere the x appears.
Thesuccessorfunctiong from ZtoZ is defined by the formulag(n) = n +I.Thus, no mat-
ter what integer is substituted for n, the output of g will be that number plus I: In
other words, g sends each integer 11 ton + I, or, symbolically,//: n ----+ n + I.
An example of a constant function is the function h from Q to Z defined by the for-
mula h(r) = 2 for all rational numbers r. This function sends each rational number r to 2.
In other words, no matter what the input, the output is always 2: h(D) = 2 or h: r----+ 2.
The functions/, g, and hare represented by the function machines in Figure 1.3.2.

squaring successor constant

function fun ction function

\
g(n)=n+I
\
ll(r) =2
(a) (b) (c)
FIGURE 1.3.2

A function is an entity in its own right. It can be thought of as a certain relationship

between sets or as an input/output machine that operates according to a certain rule. This
is the reason why a function is generally denoted by a single symbol or string of symbols,
such as/, G, of log, or sin.
A relation is a subset of a Cartesian product and a function is a special kind of relation.
Specifically, if/and g are functions from a set A to a set B, then
J= {(x, y) EA X Bly =f(x)) and g = {(x, y) EA X Bly= g(x)).

It follows that

/ equals g, written/= g, if, and only if, /(x) = g(x) for all x in A.

14£1,,j.jrj@fj Equality of Functions

Define functions f and g from R to R by the following formulas:
f(x) = lxl for every x ER.
g(x) = y} for every x E R.
Does/= g?
Solution
Yes. Because the absolute value of any real number equals the square root of its square,
lxl =#forallxER.Hence/=g.

Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanne d. or duplicated, in whole or In part. WCN 02-200-203
22 CHAPTER ! SPEAK ING MATHEM ATIC ALLY

TEST YOURSELF _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ __
1. Given sets A and B, a relation from A to B is _ _ _ b. for all elements x in A and y and z in B, if
_ __ then _ _ _ _
2. A function F from A to B is a relation from A to B
that satisfies the following two properties: 3. If Fis a function from A to Band xis an element
a. for every element x of A, there is _ _ _ _ of A, then F(x) i s - - - ·

EXERCISE SETl.3 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ __
1. Let A= {2, 3,4} andB= {6,8, IO} and define c. Write the domain and co-domain of V.
a relation R from A to B as follows: For every d. Draw an arrow diagram for V.
(x,y) EA X B,
5. Define a relation S from R to R as follows:
(x, y) E R means that l is an integer. For every (x, y) E R X R,
X
(x, y) E S means that x ;;,: y .
a. Is 4 R 6? Is 4 R 8? Is (3, 8) E R? Is (2, 10) E R?
b. Write Ras a set of ordered pairs. a. Is (2, I) E S? Is (2, 2) E S? Is 2 S 3?
c. Write the domain and co-domain of R. Is (-1) S (-2)?
d. Draw an arrow diagram for R. b. Draw the graph of Sin the Cartesian plane.
2. Let C = D = {-3, -2, - ! , !, 2, 3) and define 6. Define a relation R from R to R as follows:
a relation S from C to D as follows: For every
For every (x, y) E R X R,
(x,y)E ex D,
(x, y) E R means that y= x2.
(x, y) E S means that }- tis an integer.
a. Is (2, 4) ER? Is (4, 2) ER? Is (-3) R 9?
a. Is 2 S 2? Is - I S - I? Is (3, 3) E S? Is 9 R (-3)?
Is (3, -3) ES? b. Draw the graph of R in the Cartesian plane.
b_ Write Sas a set of ordered pairs. 7. Let A= {4, 5, 6} and B = {5, 6, 7} and define
c. Write the domain and co-domain of S. relations R, S, and T from A to Bas follows:
d. Draw an arrow diagram for S. For every (x, y) EA X B:
3. Let E = I I, 2, 3 I and F = I -2, - I, 0 I and define (x, y) E R means that x;;,: y.
a relation T from E to Fas follows: For every x-y
(x, y) E S means that is an integer.
(x,y) E £ X F,
T = {(4, 7), (6, 5), (6, 7)}.
(x, y) E T means that x; Y is an integer.
a. Draw arrow diagrams for R, S, and T.
a. Is 3 TO? Is I T(-1)? Is (2, -1) ET? b. Indicate whether any of the relations R, S, and
Is (3, -2) E T? Tare functions.
b. Write T as a set of ordered pairs.
8. Let A = {2, 4} and B = I I, 3, 5} and define rela-
c. Write the domain and co-domain of T.
tions U, V. and W from A to B as follows:
d. Draw an arrow diagram for T.
For every (x, y) EA X B:
4. Let G = {-2, 0, 2) and H = {4, 6, 8} and define a
relation V from G to Has follows: For every (x, y) E U means that y- x > 2.
(x,y)E G X H, (x, y) E V means that y- 1= f
(x, y) E V means that x Y is an integer. W = {(2, 5), (4, !), (2, 3)}.
a. Draw arrow diagrams for U, V, and W.
a. Is 2 V 6? Is (-2) V (8)? Is (0, 6) E V?
b. Indicate whether any of the relations U, V, and
Is (2, 4) EV?
W are functions.
b. Write Vas a set of ordered pairs.

Copyright 2020 Cengage Learning. AU Rights Reserved. May not be copied, scanned. or dupllcated. In whole or In part. WCN 02-200-203
 1.3 THE LANGUAGE OF RE LATIONS AND FUNCTIONS 23

9. a. Find all functions from {0, I} to {I}. a. X

b. Find two relations from {0, I} to {I} that are
not functions.
10. Find four relations from {a, b} to {x, y} that are
not functions from {a, b} to {x, y}.
11. Let A= {0, 1,2} andletSbethesetofallstrings b. X
over A. Define a relation L from S to z,wnneg as
follows: For every strings in Sand every nonnega-
tive integer n,
(s, n) EL means that the length of sis n.
Then Lis a function because every string in S has
one and only one length. Find L(0201) and L(l2). c. X

12. Let A= {x, y} and let S be the set of all strings

over A. Define a relation C from S to Sas follows:
For all strings sand I in S,
(s, t) E C means that / = ys.
d. X
Then C is a function because every string in S
consists entirely of x's and y's and adding an ad-
ditional y on the left creates a single new string
that consists of x's and y's and is, therefore, also in
S. Find C(x) and C(yyxyx).
13. Let A = { - I, 0, I} and B = It, u, v, w). Define a e. X
function F: A-+ B by the following arrow diagram:

A B

16. Letfbe the squaring function defined in Example

1.3.6. Findf(-1),f(0), andf(½).
a. Write the domain and co-domain of F. 17. Let g be the successor function defined in
b. Find F(-1), F(0), and F(I). Example 1.3.6. Find g(-1000), g(0), and g(999).
14. Let C = { I, 2, 3, 4} and D = {a, b, c, d}. Define 18. Leth be the constant function defined in
a function G: C-+ D by the following arrow Example 1.3.6. Find h(-f), h(~). and h(t-,).
diagram:
19. Define functionsfand g from R to R by the fol-
lowing formulas: For every x E R,

zxl+2x
J(x) = 2x and g(x) = 7'+"I·
Doesf= g? Explain.
a. Write the domain and co-domain of G.
b. Find G(I), G(2), G(3), and G(4). 20. Define functions Hand K from R to R by the fol-
lowing formulas: For every x E R,
15. Let X = { 2, 4, 5} and Y = { I, 2, 4 , 6}. Which of
H(x) = (x-2) 2 and K(x) = (x- l)(x-3)+ I.
the following arrow diagrams determine functions
from Xto Y? Does H = K? Explain.

Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or dupllcated. In whole or In part. WCN 02-200-203