Strong quasi-ordered residuated system

1. Introduction

The concept of residuated relational systems ordered under a quasi-order relation was introduced in 2018 by S. Bonzio and I. Chajda [1]. Previously, this concept was discussed in [2]. The author introduced and developed the concepts of filters in this algebraic structure as well as several types of filters such as implicative, associated and comparative filters [3,4,5,6].

In [6, Theorem 3.4], it is shown that every comparative filter of a quasi-ordered residuated system \(\mathfrak{ A }\) is an implicative filter of \(\mathfrak{ A }\) and the reverse it need not be valid [6, Example 3.3]. When analyzing the properties of comparative filters, a requirement appears that a quasi-ordered residuated system satisfies the condition

If the system \(\mathfrak{ A }\) satisfies the previous condition, then each comparative filter \( F \) of \(\mathfrak{ A }\) has the following property and, in that case, if the implicative filters satisfy the condition (2), then \( F \) is a comparative filter of \(\mathfrak{ A }\).

In order to achieve the conditions under which each implicative filter will be a comparative filter of a quasi-ordered residuated system, we have designed (Definition 6) the concept of strong quasi-ordered residuated systems. In such systems, the condition (1) is always fulfilled and, therefore, in that systems implicative and comparative filters coincide (Theorem 5). Finally, we show (Theorem 6) that in strong quasi-ordered residuated systems the least upper bound '\(u\sqcup v\)' for each pair \(u,v\) of elements can be determined. We finish this article by the statement (Theorem 7) that \((\mathfrak{A},\sqcup)\) is a distributive upper semi-lattice.

2. Preliminaries

2.1. Concept of quasi-ordered residuated systems

In article [1], S. Bonzio and I. Chajda introduced and analyzed the concept of residual relational systems.

Definition 1. [1, Definition 2.1] A residuated relational system is a structure \(\mathfrak{A} = \langle A, \cdot, \rightarrow, 1, R \rangle\), where \(\langle A, \cdot, \rightarrow, 1 \rangle\) is an algebra of type \(\langle 2, 2, 0 \rangle\) and \(R\) is a binary relation on \(A\) and satisfying the following properties:

• (1)   \((A, \cdot, 1)\) is a commutative monoid;
• (2)   \((\forall x \in A)((x, 1) \in R)\);
• (3)   \((\forall x,y,z \in A)((x \cdot y, z) \in R \Longleftrightarrow (x, y \rightarrow z) \in R)\).

We will refer to the operation \(\cdot\) as multiplication, to \(\rightarrow\) as its residuum and to condition (3) as residuation.

The basic properties for residuated relational systems are subsumed in the following:

Theorem 1. [1,Proposition 2.1] Let \(\mathfrak{A} = \langle A, \cdot, \rightarrow, 1, R \rangle\) be a residuated relational system. Then

• (4)   \((\forall x,y \in A)( x \rightarrow y = 1 \Longrightarrow (x, y) \in R)\);
• (5)  \((\forall x \in A)((x, 1 \rightarrow 1) \in R)\);
• (6)  \((\forall x \in A)((1, x \rightarrow 1) \in R)\);
• (7)   \((\forall x,y,z \in A)( x \rightarrow y = 1 \Longrightarrow (z \cdot x, y) \in R)\);
• (8)  \((\forall x,y \in A)((x, y \rightarrow 1) \in R).\)

Recall that a quasi-order relation \('\preccurlyeq\,'\) on a set \(A\) is a binary relation which is reflexive and transitive (Some authors use the term pre-order relation).

Definition 2. [1, Definition 3.1] A quasi-ordered residuated system (QRS) is a residuated relational system \(\mathfrak{A} = \langle A, \cdot, \rightarrow, 1, \preccurlyeq \rangle\), where \(\preccurlyeq\) is a quasi-order relation in the monoid \((A,\cdot)\).

Example 1. Let \(A = \{1, a, b, c, d\}\) and operations '\(\cdot\)' and '\(\rightarrow\)' defined on \(A\) as follows:

\(\cdot\)	1	a	b	c	d
1	1	a	b	c	d
a	a	a	d	c	d
b	b	d	b	d	d
c	c	c	d	c	d
d	d	d	d	d	d

and

\(\rightarrow\)	1	a	b	c	d
1	1	a	b	c	d
a	1	1	b	c	d
b	1	a	1	c	c
c	1	1	b	1	b
d	1	1	1	1	1

Then \(\mathfrak{A} = \langle A, \cdot,\rightarrow,1\rangle\) is a quasi-ordered residuated systems where the relation '\(\preccurlyeq\)' is defined as follows \[\preccurlyeq : =\{(1,1), (a,1), (b,1), (c,1), (d,1), (b,b), (a,a), (c,c), (d,d), (c,a),(d,a), (d,b), (d,c)\}.\]

Example 2. For a commutative monoid \(A\), let \(\mathfrak{P}(A)\) denote the powerset of \(A\) ordered by set inclusion and '\(\cdot\)' the usual multiplication of subsets of \(A\). Then \(\langle\mathfrak{P}(A),\cdot,\rightarrow,A,\subseteq\rangle\) is a quasi-ordered residuated system in which the residuum are given by \[(\forall X, Y \in \mathfrak{P}(A))(Y \rightarrow X : = \{z \in A : Yz \, \subseteq \, X\}).\]

Example 3. Let \(\mathbb{R}\) be a field of real numbers. Define a binary operations '\(\cdot\)' and '\(\rightarrow\)' on \(A = [0, 1] \, \subset \, \mathbb{R}\) by \[(\forall x,y \in [0,1])(x \cdot y : = max\{0,x+y-1\})\, \, \text{and} \, \, x \rightarrow y : = min\{1,1-x+y\}).\] Then, \( A \) is a commutative monoid with the identity \(1\) and \(\langle A,\cdot, \rightarrow, < , 1\rangle\) is a quasi-ordered residuated system.

Example 4. Let \(A = \langle -\infty,\,1] \, \subset \mathbb{R}\) (the real numbers field). If we define (\cdot\)' and '\(\rightarrow\)' as follows, \((\forall u,v \in A)(u \cdot v := min\{u,v\})\) and \(u \rightarrow v := 1\) if \(u \leqslant v\) and \(u \rightarrow v := v\) if \(v < u\) for all \(u, v \in A\), then \(\mathfrak{A} := \langle A,\cdot, \rightarrow, 1, < \rangle\) is a quasi-ordered residuated system.

Example 5. Any commutative residuated lattice \(\langle A,\cdot,\rightarrow, 0,1,\sqcap, \sqcup, R\rangle \) where \(R\) is a lattice quasi-order is a quasi-ordered residuated system.

Example 6. [7, Example 2.2] Any commutative residuated po-monoid (briefly, a CRPM) \((A,\cdot,\rightarrow,1,\leqslant)\) is a quasi-ordered system.

Remark 1. Quasi-ordered residauted system, generally speaking, differs from the commutative residuated lattice \(\langle A, \cdot, \rightarrow, 0,1, \sqcap, \sqcup, R \rangle\) where \(R\) is a lattice quasi- order. First, our observed system does not have to be limited from below. Second, the observed system does not have to be a lattice. However, the difference between a quasi-ordered relational system and a CRPM (Example 6) is only in order relations since a quasi-order relation does not have to be antisymmetric. More about this last-mentioned algebraic structure can be found in [8].

The following proposition shows the basic properties of quasi-ordered residuated systems.

Proposition 1. [1, Proposition 3.1] Let \(A\) be a quasi-ordered residuated system. Then

• (9)  \((\forall x, y, z \in A)(x \preccurlyeq y \, \Longrightarrow \, (x \cdot z \preccurlyeq y \cdot z \, \wedge \, z \cdot x \preccurlyeq z \cdot y))\);
• (10)  \((\forall x, y, z \in A)(x \preccurlyeq y \, \Longrightarrow \, (y \rightarrow z \preccurlyeq x \rightarrow z \, \wedge \, z \rightarrow x \preccurlyeq z \rightarrow y))\);
• (11)  \((\forall x, y \in A)(x \cdot y \preccurlyeq x \, \wedge \, x \cdot y \preccurlyeq y)\).

2.2. Concept of filters

In this subsection we give some notions that will be used in this article.

Definition 3. [3, Definition 3.1] For a nonempty subset \(F\) of a quasi-ordered residuated system \(\mathfrak{A}\) we say that it is a filter of \(\mathfrak{A}\) if it satisfies conditions:

• (F2)   \((\forall u, v \in A)((u \in F \, \wedge \, u \preccurlyeq v)\, \Longrightarrow \, v \in F)\), and
• (F3)   \((\forall u, v \in A)((u \in F \, \wedge \, u \rightarrow v \in F)\, \Longrightarrow \, v \in F)\).
In the article [3], the conditions were also analyzed:
• (F0)   \(1 \in F\); and
• (F1)   \((\forall u,v \in A)((u \cdot v \in F \,\Longrightarrow \, (u \in F \, \wedge\, v \in F)).\)

In [3] is shown (Proposition 3.2) that (F2) \(\Longrightarrow\) (F1). In addition, it is shown ([3, Proposition 3.4]) that for every nonempty subset of \(F\) of system \(\mathfrak{A}\) is valid (F2) \(\Longrightarrow\) (F0).

Remark 2. In implicative algebras, the term 'implicative filter' is used instead of the term 'filter' we use (see, for example [9,10]) because in the structure we study the concept of filter is determined more complexly than requirements (F3). It is obvious that our filter concept is also a filter in the sense of [9,10,11]. The term 'special implicative filter' is also used in the aforementioned sources if the implicative filter in the sense of [9] satisfies some additional condition.

There is considerable diversity in the literature in the use of terms that cover additional conditions that are met by filters (see, for example [12,13,14]). The terms we opted for our previous papers [5,6] and for use in this paper are taken from [13,14].

Definition 4. [5, Definition 3.1] For a non-empty subset \(F\) of a quasi-ordered residuated system \(\mathfrak{A}\) we say that the implicative filter of \(\mathfrak{A}\) if (F2) and the following condition

• (IF)   \((\forall u,v,z \in A)((u \rightarrow (v \rightarrow z) \in F \, \wedge \, u \rightarrow v \in F)\, \Longrightarrow \, u \rightarrow z \in F)\)

are valid.

Definition 5. [6, Definition 3.1] For a non-empty subset \(F\) of a quasi-ordered residuated system \(\mathfrak{A}\) we say that a comparative filter of \(\mathfrak{A}\) if (F2) and the following condition

• (FC)   \((\forall u,v,z \in A)((u \rightarrow ((v \rightarrow z) \rightarrow v) \in F \, \wedge \, u \in F)\, \Longrightarrow \, v \in F)\)

are valid.

Theorem 2. [6, Theorem 3.4] Any comparative filter of a quasi-ordered residuated system \(\mathfrak{A}\) is an implicative filter of \(\mathfrak{A}\).

Proposition 2. [6, Proposition 3.2] Let \(\mathfrak{ A }\) be a quasi-ordered residuated system that satisfies the condition:

• (12)   \( (\forall u, v \in A)(u \rightarrow v = ((u \rightarrow v)\rightarrow v)\rightarrow v) \).

Then any comparative filter \(F\) in \(\mathfrak{ A }\) satisfies the the condition:

• (13)   \( (\forall u,v \in A) ((u \rightarrow v) \rightarrow v \in F \, \Longrightarrow \, (v \rightarrow u)\rightarrow u \in F) \).

Theorem 3. [6, Theorem 3.3] Let \(F\) be an implicative filter of a quasi-ordered residuated system \(\mathfrak{A}\) satisfying (13). Then \(F\) is a comparative filter of \(\mathfrak{A}\).

Notions and notations that are used but not previously defined in this paper can be found in [1,3,4,5].

3. Concept of strong quasi-ordered residuated systems

In this section we introduce the concept of strong quasi-ordered residuated systems. Considering the fact that the quasi-order relation '\(\preccurlyeq\)', which appears in the determination of this algebraic system, does not have to be antisymmetric, the following definition gets a clearer meaning.

Definition 6. For a quasi-ordered residuated system \(\mathfrak{A}\) it is said to be a strong quasi-ordered residuated system if the following holds:

• (14)   \((\forall u, v \in A)((u \rightarrow v) \rightarrow v \preccurlyeq (v \rightarrow u) \rightarrow u \, \wedge \, (v \rightarrow u) \rightarrow u \preccurlyeq (u \rightarrow v) \rightarrow v )\).

Remark 3. Note that if \[(\forall u, v \in A)((u \rightarrow v) \rightarrow v = (v \rightarrow u) \rightarrow u)\] is valid, then (14) is also valid. The reverse does not have to be true.

The following is an example of a non strong QRS:

Example 7. Let \(A = \{1,a,b\}\) and the operations '\(\cdot\)' and '\(\rightarrow\)' be defined on \(A\) as follows:

\(\cdot\)	1	a	b
1	1	a	b
a	a	a	a
b	b	a	b

and

\(\rightarrow\)	1	a	b
1	1	a	b
a	1	1	1
b	1	a	1

Then \(\mathfrak{A} = \langle A, \cdot,\rightarrow,1\rangle\) is a quasi-ordered residuated systems where the relation '\(\preccurlyeq\)' is defined as follows \[\preccurlyeq := \{(1,1), (a,a), (b,b), (a,1), (b,1), (a,b)\}.\] It can be easily checked that \(\mathfrak{A}\) is a quasi-ordered residuated system. Since \[(a \rightarrow b) \rightarrow b = 1 \rightarrow b = b \, \, \, \text{and} \, \, \, (b \rightarrow a) \rightarrow a = a \rightarrow a = 1,\] we have \((a \rightarrow b) \rightarrow b \preccurlyeq (b \rightarrow a) \rightarrow a\) but \(\neg((b \rightarrow a) \rightarrow a \preccurlyeq (a \rightarrow b) \rightarrow b)\). Thus, \(\mathfrak{A}\) is not a strong quasi-ordered residuated system.

Now, we give an example of strong quasi-ordered residuated system.

Example 8. Let \(A = \{1, a, b, c\}\) and operations '\(\cdot\)' and '\(\rightarrow\)' defined on \(A\) as follows:

\(\cdot\)	1	a	b	c
1	1	a	b	c
a	a	a	a	a
b	b	a	b	a
c	c	a	a	c

and

\(\rightarrow\)	1	a	b	c
1	1	a	b	c
a	1	1	1	1
b	1	c	1	c
c	1	b	b	1

Then \(\mathfrak{A} = \langle A, \cdot,\rightarrow,1\rangle\) is a quasi-ordered residuated systems where the relation '\(\preccurlyeq\)' is defined as follows \[\preccurlyeq : = \{(1,1), (a,1), (b,1), (c,1), (a,a), (b,b), (c,c), (a,b),(a,c)\}.\] Direct verification it can prove that \(\mathfrak{ A }\) is a strong quasi-ordered residuated system.

Remark 4. It is generally known that a quasi-order relation \(\preccurlyeq\) on a set \(A\) generates an equivalence relation \( \equiv_{\preccurlyeq}: = \, \preccurlyeq \, \cap \, \preccurlyeq^{-1}\) on \( A \). Due to properties (9) and (10), this equivalence is compatible with the operations in \(\mathfrak{ A }\). Thus, \( \equiv_{\preccurlyeq}\) is a congruence on \(\mathfrak{ A }\). In light of this remark, the condition (14) can be written in the form \[(\forall u, v \in A)((u \rightarrow v) \rightarrow v \equiv_{\preccurlyeq} (v \rightarrow u) \rightarrow u).\] In this paper, we shall investigate the structure of strong quasi-ordered residuated systems.

Theorem 4. In a strong quasi-ordered residuated system \(\mathfrak{A}\) the following holds:

• (15)   \((\forall u, v \in A)(u \preccurlyeq v \, \Longrightarrow \, v \equiv_{\preccurlyeq} (v \rightarrow u) \rightarrow u).\)

Proof. Assume that \(\mathfrak{ A }\) is a strong quasi-ordered system. For given \( u, v \in A\), let be \( u \preccurlyeq v \). First, as \(v \preccurlyeq (u \rightarrow v) \rightarrow v\) is valid according to (11), from here we immediately get the following \[v \preccurlyeq (u \rightarrow v) \rightarrow v \preccurlyeq (v \rightarrow u) \rightarrow u.\] by (14). Secondly, from \(u \preccurlyeq v\) it follows \(1 \preccurlyeq u \rightarrow v\) by (3). From here, applying (10), we obtain \((u \rightarrow v) \rightarrow v \preccurlyeq 1 \rightarrow v\). Thus \[(v \rightarrow u)\rightarrow u \equiv_{\preccurlyeq} (u \rightarrow v) \rightarrow v) \preccurlyeq 1 \rightarrow v\] with respect (14). Applying the claim (d) of [1, Proposition 2.3], from here we get \((v\rightarrow u) \rightarrow u \preccurlyeq v\). This proves that \( u \preccurlyeq v \, \Longrightarrow \, v \equiv_{\preccurlyeq} (v\rightarrow u) \rightarrow u \) is valid.

As a significant consequences of this theorem we can prove some important properties of strong quasi-ordered residuared systems. In what follows, we need the following lemma:

Lemma 1. Let \(\mathfrak{A}\) be a strong quasi-ordered residuated system. Then the following holds: \[(\forall u, v \in A)(u \rightarrow v \equiv_{\preccurlyeq} ((u \rightarrow v)\rightarrow v)\rightarrow v).\]

Proof. Let \(\mathfrak{A}\) be a quasi-ordered residuated system and let \(u, v\in A\) be arbitrary elements. As \( v \preccurlyeq u \rightarrow v \) holds according to (11), by Theorem 4, we conclude that the required formula is valid.

Thus, designing a strong quasi-ordered residual system environment in such an environment it can be proven the following result:

Theorem 5. Let \(\mathfrak{A}\) be a strong quasi-ordered residuated system. Then the comparative and implicative filters of \(\mathfrak{ A }\) coincide.

Proof. By Theorem 2, each comparative filter is an implicative filter in any quasi-ordered residuated system. The second part of the proof of this theorem follows directly from the previous Lemma and Theorem 3.

The notion "least upper bound" is well-defined for partial order relations. Although it is not common to use this definition for quasi-order relations because, in the general case, for quasi-order relations the "least upper bound" is not unique, when it comes to a strong quasi-ordered relational system, this concept can be determined as shown in the following theorem:

Theorem 6. Let \(\mathfrak{A}\) be a strong quasi-ordered residuated system. For any \(u, v \in A\), the element \[u \, \sqcup v := \, (v \rightarrow u) \rightarrow u \, \equiv_{\preccurlyeq} \, (u \rightarrow v) \rightarrow v\] is the least upper bound of \(u\) and \(v\).

Proof. It is clear that the following hold: \[u \preccurlyeq (v \rightarrow u) \rightarrow u \, = \, u \sqcup v\] and \[v \preccurlyeq (u \rightarrow v) \rightarrow v \equiv_{\preccurlyeq} (v \rightarrow u) \rightarrow u \, = \, u \sqcup v\] by (11) and (14). This shows that \( u \sqcup v \) is the upper bound for \( u \) and \(v \). If \(z\) is any common upper bound of \(u\) and \(v\), then by Theorem 4, \[z \equiv_{\preccurlyeq} (z \rightarrow u) \rightarrow u \, \, \, \text{and} \, \, \, z \equiv_{\preccurlyeq} (z \rightarrow v) \rightarrow v.\] On the other hand, from \(v \preccurlyeq (z \rightarrow v) \rightarrow v\) it follows \[((z \rightarrow v) \rightarrow v) \rightarrow u \preccurlyeq v \rightarrow u\] and \[(v \rightarrow u) \rightarrow u \preccurlyeq (((z \rightarrow v) \rightarrow v) \rightarrow u) \rightarrow u \, \equiv_{\preccurlyeq} \, (z \rightarrow u) \rightarrow u \, \equiv_{\preccurlyeq} \, z\] according to (10) and (15). Therefore, \(u \sqcup v\) is the least upper bound of \(u\) and \(v\) in the system \(\mathfrak{A}\).

The following example shows that condition (14) is crucial for the defining of the least upper bound.

Example 9. Let \(A = \{1, a, b, c, d, e\}\) and operations '\(\cdot\)' and '\(\rightarrow\)' defined on \(A\) as follows:

\(\cdot\)	1	a	b	c	d	e
1	1	a	b	c	d	e
a	a	a	a	a	a	a
b	b	a	b	a	b	a
c	c	a	a	a	a	c
d	d	a	b	a	v	c
e	e	a	a	c	c	e

and

\(\rightarrow\)	1	a	b	c	d	e
1	1	a	b	c	d	e
a	1	1	1	1	1	1
b	1	e	1	e	1	e
c	1	b	b	1	1	1
d	1	a	b	e	1	e
e	1	b	b	d	b	1

\end{center} Then \(\mathfrak{A} = \langle A, \cdot,\rightarrow,1\rangle\) is a quasi-ordered residuated systems where the relation '\(\preccurlyeq\)' is defined as follows \(\preccurlyeq : = \{(1,1), (a,1), (b,1), (c,1), (d,1), (e,1), (a,a), (a,b), (a,c)\), \((a,d), (a,e), (b,b), (b,d), (c,c), (c,d),(c,e), (d,d)\}.\)

By direct verification it can be proved that \(\mathfrak{ A }\) is a quasi-ordered residuated system but is is not a strong system. For example, for \(u = b\) and \(v = c\), we have \((b\rightarrow c) \rightarrow c = e \rightarrow c = d\) and \((c \rightarrow b) \rightarrow b = b \rightarrow b = 1\). Since \(d \neq 1\), we conclude that \(\mathfrak{ A }\) is not a strong system. However, on the other hand, in this case we still have \(b \preccurlyeq d\) and \(c \preccurlyeq d\). Obviously, \(1\) is an upper bound of \(b\) and \(c\) also, but we cannot define the least upper bound \(b \sqcup c\) as in the previous theorem.

We end this section by the following theorem:

Theorem 7. Let \(\mathfrak{A}\) be a strong quasi-ordered residuated system. Then \((\mathfrak{A},\sqcup)\) is a distributive upper semi-lattice in the following sense \[(\forall x,y, z \in A)((x \sqcup y)\sqcup z \equiv_{\preccurlyeq} (x \sqcup z)\sqcup(y\sqcup z)).\]

Proof. Let \(x,y, z\) be arbitrary elements of a strong quasi-ordered residuated system. From \(x \preccurlyeq x \sqcup z\) and \(y \preccurlyeq y \sqcup z\) it follows \(x \sqcup y \preccurlyeq (x \sqcup z)\sqcup (y \sqcup z)\). At the other hand, we have \(z \preccurlyeq (x \sqcup z)\sqcup (y\sqcup z)\). Thus \[(x \sqcup y)\sqcup z \preccurlyeq (x \sqcup z)\sqcup (y \sqcup z).\] Conversely, from \(x \preccurlyeq x\sqcup y \preccurlyeq (x\sqcup y)\sqcup z\) and \( z \preccurlyeq (x\sqcup y)\sqcup z\) it follows \(x \sqcup z \preccurlyeq (x \sqcup y)\sqcup z\). Analogous to the previous one, we can get \(y \sqcup z \preccurlyeq (x \sqcup y)\sqcup z\). Hence \[(x\sqcup z)\sqcup (y \sqcup z) \preccurlyeq (x \sqcup y)\sqcup z.\] This proves the theorem.

Remark 5. The term 'distributive upper semi-lattice' used here differs from the concept of 'distributive join semi-lattice' which appears for example in the book [15] (pp. 99).

Of course, the question arises quite naturally:

Since \((\mathfrak{A}, \sqcup) \) is an upper semi-lattice, how are the standard statements for semi-lattices applied in this case?

4. Final conclusion and further work

The concept of quasi-ordered residuated system was introduced and analyzed by Bonzio and Chajda in [1]. This system differs from the commutative residuated lattice \(\langle A, \cdot, \rightarrow, 0,1, \sqcap, \sqcup, R \rangle\) where \(R\) is a lattice quasi-order (see Remark 1). In this article, a specific quasi-ordered system it was designed in which it was possible to determine the least upper bound for any two elements of the system. In such a newly defined environment, implicative and comparative filters have been shown to coincide.

In future work, we could study the internal structure of such a designed quasi-ordered residuated system as well as some of its substructures such as, for example, filters (so-called prime filter) that satisfy the additional condition

\[(\forall u,v \in A)(u\sqcup v \in F \, \Longrightarrow \, (u \in F \, \vee \, v \in F)). \]

Acknowledgments

The author is obliged to thank the reviewer because designing answers to his questions and suggestions which in relation to the ideas, concepts and processes with them presented in the first version of the text significantly contributed to the concept of the second version of the text in which terms and propositions in it are exposed in a much clearer manner.

Conflicts of Interest

The author declares no conflict of interest.