We continue our study of the characterization of existence of adjunctions (isotone Galois connections) whose codomain is insu ciently structured. This paper focuses on the fuzzy case in which we have a fuzzy ordering A on A and a surjective mapping f : hA; Ai ! hB; Bi compatible with respect to the fuzzy equivalences A and B. Speci cally, the problem is to nd a fuzzy ordering B and a compatible mapping g : hB; Bi ! hA; Ai such that the pair (f; g) is a fuzzy adjunction.
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 nd mainly
theoretical papers [
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 de ne the formal concepts actually
are a Galois connection. Just to name a few, Lumpe and Schmidt [
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 [
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 Belohlavek in [
In this paper, on the one hand, we will consider mappings compatible with fuzzy equivalences A and B de ned on A and B respectively and, on the other hand, we will just focus on the rst part of the canonical decomposition. This means that, up to isomorphism, we have a fuzzy ordering A on A and a surjective mapping f : hA; Ai ! hB; Bi compatible with respect to the fuzzy equivalences A and B. Speci cally, the problem is to characterize when there exists a fuzzy ordering B and a compatible mapping g : hB; Bi ! hA; Ai such that the pair (f; g) is a fuzzy adjunction. 2
The most usual underlying structure for considering fuzzy extensions of Galois connections is that of complete residuated lattice, L = (L; ; >; ?; ; !). As usual, supremum and in mum will be denoted by _ and ^ respectively. An Lfuzzy set in the universe U is a mapping X : U ! L where X(u) means the degree in which u belongs to X. Given X and Y two L-fuzzy sets, X is said to be included in Y , denoted as X Y , if X(u) Y (u) for all u 2 U .
An L-fuzzy binary relation on U is an L-fuzzy subset of U U , that is R : U U ! L, and it is said to be: { Re exive if R(a; a) = > for all a 2 U . { -Transitive if R(a; b) R(b; c) R(a; c) for all a; b; c 2 U . { Symmetric if R(a; b) = R(b; a) for all a; b 2 U .
From now on, when no confusion arises, we will omit the pre x \L-". De nition 1. A fuzzy preordered set is a pair A = hA; Ai in which A is a re exive and -transitive fuzzy relation on A.
De nition 2. Let A = hA; Ai be a fuzzy preordered set. The extensions to the fuzzy setting of the notions of upset and downset of an element a 2 A are de ned by a"; a# : A ! L where a#(u) =
A(u; a) and a"(u) =
A(a; u) for all u 2 A:
1. X(m) = > and 2. X m#, i.e., X(u) The de nition of minimum is similar.
A(u; m) for all u 2 A:
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 X will be denoted p-max(X), respectively p-min(X). De nition 4. Let A = hA; Ai and B = hB; Bi be fuzzy preordered sets.
for all a1; a2 2 A. 2. A mapping f : A ! A is said to be in ationary if A(a; f (a)) = > for all a 2 A.
Similarly, f is de ationary if A(f (a); a) = > for all a 2 A.
From now on, we will use the following notation: For a mapping f : A ! B and a fuzzy subset Y of B, the fuzzy set f 1(Y ) is de ned as f 1(Y )(a) = Y (f (a)), for all a 2 A.
The de nition of fuzzy adjunction given in [
A(a; g(b)) = B(f (a); b) holds.
As in the crisp case, there exist alternative de nitions which are summarized
in the theorem below:
Theorem 1 (See [
In the rest of this section, we introduce the preliminary de nitions and results needed to establish the new structure we will be working on.
De nition 6. A fuzzy relation
on A is said to be a: { Fuzzy equivalence relation if
fuzzy relation on A. { Fuzzy equality if is a fuzzy equivalence relation satisfying that > implies a = b, for all a; b 2 A: is a re exive, -transitive and symmetric (a; b) = We will use the in x notation for a fuzzy equivalence relation, that is, we will write a1 a2 instead of (a1; a2).
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 re exivity; conversely, if (x y) = >, then [x] (u) = (x u) = (y x) (x u) (y u) = [y] (u), for all u 2 A; the other inequality follows similarly.
De nition 8 (See [
A-re exive if (a1 A a2) A(a1; a2), - A-antisymmetric if A(a1; a2) A(a2; a1) (a1
A a2), for all a1; a2 2 A.
De nition 9. A triplet A = hA; A; Ai in which A is a fuzzy equivalence relation and A is A-re exive, - 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 A is a fuzzy preorder relation because > = (a A a) A(a; a), therefore A(a; a) = >, for all a 2 A. De nition 10. Let A and B be fuzzy equivalence relations on the sets A and
B if (a1 A a2) (f (a1) B f (a2)) for all a1; a2 2 A.
The main idea to extend the notion of fuzzy adjunction to take into account fuzzy equivalences, namely, a fuzzy adjunction between A = hA; A; Ai and B = hB; B; Bi is, of course, to require f and g to be compatible mappings and include the necessary adjustments due to the use of fuzzy equivalences. A reasonable possibility is the following: De nition 11. Let A = hA; A; Ai and B = hB; B; Bi be two fuzzy preordered sets wrt A and B, respectively. Let f : A ! B and g : B ! A be two mappings which are compatible with A and B. The pair (f; g) is said to be a fuzzy adjunction between A and B if the following conditions hold (A1) (a1 A a2) (A2) (b1 B b2)
A(a2; g(b)) B(f (a); b1)
B(f (a1); b)
A(a;g(b2)) for all a; a1; a2 2 A and b; b1; b2 2 B.
Surprisingly, it turns out that De nitions 5 and 11 are very closely related, in fact, they are equivalent up to compatibility of the mappings. Theorem 2. Let A = hA; A; Ai and B = hB; B; Bi be two fuzzy preordered sets wrt A and B, respectively. Let f : A ! B and g : B ! A be two mappings which are compatible with A and B, respectively.
A(a; g(b)) = B(f (a); b) for all a 2 A and b 2 B.
Proof. Assume that for all a 2 A and b 2 B the equality A(a; g(b)) = B(f (a); b) holds.
Let a1; a2 2 A and b 2 B. Since f is a map which is compatible with A and B, then (a1 A a2)
A(a2; g(b)) (f (a1) B f (a2))
A(a2; g(b)): By the hypothesis, we obtain that (f (a1) B f (a2))
A(a2; g(b)) (f (a1) B f (a2))
B(f (a2); b): As B is
B-re exive and transitive, we have that (f (a1) B f (a2))
B(f (a2); b)
B(f (a1); f (a2))
B(f (a2); b)
B(f (a1); b): Therefore, (a1 A a2) A(a2; g(b)) B(f (a1); b) for all a1; a2 2 A and b 2 B. Analogously, the condition (A2) holds.
Conversely, assume now that conditions (A1) and (A2) hold. Applying condition (A1), for a 2 A and b 2 B, we have that (a A a) A(a; g(b)) B(f (a); b). Being A re exive, it is deduced that A(a; g(b)) B(f (a); b) for all a 2 A and b 2 B. Analogously, B(f (a); b) A(a; g(b)) for all a 2 A and b 2 B. Therefore,
A(a; g(b)) = B(f (a); b) for all a 2 A and b 2 B. tu
then (f; g) is also a fuzzy adjunction between hA; =; Ai and hB; =; Bi, being = the standard crisp equality.
In the rest of this section, we extend the results in [
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; x2 2 p-max(X), note that A(x1; x2) = > =
A(x2; x1): on the one hand, by x1 2 p-max(X), we have that X(x1) = > and since x2 2 p-max(X), then X(u) A(u; x2) for all u 2 A. Hence, > = X(x1) A(x1; x2) which implies that A(x1; x2) = >.
Likewise, by - A-antisymmetry, also (x1 A x2) = > for x1; x2 2 Amax(X).
Theorem 3. Let A = hA; A; Ai and B = hB; B; Bi be two fuzzy preordered sets. If the pair (f; g) is a fuzzy adjunction between A and B then (f g f )(a) B f (a) = > and (g f g)(b) A g(b) = >, for all a 2 A; b 2 B. Proof. Since f is isotone and g f is in ationary we have > = A(a; gf (a))
B(f (a); f gf (a)); therefore, B(f (a); f gf (a)) = >.
Moreover, B(f gf (a); f (a)) = A(gf (a); gf (a)) = >. Therefore, from the - B-antisymmetric property, we obtain (f g f )(a) B f (a)) = >.
For the other composition, the proof is analogous. tu Corollary 2. Let A = hA; A; Ai and B = hB; B; Bi be two fuzzy preordered sets. If the pair (f; g) is a fuzzy adjunction between A and B then, for all a 2 A; b 2 B, (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; Ai and B = hB; B; Bi be two fuzzy preordered sets. If the pair (f; g) is a fuzzy adjunction between A and B then, for all a1; a2 2
(i) f (a1) B f (a2) = (g f )(a1) A (g f )(a2) . (ii) g(b1) A g(b2) = (f g)(b1) B (f g)(b2) .
Proof. We will prove just the rst item, since the second one is similar.
Given a1; a2 2 A, since g is compatible, we have that f (a1) B f (a2) (g f )(a1) A (g f )(a2) . On the other hand, since f is compatible, we have that g(f (a1)) A g(f (a2))
f (g(f (a1))) B f (g(f (a2))) : Now, by Theorem 3, we have that f (a) Finally, the -transitivity of B leads to f (g(f (a1))) B f (g(f (a2)))
B f (g(f (a))) = >, for all a 2 A. = f (a1) B f (g(f (a1)))
f (g(f (a1))) B f (g(f (a2))) f (a1) B f (g(f (a2))) f (a1) B f (a2) = f (a1) B f (g(f (a2))) f (g(f (a2))) B f (a2) tu 4
Some more de nitions are needed in order to solve the problem in the case of surjective mappings.
De nition 12. Let A = hA; A; Ai and B = hB; B; Bi be two fuzzy preordered sets wrt A and B, respectively, and let f : A ! B be a compatible mapping. The fuzzy kernel relation f : A A ! L associated to f is de ned as follows for a1; a2 2 A,
(a1 f a2) = (f (a1) B f (a2)): Trivially, the fuzzy kernel relation is a fuzzy equivalence relation. The equivalence class of an element a 2 A is a fuzzy set denoted by [a]f : A ! L de ned by [a]f (u) = (f (a) B f (u)) for all u 2 A.
The following de nitions recall the notion of Hoare ordering between crisp subsets, and then introduces an alternative statement in the subsequent lemma: De nition 13. Let A = hA; A; Ai be a fuzzy preordered set wrt a fuzzy equivalence relation A. For C; D crisp subsets of A, consider the following notation { (C vW D) = _ _
c2C d2D { (C vH D) = ^ _
c2C d2D { (C vS D) = ^ ^
A(c; d) A(c; d)
A(c; d) Lemma 1. Let A = hA; A; Ai be a fuzzy preordered set wrt a fuzzy equivalence relation A, X; Y A such that p-max(X) 6= ? 6= p-max(Y ), then (p-max(X) vW p-max(Y )) = (p-max(X) vH p-max(Y ))
= (p-max(X) vS p-max(Y )) = A(x; y) for any x 2 p-max(X) and y 2 p-max(Y ).
Proof. Let us show that A(x; y) = A(x; y), for any x; x 2 p-max(X) and y; y 2 p-max(Y ): Indeed, using the transitive property of A and 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; x 2 p-max(X) and y; y 2 p-max(Y ). tu
Notice that, by Lemma 1, when both sets are non-empty, for any x 2 p-max(X) and y 2 p-max(Y ), p-max(X) vH p-max(Y ) = A(x; y) and this justi es the following notation.
Notation 1 Let A = hA; A; Ai be a fuzzy preorder wrt a fuzzy equivalence relation A. Let X; Y be crisp subsets of A such that p-max(X) 6= ? 6= p-max(Y ), then A(p-max(X); p-max(Y )) denotes p-max(X) vH p-max(Y ) . Remark 3. Let A = hA; A; Ai be a fuzzy preorder wrt a fuzzy equivalence relation A and X; Y A. Observe that for all x1; x2 2 p-max(X) and y1; y2 2 p-max(Y ), we have that (x1 A y1) = (x2 A y2):
Indeed, recall that (x1 A x2) = > = (y1 A y2), then (x1 A y1) = (x2 A x1) (x1 A y1) (x2 A y1) = (x2 A y1) (y1 A y2) (x2 A y2).
Therefore, we can use the notation p-max(X) A p-max(Y ) = (x
A y) for any x 2 p-max(X); y 2 p-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 ! A two mappings which are compatible with the equivalence relations A and B. If (f; g) is a fuzzy adjunction between A and B then
2. A(a1; a2) A(p-max([a1]f ),p-max([a2]f )), for all a1; a2 2 A. 3. (a1 f a2) (p-max([a1]f ) A p-max([a2]f )), for all a1; a2 2 A. Proof.
{ Condition 1. We will show that g(f (a)) 2 p-max([a]f ):
By Theorem 3, we have (f (a) B f (g(f (a)))) = >: On the other hand, using the B-re exivity and that (f; g) is a fuzzy adjunction, for all u 2 A, [a]f (u) = (f (u) B f (a))
B(f (u); f (a)) = A(u; g(f (a))) = g(f (a)) # (u) { Condition 2. By Theorem 1, f and g are isotone maps, thus
A(a1; a2)
A(g(f (a1)); g(f (a2))) for all a1; a2 2 A. We have just shown that g(f (a)) 2 p-max([a]f ) for all a 2 A, thus, from Lemma 1, we obtain that A(a1; a2) A(p-max([a1]f ), p-max([a2]f )) for all a1; a2 2 A. { Condition 3. Since g is compatible with B and A, then (a1 f a2) = (f (a1) B f (a2)) (g(f (a1)) A g(f (a2))). But, by Condition 1, g(f (ai)) 2 p-max([ai]f ). tu
Given A = hA; A; Ai a fuzzy preordered set wrt A and a surjective mapping f : A ! B compatible with A and B, our rst goal is to nd su cient conditions to de ne a suitable fuzzy preordering wrt B on B and a mapping g : B ! A compatible with B and A such that (f; g) is an adjoint pair. Lemma 2. Let A = hA; A; Ai be a fuzzy preorder and B be a fuzzy equivalence relation on B together with a surjective mapping f : A ! B compatible with
A and B. Suppose that p-max([a]f ) 6= ? for all a 2 A. Then, B = hB; B; Bi is a fuzzy preorder wrt B, where B is the fuzzy relation de ned as follows
B(b1; b2) = A(p-max([a1]f ); p-max([a2]f )) where ai 2 f 1(bi) for each i 2 f1; 2g.
Theorem 5 (Su cient conditions). Let A = hA; A; Ai be a fuzzy preorder wrt A and B be a fuzzy equivalence relation on B together with a surjective mapping f : A ! B compatible with A and B.
Suppose that the following conditions hold:
2. A(a1; a2) A(p-max([a1]f ),p-max([a2]f )), for all a1; a2 2 A. 3. (a1 f a2) (p-max([a1]f ) A (p-max([a2]f )), for all a1; a2 2 A.
(f; g) is a fuzzy adjunction between the fuzzy preorders A and B = hB; B; Bi, where B is the fuzzy relation introduced in Lemma 2.
Proof. Following Lemma 2, by Condition 1, there exists a fuzzy preordering B de ned as follows:
B(b1; b2) = A(p-max([a1]f ); p-max([a2]f )) where ai 2 f 1(bi) for each i 2 f1; 2g.
There is a number of suitable de nitions of g : B ! A, and all of them can be speci ed as follows: given b 2 B, we choose g(b) as an element xb 2 p-max([x]f ), where x is any element of f 1(b).
The existence of g is guaranteed by the axiom of choice, since f is surjective and for all b 2 B and for all x 2 f 1(b), the set p-max([x]f ) is nonempty. Moreover, g(b) does not depend on the preimage of b, because f (x) = f (y) = b implies [x]f = [y]f .
The compatibility of g with B and A follows from Condition 3: (b1
B b2) = (f (a1)
B f (a2)) = (a1 f a2) (c1
A c2) for all ai 2 f 1(bi) and ci 2 p-max([ai]f ), for i 2 f1; 2g. In particular, (b1 B b2) (g(b1) A g(b2)):
Now, due to Theorem 2, it su ces to prove that A(a; g(b)) = B(f (a); b), for all a 2 A; b 2 B:
Firstly, by Lemma 1, B(f (a); b) = A(u; v) for all u 2 p-max([a]f ) and v 2 p-max([z]f ) where z 2 f 1(b). Since, by its de nition, we have that g(b) 2 p-max([z]f ), we obtain B(f (a); b) = A(u; g(b)). Thus, we have to prove just that
A(u; g(b)) =
A(a; g(b)) for all u 2 p-max([a]f ).
Given u 2 p-max([a]f ), we have (f (a) B f (u)) = > and (f (a) B f (x)) A(x; u), for all x 2 A. In particular, (f (a) B f (a)) A(a; u), and then, since A is re exive, we obtain A(a; u) = >. Therefore,
A(u; g(b)) =
A(a; u)
A(u; g(b))
A(a; g(b))
On the other hand, for any x 2 f 1(b), we have that g(b) 2 p-max([x]f ), then (f (x) B f (g(b))) = > which implies that [g(b)]f = [x]f , by Remark 1. Applying Condition 2,
A(a; g(b))
A(p-max([a]f ); p-max([g(b)]f )) = =
A(p-max([a]f ); p-max([x]f )) =
B(f (a); b): tu 5
This work continues the research line initiated in [12{14] on the characterization of existence of adjunctions (and Galois connections) for mappings with unstructured codomain.
We have found necessary and su cient conditions under which, given a fuzzy ordering A on A and a surjective mapping f : hA; Ai ! hB; Bi compatible with respect to the fuzzy equivalences A and B, there exists a fuzzy ordering
B and a compatible mapping g : hB; Bi ! hA; Ai such that the pair (f; g) is a fuzzy adjunction.
As pieces of future work, on the one hand, the use of fuzzy equivalences can be taken into account in order to weaken the notion of surjective function and obtain an alternative proof based on this weaker notion. On the other hand, as stated in the introduction, considering surjective mappings is just the rst step in the canonical decomposition of a general mapping f : hA; Ai ! hB; Bi, therefore we will study how to extend the obtained ordering to the whole codomain in the case that f is not surjective.
Finally, as a midterm goal, we would like to study possible links of our
constructions with some recent e orts to develop a so-called theory of constructive
Galois connections [