Every Every Concept Concept Lattice Lattice With With Hedges Hedges Is Isomorphic To Some Is Isomorphic To Some ? Generalized Generalized Concept Concept Lattice Lattice ? Stanislav Krajči Stanislav Krajči krajci@science.upjs.sk Institute of Institute of Computer Computer Science, Science, Faculty Faculty of of Science, Science, UPJŠ Košice,UPJ Slovakia krajci@science.upjs.sk Š Košice, Slovakia Abstract. We show the relationship between two different types of com- mon platforms of till known fuzzifications of a concept lattice, namely that the notion of a concept lattice with hedges is a special case of our generalized concept lattice. 1 Introduction There are some approaches to fuzzify (i. e. generalize for fuzzy case too) the classical Ganter-Wille construction of concept lattice. If we omit the (maybe slightly naive) attempt done by Burusco & Fuentes-Gonzalez ([6]), the first ap- proach, which was theoretically and practically well developed, was given by Bělohlávek ([1]) and Pollandt ([11]). It use (L-)fuzzy subsets of objects and (L- )fuzzy subsets of attributes. The another approach, so-called one-sided fuzzy concept lattice was invented independently by Ben Yahia & Jaoua ([5]), by Bělohlávek et al. ([4]) and by the author ([8]). It considers fuzzy subsets of at- tributes but ordinary/classical/crisp subsets of objects (or vice versa). Because there is no inclusion between these two fuzzy approaches the natural asking for some common platform of both had arose. We know about two such generalizations. One of them was shown by Bělohlá- vek et al. ([3] and partially in [2]) and it uses so-called hedges (or truth-stressers) (details below). The second one was given by author ([9]) and its idea is to separate between the ranges of fuzzy sets of objects and fuzzy sets of attributes (again details below). Till now it seemed that these two generalizing approaches are not compatible, but in this paper we try to show that the first is contained in the second. 2 A generalized concept lattice Let us shortly recall a notion of a generalized concept lattice given by the author. All these results are proven in [9] (and/or in [10]). Let P be a poset, C and D be complete lattices. Let • : C × D → P be monotone and left-continuous in both their arguments, i.e. ? Partially supported by grant 1/0385/03 of the Slovak grant agency VEGA. Radim Bělohlávek, Václav Snášel (Eds.): CLA 2005, pp. 1–9, ISBN 80–248–0863–3. 2 Stanislav Krajči 1a) c1 ≤ c2 implies c1 • d ≤ c2 • d for all c1 , c2 ∈ C and d ∈ D. 1b) d1 ≤ d2 implies c • d1 ≤ c • d2 for all c ∈ C and d1 , d2 ∈ D. 2a) If c • d ≤ p holds for d ∈ D, p ∈ P and for all c ∈ X ⊆ C, then sup X • d ≤ p. 2b) If c • d ≤ p holds for c ∈ C, p ∈ P and for all d ∈ Y ⊆ D, then c • sup Y ≤ p. Let A and B be non-empty sets and let R be P -relation on their Cartesian product, i.e. R : A × B → P . Define the following mapping % : B D → A C (by S T we understand the set of all mappings from the set S to the set T ): If g : B → D then %(g) : A → C is defined as follows: %(g)(a) = sup{c ∈ C : (∀b ∈ B)c • g(b) ≤ R(a, b)}. Symmetrically we define the mapping . : A C → B D: If f : A → C then .(f ) : B → D is defined as follows: .(f )(b) = sup{d ∈ D : (∀a ∈ A)f (a) • d ≤ R(a, b)}. Because these two mappings . and % form a Galois connection, it can be repeated a classical construction of concept lattice. The result of this construc- tion is called a generalized concept lattice and the following basic theorem on generalized concept lattice holds (the proofs are in [9] and [10]): Theorem 1. 1) The generalized concept lattice L is a complete lattice in which * !!+ ^ ^ _ hgi , fi i = gi , % . fi i∈I i∈I i∈I and * !! + _ _ ^ hgi , fi i = . % gi , fi . i∈I i∈I i∈I 2) Let moreover P have the least element 0P and 0C • d = 0P and c • 0D = 0P for every c ∈ C and d ∈ D. Then a complete lattice V is isomorphic to L if and only if there are mappings α : A × C → V and β : B × D → V s.t. 1a) α is non-increasing in the second argument. 1b) β is non-decreasing in the second argument. 2a) α[A × C] is infimum-dense. 2b) β[B × D] is supremum-dense. 3) For every a ∈ A, b ∈ B, c ∈ C, d ∈ D α(a, c) ≥ β(b, d) if and only if c • d ≤ R(a, b). This approach is really a generalization of Bělohlávek’s fuzzy concept lattice and of one-sided fuzzy concept lattice (and, of course, of a classical crisp case). Isomorphism of Concept Lattice With Hedges 3 3 A concept lattice with hedges Bělohlávek consider a (complete) residuated lattice L = hL, ∨, ∧, ⊗, →, 0, 1i, where ⊗ and → are connectives on L which form an adjoint pair, i.e. x ⊗ y ≤ z iff x ≤ y → z. ⊗ is isotone in both their arguments, → is antitone in the first argument and isotone in the second one, ⊗ is commutative and x⊗1 = 1⊗x = x. Moreover he has sets X and Y and an incidence relation I : X × Y → L. Then he defines the mappings 0 : LX → LY and 00 : LY → LX as follows: If A ∈ LX and B ∈ LY then ^ A0 (y) = (A(x) → I(x, y)) x∈X and ^ B 00 (x) = (B(y) → I(x, y)). y∈Y The new idea of Bělohlávek (et al.)’s is to modify these definitions in this way: ↑ ^ A (y) = (A(x)∗X → I(x, y)) x∈X and ↓ ^ B (x) = (B(y)∗Y → I(x, y)), y∈Y where ∗X and ∗Y are so-called hedges on L. A hedge is a function ∗ on L which fulfills these properties: 1∗ = 1, a∗ ≤ a, (a → b)∗ ≤ a∗ → b∗ , a∗∗ = a∗ . (Note that the last one can be rewrite in the form ∗◦∗=∗ where ◦ is the composition of mappings.) Moreover they work with the following functions: – For arbitrary A : U → L (U is some universe) define: bAc = {hu, ai ∈ U × L : a ≤ A(u)}. – For arbitrary B ⊆ U × L take the function dBe : U → L defined by: _ dBe(u) = {a ∈ L : hu, ai ∈ B}. 4 Stanislav Krajči – For arbitrary A : U → L and ∗ : L → L define the function A∗ given pointwise by: A∗ (u) = (A(u))∗ . – For arbitrary B ⊆ U × L and ∗ : L → L define: B ∗ = {hx, a∗ i : hx, ai ∈ B}. Then they have taken the set ↑ ↓ B(X ∗X , Y ∗Y , I) = {hA, Bi : A = B, B = A} of all fixpoints of the pair h↑ , ↓ i and showed that this structure is isomorphic to the ordinary concept lattice B(X × ∗X [L], Y × ∗Y [L], Ihf,gi ) where Ag = bdAe↑ c∗X and B f = bdBe↓ c∗Y , and relation Ihf,gi is given by hhx, ai, hy, bii ∈ Ihf,gi iff a ⊗ b ≤ I(x, y). Finally, they have proven this basic theorem for concept lattice with hedges (we present here only its second part): Theorem 2. An arbitrary complete lattice hV, ≤i is isomorphic to the complete lattice B(X ∗X , Y ∗Y , I) iff there are mappings γ : X × ∗X [L] → V and µ : Y × ∗Y [L] → V s. t. 1a) µ[Y × ∗Y [L]] is infimum-dense. 1b) γ[X × ∗X [L]] is supremum-dense. 2) γ(x, a) ≤ µ(y, b) if and only if a ⊗ b ≤ I(x, y). 4 A few observations We add some small, but useful assertions about these notions: Lemma 1. Every hedge is monotonous, i. e. a ≤ b implies a∗ ≤ b∗ . Proof. By properties of a hedge we obtain: a ≤ b iff 1 ⊗ a ≤ b iff 1 ≤ a → b iff 1 = a → b, which implies 1 = (a → b)∗ ≤ a∗ → b∗ , and then a∗ = 1 ⊗ a∗ ≤ b∗ . Lemma 2. For every hedge ∗ if A ⊆ ∗[L] then sup A ∈ ∗[L]. Proof. For every a ∈ A we know a ≤ sup A, and then (from the previous lemma) a = a∗ = (sup A)∗ . It means that (sup A)∗ is an upper bound of A, which implies sup A ≤ (sup A)∗ . But it follows sup A = (sup A)∗ , i. e. sup A ∈ ∗[L]. Isomorphism of Concept Lattice With Hedges 5 Lemma 3. The function b·c is monotonous. Proof. If A1 , A2 : U → L and A1 ≤ A2 , then obviously bA1 c = {hu, ai ∈ U × L : a ≤ A1 (u)} ⊆ {hu, ai ∈ U × L : a ≤ A2 (u)} = bA2 c. Lemma 4. The function d·e is monotonous. W Proof. If B1 ⊆ B2 W⊆ U × L, then for all u ∈ U we have clearly dB1 e(u) = {a ∈ L : hu, ai ∈ B1 } = {a ∈ L : hu, ai ∈ B2 } = dB2 e(u). Lemma 5. For arbitrary A : U → L it is true that dbAce = A. W W Proof. dbAce(u) = {a ∈ L : hu, ai ∈ bAc} = {a ∈ L : a ≤ A(u)} = A(u). 5 Relationship between these two approaches We can see that the basic theorem for concept lattice with hedges and the basic theorem for our generalized concept lattice are very similar. And it is suspicious. So take such special case of our generalized concept lattice given by the following table: general special P L A Y B X C ∗Y [L] D ∗X [L] • ⊗ R:A×B →P I :X ×Y →L Then our definitions can be rewritten in this form: If g : X → ∗X [L] then %(g) : Y → ∗Y [L] is defined as follows: %(g)(y) = sup{c ∈ ∗Y [L] : (∀x ∈ X)c ⊗ g(x) ≤ I(x, y)}, and if f : Y → ∗Y [L] then .(f ) : X → ∗X [L] is defined by: .(f )(x) = sup{d ∈ ∗X [L] : (∀y ∈ Y )f (y) ⊗ d ≤ I(x, y)}. And now we will try to prove that such special case of generalized concept lattice is isomorphic to the lattice from [3]: Theorem 3. The lattices L = L(X (∗X [L]), Y (∗Y [L]), I) and B = B(X×∗X [L], Y × ∗Y [L], Ihf,gi ) are isomorphic and the isomorphisms are Φ(hg, f i) = hbgc, bf ci and Ψ (hS, T i) = hdSe, dT ei, where g : X → ∗X [L], f : Y → ∗Y [L], S ⊆ X × ∗X [L], T ⊆ Y × ∗Y [L]. 6 Stanislav Krajči It is enough to prove the following six claims: Claim 1 If hg, f i ∈ L then Ψ (hg, f i) ∈ B. Proof. Let hg, f i ∈ L, i. e. g = .(f ) and f = %(g), we want to prove bgc = bf cg = bdbf ce↓ c∗ = bf ↓ c∗ (because from the lemma 5 we have dbf ce = f ) and bf c = bgcf = bdbgce↑ c∗ = bg ↑ c∗ (because again dbgce = g), which will mean Φ(hg, f i) = hbgc, bf ci ∈ B, what we want to show. By above definitions we obtain: bf ↓ c∗ = {hx, d∗X i ∈ X × ∗X [L] : hx, di ∈ bf ↓ c}, = {hx, di ∈ X × ∗X [L] : hx, d∗X i ∈ bf ↓ c}, (because ∗X ◦ ∗X = ∗X , we have d∗X = d for all d ∈ ∗X [L]), = {hx, di ∈ X × ∗X [L] : d ≤ Vf ↓ (x)}, = {hx, di ∈ X × ∗X [L] : d ≤ y∈Y (f (y)∗Y → I(x, y))}, = {hx, di ∈ X × ∗X [L] : (∀y ∈ Y )(f (y)∗Y ⊗ d ≤ I(x, y))}, = {hx, di ∈ X ×∗X [L] : (∀y ∈ Y )(f (y)⊗d ≤ I(x, y))} (because ∗Y ◦∗Y = ∗Y , we have c∗Y = c for all c ∈ ∗Y [L], especially f (y) ∈ ∗Y [L]), = {hx, di ∈ X × ∗X [L] : d ≤ sup{e ∈ ∗X [L] : (∀y ∈ Y )f (y) ⊗ e ≤ I(x, y)}}, = {hx, di ∈ X × ∗X [L] : d ≤ .(f )(x)}, = {hx, di ∈ X × ∗X [L] : d ≤ g(x)}, = bgc, So we have bf ↓ c∗ = bgc, and the equality bg ↑ c∗ = bf c can be proven symmetri- cally. Claim 2 If hS, T i ∈ B then Φ(hS, T i) ∈ L. Proof. Let hS, T i ∈ B, i. e. S = T f = bdT e↓ c∗ and T = S g = bdSe↑ c∗ , we want to prove %(dSe) = dT e and .(dT e) = dSe which will mean Ψ (hS, T i) = hdSe, dT ei ∈ L, what we want to show. Firstly we show that for all y ∈ Y we have dT e(y) ∈ ∗Y [L]: dT e(y) ↑ ∗ = dbdSe c e(y), = W{a ∈ L : hy, ai ∈ bdSe↑ c∗ }, W = {a ∈ ∗Y [L] : hy, ai ∈ bdSe↑ c∗ }, ∈ ∗Y [L] (because of lemma 2). Hence by above definitions we obtain for every x ∈ X: .(dT e)(x) = sup{d ∈ ∗X [L] : (∀y ∈ Y )dT e(y) ⊗ d ≤ I(x, y)}, = sup{d ∈ ∗X [L] : (∀y ∈ Y )dT e(y)∗Y ⊗ d ≤ I(x, y)} (because ∗Y ◦ ∗Y = ∗Y , we have c∗Y = c for all c ∈ ∗Y [L], especially for dT e(y) as we have shown above), = sup{d ∈ ∗X [L] : d ≤ y∈Y (dT e(y)∗Y → I(x, y))}, V Isomorphism of Concept Lattice With Hedges 7 = sup{d ∈ ∗X [L] : d ≤ dT e↓ (x)}, = sup{d ∈ ∗X [L] : hx, di ∈ bdT e↓ c}, = sup{d ∈ ∗X [L] : hx, d∗X i ∈ bdT e↓ c∗ }, = sup{d ∈ ∗X [L] : hx, di ∈ bdT e↓ c∗ } (because ∗X ◦ ∗X = ∗X , we have d∗X = d for all d ∈ ∗X [L]), = sup{d ∈ L : hx, di ∈ bdT e↓ c∗ } (the (stronger) condition d ∈ ∗X [L] is covered by the condition hx, di ∈ bdT e↓ c∗ ), =Wsup{d ∈ L : hx, di ∈ S}, = {d ∈ L : hx, di ∈ S}, = dSe(x). So we have .(dT e) = dSe, and the equality %(dSe) = dT e can be proven symmetrically. Claim 3 If hg, f i ∈ L then Φ(Ψ (hg, f i)) = hg, f i. Proof. Φ(Ψ (hg, f i)) = hdbgce, dbf cei = hg, f i because of lemma 5. (You can see that assumption hg, f i ∈ L is only formal, we do not need it.) Claim 4 If hS, T i ∈ B then Ψ (Φ(hS, T i)) = hS, T i. Proof. By definition we obtain Ψ (Φ(hS, T i)) = hbdSec, bdT eci, so we want to prove that bdSec = S and bdT ec = T . For one inclusion we will need the following observation: Because hS, T i ∈ B, we have S = T f = bdT e↓ c∗ , i. e. S = bgc∗ for some g : X → ∗X [L]. Using definitions we obtain: hx, di ∈ bdSec iff d ≤ dSe(x), W iff d ≤ W{e ∈ L : hx, ei ∈ S}, iff d ≤ W{e ∈ L : hx, ei ∈ bgc∗ }, iff d ≤ {e ∈ ∗X [L] : hx, e∗X i ∈ bgc∗ } (because if hx, ei ∈ bgc∗ then e ∈ ∗X ∗X [L] and W e = e ), iff d ≤ W{e ∈ ∗X [L] : hx, ei ∈ bgc}, iff d ≤ {e ∈ ∗X [L] : e ≤ g(x)} = g(x), iff hx, di ∈ bgc and d ∈ ∗X [L], iff hx, d∗X i ∈ bgc∗ and d ∈ ∗X [L], iff hx, di ∈ bgc∗ (because ∗X ◦ ∗X = ∗X , so d = d∗X for all d ∈ ∗X [L]), iff hx, di ∈ S. So we have bdSec = S, and the second equality bdT ec = T can be proven symmetrically. Claim 5 Φ is order-preserving. 8 Stanislav Krajči Proof. Let hg1 , f1 i, hg2 , f2 i ∈ L and hg1 , f1 i ≤ hg2 , f2 i. This inequality means that g1 ≤ g2 and f1 ≥ f2 (pointwise) and by monotonicity of b·c we obtain bg1 c ⊆ bg2 c and bf1 c ⊇ bf2 c, which implies Φ(hg1 , f1 i) = hbg1 c, bf1 ci ≤ hbg2 c, bf2 ci = Φ(hg2 , f2 i). Claim 6 Ψ is order-preserving. Proof. Let hS1 , T1 i, hS2 , T2 i ∈ B and hS1 , T1 i ≤ hS2 , T2 i. This inequality means that S1 ⊆ S2 and T1 ⊇ T2 and by monotonicity of d·e we obtain dS1 e ≤ dS2 e and dT1 e ≥ dT2 e, which implies Ψ (hS1 , T1 i) = hdS1 e, dT1 ei ≤ hdS2 e, dT2 ei = Ψ (hS2 , T2 i). Now we have proven that the lattices B and L are isomorphic. Hence we have this: Corrolary 1 The lattices L(X (∗X [L]), Y (∗Y [L]), I) and B(X ∗X , Y ∗Y , I) are iso- morphic. Or we can say it in another words, that every concept lattice with hedges is isomorphic to some generalized concept lattice. 6 Conclusions In this paper we showed that the notion of a generalized concept lattice defined in [10] contains as a part the notion of a fuzzy concept lattice with hedges. Hence relationships between all classes of concept lattices mentioned in Introduction can be depicted in this diagram: generalized CL L-fuzzy CL with hedge @ @ @ @ @ L-fuzzy CL one-sided fuzzy CL @ @ @ @ @ classical CL Isomorphism of Concept Lattice With Hedges 9 The inverse question arises how big is distinction between these classes, e. g. what additional conditions are needed for a generalized concept lattices to be isomorphic to some fuzzy concept lattice with hedges. Or are these notions the same?. . . References 1. R. Bělohlávek: Concept Lattices and Order in Fuzzy Logic, Annals of Pure and Applied Logic, 128 (2004), 277–298 2. R. Bělohlávek, T. Funioková, V. Vychodil: Galois Connection with Truth Stressers: Foundation for Formal Concept Analysis of Object-Attribute Data with Fuzzy Stressers, Journal of IGPL, accepted 3. R. Bělohlávek, V. Vychodil: Reducing the size of fuzzy concept lattices by hedges, Proceedings of FUZZ-IEEE 2005: The 14th IEEE International Conference on Fuzzy Systems, 2005, pp. 663-668, [IEEE, ISBN 0780391586, ISSN 10987584, Catalog Number: 05CH37680] 4. R. Bělohlávek, V. Sklenář, J. Zacpal: Crisply generated fuzzy concepts: reducing the number of concepts in formal concept analysis, Proc. 5th Int. Conf. on Recent Advances in Soft Computing, RASC 2004, Nottingham, United Kingdom, 16– 18 December, 2004, pp. 63 (extended abstract); pp. 524–529 (full paper on the included CD) [ISBN 1-84233-110-8] 5. S. Ben Yahia, A. Jaoua: Discovering knowledge from fuzzy concept lattice. In: Kandel A., Last M., Bunke H.: Data Mining and Computational Intelligence, 169–190, Physica-Verlag, 2001 6. A. Burusco, R. Fuentes-Gonzalez: The study of L-fuzzy concept lattice, Mathware & Soft Computing 3(1994), 209–218 7. B. Ganter, R. Wille: Formal Concept Analysis, Mathematical Foundation, Springer Verlag 1999, ISBN 3-540-62771-5 8. S. Krajči: Cluster based efficient generation of fuzzy concepts, Neural Network World 13,5 (2003) 521–530 9. S. Krajči: The basic theorem on generalized concept lattice, CLA 2004, Ostrava, proceedings of the 2nd international workshop, eds. V. Snášel, R. Bělohlávek, ISBN 80-248-0597-9, 25–33 10. S. Krajči: A generalized concept lattice, Journal of IGPL, accepted 11. S. Pollandt: Datenanalyse mit Fuzzy-Begriffen, in: G. Stumme, R. Wille: Begrif- fliche Wissensverarbeitung. Methoden und Anwendungen, Springer, Heidelberg 2000, 72–98