24 RELATIONS [CHAP.2 3-2-10 Fig.2-1 There are two things worth noting in the above examples.First of all A x BB x A.The Cartesian product deals with ordered pairs,so naturally the order in which the sets are considered is important.Secondly,using n(S)for the number of elements in a set S,we have: n(A×B)=6=2(3)=n(A)n(B) In fact,n(A x B)=n(A)n(B)for any finite sets A and B.This follows from the observation that,for an ordered pair(a,b)in A x B,there are n(A)possibilities for a,and for each of these there are n(B)possibilities for b. The idea of a product of sets can be extended to any finite number of sets.For any sets A1,A2,...,An,the set of all ordered n-tuples (a1,a2,...,an)where a A1,a2A2.....an An is called the product of the sets A1,....An and is denoted by A1×A2×·×Ang Just as we write A2 instead of A x A,so we write A"instead of A x A x...x A,where there are n factors all equal to A.For example,R3=Rx R x R denotes the usual three-dimensional space. 2.3 RELATIONS We begin with a definition. Definition 2.1:Let A and B be sets.A binary relation or,simply,relation from A to B is a subset of A x B. Suppose R is a relation from A to B.Then R is a set of ordered pairs where each first element comes from A and each second element comes from B.That is,for each pair aA and bB,exactly one of the following is true: (i)(a,b)E R;we then say "a is R-related to b",written aRb. (ii)(a,b)R;we then say "a is not R-related to b",written arb. If R is a relation from a set A to itself,that is,if R is a subset of A2 =A x A,then we say that R is a relation on A. The domain of a relation R is the set of all first elements of the ordered pairs which belong to R,and the range is the set of second elements. Although n-ary relations,which involve ordered n-tuples,are introduced in Section 2.10,the term relation shall then mean binary relation unless otherwise stated or implied
24 RELATIONS [CHAP. 2 Fig. 2-1 There are two things worth noting in the above examples. First of all A×B = B ×A. The Cartesian product deals with ordered pairs, so naturally the order in which the sets are considered is important. Secondly, using n(S) for the number of elements in a set S, we have: n(A × B) = 6 = 2(3) = n(A)n(B) In fact, n(A × B) = n(A)n(B) for any finite sets A and B. This follows from the observation that, for an ordered pair (a, b) in A × B, there are n(A) possibilities for a, and for each of these there are n(B) possibilities for b. The idea of a product of sets can be extended to any finite number of sets. For any sets A1, A2,...,An, the set of all ordered n-tuples (a1, a2,...,an) where a1 ∈ A1, a2 ∈ A2,...,an ∈ An is called the product of the sets A1,...,An and is denoted by A1 × A2 ×···× An or n i=1 A1 Just as we write A2 instead of A × A, so we write An instead of A × A ×···× A, where there are n factors all equal to A. For example, R3 = R × R × R denotes the usual three-dimensional space. 2.3 RELATIONS We begin with a definition. Definition 2.1: Let A and B be sets. A binary relation or, simply, relation from A to B is a subset of A × B. Suppose R is a relation from A to B. Then R is a set of ordered pairs where each first element comes from A and each second element comes from B. That is, for each pair a ∈ A and b ∈ B, exactly one of the following is true: (i) (a, b) ∈ R; we then say “a is R-related to b”, written aRb. (ii) (a, b) /∈ R; we then say “a is not R-related to b”, written aRb. If R is a relation from a set A to itself, that is, if R is a subset of A2 = A × A, then we say that R is a relation on A. The domain of a relation R is the set of all first elements of the ordered pairs which belong to R, and the range is the set of second elements. Although n-ary relations, which involve ordered n-tuples, are introduced in Section 2.10, the term relation shall then mean binary relation unless otherwise stated or implied.
CHAP.2] RELATIONS 25 EXAMPLE 2.3 (a)A =(1,2,3)and B={x,y,z),and let R={(1,y),(1,z),(3,y)).Then R is a relation from A to B since R is a subset of A x B.With respect to this relation, 1Ry,1Rz,3Ry,but 1Rx,2Rx,2Ry,2Rz,3Rx,3Rz The domain of R is (1,3)and the range is (y,) (b)Set inclusion is a relation on any collection of sets.For,given any pair of set A and B,either A C B or A B. (c)A familiar relation on the set Z of integers is"m divides n."A common notation for this relation is to write mn when m divides n.Thus 630 but 725. (d)Consider the set L of lines in the plane.Perpendicularity,written"L,"is a relation on L.That is,given any pair of lines a and b,either a⊥bora∠b.Similarly,“is parallel to,”written“l,”is a relation on L since either a ll bor a wb. (e)Let A be any set.An important relation on A is that of equality, {(a,a)a∈A} which is usually denoted by"=."This relation is also called the identity or diagonal relation on A and it will also be denoted by△A or simply△. (f)Let A be any set.Then A x A and 0 are subsets of A x A and hence are relations on A called the universal relation and empty relation,respectively. Inverse Relation Let R be any relation from a set A to a set B.The inverse of R,denoted by R-,is the relation from B to A which consists of those ordered pairs which,when reversed,belong to R;that is, R-1={b,a)I(a,b)∈R} For example,let A =(1,2,3)and B={x,y,z).Then the inverse of R={(1,y),(1,z),(3,y)}isR-={y,1),(z,1),y,3)} Clearly,if R is any relation,then (R-)-1=R.Also,the domain and range of R-are equal,respectively,to the range and domain of R.Moreover,if R is a relation on A,then R-is also a relation on A. 2.4 PICTORIAL REPRESENTATIVES OF RELATIONS There are various ways of picturing relations. Relations on R Let S be a relation on the set R of real numbers;that is,S is a subset of R2=R x R.Frequently,S consists of all ordered pairs of real numbers which satisfy some given equation E(x,y)=0(such as x2+y2=25). Since R2 can be represented by the set of points in the plane,we can picture S by emphasizing those points in the plane which belong to S.The pictorial representation of the relation is sometimes called the graph of the relation.For example,the graph of the relation x2+y2=25 is a circle having its center at the origin and radius 5. See Fig.2-2(a)
CHAP. 2] RELATIONS 25 EXAMPLE 2.3 (a) A = (1, 2, 3) and B = {x, y,z}, and let R = {(1, y), (1, z), (3, y)}. Then R is a relation from A to B since R is a subset of A × B. With respect to this relation, 1Ry, 1Rz, 3Ry, but 1Rx, 2Rx, 2Ry, 2Rz, 3Rx, 3Rz The domain of R is {1, 3} and the range is {y,z}. (b) Set inclusion ⊆ is a relation on any collection of sets. For, given any pair of set A and B, either A ⊆ B or A ⊆ B. (c) A familiar relation on the set Z of integers is “m divides n.” A common notation for this relation is to write m|n when m divides n. Thus 6 | 30 but 7 | 25. (d) Consider the set L of lines in the plane. Perpendicularity, written “⊥,” is a relation on L. That is, given any pair of lines a and b, either a ⊥ b or a⊥ b. Similarly, “is parallel to,” written “||,” is a relation on L since either a b or a b. (e) Let A be any set. An important relation on A is that of equality, {(a, a)| a ∈ A} which is usually denoted by “=.” This relation is also called the identity or diagonal relation on A and it will also be denoted by A or simply . (f) Let A be any set. Then A × A and ∅ are subsets of A × A and hence are relations on A called the universal relation and empty relation, respectively. Inverse Relation Let R be any relation from a set A to a set B. The inverse of R, denoted by R−1, is the relation from B to A which consists of those ordered pairs which, when reversed, belong to R; that is, R−1 = {(b, a)|(a, b) ∈ R} For example, let A = {1, 2, 3} and B = {x, y,z}. Then the inverse of R = {(1, y), (1, z), (3, y)} is R−1 = {(y, 1), (z, 1), (y, 3)} Clearly, if R is any relation, then (R−1)−1 = R. Also, the domain and range of R−1 are equal, respectively, to the range and domain of R. Moreover, if R is a relation on A, then R−1 is also a relation on A. 2.4 PICTORIAL REPRESENTATIVES OF RELATIONS There are various ways of picturing relations. Relations on R Let S be a relation on the set R of real numbers; that is, S is a subset of R2 = R × R. Frequently, S consists of all ordered pairs of real numbers which satisfy some given equation E(x, y) = 0 (such as x2 + y2 = 25). Since R2 can be represented by the set of points in the plane, we can picture S by emphasizing those points in the plane which belong to S. The pictorial representation of the relation is sometimes called the graph of the relation. For example, the graph of the relation x2 +y2 = 25 is a circle having its center at the origin and radius 5. See Fig. 2-2(a).
26 RELATIONS [CHAP.2 6 -5 0 5 T-5 x2+y2=25 (a) (b) Fig.2-2 Directed Graphs of Relations on Sets There is an important way of picturing a relation R on a finite set.First we write down the elements of the set,and then we draw an arrow from each element x to each element y whenever x is related to y.This diagram is called the directed graph of the relation.Figure 2-2(b),for example,shows the directed graph of the following relation R on the set A =(1,2,3,4): R={1,2),(2,2),(2,4),(3,2),(3,4),(4,1),(4,3)} Observe that there is an arrow from 2 to itself,since 2 is related to 2 under R. These directed graphs will be studied in detail as a separate subject in Chapter 8.We mention it here mainly for completeness. Pictures of Relations on Finite Sets Suppose A and B are finite sets.There are two ways of picturing a relation R from A to B. (i)Form a rectangular array(matrix)whose rows are labeled by the elements of A and whose columns are labeled by the elements of B.Put a 1 or 0 in each position of the array according as aA is or is not related to bE B.This array is called the matrix of the relation. (ii)Write down the elements of A and the elements of B in two disjoint disks,and then draw an arrow from a e A tob E B whenever a is related to b.This picture will be called the arrow diagram of the relation. Figure 2-3 pictures the relation R in Example 2.3(a)by the above two ways. 0 11 、 0 0 0 3 0 1 0 (0 (i) R={1,y以(1，z),(3,y)} Fig.2-3
26 RELATIONS [CHAP. 2 Fig. 2-2 Directed Graphs of Relations on Sets There is an important way of picturing a relation R on a finite set. First we write down the elements of the set, and then we draw an arrow from each element x to each element y whenever x is related to y. This diagram is called the directed graph of the relation. Figure 2-2(b), for example, shows the directed graph of the following relation R on the set A = {1, 2, 3, 4}: R = {(1, 2), (2, 2), (2, 4), (3, 2), (3, 4), (4, 1), (4, 3)} Observe that there is an arrow from 2 to itself, since 2 is related to 2 under R. These directed graphs will be studied in detail as a separate subject in Chapter 8. We mention it here mainly for completeness. Pictures of Relations on Finite Sets Suppose A and B are finite sets. There are two ways of picturing a relation R from A to B. (i) Form a rectangular array (matrix) whose rows are labeled by the elements of A and whose columns are labeled by the elements of B. Put a 1 or 0 in each position of the array according as a ∈ A is or is not related to b ∈ B. This array is called the matrix of the relation. (ii) Write down the elements of A and the elements of B in two disjoint disks, and then draw an arrow from a ∈ A to b ∈ B whenever a is related to b. This picture will be called the arrow diagram of the relation. Figure 2-3 pictures the relation R in Example 2.3(a) by the above two ways. Fig. 2-3
CHAP.2] RELATIONS 27 2.5 COMPOSITION OF RELATIONS Let A,B and C be sets,and let R be a relation from A to B and let S be a relation from B to C.That is,R is a subset of A x B and S is a subset of B x C.Then R and S give rise to a relation from A to C denoted by RoS and defined by: a(RoS)c if for some b E B we have aRb and bSc. That is, RoS={(a,c)Ithere exists b∈B for which(a,b)∈Rand(b,c)∈S} The relation RoS is called the composition of R and S;it is sometimes denoted simply by RS. Suppose R is a relation on a set A,that is,R is a relation from a set A to itself.Then RoR,the composition of R with itself,is always defined.Also,RoR is sometimes denoted by R2.Similarly,R3=R2oR RoRoR, and so on.Thus R"is defined for all positive n. Warning:Many texts denote the composition of relations R and S by SoR rather than RoS.This is done in order to conform with the usual use of gof to denote the composition of fand g where fand g are functions.Thus the reader may have to adjust this notation when using this text as a supplement with another text.However,when a relation R is composed with itself,then the meaning of RoR is unambiguous. EXAMPLE 2.4 Let A =(1,2,3,4).B (a,b,c,d),C=(x,y,z)and let R={(1,a),(2,d),(3,a),(3,b),(3,d)}andS={b,x),(b,z),(c,y),(d,z)} Consider the arrow diagrams of R and S as in Fig.2-4.Observe that there is an arrow from 2 to d which is followed by an arrow from d to z.We can view these two arrows as a "path"which"connects"the element 2 A to the element z∈C.Thus: 2(Ro S)z since 2Rd and dSz Similarly there is a path from 3 to x and a path from 3 to z.Hence 3(RoS)x and 3(RoS)z No other element of A is connected to an element of C.Accordingly, RoS={2,z),(3,x),(3,z)} Our first theorem tells us that composition of relations is associative. Theorem 2.1:Let A,B,C and D be sets.Suppose R is a relation from A to B,S is a relation from B to C,and Tis a relation from C to D.Then (RoS)oT=Ro(SoT) We prove this theorem in Problem 2.8. Fig.2-4
CHAP. 2] RELATIONS 27 2.5 COMPOSITION OF RELATIONS Let A, B and C be sets, and let R be a relation from A to B and let S be a relation from B to C. That is, R is a subset of A × B and S is a subset of B × C. Then R and S give rise to a relation from A to C denoted by R◦S and defined by: a(R◦S)c if for some b ∈ B we have aRb and bSc. That is , R ◦ S = {(a, c)| there exists b ∈ B for which (a, b) ∈ R and (b, c) ∈ S} The relation R◦S is called the composition of R and S; it is sometimes denoted simply by RS. Suppose R is a relation on a set A, that is, R is a relation from a set A to itself. Then R◦R, the composition of R with itself, is always defined. Also, R◦R is sometimes denoted by R2. Similarly, R3 = R2◦R = R◦R◦R, and so on. Thus Rn is defined for all positive n. Warning: Many texts denote the composition of relations R and S by S◦R rather than R◦S. This is done in order to conform with the usual use of g◦f to denote the composition of f and g where f and g are functions. Thus the reader may have to adjust this notation when using this text as a supplement with another text. However, when a relation R is composed with itself, then the meaning of R◦R is unambiguous. EXAMPLE 2.4 Let A = {1, 2, 3, 4}, B = {a, b, c, d}, C = {x, y,z} and let R = {(1, a), (2, d), (3, a), (3, b), (3,d)} and S = {(b, x), (b, z), (c, y), (d, z)} Consider the arrow diagrams of R and S as in Fig. 2-4. Observe that there is an arrow from 2 to d which is followed by an arrow from d to z. We can view these two arrows as a “path” which “connects” the element 2 ∈ A to the element z ∈ C. Thus: 2(R ◦ S)z since 2Rd and dSz Similarly there is a path from 3 to x and a path from 3 to z. Hence 3(R◦S)x and 3(R◦S)z No other element of A is connected to an element of C. Accordingly, R ◦ S = {(2, z), (3, x), (3, z)} Our first theorem tells us that composition of relations is associative. Theorem 2.1: Let A, B, C and D be sets. Suppose R is a relation from A to B, S is a relation from B to C, and T is a relation from C to D. Then (R ◦ S) ◦ T = R ◦ (S ◦ T ) We prove this theorem in Problem 2.8. Fig. 2-4
28 RELATIONS [CHAP.2 Composition of Relations and Matrices There is another way of finding RoS.Let Mg and Ms denote respectively the matrix representations of the relations R and S.Then a b c d x y Z 1 「100 0 a 000 MR= 0001 and Ms= b 10 1101 010 4 0000 d 001 Multiplying MR and Ms we obtain the matrix x y z 1「00 07 0 1 M=MRMs 0 3 0 00 The nonzero entries in this matrix tell us which elements are related by RoS.Thus M=MR Ms and MRos have the same nonzero entries. 2.6 TYPES OF RELATIONS This section discusses a number of important types of relations defined on a set A. Reflexive Relations A relation R on a set A is reflexive if aRa for every a e A,that is,if (a,a)E R for every aA.Thus R is not reflexive if there exists aA such that (a,a)R. EXAMPLE 2.5 Consider the following five relations on the set A =(1,2,3,4): R1={(1,1),(1,2),(2,3),(1,3),(4,4)} R2={(1,1)1,2),(2,1),(2,2),(3,3),(4,4)} R3={(1,3),(2,1)} R4=0,the empty relation Rs =A x A,the universal relation Determine which of the relations are reflexive. Since A contains the four elements 1,2,3,and 4,a relation R on A is reflexive if it contains the four pairs (1,1),(2,2),(3,3),and(4,4).Thus only R2 and the universal relation R5 =A x A are reflexive.Note that RI,R3,and R4 are not reflexive since,for example,(2,2)does not belong to any of them. EXAMPLE 2.6 Consider the following five relations: (1)Relation <(less than or equal)on the set Z of integers. (2)Set inclusion c on a collection C of sets. (3)Relation L(perpendicular)on the set L of lines in the plane. (4)Relation ll (parallel)on the set L of lines in the plane. (5)Relation|of divisibility on the set N of positive integers.(Recallxy if there exists z such that xz =y.) Determine which of the relations are reflexive
28 RELATIONS [CHAP. 2 Composition of Relations and Matrices There is another way of finding R◦S. Let MR and MS denote respectively the matrix representations of the relations R and S. Then MR = a bcd 1 2 3 4 ⎡ ⎢ ⎢ ⎣ 1000 0001 1101 0000 ⎤ ⎥ ⎥ ⎦ and MS = x yz a b c d ⎡ ⎢ ⎢ ⎣ 000 101 010 001 ⎤ ⎥ ⎥ ⎦ Multiplying MR and MS we obtain the matrix x yz M = MRMS = 1 2 3 4 ⎡ ⎢ ⎢ ⎣ 000 001 102 000 ⎤ ⎥ ⎥ ⎦ The nonzero entries in this matrix tell us which elements are related by R◦S. Thus M = MRMS and MR◦S have the same nonzero entries. 2.6 TYPES OF RELATIONS This section discusses a number of important types of relations defined on a set A. Reflexive Relations A relation R on a set A is reflexive if aRa for every a ∈ A, that is, if (a, a) ∈ R for every a ∈ A. Thus R is not reflexive if there exists a ∈ A such that (a, a) /∈ R. EXAMPLE 2.5 Consider the following five relations on the set A = {1, 2, 3, 4}: R1 = {(1, 1), (1, 2), (2, 3), (1, 3), (4, 4)} R2 = {(1, 1)(1, 2), (2, 1), (2, 2), (3, 3), (4, 4)} R3 = {(1, 3), (2, 1)} R4 = ∅, the empty relation R5 = A × A, the universal relation Determine which of the relations are reflexive. Since A contains the four elements 1, 2, 3, and 4, a relation R on A is reflexive if it contains the four pairs (1, 1), (2, 2), (3, 3), and (4, 4). Thus only R2 and the universal relation R5 = A × A are reflexive. Note that R1, R3, and R4 are not reflexive since, for example, (2, 2) does not belong to any of them. EXAMPLE 2.6 Consider the following five relations: (1) Relation ≤ (less than or equal) on the set Z of integers. (2) Set inclusion ⊆ on a collection C of sets. (3) Relation ⊥ (perpendicular) on the set L of lines in the plane. (4) Relation (parallel) on the set L of lines in the plane. (5) Relation|of divisibility on the set N of positive integers. (Recall x |y if there exists z such that xz = y.) Determine which of the relations are reflexive