On the Definition of Fuzzy Relational Galois Connections Between Fuzzy Transitive Digraphs

Abstract

We continue the study of different generalizations of the notion of Galois connection. Previously, we had focused on the cases in which both the domain and codomain had the structure of either a transitive digraph or a fuzzy transitive digraph. Here, we extend it to the fuzzy relational framework. Specifically, we present a suitable notion of fuzzy relational Galois connection between fuzzy transitive digraphs where both components are now fuzzy relations and the underlying truth value algebra is a complete Heyting algebra. The resulting notion of fuzzy relational Galois connection inherits interesting characterisations of the notion of (crisp) relational Galois connection.

1 Introduction

The notion of Galois connection [17] has been playing an important role in both mathematics and computer science [7] since it was introduced. One of our research lines is focused on the problem of constructing Galois connections: in a nutshell, given a mapping $f:A\rightarrow B$ between different structures (for instance, the domain A being a lattice and the codomain B a plain set), one wants to establish necessary and sufficient conditions under which it is possible to equip B with a desired structure and construct a mapping $g:B\rightarrow A$ such that the couple (f, g) is a Galois connection. It is important to note that the fact that A and B need not have the same structure rules out the application of Freyd’s adjoint functor theorem.

There have been different efforts to extend the notion of Galois connection to the fuzzy setting, and the degrees of freedom that come along with such efforts usually result in different levels of generality, and this is no different for the notion of fuzzy Galois connection [1, 2, 8, 9, 11,12,13,14,15,16, 18]. In previous works [3, 4] we explored the construction problem mentioned in the previous paragraph in various fuzzy settings, satisfactorily extending the problem to Galois connections between a fuzzy domain A and fuzzy range B. However, the proposed notion still has crisp functions as components, hence not obtaining a truly fuzzy notion of Galois connection.

Our approach to solve this situation is based on considering relations as components of the Galois connection. Recently, we focused on the cases of the domain A having the structure of a transitive digraph [5] or fuzzy transitive digraph [6], studying Galois connections whose left and right components are crisp relations satisfying certain reasonable properties expressed in terms of the so-called full powering. In this work, we expound for the first time an adequate notion of fuzzy relational Galois connection between fuzzy transitive digraphs, with both components now being fuzzy relations. The underlying algebraic setting for the truth values we are working with is that of a complete Heyting algebra. This notion of fuzzy relational Galois connection will be shown to inherit interesting equivalent characterizations of the notion of crisp Galois connection discussed in detail in [6].

2 Preliminary Notions

The framework considered in this work is that of $\mathbb L$-fuzzy set theory, where $\mathbb L$ is a complete Heyting algebra, which is an algebra $\mathbb L=(L,\le , \bot , \top , \rightarrow )$, where $(L,\le )$ is a complete lattice, $\bot$ is the bottom element, $\top$ is the top element, and the following adjointness property holds for all $p,q,r\in L$:

$$\begin{aligned} p\wedge q\le r \qquad \text { if and only if }\qquad p\le q\rightarrow r\,. \end{aligned}$$

An $\mathbb L$-fuzzy set on a universe A (also called $\mathbb L$-fuzzy subset of A) is a mapping $X:A\rightarrow \mathbb L$ from A to the algebra $\mathbb L$ of membership degrees, where X(a) denotes the degree to which element a belongs to X¹. A fuzzy set X is said to be normal if $X(a)=\top$ for some $a\in A$. Any element $a\in A$ induces a singleton, i.e., a fuzzy set $a:A\rightarrow \mathbb L$ defined by $a(x)=\top$ if $x=a$ and $a(x)=\bot$ otherwise.

An $\mathbb L$-fuzzy relation between two universes A and B is a mapping $\mu :A\times B\rightarrow \mathbb L$, where $\mu (a,b)$ denotes the degree of relationship between the elements a and b. Given a fuzzy relation $\mu$ and an element $a\in A$, the afterset $a^{\mu }$ of a is the fuzzy set $a^{\mu }:B \rightarrow \mathbb L$ defined by $a^{\mu }(b) =\mu (a,b)$. A fuzzy relation $\mu$ is said to be total if the aftersets $a^{\mu }$ are normal, for all $a\in A$.

The composition of an $\mathbb L$-fuzzy relation $\mu$ between two universes A and B and an $\mathbb L$-fuzzy relation $\nu$ between B and a universe C is the $\mathbb L$-fuzzy relation $\mu \circ \nu$ between A and C defined by

$$ \mu \circ \nu (a,c)=\bigvee _{b\in B} (\mu (a,b)\wedge \nu (b,c))\,. $$

An $\mathbb L$-fuzzy relation on a universe A is a mapping $\rho :A\times A\rightarrow \mathbb L$, and is said to be:

• reflexive if $\rho (a,a)=\top$, for all $a\in A$.

• transitive if $\rho (a,b)\wedge \rho (b,c)\le \rho (a,c)$, for all $a,b,c\in A$; or, equivalently, $\rho \circ \rho (a,c) \le \rho (a,c)$, for all $a,c\in A$.

Definition 1

$\mathbb A=\langle A, \rho \rangle$ is said to be a fuzzy T-digraph if $\rho$ is a transitive fuzzy relation on A.

In order to extend the definition of a relational Galois connection to the fuzzy framework considered in this paper, we need the notions of antitone and inflationary fuzzy relations between fuzzy T-digraphs.

Definition 2

Consider two fuzzy T-digraphs $\langle A,\rho _A\rangle$ and $\langle B,\rho _B\rangle$. A fuzzy relation $\mu :A\times B\rightarrow \mathbb L$ is said to be:

• antitone if $\rho _A(a_1,a_2)\wedge \mu (a_1,b_1)\wedge \mu (a_2,b_2)\le \rho _B (b_2,b_1)$, for all $a_1,a_2\in A$ and $b_1,b_2\in B$.

• isotone if $\rho _A(a_1,a_2)\wedge \mu (a_1,b_1)\wedge \mu (a_2,b_2)\le \rho _B(b_1,b_2)$, for all $a_1,a_2\in A$ and $b_1,b_2\in B$.

Definition 3

Let $\langle A,\rho \rangle$ be a fuzzy T-digraph. A fuzzy relation $\mu :A\times A\rightarrow \mathbb L$ is said to be:

• inflationary if $\mu (a_1,a_2)\le \rho (a_1,a_2)$, for all $a_1,a_2\in A$.

• idempotent if $\rho (x,y)=\rho (y,x)=\top$, for all $a\in A$, $x\in a^\mu$ and $y\in a^{\mu \circ \mu }$.

We recall that in the characterisation of relational Galois connections in the crisp case, a key role was played by the notion of clique [5]. Not surprisingly, a fuzzy version of this notion will play a similar role here.

Definition 4

Let $\langle A,\rho \rangle$ be a fuzzy T-digraph. A fuzzy set $X:A\rightarrow \mathbb L$ is called a clique if, for all $x,y\in A$, it holds that

$$\begin{aligned} X(x)\wedge X(y)\le \rho (x,y)\,. \end{aligned}$$

3 Fuzzy Powerings: Extending Relations to Fuzzy Powersets

Given a relation R on a set A, it is possible to lift R to the powerset $2^A$ by defining the following powerings, for all $X, Y \in 2^A$, which correspond to the construction of the Hoare, Smyth and full powersets, respectively:

$$\begin{aligned} X\, R_H\, Y\quad&\iff \quad (\forall x\in X)(\exists y\in Y) (x R y)\\ X\, R_S \,Y\quad&\iff \quad (\forall y\in Y)(\exists x\in X) (x R y)\\ X\, R_\propto \, Y\quad&\iff \quad (\forall x\in X)(\forall y\in Y) (x R y)\,. \end{aligned}$$

Note that if R is reflexive and transitive, then the two first relations defined above are actually preorder relations, specifically those used in the construction of the, respectively, Hoare and Smyth powerdomains; the third one need not be either reflexive nor transitive, and was introduced as a convenient tool to develop relational Galois connections. Nevertheless, it satisfies the following weakened version of transitivity:

$$\begin{aligned} \text {if }X\, R_{\propto }\, Y,\text { and }Y\, R_{\propto }\, Z,\text { where }Y\ne \varnothing ,\text { then }X\, R_{\propto }\, Z. \end{aligned}$$

(1)

Furthermore, it is worth noting that the powerings can be defined for any relation not necessarily being a preorder.

The adaptation of these powerings to the present fuzzy framework is explained next [10].

Definition 5

Consider a fuzzy T-digraph $\langle A,\rho \rangle$. We define the Hoare, Smyth and full fuzzy powerings as follows, for any $X, Y:A\rightarrow \mathbb L$:

• (i) $\rho _H(X, Y)=\displaystyle \bigwedge _{x\in A}\left( X(x)\rightarrow \bigvee _{y\in A}( Y(y)\wedge \rho (x,y))\right)$ ;

• (ii) $\rho _S(X, Y)=\displaystyle \bigwedge _{y\in A}\left( Y(y) \rightarrow \bigvee _{x\in A} (X(x)\wedge \rho (x,y))\right)$ ;

• (iii) $\rho _{\propto }(X,Y)=\displaystyle \bigwedge _{x\in A} \bigwedge _{y\in A} \left( X(x)\wedge Y(y) \rightarrow \rho (x,y)\right)$ .

As in the crisp case, both Hoare and Smyth powerings are reflexive and transitive fuzzy relations on $L^A$ whenever $\rho$ is. Once again, full fuzzy powering is somehow transitive in the same sense as in (1).

Lemma 1

Consider a fuzzy T-digraph $\langle A,\rho \rangle$ and fuzzy sets $X,Y,Z:A\rightarrow \mathbb L$. If Y is normal, then $\rho _\propto (X,Y)\wedge \rho _\propto (Y,Z)\le \rho _\propto (X,Z)$.

In the particular case of singletons in the first argument of the fuzzy powerings, the expressions in the above definitions are greatly simplified. Indeed, for all $a\in A$, it holds:

• (i) $\rho _H(a, Y )=\displaystyle \bigvee _{y\in A}(Y(y)\wedge \rho (a,y))$;

• (ii) $\rho _S(a, Y)=\rho _\propto (a, Y)=\displaystyle \bigwedge _{y\in A}(Y(y)\rightarrow \rho (a,y))$.

Notice that cliques can be characterized in terms of this relations: a fuzzy set $X:A\rightarrow \mathbb L$ is called a clique if $\rho _\propto (X,X)=\top$.

The following lemma establishes the relationship between the fuzzy powerings defined above.

Lemma 2

Consider a fuzzy T-digraph $\langle A,\rho \rangle$, a fuzzy set $X:A\rightarrow \mathbb L$ and $a\in A$.

• (i) If X is a normal fuzzy set, then

  $$ \rho _S(a,X)=\rho _\propto (a,X) \le \rho _H(a,X)\,. $$

• (ii) If X is a clique, then

  $$ \rho _H (a,X) \le \rho _S(a,X) =\rho _\propto (a,X)\,. $$

Finally, notions of antitone/isotone fuzzy relations, inflationarity and idempotency can be stated in terms of the full fuzzy powering $\propto$.

Consider two fuzzy T-digraphs $\langle A,\rho _A\rangle$ and $\langle B,\rho _B\rangle$. A fuzzy relation $\mu :A\times B\rightarrow \mathbb L$ is said to be:

• antitone if $\rho _A(a_1,a_2)\le {\rho _B}_{\propto }(a_2^{\mu }, a_1^{\mu })$, for all $a_1,a_2\in A$ and $b_1,b_2\in B$.

• isotone if $\rho _A(a_1,a_2)\le {\rho _B}_{\propto }(a_1^{\mu }, a_2^{\mu })$, for all $a_1,a_2\in A$ and $b_1,b_2\in B$.

Let $\langle A,\rho \rangle$ be a fuzzy T-digraph. A fuzzy relation $\mu :A\times A\rightarrow \mathbb L$ is said to be:

• inflationary if $\rho _{\propto }(a,a^{\mu })=\top$, for all $a\in A$.

• idempotent if $\rho _{\propto }(a^{\mu \circ \mu },a^\mu )=\top$ and $\rho _{\propto }(a^\mu ,a^{\mu \circ \mu })=\top$, for all $a\in A$.

4 Fuzzy Relational Galois Connections Between Fuzzy T-Digraphs

The next definition follows the classical approach of Galois connection instantiated on fuzzy transitive digraphs.

Definition 6

Consider two fuzzy T-digraphs $\langle A,\rho _A\rangle$ and $\langle B,\rho _B\rangle$ and two total fuzzy relations $\mu :A\times B\rightarrow \mathbb L$ and $\nu :B\times A\rightarrow \mathbb L$. We say that the couple $(\mu , \nu )$ is a fuzzy relational Galois connection if both $\mu$ and $\nu$ are antitone and both $\mu \circ \nu$ and $\nu \circ \mu$ are inflationary.

This definition is usually followed by a characterization in terms of the so-called Galois condition. We explore if it remains valid on this framework.

Definition 7

Consider two fuzzy T-digraphs $\langle A,\rho _A\rangle$ and $\langle B,\rho _B\rangle$ and two total fuzzy relations $\mu :A\times B\rightarrow \mathbb L$ and $\nu :B\times A\rightarrow \mathbb L$. We say that the couple $(\mu ,\nu )$ satisfies the fuzzy Galois condition if the following holds for all $a_1,a_2\in A$ and $b_1,b_2\in B$:

• (i) $\rho _A(a_1,a_2)\wedge \mu (a_1,b_1)\wedge \nu (b_2,a_2)\le \rho _B(b_2,b_1)$;

• (ii) $\rho _B(b_2,b_1)\wedge \mu (a_1,b_1)\wedge \nu (b_2,a_2)\le \rho _A(a_1,a_2)$;

or, equivalently, for all $a \in A$ and $b \in B$:

• (i) ${\rho _A}_H(a, b^\nu )\le {\rho _B}_S(b, a^\mu )$;

• (ii) ${\rho _B}_H(b, a^\mu )\le {\rho _A}_S(a, b^\nu )$.

The following example shows that the fuzzy Galois condition is not sufficient to ensure that a couple of fuzzy relations is a fuzzy relational Galois connection.

Example 1

Consider the fuzzy T-digraphs $\mathbb A=\langle \{ a_{1}, a_{2}, a_{3},a_4\}, \rho _{A}\rangle$ and $\mathbb B=\langle \{ b_{1}, b_{2}, b_{3}\}, \rho _{B}\rangle$, and the fuzzy relations $\mu :A\times B \rightarrow [0,1]$ and $\nu :B\times A \rightarrow [0,1]$ defined below:

$$ \begin{array}{c|cccc} \rho _{A} &{} a_{1}&{} a_{2} &{}a_{3}&{}a_4 \\ \hline a_{1} &{} 0.5&{} 1 &{} 1&{}0 \\ a_{2} &{} 0.5&{} 1 &{} 1&{}0 \\ a_{3} &{} 0.5&{} 0.5 &{} 1&{}0 \\ a_{4} &{} 0 &{} 0 &{}0&{} 1 \end{array} \qquad \begin{array}{c|ccc} \rho _{B} &{} b_{1}&{} b_{2} &{}b_{3} \\ \hline b_{1} &{} 1&{} 0 &{}0 \\ b_{2} &{} 0&{} 1 &{}1 \\ b_{3} &{} 0&{} 1 &{}1 \end{array} \qquad \begin{array}{c|ccc} \mu &{} b_{1}&{} b_{2} &{}b_{3} \\ \hline a_{1} &{} 1&{} 0.5 &{} 0 \\ a_{2} &{} 1&{} 0.4 &{}0 \\ a_{3} &{} 1 &{} 0.3 &{} 0\\ a_{4} &{} 0 &{} 0 &{} 1 \end{array} \quad \begin{array}{c|cccc} \nu &{} a_{1}&{} a_{2} &{}a_{3}&{}a_4 \\ \hline b_{1} &{} 0&{} 0.5 &{} 1&{}0 \\ b_{2} &{} 0&{} 0 &{}0 &{}1 \\ b_{3} &{} 0 &{} 0 &{} 0&{}1 \end{array} $$

It is routine to check that $(\mu ,\nu )$ satisfies the fuzzy Galois condition, although it is not a fuzzy relational Galois connection, since $\mu \circ \nu$ is not inflationary. Indeed, for instance, $(\mu \circ \nu )(a_1,a_4)=0.5\not \le \rho _A(a_1,a_4)=0$.    $\square$

As said above, we need to add the clique condition to the aftersets in order to get the desired characterization.

Theorem 1

Consider two fuzzy T-digraphs $\langle A,\rho _A\rangle$ and $\langle B,\rho _B\rangle$ and two total fuzzy relations $\mu :A\times B\rightarrow \mathbb L$ and $\nu :B\times A\rightarrow \mathbb L$. The couple $(\mu , \nu )$ is a fuzzy relational Galois connection between $\langle A,\rho _A\rangle$ and $\langle B,\rho _B\rangle$ if and only if the following conditions hold:

• (i) $(\mu , \nu )$ satisfies the fuzzy Galois condition;

• (ii) $a^\mu$ and $b^\nu$ are cliques, for all $a\in A$ and $b\in B$.

Now, by using Lemma 2, we can give the previous result in terms of the full powering where the fuzzy Galois condition can be expressed as an equality.

Corollary 1

Consider two fuzzy T-digraphs $\langle A,\rho _A\rangle$ and $\langle B,\rho _B\rangle$ and two total fuzzy relations $\mu :A\times B\rightarrow \mathbb L$ and $\nu :B\times A\rightarrow \mathbb L$. The couple $(\mu , \nu )$ is a fuzzy relational Galois connection between $\langle A,\rho _A\rangle$ and $\langle B,\rho _B\rangle$ if and only if the following conditions hold, for all $a\in A$ and $b\in B$:

• (i) ${\rho _A}_\propto (a, b^\nu ) = {\rho _B}_\propto (b, a^\mu )$;

• (ii) $a^\mu$ and $b^\nu$ are cliques.

5 Conclusions and Future Works

A new generalization of the notion of Galois connection has been introduced. Building upon previous approaches, we have given a suitable notion of fuzzy relational Galois connection between fuzzy transitive digraphs where both components are fuzzy relations and the underlying truth values belong to a complete Heyting algebra. The resulting notion inherits interesting properties of the notion of crisp relational Galois connection.

As immediate future work, working with this definition, we will focus on the characterisation of existence and the construction of the right adjoint to a mapping from a fuzzy T-digraph to an unstructured set.