=Paper=
{{Paper
|id=Vol-2123/paper13
|storemode=property
|title=Order-embedded Complete Lattices
|pdfUrl=https://ceur-ws.org/Vol-2123/paper13.pdf
|volume=Vol-2123
|authors=Bernhard Ganter
|dblpUrl=https://dblp.org/rec/conf/cla/Ganter18
}}
==Order-embedded Complete Lattices==
https://ceur-ws.org/Vol-2123/paper13.pdf
Order-embedded Complete Lattices
Bernhard Ganter
TU Dresden, Germany
Abstract. We study complete lattices which are contained in other com-
plete lattices as suborders, but not necessarily as subsemilattices. We de-
velop a representation of such lattices by means of implications, and show
how to navigate them using a modification of the standard Next clo-
sure algorithm. Our approach is inspired by early work of Shmuely [8]
and Crapo [1].
Keywords. Complete lattice, implication, fixed point.
1 Introduction
The interest in concept lattices [5] has stimulated the creation of algorithms for
generating lattices, and the availability of fast algorithms may conversely have
contributed to the popularity of concept lattices. Moreover, concept lattices have
easy representations either by a binary relation or by a set of implications, both
of which can conveniently be used as input for the algorithms.
Although all complete lattices are isomorphic to concept lattices, they some-
times come in a form for which the above mentioned algorithms are not easy to
apply. There are, for example, many families of sets which form complete lattices
when ordered by the subset relation ⊆, but are neither closure nor kernel sys-
tems. We provide an “implicational” representation for such lattices and modify
one of the standard algorithms accordingly.
Throughout the paper, (L, ≤) will be some abstract complete lattice. The
reader may assume, without much loss of generality, that (L, ≤) is a powerset
lattice (P(M ), ⊆). We use the abstract setting because it is more transparent.
2 Monotone Functions
Definition 1 Let (L, ≤) be a complete lattice. A function ϕ : L → L is mono-
tone1 if x ≤ y always implies ϕ(x) ≤ ϕ(y). A monotone function is called
idempotent if ϕ(x) = ϕ(ϕ(x)) for all x ∈ L,
extensive if x ≤ ϕ(x) for all x ∈ L,
contractive2 if x ≥ ϕ(x) for all x ∈ L,
tensive if ϕ(x) = ϕ(x ∧ ϕ(x)) for all x ∈ L,
increasing3 if ϕ(x) ≤ ϕ(ϕ(x)) for all x ∈ L, and
decreasing if ϕ(x) ≥ ϕ(ϕ(x)) for all x ∈ L. ♦
1
Synonyms are order-preserving and isotone.
2
A synonym is intensive.
3
Following Shmuely [8]. Tarski [9] uses “increasing” in the sense of “order-preserving”.
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, Palacký University Olomouc, 2018.
Copying permitted only for private and academic purposes.
154 Bernhard Ganter
decreasing increasing
idempo-
dually tensive tent tensive
contractive extensive
E3d E2d E2 E3
E1d E1
Fig. 1. The result of an attribute exploration [4] for monotone functions, see Proposi-
tion 1.
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 state-
ments 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 implica-
tions, 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 . t
u
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.
Order-embedded Complete Lattices 155
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 op-
erator on (L, ≤) if it is extensive, and is a kernel operator if contractive.
The set of fixed points of a closure operator is called aVclosure system. It is
well known that the closure systems are precisely the -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 lat-
tice. 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 fixedWpoints of a kernel operator are closed under arbitrary joins and
thus form a -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 order-
embedded 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 V
function ϕ : L → L. We claim that for
V any subfamily S ⊆ F the element ϕ( S)
is the infimum of S in F. V Clearly S ≤ s holds for every s ∈ S. Since ϕ is
monotone,
V we get that ϕ( S) ≤ ϕ(s) = s for all s ∈ S, which shows that
ϕ( S) is a lower bound of S.V But any lower bound b of S must
V satisfy b ≤ s for
all s ∈ S and therefore b ≤ S. If b ∈ F, then b = ϕ(b) ≤ ϕ( 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. t
u
Lemma 1 adds a kind of converse to the celebrated Knaster-Tarski theo-
rem [6,9], which states that the set of fixed points of any monotone function on
a complete lattice is itself a complete lattice:
4
Crapo [1] cites Duffus and Rival [2], while Shmuely [8] cites older notes by Crapo.
156 Bernhard Ganter
Corollary 1. A subset F ⊆ L of a complete lattice (L, ≤), with the induced
order, is a complete lattice if and only if F is the set of fixed points of some
monotone function.
Two details from the proof of Lemma 1 will be used later. We list them as
separate propositions:
Proposition 3. Let ϕ W be an
V idempotent and monotone function on a complete
lattice (L, ≤), and let , 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.
t
u
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. t
u
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)
b ≥ ϕ(x).
b
If ϕ is tensive, then so is ϕ.
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.
Order-embedded Complete Lattices 157
The second claim follows again from Proposition 5, assuming that the func-
tion ϕ is increasing.
b ∧ ϕ(x)) is the least fixed
Finally, assume that ϕ is tensive. By definition, ϕ(x
point of ϕ greater or equal to ϕ(x ∧ ϕ(x)). But when ϕ is tensive, the latter
b ∧ ϕ(x)) = ϕ(x).
equals ϕ(x), and therefore ϕ(x b But since ϕ(x) ≤ ϕ(x),
b we get
b
ϕ(x) b ∧ ϕ(x)) ≤ ϕ(x
= ϕ(x b ∧ ϕ(x))
b ≤ ϕ(x),
b which concludes the proof. t
u
b
Note that the function ϕ, defined in Lemma 2, is a closure operator, and that ϕ
has the same fixed points as ϕ.
Lemma 3. If ϕ is monotone and increasing, then for all x ∈ L
b
ϕ(x) = ϕ(ϕ(x)).
b
Proof. ϕ(x) b
is fixed and therefore closed, and contains ϕ(x), thus ϕ(x) ≥ ϕ(ϕ(x)).
b
It remains to show that ϕ(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 ϕ(x)b (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))). t
u
3 Implications
There is a simple way of constructing such monotone and increasing functions
without reference to an embedded lattice. It relies on implications. An impli-
cation 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 = ϕ. t
u
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.
158 Bernhard Ganter
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 ∅ {a} {b} {c} {a, b} {a, c} {b, c} {a, b, c}
.
ϕL (x) ∅ {a, b} ∅ ∅ {a, b} {a, b} ∅ {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 com-
puted, for example by the LinClosure algorithm (see Algorithm 15 in [4]).
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 (∗)
bL (0) = 1∨2∨3∨. . . = ∞1 . But this is no fixed point, since ϕL (∞1 ) = ∞2 .
yields ϕ
Order-embedded Complete Lattices 159
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,Tc, d}. These
S six sets, ordered
by ⊆, form a complete lattice which is neither a - nor a -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 com-
plete 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,
bL , then let S := {f ∈ F | f ≤ e} be the set of
bL (e) is a fixed point of ϕ
if e = ϕ
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. t
u
As an immediate consequence of Theorem 1 we get
Corollary 3. The subsets of a complete lattice which are, with the induced or-
der, 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.
160 Bernhard Ganter
Proposition 7. If ϕ : L → L is monotone, idempotent, and tensive, then the
set
L := {x ∧ ϕ(x) → ϕ(x) | x ∈ L}
bL = ϕ.
is such that ϕ
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 . t
u
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 The Next Fixed Point Algorithm
Many years ago the author suggested a simple algorithm [3] for finding all closed
sets of a given closure operator ϕ on a (finite, linearly ordered) set G. One starts
with the closure A := ϕ(∅) of the empty set and then repeats the procedure
shown in Figure 2, using the output of each application as the input of the
next one, until it returns ⊥. The algorithm is extremely useful for browsing and
for all g ∈ G in reverse order do
if g ∈ A then A := A \ {g}
else
B := ϕ(A ∪ {g})
if g is the smallest element of B \ A then return B
return ⊥.
Fig. 2. The Next closure algorithm, from [4]
navigating in closure systems. And since it is so simple, many variations and
generalizations have been invented, see [4].
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
Order-embedded Complete Lattices 161
A. The function
f
if x = f
ϕ(x) := 1L if a < x for some a ∈ A
0L 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 previousWoutput
as the next input, until ⊥ is reached. For each set B in this sequence, ϕ( B) is
a fixed point of ϕ, and all fixed points occur exactly once.
for all g ∈ G in reverse order do
if g ∈ A then A := A \ {g}
else W
B := {h ∈ G | h ≤ ϕ( (A ∪ {g}))}
if g is the smallest element of B \ A then return B
return ⊥.
Fig. 3. The Next fixed point algorithm
Proof. Each fixed point f of ϕ is uniquely determined by its projection
Π(f ) := {g ∈ G | g ≤ f }
to the join-dense
W set G, because it can be obtained as theWjoin of these elements:
f = ϕ( (Π(f ))) (recall from Proposition 3 that S 7→ ϕ( S) is the join opera-
tion in the fixed point lattice).
W These projection sets form a closure system on
G, for which F 7→ Π(ϕ( F )) is the closure operator. t
u
6
For example, the Dedekind numbers in case that L is a powerset lattice.
162 Bernhard Ganter
1 2 3 4 2 3 4
a × × c d
b × × ×
c × 1
d × a b
Fig. 4. A formal context and its concept lattice. Of its 66 embedded complete lattices,
20 are complete sublattices.
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 [5]. They are in 1-1-correspondence with the complete sublattices
of the concept lattice. The formal context has 20 closed relations, 18 of which
are shown in Figure 5. The two missing ones are the empty relation and the
full incidence of the formal context itself. Note that these relations (including
×
× × × ××× ××× ×××
1 2 3 4 5 6
× ×
× ×
× × × × ××
××× ××× ××× ××× ×××
7 8 9 10 11 12
× × ×
× × ×
×× ×× ×× ×× ×× ××
× × × ××× ××× ×××
13 14 15 16 17 18
× ×
× ×
Fig. 5. The non-trivial closed relations of the formal context in Figure 4
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.
Order-embedded Complete Lattices 163
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 ex-
actly one nontrivial element. These are the join-irreducible closed relations. To-
gether, 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
bL for
be closed under join and meet. So ϕ := ϕ
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 }. TheW largest element of G is R1 , which
is not in A, so B := {h ∈ G | h W ≤ ϕ( (A ∪ {RS 1 }))} must be computed.
A
W ∪ {R 1 } = {R 1 , R2 }, and the join is the union of relations. We obtain
(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.
bL for some set L of implications. Then the set
Proposition 9. Let ϕ := ϕ
{ϕ(a) | a → b ∈ L}
is join-dense in the lattice of fixed points of ϕ.
bL by definition also is a fixed point of ϕL . So if
Proof. Any fixed point of ϕ
bL (f ) = f then
ϕ
_
f = ϕL (f ) = {a ∨ b | a ≤ f, a → b ∈ L}.
164 Bernhard Ganter
W
But since a ∨ b ≤ ϕ(a) whenever a → b ∈ L, we get that f = {ϕ(a) | a → b ∈
L, a ≤ f }, which proves the claim. t
u
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 join-
irreducible, because the supremum of {a} and {b} is, using Proposition 3,
bL ({a} ∨ {b}) = ϕ
ϕ bL ({a} ∪ {b}) = ϕ
bL ({a, b}) = {a, b, c}.
5 Discussion
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
_
x 7→ {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 [8] gives interesting
hints. Her u−v-connections generalize Galois connections and are closely related
to what we construct. One might hope that these can be derived from formal
contexts with additional, meaningful structure.
Acknowledgements
The author thanks Bogdan Chornomaz for his helpful remarks, and the reviewers
for their careful proofreading.
Order-embedded Complete Lattices 165
References
1. Crapo, H.: Ordered sets: retracts and connections. Journal of Pure and Applied
Algebra 23(1), 13–28 (1982)
2. Duffus, D., Rival, I.: Retracts of partially ordered sets. Journal of the Australian
Mathematical Society 27(4), 495–506 (1979)
3. Ganter, B.: Two basic algorithms in concept analysis. FB4–Preprint 831, TH Darm-
stadt (1984), reprinted in [7]
4. Ganter, B., Obiedkov, S.: Conceptual exploration. Springer (2016)
5. Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations.
Springer (1998)
6. Knaster, B.: Un théorème sur les fonctions d’ensembles. Ann. Soc. Polon. Math. 6,
133–134 (1928)
7. Kwuida, L., Sertkaya, B. (eds.): Formal Concept Analysis. Proceedings ICFCA 2010,
Lecture Notes in Computer Science, vol. 5986. Springer (2010)
8. Shmuely, Z.: Increasing and decreasing operators on complete lattices. Journal of
Combinatorial Theory, Series A 21(3), 369–383 (1976)
9. Tarski, A.: A lattice-theoretical fixpoint theorem and its applications. Pacific J.
Math. 5(2), 285–309 (1955)