174 CHAPTER 3 Relations
Definition 6. Let R be a binary relation on a set X. For n E N, the nth power of R,denoted R', is defined as follows:
(a) R^0 ={(x,x):x eX}=Idx.
(b) Rn+^1 = R o Rn.
Let R+ = U?0 i=1 Ri and R* U U=0t^1 R'Example 9. Let A = {a, b, c, d} and let R be the relation on A consisting of the pairs
(a, b), (b, a), (b, c), and (c, d). Find R+ and R*.Solution. R^0 = {(a, a), (b, b), (c, c), (d, d)}
R2 = {(a, a), (a, c), (b, b), (b, d)}
R3 = {(a, b), (b, a), (b, c), (a, d)}
R4 = {(a, a), (a, c), (b, b), (b, d)}
Observe that R^2 = R^4 and, consequently, R^5 = R(^3) .In general, R (^2) n+l = R^3 and R^2 n -
R^2 for n > 1. Therefore,
R + ( (a, b), (b, a), (b, c), (c, d), (a, a), (a, c), (b, b), (b, d), (a, d)}I
R* = {(c, c), (d, d), (a, b), (b, a), (b, c), (c, d), (a, a), (a, c), (b, b), (b, d), (a, d)} I
Example 10. Let R be the relation IsChildOf.
(a) The expression xR^2 y means that x is a child of a child of y, so R^2 is the same as
IsGrandchildOf.
(b) The expression x R3y means that x is a child of a grandchild of y or, said another way,
that x is a great-grandchild of y. Hence, the relation R^3 could just as well be called
IsGreatGrandchildOf.
(c) R^4 could just as well be called IsGreatGreatGrandchildOf.
(d) Relation R+ is the same as IsAncestorOf.
Example 11. Let S be the relation on Z that is defined by aSb if and only if b = a + 1.
(a) It is true that aSob if and only if b = a.
(b) aS^2 b if and only if, for some integer c, it is true that c = a + 1 and b = c + 1--that
is, if and only if b = a + 2.
(c) aS^3 b if and only ifb = a + 3.
(d) aSnb if and only if b = a ± n. (Formally, this is proved by induction on n.)
(e) aS+b if and only if a < b. For if aS+b, then aSnb for some positive integer n.(f) aS*b if and only ifa < b.
Solution. (f) (=) By part (d), b = a + n, so a < b.
(==) Suppose, conversely, that a < b. Since a, b E Z, their difference b - a E Z. Since
a < b, it follows that b - a > 0. Let n = b - a. By part (d), aSnb, so aS+b. U
In Theorem 5 we give a characterization of the smallest reflexive, symmetric, and
transitive relations containing a given relation.