On the existence of right adjoints for surjective mappings between fuzzy structures.

On the existence of right adjoints for surjective mappings between fuzzy structures I.P. Cabrera1, P. Cordero1, F. Garc´ıa-Pardo1, M. Ojeda-Aciego1, and B. De Baets2 1Universidad de M´alaga. Dept. Matem´atica Aplicada. Andaluc´ıa Tech. Spain. ? 2KERMIT. Department of Mathematical Modelling, Statistics and Bioinformatics. Ghent University Abstract. We continue our study of the characterization of existence of adjunctions (isotone Galois connections) whose codomain is insufficiently structured. This paper focuses on the fuzzy case in which we have a fuzzy ordering ⇢Aon Aand a surjective mapping f:hA, ⇡Ai!hB,⇡Bicompatible with respect to the fuzzy equivalences ⇡Aand ⇡B. Specifically, the problem is to find a fuzzy ordering ⇢Band a compatible mapping g:hB,⇡Bi!hA, ⇡Aisuch that the pair (f,g) is a fuzzy adjunction. 1 Introduction Adjunctions, also called isotone Galois connections, are often used in mathematics in order to relate two (apparently disparate) theories, allowing for mutual cooperative advantages. A number of papers are being published on the applications (both theoretical and practical) of Galois connections and adjunctions. One can find mainly theoretical papers [10,15,17,23], as well as general applications to computer science, some of them dated more than thirty years ago [21] and, obviously, some more recent works on specific applications, such as programming [16, 22], data analysis [26], or logic [18,25]. The study of new properties of Galois connections found an important niche in the theory of Formal Concept Analysis (FCA) and its generalizations, since the derivation operators which are used to define the formal concepts actually are a Galois connection. Just to name a few, Lumpe and Schmidt [20] consider adjunctions and their concept posets in order to define a convenient notion of morphism between pattern structures; Bˇelohl´avek and Koneˇcn´y [3] stress on the “duality” between isotone and antitone Galois connections in showing a case of mutual reducibility of the concept lattices generated by using each type of connection; Denniston et al [8] show how new results on Galois connection are applied to formal concept analysis, etc. ?Partially supported by Spanish Ministry of Science projects TIN2014-59471-P and TIN2015-70266-C2-1-P, co-funded by the European Regional Development Fund (ERDF). It is certainly important to detect when an adjunction (or Galois connection) exists between two structured sets, and this problem has been already studied in the abstract setting of category theory. A di↵erent problem arises when either the domain or the codomain is unstructured: the authors studied in a previous work [14] the existence and construction of the right adjoint to a given mapping fin the general framework in which a mapping f:A!Bfrom a (pre-)ordered set Ainto an unstructured set Bis considered, aiming at characterizing those situations in which Bcan be (pre-)ordered and an isotone mapping g:B!A can be built such that the pair (f,g) is an adjunction. The general approach to this problem adopted in [14] was to consider the canonical decomposition of fwith respect to the kernel relation, and consider the three resulting cases separately: the projection on the quotient, the isomorphism between the quotient and the image, and the final inclusion of the image into the codomain. The really important parts of the proof were the first and the last ones, since the intermediate part is straightforward. We consider this work as an extension of the previous problem to a fuzzy framework, in which several papers on fuzzy Galois connections or fuzzy adjunctions have been written since its introduction by Bˇelohl´avek in [1]; consider for instance [4, 9, 19, 27] for some recent generalizations. Some authors have introduced alternative approaches guided by the intended applications: for instance, Shi et al [24] introduced a definition of fuzzy adjunction for its use in fuzzy mathematical morphology. In this paper, on the one hand, we will consider mappings compatible with fuzzy equivalences ⇡Aand ⇡Bdefined on Aand Brespectively and, on the other hand, we will just focus on the first part of the canonical decomposition. This means that, up to isomorphism, we have a fuzzy ordering ⇢Aon Aand a surjective mapping f:hA, ⇡Ai!hB,⇡Bicompatible with respect to the fuzzy equivalences ⇡Aand ⇡B. Specifically, the problem is to characterize when there exists a fuzzy ordering ⇢Band a compatible mapping g:hB,⇡Bi!hA, ⇡Ai such that the pair (f,g) is a fuzzy adjunction. 2 Preliminaries The most usual underlying structure for considering fuzzy extensions of Galois connections is that of complete residuated lattice, L=(L, ,>,?,⌦,!). As usual, supremum and infimum will be denoted by _and ^respectively. An Lfuzzy set in the universe Uis a mapping X:U!Lwhere X(u) means the degree in which ubelongs to X.GivenXand Ytwo L-fuzzy sets, Xis said to be included in Y, denoted as X✓Y,ifX(u)Y(u) for all u2U. An L-fuzzy binary relation on Uis an L-fuzzy subset of U⇥U, that is R:U⇥U!L, and it is said to be: –Reflexive if R(a, a)=>for all a2U. –⌦-Transitive if R(a, b)⌦R(b, c)R(a, c) for all a, b, c 2U. –Symmetric if R(a, b)=R(b, a) for all a, b 2U. 2 From now on, when no confusion arises, we will omit the prefix “L-”. Definition 1. Afuzzy preordered set is a pair A=hA, ⇢Aiin which ⇢Ais a reflexive and ⌦-transitive fuzzy relation on A. Definition 2. Let A=hA, ⇢Aibe a fuzzy preordered set. The extensions to the fuzzy setting of the notions of upset and downset of an element a2Aare defined by a",a #:A!Lwhere a#(u)=⇢A(u, a)and a"(u)=⇢A(a, u)for all u2A. Definition 3. An element m2Ais a maximum for a fuzzy set X:A!Lif 1. X(m)=>and 2. X✓m#, i.e., X(u)⇢A(u, m)for all u2A. The definition of minimum is similar. Since the maximum (respectively, minimum) of a fuzzy set needs not be unique, we will include special terminology for them: the crisp set of maxima, respectively minima, for Xwill be denoted p-max(X), respectively p-min(X). Definition 4. Let A=hA, ⇢Aiand B=hB,⇢Bibe fuzzy preordered sets. 1. Amappingf:A!Bis said to be isotone if ⇢A(a1,a 2)⇢B(f(a1),f(a2)) for all a1,a 22A. 2. Amappingf:A!Ais said to be inflationary if ⇢A(a, f(a)) = >for all a2A. Similarly, fis deflationary if ⇢A(f(a),a)=>for all a2A. From now on, we will use the following notation: For a mapping f:A!Band afuzzysubsetYof B,thefuzzysetf1(Y) is defined as f1(Y)(a)=Y(f(a)), for all a2A. The definition of fuzzy adjunction given in [11] was the expected extension of that in the crisp case. Namely, Definition 5. Let A=hA, ⇢Ai,B=hB,⇢Bibe fuzzy orders, and two mappings f:A!Band g:B!A.Thepair(f,g)forms a fuzzy adjunction between Aand B, denoted (f,g):A↵Bif, for all a2Aand b2B, the equality ⇢A(a, g(b)) = ⇢B(f(a),b)holds. As in the crisp case, there exist alternative definitions which are summarized in the theorem below: Theorem 1 (See [11]). Let A=hA, ⇢Ai,B=hB,⇢Bibe two fuzzy preordered sets, respectively, and f:A!Band g:B!Abe two mappings. The following statements are equivalent: 1. (f,g):A↵B. 2. fand gare isotone, gfis inflationary, and fgis deflationary. 3. f(a)"=g1(a")for all a2A. 3 4. g(b)#=f1(b#)for all b2B. 5. fis isotone and g(b)2p-max f1(b#)for all b2B. 6. gis isotone and f(a)2p-min g1(a")for all a2A. In the rest of this section, we introduce the preliminary definitions and results needed to establish the new structure we will be working on. Definition 6. A fuzzy relation ⇡on Ais said to be a: –Fuzzy equivalence relation if ⇡is a reflexive, ⌦-transitive and symmetric fuzzy relation on A. –Fuzzy equality if ⇡is a fuzzy equivalence relation satisfying that ⇡(a, b)= >implies a=b,foralla, b 2A. We will use the infix notation for a fuzzy equivalence relation, that is, we will write a1⇡a2instead of ⇡(a1,a 2). Definition 7. Given a fuzzy equivalence relation ⇡:A⇥A!L,theequivalence class of an element a2Ais the fuzzy set [a]⇡:A!Ldefined by [a]⇡(u)=(a⇡u)for all u2A. Remark 1. Note that [x]⇡=[y]⇡if and only if (x⇡y)=>: on the one hand, if [x]⇡=[y]⇡,then(x⇡y)=[x]⇡(y)=[y]⇡(y)=>, by reflexivity; conversely, if (x⇡y)=>,then[x]⇡(u)=(x⇡u)=(y⇡x)⌦(x⇡u)(y⇡u)=[y]⇡(u), for all u2A; the other inequality follows similarly. Definition 8 (See [6]). Given a fuzzy equivalence relation ⇡Aon A,afuzzy binary relation ⇢A:A⇥A!Lis said to be –⇡A-reflexive if (a1⇡Aa2)⇢A(a1,a 2), –⌦-⇡A-antisymmetric if ⇢A(a1,a 2)⌦⇢A(a2,a 1)(a1⇡Aa2), for all a1,a 22A. Definition 9. A triplet A=hA, ⇡A,⇢ Aiin which ⇡Ais a fuzzy equivalence relation and ⇢Ais ⇡A-reflexive, ⌦-⇡A-antisymmetric and ⌦-transitive will be called ⌦-⇡A-fuzzy preordered set or fuzzy preorder with respect to ⇡A. Observe that a fuzzy preorder relation wrt ⇡Ais a fuzzy preorder relation because >=(a⇡Aa)⇢A(a, a), therefore ⇢A(a, a)=>, for all a2A. Definition 10. Let ⇡Aand ⇡Bbe fuzzy equivalence relations on the sets Aand B, respectively. A mapping f:A!Bis said to be compatible with ⇡Aand ⇡Bif (a1⇡Aa2)(f(a1)⇡Bf(a2)) for all a1,a 22A. 4 3 On fuzzy adjunctions wrt fuzzy equivalences The main idea to extend the notion of fuzzy adjunction to take into account fuzzy equivalences, namely, a fuzzy adjunction between A=hA, ⇡A,⇢ Aiand B=hB,⇡B,⇢ Biis, of course, to require fand gto be compatible mappings and include the necessary adjustments due to the use of fuzzy equivalences. A reasonable possibility is the following: Definition 11. Let A=hA, ⇡A,⇢ Aiand B=hB,⇡B,⇢ Bibe two fuzzy preordered sets wrt ⇡Aand ⇡B, respectively. Let f:A!Band g:B!Abe two mappings which are compatible with ⇡Aand ⇡B.Thepair(f,g)is said to be a fuzzy adjunction between Aand Bif the following conditions hold (A1) (a1⇡Aa2)⌦⇢A(a2,g(b)) ⇢B(f(a1),b) (A2) (b1⇡Bb2)⌦⇢B(f(a),b 1)⇢A(a,g(b2)) for all a, a1,a 22Aand b, b1,b 22B. Surprisingly, it turns out that Definitions 5 and 11 are very closely related, in fact, they are equivalent up to compatibility of the mappings. Theorem 2. Let A=hA, ⇡A,⇢ Aiand B=hB,⇡B,⇢ Bibe two fuzzy preordered sets wrt ⇡Aand ⇡B, respectively. Let f:A!Band g:B!Abe two mappings which are compatible with ⇡Aand ⇡B, respectively. Then, the pair (f,g)is a fuzzy adjunction between Aand Bif and only if ⇢A(a, g(b)) = ⇢B(f(a),b)for all a2Aand b2B. Proof. Assume that for all a2Aand b2Bthe equality ⇢A(a, g(b)) = ⇢B(f(a),b) holds. Let a1,a 22Aand b2B.Sincefis a map which is compatible with ⇡Aand ⇡B,then (a1⇡Aa2)⌦⇢A(a2,g(b)) (f(a1)⇡Bf(a2)) ⌦⇢A(a2,g(b)). By the hypothesis, we obtain that (f(a1)⇡Bf(a2)) ⌦⇢A(a2,g(b)) (f(a1)⇡Bf(a2)) ⌦⇢B(f(a2),b). As ⇢Bis ⇡B-reflexive and transitive, we have that (f(a1)⇡Bf(a2))⌦⇢B(f(a2),b)⇢B(f(a1),f(a2))⌦⇢B(f(a2),b)⇢B(f(a1),b). Therefore, (a1⇡Aa2)⌦⇢A(a2,g(b)) ⇢B(f(a1),b) for all a1,a 22Aand b2B. Analogously, the condition (A2) holds. Conversely, assume now that conditions (A1) and (A2) hold. Applying condition (A1), for a2Aand b2B, we have that (a⇡Aa)⌦⇢A(a, g(b)) ⇢B(f(a),b). Being ⇡Areflexive, it is deduced that ⇢A(a, g(b)) ⇢B(f(a),b) for all a2Aand b2B. Analogously, ⇢B(f(a),b)⇢A(a, g(b)) for all a2Aand b2B. Therefore, ⇢A(a, g(b)) = ⇢B(f(a),b) for all a2Aand b2B.ut 5 Corollary 1. If a pair (f,g)is a fuzzy adjunction between hA, ⇡A,⇢ Aiand hB,⇡B,⇢ Bithen (f,g)is also a fuzzy adjunction between the two fuzzy preordered sets hA, ⇢Aiand hB,⇢Bi. Conversely, if a pair (f,g)is a fuzzy adjunction between hA, ⇢Aiand hB,⇢Bi then (f,g)is also a fuzzy adjunction between hA, =,⇢ Aiand hB,=,⇢ Bi, being = the standard crisp equality. In the rest of this section, we extend the results in [12,13] to the framework of fuzzy preordered sets wrt a fuzzy equivalence relation. The underlying idea is similar, but now the mappings fand gneed to be compatible with fuzzy equivalence relations ⇡Aon Aand ⇡Bon B, and this makes the development to be much more involved that in the previous case. To begin with, it is worth to mention that the equivalences in Theorem 1 are valid when considering fuzzy equivalences: obviously, the mappings have to be compatible. Remark 2. Given two elements x1,x 22p-max(X), note that ⇢A(x1,x 2)=>= ⇢A(x2,x 1): on the one hand, by x12p-max(X), we have that X(x1)=>and since x22p-max(X), then X(u)⇢A(u, x2) for all u2A. Hence, >=X(x1) ⇢A(x1,x 2) which implies that ⇢A(x1,x 2)=>. Likewise, by ⌦-⇡A-antisymmetry, also (x1⇡Ax2)=>for x1,x 22⇡Amax(X). Theorem 3. Let A=hA, ⇡A,⇢ Aiand B=hB,⇡B,⇢ Bibe two fuzzy preordered sets. If the pair (f,g)is a fuzzy adjunction between Aand Bthen (fgf)(a)⇡B f(a)=>and (gfg)(b)⇡Ag(b)=>,foralla2A, b 2B. Proof. Since fis isotone and gfis inflationary we have >=⇢A(a, gf(a)) ⇢B(f(a),fgf(a)), therefore, ⇢B(f(a),fgf(a)) = >. Moreover, ⇢B(fgf(a),f(a)) = ⇢A(gf(a),gf(a)) = >. Therefore, from the ⌦-⇡B-antisymmetric property, we obtain (fgf)(a)⇡Bf(a)) = >. For the other composition, the proof is analogous. ut Corollary 2. Let A=hA, ⇡A,⇢ Aiand B=hB,⇡B,⇢ Bibe two fuzzy preordered sets. If the pair (f,g)is a fuzzy adjunction between Aand Bthen, for all a2 A, b 2B, (i) ⇢B(fgf)(a),f(a)=⇢Bf(a),(fgf)(a)=> (ii) ⇢A(gfg)(b),g(b)=⇢Ag(b),(gfg)(b)=>. Corollary 3. Let A=hA, ⇡A,⇢ Aiand B=hB,⇡B,⇢ Bibe two fuzzy preordered sets. If the pair (f,g)is a fuzzy adjunction between Aand Bthen, for all a1,a 22 Aand b1,b 22B, the following equalities hold: (i) f(a1)⇡Bf(a2)=(gf)(a1)⇡A(gf)(a2). 6 (ii) g(b1)⇡Ag(b2)=(fg)(b1)⇡B(fg)(b2). Proof. We will prove just the first item, since the second one is similar. Given a1,a 22A,sincegis compatible, we have that f(a1)⇡Bf(a2) (gf)(a1)⇡A(gf)(a2). On the other hand, since fis compatible, we have that g(f(a1)) ⇡Ag(f(a2))f(g(f(a1))) ⇡Bf(g(f(a2))). Now, by Theorem 3, we have that f(a)⇡Bf(g(f(a)))=>, for all a2A. Finally, the ⌦-transitivity of ⇡Bleads to f(g(f(a1))) ⇡Bf(g(f(a2))) =f(a1)⇡Bf(g(f(a1)))⌦f(g(f(a1))) ⇡Bf(g(f(a2))) f(a1)⇡Bf(g(f(a2))) =f(a1)⇡Bf(g(f(a2)))⌦f(g(f(a2))) ⇡Bf(a2) f(a1)⇡Bf(a2) ut 4 Characterization and construction of the adjunction Some more definitions are needed in order to solve the problem in the case of surjective mappings. Definition 12. Let A=hA, ⇡A,⇢ Aiand B=hB,⇡B,⇢ Bibe two fuzzy preordered sets wrt ⇡Aand ⇡B, respectively, and let f:A!Bbe a compatible mapping. The fuzzy kernel relation ⌘f:A⇥A!Lassociated to fis defined as follows for a1,a 22A, (a1⌘fa2)=(f(a1)⇡Bf(a2)). Trivially, the fuzzy kernel relation is a fuzzy equivalence relation. The equivalence class of an element a2Ais a fuzzy set denoted by [a]f:A!Ldefined by [a]f(u)=(f(a)⇡Bf(u)) for all u2A. The following definitions recall the notion of Hoare ordering between crisp subsets, and then introduces an alternative statement in the subsequent lemma: Definition 13. Let A=hA, ⇡A,⇢ Aibe a fuzzy preordered set wrt a fuzzy equivalence relation ⇡A.ForC, D crisp subsets of A, consider the following notation –(CvWD)= _ c2C _ d2D ⇢A(c, d) –(CvHD)= ^ c2C _ d2D ⇢A(c, d) –(CvSD)= ^ c2C ^ d2D ⇢A(c, d) 7 Lemma 1. Let A=hA, ⇡A,⇢ Aibe a fuzzy preordered set wrt a fuzzy equivalence relation ⇡A,X, Y ✓Asuch that p-max(X)6=?6= p-max(Y), then (p-max(X)vWp-max(Y)) = (p-max(X)vHp-max(Y)) = (p-max(X)vSp-max(Y)) = ⇢A(x, y) for any x2p-max(X)and y2p-max(Y). Proof. Let us show that ⇢A(x, y)=⇢A(¯x, ¯y), for any x, ¯x2p-max(X) and y, ¯y2p-max(Y): Indeed, using the transitive property of ⇢Aand Remark 2 we have that ⇢A(x, y)⇢A(x, ¯x)⌦⇢A(¯x, y)=>⌦⇢A(¯x, y)⇢A(¯x, ¯y)⌦⇢A(¯y,y)=⇢A(¯x, ¯y). Analogously, ⇢A(¯x, ¯y)⇢A(x, y). Therefore, ⇢A(¯x, ¯y)=⇢A(x, y) for any x, ¯x2 p-max(X) and y, ¯y2p-max(Y). ut Notice that, by Lemma 1, when both sets are non-empty, for any x2 p-max(X) and y2p-max(Y), p-max(X)vHp-max(Y)=⇢A(x, y) and this justifies the following notation. Notation 1 Let A=hA, ⇡A,⇢ Aibe a fuzzy preorder wrt a fuzzy equivalence relation ⇡A. Let X, Y be crisp subsets of Asuch that p-max(X)6=?6= p-max(Y), then ⇢A(p-max(X),p-max(Y)) denotes p-max(X)vHp-max(Y). Remark 3. Let A=hA, ⇡A,⇢ Aibe a fuzzy preorder wrt a fuzzy equivalence relation ⇡Aand X, Y ✓A. Observe that for all x1,x 22p-max(X) and y1,y 22 p-max(Y), we have that (x1⇡Ay1)=(x2⇡Ay2): Indeed, recall that (x1⇡Ax2)=>=(y1⇡Ay2), then (x1⇡Ay1)=(x2⇡A x1)⌦(x1⇡Ay1)(x2⇡Ay1)=(x2⇡Ay1)⌦(y1⇡Ay2)(x2⇡Ay2). Therefore, we can use the notation p-max(X)⇡Ap-max(Y)=(x⇡Ay) for any x2p-max(X),y 2p-max(Y). Theorem 4 (Necessary conditions). Let A=hA, ⇡A,⇢ Ai,B=hB,⇡B,⇢ Bi be two fuzzy preorders and f:A!B,g:B!Atwo mappings which are compatible with the equivalence relations ⇡Aand ⇡B.If(f,g)is a fuzzy adjunction between Aand Bthen 1. p-max([a]f)is non-empty for all a2A. 2. ⇢A(a1,a 2)⇢A(p-max([a1]f),p-max([a2]f)),foralla1,a 22A. 3. (a1⌘fa2)(p-max([a1]f)⇡Ap-max([a2]f)),foralla1,a 22A. Proof. 8 –Condition 1. We will show that g(f(a)) 2p-max([a]f): By Theorem 3, we have (f(a)⇡Bf(g(f(a)))) = >. On the other hand, using the ⇡B-reflexivity and that (f,g) is a fuzzy adjunction, for all u2A, [a]f(u)=(f(u)⇡Bf(a)) ⇢B(f(u),f(a)) = ⇢A(u, g(f(a))) = g(f(a)) #(u) –Condition 2. By Theorem 1, fand gare isotone maps, thus ⇢A(a1,a 2)⇢A(g(f(a1)),g(f(a2))) for all a1,a 22A. We have just shown that g(f(a)) 2p-max([a]f) for all a2A, thus, from Lemma 1, we obtain that ⇢A(a1,a 2)⇢A(p-max([a1]f), p-max([a2]f)) for all a1,a 22A. –Condition 3. Since gis compatible with ⇡Band ⇡A,then(a1⌘fa2)= (f(a1)⇡Bf(a2)) (g(f(a1)) ⇡Ag(f(a2))). But, by Condition 1, g(f(ai)) 2 p-max([ai]f). ut Given A=hA, ⇡A,⇢ Aia fuzzy preordered set wrt ⇡Aand a surjective mapping f:A!Bcompatible with ⇡Aand ⇡B, our first goal is to find sufficient conditions to define a suitable fuzzy preordering wrt ⇡Bon B and a mapping g:B!Acompatible with ⇡Band ⇡Asuch that (f,g) is an adjoint pair. Lemma 2. Let A=hA, ⇡A,⇢ Aibe a fuzzy preorder and ⇡Bbe a fuzzy equivalence relation on Btogether with a surjective mapping f:A!Bcompatible with ⇡Aand ⇡B.Supposethatp-max([a]f)6=?for all a2A. Then, B=hB,⇡B,⇢ Bi is a fuzzy preorder wrt ⇡B, where ⇢Bis the fuzzy relation defined as follows ⇢B(b1,b 2)=⇢A(p-max([a1]f),p-max([a2]f)) where ai2f1(bi)for each i2{1,2}. Theorem 5 (Sufficient conditions). Let A=hA, ⇡A,⇢ Aibe a fuzzy preorder wrt ⇡Aand ⇡Bbe a fuzzy equivalence relation on Btogether with a surjective mapping f:A!Bcompatible with ⇡Aand ⇡B. Suppose that the following conditions hold: 1. p-max([a]f)is non-empty for all a2A. 2. ⇢A(a1,a 2)⇢A(p-max([a1]f),p-max([a2]f)),foralla1,a 22A. 3. (a1⌘fa2)(p-max([a1]f)⇡A(p-max([a2]f)),foralla1,a 22A. Then, there exists a mapping g:B!Acompatible with ⇡Aand ⇡Bsuch that (f,g)is a fuzzy adjunction between the fuzzy preorders Aand B=hB,⇡B,⇢ Bi, where ⇢Bis the fuzzy relation introduced in Lemma 2. Proof. Following Lemma 2, by Condition 1, there exists a fuzzy preordering ⇢B defined as follows: ⇢B(b1,b 2)=⇢A(p-max([a1]f),p-max([a2]f)) 9