Pointwise and global sums and negatives of binary relations

An. S¸ . Uni . O idius Cons an ¸a Vol. 10(1), 2002,87–94 POINTWISE AND GLOBAL SUMS AND NEGATIVES OF BINARY RELATIONS Tam´as Gla osi s and ´ A p´ad Sz´az Abs ac Fo any wo ela ions Fand Gon one g oupoid X o ano he Y, we de ine ( F+G)(x) = F(x) + G(x) o all x∈Xand F⊕G=  (x+z, y +w) : (x, y)∈F , (z, w)∈G  . Mo eo e , i in pa icula Xand Ya e g oups, hen we may also na u ally de ine ( −F)(x) = −F(x) o all x∈Xand ªF=  (−x , −y) : (x, y)∈F  . By using hese de ini ions, we p o e some basic heo ems abou he images o subse s o Xunde he ela ions −F,ªF,F+Gand F⊕G. In pa icula , we show ha (F⊕G)(x) = [ x=u+  F(u) + G( )  o all x∈X. The e o e, in con as o he in e sec ion con olu ion [1] , he union con olu ion o ela ions need no be in oduced. Mo eo e , i is also wo h men ioning ha he esul s ob ained can, o ins ance, be applied o ansla ion and addi i e ela ions [2] . 1 A ew basic ac s on ela ions and g oupoids A subse Fo a p oduc se X×Yis called a ela ion on X o Y. In pa icula , he ela ions ∆X={(x, x ) : x∈X}and X2=X×Xa e called he iden i y and uni e sal ela ions on X, espec i ely. Namely, i in pa icula F⊂X2, hen we may simply say ha Fis a ela ion on X. No e ha i Fis a ela ion on X o Y, hen Fis also 87 88 T. Gla osi s and ´ A. Sz´ az a ela ion on X∪Y. The e o e, i is equen ly no a se e e es ic ion o assume ha X=Y. I Fis a ela ion on X o Y, hen o any x∈Xand A⊂X he se s F(x) = {y∈Y: ( x, y )∈F}and F[A] = Sx∈AF(x) a e called he images o xand Aunde F, espec i ely. Whene e A∈Xseems unlikely, we may w i e F(A) in place o F[A] . I Fis a ela ion on X o Y, hen he alues F(x) , whe e x∈X, uniquely de e mine Fsince F=Sx∈X{x}×F(x) . The e o e, he in e se F−1o Fcan, o ins ance, be de ined such ha F−1(y) =©x∈X:y∈ F(x)ª o all y∈Y. I Fis a ela ion on X o Y, hen he se s DF=F−1(X) and RF= F(X) a e called he domain and ange o F, espec i ely. I in pa icula X=DF(and Y=RF) , hen we say ha Fis a ela ion o Xin o (on o) Y. A ela ion Fon X o Yis called a unc ion i o each x∈DF he e exis s y∈Ysuch ha F(x) = {y}. In his case, by iden i ying single ons wi h hei elemen s, we usually w i e F(x) = yin place o F(x) = {y}. I Xis non oid se and + is a unc ion o X2in o X, hen he o de ed pai X(+) = ( X, + ) is called a g oupoid. In his case, we may also na u ally w i e x+y= + ( x, y ) o all x, y ∈X. Mo eo e , i Xis a g oupoid, hen we may also na u ally w i e A+B= ©x+y:x∈A , y ∈Bª o all A , B ⊂X. Thus, he amily P(X) o all subse s o Xis also a g oupoid. No e ha i Xis, in pa icula , a g oup, hen P(X) is, in gene al, only a semig oup wi h ze o elemen {0}. Howe e , we can s ill na u ally use he no a ions −A={ − x:x∈Aªand A−B=A+ ( −B) . 2 Poin wise and global sums and nega i es o ela ions De ini ion 2.1 I Fand Ga e ela ions on a se X o g oupoid Yand F+Gis he ela ion on X o Ysuch ha (F+G)(x) = F(x) + G(x) o all x∈X, hen F+Gis called he poin wise sum o Fand G. While, i Fand Ga e ela ions on one g oupoid X o ano he Yand F⊕G=©(x+z, y +w) : (x, y)∈F , (z, w)∈Gª, hen he ela ion F⊕Gis called he global sum o Fand G. Poin wise and global sums and nega i es o bina y ela ions 89 Rema k 2.2 Thus, we ha e DF+G=DF∩DGand DF⊕G=DF+DG. The global sum F⊕Gis, in gene al, qui e di e en om he poin wise one F+Ge en i DF+G=DF⊕G. Example 2.3 I Xis a g oupoid, hen (1) ∆X+ ∆X= ∆Xi and only i x=x+x o all x∈X; (2) ∆X⊕∆X= ∆Xi and only i o each x∈X he e exis u , ∈X such ha x=u+ . The e o e, i in pa icula Xis a g oup, hen ∆X⊕∆X= ∆X, bu ∆X+ ∆X= ∆Xi and only i X={0}. Howe e , in some e y pa icula cases, he global sum o ela ions may coincide wi h he poin wise one. Example 2.4 Le Xbe a non oid se , and o all x, y ∈Xde ine x+y= x. Then Xis a semig oup such ha , o any wo ela ions Fand Gon X, we ha e F⊕G=Fwhene e G6=∅, and F+G=Fwhene e G(x)6=∅ o all x∈DF. Analogously o De ini ion 2.1, we may also na u ally in oduce he ollow- ing De ini ion 2.5 I Fis a ela ion on a se X o g oup Yand −Fis he ela ion on X o Ysuch ha (−F)(x) = −F(x) o all x∈X, hen −Fis called he poin wise nega i e o F. While, i Fis a ela ion on one g oup X o ano he Yand ªF=©(−x , −y) : (x, y)∈Fª, hen he ela ion ªFis called he global nega i e o F. Rema k 2.6 Thus, we ha e D−F=DFand DªF=−DF. The global nega i e ªFis, in gene al, also qui e di e en om he poin - wise one −Fe en i DªF=D−F. 90 T. Gla osi s and ´ A. Sz´ az Example 2.7 I Xis a g oup, hen ª∆X= ∆X, bu −∆X= ∆Xi and only i −x=x o all x∈X. Howe e , in some e y pa icula cases, he global nega i e o a ela ion may coincide wi h he poin wise one. Example 2.8 I Xis a g oup such ha −x=x o all x∈X, hen −F=Fand ªF=F o any ela ion Fon X. Conce ning he images o se s unde he ela ions −F,ªF,F+Gand F⊕G, we can easily p o e he ollowing heo ems. Theo em 2.9 I Fis a ela ion on a se X o a g oup Y, hen (−F)(A) = −F(A) o all A⊂X. Theo em 2.10 I Fis a ela ion on one g oup X o ano he Y, hen (ªF)(A) = −F(−A) o all A⊂X. P oo . I y∈(ªF)(A) , hen he e exis s x∈Asuch ha y∈ (ªF)(x) , and hus ( x, y )∈ ªF. Hence, i ollows ha ( −x, −y)∈F, and hus −y∈F(−x) . Thus, since F(−x)⊂F(−A) , we also ha e y∈ −F(−A) . The e o e, ( ªF)(A)⊂ − F(−A) . Now, by w i ing ªFin place o Fand −Ain place A, we can also see ha F(−A) = ¡ª(ªF)¢(−A)⊂ − (ªF)¡−(−A)¢=−(ªF) (A), and hus −F(−A)⊂(ªF)(A) is also ue. ¤ Co olla y 2.11 I Fis a ela ion on one g oup X o ano he Y, hen (1) ªF=Fi and only i F(−x) = −F(x) o all x∈X; (2) ªF=−Fi and only i F(−x) = F(x) o all x∈X. Theo em 2.12 I Fand Ga e ela ions on a se X o g oupoid Y, hen (F+G)(A)⊂F(A) + G(A) o all A⊂X. Poin wise and global sums and nega i es o bina y ela ions 91 Theo em 2.13 I Fand Ga e ela ions on one g oupoid X o ano he Y, hen F(A) + G(B)⊂(F⊕G)( A+B) o all A , B ⊂X. P oo I w∈F(A) + G(B) , hen he e exis y∈F(A) and z∈G(B) such ha w=y+z. Mo eo e , he e exis a∈Aand b∈Bsuch ha y∈F(a) and z∈G(b) , and hus ( a, y )∈Fand ( b, z )∈G. Hence, i ollows ha ( a+b , w ) = ( a+b , y +z)∈F⊕G, and hus w∈(F⊕G)( a+b) . Thus, since ( F⊕G)( a+b)⊂(F⊕G)( A+B) , we also ha e w∈(F⊕G)( A+B) . ¤ Co olla y 2.14 I Fand Ga e ela ions on one g oupoid X o ano he Y, and Ais a subg oupoid o X, hen F(A) + G(A)⊂(F⊕G)(A). 3 Some u he esul s on he global sums o ela ions Theo em 3.1 I Fand Ga e ela ions on one g oupoid X o ano he Y, hen (F⊕G)(A) = [ u+ ∈A ¡F(u) + G( )¢ o all A⊂X. P oo I y∈(F⊕G)(A) , hen he e exis s x∈Asuch ha y∈ (F⊕G)(x) , and hence ( x , y )∈F⊕G. The e o e, he e exis ( u , z )∈F and ( , w )∈Gsuch ha ( x , y ) = ( u+ , z +w) . Hence, i ollows ha z∈F(u) and w∈G( ) , and mo eo e x=u+ and y=z+w. The e o e, y∈F(u) + G( ) , and hence y∈Sx=u+ ¡F(u) + G( )¢⊂ Su+ ∈A¡F(u) + G( )¢. While, i y∈Su+ ∈A¡F(u) + G( )¢, hen he e exis u , ∈X, wi h x=u+ ∈A, such ha y∈F(u)+G( ) . The e o e, he e exis z∈F(u) and w∈G( ) such ha y=z+w. Hence, i is clea ha ( u , z )∈Fand ( , w )∈Gsuch ha ( x , y ) = ( u+ , z+w) . The e o e, ( x , y )∈F⊕G, and hence y∈(F⊕G)(x)⊂(F⊕G)(A) . ¤ Rema k 3.2 The A={x}pa icula case o he abo e heo em shows ha , in con as o he in e sec ion con olu ion (F∗G)(x) = x=u+ ¡F(u) + G( )¢, 92 T. Gla osi s and ´ A. Sz´ az he union con olu ion o ela ions no be in oduced since i coincides wi h he global sum. Now, as a use ul consequence o Theo em 3.1, we can also p o e Co olla y 3.3 I Fand Ga e ela ions on one g oup X o a g oupoid Y, hen (F⊕G)(A) = [ ∈X ¡F(A− ) + G( )¢ o all A⊂X. P oo I y∈(F⊕G)(A) , hen by Theo em 3.1 y∈Su+ ∈A¡F(u) + G( )¢. The e o e, he e exis u , ∈X, wi h x=u+ ∈A, such ha y∈F(u) + G( ) . Hence, i ollows ha y∈F(x− ) + G( )⊂ F(A− ) + G( ) , and hus y∈S ∈X¡F(A− ) + G( )¢. While, i y∈S ∈X¡F(A− ) + G( )¢, hen he e exis s ∈X such ha y∈F(A− ) + G( ) . The e o e, he e exis s x∈Asuch ha y∈F(x− ) + G( ) . Hence, by de ining u=x− , we can see ha u∈Xsuch ha x=u+ and y∈F(u) + G( )¢. The e o e, y∈ Sx=u+ ¡F(u) + G( )¢⊂Su+ ∈A¡F(u) + G( )¢, and hence by Theo em 3.1 y∈(F⊕G)(A) . ¤ Mo eo e , as a simple e o mula ion o he abo e co olla y we can also s a e Co olla y 3.4 I Fand Ga e ela ions on one g oup X o a g oupoid Y, hen (F⊕G) (A) = [ u∈X ¡F(u) + G(−u+A)¢ o all A⊂X. P oo I y∈(F⊕G)(A) , hen by Co olla y 3.3 y∈S ∈X¡F(A− )+G( )¢. The e o e, he e exis s ∈Xsuch ha y∈F(A− )+G( ) . Thus, he e exis s x∈Asuch ha y∈F(x− ) + G( ) . Now, by de ining u=x− , we can see ha y∈F(u) + G(−u+x)⊂F(u) + G(−u+A) . The e o e, y∈Su∈X¡F(u) + G(−u+A)¢. While, i y∈Su∈X¡F(u) + G(−u+A)¢, hen he e exis s u∈X such ha y∈F(u) + G(−u+A) . The e o e, he e exis s x∈Asuch ha y∈F(u) + G(−u+x) . Now, by de ining =−u+x, we can see ha y∈F(x− ) + G( )⊂F(A− ) + G( ) . The e o e, y∈S ∈X¡F(A− ) + G( )¢, and hence by Co olla y 3.3 y∈(F⊕G)(A) . ¤ Poin wise and global sums and nega i es o bina y ela ions 93 Rema k 3.5 Now, by using he p eceding esul s, one can also easily es ablish some p ope ies o he images o se s unde he ela ions F−G=F+ ( −G)and FªG=F⊕(ªG). Re e ences [1] ´ A. Sz´az, The in e sec ion con olu ion o ela ions and he Hahn–Banach ype heo ems, Ann. Polon. Ma h. 69 (1998), 235–249 [2] ´ A. Sz´az, T ansla ion ela ions, he building bloks o compa ible ela o s, Ma h. Mon is- nig i, o appea Ins i u e o Ma hema ics and In o ma ics, Uni e si y o Deb ecen, H-4010 Deb ecen, P . 12, Hunga y 94 T. Gla osi s and ´ A. Sz´ az