On the Existence of Right Adjoints for Surjective Mappings between Fuzzy Structures Inma P. Cabrera1 , Pablo Cordero1 Francisca Garcı́a-Pardo1 , Manuel Ojeda-Aciego, and Bernard De Baets2 1 Universidad de Málaga. Dept. Matemática Aplicada. Andalucı́a Tech. Spain. ? 2 KERMIT. 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 ρA on A and a surjective mapping f : hA, ≈A i → hB, ≈B i com- patible with respect to the fuzzy equivalences ≈A and ≈B . Specifically, the problem is to find a fuzzy ordering ρB and a compatible mapping g : hB, ≈B i → hA, ≈A i such that the pair (f, g) is a fuzzy adjunction. 1 Introduction Adjunctions, also called isotone Galois connections, are often used in mathemat- ics in order to relate two (apparently disparate) theories, allowing for mutual cooperative advantages. A number of papers are being published on the applications (both theoret- ical and practical) of Galois connections and adjunctions. One can find mainly theoretical papers [10,15,17,23], as well as general applications to computer sci- ence, 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ělohlávek and Konečný [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 different 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 f in the general framework in which a mapping f : A → B from a (pre-)ordered set A into an unstructured set B is considered, aiming at characterizing those situations in which B can 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 f with 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 adjunc- tions have been written since its introduction by Bělohlávek in [1]; consider for instance [4, 9, 19, 27] for some recent generalizations. Some authors have intro- duced 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 ≈A and ≈B defined on A and B respectively 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 ρA on A and a surjective mapping f : hA, ≈A i → hB, ≈B i compatible with respect to the fuzzy equivalences ≈A and ≈B . Specifically, the problem is to characterize when there exists a fuzzy ordering ρB and a compatible mapping g : hB, ≈B i → hA, ≈A i 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 L- fuzzy 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 ∈ 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: – Reflexive if R(a, a) = > for all a ∈ U . – ⊗-Transitive if R(a, b) ⊗ R(b, c) ≤ R(a, c) for all a, b, c ∈ U . – Symmetric if R(a, b) = R(b, a) for all a, b ∈ U . From now on, when no confusion arises, we will omit the prefix “L-”. Definition 1. A fuzzy preordered set is a pair A = hA, ρA i in which ρA is a reflexive and ⊗-transitive fuzzy relation on A. Definition 2. Let A = hA, ρA i be a fuzzy preordered set. The extensions to the fuzzy setting of the notions of upset and downset of an element a ∈ A are defined by a↑ , a↓ : A → L where a↓ (u) = ρA (u, a) and a↑ (u) = ρA (a, u) for all u ∈ A. Definition 3. An element m ∈ A is a maximum for a fuzzy set X : A → L if 1. X(m) = > and 2. X ⊆ m↓ , i.e., X(u) ≤ ρA (u, m) for all u ∈ A. 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 X will be denoted p-max(X), respectively p-min(X). Definition 4. Let A = hA, ρA i and B = hB, ρB i be fuzzy preordered sets. 1. A mapping f : A → B is said to be isotone if ρA (a1 , a2 ) ≤ ρB (f (a1 ), f (a2 )) for all a1 , a2 ∈ A. 2. A mapping f : A → A is said to be inflationary if ρA (a, f (a)) = > for all a ∈ A. Similarly, f is deflationary if ρA (f (a), a) = > for all a ∈ 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 defined as f −1 (Y )(a) = Y (f (a)), for all a ∈ A. The definition of fuzzy adjunction given in [11] was the expected extension of that in the crisp case. Namely, Definition 5. Let A = hA, ρA i, B = hB, ρB i be fuzzy orders, and two mappings f : A → B and g : B → A. The pair (f, g) forms a fuzzy adjunction between A and B, denoted (f, g) : A B if, for all a ∈ A and b ∈ B, 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, ρA i, B = hB, ρB i be two fuzzy preordered sets, respectively, and f : A → B and g : B → A be two mappings. The following statements are equivalent: 1. (f, g) : A B. 2. f and g are isotone, g ◦ f is inflationary, and f ◦ g is deflationary. 3. f (a)↑ = g −1 (a↑ ) for all a ∈ A. 4. g(b)↓ = f −1 (b↓ ) for all b ∈ B. 5. f is isotone and g(b) ∈ p-max f −1 (b↓ ) for all b ∈ B. 6. g is isotone and f (a) ∈ p-min g −1 (a↑ ) for all a ∈ A. 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 A is 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, for all a, b ∈ A. We will use the infix notation for a fuzzy equivalence relation, that is, we will write a1 ≈ a2 instead of ≈ (a1 , a2 ). Definition 7. Given a fuzzy equivalence relation ≈ : A × A → L, the equiv- alence class of an element a ∈ A is the fuzzy set [a]≈ : A → L defined by [a]≈ (u) = (a ≈ u) for all u ∈ A. 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 u ∈ A; the other inequality follows similarly. Definition 8 (See [6]). Given a fuzzy equivalence relation ≈A on A, a fuzzy binary relation ρA : A × A → L is said to be – ≈A -reflexive if (a1 ≈A a2 ) ≤ ρA (a1 , a2 ), – ⊗-≈A -antisymmetric if ρA (a1 , a2 ) ⊗ ρA (a2 , a1 ) ≤ (a1 ≈A a2 ), for all a1 , a2 ∈ A. Definition 9. A triplet A = hA, ≈A , ρA i in which ≈A is a fuzzy equivalence relation and ρA is ≈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 ≈A is a fuzzy preorder relation because > = (a ≈A a) ≤ ρA (a, a), therefore ρA (a, a) = >, for all a ∈ A. Definition 10. Let ≈A and ≈B be fuzzy equivalence relations on the sets A and B, respectively. A mapping f : A → B is said to be compatible with ≈A and ≈B if (a1 ≈A a2 ) ≤ (f (a1 ) ≈B f (a2 )) for all a1 , a2 ∈ A. 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 , ρA i and B = hB, ≈B , ρB i 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: Definition 11. Let A = hA, ≈A , ρA i and B = hB, ≈B , ρB i be two fuzzy pre- ordered 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 ) ⊗ ρA (a2 , g(b)) ≤ ρB (f (a1 ), b) (A2) (b1 ≈B b2 ) ⊗ ρB (f (a), b1 ) ≤ ρA (a, g(b2 )) for all a, a1 , a2 ∈ A and b, b1 , b2 ∈ B. 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 , ρA i and B = hB, ≈B , ρB i 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. Then, the pair (f, g) is a fuzzy adjunction between A and B if and only if ρA (a, g(b)) = ρB (f (a), b) for all a ∈ A and b ∈ B. Proof. Assume that for all a ∈ A and b ∈ B the equality ρA (a, g(b)) = ρB (f (a), b) holds. Let a1 , a2 ∈ A and b ∈ 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 -reflexive 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 ∈ A and b ∈ B. Analogously, the condition (A2) holds. Conversely, assume now that conditions (A1) and (A2) hold. Applying condi- tion (A1), for a ∈ A and b ∈ B, we have that (a ≈A a)⊗ρA (a, g(b)) ≤ ρB (f (a), b). Being ≈A reflexive, it is deduced that ρA (a, g(b)) ≤ ρB (f (a), b) for all a ∈ A and b ∈ B. Analogously, ρB (f (a), b) ≤ ρA (a, g(b)) for all a ∈ A and b ∈ B. Therefore, ρA (a, g(b)) = ρB (f (a), b) for all a ∈ A and b ∈ B. t u Corollary 1. If a pair (f, g) is a fuzzy adjunction between hA, ≈A , ρA i and hB, ≈B , ρB i then (f, g) is also a fuzzy adjunction between the two fuzzy pre- ordered sets hA, ρA i and hB, ρB i. Conversely, if a pair (f, g) is a fuzzy adjunction between hA, ρA i and hB, ρB i then (f, g) is also a fuzzy adjunction between hA, =, ρA i and hB, =, ρB i, 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 f and g need to be compatible with fuzzy equivalence relations ≈A on A and ≈B on 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 , x2 ∈ p-max(X), note that ρA (x1 , x2 ) = > = ρA (x2 , x1 ): on the one hand, by x1 ∈ p-max(X), we have that X(x1 ) = > and since x2 ∈ p-max(X), then X(u) ≤ ρA (u, x2 ) for all u ∈ A. Hence, > = X(x1 ) ≤ ρA (x1 , x2 ) which implies that ρA (x1 , x2 ) = >. Likewise, by ⊗-≈A -antisymmetry, also (x1 ≈A x2 ) = > for x1 , x2 ∈≈A - max(X). Theorem 3. Let A = hA, ≈A , ρA i and B = hB, ≈B , ρB i be two fuzzy preordered  between A and B then (f ◦g◦f )(a) ≈B sets.If the pair (f, g) is a fuzzy adjunction f (a) = > and (g ◦ f ◦ g)(b) ≈A g(b) = >, for all a ∈ A, b ∈ B. Proof. Since f is isotone and g ◦ f is inflationary 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. t u Corollary 2. Let A = hA, ≈A , ρA i and B = hB, ≈B , ρB i be two fuzzy preordered sets. If the pair (f, g) is a fuzzy adjunction between A and B then, for all a ∈ A, b ∈ 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 , ρA i and B = hB, ≈B , ρB i be two fuzzy preordered sets. If the pair (f, g) is a fuzzy adjunction between A and B then, for all a1 , a2 ∈ A and b1 , b2 ∈ B, the following equalities hold:   (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 first item, since the second one is similar.  Given a1 , a2 ∈ 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) ≈B f (g(f (a))) = >, for all a ∈ A. Finally, the ⊗-transitivity of ≈B leads to  f (g(f (a1 ))) ≈B f (g(f (a2 )))   = 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 (g(f (a2 ))) ⊗ f (g(f (a2 ))) ≈B f (a2 )  ≤ f (a1 ) ≈B f (a2 ) t u 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 , ρA i and B = hB, ≈B , ρB i be two fuzzy pre- ordered 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 defined as follows for a1 , a2 ∈ 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 ∈ A is a fuzzy set denoted by [a]f : A → L defined by [a]f (u) = (f (a) ≈B f (u)) for all u ∈ A. 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 , ρA i be a fuzzy preordered set wrt a fuzzy equiv- alence relation ≈A . For C, D crisp subsets of A, consider the following notation _ _ – (C vW D) = ρA (c, d) c∈C d∈D ^ _ – (C vH D) = ρA (c, d) c∈C d∈D ^ ^ – (C vS D) = ρA (c, d) c∈C d∈D Lemma 1. Let A = hA, ≈A , ρA i 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 ∈ p-max(X) and y ∈ p-max(Y ). Proof. Let us show that ρA (x, y) = ρA (x̄, ȳ), for any x, x̄ ∈ p-max(X) and y, ȳ ∈ 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̄, ȳ) ⊗ ρA (ȳ, y) = ρA (x̄, ȳ). Analogously, ρA (x̄, ȳ) ≥ ρA (x, y). Therefore, ρA (x̄, ȳ) = ρA (x, y) for any x, x̄ ∈ p-max(X) and y, ȳ ∈ p-max(Y ). t u Notice that, by Lemma 1, when both sets are non-empty,  for any x ∈ p-max(X) and y ∈ p-max(Y ), p-max(X) vH p-max(Y ) = ρA (x, y) and this justifies the following notation. Notation 1 Let A = hA, ≈A , ρA i be a fuzzy preorder wrt a fuzzy equivalence re- lation ≈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 , ρA i be a fuzzy preorder wrt a fuzzy equivalence relation ≈A and X, Y ⊆ A. Observe that for all x1 , x2 ∈ p-max(X) and y1 , y2 ∈ 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 ∈ p-max(X), y ∈ p-max(Y ). Theorem 4 (Necessary conditions). Let A = hA, ≈A , ρA i, B = hB, ≈B , ρB i be two fuzzy preorders and f : A → B, g : B → A two mappings which are com- patible with the equivalence relations ≈A and ≈B . If (f, g) is a fuzzy adjunction between A and B then 1. p-max([a]f ) is non-empty for all a ∈ A. 2. ρA (a1 , a2 ) ≤ ρA (p-max([a1 ]f ),p-max([a2 ]f )), for all a1 , a2 ∈ A. 3. (a1 ≡f a2 ) ≤ (p-max([a1 ]f ) ≈A p-max([a2 ]f )), for all a1 , a2 ∈ A. Proof. – Condition 1. We will show that g(f (a)) ∈ p-max([a]f ): By Theorem 3, we have (f (a) ≈B f (g(f (a)))) = >. On the other hand, using the ≈B -reflexivity and that (f, g) is a fuzzy ad- junction, for all u ∈ 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 ∈ A. We have just shown that g(f (a)) ∈ p-max([a]f ) for all a ∈ A, thus, from Lemma 1, we obtain that ρA (a1 , a2 ) ≤ ρA (p-max([a1 ]f ), p-max([a2 ]f )) for all a1 , a2 ∈ 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 )) ∈ p-max([ai ]f ). t u Given A = hA, ≈A , ρA i a fuzzy preordered set wrt ≈A and a surjective map- ping f : A → B compatible with ≈A and ≈B , our first goal is to find sufficient conditions to define 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 , ρA i be a fuzzy preorder and ≈B be a fuzzy equiva- lence 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 ∈ A. Then, B = hB, ≈B , ρB i is a fuzzy preorder wrt ≈B , where ρB is the fuzzy relation defined as follows ρB (b1 , b2 ) = ρA (p-max([a1 ]f ), p-max([a2 ]f )) where ai ∈ f −1 (bi ) for each i ∈ {1, 2}. Theorem 5 (Sufficient conditions). Let A = hA, ≈A , ρA i 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: 1. p-max([a]f ) is non-empty for all a ∈ A. 2. ρA (a1 , a2 ) ≤ ρA (p-max([a1 ]f ),p-max([a2 ]f )), for all a1 , a2 ∈ A. 3. (a1 ≡f a2 ) ≤ (p-max([a1 ]f ) ≈A (p-max([a2 ]f )), for all a1 , a2 ∈ A. Then, there exists a mapping g : B → A compatible with ≈A and ≈B such that (f, g) is a fuzzy adjunction between the fuzzy preorders A and B = hB, ≈B , ρB i, where ρB is 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 , b2 ) = ρA (p-max([a1 ]f ), p-max([a2 ]f )) where ai ∈ f −1 (bi ) for each i ∈ {1, 2}. There is a number of suitable definitions of g : B → A, and all of them can be specified as follows: given b ∈ B, we choose g(b) as an element xb ∈ 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 ∈ B and for all x ∈ 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 ∈ f −1 (bi ) and ci ∈ p-max([ai ]f ), for i ∈ {1, 2}. In particular, (b1 ≈B b2 ) ≤ (g(b1 ) ≈A g(b2 )). Now, due to Theorem 2, it suffices to prove that ρA (a, g(b)) = ρB (f (a), b), for all a ∈ A, b ∈ B: Firstly, by Lemma 1, ρB (f (a), b) = ρA (u, v) for all u ∈ p-max([a]f ) and v ∈ p-max([z]f ) where z ∈ f −1 (b). Since, by its definition, we have that g(b) ∈ 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 ∈ p-max([a]f ). Given u ∈ p-max([a]f ), we have (f (a) ≈B f (u)) = > and (f (a) ≈B f (x)) ≤ ρA (x, u), for all x ∈ A. In particular, (f (a) ≈B f (a)) ≤ ρA (a, u), and then, since ≈A is reflexive, 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 ∈ f −1 (b), we have that g(b) ∈ 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). t u 5 Conclusions This work continues the research line initiated in [12–14] on the characterization of existence of adjunctions (and Galois connections) for mappings with unstruc- tured codomain. We have found necessary and sufficient conditions under which, given a fuzzy ordering ρA on A and a surjective mapping f : hA, ≈A i → hB, ≈B i compatible with respect to the fuzzy equivalences ≈A and ≈B , there exists a fuzzy ordering ρB and a compatible mapping g : hB, ≈B i → hA, ≈A i 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 first step in the canonical decomposition of a general mapping f : hA, ≈A i → hB, ≈B i, 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 con- structions with some recent efforts to develop a so-called theory of constructive Galois connections [7] aimed at introducing adjunctions and Galois connections within automated proof checkers. References 1. R. Bělohlávek. Fuzzy Galois connections. Mathematical Logic Quarterly, 45(4):497– 504, 1999. 2. R. Bělohlávek. Fuzzy relational systems: foundations and principles. Kluwer, 2002. 3. R. Bělohlávek and J. Konecny Concept lattices of isotone vs. antitone Galois connections in graded setting: Mutual reducibility revisited. Information Sciences 199:133–137, 2012. 4. R. Bělohlávek. and P. Osička. Triadic fuzzy Galois connections as ordinary con- nections. In IEEE Intl Conf on Fuzzy Systems, 2012. 5. U. Bodenhofer and F. Klawonn. A formal study of linearity axioms for fuzzy orderings. Fuzzy Sets and Systems 145(3):323–354, 2004. 6. U. Bodenhofer, B. De Baets and J. Fodor. A compendium of fuzzy weak orders: Representations and constructions. Fuzzy Sets and Systems 158(8):811–829, 2007. 7. D. Darais and D. Van Horn. Constructive Galois Connections: Taming the Galois Connection Framework for Mechanized Metatheory. arXiv:1511.06965, 2015. 8. J. Denniston, A. Melton, and S.E. Rodabaugh. Formal Contexts, Formal Con- cept Analysis, and Galois Connections. Electronic Proc. in Theoretical Computer Science 129:105–120, 2013. 9. A. Frascella. Fuzzy Galois connections under weak conditions. Fuzzy Sets and Systems, 172(1):33–50, 2011. 10. J. G. Garcı́a, I. Mardones-Pérez, M. A. de Prada-Vicente, and D. Zhang. Fuzzy Galois connections categorically. Math. Log. Q., 56(2):131–147, 2010. 11. F. Garcı́a-Pardo, I.P. Cabrera, P. Cordero, and M. Ojeda-Aciego. On Galois con- nections and Soft Computing. Lect. Notes in Computer Science, 7903:224–235, 2013. 12. F. Garcı́a-Pardo, I.P. Cabrera, P. Cordero, and M. Ojeda-Aciego. On the construc- tion of fuzzy Galois connections. Proc. of XVII Spanish Conference on Fuzzy Logic and Technology, pages 99-102, 2014. 13. F. Garcı́a-Pardo, I.P. Cabrera, P. Cordero, and M. Ojeda-Aciego. On adjunctions between fuzzy preordered sets: necessary conditions. Lect. Notes in Computer Science, 8536,pp. 211–221, 2014. 14. F. Garcı́a-Pardo, I.P. Cabrera, P. Cordero, M. Ojeda-Aciego, and F.J. Rodrı́guez. On the definition of suitable orderings to generate adjunctions over an unstructured codomain. Information Sciences 286:173–187, 2014. 15. G. Georgescu and A. Popescu. Non-commutative fuzzy Galois connections. Soft Computing, 7(7):458–467, 2003. 16. J. Gibbons, F. Henglein, R. Hinze, and N. Wu. Relational Algebra by way of Adjunctions. In Proc of Databases and Programming Languages (DBLP), 2015 17. J. Järvinen. Pawlak’s information systems in terms of Galois connections and functional dependencies. Fundamenta Informaticae, 75:315–330, 2007. 18. J. Järvinen, M. Kondo, and J. Kortelainen. Logics from Galois connections. Int. J. Approx. Reasoning, 49(3):595–606, 2008. 19. J. Konecny. Isotone fuzzy Galois connections with hedges. Information Sciences, 181(10):1804–1817, 2011. 20. L. Lumpe and S.E. Schmidt. Pattern Structures and Their Morphisms. In Proc. of Concept Lattices and Their Applications (CLA), CEUR Workshop Proceedings 1466:171–179, 2015 21. A. Melton, D.A. Schmidt, and G.E. Strecker. Galois connections and computer science applications. Lect. Notes in Computer Science, 240:299–312, 1986. 22. S.-C. Mu and J. Oliveira. Programming from Galois connections. Journal of Logic and Algebraic Programming, 81(6):680–704, 2012. 23. M. Nowak A Proof of Tarski’s Fixed Point Theorem by Application of Galois Connections. Studia Logica 103(2):287–301, 2014 24. Y. Shi, M. Nachtegael, D. Ruan, and E. Kerre Fuzzy adjunctions and fuzzy morpho- logical operations based on implications. Intl J of Intelligent Systems 24(12):1280– 1296, 2009. 25. F.J. Valverde-Albacete, C. Peláez-Moreno, and C. del Campo. Activating Gener- alized Fuzzy Implications from Galois Connections. In Enric Trillas: A passion for fuzzy sets, Studies in Fuzzy Sets and Soft Computing 322:201–212, 2015. 26. M. Wolski. Galois connections and data analysis. Fundamenta Informaticae, 60:401–415, 2004. 27. W. Yao and L.-X. Lu. Fuzzy Galois connections on fuzzy posets. Mathematical Logic Quarterly 55:105–112, 2009