Page 600 - Discrete Mathematics and Its Applications

9.1 Relations and Their Properties 579

pairs of the form (a, b), where a = b, may or may not be in R. Hence, by the product rule for
counting, there are 2 n(n−1) reflexive relations [this is the number of ways to choose whether
each element (a, b), with a = b, belongs to R]. ▲
Formulas for the number of symmetric relations and the number of antisymmetric re-
lations on a set with n elements can be found using reasoning similar to that in Example 16
(see Exercise 47). However, no general formula is known that counts the transitive relations on a
set with n elements. Currently, T (n), the number of transitive relations on a set with n elements, is
known only for n ≤ 17. For example, T(4) = 3,994, T(5) = 154,303, and T(6) = 9,415,189.

Combining Relations

Because relations from A to B are subsets of A × B, two relations from A to B can be combined
in any way two sets can be combined. Consider Examples 17–19.

EXAMPLE 17 Let A ={1, 2, 3} and B ={1, 2, 3, 4}. The relations R 1 ={(1, 1), (2, 2), (3, 3)} and
R 2 ={(1, 1), (1, 2), (1, 3), (1, 4)} can be combined to obtain

R 1 ∪ R 2 ={(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3)},
R 1 ∩ R 2 ={(1, 1)},
R 1 − R 2 ={(2, 2), (3, 3)},
▲
R 2 − R 1 ={(1, 2), (1, 3), (1, 4)}.
EXAMPLE 18 Let A and B be the set of all students and the set of all courses at a school, respectively.
Suppose that R 1 consists of all ordered pairs (a, b), where a is a student who has taken course b,
and R 2 consists of all ordered pairs (a, b), where a is a student who requires course b to graduate.
What are the relations R 1 ∪ R 2 , R 1 ∩ R 2 , R 1 ⊕ R 2 , R 1 − R 2 , and R 2 − R 1 ?

Solution: The relation R 1 ∪ R 2 consists of all ordered pairs (a, b), where a is a student who
either has taken course b or needs course b to graduate, and R 1 ∩ R 2 is the set of all ordered
pairs (a, b), where a is a student who has taken course b and needs this course to graduate.
Also, R 1 ⊕ R 2 consists of all ordered pairs (a, b), where student a has taken course b but does
not need it to graduate or needs course b to graduate but has not taken it. R 1 − R 2 is the set of
ordered pairs (a, b), where a has taken course b but does not need it to graduate; that is, b is
an elective course that a has taken. R 2 − R 1 is the set of all ordered pairs (a, b), where b is a
course that a needs to graduate but has not taken. ▲

EXAMPLE 19 Let R 1 be the “less than” relation on the set of real numbers and let R 2 be the “greater than”
relation on the set of real numbers, that is, R 1 ={(x, y) | x< y} and R 2 ={(x, y) | x> y}.
What are R 1 ∪ R 2 , R 1 ∩ R 2 , R 1 − R 2 , R 2 − R 1 , and R 1 ⊕ R 2 ?

Solution: We note that (x, y) ∈ R 1 ∪ R 2 if and only if (x, y) ∈ R 1 or (x, y) ∈ R 2 . Hence,
(x, y) ∈ R 1 ∪ R 2 if and only if x< y or x> y. Because the condition x< y or x> y is
the same as the condition x = y, it follows that R 1 ∪ R 2 ={(x, y) | x = y}. In other words, the
union of the “less than” relation and the “greater than” relation is the “not equals” relation.
Next, note that it is impossible for a pair (x, y) to belong to both R 1 and R 2 because it is
impossible that x< y and x> y. It follows that R 1 ∩ R 2 =∅. We also see that R 1 − R 2 = R 1 ,
R 2 − R 1 = R 2 , and R 1 ⊕ R 2 = R 1 ∪ R 2 − R 1 ∩ R 2 ={(x, y) | x = y}. ▲

There is another way that relations are combined that is analogous to the composition of
functions.