The concept of residuated relational systems ordered under a quasi-order relation was introduced in 2018 by S. Bonzio and I. Chajda. In such algebraic systems, we have introduced and developed the concepts of implicative and comparative filters. In addition, we have shown that every comparative filter is an implicative filter at the same time and that converse it does not have to be. In this article, as a continuation of previous research, we introduce the concept of strong quasi-ordered residuated systems and we show that in such systems implicative and comparative filters coincide. In addition, we show that in such systems the concept of least upper bound for any two pair of elements can be determined.
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
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.
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:
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
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 |
| \(\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 |
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
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:
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
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
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:
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].
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:
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 |
| \(\rightarrow\) | 1 | a | b |
|---|---|---|---|
| 1 | 1 | a | b |
| a | 1 | 1 | 1 |
| b | 1 | a | 1 |
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 |
| \(\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 |
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:
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 |
| \(\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 |
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?
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)). \]