In a context of lattice-valued functions (also called lattice-valued fuzzy sets), where the codomain is a complete lattice L, an equivalence relation defined on L by the equality of related cuts is investigated. It is known that this relation is a complete congruence on the join-semilattice reduct of L. In terms of residuated maps, necessary and sufficient conditions under which this equivalence is a complete congruence on L are given. In the same framework of residuated maps, some known representation theorems for lattices and also for lattice-valued fuzzy sets are formulated in a new way. As a particular application of the obtained results, a representation theorem of finite lattices by meet-irreducible elements is given.
The present investigation deals with ordered structures, mostly lattices and related functions. Therefore we use classical isotone and related maps, but also some techniques originating in the theory of lattice-valued fuzzy sets.
Lattice-valued fuzzy sets (L-fuzzy sets) are firstly introduced by Goguen [1]. In the framework of our paper these objects are called lattice-valued functions (since we are concentrated to functions themselves). The topic of lattice-valued functions (fuzzy sets) has been widely investigated since their introduction. Historically one of the first books dealing with this notion was published by Negoita and Ralescu [2]. After some years, it turned out that residuated lattices and related ordered structures are a convenient tool for modeling fuzzy logic [3]. Still, the basic complete lattices are the most appropriate for investigation of general properties of lattice-valued structures. Our approach is described in detail in the overview articles [4,5]. One of the basic tools for investigation of structure properties are p-cuts (cuts) and this approach is correctly implemented only with the complete lattices and ordering relation connected with the lattice operations. The related results connected to cuts (in particular with lattice-valued Boolean functions) are published in several papers by the present authors with a coauthor [6–8]. Cuts determine particular up-sets related to lattice-valued maps [9]. If residuated lattices are applied in the analogue context, then an additional operation—multiplication is used and cuts lose some important properties.
The second tool that we use in this investigation are residuated maps, closely related to Galois connections (in its definition that includes monotonicity). They are used in order theory, having a similar role as homomorphisms in the field of algebraic structures. For detailed presentations we refer to books by Blyth and Janowitz [10], by Blyth [11], by Grätzer [12] and by Caspard et al. [13].
Galois functions were generalized to the fuzzy case by Bělohlávek [14]. Cabrera et al. investigate Galois connections in the framework of fuzzy-preordered structures using particular fuzzy equivalence relations with a residuated lattice as the membership-values structure [15–17].
1.2. Topic of Our Research
Our main goal here is to solve the problem: under which conditions the equivalence relation on a complete lattice determined by cuts of a lattice-valued function is a complete congruence. Within these investigations we characterize congruences on complete lattices by residuated mappings using the well- known connection between congruences and homomorphisms. We also present some applications.
Using a residuated mapping f from L to the power set of X ordered dually to inclusion, we identify a wide class of complete lattices for which the kernel of f is a complete congruence on L. In case the set of values of μ is a meet-dense subset of a complete lattice L, then the kernel of f is the diagonal of L. We also prove that for every complete congruence ~ on a complete lattice L there is a nonempty subset M of L and a map μ:L→P(M), so that ~ is the kernel of a residuated map determined by the cuts of μ.
We present some new versions of the representation theorems for lattices and for lattice-valued fuzzy sets by the notion of residuated maps. Finally, we show that for finite lattices, the mentioned residuated maps can naturally be used for representing these lattices by the posets of their meet-irreducible elements. Papers [18,19] contain our previous research of the similar problems related to finite lattices. The results from Sections 3.1, 3.2 and 3.4 and Example appeared (without proofs) in the Proceedings of ESCIM 2019 [20].
2. PRELIMINARIES
Some relevant notions, starting with elementary ones from algebra and order theory are listed in the sequel. Our aim is to introduce notation and properties that are used in the paper.
2.1. Functions
Throughout the text we denote by f:A→B a function, mapping, from a set A, the domain of f, to a nonempty set B, the codomain of f. The set of values of f is denoted, as usual, by f(A):
f(A)={b∈B|b=f(a)for some a∈A}.
The kernel of f is the equivalence relation ≈f on A:
a1≈fa2if and only iff(a1)=f(a2).
By A∕≈f we denote the corresponding quotient-set: A∕≈f={[a]≈f|a∈A}, where [a]≈f denotes the ≈f-class of a∈A:[a]≈f={x∈A|a≈fx}.
A composition of maps f:A→B and g:B→C is here denoted by f∘g:A→C: f∘g(a)=g(f(a)).
We also use the commuting diagram for a function h from A to B:
φ(a)=[a]≈h;Ψ([a]≈h)=h(a);h=φ∘Ψ, φ is a surjection and Ψ an injection.
We deal with functions and relations among algebraic structures. If A=(A,F) is an algebra (A≠∅, F consisting of fundamental finitary operations on A), and ℬ=(B,F) another algebra of the same type (meaning that syntactically, F is the same list of functional symbols) then the map h:A→B is a homomorphism from A (in)to ℬ if it is compatible with every fundamental (n-ary) operation f on A: for any a1,…,an∈A
h(f(a1,…,an))=f(h(a1),…,h(an)),
and clearly for a nullary operation (constant) c, h(c)=c. A bijective homomorphism is an isomorphism. The kernel ≈h of h is a congruence relation on A, meaning that for any a1,…,an,b1,…,bn∈A if a1≈hb1,…,an≈hbn, then for an n-ary f∈F, f(a1,…,an)≈hf(b1,…,bn).
In a commuting diagram of a homomorphism h from A to ℬ, φ:A→A∕≈h is a homomorphism, and ψ:A∕≈h→B is an embedding (isomorphism with the subalgebra h(A) of ℬ).
2.2. Posets and Complete Lattices
We deal with ordered sets and lattices, and here are some necessary notions and the corresponding notation. For more, see, e.g., the book by Davey and Priestley [21].
We denote by (P,⩽) a poset, a nonempty set P equipped with an ordering relation ⩽. As usual, by ⩾ we denote the dual order of ⩽: p⩾q if and only if q⩽p. If Q is a subset of a poset (P,⩽), then Q is an order filter, up-set in P, if
for all x,y∈P,x∈Q and x⩽y imply y∈Q.
The empty set is also an up-set in every poset. In particular, for an element p of a poset (P,⩽), we denote by ↑p the principal filter generated by p:
↑p={q∈P|p⩽q}.
A complete latticeL is known to be a poset (L,⩽) in which for every subset M⊆L there is a greatest lower bound (glb, infimum, meet) and a least upper bound (lub, supremum, join) denoted respectively by ⋀M and ⋁M. The meet and the join are binary operations on L denoted by x∧y and x∨y, respectively. In this sense, without necessarily requiring completeness, a lattice is an algebra with two binary operations, denoted by (L,∧,∨). A complete lattice possesses the top (1) and the bottom element (0), as, respectively, glb and lub of the empty set.
A complete join-semilattice (upper-semilattice) is a poset in which for every nonempty subset there is a least upper bound, a join. A semilattice as an algebra is a commutative, idempotent semigroup (associative groupoid). If (L,∧,∨) is a lattice, then the structure (L,∨) is an upper-semilattice, called a join-semilattice reduct of the lattice L.
A congruence ρ on a complete lattice L is complete (see, e.g., [22]) if it is compatible with arbitrary meets and joins for {pi,qi|i∈I}⊆L and piρqi for every i∈I, then also (⋀ipi)ρ(⋀iqi) and (⋁ipi)ρ(⋁iqi).
A subset M of a complete lattice L is meet-dense in L if every element of L is a meet of a subset of M.
Given a lattice L, an element a in L is meet-irreducible if
a≠1anda=b∧c implies a=b or a=c.
An element a of a complete lattice L is said to be completely meet-irreducible if a≠1 and a=∧P implies that a∈P, for every subset P of L. Equivalently, a is completely meet-irreducible if the set of elements greater than a has the smallest element (this equivalence can be easily checked by contraposition).
An element a of a lattice L is distributive if for all x,y∈L, a∨(x∧y)=(a∨x)∧(a∨y). An element a of a lattice L is infinitely distributive if for {pi|i∈I}⊆L, we have a∨⋀ipi=⋀i(a∨pi). A lattice in which every element is distributive is a distributive lattice and in this case each of the two operations is distributive with respect to the other.
A complete lattice L is dually spatial if every element of L is a meet of completely meet-irreducible elements (this is the dual notion of a spatial lattice [23,24]). Examples of dually spatial lattices are all finite lattices, complete lattices, dually atomistic lattices, etc. In the case of dually spatial lattices, the subset M of completely meet-irreducible elements is a meet-dense in L.
We use the following version of Birkhoff's representation theorem for finite distributive lattices:
Theorem 1.
Let(L,⩽)be a finite distributive lattice andMthe poset of meet-irreducible elements ofL. Then(L,⩽)is isomorphic to the lattice of all up-sets ofM, ordered dually to inclusion.
2.3. Residuated Maps
For posets P and Q, a map f:P→Q is residuated if there exists a map g:Q→P such that for all x∈P and y∈Q
f(x)⩽y is equivalent to x⩽g(y).(1)
The map g is uniquely determined by f and it is called the residual of f [11,12]. In addition, both mappings are isotone.
The following characterizations of residuated maps are used in the rest of the paper [11–13].
Proposition 2.
A mapf:P→Qis residuated with the residualg:Q→P, if and only if any of the following statements hold:
For everyy∈Qthere exists the supremum of the set{x∈P|f(x)⩽y}which is equal tog(y).
For everyq∈Q, f−1(↓q)is a principal ideal (principal down-set) inP.
fis isotone and there exists an isotone mapgfromQtoPsuch thatIP⩽f∘gandg∘f⩽IQ.
Proposition 3.
A mapf:H→L, whereHandLare complete lattices, is residuated with the residualg:L→Hif and only if any of the following statements hold:
fis completely join preserving.
fis join preserving andf(0H)=0L.
A consequence is also that the residual g is completely meet preserving.
2.4. Closure Operators
An isotone map C:P→P is a closure operator on a poset (P,⩽) if C=C∘C⩾IP. C is a dual closure operator on (P,⩽) if C=C∘C⩽IP.
If p=C(p), then p is a closed element under C.
As usual, if a closure C is a unary operation on the power set P(X) of a set X, then C is said to be a closure operator onX.
Lemma 4.
Let C be a closure (dual closure) operator on a lattice L. Then,
The subset of all closed elements of L is closed under meets (joins) in L.
The top (bottom) element of L is closed under C.
Lemma 5.
The kernel ~ of a closure (dual closure) operator C on a complete lattice L fulfils:
Each equivalence class of ~ possesses the top (bottom) element which is closed under C.
The set L∕~ (denoted also by L∕C) can be ordered: [x]~⩽[y]~ iff C(x)⩽C(y) in L.
The poset (L∕~,⩽) is a lattice isomorphic to the lattice of closed elements of L, under C.
Proposition 6.
IfPis an ordered set thenC:P→Pis a closure operator if and only if there is an ordered setQand a residuated mappingf:P→Qsuch thatC=f∘g, wheregis the residual off.
A closure system over a nonempty set X is a collection of subsets of X closed under all set intersections over X (including thus X). There is a well-known connection among a closure system over X, a closure operator on X and a complete lattice [21].
2.5. Lattice-Valued Functions
Lattice-valued or L-valued functions (lattice-valued fuzzy sets) are mappings from a nonempty set X (domain) into a complete lattice L (codomain).
Let L be a complete lattice and μ:X→L an L-valued function on a set X. For p∈L, a p-cut, or a cut of μ is a subset μp of X defined by
μp={x∈X|μ(x)⩾p}=μ−1(↑p).
By μL the collection of cuts of μ:X→L is denoted: μL:={μp|p∈L}.
The basic properties of cuts of lattice-valued functions are listed in the sequel.
Proposition 7.
LetLbe a complete lattice andμ:X→LanL-valued function on a setX. Then
forp,q∈L,p⩽qimpliesμq⊆μp;(2)
⋂(μp|p∈M⊆L)=μ∨p;(3)
for every x∈X,μ(x)=⋁(p∈L|x∈μp).(4)
A straightforward consequence of formulas (3) and (4) is that the collection μL of cuts of a lattice-valued function μ from X to L is a closure system over X.
The following two propositions connect cuts of lattice-valued functions and residuated maps. The first one is used throughout the text. Therefore we provide also the proof.
Proposition 8.
[25] Letμ:X→Lbe anL-valued function onXand let the power setP(X)be ordered dually to inclusion. Consider the functions
f:L→P(X),f(p)=μp,and(5)
g:P(X)→L,g(Y)=⋁(p∈L|μp⊇Y).(6)
Thenfis a residuated function andgis the corresponding residual.
Proof.
Straightforward by Proposition 3. Namely, by the definition of f and by (3), for every M⊆L,
f(⋁(p|p∈M⊆L))=μ∨p=⋂(μp|p∈M⊆L).
Hence, f is join preserving, according to the order ⊇ in P(X). In addition, f(0)=μ0={x∈X|μ(x)⩾0}=X, and X is the bottom element in P(X) with respect to the order ⊇.
The function g given by (6) is the corresponding residual.
Proposition 9.
[25] LetXbe a nonempty set andLa complete lattice. Further, letf:L→P(X)be a residuated map, whereP(X)is with the order dual to the set inclusion, andg:P(X)→Lthe corresponding residual. Then, the cuts of the functionμ:X→Ldefined withμ(x)=g({x})coincide with values off, namely for everyp∈L, μp=f(p).
We say that the residual mapfin Proposition 8 is induced by theL-valued functionμ.
3. RESULTS
3.1. Complete Congruences on L Induced by L-Valued Functions
Starting from a complete lattice L, and using the framework of residuated maps induced by L-valued functions μ:X→L (as in Proposition 8) we analyze complete congruences on L.
The map f from L to the power set P(X) ordered dually to inclusion, induced by μ (f(p)=μp) is residuated.
The relation ≈μ on L is the kernel of f:
p≈μqif and only ifμp=μq.(7)
By the definition of a cut, it is straightforward that for p,q∈L,
p≈μqif and only if↑p∩μ(X)=↑q∩μ(X).(8)
Proposition 10.
Letμ:X→Lbe anL-valued function and≈μbe a relation onL, defined by (7). Then
≈μis a complete congruence relation on the join-semilattice reduct ofL.
The mapp↦∨[p]≈μis a closure operator onL.
Proof.
By Proposition 8, relation ≈μ is the kernel of the residuated map f:L→P(X), f(p)=μp, where the power set P(X) is ordered dually to inclusion.
The proof of (i) now follows by Proposition 3, since a residuated map is isotone. Next, (ii) is straightforward (observe that by (3) the supremum of a ≈μ-class belongs to the class).
The poset ({⋁[p]≈μ|p∈L},⩽), is a complete lattice (as a subposet of L) but it is not a sublattice of L.
By Proposition 10(i), the relation ≈μ is a join-semilattice congruence on the complete lattice L. Hence, there is an order ⩽ on L∕≈μ induced by the order ⩽ on L:
[p]≈μ⩽[q]≈μif and only ifμq⊆μp,(9)
and we get the lattice (L∕≈μ,⩽).
In addition, we can replace the mapping f:L→P(X), by the map φ from L (on)to the lattice (f(L),⊇)=(μL,⊇), so that φ is defined in the same way as f: φ(p)=μp.
Proposition 11.
Forμ:X→L, letμLbe ordered dually to inclusion. Then the mapφ:L→μL, such thatφ(p)=μp, is residuated and(L∕≈μ,⩽)≅(f(L),⊇)under[p]≈μ↦f(p).
Proof.
The proof follows by Proposition 10, since f is a join-semilattice homomorphism.
Hence, an isomorphism of lattices is formulated in the next theorem.
Theorem 12.
Forμ:X→L, the following isomorphisms of lattices hold:
(L∕≈μ,⩽)≅({⋁[p]≈μ|p∈L},⩽)≅(μL,⊇).(10)
In other words: For a givenL-valued mapμ, the lattice of≈μ-classes is isomorphic to the lattice of top elements of these classes, and both are isomorphic to the lattice of cuts ofμordered dually to inclusion.
Relation ≈μ is not generally a congruence on L as a lattice. In the sequel, we give conditions under which it is the case.
By Proposition 10, for μ:X→L, ≈μ is a complete congruence on L if and only if the map φ:L→μL, φ(p)=μp, is compatible with arbitrary meets. This is obvious since φ is an onto map, and since (L∕≈μ,⩽)≅(μL,⊇). Our aim is to find conditions under which this holds, in terms of the L-valued function μ, analyzing the set μ(X) of values of μ.
Theorem 13.
LetLbe a dually spatial lattice andμ:X→LanL-valued function on a nonempty domainX, such thatμ(X)consists of some infinitely distributive completely meet-irreducible elements inL. Then≈μis a complete congruence relation onL.
Proof.
We prove that ≈μ is compatible with arbitrary meets in L.
Let {pi|i∈I}, {qi|i∈I} be two families of elements in L, and for every ipi≈μqi. This means that for every m∈μ(X) and for every i∈I,
pi⩽mif and only ifqi⩽m.(11)
To prove the analogue equivalence for ∧pi and ∧qi, assume that for an m∈μ(X), we have that ∧pi⩽m, i.e., that m∨∧pi=m. By assumption every m∈μ(X) is infinitely distributive, hence ∧i(m∨pi)=m and therefore, since m is completely meet-irreducible, m∨pj=m for some j∈I, hence pj⩽m; by (11) also qj⩽m, therefore ∧iqi⩽qj⩽m. Analogously we can start with ∧qi. Therefore ∧pi≈μ∧qi.
Lemma 14.
For μ:X→L, if μ(X) is meet-dense in a complete lattice L, then the residuated map f:L→P(X) induced by μ is an injection.
Proof.
Let p,q∈L and suppose f(p)=f(q), i.e., let ↑p∩μ(X)=↑q∩μ(X). Since μ(X) is meet-dense in L, we have that
p=∧(↑p∩μ(X))=q,
and f is an injective map.
A straightforward consequence of Lemma 14 follows in the sequel.
Corollary 15.
For μ:X→L, if μ(X) is meet-dense in a complete lattice L, then the relation ≈μ is the smallest (complete) congruence relation, diagonal ΔL, on L.
We note that ≈μ is a diagonal relation on L also in the case when a meet-dense set is a subset of μ(X).
A finite version of the result presented in Theorem 13 is formulated in the sequel, together with an application to quotient lattices.
Theorem 16.
LetLbe a finite lattice, letMbe a subset ofLconsisting of some distributive meet-irreducible elements, andμ:M→L,μ(m)=m. Then the following holds:
≈μis a congruence relation onL.
The set[M]:={[m]≈μ|m∈M}, consists of all meet-irreducible elements of the quotient lattice(L∕≈μ).
Proof.
This is a formulation of Theorem 13 for finite lattices.
Let m∈M and suppose [m]≈μ is not meet-irreducible in L∕≈μ. Then [m]≈μ=[u]≈μ∧[v]≈μ for some u,v∈L so that the classes [u]≈μ and [v]≈μ are not comparable. The relation ≈μ is a congruence on L, hence there are u1∈[u]≈μ and v1∈[v]≈μ such that m⩽u1 and m⩽v1. Then m⩽u1∧v1∈[m]≈μ. Since m is the top element in the class to which it belongs, we get m=u1∧v1. Contradiction, since m is meet-irreducible in L.
On the other hand, let [x]≈μ be a meet-irreducible class in L∕≈μ. Then for m=∨[x]≈μ, m is meet-irreducible. Indeed, if, contrary, m=u∧v for some incomparable u,v∈L, then [m]≈μ=[x]≈μ=[u]≈μ∧[v]≈μ and [x]≈μ is not meet-irreducible in L∕≈μ. This proves that m is meet-irreducible in L. To prove that, in addition, m∈M, observe that a meet-irreducible element m which is not in M could not be the top of the ≈μ-class to which it belongs. Indeed, such m belongs to the same class as the element covering it.
Corollary 17.
Let L be a finite distributive lattice and M⊆L, consisting of (some) meet-irreducible elements in L. Then ≈μ is a congruence relation on L.
3.2. From Congruences to Residuated Maps
In this paragraph we deal with the converse of the results in Section 3.1. In the sequel, we show that every complete congruence on a complete lattice L is the kernel of the residuated map induced by a particular L-valued function whose codomain is L.
First we need the following technical lemma.
Lemma 18.
Let L be a complete lattice, let M be a nonempty subset of L and μ:M→L, such that for every m∈M, μ(m)=m. Then for every p∈L, μp=↑p∩M.
Now we deal with a congruence on the join-semilattice reduct of L. We show that it is always the kernel of a residuated map, as in Proposition 8.
Theorem 19.
Let~be a complete congruence on the join-semilattice reduct of a complete latticeL. LetMbe a set of maximum elements in~-classes:
M={m∈L|m=∨[p]~ for some p∈L}.
Let alsoμ:M→Lbe theL-valued function given byμ(m)=m. Then the functionf:L→P(M)such thatf(p)=μpwhereP(M)is ordered dually to inclusion is residuated and~is the kernel off.
Proof.
By Proposition 8, f is a residuated map and ≈μ is the kernel of this function. Then for p,q∈M (which is the set of maximum elements of ~-classes), p≈μq if and only if μp=μq if and only if (Lemma 18) ↑p∩M=↑q∩M if and only if ∨[p]~=∨[q]~ if and only if [p]~=[q]~ if and only if p~q. Hence, ~ coincides with the kernel of f, i.e., with ≈μ.
Now, from Theorem 19, we get the answer for congruences.
Corollary 20.
For every complete congruence ~ on a complete lattice L, there is a set M, an L-valued function μ:M→L and a residuated map f:L→P(M) induced by μ by f(p)=μp, so that ~ is the kernel of f.
3.3. Representation Theorems for Lattice-Valued Fuzzy Sets
In a paper by Gorjanac Ranitović and Tepavčević [26], necessary and sufficient conditions are formulated, under which two lattice-valued fuzzy sets on the same domain have the same families of cuts. Moreover necessary and sufficient conditions are given under which for a given family of subsets ℱ of a set X and a fixed complete lattice L there is a lattice-valued fuzzy set μ:X→L, such that the collection of cuts of μ coincides with ℱ.
In the following proposition, which is reformulated using Proposition 3, conditions are given under which two fuzzy sets have the same families of cuts (when the codomain lattices are connected with the residual mappings).
Proposition 21.
Let(L,∧,∨)and(L1,∧,∨)be complete lattices and letφ:L→L1be a residuate map from(L,⩾)to(L1,⩾)(duals of latticesLandL1). Letμ:X→Lbe a fuzzy set onX. Let fuzzy setν:X→L1be defined byν(x)=φ(μ(x)). Then fuzzy setsμandνhave the same families of cuts andμp=νφ(p)for allp∈L.
Further, we give a representation theorem for lattice-valued fuzzy sets, based also on cut properties. However the present representation uses residuated functions.
Theorem 22.
LetLbe a fixed complete lattice, X≠Φandℱ⊆P(X). A necessary and sufficient condition under whichℱis a collection of cuts of a fuzzy setμ:X→Lis that there is an onto residuated mapf:L→ℱ, whereℱis ordered dually to inclusion.
Proof.
This is a straightforward consequence of Propositions 8 and 9.
In the mentioned paper [26], it is also proved that for every function μ:X→L, where L is a complete lattice, there is a function ν:X→{0,1}c, where c is a suitable cardinal number, so that the cuts of μ and ν coincide. ν is said to be given in the general form of lattice-valued fuzzy sets; the reason is that every lattice L is isomorphic to the lattice of all principal ideals of L ordered by inclusion, and the latter can be embedded into the Boolean lattice {0,1}c for some cardinal number c, so that infima are preserved. Considering cuts, this condition is sufficient that they coincide. In addition, we can assume that there is a single (sufficiently big) cardinal c for all complete lattices under consideration.
Next we use this result and the above ideas of its proof. As mentioned, we assume to have a single cardinal c and we denote by B={0,1}c the corresponding Boolean lattice.
Theorem 23.
LetXbe a nonempty set, letLbe a complete lattice andμ:X→L. Then there is a residuated mapf:B→P(X)whereP(X)is ordered dually to inclusion, so thatf(B)is a collection of cuts ofμ.
3.4. Representation of Finite Lattices
In this part, results regarding kernels of residuated maps and L-valued functions are applied to finite lattices with a given poset of meet-irreducible elements.
Starting from a finite poset M, by LM the collection of all up-sets of M is denoted. By Birkhoff's theorem, a finite distributive lattice in which M is the poset of meet-irreducibles is isomorphic to (LM,⊇) under p↦↑p∩M. In order to work with residuated functions, we replace the power set of M by LM.
Proposition 24.
LetLbe a finite lattice in whichMis the poset of meet-irreducibles andμ:M→L, μ(m)=m. Then≈μisΔL.
Proof.
Indeed, the map f:L→LM, given by f(p)=↑p∩M where LM is ordered dually to inclusion, is residuated, induced by μ, since ↑p∩M=μp. Therefore, ≈μ is ΔL by Corollary 15, since M is clearly meet-dense in L.
Under the conditions of Proposition 24, the map g:LM→L, such that
g(N):=⋁(p|f(p)⊇N,N∈LM)(12)
is the residual of function f. We proceed by analyzing this residual.
Proposition 25.
LetLbe a finite lattice with the setMof meet-irreducibles andμ:M→L, μ(m)=m. Then the mapC:LM→LMsuch thatC=g∘f, wherefandgare induced byμ, as in Proposition 24, is a dual closure operator on(LM,⊇), namelyC(Y)=μg(Y), Y∈LM.
Proof.
Straightforward by Proposition 8. Namely, C is isotone with inclusion, and clearly, for Y∈LM, C(C(Y))⊇Y.
Finally, we have a representation theorem for finite lattices in terms of up-sets and residuated functions. In the following it is proved that any finite lattice with the poset M of meet-irreducibles, is isomorphic to the lattice of closed elements of a dual closure in the distributive lattice LM ordered by ⊇.
Theorem 26.
LetLbe a finite lattice andMthe set of all meet-irreducible elements inL. Let also the functiong:LM→Lbe given by (12). ThenL≅({μg(N)|N∈LM},⊇).
Proof.
By Proposition 25, the lattice ({μg(N)|N∈LM},⊇) consists of closed elements—cuts under the closure C=g∘f. In addition, these cuts are up-sets in M, which is, by assumption, the poset of meet-irreducible elements in L. By Proposition 24, ≈μ-classes are one-element sets. Hence f is an injection and by Theorem 12, we get the isomorphism from (L,⩽) onto ({μg(N)|N∈LM},⊇): p↦↑p∩M.
By Lemma 5 (the dual), we have also the following.
Corollary 27.
Let L be a finite lattice and M the set of all meet-irreducible elements in L. Then (L,⩽)≅(LM∕~C,⩽), where ~C is the kernel of the dual closure operator C on LM defined in Proposition 25.
The converse is proved in the sequel.
Theorem 28.
LetMbe a finite poset andCa dual closure operator on(LM,⊇)fulfilling: for everym∈Mthe class[m]~Cis a singleton, where~Cis the kernel ofC. Then the poset of meet-irreducibles of the lattice(LM∕~C,⩽)is isomorphic toM.
Proof.
The map m↦[m]~C is an order embedding from the poset M into the lattice LM∕~C. Indeed, it is obviously one-to-one; the order is preserved by Birkhoff's theorem and by Lemma 5. We prove that every class [m]~C (m∈M) is meet irreducible in (LM∕~C,⩽). Suppose that this is not the case, i.e., that for some m∈M, [m]~C=[p]~C∧[q]~C for some elements p,q∈LM which we take to be the bottom elements of the corresponding classes. Since the class [m]~C is the singleton, the last formula is equivalent with m=p∧q in LM, where p and q are the bottom elements of the corresponding class. Since m is a meet-irreducible element in LM, we have that m=p or m=q, hence [m]~C is meet-irreducible in LM∕~C
Conversely, suppose that a class [n]~C is meet-irreducible in (LM∕~C,⩽), where n is the bottom element of the class. Now, n=∧xi, where xi (for i∈I) are some meet-irreducible elements in M (and in LM) (every element is a meet of meet-irreducible elements). Since all the classes [xi]~C, for i∈I are one-element, we have that [n]~C=∧i∈I[xi]~C. Since [n]~C is meet-irreducible, we have that [n]~C=[xi]~C for some i∈I and hence n=xi.
Therefore, the poset of meet-irreducible classes in LM∕~C is order-isomorphic to the poset M.
Example The lattice L in Figure 1 (a) possesses five meet-irreducible elements p, q, r, s, t denoted by filled circles, forming a poset M, represented in Figure 1 (b). According to Corollary 27, L is isomorphic to the lattice (LM∕~C,⩽). Observe that ~C is not a congruence on LM; this quotient is isomorphic to the lattice of closed elements of the dual closure C on (LM,⊇), illustrating Theorem 26.
Figure 2 uses the same finite lattice L and illustrates Theorem 16. Among the meet-irreducibles of the lattice L, only p and q are distributive, N={p,q}. The L-valued function inducing the corresponding residuated function is ν:N→L, ν(x)=x, and the corresponding congruence ≈ν is indicated in Figure 1 (c). Recall that for x,y∈L, x≈νy if and only if νx=νy if and only if ↑x∩{p,q}=↑y∩{p,q}. Hence the lattice L∕≈ν is a three-element chain.
Finally, N could be a nonempty subset of {p,q}, namely we can take N={p}, or N={q}. In both cases we get a congruence splitting L into two classes (in each case joining two neighboring classes of the congruence in Figure 2).
As presented above, we have shown that there is a natural connection among complete congruences on complete lattices and particular residuated maps induced by lattice-valued functions. As an extension of this research, we intend to deal with analog connections in particular classes of (complete) lattices, like distributive, Boolean or residuated ones. In addition, representation problems which were successfully analyzed for finite lattices, will be our topic of investigation for arbitrary lattices fulfilling some finiteness conditions.
CONFLICT OF INTEREST
The authors declare no conflict of interests.
AUTHORS' CONTRIBUTIONS
B.Seselja and A.Tepavcevic both designed the manuscript, worked on the mathematical theorems and proofs, drafted the manuscript and checked the final version of the manuscript.
ACKNOWLEDGMENTS
Research supported by Ministry of Education, Science and Technological Development, Republic of Serbia through Mathematical Institute of SASA and through Faculty of Sciences, University of Novi Sad is gratefully acknowledged.
TY - JOUR
AU - Branimir Šešelja
AU - Andreja Tepavčević
PY - 2020
DA - 2020/07/20
TI - Kernels of Residuated Maps as Complete Congruences in Lattices
JO - International Journal of Computational Intelligence Systems
SP - 966
EP - 973
VL - 13
IS - 1
SN - 1875-6883
UR - https://doi.org/10.2991/ijcis.d.200714.001
DO - 10.2991/ijcis.d.200714.001
ID - Šešelja2020
ER -
