Pointwise and global sums and negatives of binary relations

An. S¸t. Univ. Ovidius Constant¸a Vol. 10(1), 2002,87–94 POINTWISE AND GLOBAL SUMS AND NEGATIVES OF BINARY RELATIONS Tam´as Glavosits and ´ Arp´ad Sz´az Abstract For any two relations Fand Gon one groupoid Xto another Y, we define ( F+G)(x) = F(x) + G(x) for all x∈Xand F⊕G=  (x+z, y +w) : (x, y)∈F , (z, w)∈G  . Moreover, if in particular Xand Yare groups, then we may also naturally define ( −F)(x) = −F(x) for all x∈Xand ªF=  (−x , −y) : (x, y)∈F  . By using these definitions, we prove some basic theorems about the images of subsets of Xunder the relations −F,ªF,F+Gand F⊕G. In particular, we show that (F⊕G)(x) = [ x=u+v  F(u) + G(v)  for all x∈X. Therefore, in contrast to the intersection convolution [1] , the union convolution of relations need not be introduced. Moreover, it is also worth mentioning that the results obtained can, for instance, be applied to translation and additive relations [2] . 1 A few basic facts on relations and groupoids A subset Fof a product set X×Yis called a relation on Xto Y. In particular, the relations ∆X={(x, x ) : x∈X}and X2=X×Xare called the identity and universal relations on X, respectively. Namely, if in particular F⊂X2, then we may simply say that Fis a relation on X. Note that if Fis a relation on Xto Y, then Fis also 87 88 T. Glavosits and ´ A. Sz´ az a relation on X∪Y. Therefore, it is frequently not a severe restriction to assume that X=Y. If Fis a relation on Xto Y, then for any x∈Xand A⊂Xthe sets F(x) = {y∈Y: ( x, y )∈F}and F[A] = Sx∈AF(x) are called the images of xand Aunder F, respectively. Whenever A∈Xseems unlikely, we may write F(A) in place of F[A] . If Fis a relation on Xto Y, then the values F(x) , where x∈X, uniquely determine Fsince F=Sx∈X{x}×F(x) . Therefore, the inverse F−1of Fcan, for instance, be defined such that F−1(y) =©x∈X:y∈ F(x)ªfor all y∈Y. If Fis a relation on Xto Y, then the sets DF=F−1(X) and RF= F(X) are called the domain and range of F, respectively. If in particular X=DF(and Y=RF) , then we say that Fis a relation of Xinto (onto) Y. A relation Fon Xto Yis called a function if for each x∈DFthere exists y∈Ysuch that F(x) = {y}. In this case, by identifying singletons with their elements, we usually write F(x) = yin place of F(x) = {y}. If Xis nonvoid set and + is a function of X2into X, then the ordered pair X(+) = ( X, + ) is called a groupoid. In this case, we may also naturally write x+y= + ( x, y ) for all x, y ∈X. Moreover, if Xis a groupoid, then we may also naturally write A+B= ©x+y:x∈A , y ∈Bªfor all A , B ⊂X. Thus, the family P(X) of all subsets of Xis also a groupoid. Note that if Xis, in particular, a group, then P(X) is, in general, only a semigroup with zero element {0}. However, we can still naturally use the notations −A={ − x:x∈Aªand A−B=A+ ( −B) . 2 Pointwise and global sums and negatives of relations Definition 2.1 If Fand Gare relations on a set Xto groupoid Yand F+Gis the relation on Xto Ysuch that (F+G)(x) = F(x) + G(x) for all x∈X, then F+Gis called the pointwise sum of Fand G. While, if Fand Gare relations on one groupoid Xto another Yand F⊕G=©(x+z, y +w) : (x, y)∈F , (z, w)∈Gª, then the relation F⊕Gis called the global sum of Fand G. Pointwise and global sums and negatives of binary relations 89 Remark 2.2 Thus, we have DF+G=DF∩DGand DF⊕G=DF+DG. The global sum F⊕Gis, in general, quite different from the pointwise one F+Geven if DF+G=DF⊕G. Example 2.3 If Xis a groupoid, then (1) ∆X+ ∆X= ∆Xif and only if x=x+xfor all x∈X; (2) ∆X⊕∆X= ∆Xif and only if for each x∈Xthere exist u , v ∈X such that x=u+v. Therefore, if in particular Xis a group, then ∆X⊕∆X= ∆X, but ∆X+ ∆X= ∆Xif and only if X={0}. However, in some very particular cases, the global sum of relations may coincide with the pointwise one. Example 2.4 Let Xbe a nonvoid set, and for all x, y ∈Xdefine x+y= x. Then Xis a semigroup such that, for any two relations Fand Gon X, we have F⊕G=Fwhenever G6=∅, and F+G=Fwhenever G(x)6=∅ for all x∈DF. Analogously to Definition 2.1, we may also naturally introduce the following Definition 2.5 If Fis a relation on a set Xto group Yand −Fis the relation on Xto Ysuch that (−F)(x) = −F(x) for all x∈X, then −Fis called the pointwise negative of F. While, if Fis a relation on one group Xto another Yand ªF=©(−x , −y) : (x, y)∈Fª, then the relation ªFis called the global negative of F. Remark 2.6 Thus, we have D−F=DFand DªF=−DF. The global negative ªFis, in general, also quite different from the pointwise one −Feven if DªF=D−F. 90 T. Glavosits and ´ A. Sz´ az Example 2.7 If Xis a group, then ª∆X= ∆X, but −∆X= ∆Xif and only if −x=xfor all x∈X. However, in some very particular cases, the global negative of a relation may coincide with the pointwise one. Example 2.8 If Xis a group such that −x=xfor all x∈X, then −F=Fand ªF=Ffor any relation Fon X. Concerning the images of sets under the relations −F,ªF,F+Gand F⊕G, we can easily prove the following theorems. Theorem 2.9 If Fis a relation on a set Xto a group Y, then (−F)(A) = −F(A) for all A⊂X. Theorem 2.10 If Fis a relation on one group Xto another Y, then (ªF)(A) = −F(−A) for all A⊂X. Proof. If y∈(ªF)(A) , then there exists x∈Asuch that y∈ (ªF)(x) , and thus ( x, y )∈ ªF. Hence, it follows that ( −x, −y)∈F, and thus −y∈F(−x) . Thus, since F(−x)⊂F(−A) , we also have y∈ −F(−A) . Therefore, ( ªF)(A)⊂ − F(−A) . Now, by writing ªFin place of Fand −Ain place A, we can also see that F(−A) = ¡ª(ªF)¢(−A)⊂ − (ªF)¡−(−A)¢=−(ªF) (A), and thus −F(−A)⊂(ªF)(A) is also true. ¤ Corollary 2.11 If Fis a relation on one group Xto another Y, then (1) ªF=Fif and only if F(−x) = −F(x)for all x∈X; (2) ªF=−Fif and only if F(−x) = F(x)for all x∈X. Theorem 2.12 If Fand Gare relations on a set Xto groupoid Y, then (F+G)(A)⊂F(A) + G(A) for all A⊂X. Pointwise and global sums and negatives of binary relations 91 Theorem 2.13 If Fand Gare relations on one groupoid Xto another Y, then F(A) + G(B)⊂(F⊕G)( A+B) for all A , B ⊂X. Proof If w∈F(A) + G(B) , then there exist y∈F(A) and z∈G(B) such that w=y+z. Moreover, there exist a∈Aand b∈Bsuch that y∈F(a) and z∈G(b) , and thus ( a, y )∈Fand ( b, z )∈G. Hence, it follows that ( a+b , w ) = ( a+b , y +z)∈F⊕G, and thus w∈(F⊕G)( a+b) . Thus, since ( F⊕G)( a+b)⊂(F⊕G)( A+B) , we also have w∈(F⊕G)( A+B) . ¤ Corollary 2.14 If Fand Gare relations on one groupoid Xto another Y, and Ais a subgroupoid of X, then F(A) + G(A)⊂(F⊕G)(A). 3 Some further results on the global sums of relations Theorem 3.1 If Fand Gare relations on one groupoid Xto another Y, then (F⊕G)(A) = [ u+v∈A ¡F(u) + G(v)¢ for all A⊂X. Proof If y∈(F⊕G)(A) , then there exists x∈Asuch that y∈ (F⊕G)(x) , and hence ( x , y )∈F⊕G. Therefore, there exist ( u , z )∈F and ( v , w )∈Gsuch that ( x , y ) = ( u+v , z +w) . Hence, it follows that z∈F(u) and w∈G(v) , and moreover x=u+vand y=z+w. Therefore, y∈F(u) + G(v) , and hence y∈Sx=u+v¡F(u) + G(v)¢⊂ Su+v∈A¡F(u) + G(v)¢. While, if y∈Su+v∈A¡F(u) + G(v)¢, then there exist u , v ∈X, with x=u+v∈A, such that y∈F(u)+G(v) . Therefore, there exist z∈F(u) and w∈G(v) such that y=z+w. Hence, it is clear that ( u , z )∈Fand (v , w )∈Gsuch that ( x , y ) = ( u+v , z+w) . Therefore, ( x , y )∈F⊕G, and hence y∈(F⊕G)(x)⊂(F⊕G)(A) . ¤ Remark 3.2 The A={x}particular case of the above theorem shows that, in contrast to the intersection convolution (F∗G)(x) = \ x=u+v ¡F(u) + G(v)¢, 92 T. Glavosits and ´ A. Sz´ az the union convolution of relations not be introduced since it coincides with the global sum. Now, as a useful consequence of Theorem 3.1, we can also prove Corollary 3.3 If Fand Gare relations on one group Xto a groupoid Y, then (F⊕G)(A) = [ v∈X ¡F(A−v) + G(v)¢ for all A⊂X. Proof If y∈(F⊕G)(A) , then by Theorem 3.1 y∈Su+v∈A¡F(u) + G(v)¢. Therefore, there exist u , v ∈X, with x=u+v∈A, such that y∈F(u) + G(v) . Hence, it follows that y∈F(x−v) + G(v)⊂ F(A−v) + G(v) , and thus y∈Sv∈X¡F(A−v) + G(v)¢. While, if y∈Sv∈X¡F(A−v) + G(v)¢, then there exists v∈X such that y∈F(A−v) + G(v) . Therefore, there exists x∈Asuch that y∈F(x−v) + G(v) . Hence, by defining u=x−v, we can see that u∈Xsuch that x=u+vand y∈F(u) + G(v)¢. Therefore, y∈ Sx=u+v¡F(u) + G(v)¢⊂Su+v∈A¡F(u) + G(v)¢, and hence by Theorem 3.1 y∈(F⊕G)(A) . ¤ Moreover, as a simple reformulation of the above corollary we can also state Corollary 3.4 If Fand Gare relations on one group Xto a groupoid Y, then (F⊕G) (A) = [ u∈X ¡F(u) + G(−u+A)¢ for all A⊂X. Proof If y∈(F⊕G)(A) , then by Corollary 3.3 y∈Sv∈X¡F(A− v)+G(v)¢. Therefore, there exists v∈Xsuch that y∈F(A−v)+G(v) . Thus, there exists x∈Asuch that y∈F(x−v) + G(v) . Now, by defining u=x−v, we can see that y∈F(u) + G(−u+x)⊂F(u) + G(−u+A) . Therefore, y∈Su∈X¡F(u) + G(−u+A)¢. While, if y∈Su∈X¡F(u) + G(−u+A)¢, then there exists u∈X such that y∈F(u) + G(−u+A) . Therefore, there exists x∈Asuch that y∈F(u) + G(−u+x) . Now, by defining v=−u+x, we can see that y∈F(x−v) + G(v)⊂F(A−v) + G(v) . Therefore, y∈Sv∈X¡F(A− v) + G(v)¢, and hence by Corollary 3.3 y∈(F⊕G)(A) . ¤ Pointwise and global sums and negatives of binary relations 93 Remark 3.5 Now, by using the preceding results, one can also easily establish some properties of the images of sets under the relations F−G=F+ ( −G)and FªG=F⊕(ªG). References [1] ´ A. Sz´az, The intersection convolution of relations and the Hahn–Banach type theorems, Ann. Polon. Math. 69 (1998), 235–249 [2] ´ A. Sz´az, Translation relations, the building bloks of compatible relators, Math. Montisnigri, to appear Institute of Mathematics and Informatics, University of Debrecen, H-4010 Debrecen, Pf. 12, Hungary 94 T. Glavosits and ´ A. Sz´ az