Page 602 - Discrete Mathematics and Its Applications

9.1 Relations and Their Properties 581

n
Proof: We first prove the “if” part of the theorem. We suppose that R ⊆ R for n = 1,
2
2, 3,.... In particular, R ⊆ R. To see that this implies R is transitive, note that if (a, b) ∈ R
2
2
and (b, c) ∈ R, then by the definition of composition, (a, c) ∈ R . Because R ⊆ R, this means
that (a, c) ∈ R. Hence, R is transitive.
We will use mathematical induction to prove the only if part of the theorem. Note that this
part of the theorem is trivially true for n = 1.
n
Assume that R ⊆ R, where n is a positive integer. This is the inductive hypothesis. To
complete the inductive step we must show that this implies that R n+1 is also a subset of R.
n
To show this, assume that (a, b) ∈ R n+1 . Then, because R n+1 = R ◦ R, there is an
n
element x with x ∈ A such that (a, x) ∈ R and (x, b) ∈ R . The inductive hypothesis, namely,
n
that R ⊆ R, implies that (x, b) ∈ R. Furthermore, because R is transitive, and (a, x) ∈ R
and (x, b) ∈ R, it follows that (a, b) ∈ R. This shows that R n+1 ⊆ R, completing the proof.

Exercises

1. List the ordered pairs in the relation R from d) there is a Web page that includes links to both Web
A ={0, 1, 2, 3, 4} to B ={0, 1, 2, 3}, where (a, b) ∈ R page a and Web page b.
if and only if 6. Determine whether the relation R on the set of all real
a) a = b. b) a + b = 4. numbers is reflexive, symmetric, antisymmetric, and/or
c) a> b. d) a | b. transitive, where (x, y) ∈ R if and only if
e) gcd(a, b) = 1. f) lcm(a, b) = 2. a) x + y = 0. b) x =±y.
2. a) List all the ordered pairs in the relation c) x − y is a rational number.
R ={(a, b) | a divides b} on the set {1, 2, 3, 4, 5, 6}. d) x = 2y. e) xy ≥ 0.
b) Display this relation graphically, as was done in f) xy = 0. g) x = 1.
Example 4. h) x = 1or y = 1.
c) Display this relation in tabular form, as was done in 7. Determine whether the relation R on the set of all integers
Example 4. is reflexive, symmetric, antisymmetric, and/or transitive,
where (x, y) ∈ R if and only if
3. For each of these relations on the set {1, 2, 3, 4}, decide
whether it is reflexive, whether it is symmetric, whether a) x = y. b) xy ≥ 1.
c) x = y + 1or x = y − 1.
it is antisymmetric, and whether it is transitive.
d) x ≡ y(mod 7). e) x is a multiple of y.
a) {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}
f) x and y are both negative or both nonnegative.
b) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)} 2 2
g) x = y . h) x ≥ y .
c) {(2, 4), (4, 2)}
8. Show that the relation R =∅ on a nonempty set S is sym-
d) {(1, 2), (2, 3), (3, 4)}
metric and transitive, but not reflexive.
e) {(1, 1), (2, 2), (3, 3), (4, 4)}
9. Show that the relation R =∅ on the empty set S =∅ is
f) {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)}
reflexive, symmetric, and transitive.
4. Determine whether the relation R on the set of all people 10. Give an example of a relation on a set that is
is reflexive, symmetric, antisymmetric, and/or transitive,
where (a, b) ∈ R if and only if a) both symmetric and antisymmetric.
b) neither symmetric nor antisymmetric.
a) a is taller than b.
A relation R on the set A is irreflexive if for every
b) a and b were born on the same day.
a ∈ A, (a, a) /∈ R. That is, R is irreflexive if no element
c) a has the same first name as b.
in A is related to itself.
d) a and b have a common grandparent.
11. Which relations in Exercise 3 are irreflexive?
5. Determine whether the relation R on the set of all Web
12. Which relations in Exercise 4 are irreflexive?
pages is reflexive, symmetric, antisymmetric, and/or tran-
sitive, where (a, b) ∈ R if and only if 13. Which relations in Exercise 5 are irreflexive?
a) everyone who has visited Web page a has also visited 14. Which relations in Exercise 6 are irreflexive?
Web page b. 15. Can a relation on a set be neither reflexive nor irreflexive?
b) there are no common links found on both Web 16. Use quantifiers to express what it means for a relation to
page a and Web page b. be irreflexive.
c) there is at least one common link on Web page a and 17. Give an example of an irreflexive relation on the set of all
Web page b. people.