330
Relations, Functions, and Matrices
example 3
Let S = 51, 26. Then S × S = 5(1, 1), (1, 2), (2, 1), (2, 2)6. Let r on S be given
by the description x r y 4 x + y is odd. Then (1, 2) [ r and (2, 1) [ r. The
ordered pair (1, 1) o r because 1 + 1 is not odd. Similarly (2, 2) o r.
example 4
Let S = 51, 26. Then S × S = 5(1, 1), (1, 2), (2, 1), (2, 2)6. If r is defined on S by
r = 5(1, 1), (2, 1)6, then 1 r 1 and 2 r 1 hold, but not, for instance, 1 r 2. Here r
seems to have no obvious verbal description.
In this section we will be concerned almost exclusively with binary relations
on a single set, but more generally, relations can be defined on multiple sets.
DefInItIon RelationS on Multiple SetS
Given two sets S and T, a binary relation from S to T (also called a binary
relation on S × T ) is a subset of S × T . Given n sets S 1 , S 2 , … , S n , n > 2, an
n-ary relation on S 1 × S 2 × c × S n is a subset of S 1 × S 2 × c × S n .
example 5
Let S = 51, 2, 36 and T = 52, 4, 76. Then the set
5(1, 2), (2, 4), (2, 7)6
consists of elements from S × T . It is a binary relation from S to T.
■
PRaCtiCe 1 For each of the following binary relations r on N, decide which of the given ordered
pairs belong to r.
a. x r y 4 x = y + 1; (2, 2), (2, 3), (3, 3), (3, 2)
b. x r y 4 x divides y; (2, 4), (2, 5), (2, 6)
c. x r y 4 x is odd; (2, 3), (3, 4), (4, 5), (5, 6)
d. x r y 4 x > y
2
; (1, 2), (2, 1), (5, 2), (6, 4), (4, 3)
If r is a binary relation on S, then r will consist of a set of ordered pairs of the
form (s 1 , s 2 ). A given first component s 1 or second component s 2 can be paired in
various ways in the relation. The relation is one-to-one if each first component and
each second component appears only once in the relation. The relation is one-tomany if some first component s 1 appears more than once; that is, one s 1 is paired
with more than one second component. It is many-to-one if some second component s 2 is paired with more than one first component. Finally, it is many-to-many
if at least one s 1 is paired with more than one second component and at least one
s 2 is paired with more than one first component. Figure 5.1 illustrates these four
possibilities. Note that not all values in S need be components in ordered pairs of r.
Relations, Functions, and Matrices
example 3
Let S = 51, 26. Then S × S = 5(1, 1), (1, 2), (2, 1), (2, 2)6. Let r on S be given
by the description x r y 4 x + y is odd. Then (1, 2) [ r and (2, 1) [ r. The
ordered pair (1, 1) o r because 1 + 1 is not odd. Similarly (2, 2) o r.
example 4
Let S = 51, 26. Then S × S = 5(1, 1), (1, 2), (2, 1), (2, 2)6. If r is defined on S by
r = 5(1, 1), (2, 1)6, then 1 r 1 and 2 r 1 hold, but not, for instance, 1 r 2. Here r
seems to have no obvious verbal description.
In this section we will be concerned almost exclusively with binary relations
on a single set, but more generally, relations can be defined on multiple sets.
DefInItIon RelationS on Multiple SetS
Given two sets S and T, a binary relation from S to T (also called a binary
relation on S × T ) is a subset of S × T . Given n sets S 1 , S 2 , … , S n , n > 2, an
n-ary relation on S 1 × S 2 × c × S n is a subset of S 1 × S 2 × c × S n .
example 5
Let S = 51, 2, 36 and T = 52, 4, 76. Then the set
5(1, 2), (2, 4), (2, 7)6
consists of elements from S × T . It is a binary relation from S to T.
■
PRaCtiCe 1 For each of the following binary relations r on N, decide which of the given ordered
pairs belong to r.
a. x r y 4 x = y + 1; (2, 2), (2, 3), (3, 3), (3, 2)
b. x r y 4 x divides y; (2, 4), (2, 5), (2, 6)
c. x r y 4 x is odd; (2, 3), (3, 4), (4, 5), (5, 6)
d. x r y 4 x > y
2
; (1, 2), (2, 1), (5, 2), (6, 4), (4, 3)
If r is a binary relation on S, then r will consist of a set of ordered pairs of the
form (s 1 , s 2 ). A given first component s 1 or second component s 2 can be paired in
various ways in the relation. The relation is one-to-one if each first component and
each second component appears only once in the relation. The relation is one-tomany if some first component s 1 appears more than once; that is, one s 1 is paired
with more than one second component. It is many-to-one if some second component s 2 is paired with more than one first component. Finally, it is many-to-many
if at least one s 1 is paired with more than one second component and at least one
s 2 is paired with more than one first component. Figure 5.1 illustrates these four
possibilities. Note that not all values in S need be components in ordered pairs of r.