On the Isomorphism Problem of Concept Algebras Léonard Kwuida1? and Hajime Machida2 1 Technische Universität Dresden Institut für Algebra D-01062 Dresden, Germany 2 Hitotsubashi University Department of Mathematics 2-1 Naka, Kunitachi, Tokyo 186-8601, Japan Abstract. Weakly dicomplemented lattices are bounded lattices equipped with two unary operations to encode a negation on concepts. They have been introduced to capture the equational theory of concept algebras [12]. They generalize Boolean algebras. Concept algebras are concept lattices, then complete lattices, with a weak negation and a weak opposition. A special case of the representation problem for weakly dicomplemented lattices, posed in [4] is whether complete weakly dicomplemented lat- tices are isomorphic to concept algebras. In this contribution we give a negative answer to this question (Theorem 3). We also provide a new proof of a well known result due to M.H. Stone [8], saying that each Boolean algebra is a field of sets (Corollary 4). 1 Weak dicomplementation. Definition 1. A weakly dicomplemented lattice is a bounded lattice L equipped with two unary operations 4 and 5 called weak complementation and dual weak complementation, and satisfying for all x, y ∈ L the following equations: (1) x44 ≤ x, (1’) x55 ≥ x, (2) x ≤ y =⇒ x4 ≥ y 4 , (2’) x ≤ y =⇒ x5 ≥ y 5 , (3) (x ∧ y) ∨ (x ∧ y 4 ) = x, (3’) (x ∨ y) ∧ (x ∨ y 5 ) = x. We call x4 the weak complement of x and x5 the dual weak complement of x. The pair (x4 , x5 ) is called the weak dicomplement of x and the pair (4 ,5 ) a weak dicomplementation on L. The structure (L, ∧, ∨,4 , 0, 1) is called a weakly complemented lattice and (L, ∧, ∨,5 , 0, 1) a dual weakly complemented lattice. ? was supported by the grant of Prof. Hajime Machida for a stay in Japan at Hitot- subashi University, Kunitachi, Tokyo, Japan during which this paper was discussed. c Radim Belohlavek, Sergei O. Kuznetsov (Eds.): CLA 2008, pp. 217–229, ISBN 978–80–244–2111–7, Palacký University, Olomouc, 2008. 218 Léonard Kwuida, Hajime Machida The following properties are easy to verify: (i) x ∨ x4 = 1, (ii) x ∧ x5 = 0, (iii) 04 = 1 = 05 , (iv) 14 = 0 = 15 , (v) x5 ≤ x4 , (vi) (x ∧ y)4 = x4 ∨ y 4 , (vii) (x ∨ y)5 = x5 ∧ y 5 , (viii) x444 = x4 , (ix) x555 = x5 , and (x) x45 ≤ x44 ≤ x ≤ x55 ≤ x54 . Example 1. (a) The natural examples of weakly dicomplemented lattices are Boolean alge- bras. For (B, ∧, ∨, ¯, 0, 1) a Boolean algebra, (B, ∧, ∨, ¯, ¯, 0, 1) (the comple- mentation is duplicated, i.e. x4 := x̄ =: x5 ) is a weakly dicomplemented lattice. (b) Each bounded lattice can be endowed with a trivial weak dicomplemen- tation by defining (1, 1), (0, 0) and (1, 0) as the dicomplement of 0, 1 and of each x 6∈ {0, 1}, respectively. Definition 2. Let (P, ≤) be a poset and f : P → P be a map. f is a closure operator on P if for all x, y ∈ P , x ≤ f (y) ⇐⇒ f (x) ≤ f (y). This is equivalent to x ≤ f (x), x ≤ y =⇒ f (x) ≤ f (y) and f (f (x)) = f (x). Usually we will write a closure operator on a set X to mean a closure operator on the powerset (P(X), ⊆) of X. Dually, f is a kernel operator on P if for all x, y ∈ P , x ≥ f (y) ⇐⇒ f (x) ≥ f (y). As above, we will say that f is a kernel operator on X to mean a kernel operator on (P(X), ⊆). For a weakly dicomplemented lattice (L, ∧, ∨,4 ,5 , 0, 1), the maps x 7→ x44 and x 7→ x55 are resp. kernel and closure operators on L. If f is a closure operator (resp. a kernel operator) on a lattice L, then f (L) (with the induced order) is a lattice. Recall that for any closure operator h on L we it holds h(h(x)∧h(y)) = h(x)∧h(y) as well as h(h(x)∨h(y)) = h(x∨y), and for any kernel operator k on L it holds k(k(x)∧k(y)) = k(x∧y) and k(k(x)∨k(y)) = k(x)∨k(y). We denote by P d the dual poset of (P, ≤), i.e. P d := (P, ≥). Then f is a kernel operator on P iff f is a closure operator on P d . Proposition 1. Let h be a closure operator and k a kernel operator on a set X. For A ⊆ X define A4h := h(X \ A) and A5k := k(X \ A). (i) (hP(X), ∩, ∨h ,4h , h∅, X), with A ∨h B := h(A ∪ B), is a weakly comple- mented lattice. (i’) (kP(X), ∧k , ∪,5k , ∅, kX), with A ∧k B := k(A ∩ B), is a dual weakly com- plemented lattice. (ii) If hP(X) is isomorphic to kP(Y ), then h and k induce weakly dicomple- mented lattice structures on hP(X) and on kP(Y ) that are extensions of those in (i) and (i0 ) above respectively. Proof. For (i), let h be a closure operator on X; (hP(X), ∩, ∨h , h∅, X) is a bounded lattice. So we should only check the equations (1) − (3) in Definition 1. For x ∈ hP(X), we have x44 = h(X \h(X \x)) ⊆ h(X \(X \x)) = h(x) = x, and (1) is proved. For x1 ≤ x2 in hP(X), we have x1 ⊆ x2 and h(X \x1 ) ⊇ h(X \x2 ), On the Isomorphism Problem of Concept Algebras 219 and (2) is proved. Now we consider x, y ∈ hP(X). Trivially (x∩y)∨h (x∩y 4h ) ≤ x. In addition, (x ∩ y) ∨h (x ∩ y 4h ) = (x ∩ y) ∨h (x ∩ h(X \ y)) = h((x ∩ y) ∪ (x ∩ h(X \ y))) ⊇ h((x ∩ y) ∪ (x ∩ (X \ y))) = h(x) = x. (i0 ) is proved similarly. For (ii) we will extend the structures of (i) and (i0 ) to get weakly dicom- plemented lattices. By (i), (hP(X), ∩, ∨h ,4h , h∅, X) is a weakly complemented lattice. Let ϕ be an isomorphism from hPX to kPX. We define 5ϕ on hP(X) by: x5ϕ := ϕ−1 (ϕ(x)5k ). Then 5ϕ  5k  x5ϕ 5ϕ = ϕ−1 ϕ(x)5k = ϕ−1 ϕ ϕ−1 ϕ(x)5k = ϕ−1 ϕ(x)5k 5k ,  and x5ϕ 5ϕ ≥ ϕ−1 (ϕ(x)) = x. For x ≤ y in hPX we have ϕ(x) ≤ ϕ(y) implying ϕ(x)5k ≥ ϕ(y)5k and x5ϕ = ϕ−1 (ϕ(x)5k ) ≥ ϕ−1 (ϕ(y)5k ) = y 5ϕ . For x, y in hPX, we have (x ∨ y) ∧ (x ∨ y 5ϕ ) = (x ∨ y) ∧ (x ∨ ϕ−1 (ϕ(y)5k )) = ϕ−1 (ϕ(x) ∨ ϕ(y)) ∧ (ϕ(x) ∨ ϕ(y)5k )  = ϕ−1 (ϕ(x)) = x. Therefore (hP(X), ∩, ∨h ,4h ,5ϕ , h∅, X) is a weakly dicomplemented lattice. Sim- ilarly (kP(X), ∧k , ∪,4ϕ ,5k , ∅, kX) with x4ϕ := ϕ(ϕ−1 (x)4h ) is a weakly di- complemented lattice. Proposition 2. Let h be a closure operator on X and k a kernel operator on Y such that hP(X) is isomorphic to kP(Y ). Let ϕ be an isomorphism from hP(X) to kP(Y ). We set L := {(x, y) ∈ hP(X) × kP(Y ) | y = ϕ(x)}. L has a weakly dicomplemented lattice structure induced by h and k. Proof. By Lemma 1 (hP(X), ∩, ∨h ,4h , h∅, X) is a weakly complemented lattice and (kP(X), ∧k , ∪,5k , ∅, kX) a dual weakly complemented lattice. For every y ∈ kP(Y ) there is a unique x ∈ hP(X) such that y = ϕ(x). For (a, b) and (c, d) in L, we have a ≤ c ⇐⇒ b ≤ d. We define a relation ≤ on L by: π1 π2 a ≤ c ⇐⇒ : (a, b) ≤ (c, d) : ⇐⇒ b ≤ d. Then hP(X) ∼ =L∼ = kP(Y ) where πi is the ith projection. Thus (L, ≤) is a bounded lattice. Moreover (a, b) ∧ (c, d) = (a ∩ c, ϕ(a ∩ c)) and (a, b) ∨ (c, d) = (ϕ−1 (b ∪ d), b ∪ d). For (x, y) ∈ L, we define (x, y)4 := (x4h , ϕ(x4h )) and (x, y)5 := (ϕ−1 (y 5k ), y 5k ). We claim that (L, ∧, ∨,4 ,5 , 0, 1) is a weakly dicomplemented lattice. In fact, (x, y)44 = (x4h , ϕ(x4h ))4 = (x4h 4h , ϕ(x4h 4h )) ≤ (x, ϕ(x)) = (x, y). If (x, y) ≤ (z, t) in L, we have x ≤ z and y ≤ t, implying x4h ≥ z 4h and ϕ(x4h ) ≥ ϕ(z 4h ); thus (x, y)4 = (x4h , ϕ(x4h )) ≥ (z 4h , ϕ(z 4h )) = (z, t)4 . 220 Léonard Kwuida, Hajime Machida These prove (1) and (2) of Definition 1. It remains to prove (3). Let (x, y) and (z, t) in L; ((x, y) ∧ (z, t)) ∨ ((x, y) ∧ (z, t)4 ) = (x ∩ z, ϕ(x ∩ z)) ∨ ((x, y) ∧ (z 4h , ϕ(z 4h ))) = (x ∩ z, ϕ(x ∩ z)) ∨ (x ∩ z 4h , ϕ(x ∩ z 4h )) = (ϕ−1 (ϕ(x ∩ z) ∪ ϕ(x ∩ z 4h )), ϕ(x ∩ z) ∪ ϕ(x ∩ z 4h )) = ((x ∩ z) ∨h (x ∩ z 4h ), ϕ((x ∩ z) ∨h (x ∩ z 4h ))) = (x, ϕ(x)). and (3) is proved. The advantage of the weakly dicomplemented lattice L in Lemma 2 is that, in ad- dition to extending the weakly and dual weakly complemented lattice structures induced by h and k, it also keeps track of the closure and kernel systems. Definition 3. Let L be a bounded lattice and x ∈ L. The element x∗ ∈ L (resp. x+ ∈ L) is the pseudocomplement (resp. dual pseudocomplement) of x if x ∧ y = 0 ⇐⇒ y ≤ x∗ (resp. x ∨ y = 1 ⇐⇒ y ≥ x+ ) for all y ∈ L. A double p-algebra is a lattice in which every element has a pseudocomplement and a dual pseudocomplement. Example 2. Boolean algebras are double p-algebras. Finite distributive lattices are double p-algebras. N5 is a double p-algebra that is not distributive. All distributive double p-algebras are weakly dicomplemented lattices. The following result give a class of “more concrete” weakly dicomplemented lattices. Proposition 3. Let L be a finite lattice. Denote by J(L) the set of join irre- ducible elements of L and by M (L) the set of meet irreducible elements of L respectively. Define two unary operations 4 and 5 on L by _ ^ x4 := {a ∈ J(L) | a  x} and x5 := {m ∈ M (L) | m  x}. Then (L, ∧, ∨,4 ,5 , 0, 1) is a weakly dicomplemented lattice. In general, for G ⊇ J(L) and H ⊇ M (L), the operations 4G and 5H defined by _ ^ x4G := {a ∈ G | a  x} and x5H := {m ∈ H | m  x} turn (L, ∧, ∨,4G ,5H , 0, 1) into a weakly dicomplemented lattice. W Proof. Let G ⊇ J(L), b ∈ G and x ∈ L. Then b  W {a ∈ G | a  x} implies b ≤ x; i.e. b  x4G =⇒ b ≤ x. Thus x4G 4G = {b ∈ G | b  x4G } ≤ x and (1) is proved. For x ≤ y we have {a ∈ G | a  x} ⊇ {a ∈ G | a  y} implying x4G ≥ y 4G , and (2) is proved. For (3), it is enough to W prove that for a ∈ J(L), a ≤ x ⇐⇒ a ≤ (x ∧ y) ∨ (x ∧ y 4G ), since J(L) is -dense in L. Let a ≤ x. We have a ≤ y or a ≤ y 4G . Then a ≤ x ∧ y or a ≤ x ∧ y 4G . Thus a ≤ (x ∧ y) ∨ (x ∧ y 4G ). The reverse inequality is obvious. (10 ) − (30 ) are proved similarly. On the Isomorphism Problem of Concept Algebras 221 Example 3 above is a special case of concept algebras. Before we introduce con- cept algebras, let us recall some notions from Formal Concept Analysis (FCA). The reader is refered to [5]. Formal Concept Analysis was born in the eighties from the formalization of the notion of concept [10]. Traditional philosophers considered a concept to be determined by its extent and its intent. The extent consists of all objects belonging to the concept while the intent is the set of all attributes shared by all objects of the concept. In general, it may be difficult to list all objects or attributes of a concept. Therefore a specific context should be fixed to enable formalization. A formal context is a triple (G, M, I) of sets such that I ⊆ G × M . The members of G are called objects and those of M attributes. If (g, m) ∈ I, then the object g is said to have m as an attribute. For subsets A ⊆ G and B ⊆ M , A0 and B 0 are defined by A0 := {m ∈ M | ∀g ∈ A g I m} and B 0 := {g ∈ G | ∀m ∈ B g I m}. A formal concept of the formal context (G, M, I) is a pair (A, B) with A ⊆ G and B ⊆ M such that A0 = B and B 0 = A. The set A is called the extent and B the intent of the concept (A, B). B(G, M, I) denotes the set of all formal concepts of the formal context (G, M, I). For concepts (A, B) and (C, D), (A, B) is called a subconcept of (C, D) provided that A ⊆ C (which is equivalent to D ⊆ B). In this case, (C, D) is a superconcept of (A, B) and we write (A, B) ≤ (C, D). The relation subconcept-superconcept encodes the hierarchy on concepts, namely, that a concept is more general if it contains more objects, and equivalently, if it is determined by less attributes. Theorem 1 ([10]). The concept lattice B(G, M, I) is a complete lattice in which infimum and supremum are given by: !00 ! !00 ! ^ \ [ _ [ \ (At , Bt ) = At , Bt and (At , Bt ) = At , Bt . t∈T t∈T t∈T t∈T t∈T t∈T A complete lattice L is isomorphic to B(G, M, I) iff there are mappings γ̃ : G → L and µ̃ : M → L such that γ̃(G) is supremum-dense, µ̃(M ) is infimum-dense and g I m ⇐⇒ γ̃g ≤ µ̃m for all (g, m) ∈ G × M . (B(G, M, I); ≤) is called the concept lattice of the context (G, M, I). All com- plete lattices are (copies of) concept lattices. We adopt the notations below for g ∈ G and m ∈ M : g 0 := {g}0 , m0 := {m}0 , γg := (g 00 , g 0 ) and µm := (m0 , m00 ). The concept γg is called object concept and µm attribute concept. The sets γG is supremum-dense and µM infimum-dense in B(G, M, I). We usually assume our context clarified, meaning that x0 = y 0 =⇒ x = y for all x, y ∈ G ∪ M . If γg is supremum-irreducible we say that the object g is irreducible. An attribute m is said irreducible if the attribute concept µm is infimum-irreducible. A formal context is called reduced if all its objects and attributes are irreducible. For every finite lattice L there is, up to isomorphism, a unique reduced context 222 Léonard Kwuida, Hajime Machida K(L) := (J(L), M (L), ≤) such that L ∼ = B(K(L)). We call it standard context of L. The meet and join operations in the concept lattice can be used to formalize the conjunction and disjunction on concepts [6]. To formalize a negation two operations are introduced as follow: Definition 4. Let (G, M, I) be a formal context and (A, B) a formal concept. We define 00 0 its weak negation by (A, B)4 := (G \ A) , (G \ A) 0 00  and its weak opposition by (A, B)5 := (M \ B) , (M \ B) . A(K) := B(K); ∧, ∨,4 ,5 , 0, 1 is called the concept algebra of the formal  context K, where ∧ and ∨ denote the meet and the join operations of the concept lattice. These operations satisfy the equations in Definition 1 (cf. [12]). In fact concept algebras are typical examples of weakly dicomplemented lattices. One of the important and still unsolved problems in this topic is to find out the equational theory of concept algebras; that is the set of all equations valid in all concept algebras. Is it finitely generated? i.e. is there a finite set E of equations valid in all concept algebras such that each equation valid in all concept algebras follows from E? We start with the set of equations defining a weakly dicomplemented lattice and have to check whether they are enough to represent the equational theory of concept algebras. This representation problem can be split: strong representation: Describe weakly dicomplemented lattices that are iso- morphic to concept algebras. equational axiomatization: Find a set of equations that generate the equa- tional theory of concept algebras. concrete embedding: Given a weakly dicomplemented lattice L, is there a context K45 (L) such that L can be embedded into the concept algebra of   4 A K5 (L) ? We proved (see [4] or [3]) that finite distributive weakly dicomplemented lattices are isomorphic to concept algebras. However we cannot expect all weakly dicom- plemented lattices to be isomorphic to concept algebras, since concept algebras are first of all complete lattices. In Section 3 we will show that being complete is not enough for weakly dicomplemented lattices to be isomorphic to concept algebras. Before that we show in Section 2 that weakly dicomplemented lattices generalize Boolean algebras. 2 Weakly Dicomplemented Lattices with Negation Example 1 states that duplicating the complementation of a Boolean algebra leads to a weakly dicomplemented lattice. Does the converse hold? The finite case is easily obtained [Corollary 1]. Major parts of this section are taken from [4]. We will also describe weakly dicomplemented lattices whose Boolean part is the intersection of their skeletons (definitions below). On the Isomorphism Problem of Concept Algebras 223 Definition 5. A weakly dicomplemented lattice is said to be with negation if the unary operations coincide, i.e., if x5 = x4 for all x. In this case we set x4 =: x̄ := x5 . Lemma 1. A weakly dicomplemented lattice with negation is uniquely comple- mented. Proof. x44 ≤ x ≤ x55 implies that x = x̄ ¯. Moreover, x ∧ x̄ = 0 and x̄ is a complement of x. If y is another complement of x then x = (x ∧ y) ∨ (x ∧ ȳ) = x ∧ ȳ =⇒ x ≤ ȳ x = (x ∨ y) ∧ (x ∨ ȳ) = x ∨ ȳ =⇒ x ≥ ȳ Then ȳ = x and x̄ = y. L is therefore a uniquely complemented lattice. It can be easily seen that each uniquely complemented atomic lattice is a copy of the power set of the set of its atoms, and therefore distributive. Thus Corollary 1. The finite weakly dicomplemented lattices with negation are ex- actly the finite Boolean algebras. Of course, the natural question will be if the converse of Lemma 1 holds. That is, can any uniquely complemented lattice be endowed with a structure of a weakly dicomplemented lattice with negation? The answer is yes for distributive lattices. If the assertion of Corollary 1 can be extended to lattices in general, the answer will unfortunately be no. In fact R. P. Dilworth proved that each lattice can be embedded into a uniquely complemented lattice [?]. The immediate consequence is the existence of non-distributive uniquely complemented lattices. They are however infinite. If a uniquely complemented lattice could be endowed with a structure of weakly dicomplemented lattice, it would be distributive. This cannot be true for non distributive uniquely complemented lattices. Lemma 2. Each weakly dicomplemented lattice with negation L satisfies the de Morgan laws. Proof. We want to prove that x ∧ y = x̄ ∨ ȳ. (x̄ ∨ ȳ) ∨ (x ∧ y) ≥ x̄ ∨ (x ∧ ȳ) ∨ (x ∧ y) = x̄ ∨ x = 1 and (x̄ ∨ ȳ) ∧ (x ∧ y) ≤ (x̄ ∨ ȳ) ∧ x ∧ (x̄ ∨ y) = x̄ ∧ x = 0. So x̄ ∨ ȳ is a complement of x ∧ y, hence by uniqueness it is equal to x ∧ y. Dually we have x ∨ y = x̄ ∧ ȳ. Now for the distributivity we can show that Lemma 3. x ∧ (y ∨ z) is a complement of (x ∧ y) ∨ (x ∧ z). 224 Léonard Kwuida, Hajime Machida Proof. Since in every lattice the equation x ∧ (y ∨ z) ≥ (x ∧ y) ∨ (x ∧ z) holds, we have that x ∧ (y ∨ z) ≤ (x ∧ y) ∨ (x ∧ z); so we have to show only that x ∧ (y ∨ z) ∨ (x ∧ y) ∨ (x ∧ z) = 1. Using the de Morgan laws and axiom (3) several times we obtain: x ∧ (y ∨ z) ∨ (x ∧ y) ∨ (x ∧ z) = x̄ ∨ (ȳ ∧ z̄) ∨ (x ∧ y) ∨ (x ∧ z) = x̄ ∨ (ȳ ∧ z̄ ∧ x) ∨ (ȳ ∧ z̄ ∧ x̄) ∨ (x ∧ y ∧ z) ∨(x ∧ y ∧ z̄) ∨ (x ∧ z ∧ ȳ) = x̄ ∨ (ȳ ∧ z̄ ∧ x̄) ∨ (x ∧ y ∧ z) ∨ (x ∧ y ∧ z̄) ∨(x ∧ ȳ ∧ z) ∨ (x ∧ ȳ ∧ z̄) = x̄ ∨ (ȳ ∧ z̄ ∧ x̄) ∨ (x ∧ y) ∨ (x ∧ ȳ) = x̄ ∨ (ȳ ∧ z̄ ∧ x̄) ∨ x = 1. Thus x ∧ (y ∨ z) is a complement of (x ∧ y) ∨ (x ∧ z). Since the complement is unique we get the equality x ∧ (y ∨ z) = x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z). Thus weakly dicomplemented lattices generalize Boolean algebras in the follow- ing sense Theorem 2. Boolean algebras with the complementation duplicated3 are weakly dicomplemented lattices. If 4 =5 in a weakly dicomplemented lattice L, then (L, ∧, ∨, ¯, 0, 1), with x̄ := x4 = x5 for all x ∈ L, is a Boolean algebra. As the equality x4 = x5 not always holds, we can look for a maximal subset with this property. Definition 6. For any weakly dicomplemented lattice L, we will call B(L) := {x ∈ L | x4 = x5 } the subset of elements with negation. As in Definition 5 we denote by x̄ the common value of x4 and x5 . We set L4 := {a4 | a ∈ L} = {a ∈ L | a44 = a} and call it the skeleton of L, as well as L5 := {a5 | a ∈ L} = {a ∈ L | a55 = a} and call it the dual skeleton of L. Corollary 2. (B(L), ∧, ∨, ¯, 0, 1) is a Boolean algebra that is a subalgebra of the skeleton and the dual skeleton. Proof. From x4 = x5 we get x44 = x54 and x45 = x55 . Thus x45 = x44 = x = x55 = x54 3 see Example 1 On the Isomorphism Problem of Concept Algebras 225 and B(L) is closed under the operations 4 and 5 . We will prove that B(L) is a subalgebra of L. We consider x and y in B(L). We have (x ∧ y)4 = x4 ∨ y 4 = x5 ∨ y 5 ≤ (x ∧ y)5 ≤ (x ∧ y)4 and (x ∨ y)5 = x5 ∧ y 5 = x4 ∧ y 4 ≥ (x ∨ y)4 ≥ (x ∨ y)5 . Thus x ∧ y and x ∨ y belong to B(L). B(L) is a weakly dicomplemented lattice with negation, and is by Theorem 2, a Boolean algebra. While proving Corollary 2 we show that B(L) is a subalgebra of L. It is the largest Boolean algebra that is a subalgebra of the skeletons and of L. We call it the Boolean part of L. The inclusion B(L) ⊆ L4 ∩ L5 can be strict (see Fig. 1). It would be nice to find under which conditions the Boolean part is the intersection of the skeleton and dual skeleton? Lemma 4. If L is a finite distributive lattice with 5 = ∗ (pseudocomplementa- tion) and 4 = + (dual pseudocomplementation), then B(L) is the set of com- plemented elements of L. Proof. Let L be a finite distributive lattice with 5 = ∗ and 4 = +. We denote by C(L) the set of complemented elements of L. Of course B(L) ⊆ C(L). Let x ∈ C(L). From the distributivity there is a unique elements z ∈ L such that x ∨ z = 1 and x ∧ z = 0. Then z ≤ x5 ≤ x4 ≤ z, and x ∈ B(L). Even in this case, the Boolean part can still be strictly smaller than the inter- section of the skeletons (see Fig. 1 below). Fig. 1. Examples of dicomplementations. For L1 , the elements c, b and a are each im- age (of their image). The operation 4 is the dual of 5 . We have B(L1 ) = {0, 1}, L4 1 = {0, 1, c, d, e, c4 , d4 , e4 }, L5 1 = {0, 1, c, a, b, c 5 , a5 5 , b } and C(L 1 ) = {0, 1, c, a5 }. 4 5 4 5 4 Thus B(L1 ) ( C(L1 ) = L1 ∩ L1 . For L2 , + = and = . L2 = {0, 1, c, c4 }, ∗ L5 5 2 = {0, 1, c, c }, B(L2 ) = {0, 1} = C(L2 ) ( {0, 1, c} = L2 ∩ L2 . 4 5 Lemma 5. B(L) = L4 ∩ L5 iff x44 = x55 =⇒ x45 = x54 . 226 Léonard Kwuida, Hajime Machida Proof. (⇒). Let x ∈ L such that x44 = x55 . Then x ∈ L4 ∩ L5 = B(L) and implies x4 = x5 . Therefore x45 = x55 = x = x44 = x54 . (⇐). Let x ∈ L4 ∩ L5 . Then x44 = x = x55 and implies x4 = x544 ≤ x . Thus x4 = x5 , and x ∈ B(L). 5 3 Strong representation problem We start this section by a negative result, namely by showing that completeness is not enough for weakly dicomplemented lattices to be (copies of ) concept algebras. Theorem 3. There is no formal context whose concept algebra is isomorphic to a complete atomfree Boolean algebra. Proof. Let B be a complete and atomfree Boolean algebra. By Theorem 1, there is a context (G, M, I) such that B(G, M, I) ∼ = B (lattice isomorphism). Without loss of generality, we can assume that (G, M, I) is a subcontext of (B, B, ≤). We claim that there are g, h ∈ G with 0 < h < g < 1. In fact, for an element g ∈ G ⊆ B with W 0 6= g there is a ∈ B such thatW0 < a < g, since B is atomfree. Moreover G is -dense in B and then 0 6= a = {x ∈ G | x ≤ a}, implying that there {x ∈ G | 0 < x ≤ a} = 6 ∅. Thus we can chooseWh ∈ G with 0 < h ≤ a < g. In the concept algebra of (G, M, ≤) we have h4 = {x ∈ G | x  h} ≥ g > h. From h ∨ h4 = 1 we get h4 = 1 6= h0 (the complement of h in B). Theorem 3 says that an atomfree Boolean algebra is not isomorphic to a concept algebra. However it can be embedded into a concept algebra. The cor- responding context is constructed via ultrafilters. A general construction was presented in [4]. Definition 7. A primary filter is a (lattice) filter that contains w or w4 for all w ∈ L. Dually, a primary ideal is an ideal that contains w or w5 for all w ∈ L. Fpr (L) denotes the set of all primary filters and Ipr (L) the set of primary ideals of L. For Boolean algebras, a proper filter F is primary iff it is an ultrafilter, iff it is a prime filter (x ∨ y ∈ F =⇒ x ∈ F or y ∈ F ). The following result, based on Zorn’s lemma provides the sets of K4 5. Theorem 4 (“Prime ideal theorem”). For every filter F and every ideal I such that F ∩ I = ∅ there is a primary filter G containing F and disjoint from I. Dually, for every ideal I and every filter F such that I ∩ F = ∅ there is a primary ideal J containing I and disjoint from F . Corollary 3. If x 6≤ y in L, then there exists a primary filter F containing x and not y. For x ∈ L, we set Fx := {F ∈ Fpr (L) | x ∈ F } and Ix := {I ∈ Ipr (L) | x ∈ I}. On the Isomorphism Problem of Concept Algebras 227 The canonical context of a weakly dicomplemented lattice L is the formal context 4 K5 (L) := (Fpr (L), Ipr (L), 2) with F 2 I : ⇐⇒ F ∩ I 6= ∅. 4 The derivation in K5 (L) yields, Fx0 = Ix and Ix0 = Fx for every x ∈ L. Moreover, the map  4  i : L → B K5 (L) x 7→ (Fx , Ix ) is a bounded lattice embedding with i(x5 ) ≤ i(x)5 ≤ i(x)4 ≤ i(x4 ). If the first and last inequalities above were equalities, we would get a weakly dicom- plemented embedding into the concept algebra of K4 5 (L). This would give a solution to the representation problem of weakly dicomplemented lattices. Theorem 5. If L is a Boolean algebra, then the concept algebra of K4 5 (L) is a complete and atomic Boolean algebra into which L embeds. Proof. If B is a Boolean algebra, then a proper filter F of L is primary iff it is an ultrafilter, and a proper ideal J is primary iff it is maximal. Thus Fpr (L) is the set of ultrafilters of L and Ipr (L) the set of its maximal ideals. In addition, the complement of an ultrafilter is a maximal ideal and vice-versa. For F ∈ Fpr (L), L\F is the only primary ideal that does not intersect F , and for any J ∈ Ipr (L), L\J is the only primary filter that does not intersect J. Thus the context K4 5 (L) is a copy of (Fpr (L), Fpr (L), 6=). The concepts of this context are exactly pairs (A, B) such that A ∪ B = Fpr (L) and A ∩ B = ∅. Thus B(K4 ∼ 5 (L)) = P(Fpr (L)) and each subset A of Fpr (L) is an extent of K4 5 (L). It remains to prove that the lattice embedding  4  i : L → B K5 (L) x 7→ (Fx , Ix ) is also a Boolean algebra embedding. If i(x4 ) 6= i(x)4 then there is F ∈ Fx4 \ 00 (Fpr (L) \ Fx ) = Fx4 \ (Fpr (L) \ Fx ) = ∅, which is a contradiction. Similarly 5 5 i(x ) = i(x)  . Therefore  B embeds into the complete and atomic Boolean 4 algebra A K5 (L) which is a copy of P (Fpr (L)). The above result is a new proof to a well-known result (Corollary 4) due to Marshall Stone [8]. The advantage here is that the proof is very simple and does not require any knowledge from topology. Recall that a field of subsets of a set X is a subalgebra of P(X), .i.e. a family of subsets of X that contains ∅ and X, and that is closed under union, intersection, and complementation. Corollary 4 ([8]). Each Boolean algebra embeds into a field of sets. 228 Léonard Kwuida, Hajime Machida We conclude this section by an example. Consider the Boolean algebra F N of finite and cofinite subsets of N. It is not complete. But P(N) is a complete and atomic Boolean algebra containing F N. By Theorem 5 A(K4 5 (B)) is also a complete and atomic Boolean algebra into which F N embeds. The atoms of F N are {n}, n ∈ N. These generate its principal ultrafilters. F N has exactly one non-principal ultrafilter U (the cofinite subsets). Thus |F N| = |N| + 1 = |N|. We can find a bijection let say f between the atoms of P(N) and the atoms of A(K4 ˆ 4 5 (F N)). f induces an isomorphism f : P(N) → A(K5 (F N)). Is there a universal property for A(K4 4 5 (B)) of Boolean algebras. For example is A(K5 (B)) the smallest complete and atomic Boolean algebra into which B can be embedded? 4 Conclusion Weakly dicomplemented lattices with negation are exactly Boolean algebras (Thm. 2). Even if they are not always isomorphic to concept algebras (Thm. 3), they embed into concept algebras (Thm. 5). Finite distributive weakly dicomple- mented lattices are isomorphic to concept algebras [3]. Extending these results to finite weakly dicomplemented lattices in one sense and to distributive weakly dicomplemented lattices in the other are the next tasks. Finding a kind of uni- versal property to characterize the construction in Thm. 5 is a natural question to be addressed. References 1. Boole., G.: An investigation of the laws of thought on which are founded the mathematical theories of logic and probabilities. Macmillan 1854. Reprinted by Dover Publ. New york (1958). 2. Davey, B. A. Priestley, H. A. : Introduction to lattices and order. Second edition Cambridge (2002). 3. Ganter, B. Kwuida, L.: Finite distributive concept algebras. Order. (2007). 4. Kwuida, L.: Dicomplemented lattices. A contextual generalization of Boolean algebras. Dissertation TU Dresden. Shaker Verlag. (2004). 5. Ganter, B. Wille, R.: Formal Concept Analysis. Mathematical Foundations. Springer (1999). 6. Ganter, B. Wille, R.: Contextual attribute logic. in W. Tepfenhart, W. Cyre (Eds) Conceptual Structures: Standards and Practices. LNAI 1640. Springer, Heidelberg (1999) 337-338. 7. Priestley, H. A.: Representation of distributive lattices by means of ordered Stone spaces. Bull. London Math. Soc. 2 (1970) 186-190. 8. Stone, M. H.: The theory of representations for Boolean algebras. Trans. Amer. Math. Soc. 40 (1936) 37-111. 9. Wansing, H. (Ed.): Negation: a notion in focus. Perspectives in analytical philos- ophy. 7 de Gruyter (1996). 10. Wille, R.: Restructuring lattice theory: an approach based on hierarchies of con- cepts. in I. Rival (Ed.) Ordered Sets. Reidel (1982) 445-470. On the Isomorphism Problem of Concept Algebras 229 11. Wille, R.: Restructuring mathematical logic: an approach based on Peirce’s prag- matism. in Ursini, Aldo (Ed.) Logic and algebra Marcel Dekker. Lect. Notes Pure Appl. Math. 180 (1996) 267-281. 12. Wille, R.: Boolean Concept Logic in B. Ganter & G.W. Mineau (Eds.) ICCS 2000 Conceptual Structures: Logical, Linguistic, and Computational Issues Springer LNAI 1867 (2000) 317-331.