Abstract
We give set-theoretical characterizations both for weakly idempotent lattices and interlaced weakly idempotent bilattices. In particular, we obtain a set-theoretical representation for interlaced bilattices and distributive bilattices (without bounds).
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
In [9], arbitrary lattices were characterized by sets which generalize the well-known classical Birkhoff–Stone set-theoretical representation theorem for distributive lattices and Boolean algebras [8, 75] (for another generalization see [10, 12, 13, 20, 52]). Set-theoretical representations for bounded distributive bilattices are well-known and were given in [26]. However, the same problem is still open for interlaced bilattices, which have applications in multi-valued logic, artificial intelligence, logic programming and other directions of applied mathematics and computer science.
There exist various extensions of the concept of a lattice. For example, in [24, 25], the weakly associative lattices were introduced. In [39], an algebra with a system of identities was introduced, which we call a weakly idempotent lattice (see also [31, 62, 63]). The variety of weakly idempotent lattices is a nilpotent shift of the variety of lattices [39]. In paper [18], we studied weakly idempotent lattices with an additional interlaced operation. In this paper we give set-theoretical representations both for arbitrary weakly idempotent lattices and for interlaced weakly idempotent bilattices. In particular, we obtain a set-theoretical representation for interlaced bilattices, too. This problem was left open in the paper [26].
In Sect. 2, we give definitions of a weakly idempotent semilattice, a weakly idempotent lattice, a quasiordered set, an \(\mathrm{inf}\)-quasiordered set, a \(\mathrm{sup}\)-quasiordered set and an \(\mathrm{infsup}\)-quasiordered set. We establish a connection among these weakly idempotent structures and the corresponding quasiorders (Lemmas 2.6–2.9, Corollaries 2.15–2.16). In Sect. 3, we prove inequalities valid for weakly idempotent lattices. Further, we give definitions of a filter and ideal of a weakly idempotent lattice, then we characterize the filter and the ideal of a weakly idempotent lattice that are generated by a nonempty subset of the weakly idempotent lattice. On a subset of the set of all filters (ideals) of a weakly idempotent lattice, we define binary operations \(\cap ^{*}\) and \(\cup ^{*}\). In Sect. 4, we prove a set-theoretical representation theorem for arbitrary weakly idempotent lattices (Theorem 4.1). Then we define the prime filter and the prime ideal of a weakly idempotent lattice. We redefine the binary operations \(\cap ^{*}\) and \(\cup ^{*}\) on a subset of the set of all filters (ideals) of a weakly idempotent lattice by the new operations \(\cap ^{**}\) and \(\cup ^{**}\). As a corollary from Theorem 4.1 we get set-theoretical representations for distributive weakly idempotent lattices and for arbitrary lattices (Corollaries 4.6–4.7). In Sect. 5, we define a weakly idempotent bilattice, an interlaced weakly idempotent bilattice, a distributive weakly idempotent bilattice, a hyperidentity and superproduct, a filter and an ideal of the weakly idempotent bilattice. Then we prove certain inequalities valid on a weakly idempotent bilattice. Furthermore, we characterize the filter (ideal) of a weakly idempotent bilattice that is generated by a nonempty subset of the weakly idempotent bilattice (Lemmas 5.11–5.12). Also we define the binary operations \(\cap ^{*}\) and \(\cup ^{*}\) on a subset of the set of all filters (ideals) of a weakly idempotent bilattice. In Theorem 5.17 we give a set-theoretical representation for interlaced weakly idempotent bilattices. Then we define a prime filter and prime ideal of weakly idempotent bilattices, also we redefine the binary operations \(\cap ^{*}\) and \(\cup ^{*}\) on a subset of the set of all filters (ideals) of a weakly idempotent bilattice by the operations \(\cap ^{**}\) and \(\cup ^{**}\). Finally, we get as corollaries set-theoretical representations for distributive weakly idempotent bilattices, interlaced bilattices and distributive bilattices without bounds (Corollaries 5.20–5.22).
2 Preliminary results
Definition 2.1
An algebra \((L;\wedge )\) with one binary operation is called a weakly idempotent semilattice if it satisfies the following identities:
The operation is called a product. Adding the idempotence identity we obtain a semilattice. The element \(a\in L\) is called an idempotent of the weakly idempotent semilattice \((L;\wedge )\) if . The set of idempotent elements of each weakly idempotent semilattice forms a semilattice, i.e. the product of any two idempotent elements in the weakly idempotent semilattice is an idempotent element. Namely:
Definition 2.2
The relation is called a quasiorder if it is reflexive and transitive.
Example 2.3
The cover of a set L is a family \(P=\{X_{i}\}_{i\in I}\) of subsets of L such that . A relation Q, defined on the set of all covers of the set L:
is a quasiorder. It is not an order, because there exist such different covers \(P_{1}\) and \(P_{2}\) such that \(P_{1}QP_{2}\) and \(P_{2}QP_{1}\).
Example 2.4
The classical relation of divisibility on \(\mathbf {Z}\) is a quasiorder. So, the results of this paper are related to the number theory too.
Every quasiorder generates an order as follows. Let \(\theta \) be a quasiorder on the set \(L\ne \varnothing \); then is an equivalence. For any element \(x\in L\) let us denote by the class of the relation \(E_{\theta }\) which contains the element x. Let \(\leqslant _{\theta }\) be a relation induced on the set \(L/E_{\theta }\) from \(\theta \) in the following manner: for
Straightforward arguments show that this definition is correct and that it is an order.
The function \(K:L/E_{\theta }\rightarrow L \) is called a choice function if .
Definition 2.5
The pair \((L;\theta )\) is called an inf-quasiordered (sup-quasiordered) set if for any two classes of equivalences there exists (dually , i.e. if \((L/E_{\theta };\leqslant _{\theta })\) is a lower (upper) semilattice.
Lemma 2.6
Let \((L;\theta )\) be an inf-quasiordered set and let \(K:L/E_{\theta }\rightarrow L\) be an arbitrary choice function. If for every \(x,y\in L\), , then the algebra is a weakly idempotent semilattice, which we call a lower weakly idempotent semilattice.
Indeed, it is straightforward to check that satisfies identities (1)–(3).
Lemma 2.7
Let be a weakly idempotent semilattice. Then the relation is a quasiorder on the set L, the mapping \(K:L/E_{\theta }\rightarrow L\), is a choice function, and the pair \((L;\theta )\) is an inf-quasiordered set with and .
Proof
The first part is obvious. Let us show that . First note that and . Indeed, , then . Similarly for . Consider a lower bound for , then \(c\theta a\) and \(c\theta b\), thus yields and .\(\square \)
The following two lemmas are dual to Lemmas 2.6 and 2.7, respectively.
Lemma 2.8
Let \((L;\theta )\) be a sup-quasiordered set and let \(K:L/E_{\theta }\rightarrow L \) be an arbitrary choice function. If for every \(x,y\in L\), , then the algebra is a weakly idempotent semilattice, which we call an upper weakly idempotent semilattice.
Lemma 2.9
Let be a weakly idempotent semilattice. Then the relation is a quasiorder on the set L, the mapping \(K:L/E_{\theta }\rightarrow L\), is a choice function, and the pair \((L;\theta )\) is a sup-quasiordered set with and .
Definition 2.10
An algebra \((L;\wedge , \vee )\) with two binary operations is called a weakly idempotent lattice if the reducts \((L;\wedge )\) and \((L;\vee )\) are weakly idempotent semilattices and the following identities are valid:
The operation is called a sum.
Example 2.11
Let us consider the relation of divisibility on the set , which is a quasiorder on . The corresponding equivalence classes are the following sets . Define a choice function as . Then we have and . Thus, the algebra is a weakly idempotent lattice, which is not a lattice, since for negative x.
Example 2.12
If we define the choice function on as , then we have and . Hence, the algebra also is a weakly idempotent lattice.
The element \(a\in L\) is called an idempotent of the weakly idempotent lattice \((L;\wedge ,\vee )\) if and .
Remark 2.13
The product (sum) of any two elements of a weakly idempotent lattice \((L;\wedge ,\vee )\) is an idempotent element:
The other condition is proved similarly. So, the set of all idempotent elements of weakly idempotent lattice is a lattice.
Definition 2.14
A pair \((L;\theta )\) is called an infsup-quasiordered set if for any two classes of equivalences there exist both and , i.e. if \((L/E_{\theta };\leqslant _{\theta })\) is a lattice.
The following two corollaries immediately follow from Lemmas 2.6–2.9.
Corollary 2.15
Let \((L;\theta )\) be an infsup-quasiordered set and let \(K:L/E_{\theta } \rightarrow L\) be an arbitrary choice function. If for any \(x,y\in L\), , , then the algebra \((L;\wedge , \vee )\) is a weakly idempotent lattice.
Corollary 2.16
Let \((L; \wedge ,\vee )\) be a weakly idempotent lattice. Then the relation is a quasiorder on the set L, the mapping \(K:L/E_{\theta }\rightarrow L\), is a choice function, and the pair \((L;\theta )\) is an infsup-quasiordered set with , and
Definition 2.17
A weakly idempotent lattice \((L;\wedge ,\vee )\) is called bounded if the corresponding lattice \((L/E_{\theta };\leqslant _{\theta })\) is bounded.
3 Weakly idempotent lattices
Let \(L=(L;\wedge ,\vee )\) be a weakly idempotent lattice. By Corollary 2.16, each weakly idempotent lattice defines the quasiorder \(\theta \) (which is denoted by \(\leqslant \) in this section) defined by the following rule:
Remark 3.1
Note, that operations of weakly idempotent lattice preserve the corresponding quasiorder. Indeed, let \(a\leqslant b\) and \(c\leqslant d\), i.e. and , then , thus . In the same way we show that .
Lemma 3.2
Let \(L=(L; \wedge ,\vee )\) be a weakly idempotent lattice. Then .
Proof
Let \(a\leqslant b\leqslant a\), then, by (5), and , hence, . Conversely, let , then
thus, by (5), \(a\leqslant b\) and \(b\leqslant a\).\(\square \)
Lemma 3.3
Let \((L;\wedge ,\vee )\) be a weakly idempotent lattice. Then on L.
Proof
From identities (1)–(3) and Remark 2.13 we have
Hence, by (5), we obtain . The right-hand side of the inequality is proved in a similar way.\(\square \)
We say that a nonempty subset A of a weakly idempotent lattice \((L;\wedge ,\vee )\) is a weakly idempotent sublattice if it is closed under weakly idempotent lattice operations, i.e. if
Definition 3.4
A weakly idempotent sublattice F of a weakly idempotent lattice \(L=(L;\wedge ,\vee )\) is called a filter of L if \(x\in F\), \(y\in L\) implies .
A filter is called proper if it is different from L. The set of all filters of the weakly idempotent lattice L is denoted by F(L).
Definition 3.5
A weakly idempotent sublattice I of a weakly idempotent lattice \(L=(L;\wedge ,\vee )\) is called an ideal of L if \( x\in I\), \(y\in L\) implies .
An ideal is called proper if it is different from L. The set of all ideals of the weakly idempotent lattice L is denoted by I(L).
Lemma 3.6
Let \(L=(L;\wedge ,\vee )\) be a weakly idempotent lattice. The following statements are equivalent for L:
-
(a)
F is a filter of L.
-
(b)
If \(x,y\in F\), then ; and if \(x\in F\), \(y\in L,x\leqslant y\), then .
Proof
(a) \(\Rightarrow \) (b) Let F be a filter on L, then, for any \(x,y\in F\), (by (6)) and for any \(x\in F\), \(y\in L\), . Assume that \(x\leqslant y\) (i.e. ), then .
(b) \(\Rightarrow \) (a) For \(x\in F\), \(y\in L\), using Lemma 3.3, we get , since . From Remark 2.13, we obtain that . Thus, for each \(x\in F\), \(y\in L\).\(\square \)
Lemma 3.7
Let \(L=(L;\wedge ,\vee )\) be a weakly idempotent lattice. The following statements are equivalent for L:
-
(a)
I is an ideal of L.
-
(b)
If \(x,y\in I\), then ; and if \(x\in F\), \(y\in L,x\leqslant y\), then .
Lemma 3.8
Let \(L=(L;\wedge ,\vee )\) be a weakly idempotent lattice and \(X\subseteq L\). Then
is the smallest filter that contains X.
Proof
Let us show that is a filter. Take . If , then there exist such that and . By Remark 3.1 and (4), we get that . Hence, .
The cases , \(y\in X\); , \(x\in X\); and \(x,y\in X\) are proved similarly. Thus, for each we obtain that . Similarly, we prove the second condition of Lemma 3.6; hence, is a filter.
Suppose is a filter of the weakly idempotent lattice L, which contains X. Let , then there exist \(x_{1},\ldots ,x_{n}\in X\) such that . Since F is a filter which contains X, we obtain that and . By (4), we have , and \(x\in F\). Hence, and is the smallest filter that contains X.\(\square \)
Lemma 3.9
Let \(L=(L;\wedge ,\vee )\) be a weakly idempotent lattice and \(X\subseteq L\). Then
is the smallest ideal that contains X.
Corollary 3.10
Let \(L=(L;\wedge ,\vee )\) be a weakly idempotent lattice and \(a\in L\). Then
is the smallest filter that contains a.
Indeed, take in Lemma 3.8.
Corollary 3.11
Let \(L=(L;\wedge ,\vee )\) be a weakly idempotent lattice and \(a\in L\). Then
is the smallest ideal that contains a.
Indeed, take in Lemma 3.9.
Lemma 3.12
Let \(L=(L;\wedge ,\vee )\) be a weakly idempotent lattice. Then the following assertions are valid on L:
Proof
Let us show that . Suppose . Then if , from Lemma 3.3 and (4) we obtain that . Hence, . If \(a\leqslant y=K([y])\), then, by Lemma 3.3, we obtain that , i.e. . The cases and \(b\leqslant y=K([y])\) are considered similarly. Thus, .\(\square \)
For each \(a\in L\), let \(f(a)=\{ F\in F(L):a\in F\}\) and \(i(a)=\{ I\in I(L):a\in I\}\). Define on the sets \(f(L)=\{f(a):a\in L\}\) and the operations \(\cap ^{*}\) and \(\cup ^{*}\) by the following rules:
Lemma 3.13
Let \((L;\wedge ,\vee )\) be a weakly idempotent lattice. Then:
Proof
Let us prove the first equality. Suppose then . If then , and hence \(c\in F\) or . Thus, since F is a filter, we obtain that . Hence, and, by Lemma 3.12, we have . Thus, there exist and such that \(X\cup Y\subseteq F\), i.e. .
Conversely, if , then there exist and such that \(X\cup Y\subseteq F\) hence and . Then ; hence, since F is a filter, we get . Thus, .
The rest of identities are proved similarly.\(\square \)
4 A set-theoretical representation for arbitrary weakly idempotent lattices
From Lemma 3.13 it immediately follows that the algebras \(f(L)=(f(L);\cap ^{*},\cup ^{*})\) and \(i(L)=(i(L);\cup ^{*},\cap ^{*})\) are weakly idempotent lattices.
Theorem 4.1
Every weakly idempotent lattice \(L=(L;\wedge ,\vee )\) is isomorphic to the weakly idempotent lattice \(f(L)=(f(L);\cap ^{*},\cup ^{*})\), i.e. \(L\cong f(L)\).
Proof
The mapping \(\varphi :L\rightarrow (f(L);\cap ^{*},\cup ^{*})\) which is defined by the following rule:
is an isomorphism. Indeed:
Injectivity. Suppose \(\varphi (a)=\varphi (b)\), i.e. \(f(a)=f(b)\). Then, since and , we obtain that and . By Corollary 3.10, we have two cases: \(b=a\) or and . In the second case, by Lemma 3.2, we have ; and by (4), we obtain that and . Hence \(a=b\).
Surjectivity of \(\varphi \) is obvious.
The fact that \(\varphi \) is a homomorphism follows directly from identities (7) and (8): ; .\(\square \)
Corollary 4.2
For every weakly idempotent lattice \(L=(L;\wedge ,\vee )\), \(L\cong i(L)\).
Proof
The mapping \(\varphi _{1}:L\rightarrow (i(L);\cup ^{*},\cap ^{*})\) which is defined by the rule \(\varphi _{1}:x\mapsto i(x)\) is an isomorphism. The proof of injectivity of \(\varphi _{1}\) is similar to Theorem 4.1 and the fact that \(\varphi _{1}\) is a homomorphism follows immediately from (9) and (10).\(\square \)
Note that the operation \(\cup ^{*}\), defined on f(L), coincides with the operation \(\cup ^{**}\), defined in the following way:
Indeed, let , then or . Hence . From Lemma 3.12 we have . Hence, there exist and such that \(X\cap Y\subseteq F'\), yield and thus . So, on f(L).
Also note that the operation \(\cap ^{*}\), defined on f(L), can be replaced with the operation \(\cap ^{**}\), defined in the following way:
Indeed, let , then there exist filters X and Y of L such that , and \(X\cup Y\subseteq F\). So , , hence . Hence . Moreover, .
In the same way, we can show that the operations \(\cap ^{*}\) and \(\cup ^{*}\) on the set i(L) coincide with the operations \(\cap ^{**}\) and \(\cup ^{**}\) defined as follows:
Moreover, .
Definition 4.3
A filter F of a weakly idempotent lattice \((L;\wedge ,\vee )\) is called prime if F is a proper filter and implies \(x\in F\) or \(y\in F\) for \(x,y\in L\).
Definition 4.4
An ideal I of a weakly idempotent lattice \((L;\wedge ,\vee )\) is called prime if I is a proper ideal and implies \(x\in I\) or \(y\in I\) for \(x,y\in L\).
Definition 4.5
The weakly idempotent lattice \((L;\wedge ,\vee )\) is called distributive if it satisfies the following identities of distributivity:
Denote the set of all prime filters of a weakly idempotent lattice L by pF(L), and the set of all prime ideals of a weakly idempotent lattice L by pI(L). Let us make the following designations: and , \(pf (L)= \{pf(a):a\in L\}\) and \(pi(L) = \{pi(a):a\in L\}\). The operations \(\cap ^{**}\) and \(\cup ^{**}\) can be defined on pf(L) and pi(L) and then identities similar to those in Lemma 3.13 can be proven for prime filters and prime ideals too. Thus, the sets pF(L) and pI(L) are closed under the operations \(\cap ^{**}\) and \(\cup ^{**}\).
Corollary 4.6
Each distributive weakly idempotent lattice \(L=(L;\wedge ,\vee )\) is isomorphic to the distributive weakly idempotent lattice \(pf(L)=(pf(L);\cap ^{**},\cup )\), i.e. \(L\cong pf(L)\).
Proof
Let us show that on the set pf(L) the operation \(\cup ^{**}\) converts to the set-theoretical union. Namely, let us consider . By the corresponding result for (8) from Lemma 3.13, we have . Since Z is a prime filter, then \(x\in Z\) or \(y\in Z\), hence . Thus, .
The converse, namely, is trivial. Using the identities of Lemma 3.13 for the case of pf(L), we immediately get that pf(L) is a weakly idempotent lattice. On the set pf(L), we redefine the operation \(\cap ^{**}\) as . Hence, the weakly idempotent lattice pf(L) is distributive.\(\square \)
Let us make some designations: the set of all prime filters of the lattice L is denoted by \(\widetilde{F}(L)\), , \(\widetilde{f}(L)= \{\widetilde{f}(a):a\in L\}\).
Corollary 4.7
([9]) Every lattice \(L=(L;\wedge ,\vee )\) is isomorphic to the lattice \(\widetilde{f}(L)=(\widetilde{f}(L);\cap ,\cup ^{*})\), i.e. \(L\cong \widetilde{f}(L)\).
Proof
Since L is a lattice, the operation \(\cap ^{*}\) is converted into the set-theoretical intersection and the operation \(\cup ^{*}\) is defined as follows:
It is obvious that \((\widetilde{f}(L);\cap ,\cup ^{*})\) is a lattice. Indeed, , .
5 A set-theoretical representation for interlaced weakly idempotent bilattices
Bilattices are algebras with two separate lattice structures and weakly idempotent bilattices are algebras with two separate weakly idempotent lattice structures. Bilattices have been used as a basis for a denotational semantics for systems of inference that arise in artificial intelligence and knowledge-based logic programming [22, 30]. In particular, they have been used to provide a general framework for an efficient procedural semantics of logic programming languages that can deal with incomplete as well as contradictory information.
Originally, Ginsberg [30] suggested to use bilattices as an underlying framework for various AI inference systems including those based on default logics, truth maintenance systems, probabilistic logics and others. These ideas were later pursued in [22, 23, 40], in the context of logic programming semantics. Studies of the algebraic properties of bilattices have provided insight into their internal structures, and have led to practical results, especially in reducing the computational complexity of bilattice-based multi-valued logic programs.
Ginsberg’s original definition of bilattice postulated a connection of two lattice structures through a negation operation. However the terminology for bilattices is not uniform. For this reason, we often speak of a bilattice and weakly idempotent bilattice without negation for emphasis.
Definition 5.1
The algebra \(L=(L;\wedge ,\vee ,*,\triangle )\) with four binary operations is called a weakly idempotent bilattice if the reducts \(L_{1}=(L;\wedge ,\vee )\) and \(L_{2}=(L;*,\triangle )\) are weakly idempotent lattices and it also satisfies the following identity:
If \(L_{1}=(L;\wedge ,\vee )\) and \(L_{2}=(L;*, \triangle )\) are lattices, then the algebra \(L=(L;\wedge ,\vee ,*,\) \(\triangle )\) is called a bilattice.
Every bilattice is a weakly idempotent bilattice. A bilattice L is called bounded if the reducts \(L_{1}\) and \(L_{2}\) are bounded lattices. A weakly idempotent bilattice L is called bounded if the reducts \(L_{1}\) and \(L_{2}\) are bounded weakly idempotent lattices.
Definition 5.2
A (weakly idempotent) bilattice \((L;\wedge ,\vee ,*,\triangle )\) is called distributive if each pair of the operations from the set satisfies the identities of distributivity.
Let us denote the quasiorder of the first reduct \(L_{1}=(L;\wedge ,\vee )\) by \(\leqslant _{\wedge }\) and that of the second reduct \(L_{2}=(L;*,\triangle )\) by \(\leqslant _{*}\) (see Corollary 2.16), i.e.
Definition 5.3
The weakly idempotent bilattice \((L;\wedge ,\vee ,*,\triangle )\) is called interlaced if all basic weakly idempotent bilattice operations are quasiorder-preserving with respect to the both quasiorders, i.e.
Example 5.4
Every distributive weakly idempotent bilattice \((L;\wedge ,\vee ,*,\triangle )\) is interlaced. Namely, if , then and . So, and for any \(z\in L\). If , then , hence and . Thus, and for any \(z\in L\).
Example 5.5
If \((L;\wedge ,\vee )\) is a weakly idempotent lattice, then \((L;\wedge ,\vee ,\wedge ,\vee )\) is an interlaced weakly idempotent bilattice. If \((L;\wedge ,\vee )\) is a distributive weakly idempotent lattice, then \((L;\wedge ,\vee ,\wedge ,\vee )\) is a distributive weakly idempotent bilattice. If \((L;\wedge ,\vee )\) is a lattice, then \((L;\wedge ,\vee ,\wedge ,\vee )\) is an interlaced bilattice. If \((L;\wedge ,\vee )\) is a distributive lattice, then \((L;\wedge ,\vee ,\wedge ,\vee )\) is a distributive bilattice.
For the applications and characterizations of bilattices in various varieties see [3, 11, 14, 15, 17, 21–23, 27–30, 33, 40, 41, 51, 53, 59, 65–67].
Open Problem
Characterize finitely generated free algebras of these varieties.
For importance of this problem for pure and applied algebra see [69].
Note that until 2000 bilattices with bounds were investigated, but since 2006 bilattices and weakly idempotent bilattices without bounds have gained interest (see [59]). In the current paper we also consider bilattices and weakly idempotent bilattices without bounds (i.e, in the general case).
For more detail about the second-order formulae and second-order languages see [16, 36, 37]. According to [43, 44, 49, 50] a hyperidentity is a universal second-order formula of the following type:
where \(X_{1},\ldots ,X_{m}\) are functional variables and \(x_{1},\ldots ,x_{n}\) are object variables in the words (terms) of \(w_{1}, w_{2}\). Hyperidentities are usually written without quantifiers: \(w_{1}=w_{2}\). We say that the hyperidentity \(w_{1}=w_{2}\) is satisfied in the algebra (Q; F) if this equality is valid when every object variable and every functional variable in it is replaced by any element from Q and by any operation of the corresponding arity from F (supposing the possibility of such replacement) (see also [2, 4, 5, 7, 35, 42, 46, 68, 70, 72–74]).
On the characterization of hyperidentities of varieties of lattices, modular lattices, distributive lattices, Boolean and De Morgan algebras, see [45, 47–50, 54–56]. For more about hyperidentities in term (polynomial) algebras, see [6, 19, 32, 34, 45, 48, 60, 61, 64, 71, 76]. For application of hyperidentities in discrete mathematics see [38, 57, 58].
For example, a weakly idempotent bilattice \(L=(L;\wedge ,\vee ,*,\triangle )\) is distributive iff it satisfies the following hyperidentity:
One can prove that a weakly idempotent bilattice \(L=(L;\wedge ,\vee ,*,\triangle )\) is interlaced iff it satisfies the following hyperidentity:
For the categorical definition of the hyperidentity, in [43] the (bi)homomorphisms between two algebras (Q; F) and \((Q';F')\) are defined as the pairs \((\varphi ; \widetilde{\psi })\) of mappings:
with the following condition:
for any \(A\in F\), \(a_{1},\ldots ,a_{n}\in Q\), \(|A|=n\). (More about application of such morphisms in the cryptography can be found in [1].)
Algebras with their (bi)homomorphisms \((\varphi ; \widetilde{\psi })\) (as morphisms) form a category. The product in this category is called a superproduct of algebras and is denoted by for the two algebras Q and \(Q'\). For example, the superproduct of the two weakly idempotent lattices and is a binary algebra with four binary operations, where the pairs of the operations operate component-wise, i.e.
Example 5.6
The superproduct is an interlaced weakly idempotent bilattice for every two weakly idempotent lattices and . Indeed, denote the quasiorders of Q and \(Q'\) by \(\leqslant _{1}\) and \(\leqslant _{2}\), correspondingly, the quasiorders of — by \(\leqslant _\mathrm{I}\) and \(\leqslant _\mathrm{II}\), which are defined in the following way: , and , . Take \((a,b)\leqslant _\mathrm{I} (c,d)\) and \((e,f)\in Q\times Q'\). Show that . From we have , , hence for \(e\in Q\) and \(f\in Q'\) we get: and , thus and . The rest of the conditions are proved similarly.
Example 5.7
The superproduct is a distributive weakly idempotent bilattice for every two weakly idempotent distributive lattices and . The superproduct is a distributive bilattice for every two distributive lattices and . The superproduct is an interlaced bilattice for every two lattices and .
Lemma 5.8
Let \(L=(L;\wedge ,\vee ,*,\triangle )\) be an interlaced weakly idempotent bilattice. Then for any \(x,y\in L\),
Proof
From Lemma 3.3, we have and ; then, since L is an interlaced weakly idempotent bilattice, we have . From the identity of a weakly idempotent bilattice we obtain , i.e. . Similarly, from Lemma 3.3, we have and , then, since L is an interlaced weakly idempotent bilattice, we obtain . Thus, .\(\square \)
Definition 5.9
The nonempty subset \(F\subseteq L\) is called a filter of a weakly idempotent bilattice \(L=(L; \wedge ,\vee ,*,\triangle )\) if F is a filter for both reducts: \(L_{1}=(L;\wedge ,\vee )\) and , i.e. if it satisfies the following conditions:
-
(ff1)
if \(x,y\in F\) then ;
-
(ff2)
if \(x,y\in F\) then ;
-
(ff3)
if \(x\in F,y\in L\) and then ;
-
(ff4)
if \(x\in F,y\in L\) and then .
Denote the set of all filters of a weakly idempotent bilattice L by .
Definition 5.10
The nonempty subset \(I\subseteq L\) is called an ideal of a weakly idempotent bilattice \(L=(L;\wedge ,\vee ,*,\triangle )\) if I is a filter for the reduct \(L_{1}=(L;\wedge ,\vee )\) and the ideal for the reduct , i.e. if it satisfies the following conditions:
-
(ff1)
if \(x,y\in I\) then ;
-
(ff2)
if \(x,y\in I\) then ;
-
(ff3)
if \(x\in I,y\in L\) and then ;
-
(ff4)
if \(y\in I,x\in L\) and then .
Denote the set of all the ideals of a weakly idempotent bilattice L by .
Lemma 5.11
Let X be a nonempty subset of the interlaced weakly idempotent bilattice \(L=(L;\wedge ,\vee ,*,\triangle )\). Then
is the smallest filter of the interlaced weakly idempotent bilattice L that contains X.
Proof
First of all it is straightforward to prove that
Then, similar to Lemma 3.8, we show that is a filter; moreover, it is the smallest filter that contains X.\(\square \)
Lemma 5.12
Let X be a nonempty subset of the interlaced weakly idempotent bilattice \(L=(L;\wedge ,\vee ,*,\triangle )\). Then
is the smallest ideal of the interlaced weakly idempotent bilattice L that contains X.
Corollary 5.13
Let \(L=(L;\wedge ,\vee ,*,\triangle )\) be an interlaced weakly idempotent bilattice. Then
is the smallest filter of the interlaced weakly idempotent bilattice L that contains \(a\in L\).
Indeed, take in Lemma 5.11.
Corollary 5.14
Let \(L=(L;\wedge ,\vee ,*,\triangle )\) be an interlaced weakly idempotent bilattice. Then
is the smallest ideal of the interlaced weakly idempotent bilattice L that contains \(a\in L\).
Indeed, take \(X=\{a\}\) in Lemma 5.12.
Lemma 5.15
Let \(L=(L;\wedge ,\vee ,*,\triangle )\) be an interlaced weakly idempotent bilattice. The following assertions are valid on L:
Proof
Let us prove the equality . If , then, by Corollary 5.13, we have , then and ; thus, and . Thus, and , i.e. .
Conversely, let , then and . From , by Corollary 5.13, it follows that there exists \(c\in L\) such that and from Lemma 3.3 we have and it follows that , i.e. . If , then we similarly obtain that . Thus, . The rest of assertions are proved similarly.\(\square \)
For every \(a\in L\), we denote and . Let us define on the sets and , the binary operations \(\cup ^{*}\) and \(\cap ^{*}\) in the following manner:
Lemma 5.16
Let \(L=(L;\wedge ,\vee ,*,\triangle )\) be an interlaced weakly idempotent bilattice. Then the following equalities are valid on \((Bf(L);\cap ^{*},\cup ^{*})\) and \((Bi(L);\cap ^{*},\cup ^{*})\):
Proof
Let us show the first equality. Suppose that , then . Let , then by Corollary 5.13, there exists \(c\in L\) such that , so . By Lemma 5.15, we have . Thus, there exist and such that \(X\cap Y\in F\), i.e. . Conversely, let , then there exist and such that \(X\cup Y\in F\); hence, and . Then we see that and . Thus, and . The rest of equalities are proved similarly.\(\square \)
From Lemma 5.16, it immediately follows that \(Bf(L)=(Bf(L);\cap ^{*},\cup ^{*})\) and \(Bi(L)=(Bi(L);\cap ^{*},\cup ^{*})\) satisfy identities of a weakly idempotent lattice. Hence, Bf(L) and Bi(L) are weakly idempotent lattices.
Theorem 5.17
Every interlaced weakly idempotent bilattice \(L=(L;\wedge ,\vee ,*,\triangle )\) is isomorphic to the superproduct of the two weakly idempotent lattices \(Bf(L)=(Bf(L);\cap ^{*},\cup ^{*})\) and \(Bi(L)=(Bi(L);\cap ^{*},\cup ^{*})\), i.e. .
Proof
Let us show that the mapping
which is defined by
is an isomorphism. The proof of the injectivity of \(\varphi \) is similar to the proof of Theorem 4.1, while the surjectivity is obvious.
The fact that \(\varphi \) is a homomorphism follows from Lemma 5.16:
\(\square \)
Note that the operations \(\cup ^{*}\) and \(\cap ^{*}\) on the sets Bf(L) and Bi(L) coincide with the operations \(\cup ^{**}\) and \(\cap ^{**}\) respectively, which are defined in the following way:
Moreover, and .
Now, let us introduce the concepts of prime filters and prime ideals for a weakly idempotent bilattice.
Definition 5.18
The filter F of a weakly idempotent bilattice \(L=(L;\wedge ,\vee ,*,\triangle )\) is called prime if it is a prime filter for both reducts \(L_{1}=(L;\wedge ,\vee )\) and \(L_{2}=(L;*,\triangle )\).
Definition 5.19
The ideal I of a weakly idempotent bilattice \(L=(L;\wedge ,\vee ,*,\triangle )\) is called prime if it is a prime filter for the reduct \(L_{1}=(L;\wedge ,\vee )\) and prime ideal for the reduct .
Denote the set of all prime filters of a weakly idempotent bilattice L by pBF(L), and the set of all prime ideals of a weakly idempotent bilattice L by pBI(L). Let and , \(pBf (L)= \{pBf(a):a\in L\}\) and \(pBi(L) =\{pBi(a):a\in L\}\). The operations \(\cap ^{**}\) and \(\cup ^{**}\) can be defined on pBf(L) and pBi(L) and an analogue of Lemma 5.16 can be proven. So, the sets pBF(L) and pBI(L) are closed under the operations \(\cap ^{**}\) and \(\cup ^{**}\).
Corollary 5.20
Every distributive weakly idempotent bilattice \(L=(L;\wedge ,\vee ,*,\triangle )\) is isomorphic to the superproduct of the two distributive weakly idempotent lattices \(pBf(L)=(pBf(L);\cap ^{**}, \cup )\) and \(pBi(L)=(pBi(L);\cap ^{**}\!, \cup )\), i.e. .
Proof
Similarly to the proof of Corollary 4.6, we show that on the sets pBf(L) and pBi(L) the operations \(\cup ^{**}\) and \(\cup ^{**}\) convert to the set-theoretical union. Using the identities of Lemma 5.16 for prime filters and prime ideals, we get that pBf(L) and pBi(L) are weakly idempotent lattices. On the set pBf(L) we redefine the operation \(\cap ^{**}\) as and . Hence, the weakly idempotent lattices pBf(L) and pBi(L) are distributive.\(\square \)
Denote the set of all filters of the bilattice L by \(\widetilde{BF}(L)\) and the set of all ideals by \(\widetilde{BI}(L)\). Let , , \(\widetilde{Bf}(L)= \{\widetilde{Bf}(a):a\in L\}\), \(\widetilde{Bi}(L)= \{\widetilde{Bi}(a):a\in L\}\).
Corollary 5.21
Every interlaced bilattice \(L=(L;\wedge ,\vee ,*,\triangle )\) is isomorphic to the superproduct of the two lattices \(\widetilde{Bf}(L)=(\widetilde{Bf}(L);\cap , \cup ^{**})\) and \(\widetilde{Bi}(L)=(\widetilde{Bi}(L);\cap ,\) \( \cup ^{**})\), i.e. .
Proof
Since L is a bilattice, the operation \(\cap ^{**}\) is converted into the set-theoretical intersection, and the operation \(\cup ^{**}\) is defined as follows:
It is obvious that \(\widetilde{Bf}(L)\) and \(\widetilde{Bi}(L)\) are lattices. Indeed, , . \(\square \)
Denote the set of all prime filters of a bilattice L by \(\widetilde{pBF}(L)\) and the set of all prime ideals of L by \(\widetilde{pBI}(L)\). Let , , \(\widetilde{pBf}(L)= \{\widetilde{pBf}(a):a\in L\}\), \(\widetilde{pBi}(L)= \{\widetilde{pBi}(a):a\in L\}\)
Corollary 5.22
Every distributive bilattice \(L=(L;\wedge ,\vee ,*,\triangle )\) is isomorphic to the superproduct of the two distributive lattices \(\widetilde{pBf}(L)=(\widetilde{pBf}(L);\cap , \cup )\) and \(\widetilde{pBi}(L)\) \(=(\widetilde{pBi}(L);\cap , \cup )\), i.e. .
Proof
Similarly to the proof of Corollary 4.6, we get that the operations \(\cup ^{**}\) and \(\cup ^{**}\) convert into the set-theoretical union on sets \(\widetilde{pBf}(L)\) and \(\widetilde{pBi}(L)\), respectively.\(\square \)
For the bounded case the last result was proved by Gargov [26].
References
Anosov, A.D.: On homomorphisms of many-sorted algebraic systems in connection with cryptographic applications. Discrete Math. Appl. 17(4), 331–347 (2007)
Artamonov, V.A., Saliy, V.N., Skornyakov, L.A., Shevrin, L.N., Shul’geyfer, E.G.: General Algebra, vol. II. Mathematical Reference Library, Moscow, Nauka (1991). (in Russian)
Avron, A.: The structure of interlaced bilattices. Math. Structures Comput. Sci. 6(3), 287–299 (1996)
Belousov, V.D.: Systems of quasigroups with generalized identities. Russian Math. Surveys 20(1), 75–143 (1965)
Belousov, V.D., Movsisyan, YuM: On the range of generalized identities. Izv. Nats. Akad. Nauk Armenii Mat. 9(2), 135–142 (1974). (in Russian)
Bergman, G.M.: Hyperidentities of groups and semigroups. Aequationes Math. 23(1), 50–65 (1981)
Bergman, G.M.: An Invitation to General Algebra and Universal Constructions. Universitext. 2nd edn. Springer, Cham (2015)
Birkhoff, G.: Rings of sets. Duke Math. J. 3(3), 443–454 (1937)
Birkhoff, G., Frink Jr., O.: Representations of lattices by sets. Trans. Amer. Math. Soc. 64(2), 299–316 (1948)
Bloom, S.L., Ésik, Z., Manes, E.G.: A Cayley theorem for Boolean algebras. Amer. Math. Monthly 97(6), 831–833 (1990)
Bou, F., Jansana, R., Rivieccio, U.: Varieties of interlaced bilattices. Algebra Universalis 66(1–2), 115–141 (2011)
Brzozowski, J.A.: A characterization of de Morgan algebras. Internat. J. Algebra Comput. 11(5), 525–527 (2001)
Brzozowski, J.A.: De Morgan bisemilattices. In: 30th IEEE International Symposium on Multiple-Valued Logic, pp. 173–178. IEEE Computer Society, Los Alamitos (2000)
Cabrer, L.M., Craig, A.P.K., Priestley, H.A.: Product representation for default bilattices: An application of natural duality theory. J. Pure Appl. Algebra 219(7), 2962–2988 (2015)
Cabrer, L.M., Priestley, H.A.: Distributive bilattices from the perspective of natural duality theory. Algebra Universalis 73(2), 103–141 (2015)
Church, A.: Introduction to Mathematical Logic, vol. I. Princeton University, Princeton (1956)
Davey, B.A.: The product representation theorem for interlaced pre-bilattices: some historical remarks. Algebra Universalis 70(4), 403–409 (2013)
Davidova, D.S., Movsisyan, YuM: Weakly idempotent lattices and bilattices, non-idempotent Plonka functions. Demonstratio Math. 48(4), 509–535 (2015)
Denecke, K., Wismath, S.L.,: Hyperidentities and Clones. Algebra, Logic and Applications, vol. 14. Gordon and Breach Science, Amsterdam (2000)
Ésik, Z.: A Cayley theorem for ternary algebras. Internat. J. Algebra Comput. 8(3), 311–316 (1998)
Fitting, M.: Bilattices and the theory of truth. J. Philos. Logic 18(3), 225–256 (1989)
Fitting, M.: Bilattices in logic programming. In.: Proceedings of the 20th International Symposium on Multiple-Valued Logic, pp. 238–246. IEEE Computer Society, Los Alamitos (1990)
Fitting, M.: Bilattices and the semantics of logic programming. J. Logic Programming 11(2), 91–116 (1991)
Freid, E.: Weakly associative lattices with congruence extension property. Algebra Universalis 4, 151–162 (1974)
Fried, E., Grätzer, G.: A nonassociative extension of the class of distributive lattices. Pacific J. Math. 49(1), 59–78 (1973)
Gargov, G.: Knowledge, uncertainty and ignorance in logic: bilattices and beyond. J. Appl. Non-Classical Logics 9(2–3), 195–283 (1999)
Ginsberg, M.L.: Bilattices, preprint (1986)
Ginsberg, M.L.: Multi-valued logics. In: Proceedings of the Fifth National Conference on Artificial Intelligence (AAAI-86), pp. 243–247. Morgan Kaufmann, Los Altos (1986)
Ginsberg, M.L.: Multi-valued inference, preprint (1986)
Ginsberg, M.L.: Multi-valued logics: a uniform approach to reasoning in artificial intelligence. Comput. Intell. 4, 265–316 (1988)
Graczyńska, E.: On normal and regular identities. Algebra Universalis 27(3), 387–397 (1990)
Graczyńska, E.: Algebra of M-solid Quasivarieties. Siatras International Bookshop, Athens (2014)
Jung, A., Rivieccio, U.: Priestley duality for bilattices. Studia Logica 100(1–2), 223–252 (2012)
Koppitz, J., Denecke, K.: M-solid Varieties of Algebras. Advances in Mathematics, vol. 10. Springer, New York (2006)
Krapež, A.: Generalized associativity on groupoids. Publ. Inst. Math. (Beograd) 28(42), 105–112 (1980)
Mal’cev, A.I.: Algebraic Systems. Die Grundlehren der Mathematischen Wissenschaften, vol. 192. Springer, New York (1973)
Mal’tsev, A.I.: Some questions of the theory of classes of models. In: Proceedings of the Fourth All-Union Mathematics Congress, vol. 1, pp. 169–190. Moscow (1963) (in Russian)
Melkonian, V.: Circuit integration through lattice hyperterms. Discrete Math. Algorithms Appl. 3(1), 101–119 (2011)
Mel’nik, I.I.: Nilpotent shift on manifolds. Math. Notes 14(5), 962–966 (1973)
Mobasher, B., Pigozzi, D., Slutzki, G.: Multi-valued logic programming semantics: an algebraic approach. Theoret. Comput. Sci. 171(1–2), 77–109 (1997)
Mobasher, B., Pigozzi, D., Slutzki, G., Voudsadakis, G.: A duality theory for bilattices. Algebra Universalis 43(2–3), 109–125 (2000)
Movsisyan, YuM: Introduction to the Theory of Algebras with Hyperidentities. Yerevan State University, Yerevan (1986). (in Russian)
Movsisyan, YuM: Hyperidentities and Hypervarieties in Algebras. Yerevan State University, Yerevan (1990). (in Russian)
Movsisyan, YuM: Hyperidentities of Boolean algebras. Russian Acad. Sci. Izv. Math. 40(3), 607–622 (1993)
Movsisyan, Yu.M.: On a theorem of Schauffler. Math. Notes 2(53)(1-2), 172–179 (1993)
Movsisyan, YuM: Algebras with hyperidentities of the variety of Boolean algebras. Russ. Acad. Sci. Izv. Math. 60(6), 1219–1260 (1996)
Movsisyan, YuM: Superidentities in the variety of lattices. Math. Notes 59(6), 686–688 (1996)
Movsisyan, YuM: Hyperidentities in algebras and varieties. Russian Math. Surveys 53(1), 57–108 (1998)
Movsisyan, Yu.: Hyperidentities and hypervarieties. Sci. Math. Jpn. 54(3), 595–640 (2001)
Movsisyan, YuM: Interlaced, modular, distributive and Boolean bilattices. Armen. J. Math. 1(3), 7–13 (2008)
Movsisyan, YuM: Binary representation of algebras with at most two binary operations. A Cayley theorem for distributive lattices. Internat. J. Algebra Comput. 19(1), 97–106 (2009)
Movsisyan, YuM: Bilattices and hyperidentities. Proc. Steklov Inst. Math. 274(1), 174–192 (2011)
Movsisyan, YuM, Aslanyan, V.A.: Hyperidentities of De Morgan algebras. Log. J. IGPL 20(6), 1153–1174 (2012)
Movsisyan, YuM: Biprimitive classes of second order algebras. Matematicheskie Issledovania 9(1), 70–82 (1974). (in Russian)
Movsisyan, YuM, Aslanyan, V.A.: Algebras with hyperidentities of the variety of De Morgan algebras. J. Contemp. Math. Anal. 48(5), 233–240 (2013)
Movsisyan, YuM, Aslanyan, V.A.: Subdirectly irreducible algebras with hyperidentities of the variety of De Morgan algebras. J. Contemp. Math. Anal. 48(6), 241–246 (2013)
Movsisyan, YuM, Aslanyan, V.A.: Super-Boolean functions and free Boolean quasilattices. Discrete Math. Algorithms Appl. 6(2), 1450024 (2014)
Movsisyan, YuM, Aslanyan, V.A.: Super-De Morgan functions and free De Morgan quasilattices. Cent. Eur. J. Math. 12(12), 1749–1761 (2014)
Movsisyan, YuM, Romanowska, A.B., Smith, J.D.H.: Superproducts, hyperidentities, and algebraic structures of logic programming. J. Combin. Math. Combin. Comput. 58, 101–111 (2006)
Padmanabhan, R., Penner, P.: A hyperbase for binary lattice hyperidentities. J. Automat. Reason. 24(3), 365–370 (2000)
Paseman, G.R.: On two problems from “Hyperidentities and Clones” (2014). arXiv:1408.2784
Pinus, A.G.: Lattices of quasiorders on universal algebras. Algebra and Logic 34(3), 180–181 (1995)
Płonka, J.: On varieties of algebras defined by identities of some special forms. Houston J. Math. 14(2), 253–263 (1988)
Plotkin, B.: Universal Algebra, Algebraic logic, and Databases. Mathematics and Its Applications, vol. 272. Kluwer, Dordrecht (1994)
Pynko, A.P.: Regular bilattices. J. Appl. Non-Classical Logics 10(1), 93–111 (2000)
Rivieccio, U.: An Algebraic Study of Bilattice-Based Logics. PhD thesis, University of Barcelona (2010)
Romanowska, A., Trakul, A.: On the structure of some bilattices. In: Hałkowska, K., Stawski, B. (eds.) Universal and Applied Algebra, pp. 235–253. World Scientific, Teaneck (1989)
Sade, A.: Théorie des systèmes demosiens de groupoïdes. Pacific J. Math. 10(2), 625–660 (1960)
Sapir, M.V.: Combinatorial Algebra: Syntax and Semantics. Springer Monographs in Mathematics. Springer, Cham (2014)
Schauffler, R.: Die Assoziativität im Ganzen, besonders bei Quasigruppen. Math. Z. 67, 428–435 (1957)
Schweigert, D.: Hyperidentities. In: Rosenberg, I.G., Sabidussi, G. (eds.) Algebras and Orders, pp. 405–506. NATO ASI Series C Mathematical and Physical Sciences, vol. 389. Kluwer, Dordrecht (1993)
Słomiński, J.: On the satisfiabilities and varieties for abstract algebras induced by the cones and functor dynamics. Demonstratio Math. 26(1), 11–22 (1993)
Smith, J.D.H.: On groups of hypersubstitutions. Algebra Universalis 64(1–2), 39–48 (2010)
Stein, S.K.: On the foundation of quasigroups. Trans. Amer. Math. Soc. 85(1), 228–256 (1957)
Stone, M.H.: The theory of representations for Boolean algebras. Trans. Amer. Math. Soc. 40(1), 37–111 (1936)
Taylor, W.: Hyperidentities and hypervarieties. Aequationes Math. 23(1), 30–49 (1981)
Acknowledgments
Thanks to the referees for useful remarks.
Author information
Authors and Affiliations
Corresponding author
Additional information
The research of Yu. Movsisyan is supported by the State Committee of Science of the Republic of Armenia, Grant: 10-3/1-41.
Rights and permissions
About this article
Cite this article
Davidova, D., Movsisyan, Y. A set-theoretical representation for weakly idempotent lattices and interlaced weakly idempotent bilattices. European Journal of Mathematics 2, 853–873 (2016). https://doi.org/10.1007/s40879-016-0110-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40879-016-0110-8
Keywords
- Weakly idempotent semilattice
- Weakly idempotent lattice
- Weakly idempotent bilattice
- Filter and ideal of weakly idempotent lattice
- Filter and ideal of weakly idempotent bilattice