# Handling the inconsistency of systems of $\min\rightarrow$ fuzzy relational
equations

Ismaïl Baaj
Univ. Artois, CNRS, CRIL, F-62300 Lens, France
<EMAIL_ADDRESS>
###### Abstract

In this article, we study the inconsistency of systems of $\min-\rightarrow$
fuzzy relational equations. We give analytical formulas for computing the
Chebyshev distances $\nabla=\inf_{d\in\mathcal{D}}\|\beta-d\|$ associated to
systems of $\min-\rightarrow$ fuzzy relational equations of the form
$\Gamma\Box_{\rightarrow}^{\min}x=\beta$, where $\rightarrow$ is a residual
implicator among the Gödel implication $\rightarrow_{G}$, the Goguen
implication $\rightarrow_{GG}$ or Łukasiewicz’s implication $\rightarrow_{L}$
and $\mathcal{D}$ is the set of second members of consistent systems defined
with the same matrix $\Gamma$. The main preliminary result that allows us to
obtain these formulas is that the Chebyshev distance $\nabla$ is the lower
bound of the solutions of a vector inequality, whatever the residual
implicator used. Finally, we show that, in the case of the
$\min-\rightarrow_{G}$ system, the Chebyshev distance $\nabla$ may be an
infimum, while it is always a minimum for $\min-\rightarrow_{GG}$ and
$\min-\rightarrow_{L}$ systems.

_Keywords_ Fuzzy set theory ; fuzzy relational equations ; Chebyshev
approximations

##  1 Introduction

Sanchez’s pioneering work on solving systems of fuzzy relational equations
based on $\max-\min$ composition [13, 14] was followed by studies on solving
systems based on $\max-T$ composition [4, 7, 8] where $T$ is a t-norm, and
studies on systems based on $\min-\rightarrow$ composition [7, 9, 11], where
$\rightarrow$ is the residual implicator associated to a t-norm. The authors
of these studies gave necessary and sufficient conditions for systems of fuzzy
relational equations to be consistent. However, it remains difficult to
address the inconsistency of these systems.

Recently, to address this issue, the author of [2] gives an explicit
analytical formula to compute, using the $L_{\infty}$ norm, the Chebyshev
distance $\Delta=\inf_{c\in\mathcal{C}}\|b-c\|$ associated to an inconsistent
system of $\max-\min$ fuzzy relational equations $A\Box_{\min}^{\max}x=b$,
where $\mathcal{C}$ is the set of second members of consistent systems defined
with the same matrix $A$. From this Chebyshev distance and in the case that
the system $A\Box_{\min}^{\max}x=b$ is inconsistent, the author of [2]
describes the structure of the set of Chebyshev approximations of the second
member $b$, which is formed by the vectors $c$ such that $\|b-c\|=\Delta$ and
the system $A\Box_{\min}^{\max}x=c$ is a consistent system [3, 6]. He also
establishes a structure theorem for the approximate solutions set of the
inconsistent system, which is the set of solutions of consistent systems
$A\Box_{\min}^{\max}x=c$, where $c$ is a Chebyshev approximation of $b$. From
these results, the author introduces a learning paradigm of approximate weight
matrices based on $\max-\min$ composition according to training data.
In [1], the author extends some of these results for a system of max-product
fuzzy relational equations and for a system of max-Łukasiewicz fuzzy
relational equations. He gives analytical formulas for computing the Chebyshev
distance $\Delta$ associated to inconsistent systems based on max-product or
max-Łukasiewicz compositions. For these two systems, the greatest approximate
solution and the greatest Chebyshev approximation are directly computed
according to the components of the matrix and those of the second member of
the system, so the learning paradigm introduced in [2] can be used for the
max-product and max-Łukasiewicz systems.

In this article, analogously to [1, 2], for systems of $\min-\rightarrow$
fuzzy relational equations of the form
$\Gamma\Box_{\rightarrow}^{\min}x=\beta$ where $\Gamma$ is a fuzzy matrix of
size $(m,n)$, $\beta$ is a column-vector of $m$ components and $\rightarrow$
is a residual implicator among the Gödel implication $\rightarrow_{G}$, the
Goguen implication $\rightarrow_{GG}$ or Łukasiewicz’s implication
$\rightarrow_{L}$, we give explicit analytical formulas for computing the
Chebyshev distance $\nabla=\inf_{d\in\mathcal{D}}\|\beta-d\|$ where
$\mathcal{D}$ is the set of second members of consistent systems defined with
the same matrix $\Gamma$. Analogously to the application $F$ introduced in [1,
2] for systems based on $\max-T$ composition, we introduce an idempotent,
increasing and right-continuous application denoted $G$ for $\min-\rightarrow$
systems, see (24). The application $G$ allows us to reformulate the necessary
and sufficient conditions [7, 9, 11] for checking if a $\min-\rightarrow$
system defined with a fixed matrix and a given vector used as the second
member is a consistent system, see (25). As a first result (Theorem 1), this
application $G$ allows us to show that the Chebyshev distance $\nabla$ of a
$\min-\rightarrow$ system $\Gamma\Box_{\rightarrow}^{\min}x=\beta$ is the
lower bound of the solutions of a vector inequality expressed with this
application $G$. Our (Theorem 1) for $\min-\rightarrow$ systems, is the
version of (Theorem 1) of Cuninghame-Green and Cechlárová for a $\max-\min$
system [3], which was recently extended in [1] for $\max-T$ systems.
Furthermore, from this result, we obtain the decomposition of the Chebyshev
distance $\nabla=\max_{1\leq j\leq m}\nabla_{j}$ (Proposition 5), where for
all $j\in\\{1,2,\dots,m\\}$, each $\nabla_{j}$ is the lower bound of the
solutions of the $j$-th scalar inequality in the above-mentioned vector
inequality, see (36).
For each of the three systems of $\min-\rightarrow$ fuzzy relational equations
(depending on whether $\rightarrow$ is the Gödel implication
$\rightarrow_{G}$, the Goguen implication $\rightarrow_{GG}$ or Łukasiewicz’s
implication $\rightarrow_{L}$), we give an explicit formula for computing its
associated Chebyshev distance $\nabla$ ((Theorem 2), (Theorem 3) and (Theorem
5), respectively). We also prove the following important results: for
$\min-\rightarrow_{G}$ system, the Chebyshev distance $\nabla$ may be an
infimum (based on (Proposition 8) and showed in (Example 5)) while, for
$\min-\rightarrow_{GG}$ and $\min-\rightarrow_{L}$ systems, the Chebyshev
distance $\nabla$ is always a minimum i.e. an attainable lower bound (see
(Corollary 5) and (Corollary 8)). For $\min-\rightarrow_{G}$ systems, we give
a sufficient condition for $\nabla$ to be a minimum (see (Corollary 2) and
(Corollary 3)). For $\min-\rightarrow_{GG}$ systems, $\min-\rightarrow_{L}$
systems, or $\min-\rightarrow_{G}$ systems whose Chebyshev distance has been
verified as a minimum, we can always compute the lowest Chebyshev
approximation of the second member and an approximate solution (see (Corollary
4), (Corollary 7) and (Corollary 3)). However, for the $\min-\rightarrow_{G}$
systems whose Chebyshev distance has been verified as not being a minimum, the
set of Chebyshev approximations of its second member is empty (Lemma 7).

The article is structured as follows. In (Section 2), we remind the recent
results of [1, 2] on solving systems of $\max-T$ fuzzy relational equations,
where $T$ is a continuous t-norm. In (Section 3), we introduce our main tools
for studying the inconsistent systems of $\min-\rightarrow$ fuzzy relational
equations: the application $G$ and its main properties, and an important
decomposition of the Chebyshev distance $\nabla$ associated to a system of
$\min-\rightarrow$ fuzzy relational equations. Then, in the next three
sections, we give the explicit analytical formulas for computing the Chebyshev
distances $\nabla=\inf_{d\in\mathcal{D}}\|\beta-d\|$ in the case where the
residual implicator is the Gödel implication (Section 4), the Goguen
implication (Section 5) and Łukasiewicz’s implication (Section 6). Finally, we
conclude with some perspectives and we propose some applications of our work.

##  2 Background

In this section, we remind the necessary background for solving systems of
fuzzy relational equations. We reuse some notations of [1, 2] and denote by
$T$ a continuous t-norm and $\mathcal{I}_{T}$ its associated residual
implicator [5]. Finally, we present some recent results of [1, 2] on the
inconsistency of systems of $\max-T$ fuzzy relational equations.

###  2.1 Notations

The set $[0,1]^{n\times m}$ is the set of matrices of size $(n,m)$ i.e., $n$
rows and $m$ columns, whose components are in $[0,1]$, thus, the set
$[0,1]^{n\times 1}$ is the set of column vectors of $n$ components and
$[0,1]^{1\times m}$ denotes the set of row matrices of $m$ components.

The order relation $\leq$ on the set $[0,1]^{n\times m}$ is defined by:

$A\leq B\quad\text{iff we have}\quad a_{ij}\leq b_{ij}\quad\text{ for all
}\quad 1\leq i\leq n,1\leq j\leq m,$

where $A=[a_{ij}]_{1\leq i\leq n,1\leq j\leq m}$ and $B=[b_{ij}]_{1\leq i\leq
n,1\leq j\leq m}$.

For $x,y,z,u,\delta\in[0,1]$, we put:

  * •

$x^{+}=\max(x,0)$,

  * •

$\overline{z}(\delta)=\min(z+\delta,1)$,

  * •

$\underline{z}(\delta)=\max(z-\delta,0)=(z-\delta)^{+}$

and we have the following equivalence in $[0,1]$:

$\mid x-y\mid\leq\delta\Longleftrightarrow\underline{x}(\delta)\leq
y\leq\overline{x}(\delta).$ (1)

To a column-vector $b=[b_{i}]_{1\leq i\leq n}$ and a number $\delta\in[0,1]$,
we associate two column-vectors:

$\underline{b}(\delta)=[(b_{i}-\delta)^{+}]_{1\leq i\leq
n}\quad\text{and}\quad\overline{b}(\delta)=[\min(b_{i}+\delta,1)]_{1\leq i\leq
n}.$ (2)

Then, from (1), we deduce for any $c=[c_{i}]_{1\leq i\leq n}\in[0,1]^{n\times
1}$:

$\|b-c\|\leq\delta\Longleftrightarrow\underline{b}(\delta)\leq
c\leq\overline{b}(\delta).$ (3)

where $\|b-c\|=\max_{1\leq i\leq n}\mid b_{i}-c_{i}\mid$.

###  2.2 T-norms and their associated residual implicators

A triangular-norm (t-norm, see [5]) is a map $T:[0,1]\times[0,1]\mapsto[0,1]$,
which satisfies:

  * $T$ is commutative: $T(x,y)=T(y,x)$,

  * $T$ is associative: $T(x,T(y,z))=T(T(x,y),z)$,

  * $T$ is increasing : $x\leq x^{\prime}\quad\text{and}\quad y\leq y^{\prime}\,\Longrightarrow\,T(x,y)\leq T(x^{\prime},y^{\prime})$,

  * $T$ has $1$ as neutral element: $T(x,1)=x$.

To the t-norm $T$ is associated the residual implicator ${\cal
I}_{T}:[0,1]\times[0,1]\rightarrow[0,1]:(x,y)\mapsto{\cal
I}_{T}(x,y)=\sup\\{z\in[0,1]\,\mid\,T(x,z)\leq y\\}$.

For all $a,b\in[0,1]$, the main properties of the residual implicator ${\cal
I}_{T}$ associated to a continuous t-norm $T$ are:

  * •

${\cal I}_{T}(a,b)=\max\\{z\in[0,1]\,\mid\,T(a,z)\leq b\\}$. Therefore,
$T(a,{\cal I}_{T}(a,b))\leq b$.

  * •

${\cal I}_{T}$ is left-continuous and decreasing in its first argument as well
as right-continuous and increasing in its second argument.

  * •

For all $z\in[0,1]$, we have:

$T(a,z)\leq b\Longleftrightarrow z\leq{\cal I}_{T}(a,b).$

  * •

We have $\,b\leq{\cal I}_{T}(a,T(a,b))$.

The t-norm $\min$ denoted by $T_{M}$, has a residual implicator
$\mathcal{I}_{T_{M}}$ which is the Gödel implication:

$T_{M}(x,y)=\min(x,y)\quad;\quad{\cal
I}_{T_{M}}(x,y)=x\underset{G}{\longrightarrow}y=\begin{cases}1&\text{ if
}x\leq y\\\ \ y&\text{ if }x>y\end{cases}.$ (4)

The t-norm defined by the usual product is denoted by $T_{P}$. Its associated
residual implicator is the Goguen implication:

$T_{P}(x,y)=x\cdot y\quad;\quad{\cal
I}_{T_{P}}(x,y)=x\underset{GG}{\longrightarrow}y=\begin{cases}1&\text{ if
}x\leq y\\\ \frac{y}{x}&\text{ if }x>y\end{cases}.$ (5)

Łukasiewicz’s t-norm is denoted by $T_{L}$ and its associated residual
implicator ${\cal I}_{T_{L}}$:

$T_{L}(x,y)=\max(x+y-1,0)={(x+y-1)}^{+}\quad;\quad{\cal
I}_{T_{L}}(x,y)=x\underset{L}{\longrightarrow}y=\min(1-x+y,1).$ (6)

###  2.3 Solving systems of $\max-T$ fuzzy relational equations

A system of $\max-T$ fuzzy relational equations based on a matrix
$A=[a_{ij}]\in[0,1]^{n\times m}$ and a column-vector
$b=[b_{i}]\in[0,1]^{n\times 1}$ is of the form:

$(S):A\Box_{T}^{\max}x=b,$ (7)

where $x=[x_{j}]_{1\leq j\leq m}\in[0,1]^{m\times 1}$ is an unknown vector and
the matrix operator $\Box_{T}^{\max}$ is the matrix product that uses the
continuous t-norm $T$ as the product and $\max$ as the addition.

Using the vector

$e=A^{t}\Box_{{\cal I}_{T}}^{\min}b,$ (8)

where $A^{t}$ is the transpose of $A$ and the matrix product $\Box_{{\cal
I}_{T}}^{\min}$ uses the residual implicator ${\cal I}_{T}$ (associated to
$T$) as the product and $\min$ as the addition, we have the following
equivalence proved by Sanchez for $\max-\min$ composition [13], and extended
to $\max-T$ composition by Pedrycz [8, 10] and Miyakoshi and Shimbo [7]:

$A\Box_{T}^{\max}x=b\text{ is consistent}\Longleftrightarrow
A\Box_{T}^{\max}e=b.$ (9)

###  2.4 Chebyshev distance associated to the second member of a system of
$\max-T$ fuzzy relational equations

To the matrix $A$ and the second member $b$ of the system $(S)$ of $\max-T$
fuzzy relational equations, see (7), is associated the set of vectors
$c=[c_{i}]\in[0,1]^{n\times 1}$ such that the system $A\Box_{T}^{\max}x=c$ is
consistent:

$\mathcal{C}=\\{c=[c_{i}]\in{[0,1]}^{n\times 1}\mid A\Box_{T}^{\max}x=c\text{
is consistent}\\}.$ (10)

This set allows us to define the Chebyshev distance associated to the second
member $b$ of the system $(S)$.

######  Definition 1.

The Chebyshev distance associated to the second member $b$ of the system
$(S):A\Box_{T}^{\max}x=b$ is:

$\Delta=\Delta(A,b)=\inf_{c\in\mathcal{C}}\|b-c\|$ (11)

where:

$\|b-c\|=\max_{1\leq i\leq n}\mid b_{i}-c_{i}\mid.$

and

######  Definition 2.

A Chebyshev approximation of the second member $b$ is an element
$c\in\mathcal{C}$, see (10), such that $\|b-c\|=\Delta$.

The set of Chebyshev approximations of the second member $b$ is:

$\mathcal{C}_{b}=\\{c\in\mathcal{C}\mid\|b-c\|=\Delta\\}.$ (12)

We have the following fundamental result, proven for $\max-\min$ system in [3]
and extended for $\max-T$ systems in [1]:

$\Delta=\min\\{\delta\in[0,1]\mid\underline{b}(\delta)\leq
F(\overline{b}(\delta))\\}.$ (13)

which is based on the following application:

$F:[0,1]^{n\times 1}\longrightarrow[0,1]^{n\times 1}:c=[c_{i}]\mapsto
F(c)=A\Box_{T}^{\max}(A^{t}\Box_{{\cal I}_{T}}^{\min}c)=[F(c)_{i}]$ (14)

where:

$\forall i\in\\{1,2,\dots,n\\},\,F(c)_{i}=\max_{1\leq j\leq
m}T(a_{ij},\min_{1\leq k\leq n}{\cal I}_{T}(a_{kj},c_{k})).$ (15)

By solving (13) in the case of a system of $\max-\min$ fuzzy relational
equations $A\Box_{T_{M}}^{\max}x=b$, the author of [2] gave the following
analytical formula for computing the Chebyshev distance associated to its
second member $b$:

$\Delta_{M}=\max_{1\leq i\leq n}\min_{1\leq j\leq
m}\,\max[(b_{i}-a_{ij})^{+},\max_{1\leq k\leq
n}\,\,\sigma_{G}\,(b_{i},a_{kj},b_{k})],$ (16)

where

$\sigma_{G}(x,y,z)=\min(\frac{(x-z)^{+}}{2},(y-z)^{+}).$ (17)

Similarly, for the case of a system of $\max$-product fuzzy relational
equations $A\Box_{T_{P}}^{\max}x=b$, the author of [1] gave the following
analytical formula for computing the Chebyshev distance associated to $b$:

$\Delta_{P}=\max_{1\leq i\leq n}\min_{1\leq j\leq m}\,\max_{1\leq k\leq
n}\,\sigma_{GG}\,(a_{ij},b_{i},a_{kj},b_{k}),$ (18)

where

$\sigma_{GG}(u,x,y,z)=\max[(x-u)^{+},\min(\varphi(u,x,y,z),(y-z)^{+})]$ (19)

and

$\varphi(u,x,y,z)=\begin{cases}\frac{(x\cdot y-u\cdot z)^{+}}{u+y}&\text{ if
}u>0\\\ x&\text{ if }u=0\end{cases}.$ (20)

The author of [1] also gave the following analytical formula for computing
Chebyshev distance associated to the second member $b$ of a system of
$\max$-Łukasiewicz fuzzy relational equations $A\Box_{T_{L}}^{\max}x=b$:

$\Delta_{L}=\max_{1\leq i\leq n}\min_{1\leq j\leq m}\,\max_{1\leq k\leq
n}\,\sigma_{L}\,(1-a_{ij},b_{i},a_{kj},b_{k}),$ (21)

where

$\sigma_{L}(u,x,y,z)=\min(x,\max(v^{+},\frac{(v+y-z)^{+}}{2}))\text{ with
}v=x+u-1.$

For the $\max-\min$ system, the author of [2] showed that the formula (16)
allows us to get directly its greatest approximate solution and its greatest
Chebyshev approximation of its second member (thus, the set $\mathcal{C}_{b}$
is non-empty and $\Delta_{M}$ is always a minimum). For $\max$-product and
max-Łukasiewicz systems, the author of [1] showed the same results using the
formulas (18) and (21). From (16), the author of [2] also gave a description
of the set $\mathcal{C}_{b}$ of Chebyshev approximations, see (12) and that of
the approximate solutions set of the inconsistent system.

##  3 General results on solving systems of $\min-\rightarrow$ fuzzy
relational equations where $\rightarrow$ is one of the implications among
Gödel’s implication, Goguen’s or Łukasiewicz’s

In this section, we begin by reminding the solving of a system of
$\min-\rightarrow$ fuzzy relational equations, which is based on a matrix
$\Gamma=[\gamma_{ji}]_{1\leq j\leq m,1\leq i\leq n}\in[0,1]^{m\times n}$ of
size $(m,n)$ and a column-vector of $m$ components
$\beta=\begin{bmatrix}\beta_{j}\end{bmatrix}_{1\leq j\leq m}\in[0,1]^{m\times
1}$:

$(\Sigma):\Gamma\Box_{\rightarrow}^{\min}x=\beta,$ (22)

where $x$ is an unknown column-vector of $n$ components.
Using the vector $\epsilon=\Gamma^{t}\Box_{T}^{\max}\beta$ (where $\Gamma^{t}$
is the transpose of the matrix $\Gamma$), we have the following equivalence
[7, 9, 11]:

$(\Sigma)\text{ is consistent
}\Longleftrightarrow\Gamma\Box_{\rightarrow}^{\min}\epsilon=\beta.$ (23)

######  Example 1.

Let us use the Gödel’s implication $\rightarrow_{G}$, see (4), the matrix
$\Gamma=\begin{bmatrix}0.6&0.49\\\ 0.26&0.9\\\ \end{bmatrix}$ and the vector
$\beta=\begin{bmatrix}0.58\\\ 0.88\end{bmatrix}.$
We have $\Gamma^{t}=\begin{bmatrix}0.6&0.26\\\ 0.49&0.9\\\ \end{bmatrix}$. We
compute $\epsilon=\Gamma^{t}\Box_{\min}^{\max}\beta=\begin{bmatrix}0.58\\\
0.88\end{bmatrix}$. The $\min-\rightarrow_{G}$ composition of the matrix
$\Gamma$ by the vector $\epsilon$ is:

$\Gamma\Box_{\rightarrow_{G}}^{\min}\epsilon=\begin{bmatrix}0.58\\\
0.88\end{bmatrix}=\beta.$

Therefore, the system $\Gamma\Box_{\rightarrow_{G}}^{\min}x=\beta$ is
consistent.

Similarly to the application $F$, see (14), studied for systems of $\max-T$
fuzzy relational equations in [1, 2], we introduce the following application
for systems of $\min-\rightarrow$ fuzzy relational equations:

$G:[0,1]^{m\times 1}\rightarrow[0,1]^{m\times 1}:\xi\mapsto
G(\xi)=\Gamma\Box_{{\cal I}_{T}}^{\min}(\Gamma^{t}\Box_{T}^{\max}\xi),$ (24)

which allows us to reformulate the equivalence (23) as:

$(\Sigma)\text{ is consistent }\Longleftrightarrow G(\beta)=\beta.$ (25)

The rest of this section is structured as follows. In (Subsection 3.1) we
study the main properties of the function $G$. In (Subsection 3.2) we define
the Chebyshev distance $\nabla=\inf_{d\in\mathcal{D}}\|\beta-d\|$ associated
to the second member $\beta$ of the system $(\Sigma)$ where $\mathcal{D}$ is
the set formed by the second members of the consistent systems of
$\min-\rightarrow$ fuzzy relational equations defined with the same matrix
$\Gamma$. We show in (Theorem 1) that the Chebyshev distance $\nabla$ is the
lower bound of the solutions of a vector inequality expressed with the
application $G$. From this result, we obtain the decomposition of the
Chebyshev distance $\nabla=\max_{1\leq j\leq m}\nabla_{j}$ (Proposition 5),
where for all $j\in\\{1,2,\dots,m\\}$, each $\nabla_{j}$ is the lower bound of
the solutions of the $j$-th scalar inequality in the above-mentioned vector
inequality, see (36).

###  3.1 Study of the application $G$

From the system $(\Sigma):\Gamma\Box_{{\cal I}_{T}}^{\min}x=\beta$, see (22),
where $\Gamma=[\gamma_{ji}]_{1\leq j\leq m,1\leq i\leq n}\in[0,1]^{m\times
n}$, let us compute the components of $G(\xi)$ for any vector
$\xi=[\xi_{j}]_{1\leq j\leq m}\in[0,1]^{m\times 1}$.
For $1\leq j\leq m$, we have:

$G(\xi)_{j}=\min_{1\leq i\leq n}\,{\cal I}_{T}(\gamma_{ji},\max_{1\leq l\leq
m}\,T(\gamma_{li},\xi_{l})).$

The application $G$ has the following properties:

######  Proposition 1.

$\forall\xi\in[0,1]^{m\times 1},\quad\xi\leq G(\xi).$

To prove the inequality $\xi_{j}\leq G(\xi)_{j}$ for each
$j\in\\{1,2,\dots,m\\}$, we rely on the inequality ${\cal I}_{T}(a,T(a,b))\geq
b$.

###### Proof.

Let $j\in\\{1,2,\dots,m\\}$, we have:

$\displaystyle G(\xi)_{j}$ $\displaystyle=\min_{1\leq i\leq n}\,{\cal
I}_{T}(\gamma_{ji},\max_{1\leq l\leq m}\,T(\gamma_{li},\xi_{l}))$
$\displaystyle\geq\min_{1\leq i\leq n}\,{\cal
I}_{T}(\gamma_{ji},T(\gamma_{ji},\xi_{j}))$ $\displaystyle\geq\min_{1\leq
i\leq n}\,\xi_{j}$ $\displaystyle=\xi_{j}.$

∎

######  Proposition 2.

The application $G$ is increasing ; given $\xi,\xi^{\prime}\in[0,1]^{m\times
1}$ we have:

$\xi\leq\xi^{\prime}\Longrightarrow G(\xi)\leq G(\xi^{\prime}).$

###### Proof.

The increasing property of the application $G$ is a consequence of the
increasing property of the t-norm $T$ and that of its associated residual
implicator ${\cal I}_{T}$ with respect to the second variable. It results that
the following two applications are also increasing:

$[0,1]^{n\times 1}\rightarrow[0,1]^{m\times 1}:c\mapsto\Gamma\Box_{{\cal
I}_{T}}^{\min}c\quad;\quad[0,1]^{m\times 1}\rightarrow[0,1]^{n\times
1}:\xi\mapsto\Gamma^{t}\Box_{T}^{\max}\xi.$

∎

######  Proposition 3.

The application $G$ is idempotent i.e., $G\circ G=G$.

To prove the idempotent property of $G$, we have to show that
$\forall\xi\in[0,1]^{m\times 1}$, $G(G(\xi))=G(\xi)$. The proof is a
consequence of the relation: $\forall\xi\in[0,1]^{m\times
1},\quad\Gamma^{t}\Box_{T}^{\max}G(\xi)=\Gamma^{t}\Box_{T}^{\max}\xi$, which
we will deduce from a property of the application $F$, see (14).

###### Proof.

Let $\xi\in[0,1]^{m\times 1}$ be fixed and we put
$c=\Gamma^{t}\Box_{T}^{\max}\xi\in[0,1]^{n\times 1}$. Thus,
$\Gamma^{t}\Box_{T}^{\max}x=c$ is a consistent system and $\xi$ one of its
solution. We remind that the application $F$ of [1, 2], see (14), associated
to the matrix $A:=\Gamma^{t}$ satisfies $F(c)=c$.

We have:

$\displaystyle\Gamma^{t}\Box_{T}^{\max}G(\xi)$
$\displaystyle=\Gamma^{t}\Box_{T}^{\max}(\Gamma\Box_{{\cal
I}_{T}}^{\min}(\Gamma^{t}\Box_{T}^{\max}\xi))$
$\displaystyle=\Gamma^{t}\Box_{T}^{\max}(\Gamma\Box_{{\cal I}_{T}}^{\min}c)$
$\displaystyle=F(c)$ $\displaystyle=c=\Gamma^{t}\Box_{T}^{\max}\xi.$

The equality $\Gamma^{t}\Box_{T}^{\max}G(\xi)=\Gamma\Box_{T}^{\max}\xi$ leads
to:

$G(G(\xi))=\Gamma\Box_{{\cal
I}_{T}}^{\min}(\Gamma^{t}\Box_{T}^{\max}G(\xi))=\Gamma\Box_{{\cal
I}_{T}}^{\min}(\Gamma^{t}\Box_{T}^{\max}\xi)=G(\xi).$

∎

######  Proposition 4.

The application $G$ is right-continuous.

If the application ${\cal I}_{T}:[0,1]^{2}\rightarrow[0,1]$ is continuous,
then $G:[0,1]^{m\times 1}\rightarrow[0,1]^{m\times 1}$ is also continuous.

The right-continuity of the application $G$ means that for any sequence
$(\xi^{(k)})$ verifying: $\forall k,\xi^{(k)}\geq\xi\text{ and
}(\xi^{(k)})\rightarrow\xi$, we have $(G(\xi^{(k))})\rightarrow G(\xi)$. Note
that, in $[0,1]^{m\times 1}$, the convergence of a sequence of vectors
$(\eta^{(k)})$ to a vector $\eta\in[0,1]^{m\times 1}$ is the convergence
component by component: $\forall
j\in\\{1,2,\dots,m\\},\,\eta^{(k)}_{j}\rightarrow\eta_{j}$.

###### Proof.

The right-continuity of the application $G$ is a consequence of the continuity
of the t-norm $T$ and the right-continuity with respect to the second variable
of the residual implicator $\mathcal{I}_{T}$ associated to $T$. It is obtained
by applying the general theorems on continuity [12], which also allow, in the
case where ${\cal I}_{T}$ is continuous, to obtain the continuity of the
application $G$. ∎

In the following subsection, the application $G$ is used for computing the
Chebyshev distance associated to the second member of a system of
$\min-\rightarrow$ fuzzy relational equations.

###  3.2 Chebyshev distance associated to the second member of a system of
$\min-\rightarrow$ fuzzy relational equations

In this subsection, we begin by defining the set $\mathcal{D}$ formed by the
second members of the consistent systems of $\min-\rightarrow$ fuzzy
relational equations defined with the same matrix $\Gamma$. For $\max-T$
systems, an analogous set denoted $\mathcal{C}$ was defined, see (10).

To the matrix $\Gamma$, let us associate the set of vectors
$d=[d_{j}]\in[0,1]^{m\times 1}$ such that the system
$\Gamma\Box_{\rightarrow}^{\min}x=d$ is consistent:

$\mathcal{D}=\\{d=[d_{j}]\in{[0,1]}^{m\times
1}\mid\Gamma\Box_{\rightarrow}^{\min}x=d\text{ is consistent}\\}.$ (26)

Note that the equivalence (25) allows us to obtain a second definition of the
set $\mathcal{D}$:

$\mathcal{D}=\\{d=[d_{j}]\in{[0,1]}^{m\times 1}\mid G(d)=d\\}.$ (27)

Using the idempotence property of the application $G$ (Proposition 3), we also
deduce:

$\forall\beta\in[0,1]^{m\times 1}\,,\,G(\beta)\in\mathcal{D}.$ (28)

The set $\mathcal{D}$ is non-empty: the vector $d\in[0,1]^{m\times 1}$ whose
components are equal to $1$, satisfies the equality $G(d)=d$ and then
$d\in\mathcal{D}$.
This set allows us to define:

######  Definition 3.

The Chebyshev distance associated to the system
$(\Sigma):\Gamma\Box_{\rightarrow}^{\min}x=\beta$ is:

$\nabla=\nabla(\Gamma,\beta)=\inf_{d\in\mathcal{D}}\|\beta-d\|$ (29)

where:

$\|\beta-d\|=\max_{1\leq j\leq m}\mid\beta_{j}-d_{j}\mid.$

and

######  Definition 4.

A Chebyshev approximation of the second member $\beta$ is an element
$d\in\mathcal{D}$, see (27), such that $\|d-\beta\|=\nabla$.

The set of Chebyshev approximations of the second member $\beta$ is:

$\mathcal{D}_{\beta}=\\{d\in\mathcal{D}\mid\|d-\beta\|=\nabla\\}.$ (30)

In the case of a system of $\max-T$ fuzzy relational equations, the authors of
[1, 3] showed that its associated Chebyshev distance $\Delta$ is the lower
bound of the solutions of a vector inequality involving the application $F$,
(see 13).
Similarly, for a system of $\min-\rightarrow$ fuzzy relational equations, we
will prove in (Theorem 1) that the Chebyshev distance (29) is the lower bound
of the solutions of a vector inequality involving the application $G$.

We rely on the following sets:

######  Notation 1.

$E=\\{\delta\in[0,1]\mid
G(\underline{\beta}(\delta))\leq\overline{\beta}(\delta)\\}.$ (31)

For all $1\leq j\leq m$:

$E_{j}=\\{\delta\in[0,1]\,\mid\,G(\underline{\beta}(\delta))_{j}\leq\overline{\beta}(\delta)_{j}\\},\quad\nabla_{j}=\inf
E_{j}.$ (32) ${\cal A}_{j}=\\{i\in\\{1,2,\dots,n\\}\,\mid\,\gamma_{ji}>0\\},$
(33)

We need the following lemma:

######  Lemma 1.

We have:

  1. 1.

$E=\bigcap_{1\leq j\leq m}E_{j}.$

  2. 2.

for all $\delta,\delta^{\prime}\in[0,1]$ and $j\in\\{1,2,\dots,m\\}$ , we
have:

$\delta\in
E_{j}\quad\text{and}\quad\delta\leq\delta^{\prime}\,\Longrightarrow\,\delta^{\prime}\in
E_{j}.$

###### Proof.

The proof of the first statement is easy: for any $\delta\in[0,1]$, we have:

$\delta\in
E\,\Longleftrightarrow\,G(\underline{\beta}(\delta))\leq\overline{\beta}(\delta)\,\Longleftrightarrow\,\forall
j\in\\{1,\dots,m\\}\,,\,G(\underline{\beta}(\delta))_{j}\leq\overline{\beta}(\delta)_{j}\,\Longleftrightarrow\,\forall
j\in\\{1,\dots,m\\}\,,\,\delta\in E_{j}.$

Let $\delta\in E_{j}$ and $\delta^{\prime}\in[0,1]$ satisfy the inequality
$\delta\leq\delta^{\prime}$. Then, using the increasing (Proposition 2) of
$G$, we obtain:

$G(\underline{\beta}(\delta^{\prime}))_{j}\leq
G(\underline{\beta}(\delta))_{j}\leq\overline{\beta}(\delta)_{j}\leq\overline{\beta}(\delta^{\prime})_{j}.$

Thus, we obtain
$G(\underline{\beta}(\delta^{\prime}))_{j}\leq\overline{\beta}(\delta^{\prime})_{j}$,
i.e., $\delta^{\prime}\in E_{j}$. ∎

The Chebyshev distance $\nabla$ (Definition 3) of a $\min-\rightarrow$ system
$(\Sigma):\Gamma\Box_{\rightarrow}^{\min}x=\beta$, see (22) is:

######  Theorem 1.

We have:

$\nabla=\inf\\{\delta\in[0,1]\mid
G(\underline{\beta}(\delta))\leq\overline{\beta}(\delta)\\}=\inf E.$ (34)

###### Proof.

We put $\nabla^{\prime}=\inf E.$ Let us show that we have
$\nabla=\nabla^{\prime}$ in two steps:

  1. 1.

$\nabla\leq\nabla^{\prime}$: we have to show:

$\forall\delta\in E,\,\nabla\leq\delta.$

Let $\delta\in E$, we put $d=G(\underline{\beta}(\delta))$. From (28), we
deduce that $d\in\mathcal{D}$. Then, we obtain:

$\|\beta-G(\underline{\beta}(\delta))\|=\|\beta-d\|\geq\nabla.$

From (Proposition 1), we have $\underline{\beta}(\delta)\leq
G(\underline{\beta}(\delta))$ and $\delta\in E$. So, we deduce the double
inequality

$\underline{\beta}(\delta)\leq
G(\underline{\beta}(\delta))\leq\overline{\beta}(\delta).$

Using the inequality (3), we conclude that:

$\|\beta-d\|=\|\beta-G(\underline{\beta}(\delta))\|\leq\delta$

and finally $\nabla\leq\|\beta-d\|\leq\delta$.

  2. 2.

$\nabla^{\prime}\leq\nabla$: we have to show:

$\forall d\in{\cal D}\,,\,\nabla^{\prime}\leq\|\beta-d\|.$

Let $d\in{\cal D}$, we put $\delta=\|\beta-d\|$. From (3), we deduce:

$\underline{\beta}(\delta)\leq d\leq\overline{\beta}(\delta).$

Using that $G$ is increasing (Proposition 2) and the equivalence (25), we
obtain:

$G(\underline{\beta}(\delta))\leq G(d)=d\leq\overline{\beta}(\delta),$

so $\delta\in E$ and by definition of $\nabla^{\prime}$, we have
$\nabla^{\prime}\leq\delta=\|\beta-d\|$.

∎

(Theorem 1) states that $\inf_{d\in\mathcal{D}}\|\beta-d\|=\nabla=\inf E$. In
fact, in the following sections, we will see that, whatever the residual
implicator used among the Gödel implication, the Goguen implication and the
Łukasiewicz implication, we have:

$\nabla=\min_{d\in\mathcal{D}}\|\beta-d\|\Longleftrightarrow\nabla=\min E.$

From the above lemma and theorem, we deduce the following useful decomposition
of the Chebyshev distance $\nabla$:

######  Proposition 5.

$\nabla=\max_{1\leq j\leq m}\nabla_{j}$ (35)

where:

$\nabla_{j}=\inf\\{\delta\in[0,1]\,\mid\,G(\underline{\beta}(\delta))_{j}\leq\overline{\beta}(\delta)_{j}\\}=\inf
E_{j}.$ (36)

###### Proof.

We will prove the equality $\nabla=\max_{1\leq j\leq m}\nabla_{j}$ in the
following two steps:

  1. 1.

$\max_{1\leq j\leq m}\nabla_{j}\leq\nabla$ ; we have to show:

$\forall\delta\in E,\,\max_{1\leq j\leq m}\nabla_{j}\leq\delta.$

Using (Lemma 1) the equality $E=\bigcap_{1\leq j\leq m}E_{j}$, we deduce that
for any $\delta\in E$, we have:

$\forall j\in\\{1,2,\dots,m\\}\,\,\nabla_{j}=\inf E_{j}\leq\delta.$

Thus, $\max_{1\leq j\leq m}\nabla_{j}\leq\delta.$

  2. 2.

$\nabla\leq\max_{1\leq j\leq m}\nabla_{j}$

To rely on the properties of a lower bound, we use the well-known equivalence:

$\nabla\leq\max_{1\leq j\leq
m}\nabla_{j}\,\Longleftrightarrow\,\forall\varepsilon>0\,,\,\nabla<\max_{1\leq
j\leq m}\nabla_{j}+\varepsilon.$

Let $\varepsilon>0$. For any $j\in\\{1,2,\dots,m\\}$, there is an element
$\delta_{j}\in E_{j}$ such that

$\delta_{j}<\nabla_{j}+\varepsilon.$

We put $\delta=\max_{1\leq j\leq m}\delta_{j}$. Then, for any
$j\in\\{1,2,\dots,m\\}$, we get:

$\delta_{j}\in E_{j}\quad\text{and}\quad\delta_{j}\leq\delta.$

Using (Lemma 1), we conclude that $\delta\in E$ and:

$\nabla\leq\delta=\max_{1\leq j\leq m}\delta_{j}<\max_{1\leq j\leq
m}(\nabla_{j}+\varepsilon)=\max_{1\leq j\leq m}\nabla_{j}+\varepsilon.$

∎

As we will see in the next sections, the formula for computing $\nabla_{j}$,
involves the value $1-\beta_{j}$ (thus using the $j$-th component $\beta_{j}$
of the second member $\beta$), whatever the residual implicator used among the
Gödel implication, the Goguen implication and the Łukasiewicz implication.

######  Lemma 2.

For any $j\in\\{1,2,\dots,m\\}$, we have:

  1. 1.

$1-\beta_{j}\in E_{j}$,

  2. 2.

$\nabla_{j}\leq 1-\beta_{j}$.

In particular, we have:

$\beta_{j}=1\Longrightarrow\nabla_{j}=0.$

###### Proof.

For $\delta=1-\beta_{j}$, we have $\overline{\beta}(\delta)_{j}=1$, so the
inequality
$G(\underline{\beta}(\delta))_{j}\leq\overline{\beta}(\delta)_{j}=1$ is
satisfied and therefore we have $1-\beta_{j}\in E_{j}$.

As we proved $1-\beta_{j}\in E_{j}$, the inequality $\nabla_{j}\leq
1-\beta_{j}$ is a consequence of the definition $\nabla_{j}=\inf E_{j}$. ∎

In the following sections, for each of the three systems of $\min-\rightarrow$
fuzzy relational equations (depending on whether $\rightarrow$ is Gödel’s
implication, Goguen’s implication or Łukasiewicz’s implication), we give an
explicit formula for computing the Chebyshev distance associated to the second
member of the system.

##  4 Chebyshev distance associated to the second member of systems based on
$\min-\rightarrow_{G}$ composition

In this section, our purpose is to give an explicit formula (Theorem 2) for
computing the Chebyshev distance $\nabla$, see (Definition 3), associated to
the second member of a system of $\min-\rightarrow_{G}$ fuzzy relational
equations $(\Sigma):\Gamma\Box_{\rightarrow_{G}}^{\min}x=\beta$, see (22),
where $\rightarrow_{G}$ is the Gödel implication, see (4). The main
preliminary results ((Proposition 6), (Corollary 1) and (Proposition 7))
needed for establishing the formula (Theorem 2) follow from the key result
stated in (Lemma 4).

We remind from (Proposition 5) that $\nabla=\max_{1\leq j\leq m}\nabla_{j}$
where $\nabla_{j}=\inf E_{j}$ and the set $E_{j}$ is defined in (32). As
illustrated at the end of the section by (Example 5), the set $E_{j}$ does not
necessarily admit a minimum element, i.e. $\nabla_{j}$ does not necessarily
belong to $E_{j}$. In (Proposition 8), we characterize when $E_{j}$ admits a
minimum element i.e., $\nabla_{j}\in E_{j}$ and deduce a sufficient condition
for $\nabla$ being a minimum element of $E$ (Corollary 2) i.e., $\nabla\in E$.
Therefore, as we will see in (Example 5), in the case of a
$\min-\rightarrow_{G}$ system, the Chebyshev distance $\nabla$ may be an
infimum. For $\min-\rightarrow_{G}$ systems whose $\nabla$ has been verified
as a minimum, we can always compute the lowest Chebyshev approximation of the
second member and an approximate solution (Corollary 3). However, for the
$\min-\rightarrow_{G}$ systems whose Chebyshev distance has been verified as
not being a minimum, the set of Chebyshev approximations of its second member
is empty (Lemma 7).

We use the following notations:

######  Notation 2.

For $1\leq j\leq m,1\leq i\leq n$, to each coefficient $\gamma_{ji}$ of the
matrix $\Gamma$ of the system $(\Sigma)$, see (22), we associate:

  * •

$V(j,i)=\big{\\{}l\in\\{1,2,\dots,m\\}\mid\gamma_{ji}\leq\gamma_{li}\big{\\}}$,

  * •

$\theta_{ji}=\max_{l\in V(j,i)}(\beta_{l}-\gamma_{ji})$,

  * •

$\zeta_{ji}=\max_{1\leq l\leq m}\sigma_{G}(\beta_{l},\gamma_{li},\beta_{j})$.

where $\sigma_{G}(x,y,z)=\min(\dfrac{(x-z)^{+}}{2},(y-z)^{+})$ was defined in
(17) from [2].

To give the formula for computing $\nabla_{j}$ for $j\in\\{1,2,\dots,m\\}$,
see (36), we will study the solving of the involved inequality
$G(\underline{\beta}(\delta))_{j}\leq\overline{\beta}(\delta)_{j}$.

The following result gives an equivalent definition of the function
$\sigma_{G}$ introduced in [2], see (17), which is adapted to our needs:

######  Lemma 3.

For all $x,y,z,\delta\in[0,1]$, we have:

$\min(y,\underline{x}(\delta))\leq\overline{z}(\delta)\,\Longleftrightarrow\,\sigma_{G}(x,y,z)\leq\delta.$

###### Proof.

We have:

$y-\overline{z}(\delta)=\max(y-z-\delta,y-1).$
$\displaystyle\underline{x}(\delta)-\overline{z}(\delta)$
$\displaystyle=\max(\underline{x}(\delta)-z-\delta,\underline{x}(\delta)-1)$
$\displaystyle=\max[\max(x-\delta,0)-z-\delta,\underline{x}(\delta)-1]$
$\displaystyle=\max[\max(x-\delta-z-\delta,-z-\delta),\underline{x}(\delta)-1]$
$\displaystyle=\max(x-z-2\delta,-z-\delta,\underline{x}(\delta)-1).$

We remark that: $y-1\leq 0,\,-z-\delta\leq 0,\text{ and
}\underline{x}(\delta)-1\leq 0$.

We have:

$\displaystyle\min(y,\underline{x}(\delta))\leq\overline{z}(\delta)$
$\displaystyle\Longleftrightarrow\,\min(y-\overline{z}(\delta),\underline{x}(\delta)-\overline{z}(\delta))\leq
0$ $\displaystyle\Longleftrightarrow\,y-\overline{z}(\delta)\leq 0\,\text{ or
}\,\underline{x}(\delta)-\overline{z}(\delta))\leq 0$
$\displaystyle\Longleftrightarrow\,y-z-\delta\leq 0\,\text{ or
}\,x-z-2\delta\leq 0$
$\displaystyle\Longleftrightarrow\,(y-z)^{+}\leq\delta\,\text{ or
}\,\dfrac{(x-z)^{+}}{2}\leq\delta$
$\displaystyle\Longleftrightarrow\,\min(\dfrac{(x-z)^{+}}{2},(y-z)^{+})\leq\delta$
$\displaystyle\Longleftrightarrow\,\sigma_{G}(x,y,z)=\min(\dfrac{(x-z)^{+}}{2},(y-z)^{+})\leq\delta.$

∎

######  Example 2.

Let $x=0.6,y=0.4$ and $z=0.2$. We have $\min(y,x)>z$. We compute
$\delta=\sigma_{G}(x,y,z)=0.2$, then the inequality
$\min(y,\underline{x}(\delta))\leq\overline{z}(\delta)$ is satisfied.

We establish the following important lemma, which will provide important
information in (Proposition 6) on $\nabla_{j}$, in the case where
$\nabla_{j}<1-\beta_{j}$:

######  Lemma 4.

Let $j\in\\{1,2,\dots,m\\}$. For all $\delta\in[0,1]$ such that
$\delta<1-\beta_{j}$, we have the following equivalence between these two
statements:

  1. 1.

$G(\underline{\beta}(\delta))_{j}\leq\overline{\beta}(\delta)_{j}$,

  2. 2.

there exists $i\in\\{1,2,\dots,n\\}$ such that:

$\gamma_{ji}>0,\quad\theta_{ji}<\delta\quad\text{ and
}\quad\zeta_{ji}\leq\delta.$

###### Proof.

$\Longrightarrow$:
We have:

$G(\underline{\beta}(\delta))_{j}=\min_{1\leq i\leq
n}(\gamma_{ji}\rightarrow_{G}(\max_{1\leq l\leq
m}\min(\gamma_{li},\underline{\beta}(\delta)_{l})))\leq\overline{\beta}(\delta)_{j}=\beta_{j}+\delta<1.$

We deduce that there exists an index $i\in\\{1,2,\dots n\\}$ such that:

$\gamma_{ji}\rightarrow_{G}(\max_{1\leq l\leq
m}\min(\gamma_{li},\underline{\beta}(\delta)_{l}))=G(\underline{\beta}(\delta))_{j}\leq\overline{\beta}(\delta)_{j}=\beta_{j}+\delta<1$

which implies

$\gamma_{ji}>\max_{1\leq l\leq
m}\min(\gamma_{li},\underline{\beta}(\delta)_{l})\quad\text{ and
}\quad\max_{1\leq l\leq
m}\min(\gamma_{li},\underline{\beta}(\delta)_{l})\leq\beta_{j}+\delta$

so

$\gamma_{ji}>0\text{ and }\forall
l\in\\{1,2,\dots,m\\}\,,\,\gamma_{ji}>\min(\gamma_{li},\underline{\beta}(\delta)_{l})\text{
and }\min(\gamma_{li},\underline{\beta}(\delta)_{l})\leq\beta_{j}+\delta.$
(39)

By (Lemma 3), we know that for all $l\in\\{1,2,\dots,m\\}$ , we have:

$\min(\gamma_{li},\underline{\beta}(\delta)_{l})\leq\beta_{j}+\delta=\overline{\beta}(\delta)_{j}\Longleftrightarrow\sigma_{G}(\beta_{l},\gamma_{li},\beta_{j})\leq\delta$

so (39) implies $\zeta_{ji}=\max_{1\leq l\leq
m}\sigma_{G}(\beta_{l},\gamma_{li},\beta_{j})\leq\delta.$

To establish the inequality $\theta_{ji}<\delta$, we will show that:

$\forall l\in V(j,i)\,,\,\beta_{l}-\gamma_{ji}<\delta.$

Let $l\in V(j,i)$ i.e., $\gamma_{ji}\leq\gamma_{li}$ and by (39) we have:
$\gamma_{ji}>\min(\gamma_{li},\underline{\beta}(\delta)_{l})$, so

$\min(\gamma_{li},\underline{\beta}(\delta)_{l})=\underline{\beta}(\delta)_{l}<\gamma_{ji}.$

Then, we have:

$\underline{\beta}(\delta)_{l}-\gamma_{ji}=\max(\beta_{l}-\delta,0)-\gamma_{ji}=\max(\beta_{l}-\gamma_{ji}-\delta,-\gamma_{ji})<0$

so $\beta_{l}-\gamma_{ji}<\delta$ and finally $\theta_{ji}=\max_{l\in
V(j,i)}\beta_{l}-\gamma_{ji}<\delta$.

$\Longleftarrow$:
Let $i\in\\{1,2,\dots,n\\}$ such that:

$\gamma_{ji}>0,\quad\theta_{ji}<\delta,\quad\zeta_{ji}\leq\delta.$

We have:

$G(\underline{\beta}(\delta))_{j}=\min_{1\leq i^{\prime}\leq
n}(\gamma_{ji^{\prime}}\rightarrow_{G}(\max_{1\leq l\leq
m}\min(\gamma_{li^{\prime}},\underline{\beta}(\delta)_{l}))\leq\gamma_{ji}\rightarrow_{G}(\max_{1\leq
l\leq m}\min(\gamma_{li},\underline{\beta}(\delta)_{l})).$

We will show that we have:

$\gamma_{ji}\rightarrow_{G}(\max_{1\leq l\leq
m}\min(\gamma_{li},\underline{\beta}(\delta)_{l})\leq\overline{\beta}(\delta)_{j}.$

From the general equality:
$x\rightarrow_{G}\max(y,z)=\max(x\rightarrow_{G}y,x\rightarrow_{G}z)$, we
deduce:

$\gamma_{ji}\rightarrow_{G}(\max_{1\leq l\leq
m}\min(\gamma_{li},\underline{\beta}(\delta)_{l}))=\max_{1\leq l\leq
m}\gamma_{ji}\rightarrow_{G}\min(\gamma_{li},\underline{\beta}(\delta)_{l}).$

We will establish

$\forall
l\in\\{1,2,\dots,m\\},\,\gamma_{ji}\rightarrow_{G}\min(\gamma_{li},\underline{\beta}(\delta)_{l})\leq\overline{\beta}(\delta)_{j}=\beta_{j}+\delta.$
(40)

Let $l\in\\{1,2,\dots,m\\}$. We distinguish the following two cases:

$\bullet\,$ We suppose that $l\in V(j,i)$ i.e., $\gamma_{ji}\leq\gamma_{li}$.
We then have:

$\beta_{l}-\gamma_{li}\leq\beta_{l}-\gamma_{ji}\leq\theta_{ji}<\delta.$

We deduce:

$\beta_{l}-\gamma_{li}-\delta\leq\beta_{l}-\gamma_{ji}-\delta<0\quad\text{ and
}\quad\gamma_{li}\geq\gamma_{ji}>0.$

So:

$\underline{\beta}(\delta)_{l}-\gamma_{li}=\max(\beta_{l}-\gamma_{li}-\delta,-\gamma_{li})<0$

which leads to
$\min(\gamma_{li},\underline{\beta}(\delta)_{l})=\underline{\beta}(\delta)_{l}$.
On the other hand, $\beta_{l}-\gamma_{ji}-\delta<0\quad\text{ and
}\quad\gamma_{ji}>0$ lead to

$\underline{\beta}(\delta)_{l}-\gamma_{ji}=\max(\beta_{l}-\gamma_{ji}-\delta,-\gamma_{ji})<0$

so $\underline{\beta}(\delta)_{l}<\gamma_{ji}$ and we obtain

$\gamma_{ji}\rightarrow_{G}\min(\gamma_{li},\underline{\beta}(\delta)_{l})=\min(\gamma_{li},\underline{\beta}(\delta)_{l}).$

By taking into account
$\sigma_{G}(\beta_{l},\gamma_{li},\beta_{j})\leq\zeta_{ji}\leq\delta$, we
deduce from (Lemma 3):

$\min(\gamma_{li},\underline{\beta}(\delta)_{l})\leq\overline{\beta}(\delta)_{j}$

so

$\gamma_{ji}\rightarrow_{G}\min(\gamma_{li},\underline{\beta}(\delta)_{l})\leq\overline{\beta}(\delta)_{j}=\beta_{j}+\delta.$

$\bullet\,$ If we suppose $l\in V(j,i)^{c}$, i.e, $\gamma_{ji}>\gamma_{li}$
and taking into account that
$\gamma_{li}\geq\min(\gamma_{li},\underline{\beta}(\delta)_{l})$, we then
have:

$\gamma_{ji}\rightarrow_{G}\min(\gamma_{li},\underline{\beta}(\delta)_{l})=\min(\gamma_{li},\underline{\beta}(\delta)_{l}).$

As by hypothesis we have
$\sigma_{G}(\beta_{l},\gamma_{li},\beta_{j})\leq\zeta_{ji}\leq\delta$, we
deduce from (Lemma 3):

$\min(\gamma_{li},\underline{\beta}(\delta)_{l})\leq\overline{\beta}(\delta)_{j}.$

So:

$\gamma_{ji}\rightarrow_{G}\min(\gamma_{li},\underline{\beta}(\delta)_{l})=\min(\gamma_{li},\underline{\beta}(\delta)_{l})\leq\overline{\beta}(\delta)_{j}=\beta_{j}+\delta.$

We have established (40) and therefore we have proven
$G(\underline{\beta}(\delta))_{j}\leq\overline{\beta}(\delta)_{j}$. ∎

We illustrate this result:

######  Example 3.

Let us use the matrix $\Gamma=\begin{bmatrix}0.6&0.49\\\ 0.26&0.9\\\
\end{bmatrix}$ and the vector $\beta=\begin{bmatrix}0.1\\\ 0.4\end{bmatrix}$.
For $j=1$, we have:

$\displaystyle G(\underline{\beta}(\delta))_{1}$ $\displaystyle=\min_{1\leq
i\leq 2}(\gamma_{1i}\rightarrow_{G}(\max_{1\leq l\leq
2}\min(\gamma_{li},\underline{\beta}(\delta)_{l})))$
$\displaystyle=\min(0.6\rightarrow_{G}(\max_{1\leq l\leq
2}\min(\gamma_{l1},\underline{\beta}(\delta)_{l})),0.49\rightarrow_{G}(\max_{1\leq
l\leq 2}\min(\gamma_{l2},\underline{\beta}(\delta)_{l})))$

We compute:

  * •

$\max_{1\leq l\leq
2}\min(\gamma_{l1},{\beta}_{l})=\max(\min(0.6,0.1),\min(0.26,0.4))=0.26$,

  * •

$\max_{1\leq l\leq
2}\min(\gamma_{l2},{\beta}_{l})=\max(\min(0.49,0.1),\min(0.9,0.4))=0.4$

and then: $0.6\rightarrow_{G}0.26=0.26$ and $0.49\rightarrow_{G}0.4=0.4$. So
the inequality is not satisfied for $\delta=0$.

For solving the inequality, we rely on: $V(1,1)=\\{1\\}$ and
$V(1,2)=\\{1,2\\}$ and we compute:

  * •

$\theta_{11}=\beta_{1}-\gamma_{11}=0.1-0.6=-0.5$,

  * •

$\theta_{12}=\max(\beta_{1}-\gamma_{12},\beta_{2}-\gamma_{12})=\max(0.1-0.49,0.4-0.49)=-0.09$,

  * •

$\zeta_{11}=\max(\sigma_{G}(0.1,0.6,0.1),\sigma_{G}(0.4,0.26,0.1))=0.15$,

  * •

$\zeta_{12}=\max(\sigma_{G}(0.1,0.49,0.1),\sigma_{G}(0.4,0.9,0.1))=0.15$.

We take $\delta=0.15$ and we have $\gamma_{11}>0$, $\theta_{11}<\delta$ and
$\zeta_{11}=\delta$.

Then we observe that
$G(\underline{\beta}(\delta))_{1}=\min(0.6\rightarrow_{G}0.25,0.49\rightarrow_{G}0.25)=0.25\leq\overline{\beta}(\delta)_{1}=0.25$.
So the inequality is solved with $\delta=0.15$.

######  Proposition 6.

Let $j\in\\{1,2,\dots,m\\}$. Suppose that $\nabla_{j}<1-\beta_{j}$. Then,
there exists $i^{0}\in\\{1,2,\dots,n\\}$ such that:

$\gamma_{ji^{0}}>0\quad\text{ and
}\quad\nabla_{j}\geq\max(\theta_{ji^{0}},\zeta_{ji^{0}}).$

###### Proof.

The inequality $\nabla_{j}<1-\beta_{j}$ and the properties of the lower bound
$\nabla_{j}=\inf E_{j}$ allow us to find a sequence $(\delta_{k})$ in $[0,1]$
such that:

$\forall k\,,\,\delta_{k}\in
E_{j}\,\,\text{i.e}\,\,G(\underline{\beta}(\delta_{k}))_{j}\leq\overline{\beta}(\delta_{k})_{j},\quad(\delta_{k})\rightarrow\nabla_{j},\quad\forall
k\,,\,\nabla_{j}\leq\delta_{k}<1-\beta_{j}.$

By applying (Lemma 4) to each $\delta_{k}$, we get an integer
$i_{k}\in\\{1,2,\dots,n\\}$ such that:

$\gamma_{ji_{k}}>0,\quad\theta_{ji_{k}}<\delta_{k},\quad\zeta_{ji_{k}}\leq\delta_{k}.$

The sequence of integers $k\mapsto i_{k}$ takes its values in the finite set
$\\{1,2,\dots,n\\}$, so by (Theorem 3.6) of [12], it admits a subsequence
$k\mapsto i_{\alpha(k)}$, which is stationary (see the proof of (Theorem 3.6)
of [12]). Therefore, we have an integer $i^{0}\in\\{1,2,\dots,n\\}$ such that:

$\forall k\,,\,i_{\alpha(k)}=i^{0}.$

Then, we deduce:

$\gamma_{ji^{0}}>0,\quad\forall
k\,,\,\theta_{ji^{0}}<\delta_{\alpha(k)},\quad\zeta_{ji^{0}}\leq\delta_{\alpha(k)}.$

By passage to the limit when $k\rightarrow\infty$, we obtain:

$\theta_{ji^{0}}\leq\nabla_{j},\quad\zeta_{ji^{0}}\leq\nabla_{j}.$

∎

As a direct consequence, we have:

######  Corollary 1.

Let $j\in\\{1,2,\dots,m\\}$. Suppose that $\nabla_{j}<1-\beta_{j}$. Then, the
set ${\cal A}_{j}$, see (33), is non empty.

From (Proposition 6) and (Corollary 1), we establish a formula for computing
$\nabla_{j}$ if $\nabla_{j}<1-\beta_{j}$:

######  Proposition 7.

Suppose that $\nabla_{j}<1-\beta_{j}$, then we have:

$\nabla_{j}=\min_{i\in{\cal A}_{j}}\,\max(\theta_{ji},\zeta_{ji}).$

###### Proof.

We put $\tau_{j}=\min_{i\in{\cal A}_{j}}\,\max(\theta_{ji},\zeta_{ji})$ and we
will show $\nabla_{j}=\tau_{j}$ in the following two steps:

  * •

$\nabla_{j}\geq\tau_{j}$: by (Proposition 6), we have an index
$i^{0}\in\\{1,2,\dots,n\\}$ such that:

$\gamma_{ji^{0}}>0,\quad\max(\theta_{ji^{0}},\zeta_{ji^{0}})\leq\nabla_{j}.$

Therefore $i^{0}\in\mathcal{A}_{j}$ and
$\max(\theta_{ji^{0}},\zeta_{ji^{0}})\leq\nabla_{j}$ and we deduce:

$\tau_{j}\leq\max(\theta_{ji^{0}},\zeta_{ji^{0}})\leq\nabla_{j}.$

  * •

$\nabla_{j}=\tau_{j}$. To prove this equality, we proceed by contradiction: we
suppose that $\nabla_{j}\neq\tau_{j}$. We then have $\nabla_{j}>\tau_{j}$. The
set $\mathcal{A}_{j}$ being non-empty (Corollary 1), let $i\in\mathcal{A}_{j}$
such that $\tau_{j}=\max(\theta_{ji},\zeta_{ji})$, so we have:

$\gamma_{ji}>0,\quad\max(\theta_{ji},\zeta_{ji})=\tau_{j}<\nabla_{j}.$ (41)

We take a number $\delta$ verifying $\tau_{j}<\delta<\nabla_{j}$, then
$\delta$ satisfy:

$\delta<\nabla_{j}<1-\beta_{j},$

and the index $i\in\mathcal{A}_{j}$ verify:

$\gamma_{ji}>0,\quad\max(\theta_{ji},\zeta_{ji})=\tau_{j}<\delta<1-\beta_{j}.$

By (Lemma 4), we deduce that $\delta\in E_{j}$, i.e.,
$G(\underline{\beta}(\delta))_{j}\leq\overline{\beta}(\delta)_{j}$), so
$\nabla_{j}=\inf E_{j}\leq\delta$, which is a contradiction.

∎

We then give the explicit analytical formula for computing the Chebyshev
distance $\nabla$ (see (Definition 3) and (Proposition 5)), associated to the
second member $\beta$ of a system of $\min-\rightarrow_{G}$ fuzzy relational
equations $(\Sigma):\Gamma\Box_{\rightarrow_{G}}^{\min}x=\beta$, see (22):

######  Theorem 2.

$\nabla=\max_{1\leq j\leq m}\nabla_{j}\quad\text{where for
}j\in\\{1,2,\dots,m\\},\quad\nabla_{j}=\min(1-\beta_{j},\tau_{j})$ $\text{
with }\quad\tau_{j}=\min_{i\in{\cal
A}_{j}}\,\max(\theta_{ji},\zeta_{ji})\quad\text{ and the convention
}\min_{\emptyset}=1.$

Following (Proposition 5), we have to prove that $\text{for all
}j\in\\{1,2,\dots,m\\},\nabla_{j}=\inf E_{j}$ is equal to
$\min(1-\beta_{j},\tau_{j})$.

###### Proof.

We distinguish the following cases:

  * •

If $\beta_{j}=1$, we deduce from (Lemma 2) that
$\nabla_{j}=0=\min(1-\beta_{j},\tau_{j}).$

  * •

Suppose that $\beta_{j}<1$. We then have:

    * –

If $\mathcal{A}_{j}=\emptyset$, then by (Lemma 2) and (Corollary 1), we have
$\nabla_{j}=1-\beta_{j}$ and $\tau_{j}=1$ (by the convention). Therefore,
$\nabla_{j}=\min(1-\beta_{j},\tau_{j}),$

    * –

If $\mathcal{A}_{j}\neq\emptyset$, then there exists an index
$i\in\mathcal{A}_{j}$ such that $\tau_{j}=\max(\theta_{ji},\zeta_{ji})$.
Let us prove the inequality $\nabla_{j}\leq\tau_{j}$ by contradiction.
Assume that we have $\tau_{j}<\nabla_{j}$. We know from (Lemma 2) that
$\nabla_{j}\leq 1-\beta_{j}$. Let $\delta$ be a number verifying
$\tau_{j}<\delta<\nabla_{j}$. Then, we have:

$\gamma_{ji}>0\quad\text{ and
}\quad\tau_{j}=\max(\theta_{ji},\zeta_{ji})<\delta<\nabla_{j}\leq
1-\beta_{j}.$

By (Lemma 4), we deduce $\delta\in E_{j}$, so $\nabla_{j}=\inf
E_{j}\leq\delta$ which is a contradiction.

To summarize, we know that:

$\nabla_{j}\leq\min(1-\beta_{j},\tau_{j})\quad\text{ and by
(\ref{enplus1})}\quad\nabla_{j}<1-\beta_{j}\Longrightarrow\nabla_{j}=\tau_{j}$

so $\nabla_{j}=\min(1-\beta_{j},\tau_{j})$. ∎

We illustrate this theorem:

######  Example 4.

We continue (Example 3). For $j=1$, we compute
$\tau_{1}=\min_{i\in\mathcal{A}_{1}}\max(\theta_{1i},\zeta_{1i})$ where
$\mathcal{A}_{1}=\\{1,2\\}$. We obtain $\tau_{1}=0.15$. As $1-\beta_{1}=0.9$,
we have $\nabla_{1}=\min(0.9,0.15)=0.15$.

As we will see in (Example 5), $\nabla_{j}=\inf E_{j}$ does not always belong
to the set $E_{j}$ (the set $E_{j}$ is defined in (32)) i.e., $E_{j}$ does not
necessarily admit a minimum element. Our aim in what follows is to
characterize the case in which $E_{j}$ admits a minimum element i.e.,
$\nabla_{j}\in E_{j}$.

We know from (Lemma 2) that $1-\beta_{j}\in E_{j}$ and $\nabla_{j}\leq
1-\beta_{j}$. We are left with the case where $\nabla_{j}<1-\beta_{j}$. Thus,
we have $\beta_{j}<1$. We will need the following lemma:

######  Lemma 5.

Suppose that we have $\beta_{j}<1$, then for all $i\in{\cal A}_{j}$, we have
$\zeta_{ji}<1-\beta_{j}.$

###### Proof.

$\displaystyle\zeta_{ji}$ $\displaystyle=\max_{1\leq l\leq
m}\sigma_{G}(\beta_{l},\gamma_{li},\beta_{j})$ $\displaystyle=\max_{1\leq
l\leq
m}\min(\dfrac{(\beta_{l}-\beta_{j})^{+}}{2},(\gamma_{li}-\beta_{j})^{+})$
$\displaystyle\leq\max_{1\leq l\leq m}\dfrac{(\beta_{l}-\beta_{j})^{+}}{2}$
$\displaystyle\leq\dfrac{1-\beta_{j}}{2}<1-\beta_{j}.$

∎

We use the following sets:

######  Notation 3.

For $j\in\\{1,2,\dots,m\\}$:

$\mathcal{F}_{j}=\\{i\in\mathcal{A}_{j}\mid\theta_{ji}<\zeta_{ji}\\}\quad\text{and}\quad\widetilde{\nabla}_{j}=\min_{i\in\mathcal{F}_{j}}\zeta_{ji}\quad\text{
with the convention }\min_{\emptyset}=1.$ (42)

######  Lemma 6.

Suppose we have $\beta_{j}<1$. We have: $\widetilde{\nabla}_{j}\in E_{j}$.

###### Proof.

We distinguish the following two cases:

  * •

If $\mathcal{F}_{j}=\emptyset$, then $\widetilde{\nabla}_{j}=1\in E_{j}$.

  * •

If $\mathcal{F}_{j}\neq\emptyset$, let $i\in\mathcal{F}_{j}$ such that

$\widetilde{\nabla}_{j}=\zeta_{ji}.$

From $i\in\mathcal{F}_{j}$ and (Lemma 5), we deduce:

$\gamma_{ji}>0\quad\text{and}\quad\theta_{ji}<\zeta_{ji}<1-\beta_{j}$

By taking $\delta=\zeta_{ji}<1-\beta_{j}$, we get:

$\gamma_{ji}>0\,,\quad\theta_{ji}<\delta\quad\text{and}\quad\zeta_{ji}=\delta$

We deduce from (Lemma 4) that we have:

$\widetilde{\nabla}_{j}=\zeta_{ji}=\delta\in E_{j}.$

∎

The characterization of the case where $E_{j}$ admits a minimum element, here
$\nabla_{j}$, is given by:

######  Proposition 8.

Suppose we have $\nabla_{j}<1-\beta_{j}$. Then, we have:

  1. 1.

$\nabla_{j}\leq\widetilde{\nabla}_{j}$,

  2. 2.

$\nabla_{j}\in E_{j}\,\Longleftrightarrow\,\nabla_{j}=\widetilde{\nabla}_{j}.$

We may have $\nabla_{j}\notin E_{j}$ (see in (Example 5)).

###### Proof.

We know from (Lemma 6) that $\widetilde{\nabla}_{j}\in E_{j}$. Then the
definition of $\nabla_{j}=\inf E_{j}$ implies that
$\nabla_{j}\leq\widetilde{\nabla}_{j}.$

To prove the equivalence of the second statement, since from (Lemma 6) we know
that $\widetilde{\nabla}_{j}\in E_{j}$, the equality
$\nabla_{j}=\widetilde{\nabla}_{j}$ implies that $\nabla_{j}\in E_{j}.$

To prove the implication $\Longrightarrow$, let us first remark that the
hypothesis $\nabla_{j}\in E_{j}$ means that $\nabla_{j}=\min E_{j}$.

As we suppose $\nabla_{j}<1-\beta_{j}$, we deduce from (Lemma 4) that there is
an index $i^{0}\in{\cal A}_{j}$ such that

$\theta_{ji^{0}}<\nabla_{j}\quad\text{and}\quad\zeta_{ji^{0}}\leq\nabla_{j}.$

Let us show that we have $i^{0}\in\mathcal{F}_{j}$ i.e.,
$\theta_{ji^{0}}<\zeta_{ji^{0}}$ by contradiction.

Suppose we have $\zeta_{ji^{0}}\leq\theta_{ji^{0}}$. Let us take a number
$\delta$ verifying:

$\theta_{ji^{0}}<\delta<\nabla_{j}.$

We then have:

$\gamma_{ji^{0}}>0\quad\text{and}\quad\zeta_{ji^{0}}\leq\theta_{ji^{0}}<\delta<\nabla_{j}<1-\beta_{j}.$

By applying (Lemma 4) to $\delta$,we obtain that $\delta\in E_{j}$, so
$\nabla_{j}\leq\delta$ which is a contradiction.

Finally, we have:

$\widetilde{\nabla}_{j}=\min_{i\in\mathcal{F}_{j}}\zeta_{ji}\leq\zeta_{ji^{0}}\leq\nabla_{j}$

so $\nabla_{j}=\widetilde{\nabla}_{j}$. ∎

We immediately deduce from (Lemma 1) and (Proposition 5):

######  Corollary 2.

Assume that for all $j\in\\{1,2,\dots,m\\}$, we have either
$\nabla_{j}=1-\beta_{j}$ or $\nabla_{j}=\widetilde{\nabla}_{j}$, then we have
$\nabla\in E$.

We then deduce:

######  Corollary 3.

If $\nabla\in E$, then $G(\underline{\beta}(\nabla))$ is the lowest Chebychev
approximation for $\beta$. Moreover,
$\xi=\Gamma^{t}\Box_{\min}^{\max}\underline{\beta}(\nabla)$ is an approximate
solution for the system $(\Sigma):\Gamma\Box_{\rightarrow_{G}}^{\min}x=\beta$.

(From the second part of the following proof, one can see that if
$\nabla=\min_{d\in\mathcal{D}}\|\beta-d\|$ then $\nabla\in E$).

###### Proof.

By definition of the application $G$, we have
$G(\underline{\beta}(\nabla))=\Gamma\Box_{\rightarrow_{G}}^{\min}\xi$, so
$G(\underline{\beta}(\nabla))\in{\cal D}$ is a consistent second member. By
definition of $\nabla$ (Definition 3), we have
$\|\beta-G(\underline{\beta}(\nabla))\|\geq\nabla$.

From (Proposition 1) and the equality $\nabla=\min E$, we deduce the double
inequality:

$\underline{\beta}(\nabla)\leq
G(\underline{\beta}(\nabla))\leq\overline{\beta}(\nabla).$

By applying the inequality (3), we get:

$\|\beta-G(\underline{\beta}(\nabla))\|\leq\nabla\quad\text{so}\quad\|\beta-G(\underline{\beta}(\nabla))\|=\nabla.$

We have proven that $G(\underline{\beta}(\nabla))$ is a Chebyshev
approximation of $\beta$ and $\xi$ is an approximate solution for the system
$(\Sigma)$.

Let $c\in{\cal D}_{\beta}$ be any Chebyshev approximation of $\beta$, i.e.,
$G(c)=c$ and $\|\beta-c\|=\nabla$. By reusing the inequality (3), we get:

$\underline{\beta}(\nabla)\leq c\leq\overline{\beta}(\nabla).$

As $G$ is an increasing application, see (Proposition 2), and applying this
property to the inequality $\underline{\beta}(\nabla)\leq c$ , we get:

$G(\underline{\beta}(\nabla))\leq G(c)=c.$

∎

With the help of the following example, we show that $E_{j}$ does not
necessarily admit a minimum element and $\nabla\notin E$:

######  Example 5.

We use $\Gamma=\begin{bmatrix}0.41&0.07\\\ 0.29&0.31\end{bmatrix}$ and
$\beta=\begin{bmatrix}0.88\\\ 0.46\end{bmatrix}$. We compute:

  * •

$V(1,1)=\\{1\\}$, $\theta_{11}=0.47$, $\zeta_{11}=0$,

  * •

$V(1,2)=\\{1,2\\}$, $\theta_{12}=0.81$, $\zeta_{12}=0$,

  * •

$V(2,1)=\\{1,2\\}$, $\theta_{21}=0.59$, $\zeta_{21}=0$,

  * •

$V(2,2)=\\{2\\}$, $\theta_{22}=0.15$, $\zeta_{22}=0$.

We deduce that:

$\tau_{1}=0.47,\quad
1-\beta_{1}=0.12,\quad\nabla_{1}=\min(0.12,0.47)=0.12=1-\beta_{1}\in E_{1}$
$\tau_{2}=0.15,\quad
1-\beta_{2}=0.54,\quad\nabla_{2}=\min(0.54,0.15)=0.15<1-\beta_{2}.$

We have $\nabla=\max(\nabla_{1},\nabla_{2})=0.15$. We note that for all
$j\in\\{1,2\\}$, we have ${\cal F}_{j}=\emptyset$. But, we remark that:

$\bullet\,$ We have $\nabla_{1}\in E_{1}$ although ${\cal F}_{1}=\emptyset$
because $\nabla_{1}=1-\beta_{1}$.

$\bullet\,$ We have $\nabla_{2}\notin E_{2}$ because $\nabla_{2}<1-\beta_{2}$
and ${\cal F}_{2}=\emptyset$ which implies
$\nabla_{2}<\widetilde{\nabla_{2}}=1$.

$\bullet\,$ Therefore, we have
$\nabla=\max(\nabla_{1},\nabla_{2})=\nabla_{2}\notin E_{2}$. So, as
$E=E_{1}\cap E_{2}$, we have $\nabla\notin E$ i.e., the set $E$ does not admit
a minimum element.

As we have seen, the Chebyshev distance $\nabla$ may be an infimum. Therefore,
as one might expect, we have:

######  Lemma 7.

If $\nabla\notin E$, then the set of Chebyshev approximations
$\mathcal{D}_{\beta}$, see (30), of the second member $\beta$ of the system
$\Gamma\Box_{\rightarrow_{G}}^{\min}x=\beta$ is empty.

###### Proof.

We prove that $\mathcal{D}_{\beta}$ is empty by contradiction.
Assume that we have an element $d\in\mathcal{D}_{\beta}$ i.e., $G(d)=d$ and
$\|d-\beta\|=\nabla$. From the inequality (3), we deduce:

$\underline{\beta}(\nabla)\leq d\leq\overline{\beta}(\nabla),$

Then, by applying the increasing application $G$ to the inequality
$\underline{\beta}(\nabla)\leq d$, we have:

$G(\underline{\beta}(\nabla))\leq G(d)=d\leq\overline{\beta}(\nabla)$

Then, we have $G(\underline{\beta}(\nabla))\leq\overline{\beta}(\nabla)$ i.e.,
$\nabla\in E$, which is contradiction. ∎

In the next two sections, we will show that for $\min-\rightarrow_{GG}$ and
$\min-\rightarrow_{L}$ systems, the sets $E_{j}$ always admit a minimum
element, i.e., we always have $\nabla_{j}\in E_{j}$ and therefore by (Lemma 1)
and (Proposition 5), we have $\nabla\in E$.

##  5 Chebyshev distance associated to the second member of systems based on
$\min-\rightarrow_{GG}$ composition

In this section, we study the Chebyshev distance $\nabla$ associated to the
second member of a system of $\min-\rightarrow_{GG}$ fuzzy relational
equations $(\Sigma):\Gamma\Box_{\rightarrow_{GG}}^{\min}x=\beta$, see (22),
where $\rightarrow_{GG}$ is the Goguen implication, see (5).

The proofs of some (but not all) of the statements in this section are similar
to those of some of the results in the previous section. To avoid repeating
the same arguments in the proofs, we have retained the notations
$\nabla_{j},\theta_{ji}$ and $\zeta_{ji}$ from the previous section, whose
definitions are here adapted to the case of the $\min-\rightarrow_{GG}$
system. They differ from those given for the $\min-\rightarrow_{G}$ system in
the previous section.

The formula for computing the Chebyshev distance associated to the second
member of a system of $\min-\rightarrow_{GG}$ fuzzy relational equations is
established in (Theorem 3). Thanks to the choice of the same notations
($\nabla_{j},\theta_{ji}$ and $\zeta_{ji}$) for the $\min-\rightarrow_{G}$
system and the $\min-\rightarrow_{GG}$ system, (Theorem 3) is formulated in
the same way as (Theorem 1) for the $\min-\rightarrow_{G}$ system.

We remind that we have $\nabla=\max_{1\leq j\leq m}\nabla_{j}$ where
$\nabla_{j}=\inf E_{j}$ (Proposition 5) and the set $E_{j}$ is defined in
(32). Unlike the $\min-\rightarrow_{G}$ system, which we studied in the
previous section, we will show that in the case of the $\min-\rightarrow_{GG}$
system, for all $j\in\\{1,2,\cdots,m\\}$, we always have $\nabla_{j}\in
E_{j}$, i.e., $\nabla_{j}$ is always the minimum element of the set $E_{j}$
although the Goguen’s implication $\rightarrow_{GG}$ is not continuous with
respect to its two variables. By applying (Lemma 1) and (Proposition 5), we
obtain $\nabla=\min E$ (Theorem 4), where $E$ is defined in (31). Therefore,
in the case of a $\min-\rightarrow_{GG}$ system, we will show that the
Chebyshev distance $\nabla$ (Definition 3) is always a minimum, see (Corollary
5). In fact, we can always compute the lowest Chebyshev approximation of the
second member and an approximate solution of the system $(\Sigma)$, see
(Corollary 4).

We begin by introducing a new function based on the function $\sigma_{GG}$,
see (19), which was introduced in [1]:

$P(u,x,y,z)=\begin{cases}0&\text{ if }u=0,\\\ 0&\text{ if }y=0,\\\
\sigma_{GG}(\dfrac{u}{y},x,1,z)&\text{ if }u>0\text{ and }y>0\end{cases}.$
(43)

We have:

$\sigma_{GG}(\dfrac{u}{y},x,1,z)=\max[(x-\dfrac{u}{y})^{+},\min(\dfrac{(xy-
uz)^{+}}{u+y},1-z)].$ (44)

We use the following notations:

######  Notation 4.

For $1\leq j\leq m,1\leq i\leq n$, to each coefficient $\gamma_{ji}$ of the
matrix $\Gamma$ of the system $(\Sigma)$, see (22), we associate:

  * •

$W(j,i)=\\{l\in\\{1,2,\dots,m\\}\,\mid\,\gamma_{ji}\leq\gamma_{li}\,\text{ and
}\,\gamma_{li}>0\\}$,

  * •

$\theta_{ji}=\max_{l\in W(j,i)}(\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}})$
with the convention $\max\limits_{\emptyset}=0$,

  * •

$\zeta_{ji}=\max_{1\leq l\leq
m}P(\gamma_{ji},\beta_{l},\gamma_{li},\beta_{j})$.

The function $P$, see (43), allows us to solve a particular inequality:

######  Lemma 8.

For all $u,x,y,z,\delta\in[0,1]$ with $u>0$ and $\delta<1-z$, we have:

$\dfrac{y\,\underline{x}(\delta)}{u}\leq\overline{z}(\delta)\,\Longleftrightarrow\,P(u,x,y,z)\leq\delta.$

###### Proof.

We remind that if $y>0$, the following equivalence was established in
(Proposition 2) of [1]:

$\underline{x}(\delta)\leq\dfrac{u}{y}(1\rightarrow_{GG}\overline{z}(\delta))\,\Longleftrightarrow\,\sigma_{GG}(\dfrac{u}{y},x,1,z)\leq\delta.$
(45)

$\Longrightarrow$:
If $y=0$, we have

$P(u,x,y,z)=0\leq\delta.$

If $y>0$, from the inequality $\overline{z}(\delta)<1$ , we deduce :

$\underline{x}(\delta)\leq\dfrac{u}{y}\overline{z}(\delta)=\dfrac{u}{y}(1\rightarrow_{GG}\overline{z}(\delta)).$

So, by (45), we have $P(u,x,y,z)=\sigma_{GG}(\dfrac{u}{y},x,1,z)\leq\delta$.

$\Longleftarrow$:
Suppose that $P(u,x,y,z)\leq\delta$.

$\bullet$ If $y=0$, the inequality
$\dfrac{y\,\underline{x}(\delta)}{u}\leq\overline{z}(\delta)$ is trivial.

$\bullet$ If $y>0$, since $\overline{z}(\delta)<1$, the inequality to prove
is:

$\underline{x}(\delta)\leq\dfrac{u}{y}\overline{z}(\delta))=\dfrac{u}{y}(1\rightarrow_{GG}\overline{z}(\delta)).$

As we have $P(u,x,y,z)=\sigma_{GG}(\dfrac{u}{y},x,1,z)\leq\delta$, by (45) the
inequality
$\underline{x}(\delta)\leq\dfrac{u}{y}(1\rightarrow_{GG}\overline{z}(\delta))$
is verified. ∎

We illustrate this result:

######  Example 6.

Let $u=0.3,x=0.6,y=0.4$ and $z=0.2$. We compute
$\delta:=P(0.3,0.6,0.4,0.2)=\dfrac{xy-uz}{u+y}$ then
$\dfrac{y\,\underline{x}(\delta)}{u}=\overline{z}(\delta)$ so the inequality
is satisfied with $\delta\simeq 0.257$.

We establish the following version of (Lemma 4) for the
$\min-\rightarrow_{GG}$ system:

######  Lemma 9.

Let $j\in\\{1,2,\dots,m\\}$. for all $\delta\in[0,1]$ such that
$\delta<1-\beta_{j}$, we have the following equivalence between the following
two statements:

  1. 1.

$G(\underline{\beta}(\delta))_{j}\leq\overline{\beta}(\delta)_{j}$,

  2. 2.

there exists $i\in\\{1,2,\dots,n\\}$ such that:

$\gamma_{ji}>0,\quad\theta_{ji}<\delta,\quad\zeta_{ji}\leq\delta.$

###### Proof.

$\Longrightarrow$:
We have:

$G(\underline{\beta}(\delta))_{j}=\min_{1\leq i\leq
n}\gamma_{ji}\rightarrow_{GG}[\max_{1\leq l\leq
m}\gamma_{li}\cdot\underline{\beta}(\delta)_{l}]\leq\overline{\beta}(\delta)_{j}=\beta_{j}+\delta<1.$

We deduce that there exists $i\in\\{1,2,\dots n\\}$ such that:

$\gamma_{ji}\rightarrow_{GG}[\max_{1\leq l\leq
m}\gamma_{li}\,\underline{\beta}(\delta)_{l}]=.G(\underline{\beta}(\delta))_{j}\leq\overline{\beta}(\delta)_{j}=\beta_{j}+\delta<1$

which implies

$\gamma_{ji}>\max_{1\leq l\leq
m}\gamma_{li}\,\underline{\beta}(\delta)_{l}\quad\text{ and
}\quad\gamma_{ji}\rightarrow_{GG}[\max_{1\leq l\leq
m}\gamma_{li}\,\underline{\beta}(\delta)_{l}]=\dfrac{1}{\gamma_{ji}}\max_{1\leq
l\leq m}\gamma_{li}\,\underline{\beta}(\delta)_{l}\leq\beta_{j}+\delta$

so we have

$\gamma_{ji}>0\quad\text{and}\quad\forall
l\in\\{1,2,\dots,m\\}\,,\,\gamma_{ji}>\gamma_{li}\,\underline{\beta}(\delta)_{l}\quad\text{
and
}\quad\dfrac{\gamma_{li}\,\underline{\beta}(\delta)_{l}}{\gamma_{ji}}\leq\beta_{j}+\delta=\overline{\beta}(\delta)_{j}<1.$
(46)

By (Lemma 8), since $\delta<1-\beta_{j}$, we know that for all
$l\in\\{1,2,\dots,m\\}$, we have:

$\dfrac{\gamma_{li}\,\underline{\beta}(\delta)_{l}}{\gamma_{ji}}\leq\beta_{j}+\delta=\overline{\beta}(\delta)_{j}\Longleftrightarrow
P(\gamma_{ji},\beta_{l},\gamma_{li},\beta_{j})\leq\delta$

so $\zeta_{ji}:=\max_{1\leq l\leq
m}P(\gamma_{ji},\beta_{l},\gamma_{li},\beta_{j})\leq\delta$.

To establish the inequality $\theta_{ji}<\delta$, we just have to show that we
have:

$\forall l\in W(j,i)\,,\,\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}}<\delta.$

(We have $W(j,i)\not=\emptyset$, because $\gamma_{ji}>0$, so $j\in W(j,i)$)

Let $l\in W(j,i)$ i.e., $0<\gamma_{ji}\leq\gamma_{li}$, and we deduce from
(46):

$\dfrac{\gamma_{li}}{\gamma_{ji}}\,\underline{\beta}(\delta)_{l}=\max(\dfrac{\gamma_{li}}{\gamma_{ji}}\beta_{l}-\dfrac{\gamma_{li}}{\gamma_{ji}}\delta,0)<1.$

Therefore, we have:

$\dfrac{\gamma_{li}}{\gamma_{ji}}\beta_{l}-\dfrac{\gamma_{li}}{\gamma_{ji}}\delta<1$

so $\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}}<\delta$ and
$\theta_{ji}:=\max_{l\in
W(j,i)}(\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}})<\delta.$

$\Longleftarrow$:
Let $i\in\\{1,2,\dots,n\\}$ such that

$\gamma_{ji}>0,\quad\theta_{ji}<\delta,\quad\zeta_{ji}\leq\delta.$

We have:

$G(\underline{\beta}(\delta))_{j}=\min_{1\leq i^{\prime}\leq
n}\gamma_{ji^{\prime}}\rightarrow_{GG}[\max_{1\leq l\leq
m}\gamma_{li^{\prime}}\,\underline{\beta}(\delta)_{l}]\leq\gamma_{ji}\rightarrow_{GG}[\max_{1\leq
l\leq m}\gamma_{li}\,\underline{\beta}(\delta)_{l}]$

and it suffices to show that:

$\gamma_{ji}\rightarrow_{GG}[\max_{1\leq l\leq
m}\gamma_{li}\,\underline{\beta}(\delta)_{l}]\leq\overline{\beta}(\delta)_{j}$

From the general equality
$x\rightarrow_{GG}\max(y,z)=\max(x\rightarrow_{GG}y,x\rightarrow_{GG}z)$, we
deduce:

$\gamma_{ji}\rightarrow_{GG}[\max_{1\leq l\leq
m}\gamma_{li}\,\underline{\beta}(\delta)_{l}]=\max_{1\leq l\leq
m}\gamma_{ji}\rightarrow_{GG}\gamma_{li}\,\underline{\beta}(\delta)_{l}.$

We will establish that

$\forall
l\in\\{1,2,\dots,m\\}\,,\,\gamma_{ji}\rightarrow_{GG}\gamma_{li}\,\underline{\beta}(\delta)_{l}\leq\overline{\beta}(\delta)_{j}=\beta_{j}+\delta.$
(47)

Let $l\in\\{1,2,\dots,m\\}$. We distinguish the following two cases:

  * •

Suppose that $l\in W(j,i)$, i.e., $\gamma_{ji}\leq\gamma_{li}$. We have
$\gamma_{li}>0$. Then, we have

$\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}}\leq\theta_{ji}<\delta.$

We deduce:

$\dfrac{\gamma_{li}}{\gamma_{ji}}\beta_{l}-\dfrac{\gamma_{li}}{\gamma_{ji}}\delta<1$

. so

$\dfrac{\gamma_{li}}{\gamma_{ji}}\underline{\beta}(\delta)_{l}=\max(\dfrac{\gamma_{li}}{\gamma_{ji}}\beta_{l}-\dfrac{\gamma_{li}}{\gamma_{ji}}\delta,0)<1$

which leads to

$\gamma_{ji}\rightarrow_{GG}\gamma_{li}\,\underline{\beta}(\delta)_{l}=\dfrac{\gamma_{li}}{\gamma_{ji}}\underline{\beta}(\delta)_{l}.$

By the hypothesis, we have
$P(\gamma_{ji},\beta_{l},\gamma_{li},\beta_{j})\leq\zeta_{ji}\leq\delta$.

As $\gamma_{ji}>0$ and $\delta<1-\beta_{j}$ , by (Lemma 8), we deduce:

$\dfrac{\gamma_{li}}{\gamma_{ji}}\underline{\beta}(\delta)_{l}\leq\beta_{j}+\delta.$

So, in this case, (47) is proved.

  * •

Suppose that $l\in W(j,i)^{c}$ i.e. $\gamma_{ji}>\gamma_{li}$. Since
$\gamma_{li}\geq\gamma_{li}\underline{\beta}(\delta)_{l}$, we have:

$\gamma_{ji}\rightarrow_{GG}\gamma_{li}\,\underline{\beta}(\delta)_{l}=\dfrac{\gamma_{li}}{\gamma_{ji}}\underline{\beta}(\delta)_{l}.$

As in the previous case, by the inequality
$P(\gamma_{ji},\beta_{l},\gamma_{li},\beta_{j})\leq\zeta_{ji}\leq\delta$ and
(Lemma 8) we then deduce:

$\gamma_{ji}\rightarrow_{GG}\gamma_{li}\,\underline{\beta}(\delta)_{l}=\dfrac{\gamma_{li}}{\gamma_{ji}}\underline{\beta}(\delta)_{l}\leq\beta_{j}+\delta.$

So, we proved (47).

∎

In the previous section, for the $\min-\rightarrow_{G}$ system, (Lemma 4) has
allowed us to prove the results stated in (Proposition 6), (Corollary 1),
(Proposition 7) and (Theorem 2). Thanks to the choice of notations $E_{j}$,
$\nabla_{j}$, $\theta_{ji}$ and $\zeta_{ji}$ which are used for the
$\min-\rightarrow_{G}$ system and the $\min-\rightarrow_{GG}$ system, and
using (Lemma 9), it is easy to establish the same results stated in
(Proposition 6), (Corollary 1), (Proposition 7) and (Theorem 2) for the
$\min-\rightarrow_{GG}$ system. To avoid unnecessary repetition, we only state
a new theorem below (Theorem 3), which corresponds to (Theorem 2) for the
$\min-\rightarrow_{GG}$ system. Both theorems have the same proof.

We then give the explicit analytical formula for computing the Chebyshev
distance $\nabla$ (see (Definition 3) and (Proposition 5)), associated to the
second member $\beta$ of a system of $\min-\rightarrow_{GG}$ fuzzy relational
equations $(\Sigma):\Gamma\Box_{\rightarrow_{GG}}^{\min}x=\beta$, see (22):

######  Theorem 3.

$\nabla=\max_{1\leq j\leq m}\nabla_{j}\quad\text{where for
}j\in\\{1,2,\dots,m\\},\quad\nabla_{j}=\min(1-\beta_{j},\tau_{j})$ $\text{
with }\quad\tau_{j}=\min_{i\in{\cal
A}_{j}}\,\max(\theta_{ji},\zeta_{ji})\quad\text{ and the convention
}\min_{\emptyset}=1.$

We illustrate this theorem:

######  Example 7.

Let us reuse the matrix $\Gamma=\begin{bmatrix}0.6&0.49\\\ 0.26&0.9\\\
\end{bmatrix}$ and the vector $\beta=\begin{bmatrix}0.1\\\ 0.4\end{bmatrix}$.
For $j=1$, we have:

$\displaystyle G(\underline{\beta}(\delta))_{1}$ $\displaystyle=\min_{1\leq
i\leq 2}(\gamma_{1i}\rightarrow_{GG}(\max_{1\leq l\leq
m}\gamma_{li}\cdot\underline{\beta}(\delta)_{l}))$
$\displaystyle=\min(0.6\rightarrow_{GG}(\max_{1\leq l\leq
2}\gamma_{l1}\cdot\underline{\beta}(\delta)_{l}),0.49\rightarrow_{GG}(\max_{1\leq
l\leq 2}\gamma_{l2}\cdot\underline{\beta}(\delta)_{l}))$

We compute:

  * •

$\max_{1\leq l\leq 2}\gamma_{l1}\cdot{\beta}_{l}=\max(0.6\cdot 0.1,0.26\cdot
0.4)=0.10$,

  * •

$\max_{1\leq l\leq 2}\gamma_{l2}\cdot{\beta}_{l}=\max(0.49\cdot 0.1,0.9\cdot
0.4)=0.36$

and then: $0.6\rightarrow_{GG}0.10=0.16$ and $0.49\rightarrow_{GG}0.36=0.73$.
So the inequality
$G(\underline{\beta}(\delta))_{1}\leq\overline{\beta}(\delta)_{1}$ is not
satisfied for $\delta=0$.

For solving the inequality, we rely on: $W(1,1)=\\{1\\}$ and
$W(1,2)=\\{1,2\\}$ and we compute:

  * •

$\theta_{11}=\beta_{1}-\dfrac{\gamma_{11}}{\gamma_{11}}=0.1-1=-0.9$,

  * •

$\theta_{12}=\max(\beta_{1}-\dfrac{\gamma_{12}}{\gamma_{12}},\beta_{2}-\dfrac{\gamma_{12}}{\gamma_{22}})=\max(0.1-1,0.4-\dfrac{0.49}{0.9})=\max(-0.9,-0.14)=-0.14$,

  * •

$\zeta_{11}=\max(P(0.6,0.1,0.6,0.1),P(0.6,0.4,0.26,0.1))=0.05$,

  * •

$\zeta_{12}=\max(P(0.49,0.1,0.49,0.1),P(0.49,0.4,0.9,0.1))=0.22$.

We compute $\tau_{1}=\min(0.05,0.22)=0.05$ so we have
$\nabla_{1}=\min(0.9,0.05)=0.05$.

Then we observe that
$G(\underline{\beta}(\nabla_{1}))_{1}=\min(0.6\rightarrow_{G}0.09,0.49\rightarrow_{G}0.31)=0.15\leq\overline{\beta}(\nabla_{1})_{1}=0.15$.
So the inequality is solved with $\nabla_{1}=0.05$.

Although for the t-norm product, its associated residual implicator
$\rightarrow_{GG}$ (called Goguen’s implication) is not continuous with
respect to its two variables, we show in the remainder of this section that
the lower bounds $\nabla_{j}$ and $\nabla$ are in fact minimum elements of the
sets $E_{j}$ and $E$ respectively, i.e., we have $\nabla_{j}\in E_{j}$ and
$\nabla\in E$. Recall that, by (Example 5), these properties are not always
true for the $\min-\rightarrow_{G}$ system.

We begin by establishing two useful lemmas to show that we have $\nabla_{j}\in
E_{j}$ for all $j\in\\{1,2,\dots,m\\}$.

######  Lemma 10.

Let $u,x,y,z\in[0,1]$ satisfy the following two conditions:

  1. 1.

$0<u<y$

  2. 2.

$0<x-\dfrac{u}{y}<1-z$.

Then, we have :

$\dfrac{(xy-uz)^{+}}{u+y}=\dfrac{xy-uz}{u+y}>x-\dfrac{u}{y}.$

###### Proof.

Since by hypothesis we have $x-\dfrac{u}{y}>0$ and $u+y>0$, We just have to
show the strict inequality $\dfrac{xy-uz}{u+y}>x-\dfrac{u}{y}$.

We have:

$\displaystyle\dfrac{xy-uz}{u+y}$ $\displaystyle=\dfrac{xy+xu-xu-uz}{u+y}$
$\displaystyle=x-\dfrac{u}{u+y}(x+z)$
$\displaystyle>x-\dfrac{u}{u+y}(1+\dfrac{u}{y})$
$\displaystyle=x-\dfrac{u}{y}>0.$

∎

######  Lemma 11.

We have:

$\forall i\in{\cal A}_{j}\,,\,\theta_{ji}\leq\zeta_{ji}.$

###### Proof.

Let $i\in{\cal A}_{j}$, i.e., $\gamma_{ji}>0$, we deduce:

$W(j,i)=\\{l\in\\{1,2,\dots,m\\}\,\mid\,\gamma_{ji}\leq\gamma_{li}\,\,\text{and}\,\,\gamma_{li}>0\\}\not=\emptyset.$

We recall that $\theta_{ji}:=\max_{l\in
W(j,i)}(\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}})$ and
$\zeta_{ji}=\max_{1\leq l\leq
m}P(\gamma_{ji},\beta_{l},\gamma_{li},\beta_{j})$.

For all $l\in W(j,i)$, let us show the inequality:

$\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}}\leq\zeta_{ji}.$

Since $\gamma_{ji}>0$ and $\gamma_{li}>0$, we have:

$\displaystyle\zeta_{ji}$ $\displaystyle\geq
P(\gamma_{ji},\beta_{l},\gamma_{li},\beta_{j})$
$\displaystyle=\max((\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}})^{+},\,\min(\dfrac{(\beta_{l}\gamma_{li}-\beta_{j}\gamma_{ji})^{+}}{\gamma_{ji}+\gamma_{li}},1-\beta_{j}))\quad\text{see
(\ref{eq:egalitesursigmagg})}$
$\displaystyle\geq(\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}})^{+}$
$\displaystyle\geq\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}}.$

Therefore

$\zeta_{ji}\geq\max_{l\in
W(j,i)}(\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}})=\theta_{ji}.$

∎

We are now able to show that for $j\in\\{1,2,\dots,m\\}$, we have
$\nabla_{j}\in E_{j}$ i.e., $\nabla_{j}=\min E_{j}$, and therefore $\nabla\in
E$ i.e., $\nabla=\min E$.

######  Theorem 4.

For all $j\in\\{1,2,\dots,m\\}$ , we have:

$\nabla_{j}=\min E_{j}\quad\text{ i.e.,}\quad\nabla_{j}\in E_{j}.$

Therefore:

$\nabla=\min E.$

###### Proof.

From (Lemma 2), we know that $1-\beta_{j}\in E_{j}$ and $\nabla_{j}\leq
1-\beta_{j}$.

It remains to show that $\nabla_{j}=\min E_{j}$ under the hypothesis
$\nabla_{j}<1-\beta_{j}$.

From (Theorem 3) and (Lemma 11) we know:

$\nabla_{j}=\min(1-\beta_{j},\tau_{j})=\tau_{j}<1\quad\text{and}\quad\tau_{j}=\min_{i\in{\cal
A}_{j}}\max(\theta_{ji},\zeta_{ji})=\min_{i\in{\cal A}_{j}}\zeta_{ji}.$

Therefore ${\cal A}_{j}\not=\emptyset$. Let $i\in{\cal A}_{j}$ i.e.,
$\gamma_{ji}>0$, such that:

$\nabla_{j}=\tau_{j}=\max(\theta_{ji},\zeta_{ji})=\zeta_{ji}.$ (48)

To show that $\nabla_{j}\in E_{j}$, we will prove that $\nabla_{j}$ satisfies
the second assumption of (Lemma 9). Taking into account the hypothesis
$\nabla_{j}<1-\beta_{j}$ and the equality $\nabla_{j}=\zeta_{ji}$, see (48),
we have to show the strict inequality:

$\theta_{ji}<\zeta_{ji}.$ (49)

Let us prove this strict inequality $\theta_{ji}<\zeta_{ji}$ in the following
two steps:

$\bullet\,$ If $\nabla_{j}=0$ : we must prove that $\theta_{ji}<0$.

Since $W(j,i)\neq\emptyset$ (we have $j\in W(j,i)$), let $l\in W(j,i)$ be such
that $\theta_{ji}=\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}}$. We have

$\displaystyle 0=\nabla_{j}=$ $\displaystyle\zeta_{ji}$ $\displaystyle\geq
P(\gamma_{ji},\beta_{l},\gamma_{li},\beta_{j})$
$\displaystyle=\max((\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}})^{+},\min(\dfrac{(\beta_{l}\gamma_{li}-\beta_{j}\gamma_{ji})^{+}}{\gamma_{ji}+\gamma_{li}},1-\beta_{j}))\quad\text{see
(\ref{eq:egalitesursigmagg})}$

Since $1-\beta_{j}>\nabla_{j}=0$, we deduce
$\dfrac{(\beta_{l}\gamma_{li}-\beta_{j}\gamma_{ji})^{+}}{\gamma_{ji}+\gamma_{li}}=0$,
which implies $\beta_{l}\gamma_{li}\leq\beta_{j}\gamma_{ji}$. We have:

$\displaystyle\theta_{ji}$
$\displaystyle=\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}}$
$\displaystyle\leq\dfrac{\gamma_{ji}}{\gamma_{li}}\beta_{j}-\dfrac{\gamma_{ji}}{\gamma_{li}}$
$\displaystyle=\dfrac{\gamma_{ji}}{\gamma_{li}}(\beta_{j}-1)<0.$

$\bullet\,$ If $\nabla_{j}>0$: let us prove by contradiction the strict
inequality $\theta_{ji}<\zeta_{ji}$.
Assume we have $\theta_{ji}\geq\zeta_{ji}.$ Then, by (Lemma 11) we have:

$\theta_{ji}=\zeta_{ji}.$

Let $l\in W(j,i)$ be such that
$\theta_{ji}=\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}}$. So we have

$\nabla_{j}=\zeta_{ji}=\theta_{ji}=\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}}>0.$
(50)

We then have:

$\displaystyle 1-\beta_{j}$ $\displaystyle>\nabla_{j}$
$\displaystyle=\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}}$
$\displaystyle=\zeta_{ji}$ $\displaystyle\geq
P(\gamma_{ji},\beta_{l},\gamma_{li},\beta_{j})\quad\text{see
(\ref{eq:egalitesursigmagg})}$
$\displaystyle=\max(\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}},\min(\dfrac{(\beta_{l}\gamma_{li}-\beta_{j}\gamma_{ji})^{+}}{\gamma_{ji}+\gamma_{li}},1-\beta_{j})).$

Therefore:

$\min(\dfrac{(\beta_{l}\gamma_{li}-\beta_{j}\gamma_{ji})^{+}}{\gamma_{ji}+\gamma_{li}},1-\beta_{j})\leq\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}}<1-\beta_{j}.$

This last inequality implies:

$\dfrac{(\beta_{l}\gamma_{li}-\beta_{j}\gamma_{ji})^{+}}{\gamma_{ji}+\gamma_{li}}\leq\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}}<1-\beta_{j}.$

We put $u=\gamma_{ji},x=\beta_{l},y=\gamma_{li},z=\beta_{j}$. By the previous
calculations, we have:

  * •

$0<u<y$ because $l\in W(j,i)$ and
$\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}}=\nabla_{j}>0$,

  * •

$0<x-\dfrac{u}{y}=\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}}<1-\beta_{j}=1-z$.

Applying (Lemma 10), we get:

$\dfrac{(xy-uz)^{+}}{u+y}>x-\dfrac{u}{y}.$

We replace $u,x,y,z$ with their values. This leads to the following
inequality:

$\dfrac{(\beta_{l}\gamma_{li}-\beta_{j}\gamma_{ji})^{+}}{\gamma_{ji}+\gamma_{li}}>\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}}$

which contradicts

$\dfrac{(\beta_{l}\gamma_{li}-\beta_{j}\gamma_{ji})^{+}}{\gamma_{ji}+\gamma_{li}}\leq\beta_{l}-\dfrac{\gamma_{ji}}{\gamma_{li}}.$

We have therefore shown the strict inequality $\theta_{ji}<\zeta_{ij}$, see
(49). Therefore $\nabla_{j}\in E_{j}$.

As a consequence, since we proved that for all $j\in\\{1,2,\dots,m\\}$ we have
$\nabla_{j}\in E_{j}$, we deduce from (Lemma 1) and (Proposition 5) that
$\nabla=\min E\text{ i.e., }\nabla\in E$. ∎

The equality $\nabla=\min E$ allows us to prove directly that the set of
Chebyshev approximations $\mathcal{D}_{\beta}$, see (30), always has a minimum
element. We also give an approximate solution:

######  Corollary 4.

$G(\underline{\beta}(\nabla))$ is the lowest Chebychev approximation for
$\beta$. Moreover,
$\xi=\Gamma^{t}\Box_{T_{P}}^{\max}\underline{\beta}(\nabla)$ is an approximate
solution for the system
$(\Sigma):\Gamma\Box_{\rightarrow_{GG}}^{\min}x=\beta$.

###### Proof.

Same proof as (Corollary 3) but using the $\min-\rightarrow_{GG}$ composition.
∎

By definition of $\nabla$ (Definition 3) and the above corollary, it is clear
that:

######  Corollary 5.

We have:

$\nabla=\min_{d\in{\cal D}}\|\beta-d\|.$

and the set of Chebyshev approximations $\mathcal{D}_{\beta}$, see (30), is
non-empty.

##  6 Chebyshev distance associated to the second member of systems based on
$\min-\rightarrow_{L}$ composition

In this section, we study the Chebyshev distance $\nabla$, see (Definition 3),
associated to the second member of a system of $\min-\rightarrow_{L}$ fuzzy
relational equations $(\Sigma):\Gamma\Box_{\rightarrow_{L}}^{\min}x=\beta$,
see (22), where $\rightarrow_{L}$ is the Łukasiewicz implication, see (6).

To establish the formula for computing the Chebyshev distance $\nabla$, we
prove a version of (Lemma 4) (or (Lemma 9)) for the $\min-\rightarrow_{L}$
system (Lemma 13). In (Lemma 13), we have retained the two notations
$\nabla_{j}$ and $\zeta_{ji}$ from previous sections with their own
definitions for the $\min-\rightarrow_{L}$ system (but not the notation
$\theta_{ji}$, which is not needed).

Since Łukasiewicz’s implication is continuous with respect to its two
variables, establishing the formula for $\nabla$ (Theorem 5), is easier than
for $\min-\rightarrow_{G}$ and $\min-\rightarrow_{GG}$ systems.

We remind that we have $\nabla=\max_{1\leq j\leq m}\nabla_{j}$ where
$\nabla_{j}=\inf E_{j}$ (Proposition 5) and the set $E_{j}$ is defined in
(32). Unlike the $\min-\rightarrow_{G}$ system, we will show that in the case
of the $\min-\rightarrow_{L}$ system (as it is the same for the
$\min-\rightarrow_{GG}$ system), for all $j\in\\{1,2,\cdots,m\\}$, we always
have $\nabla_{j}\in E_{j}$, i.e., $\nabla_{j}$ is always the minimum element
of the set $E_{j}$. By applying (Lemma 1), we obtain $\nabla=\min E$, where
$E$ is defined in (31). Therefore, for a $\min-\rightarrow_{L}$ system, the
Chebyshev distance $\nabla$ is always a minimum, see (Corollary 8). In fact,
we can always compute the lowest Chebyshev approximation of the second member
and an approximate solution of the system $(\Sigma)$, see (Corollary 7).

We rely on the following function:

$L(u,v,x,y)=\max((u-y)^{+},\min((x-v)^{+},\dfrac{(x-y+u-v)^{+})}{2})).$ (51)

and we introduce new notations:

######  Notation 5.

For $1\leq j\leq m,1\leq i\leq n$, to each coefficient $\gamma_{ji}$ of the
matrix $\Gamma$ of the system $(\Sigma)$, see (22), we associate:

$\zeta_{ji}=\max_{1\leq l\leq
m}L(1-\gamma_{ji},1-\gamma_{li},\beta_{l},\beta_{j}).$

The function $L$ allows us to solve an inequality:

######  Lemma 12.

Let $u,v,x,y$ in $[0,1]$. For all $\delta\in[0,1-y[$, we have the following
equivalence:

$(\underline{x}(\delta)-v)^{+}\leq\overline{y}(\delta)-u\,\Longleftrightarrow\,\delta\geq
L(u,v,x,y).$ (52)

###### Proof.

$\Longrightarrow$:

$\bullet$ We have $\delta\geq(u-y)^{+}$. Indeed, we deduce from the inequality
of the left side of (52) and the hypothesis $y+\delta<1$ that we have:

$0\leq\overline{y}(\delta)-u=\min(y+\delta-u,1-u)=y+\delta-u,$

so $\delta\geq u-y$. As $\delta\geq 0$, we obtain that $\delta\geq(u-y)^{+}$.

$\bullet$ Let us prove $\delta\geq\min((x-v)^{+},\dfrac{(x-y+u-v)^{+})}{2})$.

The associativity of the function $\max$ (i.e, $\max(x,y,z)=\max(\max(x,y),z)$
leads to the equality:

$(\underline{x}(\delta)-v)^{+}=(x-\delta-v)^{+}.$ (53)

Indeed, we have:

$\displaystyle(\underline{x}(\delta)-v)^{+}$
$\displaystyle=\max(\underline{x}(\delta)-v,0)$
$\displaystyle=\max(\underline{x}(\delta),v)-v$
$\displaystyle=\max(\max(x-\delta,0),v)-v$
$\displaystyle=\max(x-\delta,0,v)-v$ $\displaystyle=\max(x-\delta-v,-v,0)$
$\displaystyle=\max((x-\delta-v)^{+},-v)=(x-\delta-v)^{+}$

We then deduce:

$\displaystyle(\underline{x}(\delta)-v)^{+}=0$
$\displaystyle\Longleftrightarrow(x-\delta-v)^{+}=0$
$\displaystyle\Longleftrightarrow x-\delta\leq v$
$\displaystyle\Longleftrightarrow x-v\leq\delta$
$\displaystyle\Longleftrightarrow(x-v)^{+}\leq\delta.$ (54)

It is clear that we have:

$\delta\geq(x-v)^{+}\Longrightarrow\delta\geq\min((x-v)^{+},\dfrac{(x-y+u-v)^{+})}{2}).$

Suppose now that $\delta<(x-v)^{+}$. Then by (6), we have:

$0<(\underline{x}(\delta)-v)^{+}=\underline{x}(\delta)-v.$

and the hypothesis becomes:

$0<\underline{x}(\delta)-v\leq\overline{y}(\delta)-u=y+\delta-u$

The inequality $\underline{x}(\delta)-v\leq\overline{y}(\delta)-u=y+\delta-u$
is equivalent to

$\max(x-\delta,0)-v-[y+\delta-u]=\max(x-y+u-v-2\delta,-v-[y+\delta-u])\leq 0.$

so $x-y+u-v-2\delta\leq 0$. As $\delta\geq 0$, we also have $(x-y+u-v)^{+}\leq
2\delta$. Finally, we have:

$\delta\geq\dfrac{(x-y+u-v)^{+}}{2}\geq\min((x-v)^{+},\dfrac{(x-y+u-v)^{+}}{2}).$

To summarize, we have proven that
$\delta\geq\max((u-y)^{+},\min((x-v)^{+},\dfrac{(x-y+u-v)^{+})}{2}))=L(u,v,x,y).$

$\Longleftarrow:$
We must show the inequality:
$(\underline{x}(\delta)-v)^{+}\leq\overline{y}(\delta)-u.$
We note that, by hypothesis, we have $\overline{y}(\delta)=y+\delta<1$.

$\bullet\,$ Let us show that $\overline{y}(\delta)-u=y+\delta-u$ is positive.
In fact, we deduce from the hypothesis:

$\delta\geq(u-y)^{+}\geq u-y\quad\text{ so }\quad y+\delta-u\geq 0.$ (55)

$\bullet$ If $(\underline{x}(\delta)-v)^{+}=0$, the inequality
$(\underline{x}(\delta)-v)^{+}\leq\overline{y}(\delta)-u$ is clear.

$\bullet$ Suppose that $(\underline{x}(\delta)-v)^{+}>0$. We deduce from (53)
that:

$0<(x-\delta-v)^{+}=x-\delta-v\quad\text{so}\quad\delta<x-v=(x-v)^{+}.$

As we suppose that
$\delta\geq\max((u-y)^{+},\min((x-v)^{+},\dfrac{(x-y+u-v)^{+}}{2}))$, we
deduce:

$\delta\geq\dfrac{(x-y+u-v)^{+}}{2}\geq\dfrac{x-y+u-v}{2}.$ (56)

Let us show now the inequality
$(\underline{x}(\delta)-v)^{+}\leq\overline{y}(\delta)-u$. We have:

$\displaystyle(\underline{x}(\delta)-v)^{+}-[\overline{y}(\delta)-u]$
$\displaystyle=\underline{x}(\delta)-v-[y+\delta-u]$
$\displaystyle=\max(x-y+u-v-2\delta,-v-[y+\delta-u])\leq 0,$

because the numbers $x-y+u-v-2\delta$ and $-v-[y+\delta-u]$ are negative (see
(55) and (56)).

∎

We illustrate this result:

######  Example 8.

Let $u=0.3,v=0.4,x=0.5,y=0.2$. We have $0.1=x-v>y-u=-0.1$. We compute
$\delta=L(u,v,x,y)=0.1$ then we have $\delta=0.1<1-y=0.8$ and the inequality
$(\underline{x}(\delta)-v)^{+}\leq\overline{y}(\delta)-u$ is satisfied.

The version of (Lemma 4) (or (Lemma 9)) for the $\min-\rightarrow_{L}$ system
is:

######  Lemma 13.

Let $j\in\\{1,2,\dots,m\\}$. For all $\delta\in[0,1]$ such that
$\delta<1-\beta_{j}$, there is an equivalence between the following two
statements:

  1. 1.

$G(\underline{\beta}(\delta)_{j}\leq\overline{\beta}(\delta)_{j}$

  2. 2.

There exists $i\in\\{1,2,\dots,n\\}$ such that:

$\delta\geq\zeta_{ji}.$

###### Proof.

$\Longrightarrow:$
We have:

$\displaystyle G(\underline{\beta}(\delta))_{j}$ $\displaystyle=\min_{1\leq
i\leq n}\,\gamma_{ji}\rightarrow_{L}[\max_{1\leq l\leq
m}\,T_{L}(\gamma_{li},\underline{\beta}(\delta)_{l})]$
$\displaystyle=\min_{1\leq i\leq n}\,\min(1-\gamma_{ji}+[\max_{1\leq l\leq
m}\,(\gamma_{li}+\underline{\beta}(\delta)_{l}-1)^{+}],1)$

The hypothesis implies that we have an index $i\in\\{1,2,\dots,n\\}$ such
that:

$G(\underline{\beta}(\delta))_{j}=\min(1-\gamma_{ji}+[\max_{1\leq l\leq
m}\,(\gamma_{li}+\underline{\beta}(\delta)_{l}-1)^{+}],1)\leq\overline{\beta}(\delta)_{j}.$

As we suppose that $\beta_{j}+\delta<1$, we have
$\overline{\beta}(\delta)_{j}=\beta_{j}+\delta<1$, and we deduce:

$G(\underline{\beta}(\delta))_{j}=1-\gamma_{ji}+[\max_{1\leq l\leq
m}\,(\gamma_{li}+\underline{\beta}(\delta)_{l}-1)^{+}]\leq\overline{\beta}(\delta)_{j}<1.$

For all $l\in\\{1,2,\dots,m\\}$, we deduce:

$(\gamma_{li}+\underline{\beta}(\delta)_{l}-1)^{+}\leq\overline{\beta}(\delta)_{j}-(1-\gamma_{ji}).$

Let us show that $\forall l\in\\{1,2,\dots,m\\}\,,\,\delta\geq
L(1-\gamma_{ji},1-\gamma_{li},\beta_{l},\beta_{j})$. We have for all
$l\in\\{1,2,\dots,m\\}$:

$(\gamma_{li}+\underline{\beta}(\delta)_{l}-1)^{+}\leq\overline{\beta}(\delta)_{j}-(1-\gamma_{ji}).$

We put $u=1-\gamma_{ji},v=1-\gamma_{li},x=\beta_{l},y=\beta_{j}$. With these
notations, we can easily check that we have:

$\gamma_{li}+\underline{\beta}(\delta)_{l}-1=\underline{x}(\delta)-v\quad\text{and}\quad\overline{\beta}(\delta)_{j}-(1-\gamma_{ji})=\overline{y}(\delta)-u.\quad$

The previous inequality is rewritten as:

$(\underline{x}(\delta)-v)^{+}\leq\overline{y}(\delta)-u$

and we also have $\delta<1-\beta_{j}=1-y$.

By applying (Lemma 12), we obtain $\delta\geq
L(u,v,x,y)=L(1-\gamma_{ji},1-\gamma_{li},\beta_{l},\beta_{j})$.

We have shown $\delta\geq\max_{1\leq l\leq
m}\,L(1-\gamma_{ji},1-\gamma_{li},\beta_{l},\beta_{j})=\zeta_{ji}$.

$\Longleftarrow$:
Suppose we have an index $i\in\\{1,2,\dots,n\\}$ such that:

$\delta\geq\zeta_{ji}=\max_{1\leq l\leq
m}\,L(1-\gamma_{ji},1-\gamma_{li},\beta_{l},\beta_{j}).$

We have:

$G(\underline{\beta}(\delta))_{j}=\min_{1\leq i^{\prime}\leq
n}\,\min(1-\gamma_{ji^{\prime}}+[\max_{1\leq l\leq
m}\,(\gamma_{li^{\prime}}+\underline{\beta}(\delta)_{l}-1)^{+}],1)\leq\min(1-\gamma_{ji}+[\max_{1\leq
l\leq m}\,(\gamma_{li}+\underline{\beta}(\delta)_{l}-1)^{+}],1).$

Let us show the inequality

$\min(1-\gamma_{ji}+[\max_{1\leq l\leq
m}\,(\gamma_{li}+\underline{\beta}(\delta)_{l}-1)^{+}],1)\leq\overline{\beta}(\delta)_{j},$
(57)

which will lead to the inequality to be proved.
We have:

$1-\gamma_{ji}+[\max_{1\leq l\leq
m}\,(\gamma_{li}+\underline{\beta}(\delta)_{l}-1)^{+}]=\max_{1\leq l\leq
m}\,(1-\gamma_{ji}+(\gamma_{li}+\underline{\beta}(\delta)_{l}-1)^{+}).$

We deduce:

$\displaystyle\min(1-\gamma_{ji}+[\max_{1\leq l\leq
m}\,(\gamma_{li}+\underline{\beta}(\delta)_{l}-1)^{+}],1)$
$\displaystyle=\min([\max_{1\leq l\leq
m}\,(1-\gamma_{ji}+(\gamma_{li}+\underline{\beta}(\delta)_{l}-1)^{+})],1)$
$\displaystyle=\max_{1\leq l\leq
m}\,\min(1-\gamma_{ji}+(\gamma_{li}+\underline{\beta}(\delta)_{l}-1)^{+},1).$

To prove (57), it is sufficient to check that $\forall
l\in\\{1,2,\dots,m\\},\,\min(1-\gamma_{ji}+(\gamma_{li}+\underline{\beta}(\delta)_{l}-1)^{+},1)\leq\overline{\beta}(\delta)_{j}$.

In fact, we just have to show that for all $l\in\\{1,2,\dots,m\\}$, that we
have:

$1-\gamma_{ji}+(\gamma_{li}+\underline{\beta}(\delta)_{l}-1)^{+}\leq\overline{\beta}(\delta)_{j}.$
(58)

Let $l\in\\{1,2,\dots,m\\}$. By hypothesis, we have:

$\delta\geq\zeta_{ji}\geq P(1-\gamma_{ji},1-\gamma_{li},\beta_{l},\beta_{j}).$

As $\delta<1-\beta_{j}$, by applying (Lemma 12) with
$u=1-\gamma_{ji},v=1-\gamma_{li},x=\beta_{l},y=\beta_{j}$, we obtain:

$(\underline{x}(\delta)-v)^{+}\leq\overline{y}(\delta)-u.$

Therefore:

$(\gamma_{li}+\underline{\beta}(\delta)_{l}-1)^{+}=(\underline{x}(\delta)-v)^{+}\leq\overline{y}(\delta)-u=\overline{\beta}(\delta)_{j}-(1-\gamma_{ji})$

This last inequality is equivalent to the inequality (58). ∎

We prove that for all $j\in\\{1,2,\dots,m\\}$, the set $E_{j}$, see (32),
admits $\nabla_{j}$ as minimum element:

######  Proposition 9.

For all $j\in\\{1,2,\dots,m\\}$, we have $\nabla_{j}=\min
E_{j}\,\,\text{i.e.,}\,\,\nabla_{j}\in E_{j}$.

###### Proof.

For any $\delta\in[0,1]$, we have:

$G(\underline{\beta}(\delta))_{j}=\min_{1\leq i\leq
n}\,\min(1-\gamma_{ji}+[\max_{1\leq l\leq
m}\,(\gamma_{li}+\underline{\beta}(\delta)_{l}-1)^{+}],1).$

Since the functions
$[0,1]\rightarrow[0,1]:\delta\mapsto\underline{\beta}(\delta)_{l}$ are
continuous, we deduce that the function

$[0,1]\rightarrow[0,1]:\delta\mapsto G(\underline{\beta}(\delta))_{j}$

is continuous.

Since the function $\delta\mapsto\overline{\beta}_{j}(\delta)$ is also
continuous, by applying general continuity theorems (see Corollary of Theorem
4.8 in [12]), we deduce that the set $E_{j}$ is a closed (non-empty) set of
$[0,1]$, and then

$\nabla_{j}=\inf E_{j}=\min E_{j}.$

∎

######  Corollary 6.

We have:

$\nabla=\min E.$ (59)

###### Proof.

Consequence of (Proposition 9), (Lemma 1) and (Proposition 5). ∎

For all $j\in\\{1,2,\dots,m\\}$, to establish the formula for computing
$\nabla_{j}$, we put:

######  Notation 6.

$\tau_{j}:=\min_{1\leq i\leq
n}\,\zeta_{ji}\quad\text{where}\quad\zeta_{ji}=\max_{1\leq l\leq
m}L(1-\gamma_{ji},1-\gamma_{li},\beta_{l},\beta_{j})$ (Notation 5).

We have:

######  Lemma 14.

If $\tau_{j}<1-\beta_{j}$, then $\tau_{j}\in E_{j}$ , so
$\nabla_{j}\leq\tau_{j}$.

###### Proof.

Let $i\in\\{1,2,\dots,n\\}$ be such that $\tau_{j}=\zeta_{ji}$. As we suppose
that $\tau_{j}<1-\beta_{j}$, we remark that $\tau_{j}$ satisfies the condition
of the second statement of (Lemma 13). So $\tau_{j}\in E_{j}$ and then
$\nabla_{j}=\min E_{j}\leq\tau_{j}$. ∎

We now give the explicit analytical formula for computing the Chebyshev
distance $\nabla$ (see (Definition 3) and (Proposition 5)), associated to the
second member $\beta$ of a system of $\min-\rightarrow_{L}$ fuzzy relational
equations $(\Sigma):\Gamma\Box_{\rightarrow_{L}}^{\min}x=\beta$, see (22):

######  Theorem 5.

$\nabla=\max_{1\leq j\leq m}\nabla_{j}\quad\text{where for }\quad
j\in\\{1,2,\dots,m\\},\quad\nabla_{j}=\min(1-\beta_{j},\tau_{j})$ $\text{ with
}\quad\tau_{j}=\min_{1\leq i\leq n}\,\zeta_{ji}.$

###### Proof.

From (Lemma 2), we know that $\nabla_{j}\leq 1-\beta_{j}$.

Let us show the following implication:

$\nabla_{j}<1-\beta_{j}\Longrightarrow\nabla_{j}=\tau_{j}.$

Indeed, if $\nabla_{j}<1-\beta_{j}$, as we have $\nabla_{j}\in E_{j}$,
applying (Lemma 13), we obtain an index $i\in\\{1,2,\dots,n\\}$ such that
$\nabla_{j}\geq\zeta_{ji}$. From the definition of $\tau_{j}$, we deduce:

$\tau_{j}\leq\zeta_{ji}\leq\nabla_{j}.$

As $\nabla_{j}<1-\beta_{j}$, we get $\tau_{j}<1-\beta_{j}$. By applying (Lemma
14), we finally obtain $\nabla_{j}\leq\tau_{j}$, so $\nabla_{j}=\tau_{j}$.

Since the inequality $\nabla_{j}\leq 1-\beta_{j}$ is true (Lemma 2) and using
the two implications

$\nabla_{j}<1-\beta_{j}\Longrightarrow\nabla_{j}=\tau_{j}\quad\text{and by
(Lemma
\ref{lemma:lastlemmaforL})}\quad\tau_{j}<1-\beta_{j}\Longrightarrow\nabla_{j}\leq\tau_{j}$

lead us to obtain the equality $\nabla_{j}=\min(1-\beta_{j},\tau_{j}).$

∎

We illustrate this theorem:

######  Example 9.

Let us reuse the matrix $\Gamma=\begin{bmatrix}0.6&0.49\\\ 0.26&0.9\\\
\end{bmatrix}$ and the vector $\beta=\begin{bmatrix}0.1\\\ 0.4\end{bmatrix}$.
For $j=1$, we have:

$\displaystyle G(\underline{\beta}(\delta))_{1}$ $\displaystyle=\min_{1\leq
i\leq 2}(\gamma_{1i}\rightarrow_{L}(\max_{1\leq l\leq
2}T_{L}(\gamma_{li},\underline{\beta}(\delta)_{l})))$
$\displaystyle=\min(0.6\rightarrow_{L}(\max_{1\leq l\leq
2}T_{L}(\gamma_{l1},\underline{\beta}(\delta)_{l})),0.49\rightarrow_{L}(\max_{1\leq
l\leq 2}T_{L}(\gamma_{l2},\underline{\beta}(\delta)_{l}))).$

We compute:

  * •

$\max_{1\leq l\leq
2}T_{L}(\gamma_{l1},{\beta}_{l})=\max(T_{L}(0.6,0.1),T_{L}(0.26,0.4))=0$,

  * •

$\max_{1\leq l\leq
2}T_{L}(\gamma_{l2},{\beta}_{l})=\max(T_{L}(0.49,0.1),T_{L}(0.9,0.4))=0.3$

and then: $0.6\rightarrow_{L}0=0.4$ and $0.49\rightarrow_{L}0.3=0.81$. So the
inequality $G(\underline{\beta}(\delta))_{1}\leq\overline{\beta}(\delta)_{1}$
is not satisfied for $\delta=0$.

For solving the inequality, we compute:

  * •

$\zeta_{11}=\max(L(1-0.6,1-0.6,0.1,0.1),L(1-0.6,1-0.26,0.4,0.1))=0.3$,

  * •

$\zeta_{12}=\max(L(1-0.49,1-0.49,0.1,0.1),L(1-0.49,1-0.9,0.4,0.1))=0.41$.

We compute $\tau_{1}=\min(0.3,0.41)=0.3$ and $\nabla_{1}=\min(0.9,0.3)=0.3$.

Then we observe that
$G(\underline{\beta}(\nabla_{1}))_{1}=\min(0.6\rightarrow_{L}0,0.49\rightarrow_{L}0)=0.4\leq\overline{\beta}(\nabla_{1})_{1}=0.4$.
So the inequality is solved with $\nabla_{1}=0.3$.

The equality $\nabla=\min E$ (Corollary 6) allows us to prove directly that
the set of Chebyshev approximations $\mathcal{D}_{\beta}$, see (30), always
has a minimum element. We can also give an approximate solution:

######  Corollary 7.

$G(\underline{\beta}(\nabla))$ is the lowest Chebychev approximation for
$\beta$. Moreover,
$\xi=\Gamma^{t}\Box_{T_{L}}^{\max}\underline{\beta}(\nabla)$ is an approximate
solution for the system $(\Sigma):\Gamma\Box_{\rightarrow_{L}}^{\min}x=\beta$.

###### Proof.

Same proof as for (Corollary 3) but using the $\min-\rightarrow_{L}$
composition. ∎

By definition of $\nabla$ (Definition 3) and the above corollary, it is clear
that:

######  Corollary 8.

We have:

$\nabla=\min_{d\in{\cal D}}\|\beta-d\|.$

and the set of Chebyshev approximations $\mathcal{D}_{\beta}$ is non-empty.

##  7 Conclusion

In this article, we studied the inconsistency of systems of $\min-\rightarrow$
fuzzy relational equations. We expressed the Chebyshev distance
$\nabla=\inf_{d\in\mathcal{D}}\|\beta-d\|$ associated to an inconsistent
system of $\min-\rightarrow$ fuzzy relational equations
$\Gamma\Box_{\rightarrow}^{\min}x=\beta$, where $\mathcal{D}$ is the set of
second members of consistent systems defined with the same matrix $\Gamma$, as
the lower bound of the solutions of a vector inequality. From this result, we
gave explicit analytical formulas for computing the Chebyshev distances for
systems of $\min-\rightarrow$ fuzzy relational equations
$\Gamma\Box_{\rightarrow}^{\min}x=\beta$, where $\rightarrow$ is a residual
implicator among the Gödel implication, the Goguen implication or
Łukasiewicz’s implication. An important result is that in the case of the
$\min-\rightarrow_{G}$ system, the Chebyshev distance $\nabla$ may be an
infimum while for $\min-\rightarrow_{GG}$ and $\min-\rightarrow_{L}$ systems
the Chebyshev distance $\nabla$ is always a minimum. For
$\min-\rightarrow_{G}$ systems, we added a sufficient condition for $\nabla$
to be a minimum. For $\min-\rightarrow_{GG}$ systems, $\min-\rightarrow_{L}$
systems, or $\min-\rightarrow_{G}$ systems whose Chebyshev distance has been
verified as a minimum, we can always compute the lowest Chebyshev
approximation of the second member and an approximate solution. However, for
the $\min-\rightarrow_{G}$ systems whose Chebyshev distance has been verified
as not being a minimum, the set of Chebyshev approximations of its second
member is empty.

As perspectives, we may study the structure of the approximate solutions set
of a system of $\min-\rightarrow$ fuzzy relational equations
$\Gamma\Box_{\rightarrow}^{\min}x=\beta$ and that of the set of Chebyshev
approximations of the second member $\beta$ with respect to the Chebyshev
distance $\nabla$. For a $\max-\min$ system, the structure of these sets was
given in [2]. One of the difficulties encountered is the determination of the
set of maximal Chebyshev approximations of the second member $\beta$, which
may be obtained from the solutions of a particular system of
$\min-\rightarrow$ inequalities (as it is done for a $\max-\min$ system in
[2]). Currently, to our knowledge, there is no extensive study of the
solutions set of systems of $\min-\rightarrow$ inequalities. Similarly to [2],
we may also develop a learning method of approximate weight matrices based on
$\min-\rightarrow$ composition according to training data.

As applications, we have the complete solution of the problem of the
invertibility of a fuzzy matrix for $\min-\rightarrow$ composition, where
$\rightarrow$ is the Gödel implication, the Goguen implication or
Łukasiewicz’s implication: we know the set of matrices which admit a pre-
inverse or a post-inverse. In [15], this problem was tackled in the case of
the $\max-\min$ composition.

## References

  * Baaj [2023a] Ismaïl Baaj.  Chebyshev distances associated to the second members of systems of Max-product/Lukasiewicz Fuzzy relational equations.  _arXiv e-prints_ , art. arXiv:2302.08554, January 2023a.  doi:10.48550/arXiv.2302.08554.
  * Baaj [2023b] Ismaïl Baaj.  Max-min Learning of Approximate Weight Matrices from Fuzzy Data.  _arXiv e-prints_ , art. arXiv:2301.06141, January 2023b.  doi:10.48550/arXiv.2301.06141.
  * Cuninghame-Green and Cechlárová [1995] RA Cuninghame-Green and Katarína Cechlárová.  Residuation in fuzzy algebra and some applications.  _Fuzzy Sets and Systems_ , 71(2):227–239, 1995\.
  * Di Nola et al. [1984] Antonio Di Nola, Witold Pedrycz, Salvatore Sessa, and Wang Pei Zhuang.  Fuzzy relation equation under a class of triangular norms: A survey and new results.  _Stochastica_ , 8(2):99–145, 1984.
  * Klement et al. [2013] Erich Peter Klement, Radko Mesiar, and Endre Pap.  _Triangular norms_ , volume 8.  Springer Science & Business Media, 2013.
  * Li and Fang [2010] Pingke Li and Shu-Cherng Fang.  Chebyshev approximation of inconsistent fuzzy relational equations with max-t composition.  In _Fuzzy Optimization_ , pages 109–124. Springer, 2010.
  * Miyakoshi and Shimbo [1985] Masaaki Miyakoshi and Masaru Shimbo.  Solutions of composite fuzzy relational equations with triangular norms.  _Fuzzy Sets and Systems_ , 16(1):53–63, 1985\.
  * Pedrycz [1982] Witold Pedrycz.  Fuzzy relational equations with triangular norms and their resolutions.  _Busefal_ , 11:24–32, 1982.
  * Pedrycz [1985a] Witold Pedrycz.  Applications of fuzzy relational equations for methods of reasoning in presence of fuzzy data.  _Fuzzy sets and systems_ , 16(2):163–175, 1985a.
  * Pedrycz [1985b] Witold Pedrycz.  On generalized fuzzy relational equations and their applications.  _Journal of mathematical Analysis and applications_ , 107(2):520–536, 1985b.
  * Perfilieva and Nosková [2008] Irina Perfilieva and Lenka Nosková.  System of fuzzy relation equations with inf-→ composition: Complete set of solutions.  _Fuzzy Sets and Systems_ , 159(17):2256–2271, 2008.
  * Rudin [1976] Walter Rudin.  _Principles of mathematical analysis_.  International series in pure and applied mathematics. McGraw-Hill, Auckland, 3rd ed edition, 1976.
  * Sanchez [1976] Elie Sanchez.  Resolution of composite fuzzy relation equations.  _Information and control_ , 30(1):38–48, 1976\.
  * Sanchez [1977] Elie Sanchez.  Solutions in composite fuzzy relation equations: Application to medical diagnosis in brouwerian logic.  In M. M. Gupta, G. N. Saridis, and B. R. Gaines, editors, _Fuzzy automata and decision processes_ , pages 221–234. Amsterdam: North-Holland, 1977\.
  * Wu et al. [2022] Yan-Kuen Wu, Yung-Yih Lur, Ching-Feng Wen, and Shie-Jue Lee.  Analytical method for solving max-min inverse fuzzy relation.  _Fuzzy Sets and Systems_ , 440:21–41, 2022.