Relations 2.4 INTRODUCTION The reader is familiar with many relations which are used in mathematics and computer in mathematics and computer science, e.g., “less than”, “is parallel to”, “is a subset of”, and so on. Ina certain sensc, these rela- tions consider the existence or nonexistence of a certain connection between pairs of objects taken in a definite order. Formally, we define a relation in terms of these “ordered pairs”, There are three kinds of relations which play a major role in our theory: (i) equivalence relations, (i) order relations, (iii) functions. Equivalence relations are mainly covered in this chapter. Order relations are introduced here, but will also be discussed in Chapter 14. Functions are covered in the next chapter. Relations, as noted above, will be defined in terms of ordered pairs (a,b) of elements, where ais designated as the first element and 6 as the second element. In particular, (a, b) =(¢.d) iftand only if a= c and b = d. The (a, 6) # (b, a) unless a= b. This contrasts with sets studied in Chapter 1, where the order of elements is irrelevant; for example {3, 5) = {5, 3}. Although matrices will be covered in Chapter 5, we have included their connection with relations here for completeness. These sections, however, can be ignored at a first reading by those with no previous knowledge of matrix theory. | | | | | 22 PRODUCT SETS Consider two arbitrary sets A and B. The set of all ordered pairs (a, b) where a € A and be Bis called the product, or Cartesian product, of A and B.A short designation of this product is A x B, which is read “A cross B”. By definition, AXB={(a,b):a€ Aandbe B} One frequently writes 4? instead of A x A.Discrete Mathematics | Example 2.4 R denotes the set of real numbers and so R? = Rx R is the set of ordered pairs of real numbers, The reader is familiar with the geometrical representation of R’ as points in the plane as in Fig. 2.1. Here each point P represents an ordered pair (a, b) of real numbers and vice versa; the vertical line through P meets the x axis at a, and the horizontal line through P meets the y axis at b R’ is frequently called the Cartesian plane. | Example 2.2 let A={1, 2} and B= {a, 6, c}. Then | Ax B= {(1, a), (1, b), (1, ¢), (2, a), (2, 6), (2, c)} BxA={(a, 1), (a, 2), (by 1), (by 2), (C1), (c, 2)} Also Ax A={(1, 1), (1, 2), (2, 1), (2, 2)} | There are two things worth noting in the above example. First of all 1 Ax B +B 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 -2 n(A x B) = 6 =2-3=n(A) - n(B) a 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 xB, there are n(A) possibilities for a, and for each of these there Fig, 2.4 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 Ay Az, +4 Ay» the set of all ordered n-tuples (ay, dz, ..., d,) Where a, € Ay, dy © Ap, «5 dy © Ay is called the product of the sets 4,,..., 4, and is denoted by AyXA,x-xA, or [A mi Just as we write 4? instead of A x A, so we write A" instead of A x Ax +. x A, where there are 1 factors all equal to A. For example, R? = R x R x R denotes the usual three-dimensional space. 2.3. RELATIONS We begin with a definition. Definition 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 4 to B. Then 2 is a set of ordered pairs where each first element comes_— Relations 2. from A and cach second clement comes from B. That is, for each pair a © A and b © By € the following is true: (i) (a, b) © R; we then s (ii) (a, b) € Ry we then say “a is not R-related to b”, written ab, ‘ais R-related to b”, written aRb, is, if R isa sul If Risa relation from a set 4 to itself, tha set of A? = A x A, then we say that R is a relation on. The domain of a relation R is the sct of all first elements of the ordered pairs which belong to R, and the range of Ris the set of second elements, ‘Although n-ary relations, which involve ordered n-tuples, are introduced in Section 2. 12, the term relation shall mean binary relation unless otherwise stated or implied. ! Example 2.3 zsh * (a) Let A=(1, 2, 3) and B= {x, y, 2), and let R= {(1, y), (1, 2), (3, y)}. Then Ris a relation from A to B since R is a subset of A x B. With respect to this relation. 1Ry, 1Rz, 3Ry, but 1, 2Rk, 2ky, 2Re, 3Rk, 3Rz, The domain of R is {1, 3} and the range is {y, z}. (b) Let A= {eggs, milk, com} and B = {cows, goats, hens}. We can define a relation from A to B by (a, 6) € R if a is produced by 6. In other words, R= {(eggs, hens), (milk, cows), (milk goats)} With respect to this relation. eggs Rhens, milk R cows, etc. | (c) Suppose we say that two countries are adjacent if they have some part of their boundaries in common. Then “is adjacent to” is a relation R on the countries of the earth. Thus (Italy, Switzerland) € R but (Canada, Mexico) ¢ R (d) Set inclusion c is a relation on any collection of sets. For, given any pair of sets A and B, / eitherA c BorAcB. ‘A familiar relation on the set Z of integers in “m divides n”. A common notation for this relation is to write m|n when m divides n. Thus 6|30 but 7/25. Consider the set L of lines in the plane. Perpendicularity, written LL, is a relation on L. That is, given any pair of lines a and 6, eithera Lb ora£b. Similarly, “is parallel to”, written |], is a relation on L since either a || b or af. 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 A. Let A be any set. Then A x A and @ are subsets of A x A and hence are relations on A called the universal relation and empty relation, respectively. it (9) (h2.4 = ___ Discrete Mathematics (i) Ifa set has n elements, how many relations are there on the set? Let A be the set with [A] =n. Relation on set A is subset of Ax A and |A x Al = n®. Also set of all possible subsets of Ax Ais power set of Ax A ie. P(A x A). If lA xA| =n? then [P(A x A)| = 2” i.e. if set has n element then there are 2” relations on it. (i) Let A be the set {1, 2, 3, 4}, enlist elements of relation R= {(a, b) |a divisible by 6} | R= {(1,1), (2,1), (3,1), (4,1), (4,2), (2.2), (3,3), (4.4)} (k) Let A be the set of programmers and B denote the set of computer languages, what possible | interpretation can be given to | (i) 4% B: all possible set of ordered pairs (a, 6) where ae A and 6 € B which means we | get all possible pairs of programmers and computer languages. | (ii) Relation from A to Bas Ax B | Relation R from A x B, represents all the relations such as j R= {(a, b) |ae A, 6 B such that a can work on b language based project} or | S={(a, ) |a@ A, b © B such that a is undergoing training on programming | language 6} and so on. | (Relations from sets, say A to B, are subsets of the Cartesian product as A x B, two relations j on sets, say from A to B can be combined in any way two sets are combined. Solve following. | {a,b,c} and B={a, b,c, d}. The relations | {(a, a), (b, 6), (c,)} and S={(a, a), (a, 6), (a, ¢), (a, d)} | Now RUS ={(a, a), (a, 6), (a, ¢), (a, d), (b, 6), (c, o)} | ROS ={(a, a)} | R-S ={(b, b), (6. O} | 2. Let A be the set of computer science students and B be the set of computer languages. | Let R be the relation consisting of all ordered pairs (a, 6) where student a is required 1. Let A R | to learn language b in a course. Let 5 be the relation consisting of all ordered pairs (a, 6) such that student a has learnt language 6. Describe the ordered pairs in each | of the following relations. | 1. RUS RUS = {(a, 6) | student a is required to learn or has learnt language 6} 2 RAS ROS={(a, 6) | ais required to learn and has learnt language 6} 3. ROS R®S = {(a, 6) | either a is required to learn 6 but has not learnt it or a has learnt 6 but is not required to} i 4 R-S R—S={(a, b) | a is required to learn 6 but has not learnt it} 5-R S-R ={ (a, 6) | a has learnt language b but is not required to}2.5 Relations 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, Rl ={(b,a): (a, De R} For example, the inverse of the relation R = {(1, y), (1, 2), (3, »)} from 4 = {1, 2, 3} to B= (x= follows: R°={0,),G 0,3} Clearly, if is any relation, then (Ry =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 REPRESENTATIONS OF RELATIONS First we consider a relation S on the set R of real numbers; that is, Sis a subset of R’ = Rx R. Since R? 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. Frequently, the relation S consists of all ordered pairs of real numbers which satisfy some given equation EQ, y) =0 We usually identify the relation with the equation; that is, we speak of the relation E(x, y) = 0. | Consider the relation S defined by the exyjuation ery =25 That is, 5 consists of all ordered pairs (x, y) which satisfy the given equation. The graph of the equation is a circle having its center at the origin and radius 5. See Fig. 2.2.Discrete Mathematics 2.6 Representations of Relations on Finite Sets ise A and B are finite sets. The following are two ways of picturing a relation R from 4 to B. by the elements of 4 and whose columns are’ labeled ‘Suppo: ing as a € A is or is not related (i) From rectangular array whose rows are labeled 2 by the elements of B. Put a 1 or 0 in each position of the array accordi to B. This array is called the matrix of the relation. (ii) Write down the elements of 4 and the elements of B in two disjoint disks, and then draw an arrow froma Ato b € B whenever a is related to b. The picture will be called the arrow diagram of the relation. Figure 2.3 pictures the first relations in Example 2.3 by the above two ways. Lz y 2 a (2) i}o 1 1 Se 2; 0 0 0 \ 3 ee 3/0 1 0 nw R= (0,9). (1,2 9} Fig. 23 Directed Graphs of Relations on Sets There is another way of picturing a relation R when R is a relation from a finite set to itself. First we write down the elements of the set, and then we draw an arrow from each element x to each element y whenever is related to y. This diagram is called the directed graph of the relation. Figure 2.4, for example, shows tht 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. @ a? Fig. 24___ Relations __ ar) 2.5 COMPOSITION OF RELATIONS Let A, B, and are nd te R be a relation from A to B and let be a relation from B to C. That is, R is a subset of AX B and Sis a subset of B x C. Then R and S give rise to a relation from A to C denoted by Ro S and defined by a(R © S)c if for some b € B we have aRb and bSc That is, Re S= {(a,c): there exists b € B for which (a, b) € Rand (b,c) € S} The relation Ro 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 ition of R with itself is always defined, and R © R is sometimes denoted by R’. Similarly, = Re RoR, and so on. Thus R" is defined for all positive n. Warning: Many texts denote the composition of relations R and S by Se 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 his 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 e R is unambiguous. The arrow diagrams of relations give us a geometrical interpretation of the composition Re S as seen in the following example. E ample 2.5 peseoee | 1 | Let A= (1, 2, 3, 4}, B= {a, b,c dj, C={x, y, z} and let R={(1, a), (2, d), (3, a), (3, 6), (3, )} and S= {(b, x), (b, 2), (Gy), (d, 2)} Consider the arrow diagrams of R and S as in Fig. 2.5. 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(ReS)z since 2Rd and dSz Similarly there is a path from 3 to x and a path from 3 to z. Hence 3(ReS)x and 3(ReS)z No other element of A is connected to an element of C. Accordingly, Ro S={(2, 2), (3), (3, 2)}re] Discrete Mathematics Composition of Relations and Matrices There is another way of finding R © S. Let My and and 5. Then Ms denote respectively the matrices of the relations z abed xyz 1/1 0 0 0 a(0 0 0} Mg=2/0 00 11 and Mg=|1 0 1 3]1 101 cj0 10 4\0 00 0 d\0 01 Multiplying My and M, we obtain the matrix x ya 1/0 0 0 2}0 01 M =M,Ms= eS 3ht 0 2 4\0 0 0 The nonzero entries in this matrix tell us which elements are related by R » S. Thus M=Mg Mg and Mz , shave the same nonzero entries. Our first theorem tells us that the 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 fron Bto C, and Tis a relation from C to D. Then (ReS)eT=Ro(SeT) Example 2.6 2: let R = {(a, 6), (c, d), (6, 6)} and S = {(d, 6), (6, €), (c, a), (a, ¢)}. Compute (i) ReS = {(a, e), (c, 6), (6, e)} (ii) SoR={(d, 6), (c, 6), (a, d)}. Note that Ro S#5 oR (iii) (RoS)oR={(c, b)}. (iv) Ro(SeR)={(c, b)} Note that (Ro S)oR =Ro(SoR) (v) ReR={(a, 6), (6, b)} (vi) S05 ={(d, e), (co), (a, a}. (vii) RoR oR={(a, 6), (b, 6)}| | t | | 1 Relations 2.9 Example 2,7 Find the relation determined by following Fig, 2.6, Fig. 26 A={1, 2, 3, 4, 5} R={(1 1), (2, 2), (5,5), (1, 2), (4, 3), (1,4), (2 1), (4, 2), (3,5), (3, 4)} Example 2.8 Let R and 5 be two relations on set of positive integers I and (a, 3a) |ae I} S={(a,0+1) ae I} Compute: (i) RoS={(a, 30+1) la J} (ii) RoR={(a, 9a) lae I} (iii) Ro Ro R={(a, 270) |ae I} (iv) ReSoR={(a, 9043) [ae T} Let P be a set of programmers and Q a set of projects. Let R be a binary relation from P to Q such that (o, 6) is in R if programmer a is assigned project b. Let 5 be a binary relation on P such that ‘(x.y) is in S if x and y can get along with each other if they were assigned same project. State the Condition in terms of R and S and a relation derived from R and S such that an assignment of the Programmers to the project according to R will put only those programmers together on the same Project who can get along with each other. Here P = Set of programmers Q= Set of projects[z40 | d project 6} and y can get along with each other on same projec) p. b< Qand (a, a;) € R, (a, b)€ Sand (ay, b) © S). Twill assign @ project, who can set along with each other, 2.6 TYPES OF RELATIONS Consider a given set 4. This section discusses a number of important types of relations which are deting, on A. Reflexive Relations A relation R on a set 4 is reflexive if aRa for every a € A, that is, if (a, a) € R for every ae A, Thus R is Hot reflexive if there exists an a € A such that (a,a) € R. Example 2.10 3 f Consider the following five relations on the set A = {1, 2, 3, 4}: Ry ={(1, 1), (1, 2), (2, 3), (4, 3), (4, 4)} Ro={(t, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)} Ry = {(1, 3), (2, I} R, = ©, the empty relation 8s =AxA, the universal relation | Determine which of the relations are reflexive. Since A contains the four elements 1, 2, 3, and 4 pairs (1, 1), (2, 2), (3, 3), and (4, 4). Thus only , 2 relation R on A is reflexive if it contains the four | Note that R,, Ry, and R; | R, and the universal relation R, =A x A are reflexiy are not reflexive since, for example, (2, 2) does not belong to any of ther : Example 2.11 Consider the following.five relations: | 1. Relation < (less than or equal) on the set | 2, Set inclusion < on a collection C of sets 3. Relation (perpendicutar : ) on the set L of lines in the plane. 4, Relation || (paraltel) on the set 2 of lines in the plane. 2 of integers= Relations 2.11 Ss 5, Relation | of divistbility on the set N of positive integers. (Recall x[y if there exists z such that x2 = y.) Determine which of the relations are reflexi The relation (3) is not reflexive since no line is perpendicular to itself. Also (4) is not reflexive since no line is parallel to itself. The other relations are reflexive: that is, x 12. Let R be relation on A such that R={(a, 6)|a and 6 € A, a and 6 have their birth dates in the same month} | Under relation R, has many could be maximum equivalence classes of A? | Here maximum number of equivalence classes could be 12 for twelve months and minimum one.Relations 9 29 PARTIAL ORDERING RELATIONS ion defines another important class of relations. A relation R on a set S is called a partial ordering 12 partial order if R is reflexive, antisymmetric, and transitive. A set S together with a partial ordering R is Jled a partially ordered set ot poset. Partially ordered sets will be studied in more detail in Chapter 14, so re we simply give some examples. Example 2.24 pores 8 ‘ (2) The relation ¢ of set inclusion is a partial ordering on any collection of sets since set inclusion has the three desired properties. That is, 1. ACA for any set A. 2. IfAcBand BCA, then A= 8. 3. fACBand BoC, thenAcl. (b) The relation < on the set R of real numbers is reflexive, antisymmetric, and transitive. Thus < is a partial ordering. (©) The relation “a divides 6” is a partial ordering on the set N of positive integers. However, “a divides b” is not a partial ordering on the set Z of integers since a|b and bla does not ___imply a = b. For example, 3-3 and - 33 but 34-3.21 Pe Relations ORDERED PAIRS AND PRODUCT SETS Given: A= (1, 2,3) and B= {a,b}. Find; (a) A x B; (b) BX A; (c) Bx B. (a) 4x B consists of all ordered pairs (x, y) where x € A and y € B. Hence AXB=4(1,a), (1, b), (2, 4), (2, 6), (3, 4), (3, )} (b) BX A consists of all ordered pairs (y, x) where y € Band.x € A, Hence Bx A= {(a, 1), (ay 2), (4, 3), (b, 1), (65 2), (6, 3D} (c) BX B consists of all ordered pairs (x, y) where x,y € B. Hence BXB= {(a,a), (a,b), (b, a), (b, b)} As expected, the number of elements in the product set is equal to the product of the numbers of the elements in cach set, Given: A= (1,2), B= {x,y,z}, and C= (3, 4}. Find: A xB x C. Ax BX C consists of all ordered triplets (a, b,c) where a € A, b € B,c € C. These elements of A x B can be systematically obtained by a so-called tree diagram (Fig. 2.7). The elements of A x B x C ly the 12 ordered triplets to the right of the tree diagram. Observe that n(A) = n(B) = 3, and n(C) = 2 and, as expected, n(A X BX C) = 12 = n(A) - n(B) - n(C) < 1 <<, 3 b + x hence (1, x) belongs to Re S. 2 Similarly, (2, ») and (2, =) belong to <7] =] ReS. We have aa a y | Re S={1,x), (2,y), (2,2)} (See Example 2.5.) Fig. 2.10 (b) The matrices of Mz, Mz, andM,., « follow: abe x ya ies 1/0 1 oO) afo I oO 100 Me= ait g | Ms= 10 of Mres= a]q 4 t a) clo 14 3(0 0 0Relations _ — [ees] Multiplying My and My, we obtain 100 MaMy=\0 24 000 Observe that My, sand Mp Ms have the same zero entries. 213 Let R and S'be the following relations on A = {1, 2,3}: R= ((1, D.C, 2), (2, 3), 3, 1), (3, 3)}, S= 41, 2), (1, 3), (2, 1), 3, 3)} Find — (ROS ROS RS (b)RoS; (eS =S0S. ets, and take the usual intersection and union. For A°, use the fact that ersal relation on A. = {(1, 2), 3, 3)} ROS={(1, 1), (1, 2), A, 3), 2, 1, (2, 3), B, 1) 3, 3)5 Re = {(1, 3), (2, 1), (2, 2), 3, 2)} (b) For each pair (a, b) € R, find all pairs (b, c) € S. Then (a, c) € Ro S. For example, (1, 1) © Rand (1, 2), (1, 3) € S: hence (1, 2) and (1, 3) belong to R oS. Thus, (1, 2), (1, 3) (Ls 1), (2, 3), (3, 2), (3, 3) (c) Following the algorithm in (b), we get S$? =SoS={(1, 1), (1, 3), (2,2), (2,3), 3)} (a) Treat R and S simply as Ax Ais the uni Ras 2.14 Prove Theorem 2.1; Let A, B, C and D be sets. Suppose & is a relation from A to B, Sis a relation from B to Cand Tis a relation from C to D. Then (R oS) e T=Re (Se T). We need to show that cach ordered pair in (R © S) © T belongs to R (Se 7), and vice versa. Suppose (a, d) belongs to (Re S) ¢ T. Then there exists a c in C such that (a, ¢) € Re S and (cd) © T. Since (a, c) € Re S, there exists a b in B such that (a, b) € R and (b, c) € S. Since (b,c) € Sand (c, d) € T, we have (b, d) € S° T; and since (a, b) € Rand (b, d) < ST, we have (a, d) € Re (So 7), Therefore, (Re S)> TR e (So 7). Similarly Re (Se Tc (Ro 8) © T, Both inclusion relations prove (R ° S)° T=Re (Se 7). PES OF RELATIONS AND CLOSURE PROPERTIES 2415 Consider the following five relations on the set A = {1, 2, 3}: R={(1, 1), (1, 2), (1, 3), 3, 3)} O = empty relation S={(1, 1), (1, 2), (2, 1), 2, 2), B, 3) AxA = universal, relation T= {(, 1), (1, 2), (2, 2), (2; 3)} Determine whether or not each of the above relations on A is: (a) reflexive; (b) symmetric; (c) transitive; (d) antisymmetric.2.26 Discrete Mathematics (a) Ris not refleri is not reflexive. since 2 € 4 but (2, 2) € R. Tis not reflexive since (3, 3) € Tand, similarly, and 4X4 are reflexive. (b) Ris not symmetric since (1, 2) € R but (2, 1) € R, and similarly 7 is not symmetry S.O. and 4X A are symmetric. (c) Tis not transitive since (1, 2) and (2, 3) belong to 7, but (1, 3) does not belong to T. The ot four relations are transitive. 2 (@) Sis not antisymmetric since 1 #2, and (1, 2) and (2, 1) both belong to S. Similarly, 4 x4 is antisymmetric. The other three relations are antisymmetric. ‘e Given: 4 = {1, 2, 3, 4}. Consider the following relation in 4: 2417 R={(, 1.22.23) 3.2). 4,24} (a) Draw its directed graph. (b) Is R (i) reflexive, (ii) symmetric, (iii) transitive, or (iv) antisymmetric? (c) Find P=ReR. (i) R is not refiexive because 3 € 4 but 3X3, ie. (3,3) € R. Gi) Ris not symmetric because 4R2 but 2K4, ie. (4,2) < Rbut (2, 4) ¢ R. ii) R is not transitive because 4R2 and 2R3 but 483, i.e. (4, 2) = R and (2, 3) but (4.3) € R. (iv) Ris not antisymmetric because 2R3 and 3R2 but 2 +3. (c) For each pair (a, 6) € R, find all (b,c) € R. Since (a, c) = R°, R= {(1, 1), (2, 2), (2, 3), 3, 2), 3, 3), (4, 2), (4, 3), (4, 49} o Fig. 2.14 Give examples of relations R on 4 = {1, 2, 3} havin, 2 92, g the stated property. (@) Ris both symmetric and antisymmetric. ae iu (b) Ris neither symmetric nor antisymmetric. (©) Ris transitive but R U R™ is not transitive. There are several possible examples for each answer. One possible set of examples follows: (@) R={(,1),(2,2)). (b) R= {C, 2), 2, 1),2,3)}. (©) R={(, 2)}-218 219 2.20 iezal Suppose C is a collection of relations S on a set A and let T be the intersection of the relation S$, that is, T= (S: Se ©). Prove: (a) [every Sis symmetric, then (b) Ifevery Sis Relations me symmetric. transitive, then T is transitive (a) Suppose (a, b) € T. Then (a, b) € $ for every S. $ S. Hence (b, a) € Tand Tis symmetric, (b) Suppose (a, b) and (b, c) belong to 7. Then (a, b) and (b,c) belong to S for every 8 Sis transitive, (a, c) belongs to S for every 5. Hence, (a, ¢) € Tand Tis transiti cach Sis symmetric, (b, a) € S for every ince each Let R be a relation on a set A, and let P be a property of relations, such as, symmetry and transitivity. Then P will be called R-closable if P satisfies the following two conditions: 1. There is a P-relation § containing &. 2. The intersection of P-relations is a P-relation. (a) Show that symmetry and transitivity are R-closable for any relation R, (b) Suppose P is R-closable. Then P(R), the P-closure of R, is the intersection of all P-relations Scontaining R, that is, P(R) = 0 (S: Sis.a P-relation and Rc S) (a) The universal relation A x A is symmetric and transitive and A x A contains any relation Ron. Thus (1) is satisfied. By Problem 2.15, symmetry and transitivity satisfy (2). Thus symme- try and transitivity are R-closable for any relation Let T= A (S: Sis a P-relation and R <5). Since P is R-closable, T is nonempty by (1) and Tis a P-relation by (2). Since each relation $ contains R, the intersection T contains R. Thus, Tis a P-relation containing R. By definition, P(R) is the smallest P-relation containing R; hence PCR) CT. On the other hand, P(R) is one of the sets $ defining 7, that is, P(R) is a P-relation and R & P(R). Therefore, T< P(R). Accordingly, P(R) = T- © Consider a set A = {a, b, c} and the relation R on A defined by R= {(a,a), (4,5) (6.0, (6 0} Find (a) reflexive(R); (b) symmetric(R); and (c) transitive(2). (a) ‘The reflexive closure on R is obtained by adding all diagonal pairs of 4 x A to R which are not currently in R. Hence, reflexive(R) = Ro {(b, b)} = {(a, a), (a, b), (b, b), (6, 0) ( )} (b) The symmetric closure on 2 is obtained by adding all the pairs in R-! to R which are not currently in R. Hence, symmetric(R) = RU {(b, 4), (€, BY} = {Ca as (a 6), (bs )s (bs €)s (Cs Bs (I (c) The transitive closure on R, since A has three elements, is obtained by taking the union of R with R= Ro Rand R?=Re Re KR. Note that R= Ro R= ((a, a), (a, b), (a, €)s (b, €)s (6 €)} R= Re Ro R= {(a, a), (a,b), (A, C)y (6, €), (6 €} Hence transitive(R) = R U R? U R? = {(a, a), (a, b), (a, ©), (b, ©), (¢ D}28 Discrete Mathematics EQUIVALENCE RELATIONS AND PARTITIONS, 2.21 222 Consider the Z of integers and an integer m > 1, We say that x is congruent to y modulo m, written xm y(mod m1) lefines divisible by m. Show that this n equivalence relation on Z, We must show that the relation i reflexive, symmetric, and transitive ex =x (mod m) because x ~ x = 0 is divisible by m. Hence the relation jy (ii) Suppose x = y (mod m), s —y is divisible by m. Then ~ (x ~y) = y=. is also divi ‘mod im). Thus the relation is symmetti Gi) Now suppose x= y (mod m) and y= 2 (mod m), sox ~y and y ~ z are each divisible by m. Then the sum sible by m, x9 (-y)+(y-2)ex-z is also divisible by m; hence x = z (mod m). Thus the relation is transitive. Accordingly, the relation of congruence modulo m on Z in an equivalence relation Let d bea set of nonzero integers and let = be the relation on A x defined by (a,b) = (c,d) whenever ad = be Prove that = is an equivalence relation, ‘We must show that = is reflexive, symmetric, and tra (i) Reflexivity: We have (a, b) = (a, b) since a Gi) Symmetry: Suppose (a, b) = (c,d). Then a Thus, = is symmetric. Gli) Trunsitivig: Suppose (a, b) = (6, d) and (c, d) = (e, f). Then add = he and cf = de. Multiplying Corresponding terms of the equations gives (ad) (cf) = (be) (de). Canceling ¢ # 0 and d #0 from both sides of the equation yields a/= he, and hence (a, b) ~ (e, J). Thus = is transitive, Accord: ingly, = is an equivalence relation, da and hence (c,d) = (a,b) Let R be the following equivalence relation on the set = {1, 2, 3,4, 5, 6}: R ={(1,).(1, 5), 2,2), (2,3), 2, 6), (3,2), G, 3), B, 6), (4, 4), (5, 1), (5,5), (6, 2), (6, 3), (6, 6) Find the partition of 4 induced by R, ic,, find the equivalence classes of R, Those elements related to | are | and 5 hence (= (1,5) We pick an element which does not belong to [1}, nen Say 2. Those elements related to 2 are 2, 3 and 6. [2] = {2, 3, 6} The only element which docs not belong to [1] or [lis 4. The only clemer nt related to 4 is 4. Thus [4] = (4)Accordingly, 11.9), {2,3,6), (4) is the partition of induced by R, 24 Prove Theorem 2.6: Let R be an equivalence relation in a set A. Then the quotient set A/R isa partition of 4. Specifically, (i) ae [a]. for everyae A (i) [a] = [6] ifand only if (a, b) R. (iii) 1f [a] (4), then [a] and [4] are disjoint. Proof of (i): Since R is reflexive, (a, a) € R for every ae A and therefore a € [a]. Proof of (Gi): Suppose (a, b) € R. We want to show that [a] = [b]. Let x € [6]; then (b, x) € R. But by hypothesis (a, b) € R and so, by transitivity, (a, x) € R. Accordingly x € [a]. Thus {6] < [a]. To prove that [a] & [5], we observe that (a, 6) € R implies, by symmetry, that (, a) € R. Then, by a similar argument, we obtain [a] ¢ [5]. Consequently, [a] = [b]. On the other hand, if [a] = [5], then, by (i) b € [6] = [a]; hence (a, b) € R. Proof of (iii): We prove the equivalent contrapositive statement: If[a]O[b]#@ then [a]=[6] If [a] > [6] + @, then there exists an element x € A with x € [a] 0 [6]. Hence (a, x) € Rand (b,x) € R. By symmetry, (x, b) € Rand by transitivity, (a, b) € R. Consequently by (ii), [a] = [d]. 25 Consider the set of words 17'= {sheet, last, sky, wash, wind, sit}. Find J//R where R is the equivalence rela- tion on W defined by either (a) “has the same number of letters as”; (b) “begins with the same letter as”. (a) Those words with the same number of letters belong to the same cell; hence WIR = [{sheet}, (last, wash, wind), {sky, sit}]. (6) Those words beginning with the same letter belong to the same cell; hence WIR = [{sheet, sky, sit}, {last}, {wash, wind}]. PARTIAL ORDERING 26 Let 2 be any collection of sets. Is the relation of set inclusion ¢ a partial order on 2? Yes, since set inclusion is reflexive, antisymmetric, and transitive, That is, for any sets 4, B, Cin ¢ we have: (i) A CA; (ii) if A CB and BCA, then A = B, (iii) if A C Band BCC, then CC. .27 Consider the set Z of integers. Define aRb by b =a’ for some positive integer r. Show that R is a partial order on Z, that is, show that 2 is: (a) reflexive; (b) antisymmetric, (c) transitive. (a) Ris reflexive since a=a'. (b) Suppose aRb and bRa, say b = a” and a = bY, Then a = (a")’ = a’, There are three possibilities: (i) rs = 1, (ii) @ = 1, and (iii) a=— 1. If ry = 1 then = 1 ands = I and soa=b.Ifa=1 then b= /"=1 =a, and, similarly, if b = 1 then a= 1. Lastly, if =— 1 then 1 (since b # 1) and a = b, In all three cases, a = b. Thus 2 is antisymmetric,0 Discrete Mathematics 2.28 2.29 (c) Suppose aRb and bRe are, say, b= a" and c= b*. Then = (a Ris transitive, Accordingly, 2 is a partial order on Z. y' =a" and, therefore, aRe. Hence Let S = {set of all points in a plane} and R be relation on S, such that R = {(a, 4) |b is within one inch distance from a}. Is R equivalence relation? As every a € Sis within one inch distance from itself, R is reflex- d) ive. If a is within one inch distance from b then b is also within 3 \ one inch distance from a, hence R is symmetric and R is not NN antisymmetric. NN my Let a, b, c be three points on the plane as drawn in Fig. 2.12 Letd; and d, be distances between a and b and b and c respectively 3B and both d; and d, be less than or equal to one inch, Note that d NN may or may not be less than one inch, hence R is not transitive. Nt Hence 2 is not equivalence relation. ic Fig. 2.12 Let R be relation of set A of people. & = {(a, b)|a is brother of b}. Is it equivalence? Is R partial ordering? (discard half brother, paternity brother). Here R is not reflexive as no female is said to (a, b) € Rthen (b, a) may not be a member of Ras b could be female in which case b is not brother of a. Ris not antisymmetric as if (a, b) € R and if both a and b are male then both a and b are brothers of cach other. R is transitive. Let us consider that (a, 6) € R and (b, c) € R. Here if (a, b) © Rea has to be male and if (b, c) € R, b has to be male. Hence a and 6 both are male. Now if (a, b) € Rand (b,c) Rihen (a,c) ¢ R, Ris not reflexive, not symmetric, not antisymmetric and is trancitwwe, Hence Ris neither equivalence nor partial ordering. be brother of herself. R is not symmetric as if From following diagraphs, write relation as set of ordered pairs and check for equivalence or part ordering. (a) Here from Fig. 2.13 we get R= {(a, b), (b, a), Ris not reflexive as (b, b) ¢ R Ris not symmetric as (a,c) € Rbut(c, aye R Ris not antisymmetric as (a, b) ¢ R and (b,a)¢ R Ris not transitive as (a,c) € Rand (c,d) € Rbut (a, d) € R. Hence R is neither equivalence nor partial ordering relation. (c, ¢), (c,d), (a,c), (b, d)}Relations (b) Here from Fig. 2.14 we get R= {(@, a), (b, b), (c, €), (a, ©), (¢, b), (b, a)} Ris reflexive. Ris not symmetric, Ris antisymmetric, Ris not transitive as (a, ¢) and (c, b) € R but (a,b) ¢ R. Hence 2 is neither equivalence nor partial ordering relation. Fig. 2.14 2.31 Draw diagraph for relation R on A. (see Fig, 2.15) = A={1,2,3,4, 5, 6, 7,8}. Letx Ry whenever y is divisible by x. Is R equivalence relation? Is R Partial ordering? Ris reflexive, antisymmetric and transitive, hence R is not equivalence, is a partial ordering relation, Fig. 2.45 2.32 Let A be a set books. (a) Let R be a binary relation on A such that(a, b) € Rif book a costs more and contains fewer pages than book b. Is R reflexive? symmetric? antisymmetric? transitive? | No book costs more than itself nor pages fewer than itself, hence R is not reflexive. If (a, b) Rand as R is more than and less to relation (b, a) € R, hence R is not symmetric and is antisymmetric relation and is a transitive relation. R is neither equivalence nor partial ordering relation.[2.32 Discrete Mathematics (b) Let S be a binary relation on A such that (a, 6) € R, if book a costs more or contains fewer pages than b. Is R reflexive? Symmetric? Antisymmetric? Transitive? Note that, R is not reflexive. Let (a, b) € R such that a has cost 100 with 20 pages b costing 200 with 10 pages and C costing 50 with 35 pages. Here we can easily verify that Rig not symmetric. Also & is not antisymmetric nor is transitive. 21 2.2 23 24 25 2.6 27 The binary relation S= $ (empty set) on set 4 = (1, 2, 3} is (a) Neither reflexive nor symmetric (b) Symmetric and reflexive (c) Transitive and reflexive (4) Transitive and symmetric A relation R is defined on the set of integers as xR, iff (x+y) is even. Which of the following statement is TRUE? (a) Ris not an equivalence relation (b) Ris an equivalence relation having one equivalence class (c) Ris an equivalence relation having two equivalence classes (d) Ris an equivalence relation having three equivalence classes ‘The number of binary relations on asset with » elements is (a) ”, (b) 2" (©) 2" (@) none of these Suppose A is a finite set with n elements. The number of elements in the largest equivalence relation of Ais (a) 1 (b) 1 (c) n+] @ The number of equivalence relations of the set {1, 2, 3, 4} is (@) 4 (b) 15 (©) 16 (@) 24 Let R be non-empty relation on a collection of sets defined by ARB if and only if A 7 B= 6. Thea, (pick the TRUE statement) (a) Ris reflexive and transitive (b) Ris symmetric and not transitive (c) Ris an equivalence relation (d) Ris not reflexive and not transitive Let R be a symmetric and transitive relation on a set A, then (a) Ris reflexive and hence an equivalence relation (b) Ris reflexive and hence a partial order (c) Ris not reflexive and hence not an equivalence relation (d) None of theseThe ‘Subset’ relation on (a) A partial ordering (b) An equivalence relation (©) Transitive and symmetric only (@) Transitive and anti-symmetrie only A set of sets is Consider the following relations: R, (a, b) iff (a + 5) is even over the set of integers R; (a, b) iff (a + b) is odd over the set of integers R; (a, b) iff'a - b>0 over the set of non-zero relational numbers. Ry (a, b) iff | ab | <=2 over the set of natural numbers. Which of the following statements is correct? (a) Ry and R; are equivalence relational, Ry and R, are not (b) Ry and R; are equivalence relational, Ry and R, are not (©) Ry and R, are equivalence relational, R, and R, are not (4) Ry, Ry, Ry and R, are all equivalence relational Let Ry and R, be two equivalence relations on a set. Consider the following assertions: i) Ry U Ry is an equivalence relation. Gi) Ry A Ry is an equivalence relation. Which of the following is correct? (a) Both assertions are true (b) Assertion (i) is true but assertion (ii) is not true (©) Assertion (ji) is true but assertion (i) is not true (@) Neither (i) or (ii) is true Bo enacts RELATIONS ) 2A 2.2 23 24 25 Let 17'= {Mare, Erik, Paul} and let = (Erik, David). Find: (a) Wx V; (b) Vx W; (0) Vx V. Let $= {a, b,c}, T= {b, c, d}, and W= {a, d}. Construct the tree diagram of Sx Tx W and then find SxTxW. Find x and y if: (a) (x +2, 4) = (5, 2x +); (b) (7-2, 2+ 1) =(e- 1, y +2). Prove: (a) A x (B.C) = (A XB) 0 (AX C); (b) 4 x (BUC) = (Ax B) U(A XB). Let R be the following relation on 4 = {1, 2,3, 4}: R={(, 3), (1, 4), B, 2), G, 3), B, 4} (a) Find the matrix Mp of R. (b) Find the domain and range of R. (©) Find R*. (d) Draw the directed graph of R. (©) Find the composition relation Ro R. Let R and S be the following relations on B = {a, b, c, d}. R= {(a, a), (a,c), (¢, b), (6, d), @, b)} and S= {(b, a), (c, ¢), (c,d), (d, a)} Find the following composition relations: (a) Ro S; (b) S'° R; (c) Re R; (d) SoS.2.34 Discrete Mathematics 2.7. Let R be the relation on the positive integers N defined by the equation x + 3y = 12; that is, R= {(x,):x43y= 12) (a) Write Ras a set of ordered pairs. (b) Find: (i) domain of R, (ii) range of R, and (iii) R"!, (c) Find the composition relation R © R. PROPERTIES OF RELATIONS 2.8 _ Each of the following defines a relation on the positive integers N: 1, “vis greater than y". 2. “xy is the square of an integer”. 3. 10. 4. x+4y=10. Determine which relations are (a) reflexive; (b) symmetric, (c) antisymmetric, (d) transitive, 2.9 Let R and S be relations on a set A. Assuming A has at least three elements, state whethe each of the following statements is true or false. If it is false, give a counterexample on the se A={1,2,3}: (a) If Rand S are symmetric then RS is symmetric. (b) If Rand S are symmetric then R U Sis symmetric. (c) If Rand S are reflexive then R A Sis reflexive. (d) If Rand S are reflexive then R U Sis reflexive. (e) If R and S are transitive then R U S is transitive. (f) If R and S are antisymmetric then R U Sis antisymmetric. (g) IfR is antisymmetric, then R™ is antisymmetric. (h) IF R is reflexive then R 7 Ris not empty. (i) If R is symmetric then R A RT is not empty. 2.10 Suppose R and S are relations on a set A and R is antisymmetric. Prove that RN Sis antisymmetric. EQUIVALENCE RELATIONS 2.11. Prove that if R is an equivalence relation on a set A, then R is also an equivalence relation on 4 242 Let $= {1, 2,3, 19, 20}. Let R be the equivalence relation on S defined by x = y (mod 5), that x—y is divisible by 5. Find the partition of 5 induced by R, i.e., the quotient set S/R. 2.13 Let A= {1, 2, 3,..., 9} and let ~ be the relation on A x A defined by (a,b)~(c,d) if atd=bt+e (a) Prove that ~ is an equivalence relation. (b) Find [(2, 5)], i. the equivalence class of (2, 5).—————— Relations [235] ——felations eo) ko NADA aretha 21 @ ioe fe 2.3. (6) 24 (d) 2.5 (b) 26 (b) “7 (d) 2.8 (a) 2.9 (b) 2.10 (c) PVors hh una beni gl atest ty 21 (a) Wx V= {(Mare, Erik), (Mare, (0) Vx W= (Erik, Mare), (D; (©) VX V={(Erik, Erik), ©, David), (Erik, Erik), (Erik, David), (Paul, Erik), (Paul, David)}. avid, Mare), (Erik, Erik), (David, Erik), (Erik, Paul), (David, Paul)}- (Erik, David), (David, Erik), (David, David)}. 2.2, The tree diagram of $x Tx I is shown in Fi, ig. 2.16. The set Sx Tx Wis equal to {(@, b, a), (a, b, d), (a, ¢,a), (a, ¢, 4), (a, d, a), (a, d, d), (6, b, a), (b, b, d), (b, ¢, a), (b, 6, d), (6, d, a), (b, d, d), (c, b, a), (6, B, d), (c,c, 4), (6, 6, 4), (6, d, a), (c,d, d)} a a os ai bm b os It ot a ot Is Fig. 2.16 23 (b) x=2,y=3. 25 (a) My= 00 00 ol 00 ono 1 0 1 036 | (by n= {1,3}, range = {2.3.4}. G) (2) te) GoD. LD, 2.3), G3) (4, 3} (dd) See Vig. 2.17 @ = 1, 2). 1, 3). 1. AD, (3, 2B, 3), BA} (ao) (a), (ea), (da). GY (3) 2.6 (a) Ub) So R= {bad (He CD) (6, (dO (O}- Ce) Re R= Ha. ade (a PCa eds (a, OD, (6 DY (@) SoS =e ca (ed. Fig, 2.17 2.7 (a) (9,1). (6,2), 3, 3)} (b) (19.6.3). Gi) {1.2.3}, GHD (CL, 9), 2, 6), B, 3)} (ce) {G30} 2.8 (a) None: (b) (2)and GB); (©) (1) and ;__ (A) all except 3). 2.9 Allare true except (c) R= {(1, 2)}. = (C2, 3)} and (R= {(, 2)}, S= (2, V} DAZ [{1.6. 11, 16}. (2.7, 12, 17}, (3,8, 13, 18}, (4,9, 14, 19}, (5, 10, 15, 203] DAB (b) (1.4). (2. 5), (3, 6), (4, 7s (5, 8), (6 9}