We study complete lattices which are contained in other complete lattices as suborders, but not necessarily as subsemilattices. We develop a representation of such lattices by means of implications, and show how to navigate them using a modification of the standard Next closure algorithm. Our approach is inspired by early work of Shmuely [8] and Crapo [1].
c paper author(s), 2018. Proceedings volume published and copyrighted by its editors.
Paper published in Dmitry I. Ignatov, Lhouari Nourine (Eds.): CLA 2018, pp. 153{165, Department of Computer Science, Palacky University Olomouc, 2018. Copying permitted only for private and academic purposes.
decreasing
increasing dually tensive idempotent
tensive E2d E1d
E2 E1 extensive E3 contractive
E3d
Proposition 1. Figure 1 shows the logical hierarchy of the properties given in Definition 1. In particular, if ϕ : L → L is monotone, then the following statements hold (as well as their duals): 1. If ϕ is extensive, then ϕ is tensive. 2. If ϕ is tensive, then ϕ is increasing. 3. ϕ is idempotent iff ϕ is both increasing and decreasing. 4. If ϕ is idempotent and extensive, then ϕ is dually tensive.
Moreover, there are examples of monotone functions falsifying other implications, as indicated in the diagram.
Proof. 1) If x ≤ ϕ(x), then x ∧ ϕ(x) = x and thus ϕ(x ∧ ϕ(x)) = ϕ(x). 2) From x ∧ ϕ(x) ≤ ϕ(x) we infer ϕ(x) = ϕ(x ∧ ϕ(x)) ≤ ϕ(ϕ(x)). 3) is obvious. 4) If x ≤ ϕ(x) then ϕ(x ∨ ϕ(x)) = ϕ(ϕ(x)) = ϕ(x).
For the separating examples we use functions of the form ϕL, to be defined in Proposition 6. (L, ≤) is the powerset lattice of {a, b, c} for E1 and E2 and of {a, b} for E3. E1: L = {{a} → {b, c}, {b} → {c}, {c} → {b}}, E2: L = {{a} → {b}, {a, b, c} → {a, b, c}} (see Example 1 below), E3: L = {∅ → {a}, {a} → {b}, {b} → {b}}. E1d, E2d, E3d are dual to E1, E2, E3. tu Definition 2 If ϕ : L → L is a mapping and x ∈ L, then we say that x is a fixed point of ϕ, iff ϕ(x) = x, and that x is a closed point of ϕ, iff ϕ(x) ≤ x. ♦ Proposition 2. Every fixed point is closed. If ϕ is monotone and increasing, and x is closed, then ϕ(x) is fixed. Proof. The first statement is obvious. Suppose that x is closed, i.e., that x ≥ ϕ(x). Then ϕ(x) ≥ ϕ(ϕ(x)) ≥ ϕ(x), since ϕ is monotone and increasing. We conclude that ϕ(x) = ϕ(ϕ(x)) and thus ϕ(x) is fixed.
The proposition may suggest a pairing between fixed and closed elements. But note for example that when ϕ is the function which maps everything to the least element of (L, ≤), then every element of (L, ≤) is closed, but only the least element is fixed.
A function that is both idempotent and monotone is called a closure operator on (L, ≤) if it is extensive, and is a kernel operator if contractive. The set of fixed points of a closure operator is called a closure system. It is well known that the closure systems are precisely the V-subsemilattices. Each complete meet-subsemilattice of a complete lattice is itself a complete lattice, because the join operation can be expressed in terms of the meet operation: the join of a subset S equals the meet of all upper bounds of S. However, this join operation usually is not identical with the join in the original complete lattice. The meet-subsemilattice therefore is a complete lattice, but not a complete sublattice in general. In a closure system of sets, for example, the join of two elements is usually not given by their set union, but by the closure of this union. Thus a closure system, ordered by set inclusion, is a complete lattice, but not necessarily a sublattice.
The fixed points of a kernel operator are closed under arbitrary joins and thus form a W-subsemilattice, also called a kernel system. Again we get the second operation from the first, so that each kernel system also is a complete lattice.
This shows that closure systems are not the only subsets yielding orderembedded complete lattices. In fact, the following is well known4: Lemma 1. A subset of a complete lattice (L, ≤), with the induced order, is a complete lattice if and only if it is the image of a monotone and idempotent function ϕ : L → L.
Proof. Suppose that F = {ϕ(x) | x ∈ L} for some monotone and idempotent function ϕ : L → L. We claim that for any subfamily S ⊆ F the element ϕ(V S) is the infimum of S in F . Clearly V S ≤ s holds for every s ∈ S. Since ϕ is monotone, we get that ϕ(V S) ≤ ϕ(s) = s for all s ∈ S, which shows that ϕ(V S) is a lower bound of S. But any lower bound b of S must satisfy b ≤ s for all s ∈ S and therefore b ≤ V S. If b ∈ F , then b = ϕ(b) ≤ ϕ(V S), as desired.
For the converse suppose that F ⊆ L is a complete lattice and define a function ϕ : L → L by ϕ(x) := supF {f ∈ F | f ≤ x} (where supF denotes the supremum in F ). This function is clearly idempotent and monotone, and its image is F . tu
Lemma 1 adds a kind of converse to the celebrated Knaster-Tarski
theorem [
Two details from the proof of Lemma 1 will be used later. We list them as separate propositions: Proposition 3. Let ϕ be an idempotent and monotone function on a complete lattice (L, ≤), and let W, V denote the supremum and infimum operation of (L, ≤), respectively.
In the complete lattice of fixed points of ϕ, the supremum and infimum of a set S are given by ϕ(_ S) and ϕ(^ S).
The second part of the proof of Lemma 1 is stronger than necessary: the function which was used is not only monotone and idempotent, but has an additional property: Proposition 4. The function which was used in the proof of Lemma 1, x 7→ ϕ(x) := supF {f ∈ F | f ≤ x}, is tensive.
Proof. If f ≤ x and f ∈ F , then f ≤ ϕ(x) and so f ≤ x ∧ ϕ(x). Thus {f ∈ F | f ≤ x} ⊆ {f ∈ F | f ≤ x ∧ ϕ(x)}, which implies that ϕ(x) ≤ ϕ(x∧ϕ(x)). Since ϕ is monotone, we conclude equality. tu A simple consequence of the Knaster-Tarski result which we will use is Proposition 5. If (L, ≤) is a complete lattice, ϕ : L → L is monotone, and x ∈ L is an element for which x ≤ ϕ(x), then there is a least fixed point of ϕ that is greater or equal to x.
Proof. Note that since ϕ is monotone, the set ↑ x := {y ∈ L | x ≤ y} is mapped into itself by ϕ: when y ≥ x, then ϕ(y) ≥ ϕ(x) ≥ x. But ↑ x is a complete lattice as well, to which the Knaster-Tarski result can be applied. So there is a least fixed point of ϕ in ↑ x. tu Lemma 2. If ϕ : L → L is monotone and increasing, then for each x ∈ L there is a least closed element ϕ(x) ≥ x, and there is a least fixed element ϕ(x) ≥ ϕ(x). b If ϕ is tensive, then so is ϕb.
Proof. For the first claim define a function ρ(x) := x ∨ ϕ(x). Note that the fixed points of ρ are precisely the closed points of ϕ. Clearly ρ is monotone and extensive, so by Proposition 5 there is a least fixed point y of ρ which is greater or equal to x.
The second claim follows again from Proposition 5, assuming that the function ϕ is increasing.
Finally, assume that ϕ is tensive. By definition, ϕ(x ∧ ϕ(x)) is the least fixed b point of ϕ greater or equal to ϕ(x ∧ ϕ(x)). But when ϕ is tensive, the latter equals ϕ(x), and therefore ϕb(x ∧ ϕ(x)) = ϕ(x). But since ϕ(x) ≤ ϕ(x), we get b b ϕb(x) = ϕb(x ∧ ϕ(x)) ≤ ϕb(x ∧ ϕb(x)) ≤ ϕb(x), which concludes the proof. tu Note that the function ϕ, defined in Lemma 2, is a closure operator, and that ϕb has the same fixed points as ϕ.
Lemma 3. If ϕ is monotone and increasing, then for all x ∈ L ϕ(x) = ϕ(ϕ(x)).
b Proof. ϕb(x) is fixed and therefore closed, and contains ϕ(x), thus ϕ(x) ≥ ϕ(ϕ(x)). b It remains to show that ϕb(x) ≤ ϕ(ϕ(x)). Proposition 2 yields that ϕ(ϕ(ϕ(x))) b is fixed and less or equal to ϕ(ϕ(x)). The proof is complete if we show that this fixed element contains ϕ(x), because that forces it to be equal to ϕb(x) (which is the least such fixed point). But from ϕ(x) ≤ ϕ(ϕ(x)) and the fact that ϕ is increasing and monotone we conclude that ϕ(x) ≤ ϕ(ϕ(x)) ≤ ϕ(ϕ(ϕ(x))). tu
There is a simple way of constructing such monotone and increasing functions without reference to an embedded lattice. It relies on implications. An implication over L is just an ordered pair5 of elements x, y ∈ L, denoted x → y. We say that a lattice element z respects an implication x → y if x 6≤ z or y ≤ z. Proposition 6. Let L be a set of implications over L. The function ϕL : L → L, defined as
ϕL(x) := _{a ∨ b | a ≤ x, a → b ∈ L}, is monotone and tensive. Conversely, if ϕ : L → L is monotone and tensive, then ϕ = ϕL for
L = {x ∧ ϕ(x) → ϕ(x) | x ∈ L}.
Proof. When x ≤ y, then {a → b ∈ L | a ≤ x} ⊆ {a → b ∈ L | a ≤ y}, and thus ϕL(x) ≤ ϕL(y). So ϕL is monotone. For the other claim, note that if a → b ∈ L and a ≤ x, then a ≤ ϕL(x) and thus a ≤ x ∧ ϕL(x). It follows that ϕL(x ∧ ϕL(x)) ≥ ϕL(x). Monotonicity of ϕL yields equality and concludes the proof that ϕL is tensive.
For the converse we claim that we have ϕL(y) = ϕ(y) for all y ∈ L. Since y ∧ ϕ(y) ≤ y and y ∧ ϕ(y) → ϕ(y) ∈ L, we get that ϕL(y) ≥ ϕ(y). If x ∧ ϕ(x) ≤ y holds for some x, then ϕ(x) = ϕ(x ∧ ϕ(x)) ≤ ϕ(y) (since ϕ is monotone and tensive), and therefore ϕL(y) ≤ ϕ(y). This proves ϕL = ϕ. tu 5 The notion abstracts that of an attribute implication in Formal Concept Analysis.
Note that in our approach implication sets are not assumed to be closed under the Armstrong rules. Example 1. The separating example E2 of Figure 1 was defined in the proof of Proposition 1 as the monotone function ϕL on the power set of {a, b, c} given by the implication set
L := {{a} → {b}, {a, b, c} → {a, b, c}}.
According to the definition in Proposition 6, this function has the following values:
x ϕL(x) ∅ ∅ {a} {a, b} {b} ∅ {c} ∅ {a, b} {a, b} {a, c} {a, b} {b, c} ∅ {a, b, c} . {a, b, c} It is easy to check that the function is monotone, idempotent, and tensive. But it is not dually tensive, since ϕL({a, c}) = {a, b} 6= ϕL({a, c} ∪ ϕL({a, c})) = ϕL({a, b, c}) = {a, b, c}.
Following Definition 2 we call an element x ∈ L fixed under a set L of implications, if x = ϕL(x), and closed, if x ≥ ϕL(x). It is easy to see that the latter is equivalent to the standard definition in Formal Concept Analysis, where an element is called closed under L when it respects all implications in L. The corresponding closure operator is often denoted x 7→ L(x). Here we write ϕL, as it is suggested by Lemma 2. The following is a corollary to that lemma. Corollary 2. Let L be a set of implications over L. Then the function ϕbL : L → L, defined by
ϕbL(x) is the least fixed point of ϕL greater or equal to ϕL(x), is idempotent, monotone, and tensive. Moreover,
ϕbL(x) = ϕL(ϕL(x)) for all x ∈ L.
A very welcome consequence of this corollary is that ϕbL can efficiently be
computed, for example by the LinClosure algorithm (see Algorithm 15 in [
It is actually possible to give a (kind of) explicit representation of ϕbL in terms of ϕL: If (L, ≤) is finite, then ϕbL(x) := ϕL(x) ∨ ϕL(ϕL(x)) ∨ ϕL(ϕL(ϕL(x))) ∨ . . . . (∗) Without the finiteness condition it may be necessary to apply ϕL “transfinitely often”, as the following example shows.
Example 2. Let L := N ∪ {∞1, ∞2}, where the integers are in the natural order, ∞1 is greater than all integers and ∞1 < ∞2. Moreover, let
L := {0 → 1, 1 → 2, 2 → 3, . . .} ∪ {∞1 → ∞2}.
For x := 0 we get ϕL(x) = 1, ϕL(ϕL(x)) = 2, and so on. Applying formula (∗) yields ϕbL(0) = 1∨2∨3∨. . . = ∞1. But this is no fixed point, since ϕL(∞1) = ∞2. Example 3. Let M := {a, b, c, d}, (L, ≤) := (P(M ), ⊆), and
L := {{a} → {a}, {b} → {b}, {b, c, d} → {b, c, d}, {a, b} → {c}}.
Then, for example, ϕbL({a, c, d}) = {a} and ϕbL({a, b, d}) = {a, b, c}. ϕbL has six fixed points; ∅, {a}, {b}, {a, b, c}, {b, c, d}, and {a, b, c, d}. These six sets, ordered by ⊆, form a complete lattice which is neither a T- nor a S-subsemilattice of the powerset lattice.
We claim that our construction based on implications is universal in the sense, that every embedded complete lattice is obtained. This is shown in the theorem below.
Theorem 1. For every monotone function ϕ : L → L on a complete lattice (L, ≤) there is a set L of implications over L such that ϕ and ϕbL have the same fixed points.
Proof. The set F of fixed points of any monotone function is, according to Knaster and Tarski (see Corollary 1), a complete lattice. For each such complete lattice (F , ≤) we therefore need to find a suitable set of implications. Let supL denote the supremum in (L, ≤) and supF denote the supremum in (F , ≤). We choose
L := {supL S → supF S | S ⊆ F } and prove that the fixed points of ϕbL are precisely the elements of F :
First suppose that e ∈ F . The ϕL(e) = e because, first of all, e → e ∈ L, and secondly e respects all implications in L: if supL S ≤ e for some set S ⊆ F , then e ≥ s for all s ∈ S and, since (F , ≤) is a complete lattice, e ≥ supF S. Conversely, if e = ϕbL(e) is a fixed point of ϕbL, then let S := {f ∈ F | f ≤ e} be the set of all F -elements below e. Since e respects the implication supL S → supF S, we get supF S ≤ e. But whenever the premise of an implication in L is below e, it must be below supL S. Therefore e = ϕL(e) = supF S and thus e ∈ F . tu As an immediate consequence of Theorem 1 we get Corollary 3. The subsets of a complete lattice which are, with the induced order, complete lattices themselves, are precisely the sets of fixed elements under some set of implications.
ϕbL is usually not extensive, while the closure operator ϕL is. That condition can easily be achieved by including {x → x | x ∈ L} into the list of implications (it actually suffices to do this for a join-dense set of elements), so all closure operators are of the form ϕbL for a suitable set L.
But kernel operators can be represented as well: If F is a kernel system, then ϕbL is the corresponding kernel operator when L := {f → f | f ∈ F }. More generally, if F is an arbitrary family of sets then the so defined function ϕbL is the kernel operator for the kernel system generated by F .
Is it possible to find, for a given function, a suitable implication set without reference to the embedded lattice of fixed points? The next proposition gives an answer. However, we shall learn from Example 4 that this is not always practical. Proposition 7. If ϕ : L → L is monotone, idempotent, and tensive, then the set
L := {x ∧ ϕ(x) → ϕ(x) | x ∈ L} is such that ϕbL = ϕ.
Proof. From Proposition 6 we get that ϕ = ϕL. But when ϕ is idempotent, then ϕ(x) → ϕ(x) ∈ L, which makes ϕ(x) a fixed point of ϕL, and we conclude ϕ = ϕL = ϕbL. tu To summarize: Every embedded complete lattice is the image of some function which is monotone, idempotent and tensive (Proposition 4). These are precisely the functions which can be described by means of implications as in Corollary 2. Implications can easily be found for any given such function (Proposition 7). 4
Many years ago the author suggested a simple algorithm [
It is easy to generalize the algorithm to closure operators on complete lattices, not only powerset lattices. It therefore seems natural to ask if a modification of Next closure can be used for generating all images of any given idempotent, monotone, and tensive function. Unfortunately, the answer is “no”, unless some additional information is provided. Our pessimism is prompted by the following example: Example 4. Let A ⊆ L be an antichain in a complete lattice (L, ≤), let 0L and 1L be the least and the greatest element of (L, ≤), and let f be an element of A. The function if x = f if a < x for some a ∈ A else is idempotent, monotone, and tensive.
In this example it is tedious to determine the fixed points by repeated invocation of ϕ. Since the number of antichains may be exponential6 in the size of L, but nevertheless may be large on average, it seems difficult to find an algorithm which determines the fixed point f reasonably fast. Stronger assumptions are needed.
Proposition 8. Let (L, ≤) be a complete lattice, let ϕ : L → L be a monotone and idempotent function and let G ⊆ L be a finite set that is join-dense in the complete lattice formed by the images of ϕ. Endow G with an arbitrary linear order.
Compute a sequence of sets, starting with A := {g ∈ G | g ≤ ϕ(∅)}, and then repeatedly invoking the algorithm in Figure 3, always using the previous output as the next input, until ⊥ is reached. For each set B in this sequence, ϕ(W B) is a fixed point of ϕ, and all fixed points occur exactly once.
B := {h ∈ G | h ≤ ϕ(W(A ∪ {g}))} if g is the smallest element of B \ A then return B Proof. Each fixed point f of ϕ is uniquely determined by its projection Π(f ) := {g ∈ G | g ≤ f } to the join-dense set G, because it can be obtained as the join of these elements: f = ϕ(W(Π(f ))) (recall from Proposition 3 that S 7→ ϕ(W S) is the join operation in the fixed point lattice). These projection sets form a closure system on G, for which F 7→ Π(ϕ(W F )) is the closure operator. tu 6 For example, the Dedekind numbers in case that L is a powerset lattice. a b c d 1 2 3 4 × × × × × × ×
Example 5. We illustrate our findings by calculating the closed relations of the
formal context in Figure 4. Closed relations are subrelations with the property
that every formal concept of the subrelation is a formal concept of the original
formal context [
× × × × × × × × × × × × × 3 9 15 × × × × × 4 × × × 5 × × ×
6 × × × × 10 × × × × × 11 × × × × × 12
× 16 × × × × × 17 × × × × × 18 × × × × × ×
× × × × × × × × × the trivial ones) are not closed under intersection nor under union. The union of relations R1 and R2 is not closed, nor is the intersection of R3 and R4 closed. However, when ordered by set inclusion ⊆, these 20 relations form a complete lattice which is isomorphic to the lattice of all complete sublattices. This lattice of closed relations is contained in the lattice (P({a, b, c, d} × {1, 2, 3, 4}), ⊆) of all relations between these two sets as a suborder, but not as a sublattice.
The closed relations R1, R2, R3, R4, and R12 are of the form A × B for some nontrivial formal concept (A, B) and represent the complete sublattice with exactly one nontrivial element. These are the join-irreducible closed relations. Together, they form a join-dense set. For reasons that become clear later we reverse the order and work with
G := {R12 < R4 < R3 < R2 < R1}.
The function ϕ will be given by eight implications, five of which are of the form X → X. Three more are derived from the condition that a sublattice must be closed under join and meet. So ϕ := ϕbL for
L := {R1 → R1, R2 → R2, R3 → R3, R4 → R4, R12 → R12}
∪ {R1 ∪ R2 → R4, R1 ∪ R3 → R4, R2 ∪ R3 → R4}.
If Algorithm 3 is used for this operator ϕ and is started with the empty relation, it produces all closed relations in the order of Figure 5, terminating with the full incidence relation of the context in Figure 4.
We give one intermediate step of the algorithm in detail, namely the step from R2 to R3:
R2 contains none of the other relations in G, so the Next fixed point algorithm is invoked with A := {R2}. The largest element of G is R1, which is not in A, so B := {h ∈ G | h ≤ ϕ(W(A ∪ {R1}))} must be computed. A ∪ {R1} = {R1, R2}, and the join W is the union S of relations. We obtain W(A ∪ {R1}) = R1 ∪ R2, which is not a closed relation. But L contains three implications the premise of which is contained in R1 ∪ R2, and we find that ϕL(R1 ∪ R2) = ϕ(R1 ∪ R2) = R1 ∪ R2 ∪ R4 = R7 and, since R7 contains no further elements of G, B = {R1, R2, R4}. However, R1 is not the smallest element of B \ A (the smallest element is R4), so this iteration step does not return a result. The next iteration has A = {R1} and g = R1, so R1 is simply removed from A. Then A = ∅ and g = R3 result in B = {R3}, which is returned as the next closed relation.
For this particular example, the set of all 20 sublattices of the lattice in Figure 5 is easily determined by hand. In general, a concept lattice can be much larger than its formal context. Working with the formal context then may be more efficient.
How to find a join-dense set, as it is required in Proposition 8 ? There is an easy answer when the function ϕ is given by implications.
Proposition 9. Let ϕ := ϕbL for some set L of implications. Then the set {ϕ(a) | a → b ∈ L} is join-dense in the lattice of fixed points of ϕ.
Proof. Any fixed point of ϕbL by definition also is a fixed point of ϕL. So if ϕbL(f ) = f then
f = ϕL(f ) = _{a ∨ b | a ≤ f, a → b ∈ L}. But since a ∨ b ≤ ϕ(a) whenever a → b ∈ L, we get that f = W{ϕ(a) | a → b ∈ L, a ≤ f }, which proves the claim. tu Example 6. The set L in Example 3 consists of four implications, and we get {{a}, {b}, {b, c, d}, {a, b, c}} = {ϕbL({a}), ϕbL({b}), ϕbL({b, c, d}), ϕbL({a, b})} as a join-dense set according to Proposition 9. However, {a, b, c} is not joinirreducible, because the supremum of {a} and {b} is, using Proposition 3, ϕbL({a} ∨ {b}) = ϕbL({a} ∪ {b}) = ϕbL({a, b}) = {a, b, c}. 5
Apart from closure and kernel systems, there are many “lattices of sets”, i.e., families of sets which form complete lattices, when ordered by set inclusion. More generally we have studied subsets of arbitrary complete lattices which, endowed with the induced order, are complete lattices themselves. We have shown that each such complete lattice can be described by a set of implications, in a way which is very similar to the standard one in Formal Concept Analysis. The Next closure algorithm can be tweaked to work with this representation, so that we were able to give an algorithm for generating such lattices.
The reader may wonder why we did not use the even more general operator _{b | a ≤ x, a → b ∈ L}, x ∈ L, which also is monotone. But such operators are no longer tensive in general, not even increasing. Actually, it is easy to see that every monotone function ϕ can so be represented (choose L := {a → ϕ(a) | a ∈ L}). Such operators are more difficult to handle, and we see no possibility of using LinClosure here. But the fixed point sets of such functions describe the same as we have treated with tensive functions: all embedded complete lattices.
Much more important is the question if embedded complete lattices have
a natural and useful interpretation. The work of Shmuely [
The author thanks Bogdan Chornomaz for his helpful remarks, and the reviewers for their careful proofreading.