Continuing our categorical study of L-fuzzy extensions of formal concept analysis, we provide a representation theorem for the category of L-Chu correspondences between L-formal contexts and prove that it is equivalent to the category of completely lattice L-ordered sets.
This paper deals with an extremely general form of Formal Concept Analysis (FCA) based on categorical constructs and L-fuzzy sets. FCA has become an extremely useful theoretical and practical tool for formally describing structural and hierarchical properties of data with “object-attribute” character, and this applicability justifies the need of a deeper knowledge of its underlying mechanisms: and one important way to obtain this extra knowledge turns out to be via generalization and abstraction.
Several approaches have been presented for generalizing the framework and
the scope of formal concept analysis and, nowadays, one can see works which
extend the theory by using ideas from fuzzy set theory, rough set theory, or
possibility theory [
Concerning applications of fuzzy formal concept analysis, one can see papers
ranging from ontology merging [
We are concerned in this work with the category L-ChuCors, built on top
of several fuzzy extensions of the classical concept lattice, mainly introduced by
Bˇelohl´avek [
The categorical treatment of morphisms as fundamental structural
properties has been advocated by [
The main result in this work is a constructive proof of the equivalence between the categories of L-formal contexts and L-Chu correspondences and that of completely lattice L-ordered sets and their corresponding morphisms. In order to obtain a reasonably self-contained document, Section 2 introduces the basic definitions concerning the L-fuzzy extension of formal concept analysis, as well as those concerning L-Chu correspondences; then, the categories associated to L-formal contexts and L-CLLOS are defined in Section 3 and, finally, the proof of equivalence is in Section 4. 2 2.1
Definition 1. An algebra hL, ∧, ∨, ⊗, →, 0, 1i is said to be a complete residuated lattice if – hL, ∧, ∨, 0, 1i is a complete lattice with the least element 0 and the greatest element 1, – hL, ⊗, 1i is a commutative monoid, – ⊗ and → are adjoint, i.e. a⊗b ≤ c if and only if a ≤ b → c, for all a, b, c ∈ L, where ≤ is the ordering in the lattice generated from ∧ and ∨.
Definition 2. Let L be a complete residuated lattice, an L-fuzzy context is a triple hB, A, ri consisting of a set of objects B, a set of attributes A and an Lfuzzy binary relation r, i.e. a mapping r : B × A → L, which can be alternatively understood as an L-fuzzy subset of B × A.
Definition 3. Consider an L-fuzzy context hB, A, ri. Mappings ↑ : LB → LA and ↓ : LA → LB can be defined for every f ∈ LB and g ∈ LA as follows: ↑ (f )(a) = ^ f (o) → r(o, a) ↓ (g)(o) = ^ g(a) → r(o, a) o∈B a∈A Definition 4. An L-fuzzy concept is a pair hf, gi such that ↑ (f ) = g and ↓ (g) = f . The first component f is said to be the extent of the concept, whereas the second component g is the intent of the concept.
The set of all L-fuzzy concepts associated to a fuzzy context hB, A, ri will be denoted as L-FCL(B, A, r).
An ordering between L-fuzzy concepts is defined as follows: hf1, g1i ≤ hf2, g2i
if and only if f1 ⊆ f2 (f1(o) ≤ f2(o) for all o ∈ B) if and only if g1 ⊇ g2
(g1(o) ≥ g2(o) for all a ∈ A).
Theorem 1 (See [
Moreover a complete lattice V = hV, ≤i is isomorphic to L-FCL(B, A, r) iff there are mappings γ : B × L → V and µ : A × L → V , such that γ(B × L) is W-dense and µA × L is V-dense in V, and (k ⊗ l) ≤ r(o, a) is equivalent to γ(o, k) ≤ µ (a, l) for all o ∈ B, a ∈ A and k, l ∈ L.
Bˇelohl´avek has extended the fundamental theorem of concept lattices by
Dedekind-MacNeille completion in fuzzy settings by using the notions of
Lequality and L-ordering. All the definitions and related constructions given until
the end of the section are from [
Definition 5. A binary L-relation ≈ on X is called an L-equality if it satisfies 1. (x ≈ x) = 1, (reflexivity), 2. (x ≈ y) = (y ≈ x), (symmetry), 3. (x ≈ y) ⊗ (y ≈ z) ≤ (x ≈ z), (transitivity), 4. (x ≈ y) = 1 implies x = y
L-equality is a natural generalization of the classical (bivalent) notion. Definition 6. An L-ordering (or fuzzy ordering) on a set X endowed with an L-equality relation ≈ is a binary L-relation which is compatible w.r.t. ≈ (i.e. f (x) ⊗ (x ≈ y) ≤ f (y), for all x, y ∈ X) and satisfies 1. x 2. (x 3. (x x = 1, (reflexivity), y) ∧ (y x) ≤ (x ≈ y), (antisymmetry), y) ⊗ (y z) ≤ (x z), (transitivity).
If is an L-order on a set X with an L-equality ≈, we call the pair hhX, ≈i i an L-ordered set.
Clearly, if L = 2, the notion of L-order coincides with the usual notion of (partial) order.
Definition 7. An L-set f ∈ LX is said to be an L-singleton in hX, ≈i if it is compatible w.r.t. ≈ and the following holds: 1. there exists x0 ∈ X with f (x0) = 1 2. f (x) ⊗ f (y) ≤ (x ≈ y), for all x, y ∈ X.
Definition 8. For an L-ordered set hhX, ≈i i and f ∈ LX we define the L-sets inf(f ) and sup(f ) in X by where – L(f )(x) = Vy∈X f (y) → (x – U (f )(x) = Vy∈X f (y) → (y y) x) inf(f ) and sup(f ) are called infimum or supremum, respectively. Definition 9. An L-ordered set hhX, ≈i i is said to be completely lattice L-ordered set if for any f ∈ LX both sup(f ) and inf(f ) are ≈-singletons.
By proving of all the following lemmas some of the properties of residuated
lattices are used. All details could be found in [
^ f1(o) → f2(o) = ^ o∈B a∈A g2(a) → g1(a)
^ f1(o) → f2(o) = ^ o∈B o∈B
f1(o) → ↓ (g2)(o) Definition 10. We define an L-equality ≈ and L-ordering mal concepts L-FCL(C) of L-context C as follows: 1. hf1, g1i hf2, g2i = Vo∈B f1(o) → f2(o) = Va∈A g2(a) → g1(a) 2. hf1, g1i ≈ hf2, g2i = Vo∈B f1(o) ↔ f2(o) = Va∈A g2(a) ↔ g1(a) where k ↔ m is defined as (k → m) ∧ (m → k) for any k, m ∈ L. = ^
o∈B = ^
a∈A = ^ = ^ a∈A a∈A f1(o) → ^
a∈A g2(a) → ^
o∈B g2(a) → ↑ (f1)(a) g2(a) → g1(a) g2(a) → r(o, a) f1(o) → r(o, a)
⊔⊓ on the set of forDefinition 11. Let C = hB, A, ri be an L-fuzzy formal context and γ be an Lset from LL-FCL(C). We define L-sets of objects and attributes SB γ and SA γ, respectively, as follows: 1. (SB γ)(o) = 2. (SA γ)(a) =
_ hf,gi∈L-FCL(C)
_ hf,gi∈L-FCL(C) (γ(hf, gi) ⊗ f (o)), for o ∈ B (γ(hf, gi) ⊗ g(a)), for a ∈ A Theorem 2. Let C = hB, A, ri be an L-context. hhL-FCL(C), ≈i, i is a completely lattice L-ordered set in which infima and suprema can be described as follows: for an L-set γ ∈ LL−FCL(C) we have: 1 inf(γ) = n ↓ [ γ , ↑↓ A [ γ o A 1 sup(γ) = n ↓↑ [ γ , ↑ B [ γ o B
Moreover a completely lattice L-ordered set V = hhV, ≈i, i is isomorphic to hhL-FCL(hB, A, ri), ≈1i, 1i iff there are mappings γ : B × L → V and µ : A×L → V , such that γ(B ×L) is {0, 1}-supremum dense and µ (A×L) is {0, 1}infimum dense in V, and ((k ⊗ l) → r(o, a)) = (γ(o, k) µ (a, l)) for all o ∈ B, a ∈ A and k, l ∈ L. In particular, V is isomorphic to hhL-FCL(V, V, ), ≈1i, 1i. 2.2
L-Chu correspondences Definition 12. Consider two L-fuzzy contexts Ci = hBi, Ai, rii, (i = 1, 2), then the pair ϕ = (ϕL, ϕR) is called a correspondence from C1 to C2 if ϕL and ϕR are L-multifunctions, respectively, from B1 to B2 and from A2 to A1 (that is, ϕL : B1 → LB2 and ϕR : A2 → LA1 ).
The L-correspondence ϕ is said to be a weak L-Chu correspondence if the equality
^ (ϕR(a2)(a1) → r1(o1, a1)) = a1∈A1
^ (ϕL(o1)(o2) → r2(o2, a2)) o2∈B2 (1) holds for all o1 ∈ B1 and a2 ∈ A2.
A weak Chu correspondence ϕ is an L-Chu correspondence if ϕL(o1) is an L-set of objects closed in C2 and ϕR(a2) is an L-set of attributes closed in C1 for all o1 ∈ B1 and a2 ∈ A2. We will denote the set of all L-Chu correspondences from C1 to C2 by L-ChuCors(C1, C2).
Definition 13. Given a mapping ̟ : X → LY , we define ̟+ : LX → LY for all f ∈ LX by ̟+(f )(y) = Wx∈X f (x) ⊗ ̟(x)(y) . 3 Introducing the relevant categories 3.1
The category L-ChuCors – objects L-fuzzy formal contexts – arrows L-Chu correspondences – identity arrow ι : C → C of L-context C = hB, A, ri • ιL(o) =↓↑ (χo), for all o ∈ B • ιR(a) =↑↓ (χa), for all a ∈ A – composition ϕ2 ◦ ϕ1 : C1 → C3 of arrows ϕ1 : C1 → C2, ϕ2 : C2 → C3 (Ci = hBi, Ai, rii, i ∈ {1, 2}) • (ϕ2 ◦ ϕ1)L : B1 → LB3 defined as (ϕ2 ◦ ϕ1)L(o1) = ↓3↑3 ϕ2L+(ϕ1L(o1)) where ϕ2L+(ϕ1L(o1))(o3) =
_ ϕ1L(o1)(o2) ⊗ ϕ2L(o2)(o3) • and (ϕ2◦ϕ1)R : A3 → LA1 defined as (ϕ2◦ϕ1)R(a3) = ↑1↓1 ϕ1R+(ϕ2R(a3)) where ϕ1R+(ϕ2R(a3))(a1) =
_ ϕ2R(a3)(a2) ⊗ ϕ1R(a2)(a1) o2∈B2 a2∈A2
All details about definition of the category L-ChuCors could be found in [
Category L-CLLOS Here we define another category Objects are completely lattice L-ordered sets (in short, L-CLLOS) i.e. our objects will be represented as V = hhV, ≈i, i Arrows are pairs of mappings between two L- CLLOSs i.e. hs, zi between V1 and V2, such that: 1. s : V1 → V2, 2. z : V2 → V1, 3. (s(v1) 2 v2) = (v1 1 z(v2)), for all (v1, v2) ∈ V1 × V2.
Identity arrow of hhV, ≈i, i is a pair of identity morphisms hidV , idV i Composition of arrows is based on composition of mappings: consider two arrows hsi, zii : Vi → Vi+1, where i ∈ {1, 2}. Composition is defined as follows:
hs2, z2i ◦ hs1, z1i = hs2 ◦ s1, z1 ◦ z2i.
Thus, given a pair of two arbitrary elements (v1, v3) ∈ V1 × V3 then: (s2 ◦ s1)(v1) 3 v3 = s2(s1(v1)) 3 v3 = s1(v1) 2 z2(v3) = v1 1 z1(z2(v3)) = v1 1 (z1 ◦ z2)(v3) Associativity of composition follows trivially because of the associativity of composition of mappings between sets.
The categories L-ChuCors and L-CLLOS are equivalent In this section we start to build the equivalence by introducing a functor Γ from L-ChuCors to L-CLLOS in the following way: 1. Γ (C) = hhL-FCL(C), ≈i, i for any L-context C will be its L-concept L
CLLOS. 2. Γ (ϕ) = hϕ∨, ϕ∧i. To any L-Chu correspondence ϕ ∈ L-ChuCors(C1, C2), Γ (ϕ) will be a pair of mappings hϕ∨, ϕ∧i defined as follows: – ϕ∨ hf1, g1i = ↓2↑2 ϕL+(f1) , ↑2 ϕL+(f1) – ϕ∧ hf2, g2i = ↓1 ϕR+(g2) , ↑1↓1 ϕR+(g2) where hfi, gii ∈ L-FCL(Ci) for i ∈ {1, 2}.
Lemma 2. Γ (ϕ) ∈ L-CLLOS(Γ (C1), Γ (C2)) for any ϕ ∈ L-ChuCors(C1, C2). Proof. Consider two arbitrary L-concepts hfi, gii of hhL-FCL(Ci), ≈ii, ii for i ∈ {1, 2}, such that Ci = hBi, Ai, rii. ϕ∨ hf1, g1i
2 hf2, g2i = ↓2↑2 ϕL+(f1) , ↑2 ϕL+(f1)
2 hf2, g2i = ^
_ ιL(b)(o) ⊗ f (b) → r(o, a) o∈B b∈B = ^ ^
o∈B b∈B = ^
o∈B = ^
b∈B = ^ b∈B
ιL(b)(o) ⊗ f (b) → r(o, a) f (b) → ^ ιL(b)(o) → r(o, a)
b∈B f (b) → ↑↓↑ χb (a) f (b) → r(b, a) = ↑ (f )(a) Therefore, we have ι∨(hf, gi) = hf, gi. The proof for ι∧ is similar. ⊔⊓ Lemma 4. Consider arbitrary ϕi ∈ L-ChuCors(Ci, Ci+1) for i ∈ {1, 2} and any element o1 ∈ B1 and g3 ∈ LA3 . Then ↓1 ϕ1R+ ϕ2R+(g3) (o1) = ↓1 ϕ1R+ ↑2↓2 ϕ2R+(g3) (o1).
Proof.
= ^ by applying the same chain of modifications in opposite way we will obtain = ↓1 ϕ1R+ ↑2↓2 ϕ2R+(g3) (o1) ⊔⊓
Proof. Consider ϕi ∈ L-ChuCors(Ci, Ci+1) for i ∈ {1, 2}. Let hfi, gii ∈ L-FCL(Ci) be an arbitrary L-context for all i ∈ {1, 3}. Recall that 1. Γ (ϕ2 ◦ ϕ1) = (ϕ2 ◦ ϕ1)∨, (ϕ2 ◦ ϕ1)∧ 2. Γ (ϕ2) ◦ Γ (ϕ1) = ϕ2∨ ◦ ϕ1∨, ϕ1∧ ◦ ϕ2∧ The proof will be based on equality of corresponding elements of the previous pairs: only one part will be proved, the other one is similar.
(ϕ1∧ ◦ ϕ2∧) hf3, g3i = ϕ1∧ ϕ2∧ hf3, g3i = ↓1 (ϕ1R+(↑2↓2 (ϕ2R+(g3)))), ↑1↓1 (ϕ1R+(↑2↓2 (ϕ2R+(g3))))
by lemma 4 we have = ↓1 (ϕ1R+(ϕ2R+(g3))), ↑1↓1 (ϕ1R+(ϕ2R+(g3))) = ⋆ ↓1 (ϕ1R+(ϕ2R+(g3)))(o1) =
We continue by showing that the previous functor satisfies the conditions to
define a categorical equivalence, characterized by the following result:
Theorem 3 (See [
Let us recall the definition of the notions required by the previous theorem:
1. A functor F : C → D is faithful if for all objects A, B of a category C, the map FA,B : HomC(A, B) → HomD(F (A), F (B)) is injective.
In our cases, for proving fullness and faithfulness of the functor Γ we need to prove surjectivity and injectivity of the mapping
ΓC1,C2 : L-ChuCors(C1, C2) → L-CLLOS(Γ (C1), Γ (C2)) for any two L-contexts C1 and C2. This will be done in the forthcoming lemmas.
Proof. The point of the proof is to show that given any arrow hs, zi from the set L-CLLOS(Γ (C1), Γ (C2)) there exists an L-Chu correspondence ϕhs,zi from the set L-ChuCors(C1, C2), for any two L-contexts Ci = hBi, Ai, rii for i = {1, 2}. Let us define the following mappings: – ϕhs,zi(o1) = Ext s h↓1↑1 (χo1 ), ↑1 (χo1 )i
L – ϕhs,zi(a2) = Int z h↓2 (χa2 ), ↑2↓2 (χa2 )i
R ↑2 ϕhs,zi(o1) (a2) =
L ^ ϕhs,zi(o1)(o2) → r2(o2, a2)
L
Ext(s(h↓1↑1 (χo1 ), ↑1 (χo1 )i))(o2) → ↓2 (χa2 )(o2) ⊔⊓
Proof. Now the point is to prove the injectivity of ΓC1,C2 .
Consider two L-Chu correspondences ϕ1, ϕ2 from L-ChuCors(C1, C2) such that ϕ1 6= ϕ2, and let us fix the pair (o1, a2) ∈ B1 × A2, such that ↑2 ϕ1L(o1) (a2) = ↓1 ϕ1R(a2) (o1) 6= ↑2 ϕ2L(o1) (a2) = ↓1 ϕ2R(a2) (o1)
Let us assume that either ↓1 ϕ1R(a2) (o1) > ↑2 ϕ2L(o1) (a2) or that both values from L are incomparable, that is equivalent to the following: ↓1 ϕ1R(a2) (o1) → ↑2 ϕ2L(o1) (a2) < 1
Now consider the L-concept h↓1 (ϕ1R(a2)), ϕ1R(a2)i and let us compare its images under the mappings ϕ1∨ and ϕ2∨.
↑2 ϕ2L+ ↓1 (ϕ1R(a2)) (a2)
ϕ2L+(↓1 (ϕ1R(a2)))(o2) → r2(o2, a2) = ^ Proposition 2. The functor Γ is an equivalence functor between L-ChuCors and L-CLLOS.
Proof. Fullness and faithfulness of Γ is given by previous lemmas. Essential surjectivity on objects is ensured by the fact that given any object hhV, ≈i, i of L-CLLOS there exists an L-context hV, V, i, such that Γ hV, V, i ∼= hhV, ≈i, i. Hence, we can state that Γ is the functor of equivalence between L-ChuCors and L-CLLOS. ⊔⊓