RELATIONS — 7% & FUNCTIONS 2-4 Relations. _ ACbinary) relation between two sets Sand T /s a subset of SxT provided Shat coordi-~ nates of its elements satisfy cer/ain condition. This R is a relation from § to T, if RE S*T, and if the components of fhe ordered pairs belonging to R satisfy certain conditions. If §=T, wesay _ that R is a relation onS. We write Ry if Guy) €R and Say That “x is R-velated toy? or that “y is a R-relative of x” We shalt write x(YR) y if x és mot R- related fy. The set S on which a relation is defined is called its Support. ' SAPS consists of 7 elements and Tconsists of 'n elements, Jhen Sx*T consists of mn elements : Thee ry "refers lo The pairs — (xy) because it is 2 Wider Schon elements (bi aaeet lane Oe : BE on ae ——T6. teachers of He same shoot. ia we a natural yetation “x fsa student a x a xis one of He Siudents oe oe oe | ‘Set $). 2 Is clear “hat far one 3: 1 for different Student x, this telatian may Fo a teachers. euneely one and e a has different students. (2) Let S be He set of att people. Then R: is a brother of y” 7s a velation 077 S. That is, XES, yES, (x, VIER CSAS. (3) Let 5 ={4,2,35, Then SxS=1C,1),G,2),4,5),(B),(22),(2,3),6 (3,2), (3,3)5. Let R=1Gqy): xES, yes, xLy |. Then - R= i,2),4,3), 2,35 C SS, / a telaiion an S. (4y Let $= {4,2,3} and T= {x,y } Then R= i(4,x), C4, Fis) fon St s 7)4, y),(5 2) F (s a velati . ole: 1Rz, 20.R)e, SRe, 3ar The concept of a binary aes os paced to that of n-aty relation on a set S zie can tatk of He Subsets of Zhe m-fold Product SxSx---x5=S ofS wwipy itsele ‘ Example: a the set of poi; i telalion nts cn ele of “ betneeness”c the set og ‘mentary geomelsy j: = rere relation Than an " && Domain ana aa a Tf Ris a vetation fy oMge OF a “set enine derdiom doer Git Sit3t or left) coordinatese fs Me reine Tange Of R és met Tight) coordinates ona7 THUS Dom R= {xt Cxsy)€ R, for same ye THs Ran R=f y:( %y)E R, for some 2€S $+ amples:(1) Let S be He set of ak mer fiv- ing ” a tattgin. locatity of Hyderabad and T be the set of all women én ke same locality. _ Then the siatemeni “ x 5 a husbared OF ¥3 where x€S and ye ete yetation from ST If we denote. Mis relation by R, rer R will be Ae Set of all ordesed pairs in athich the first coordinate is a man, who ts he husband of he Second coordinate which 1s awoman, ¥ Evidently R ts a subset of SxT. Here He domain af Rts fhe set of all Aushands and the ue of R ts fhe set of alt wives tiving iv that locatity. . > Note: The relation is the set R (wiih Hie con- dition, the phrase“ is a husband of”) and~ not he phrase alone. * (2) Let § = £4,2,34Y and T=10;b,ct and the relation > R= t@,a),4,a), G0): Then the. domain of R is the set t2,45 and. 1 rey Riste sel fasch Care ee = 25° The Identity Relation: Let's beany &. Then a relation ps 5 is called ae taeniily diagonal) relation wher (aye E guy. oe i 5 =a Then * : 2) Nieleradibo hs relation. _ ne ate eee 24 The Inverse Relation. = pl ers eli, a pear OnMeR te bbs > ellsTce th at fhe domain R Us the domain of R™* an in oR G te yange okt iegnte then Rand R gic ee Ceci ye T, ES, G4YER is ic the sel of Exampleslet R be Me relation o7 s real pexatbers defined by “ x is aa aah 3 Xyy being real numbers? Ther one Telation eee by “ ais grealer Hany; %y ing veal numbers” me a) Let $=14,2,33 and T= {a,b}. Then R={(1,a),(4,b), (3,a)} is a relation ‘Tom Sto T: . ie inverse relation of R is R* = t (a,4), Cb, 4), Ca,3) F. 2-5 The Composition Relation. Let Ra bea relation froma set At a set B and Rz be he relation from Bf C; ken she composition Telation or the product of Mhe teio yelations R, _ That (xy)e Rt and (y,2z)€ R2.In Particular, if A=B=C=5, say, then Ru. relationson Ye Same set ee eBid Re Rgare . Examples: (4) Let sb , . fuer n Hyderabad, Lan be ghee ea 2 ee wile pte Festi bape Falke A” both dofineg OR ONG and the Sa oper | Accoreling ts ouy Left nition + teat © Of Z" In other words “xis 2. a faiher "Thal 13, * x¢ & lhe om, FEOF 2's Step. mother of gi? © ee ar ae "gol Let 5 be the same (x, 2)€ Ry had 4o . ie In fis sec~ 2-9 Properties of a Relation re Sea. tion wie deal wilh sonre prope’ set S ts vii Y a A) Reflexivity. Aretation Ron ; Said 70 ri wen “px RYH €5, Matis, i KIER WES. ‘ : * lat T yetation Ronee Bet.S18 Teheenme i identity relation E 4 ht tion “ta be of thes E: tes: (4) Let R be a rela oo define The sot § of all people. 7#e7 age of” defined on Ris reflexive. ca) Let $2 44;2,35. Then, i Re {c4,13, (2,2), 205 /s reflexive. Mt cviangles 272A x is Simitar fo y, every tyiazgle cB) Let S be He Set of a plane. Then /he relation R“ ES; YES” Us reflexive, since is sumilar to déself. (2) Symmetry: A relation Ron aset S és Said lobe symmetric if (x,y) ER? Gy xJER, that is x Ry =) yRx. Evidently R is Sy7ze- tric if Rt2R, . Examples: () Let R be the relation “to b relative of ” on the sets oa R is Symmetric. ° ee ae _, A) Let L be He setofall straight fy; te 4 plane, Then. Re §lasy)s2 is ears ar my, xELyeL } és Symmelvie. Pease °"CB) Let $={fa,b}, Then ; R=fCa,a’ 3 . reflexive a5 nell ds sy poe eb) is _ @) ransitivity : A yela?y, a said % be ‘ramdioe pater B — set Sis nad YRZ= xRz, is, Tat ; RORE Kime RistranAL caution: If 2 relation R is transitive Then x Ry and yRz must émply RZ, even whem 7% =F- Examples: d) Let S=i a,b,c 5..7%en : R=. £Ca,2),(b,b), (a,b), (b,a) 5 £5 symmetric as well as (vansitive but rot refexive (hy Let Rbe a relation in real numbers defined by “ x is bess Than y®. Then ROS transitive. (3) Let A= { Roohi,Habib, Taha }. 7#er the relation R=“to be abramer of nadefined on A ts atvansitive retation. * G) Anti-Symmetry. Aretation Ron a set Sis said to be anti-symmetric if x Ry and yRxax-y Evidently, a relation R on a set Sis anti-symmeitic if RMR*GE, where E denotes “re identity relation on S, Examples (4) Division «7 fhe set ural numbers /s anti symmetric. (2) Let Abe a family of sets and R be fhe velation in A defimed by “S 16 a subset of T.” Zhen Ris anti-symmetric, Since S&T and TESS=T. 4 2:10 Equivalence Relation. Ayelation Rona Set.S (s.called an equivalence-relation if itis reflexive, symmetric and transitive . . Examples:(1) Let'S be she set of alt triangles ina plane. Then R= t(xsy): x is equal in a ei Ys % YES bis reflexive, symmetric and prmuene frat is, it is anveguivalence relation N of nat- (2) Let L be the set of all lines én a pli The s plane. Then R=i¢x,y): x és parallel toy; xEL,yEL} _ 18 an eqivalence relation on L.» Classes which evidently form ruduall Note: Co] = pay? 742.459, 2. + and soon. rye b= Ctbl=” Med “i. "is said to be congruent a . Then an inte (3) Lee S21, the set apa cr ise i write ab Cred > sible by m. Sy mbolicatly Pe : is an equivatence. réla: : e Sat (4) The “equality” relation . ae S=fxyz J is an equivalence rela > (a) x=x. ey =) =m (Symme +e © seeped y2u=p meh biesabiees mee (5) Let A be He set of all automobiles on a University campus parking bot ata given mom. ent. Then she vebation Rix és the Same make as y, xEA, YEA’, is an equivalence relation on A. &-4t Equivalence Classes, Let S be a Ton. empty set and let R be an equivalence relation on S. Leta be an arhitary element of 5. The elements xE5 Satisfying a Rx constitute a Subset Sa of 5, called an equivalence class ofS Valence class is denoted by Sa or by @ oy b Cal. Thus La} = 12:2ES and ahx bE : Examptes:.4) Let § be the set of alt i any Particulay School. The School ieee Subsets. Yasfeint Sb) Let R be oe uiva le: i : Congment oy wee S, ree ae pnts Sater Classes are: : * Then the = Co} 9715. =40 —. 5,-10,-5 0, a7 14-9, i, p 8; 40, 45, hy ee eee ey 2. Us §p Th eB i ; =[e]=[44 Cfuivalence ane there are Onby five yi? : 8S. The Follauis,¥ Se alistinct : ~ 9 Lacks are -- 43 jmportare 10 mote. iP The union of These five non-empky classes I, fhe set of all categers. i = (2d Integers in aon class Aave fhe relation R with one anashey. ) Integers cn alifferent classes da nae ave the relation R wih one another. i i. (A) The classes are rnutually atrsjoint or identical. 2-42 Partitions: Let S bea nonempty set- Then a partition (or adecamposition) of Ss 4 collection of non-empty disjaint subsets of S whose union ts S. S:be the set of atl pupils who alendseco- Extroipte ndary schoobs in. Karachi. Then ste set Scan be tit up into the mutually cisgornt subsets, of which pupits of one and Me same school form one class, (dividing Me pupils according asthools), whose union-(s the set S. (2) Anahher partition on fhe same set 5 as above 03 by Me sets of pupils of one and the Same year tx different schaals forming the mutually disjoint subset s of S wilh § as Steir union. zh. PROBLEM: SET -4. LI f each of the follouing are relations on the Set of all people now tevings then en each case test wheter it satis fies reflexive, symmetric oy : wee Ploperzyes ot pat. 5 * a)" ds an ancester of” (b)“ is smarter . ‘ds er of Than’ (ais the same sex. as”. (d) "sits next eo” a i 4 neighbourer of” (f) “és a sister of ? s aves” ' ay (oseighs at leashas mauchast4> “ an — sith” {K) is the wife of® ee i ife of? hag :a, ing relations [AG ify the properties of olla al ‘ 2. Bie neg so imenin Pakistan TEE bhckece fon the sebof a OT A pakiston (b)*is she mother of “on the se eon Me set of all (c) “has Me same birt marelh’ apa) ie re sludents of m meahhemalicg, Galhematics Cig (d) “Sits in ihe sarhe pnsl rned 072 The 3. Let the follawing relajions bs ine ae Power Se? PCS) of a Sez S. Name ape) of each of He following relations: MC, bi, tcx=, td) $* 4. Identify /te properties of each of te follay- inylalons ae we defined on The set =14,2,33. (art(42¥, 2,3), (4,3), ,0}- tb) 14), (2,2); (63)5(Zo3)} , (co) $C4,4)F (dy 1452), (249,454), (252) }. (). : fr 1 Benen, (2:2)5(8,3)} - 9) 7(4,1),(2,5), 554),(252)5C4,2), 3 (hr) 252),3,0), (4,3) p23.) } Gi) T2)F- G) 1,273, fn) £4,3)s(3,5) }. am 1€2,2)5(2,5)$. (m) L223, 2), S. If A=$4,2,3,43 " Cath Of the followin rel dind etter PAG ii ve Gi) y eemelite sii an sine + xive, (©) CL adrig} tb) $4.26 Cyy} i Gaaee ieee, (9) 120.3), cay Caco F ainatsane vive Rekarions element in A is eset Lis san to be reffesive iF © ‘aa tor every a © A, 3.4) eer rr ADD, 4, 4) is a reflexive: oe whereas ra = 12. Ds 2D, (3, 4) is not a reflexive relation i) Srmmetrie Relations ‘A relation r is said to be symmetric it ath» ra (a all. a,b & A. For example, it : A= (29) then on and r= (02, QD, a), GDP 11 is also reflexive whereas r2 is not reflexive fh implies Ma) for + (1. Ds 2, 2 G3} f are symmetric relation Gi) antisymmetric Relations . A relation r on a set al is said to be antisymmetric if (a, 6) & rand (b, a) Er implies a= b fora, bE AL « a (1208, 4), then + (1, 3), 4, 2, G4) 4 DP G3, 4) Grand (4, 3) Er, but 3 4 4 isnot an antisymmetric relation sin iv) Transitive Relations A relation ron a set A is said to be transitive if and only if 4% and be implies ae, ie., ab, bic = ave, where a,b, CEA. For example, the relations ‘is less ghan’ and ‘is greater than’ are transiti = relations. 9) Equivatence Relations i es which is reflexive, symmetric and transitive is called an equi (i) Partial Order Relations A relation which is reflexive antisymmetric and transitive is called « aertiet cei relation. For example, the relation ‘x divides y" on NV isa Partial oder relation. 4.2.3 Solved Examples Example 1, ip As t0,b, ci} and 8 w (waa 2), Ma ys (ay 2), (e, (4,99) isa relation trom et to B,whereas (a, »), (b, »), ( .(2.d)) and {4.8.6.9 are not relations Example 2. Find the domain and Fange of each of the follo () (3, (1, 1, (1,09, ¢ OF 9. (—1, 0. 0, 0), (1, 0), 2, 0. (a) Domain ~ {_3, ~'13), Range = 40, 1). (©) Domain = (—2, _ | 9, 1,2}, Range = (0), Example 3, Eight articles are Purchased. The first two articles cost Rs 10)- each and the price, because of discounts, decreases Re 1 with each additional article purchased, Determine the relation of articles to Price Let the set of 8 articles be denoted by 4 > (a1, a2, 03, a4, a5, a6, 41, as}. Also let the set of Prices be denoted by P where R= (10, 99859 615 4), In r, We see that two elements of the domain are related to the same element of the range, Viz, (a1, 10) and (az, 9). Hence the relation may be described lows: : ra) = 10 for i= 1,2 BCG) S10 aes ae ce T= 3.48, Example 4. The relation from N + y is given as follows: 7 =12,9,G, 4), 4,5), (5,6), Find r=, The corresponding ordered pairs of are 3,2), (4, 3), (5, 4), (6, 5. Hence rt = (3, 2), 4, 3), (5, 4), (6, 5). 5. Given a = (1, 2,3, 4) find a relation which ig e) symmetric and transitive, antisymmetric imateo (1, D, 2, 2, 8,34. 4,0, DF is reflexive, antisymmetric and transitive. (c) The relation n= (0.2), DE is symmetric but neither transitive nor reflexive since (I, 1) & + Example 6. Check the following relations, R and P, for refle symmetricity and transitivity: (i) a, ifand only if b is divisible by a where @ and b are naturit numbers. : 8, if and only if is perpendicular to 8 where x and ? are si lines in a plane. Ti (i) R is reflexive since a is divisible by a. It is antisymmetric sinc: not divisible by a. It is, however, transitive since a/b and b/c implies a/c is perpendicular to 8. Hence P is not reflexive since a line cannot be perpendicular to itsel Since 8 is perpendicular to +, it follows that P is symmetric. and 8 | ¥ does not imply that x |. ¥. Hence P is not transitive EXERCISES 4.2 IA = {a,b, c,d) and B = {x,y,z}, which of the followin relations from B to A (Exs. 1-5)? 1. (@, 2), @ 9), ad}. (G, a), GB), G0, (@, dh . (0x, b), On). (c, 2), (@, 9). 1), (=, BI}. Give the domain and range of the following relations (Exs. 6-!): {0.5 (—3, 2}, (1, 0, (1, 2), B, 4), (5, 6), - -}. (1,1), 2, 9, GD 4D, de (C1, 5), (4, 5), 1, 4), 4, 6), (3, 2s (7, 60}. IfA = (1, 2, 3}, state whether the following relations in 4 sve reflexive (Exs. 9-1 9% r= ((1, 2), (3,2) (2, 2), (2, 3D). 10. r = ((1, 2), (2, 3), 1, Mr = ((1, 1), 2, 2), 3, 3), (2, 3), B, 2). 12, If A = (1, 2, 3), is the relation given by 1 = (0, D, 2 0, 2,2), G, 2) 2, 3)}