=Paper=
{{Paper
|id=Vol-1624/paper8
|storemode=property
|title=On the Existence of Right Adjoints for Surjective Mappings between Fuzzy Structures
|pdfUrl=https://ceur-ws.org/Vol-1624/paper8.pdf
|volume=Vol-1624
|authors=Inma P. Cabrera,Pablo Cordero,Francisca García-Pardo,Manuel Ojeda-Aciego,Bernard De Baets
|dblpUrl=https://dblp.org/rec/conf/cla/CabreraCGOB16
}}
==On the Existence of Right Adjoints for Surjective Mappings between Fuzzy Structures==
https://ceur-ws.org/Vol-1624/paper8.pdf
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