=Paper=
{{Paper
|id=None
|storemode=property
|title=Block Relations in Fuzzy Setting
|pdfUrl=https://ceur-ws.org/Vol-959/paper8.pdf
|volume=Vol-959
|dblpUrl=https://dblp.org/rec/conf/cla/KonecnyK11
}}
==Block Relations in Fuzzy Setting==
https://ceur-ws.org/Vol-959/paper8.pdf
Block relations in fuzzy setting?
Jan Konecny, Michal Krupka
Department of Computer Science
Palacký University in Olomouc
17. listopadu 12, CZ-77146 Olomouc
Czech Republic
jan.konecny@upol.cz, michal.krupka@upol.cz
Abstract. One of the main problems in FCA (especially in fuzzy setting) is to
reduce a concept lattice to appropriate size to make it graspable and understand-
able. We generalize known results on the correspondence of block relations of
formal contexts and complete tolerances on concept lattices to fuzzy setting. Us-
ing an illustrative example we show that the results can be used for reduction of
fuzzy concept lattices.
Keywords: Fuzzy concept lattice, Tolerance, Block relation, Factorization
1 Introduction
The problem of the size of concept lattices is recognized as one of the most important
problems of Formal Concept Analysis (FCA). The main aim of this paper is to describe
approximation of formal concepts by fuzzy tolerances in fuzzy setting.
In [3, 2], a method of factorization of fuzzy concept lattices is presented. A similar-
ity threshold a is supplied and the method outputs a factor lattice instead of the whole
concept lattice which might be large. The elements of the factor lattice are maximal
blocks of concepts from the whole concept lattice which are pairwise similar to degree
at least a. We generalize the results to a more general family of similarities (complete
fuzzy tolerances) than those induced by a single threshold. We also show that the factor
lattice can be computed from a special kind of superrelations of the incidence relation,
called fuzzy block relations; and the relationship between complete fuzzy tolerances
and fuzzy block relations. That way we generalize a Wille’s results on (crisp) toler-
ances and block relations in [17] (see also [7]).
In [13], Meschke proposed a method of approximation of (crisp) concepts by toler-
ances and block relations. We use some of his ideas (namely the selection of important
objects and attributes) in an illustrative example at the end of this paper.
The organization of the paper is as follows. In Section 2 we recall the fundamental
notions and results on the basic fuzzy structures used in the paper. Section 3 is devoted
to study of fuzzy tolerance relations: we define complete tolerance relations on com-
pletely lattice ordered fuzzy sets and show fundamental properties of the corresponding
factor sets. In Section 4 we describe fuzzy block relations and prove the main result
? Supported by grant no. P103/10/1056 of the Czech Science Foundation.
of the paper: the correspondence between fuzzy block relations and factor structures of
concept lattices. Section 5 contains an illustrative example.
Due to space limitations, we abbreviate, resp. omit, some proofs.
2 Preliminaries
We recall basic notions and facts of residuated lattices, fuzzy sets and fuzzy relations,
fuzzy Galois connections and fuzzy concept lattices.
2.1 Residuated lattices and fuzzy sets
We use complete residuated lattices as basic structures of truth degrees. A complete
residuated lattice [3, 9, 16] is a structure L = hL, ∧, ∨, ⊗, →, 0, 1i such that
(i) hL, ∧, ∨, 0, 1i is a complete lattice, i.e., a partially ordered set in which arbitrary
infima and suprema exist;
(ii) hL, ⊗, 1i is a commutative monoid, i.e., ⊗ is a binary operation which is commuta-
tive, associative, and a ⊗ 1 = a for each a ∈ L;
(iii) ⊗ and → satisfy adjointness, i.e., a ⊗ b ≤ c iff a ≤ b → c.
0 and 1 denote the least and greatest elements. The partial order of L is denoted by ≤.
Throughout the paper, L denotes an arbitrary complete residuated lattice.
Elements a of L are called truth degrees. ⊗ and → (truth functions of) “fuzzy con-
junction” and “fuzzy implication”.
Common examples of complete residuated lattices include those defined on a unit
interval, (i.e., L = [0, 1]) or on a finite chain in the unit interval, e.g. L = {0, 1n , . . . , n−1
n , 1},
∧ and ∨ being minimum and maximum, ⊗ being a left-continuous t-norm with the cor-
responding →.
The three most important pairs of adjoint operations on the unit interval are
a ⊗ b = max(a + b − 1, 0)
Łukasiewicz:
a → b = min(1 − a + b, 1)
a ⊗ b = min(a,
b)
Gödel: 1a≤b
a→b=
b otherwise
a⊗b = a·b
Goguen (product): 1 a≤b
a→b= b
a otherwise
An L-set (or fuzzy set) A in a universe set X is a mapping assigning to each x ∈ X
some truth degree A(x) ∈ L where L is the support of a complete residuated lattice. The
set of all L-sets in a universe X is denoted LX .
The operations with L-sets are defined componentwise. For instance, the intersec-
tion of L-sets A, B ∈ LX is an L-set A ∩ B in X such that (A ∩ B)(x) = A(x) ∧ B(x) for
each x ∈ X, etc. An L-set A ∈ LX is also denoted {A(x)/x | x ∈ X}. If for all y ∈ X distinct
from x1 , x2 , . . . , xn we have A(y) = 0, we also write {A(x1 )/x1 , A(x2 )/x1 , . . . , A(xn )/xn }.
Binary L-relations (binary fuzzy relations) between X and Y can be thought of as
L-sets in the universe X ×Y . That is, a binary L-relation I ∈ LX×Y between a set X and
a set Y is a mapping assigning to each x ∈ X and each y ∈ Y a truth degree I(x, y) ∈ L (a
degree to which x and y are related by I). An L-set A ∈ LX is called crisp if A(x) ∈ {0, 1}
for each x ∈ X. Crisp L-sets can be identified with ordinary sets. For a crisp A, we also
write x ∈ A for A(x) = 1 and x 6∈ A for A(x) = 0. An L-set A ∈ LX is called empty
(denoted by 0)/ if A(x) = 0 for each x ∈ X. For a ∈ L and A ∈ LX , a ⊗ A ∈ LX and
X
a → A ∈ L are defined by
(a ⊗ A)(x) = a ⊗ A(x) and (a → A)(x) = a → A(x).
For an L-set A ∈ LX and a ∈ L, the a-cut of A is a crisp subset a A ⊆ X such that
x ∈ a A iff a ≤ A(x). This definition applies also to binary L-relations, whose a-cuts are
interpreted as classical (crisp) binary relations.
For universe X we define L-relation graded subsethood LX × LX → L by:
^
S(A, B) = A(x) → B(x) (1)
x∈X
Graded subsethood generalizes the classical subsethood relation ⊆; indeed, in the crisp
case (i.e. L = {0, 1}) (1) becomes S(A, B) = 1 iff ∀x ∈ X : x ∈ A implies y ∈ B. Note
that unlike ⊆, S is a binary L-relation on LX . Described verbally, S(A, B) represents a
degree to which A is a subset of B. In particular, we write A ⊆ B iff S(A, B) = 1. As a
consequence, we have A ⊆ B iff A(x) ≤ B(x) for each x ∈ X.
Further we set
A ≈X B = S(A, B) ∧ S(B, A). (2)
The value A ≈X B is interpreted as the degree to which the sets A and B are similar.
A binary L-relation R on a set X is called reflexive if R(x, x) = 1 for any x ∈ X, sym-
metric if R(x, y) = R(y, x) for any x, y ∈ X, and transitive if R(x, y) ⊗ R(y, z) ≤ R(x, z) for
any x, y, z ∈ X. R is called an L-tolerance, if it is reflexive and symmetric, L-equivalence
if it is reflexive, symmetric and transitive. If R is an L-equivalence such that for any
x, y ∈ X from R(x, y) = 1 it follows x = y, then R is called an L-equality on X. L-
equalities are often denoted by ≈. The similarity ≈X of L-sets (2) is an L-equality on
LX .
Let ∼ be an L-equivalence on X, A ∈ LX an L-set. We say that A is compatible with
∼ (or extensional with respect to ∼) if the following condition holds for any x, x0 ∈ X:
A(x) ⊗ (x ∼ x0 ) ≤ A(x0 ).
For each A ∈ LX there exists a minimal (with respect to inclusion of L-sets) L-set
C≈ (A) ∈ LX , compatible with ∼, and such that A ⊆ C∼ (A). It holds
A(x0 ) ⊗ (x0 ∼ x).
_
C∼ (A)(x) = (3)
x0 ∈X
We say that a binary L-relation R on X is compatible with ∼ if for each x, x0 , y, y0 ∈ X,
R(x, y) ⊗ (x ∼ x0 ) ⊗ (y ∼ y0 ) ≤ R(x0 , y0 ).
For a mapping f : X → Y , where Y is endowed with an L-equality ≈, and L-set
A ∈ LX we define the image of A with respect to f as an L-set f (A) ∈ LY satisfying
_
f (A)(y) = A(x) ⊗ ( f (x) ≈ y).
x∈X
f (A) is compatible with ≈ and f (A) = C≈ (B), where B is is an L-set in Y given by
W
B(y) = x∈ f −1 ({y}) A(x).
In the following we use well-known properties of residuated lattices and fuzzy struc-
tures which can be found e.g. in [3, 9].
2.2 L-ordered sets
In this section, we recall basic definitions and results of the theory of L-ordered sets.
Basic references are [1, 3] and the references therein.
An L-order on a set U with an L-equality relation ≈ is a binary L-relation on U
which is compatible with ≈, reflexive, transitive and satisfies (u v) ∧ (v u) ≤ u ≈ v
for any u, v ∈ U (antisymmetry). The tuple U = hhU, ≈i, i is called an L-ordered set.
An immediate consequence of the definition is that for any u, v ∈ U it holds
u ≈ v = (u v) ∧ (v u). (4)
If U = hhU, ≈i, i is an L-ordered set, then the tuple hU, 1 i, where 1 is the 1-
cut of , is Va (partially) ordered set. We sometimes write ≤ instead of 1 and use the
symbols ∧, resp. ∨, for denoting infima resp. suprema in hU, 1 i.
W
For two L-ordered sets U = hhU, ≈U i, U i and V = hhV, ≈V i, V i, a mapping f :
U → V is called an isomorphism of U and V, if it is a bijection and (u1 U u2 ) =
( f (u1 ) V f (u2 )) for any u1 , u2 ∈ V . U and V are then called isomorphic.
For an L-ordered set U and an L-set V ∈ LU we define L-sets U V , L V ∈ LU by
L V (u) = U V (u) =
^ ^
V (v) → (u v), V (v) → (v u).
v∈U v∈U
Using basic rules of fuzzy logic, L V (resp. U V ) can be interpreted as the set of ele-
ments which are smaller (resp. greater) than or equal to elements of V . L V (resp. U V )
is called the lower cone (resp. the upper cone) of U.
For any L-set V ∈ LU there exists at most one element u ∈ U such that L V (u) ∧
U (L V )(u) = 1 (resp. U V ∧L (U V )(u) = 1) [1, 3]. If there is such an element, we call
it the infimum of V (resp. the supremum of V ) and denote infV (resp. supV ); otherwise
we say, that the infimum (resp. supremum) does not exist.
If u, v ∈ U, v ≤ u, then the L-set [v, u] = U {v} ∩ L {u} is called an interval in U. It
holds inf[v, u] = v, sup[v, u] = u.
An L-ordered set U is called completely lattice L-ordered, if for each V ∈ LU , both
infV and supV exist.
Let U be an L-ordered set. For a ∈ L and u ∈ U we set a → u = inf{a/u} and
a ⊗ u = sup{a/u}. a → u is called the a-shift of u, a ⊗ u is called the a-multiple of u.
U is called shift complete (resp. multiple complete) if a → u (resp. a ⊗ u) exists for any
a ∈ L, u ∈ U.
The notions of shift and multiple coincide with the notions of cotensor and tensor
[10, 15, 18] and shift-complete resp. multiple-complete L-ordered sets are cotensored
resp. tensored Ω -categories from [15, 18]. In this paper, we use basic properties of shifts
and multiples, which can be found in these papers and also in [12]. We summarize some
of them below.
For any u, v ∈ U and a ∈ L it holds v = a → u iff for each w ∈ U,
(w v) = a → (w u). (5)
Similarly, v = a ⊗ u iff for each w ∈ U,
(v w) = a → (u w). (6)
Shifts and multiples satisfy the following adjointness condition: If a → v and a ⊗ u
both exist then (u (a → v)) = ((a ⊗ u) v).
The following theorem has been proved in [18] (Propositions 3.12, 3.13) and shows
how shifts and multiples can be efficiently used for proving that an L-ordered set is
completely lattice L-ordered.
Theorem 1. V is a completely lattice L-ordered set iff V is shift complete and multiple
complete and hV, 1 i is a complete lattice.
2.3 Isotone L-Galois connections
We introduce the notion of isotone L-Galois connections. For details, see [8].
An isotone L-Galois connection between L-ordered sets U and V is a pair h f , gi,
where f : U → V , g : V → U are mappings such that for each u ∈ U, v ∈ V it holds
( f (u) v) = (u g(v)). (7)
A pair hu, vi, where u ∈ U and v ∈ V , is called a fixpoint of h f , gi if f (u) = v and
g(v) = u. More generally, the degree to which hu, vi is a fixpoint of h f , gi is defined by
Fixh f ,gi (hu, vi) = ( f (u) ≈ v) ∧ (g(v) ≈ u). (8)
Fixh f ,gi is an L-set in U ×V and is called the L-set of fixpoints of h f , gi.
Theorem 2 (basic properties of isotone L-Galois connections). Let h f , gi be an iso-
tone L-Galois connection between L-ordered sets U and V. Then
(a) u ≤ g( f (u)) for each u ∈ U, f (g(v)) ≤ v for each v ∈ V .
(b) f and g are increasing: (u1 u2 ) ≤ ( f (u1 ) f (u2 )) and (v1 v2 ) ≤ (g(v1 )
g(v2 )).
(c) f (g( f (u))) = f (u), g( f (g(v))) = g(v).
(d) If U 0 ∈ LU then f (infU 0 ) ≤ inf f (U 0 ) and f (supU 0 ) ≥ sup f (U 0 ). If V 0 ∈ LV then
g(infV 0 ) ≤ inf g(V 0 ) and g(supV 0 ) ≥ sup g(V 0 ).
(e) If U and V are completely lattice L-ordered sets and K ∈ LU×V , then
S(K, Fixh f ,gi ) ≤ Fixh f ,gi (hinf prU (K), f (g(inf prV (K)))i), (9)
S(K, Fixh f ,gi ) ≤ Fixh f ,gi (hg( f (sup prU (K))), sup prV (K)i), (10)
where prU : U ×V → U and prV : U ×V → V are Cartesian projections.
Proof. Omitted. Some of the properties are proved in [8].
For an L-ordered set U, an isotone L-Galois connection h f , gi between U and U is
called an inflationary Galois connection on U if f is deflationary and g inflationary:
f (u) ≤ u and g(u) ≥ u (11)
for each u ∈ U. Notice that if one of the conditions (11) holds true, then the second one
follows from (7).
2.4 Composition Operators and Concept Lattices Associated to I
We use three relational composition operators, ◦, /, and .. The composition operators
are defined by
(A ◦ B)(x, y) = z∈Z A(x, z) ⊗ B(z, y),
W
(12)
z∈Z A(x, z) → B(z, y),
V
(A / B)(x, y) = (13)
z∈Z B(z, y) → A(x, z).
V
(A . B)(x, y) = (14)
Note that these operators were extensively studied by Bandler and Kohout, see e.g.
[11] to which we refer for an overview of knowledge processing applications. One may
easily see that . can be defined in terms of / and vice versa. They have natural verbal
descriptions. For instance, (A ◦ B)(x, y) is the truth degree of the proposition “there is
a factor z such that z applies to the object x and the attribute y is a manifestation of z”;
(A / B)(x, y) is the truth degree of “for every factor z, if z applies to the object x then the
attribute y is a manifestation of z”. Note also that for L = {0, 1}, A ◦ B coincides with
the well-known composition of binary relations.
A formal L-context (or just context) is a triple hX,Y, Ii where X and Y are sets whose
elements are called objects and attributes, respectively and I is an L-relation between
X and Y . Consider the following pairs of operators between LX and LY induced by an
L-relation I ∈ LX×Y :
A↑ (y) = x∈X A(x) → I(x, y), B↓ (x) = y∈Y B(y) → I(x, y),
V V
(15)
∩ ∪
x∈X A(x) ⊗ I(x, y), y∈Y I(x, y) → B(y),
W V
A (y) = B (x) = (16)
∧ ∨
x∈X I(x, y) → A(x), y∈Y B(y) ⊗ I(x, y),
V W
A (y) = B (x) = (17)
for A ∈ LX , B ∈ LY . We call (15) antitone concept-forming operators and (16), (17)
isotone concept-forming operators (these are less common if FCA). Furthemore, denote
the set of fixpoints of h↑ , ↓ i by B(X ↑ ,Y ↓ , I). We have
B(X ↑ ,Y ↓ , I) = {hA, Bi | A↑ = B, B↓ = A},
B(X ↑ ,Y ↓ , I) is a completely lattice L-ordered set with the L-equality ≈ and L-order
defined by
hA1 , B1 i ≈ hA2 , B2 i = (A1 ≈X A2 ) (= B1 ≈Y B2 ), (18)
hA1 , B1 i hA2 , B2 i = S(A1 , A2 ) (= S(B2 , B1 )), (19)
and is called the L-concept lattice associated to I. Its elements are called formal L-
concepts. L-concept lattices are the fundamental structures of formal concept analysis
in fuzzy setting [7, 3]. For a formal L-concept hA, Bi, A and B are called the extent and
the intent and they represent the collection of objects and attributes to which the formal
concept applies. The sets of all extents and intents of the respective concept lattices are
denoted by Ext(X ↑ ,Y ↓ , I) and Int(X ↑ ,Y ↓ , I), respectively. It may be shown that
Ext(X ↑ ,Y ↓ , I) = {A ∈ LX | A = A↑↓ },
Int(X ↑ ,Y ↓ , I) = {B ∈ LY | B = B↓↑ }.
The above-defined operators and their sets of fixpoints have been extensively studied,
see e.g. [1, 3, 8, 14].
Example 1. Let L be the 6-element Łukasiewicz chain (i.e., L = {0, 0.2, 0.4, 0.6, 0.8, 1})
and hX,Y, Ii be a formal L-context, where X = {BV, LH, MD, TSS}, Y = {c1, c2, c3, c4,
c5}, and I is depicted in Fig. 1. Elements of X are four selected movies by director David
Lynch, elements of Y are five film critics and values of I are ratings the critics assigned
to the movies, taken from www.metacritic.com and rescaled to the six-element scale.
The context is our central example in this paper and we describe it deeper and work with
it in Section 5. For now, we use it just to give an example of an L-concept lattice.
Note that our data are suitable for interpreting by means of fuzzy logic. A movie
rating (usually given by number of “stars” or by a percentage) can be interpreted as an
answer to the question: “Do you like this movie?”, given in degrees. In most cases, it is
not possible to answer the above question with simple “Yes” or “No”, and, in the same
time, there are no doubts about the answer (especially, if given by a film critic).
c1 c2 c3 c4 c5
BV 0.4 0.4 0.2 0.4 0.6
LH 0.8 0.8 0.8 1 1
MD 0.8 0.4 1 0.8 1
TSS 0.4 0.4 0.8 0.6 0.4
Fig. 1. Formal context of movies (“Blue Velvet” (BV), “Lost Highway” (LH), ”Mulhol-
land Drive” (MD), and “The Straight Story” (TSS)), reviewers (David Sterritt (c1), Desson
Thomson (c2), Jonathan Rosenbaum (c3), Owen Gleiberman (c4) and Roger Ebert (c5)) and
their ratings on the 6-element Łukasievicz chain L = {0, 0.2, 0.4, 0.6, 0.8, 1}. Data taken from
www.metacritic.com on March 20, 2011.
The L-concept lattice B(X ↑ ,Y ↓ , I) is depicted in Fig. 2. When displaying L-concept
lattices, we use labeled Hasse diagrams to include all the information on extents and
intents. For any x ∈ X, y ∈ Y and formal L-concept hA, Bi we have A(x) ≥ a and B(y) ≥ b
if and only if there is a formal concept hA1 , B1 i ≤ hA, Bi, labeled by a/x and a formal
concept hA2 , B2 i ≥ hA, Bi, labeled by b/y. We use labels x resp. y instead of 1/x resp.
1/y and omit redundant labels (i.e., if a concept has both the labels a/x and b/x then
we keep only that with the greater degree; dually for attributes). The whole structure
of L-ordered set on B(X ↑ ,Y ↓ , I) can be determined from the labeled diagram using the
results from [1] (see also [3]).
0.4/c1, 0.4/c2, 0.2/c3, 0.4/c4, 0.4/c5
BV, 0.6/c5 0.4/c3, 0.6/c4
0.6/c1 0.6/c3
0.6/c2 0.8/c5 0.8/c4 TSS, 0.8/c3
0.8/BV 0.8/c1
c3
0.8/c2 c4 0.8/TSS
c5
0.6/TSS
0.6/BV
LH c1 MD
0.8/MD
0.4/BV, c2
0.6/MD
0.2/BV, 0.8/LH, 0.4/MD, 0.4/TSS,
Fig. 2. L-concept lattice of movies, critics and ratings (from Fig. 1).
3 Complete L-tolerances
In this section we develop a generalization of the known results on factorization of
complete lattices by complete tolerances [6, 17, 7] to fuzzy setting. We give a definition
of a complete L-tolerance on a completely lattice L-ordered set, introduce a structure
of an L-ordered set on the corresponding factor set and show that together with this
structure, the factor set is a completely lattice L-ordered set (Theorem 7). In addition,
we show that complete L-tolerances on a completely lattice L-ordered set are in one-
to-one correspondence with inflationary L-Galois connections (Theorem 8).
For an L-tolerance ∼ on a set X, an L-set B ∈ LX is called a block of the L-tolerance
∼ if for each x1 , x2 ∈ X it holds B(x1 ) ⊗ B(x2 ) ≤ (x1 ∼ x2 ). A block B is called maximal
if for each block B0 from B ⊆ B0 it follows B = B0 . The set of all maximal blocks of ∼
always exists by Zorn’s lemma, is called the factor set of X by ∼ and denoted by X/∼.
Further we set for each x ∈ X, JxK∼ (y) = x ∼ y, obtaining an L-set JxK∼ called the
class of ∼ determined by x.
An L-tolerance ∼ on a completely lattice L-ordered set U = hhU, ≈i, i is called
complete if it is compatible with ≈ and for each R ⊆ ∼ it holds
sup(pr1 (R)) ∼ sup(pr2 (R)) = inf(pr1 (R)) ∼ inf(pr2 (R)) = 1, (20)
where pr1 (resp. pr2 ) is the projection U ×U → U to the first (resp. second) component.
Note that in the classical case the condition (20) becomes the well-known condition
of completeness of ∼ [17, 7]: Any subset R ⊆ ∼ is a setWof pairs {hu j , v j i | j ∈ J} such
that for each j ∈ J it holds u j ∼ v j and sup(pr1 (R)) = j∈J u j , sup(pr2 (R)) = j∈J v j
W
and similarly for infima.
For the rest of this section we suppose ∼ is a complete L-tolerance on a completely
lattice L-ordered set U = hhU, ≈i, i.
Lemma 1. If u ∼ v = 1 then (a ⊗ u) ∼ (a ⊗ v) = 1 and (a → u) ∼ (a → v) = 1.
Proof. Follows directly from the definition.
Lemma 2. If ∼ is a complete L-tolerance on a complete lattice L-ordered set U =
hhU, ≈i, i then so is a → ∼, for each a ∈ L.
Proof. Since ∼ is compatible with ≈ then for u, u0 , v, v0 ∈ U we have (u ≈ u0 ) ⊗ (a →
(u0 ∼ v0 )) ⊗ (v0 ≈ v) ≤ a → ((u ≈ u0 ) ⊗ (u0 ∼ v0 ) ⊗ (v0 ≈ v)) ≤ a → (u ∼ v), proving
a → ∼ is compatible with ≈.
Let R ⊆ a → ∼. We have for each u, v ∈ U, (uRv) ≤ a → (u ∼ v), which is equivalent
to a ⊗ (u R v) ≤ (u ∼ v). Thus, a ⊗ R ⊆ ∼ and we can use (20). We have sup(pr1 (a ⊗
R)) = sup(a ⊗ pr1 (R)) = a ⊗ sup(pr1 (R)), inf(pr1 (a ⊗ R)) = inf(a ⊗ pr1 (R)) = a →
inf(pr1 (R)) and similarly for pr2 . Now the result follows from Lemma 1.
Theorem 3. If ∼ is a complete L-tolerance on U, then for each a ∈ L the a-cut a ∼ is a
complete tolerance on the complete lattice hU, 1 i.
Proof. For a = 1 the assertion follows easily from the definition of complete L-tolerances.
The rest follows from Lemma 2.
We set for any u ∈ U,
u∼ = supJuK∼ , u∼ = infJuK∼ . (21)
Theorem 4. The pair h∼ , ∼ i is an inflationary isotone L-Galois connection on U.
Proof. We show that for u, v ∈ U it holds (v∼ u) ≤ (v u∼ ), the proof of the opposite
inequality is similar. Denote (v∼ u) = a. Since U {a/v∼ }(u) = 1 (by the definition
of upper cone), then we have a ⊗ v∼ ≤ u. Now, (a ⊗ v) ∼ (a ⊗ v∼ ) = 1 (Lemma 1)
and u ∼ (u ∨ (a ⊗ v)) = 1. Thus, u ∨ (a ⊗ v) ≤ u∼ which means that (a ⊗ v) ≤ u∼ or
v u∼ ≥ a. The fact that h∼ , ∼ i is inflationary is trivial.
Lemma 3. Let u, v ∈ U be such that v ≤ u, u ∼ v = 1. If w1 ≤ u, then (v w1 ) ≤ (u ∼
w1 ) and if v ≤ w2 , then (w2 u) ≤ (w2 ∼ v).
Proof. By completeness of ∼, (u ∨ w1 ) ∼ (v ∨ w1 ) = 1. Thus,
(v w1 ) = (v ∨ w1 ) ≈ w1 = (u ∼ (v ∨ w1 )) ⊗ ((v ∨ w1 ) ≈ w1 ) ≤ (u ∼ w1 ).
Similarly for w2 .
Theorem 5. For each u ∈ U the class JuK∼ is equal to the interval [u∼ , u∼ ] in U.
Proof. The inclusion JuK∼ ⊆ [u∼ , u∼ ] follows from basic properties of cones (for ex-
ample, JuK∼ ⊆ L U JuK∼ = L {u∼ }).
We prove the opposite inclusion. For w ∈ U denote u∼ w = a and w u∼ = b. We
have [u∼ , u∼ ](w) = a ∧ b. By Lemma 3, (u∼ (w ∧ u)) ≤ ((w ∧ u) ∼ u) and ((w ∨ u)
u∼ ) ≤ ((w ∨ u) ∼ u). But u∼ (w ∧ u) = a and (w ∨ u) u∼ = b which means that
[u∼ , u∼ ](w) = a ∧ b ≤ ((w ∧ u) ∼ u) ∧ ((w ∨ u) ∼ u). Using Theorem 3 we easily obtain
that the right-hand side is less than or equal to w ∼ u.
Theorem 6. Maximal blocks of ∼ are exactly L-intervals [v, u] where hu, vi are fix-
points of h∼ , ∼ i.
Proof. Let w1 , w2 ∈ U. We have
[v, u](w1 ) ⊗ [v, u](w2 ) = ((v w1 ) ∧ (w1 u)) ⊗ ((v w2 ) ∧ (w2 u))
≤ ((v w1 ) ⊗ (w2 u)) ∧ ((w1 u) ⊗ (v w2 ))
= ((v w1 ) ⊗ (w2∼ v)) ∧ ((w1 u) ⊗ (u w∼
2 ))
≤ (w2∼ w1 ) ∧ (w1 w∼
2 ) = Jw2 K∼ (w1 ) = (w1 ∼ w2 ),
showing [v, u] is a block.
Conversely, if W ∈ LU is a block then so is the interval [infW, supW ] which contains
W as a subset. Among all intervals [v, u], the maximal blocks are those satisfying v∼ = u
and u∼ = v.
We define two binary L-relations ≈ and on U/∼ by
[v1 , u1 ] ≈ [v2 , u2 ] = v1 ≈ v2 (= u1 ≈ u2 ), (22)
[v1 , u1 ] [v2 , u2 ] = v1 v2 (= u1 u2 ) (23)
(the equalities in the parentheses follow directly from (4), Theorem 4, and Theorem 2
(b))
Theorem 7. The tuple hhU/∼, ≈i, i is a completely lattice L-ordered set.
Proof. Sketch: we use Theorem 1, (5), (6).
Let h f , gi be an inflationary Galois connection on U. Set for each u, v ∈ U
u ∼h f ,gi v = ( f (u) v) ∧ (v g(u)). (24)
Theorem 8. ∼h f ,gi is an L-complete tolerance, satisfying u∼h f ,gi = f (u), u∼h f ,gi = g(u),
for each u ∈ U. The assignment h f , gi 7→ ∼h f ,gi is a bijection between the set of all
inflationary isotone L-Galois connections U and the set of all L-complete tolerances
on U.
Proof. Sketch: We use basic properties of isotone L-Galois connections (Theorem 2)
and the definition of an L-complete tolerance on U.
4 Block L-relations
This section introduces block L-relations on L-formal contexts, their properties and the
relationship to complete L-tolerances on L-concept lattices. The main results are con-
tained in Theorems 11 and 12, where we show that block L-relations of any formal
L-context are in one-to-one correspondence with complete L-tolerances on the associ-
ated L-concept lattice and that the L-concept lattice of each of the block relations is
isomorphic to the original L-concept lattice, factorized by the corresponding complete
L-tolerance.
We define block relations as follows: Block L-relation of I ∈ LX×Y is an L-relation
J ⊇ I such that Ext(X ↑ ,Y ↓ , J) ⊆ Ext(X ↑ ,Y ↓ , I) and Int(X ↑ ,Y ↓ , J) ⊆ Int(X ↑ ,Y ↓ , I).
In crisp setting, [17] defines block relation as a relation J ⊇ I where each row is an
intent of I and each column is an extent of I. Lemma 4 says that block L-relation is a
proper generalization of crisp block relation. The reason we define the notion that way
is to allow an analogous definition in the isotone case.
Lemma 4. J ∈ LX×Y , J ⊇ I is a block L-relation of I iff {x}↑I ∈ Int(X ↑ ,Y ↓ , I) for each
x ∈ X and {y}↓I ∈ Ext(X ↑ ,Y ↓ , I) for each y ∈ Y .
The following theorem provide characterization of block L-relations.
Theorem 9. Let I ∈ LX×Y be an L-relation. The following statements are equivalent:
(a) J is a block relation of I.
(b) J = I . Si with Si ∈ LY ×Y and for the induced mapping ∧Si we have B∧Si ∈
Int(X ↑ ,Y ↓ , I) and B ⊆ B∧Si for each B ∈ Int(X ↑ ,Y ↓ , I).
(c) J = Se / I with Se ∈ LX×X and for the induced mapping ∪Se we have A∪Se ∈
Ext(X ↑ ,Y ↓ , I) and A ⊆ A∪Se for each A ∈ Ext(X ↑ ,Y ↓ , I).
Proof. (sketch, equivalence of (a) and (b)): We have Ext(X ↑ ,Y ↓ , J) ⊆ Ext(X ↑ ,Y ↓ , I)
iff there exists a matrix Si such that J = I . Si by [4, Theorem 7]. We have A↑J =
A↑I.Si = (A↑I )∧Si for A ∈ LX . Since A↑I is any intent B in Int(X ↑ ,Y ↓ , I) and A↑J = B∧Si ∈
Int(X ↑ ,Y ↓ , I) we obtain B∧Si ∈ Int(X ↑ ,Y ↓ , I) for each B ∈ Int(X ↑ ,Y ↓ , I). By (16) and
(14) we have that J(x, y) is equal to {x}↑I ∧Si (y) and with the property B ⊆ B∧Si we get
I ⊆ J proving that J is a block L-relation.
Theorem 10. Let I ∈ LX×Y be an L-relation between X and Y .
(a) The set of all block L-relations J of I is an L-closure system (i.e. it is closed
under and →).
V
(b) The set of all Se (from Theorem 9) is an L-interior system (i.e. it is closed under
and ⊗).
W
(c) The set of all Si (from Theorem 9) is an L-interior system.
Proof. (a) Let Ji be block L-relations of I. Let J = i Ji and let B ∈ Int(X ↑ ,Y ↓ , J), hence
V
B = A↑J for some A ∈ LX . By definition of ↑J and properties of residuated lattices we
have
^ ↑
A↑J (y) =
^ ^ ^ ^^
A(x) → J(x, y) = A(x) → Ji (x, y) = A(x) → Ji (x, y) = A Ji .
x∈X x∈X i i x∈X i
Thus we have A↑J = i A↑Ji ∈ Int(X ↑ ,Y ↓ , I). Similarly, B↓J = i B↓Ji ∈ Ext(X ↑ ,Y ↓ , I),
T T
↑a→Ji ↑Ji
= a → A ∈ Int(X ↑ ,Y ↓ , I), and B a→Ji = i a → B↓Ji ∈ Ext(X
↓ ↑ ,Y ↓ , I).
T
A
Finally, from I ⊆ Ji we have I ⊆ i Ji and I ⊆ a → Ji . Whence i Ji and I ⊆ a → Ji
V V
are block L-relations proving that set of all block L-relations J of I is an L-closure
system.
(b) and (c) can be proved similarly.
The induced operators ∩ , ∪ of the matrices Se and Si have following properties:
Lemma 5. Let I ∈ LX×Y be an L-relation between X and Y and let J be its block L-
relation:
(a) A∪Se = A↑I ↓J for any A ∈ Ext(X ↑ ,Y ↓ , I), B∧Si = B↓I ↑J for any B ∈ Int(X ↑ ,Y ↓ , I).
(b) hA∪Se , A∪Se ∩Se ↑I i ∈ B(X ↑ ,Y ↓ , J) and hB∧Si ∨Si ↓I , B∧Si i ∈ B(X ↑ ,Y ↓ , J) for each
hA, Bi ∈ B(X ↑ ,Y ↓ , I).
(c) A∩Se ↑I = A↑I ∧Si = A↑J for any A ∈ LX and B∨Si ↓I = B↓I ∪Se = B↓J for any B ∈ LY .
Let I ∈ LX×Y be an L-relation between X and Y and let J be its block relation.
Denote by θJ a mapping θJ : B(X ↑ ,Y ↓ , I) → B(X ↑ ,Y ↓ , I) defined by
hA, BiθJ = hA∪Se , A∪Se ↑I i (25)
and denote by θJ a mapping θJ : B(X ↑ ,Y ↓ , I) → B(X ↑ ,Y ↓ , I) defined by
hA, BiθJ = hB∧Si ↓I , B∧Si i (26)
Notice, that different block L-relations J of an L-relation I induce different mappings
θJ , θJ , θ
θJ . In what follows we omit subscript in the notation θJ and write just , θ .
Obviously, for each hA, Bi ∈ B(X ,Y , I) we have hA, Biθ ≤ hA, Bi ≤ hA, Bi .
↑ ↓ θ
Now, we explain the relationship between block L-relations and compatible L-
tolerances.
Theorem 11. (a) Let J ⊇ I be a block L-relation. Then the mappings θ , θ form an
inflationary L-Galois connection on B(X ↑ ,Y ↓ , I).
(b) For any inflationary L-Galois connection h f , gi on B(X ↑ ,Y ↓ , I) the L-relation
J ∈ LX×Y given by
J(x, y) = f (h{x}↑I ↓I , {x}↑I i) h{y}↓I , {y}↓I ↑I i (27)
↑I ↓I ↑I ↓I ↓I ↑I
( = h{x} , {x} i g(h{y} , {y} i) )
is a block L-relation of hX,Y, Ii such that its mappings θ and θ are equal to the map-
pings f and g, respectively.
Proof. (a) Since J is a block L-relation then A↑J is an intent of hX,Y, Ii and f (hA, Bi) ∈
B(X ↑ ,Y ↓ , I). Similarly for g.
The pair h↑J , ↓J i is an antitone L-Galois connection between LX and LY . Thus, for
each A ∈ LX and B ∈ LY we have S(A, B↓J ) = S(B, A↑J ). Now,
f (hA1 , B1 i) hA2 , B2 i = S(B2 , A↑1J ) = S(A1 , B↓2J ) = hA1 , B1 i g(hA2 , B2 i)
proving h f , gi is an isotone L-Galois connection. Since I ⊆ J then A↑I ⊆ A↑J and f is
deflationary.
(b) First we need to show that each object intent of hX,Y, Ji is an intent of hX,Y, Ii
and each attribute extent of hX,Y, Ji is an extent of hX,Y, Ii. We shall prove the part for
extents. For each x ∈ X we have
{x}↑J (y) = J(x, y) = S( fX ({x}↑I ↓I ), {y}↓I ) = fX ({x}↑I ↓I )(x0 ) → {y}↓I (x0 )
^
x0 ∈X
↑I ↓I
)(x ) → I(x , y) = fX ({x}↑I ↓I )↑I (y)
0 0
^
= fX ({x}
x0 ∈X
and {x}↑J is an intent of hX,Y, Ii. That proves that Ext(X ↑ ,Y ↓ , J) ⊆ Ext(X ↑ ,Y ↓ , I); sim-
ilarly can be shown that Int(X ↑ ,Y ↓ , J) ⊆ Int(X ↑ ,Y ↓ , J). From properties of inflation-
ary L-Galois connections and antitone Galois connections, we have fX ({x}↑I ↓I )↑I (y) ≥
{x}↑I ↓I ↑I (y) = {x}↑I (y); hence J ⊇ I. The equality of θ , θ and f , g is immediate.
Theorem 11 and Theorem 8 generalize [7, Theorem 15]. The following theorem
represents the main result of this paper.
Theorem 12. (a) Complete L-tolerances are in one-to-one correspondence with block
L-relations.
(b) If complete L-tolerance ∼ and block L-relation J are in that correspondence,
then B(X ↑ ,Y ↓ , J) is isomorphic to the lattice of blocks of L-tolerance ∼.
Proof. The one-to-one correspondence follows from Theorem 11 and the fact that dif-
ferent block relation produce different mappings θ , θ . The isomorphism of B(X ↑ ,Y ↓ , J)
and the lattice of ∼ then follows from definition of θ , θ and their equality to mappings
f , g of ∼.
5 Illustrative Example
In this section, we use results developed in the previous sections to factorize the L-
concept lattice B(X ↑ ,Y ↓ , I) from Example 1.
Our aim is to reduce the size of the L-concept lattice B(X ↑ ,Y ↓ , I) by factoriza-
tion by complete L-tolerances. First we take the approach from [2]. This approach is
based on a choice of a threshold a ∈ L and using the a-cut a ≈ of the L-equality ≈ on
B(X ↑ ,Y ↓ , I) for factorization. The a-cut a ≈ is a complete tolerance on the complete
lattice hB(X ↑ ,Y ↓ , I), 1 i and, as noted in [5], the factor lattice is isomorphic to the
crisp part of the concept lattice B(X ↑ ,Y ↓ , a → I). As it can be easily seen, these re-
sults are a special case of the results of this paper. Namely, one can take the complete
L-tolerance a → ≈ on B(X ↑ ,Y ↓ , I) (the fact that it is indeed a complete L-tolerance eas-
ily follows from Lemma 2) and construct the associated block L-relation J ⊇ I, which
is equal to a → I. The factorized L-concept lattice B(X ↑ ,Y ↓ , I)/a ≈ is isomorphic to
B(X ↑ ,Y ↓ , a → I).
As an example, we present in Fig. 3 results we obtained for our formal context of
movies, critics and ratings with values of the threshold a equal to 0.4 and 0.3.
0.6/c1, 0.6/c2, 0.4/c3, 0.6/c4, 0.6/c5
BV, 0.8/c5 0.6/c3, 0.8/c4
0.8/c1 0.8/c3
0.8/c1, 0.8/c2, 0.6/c3, 0.8/c4, 0.8/c5
0.8/c2 c5 c4 TSS, c3
0.8/BV c1 BV, 0.8/c5 0.8/c3, c4
MD c1 TSS, c3
0.6/BV, c2 0.6/MD 0.8/TSS 0.8/BV, c2 MD
0.4/BV, LH, 0.6/MD, 0.6/TSS 0.6/BV, LH, 0.8/MD, 0.8/TSS
Fig. 3. L-concept lattice of movies, critics and ratings (from Fig. 1), factorized with respect to the
threshold a = 0.8 (left) and a = 0.6 (right).
We also tried a more sophisticated approach, based on [13]. The author’s method
is based on using a complete tolerance on a complete lattice induced by an interior
and closure operator. As an example, the author uses a complete tolerance on a (crisp)
concept lattice, obtained by selecting subsets X 0 ⊆ X and Y 0 ⊆ Y of important objects
and important attributes, respectively.
Although a proper fuzzification of the results from [13] remains to be developed, it
is possible to try some experiments. We provide a short outline of our method here and
leave the details to a forthcoming paper.
For a formal L-context hX,Y, Ii we select two L-sets X 0 ∈ LX and Y 0 ∈ LY and
interpret them as L-sets of “important objects” and “important attributes”, respectively.
Thus, for an object x ∈ X, the value X 0 (x) is the degree to which x is important, and
similarly for attributes. Further we define two L-relations IX 0 , IY 0 ∈ LX×Y by
IX 0 (x, y) = X 0 (x) → I(x, y), IY 0 (x, y) = Y 0 (y) → I(x, y).
As it can be easily seen from (15), Int(X ↑ ,Y ↓ , IX 0 ) ⊆ Int(X ↑ ,Y ↓ , I) and Ext(X ↑ ,Y ↓ , IY 0 ) ⊆
Ext(X ↑ ,Y ↓ , I). Thus, the L-relations IX 0 and IY 0 select some intents and extents of formal
0.4/c1, 0.4/c2, 0.2/c3, 0.4/c4, 0.4/c5 0.4/c1, 0.4/c2, 0.4/c3, 0.6/c4, 0.4/c5
BV, 0.6/c5 0.4/c3, 0.6/c4 BV, 0.6/c1, 0.6/c5
0.6/c1, 0.6/c2 0.6/c3 0.6/c2, 0.6/c4 TSS
0.8/BV 0.8/c4 TSS, 0.8/c3 0.8/BV, 0.8/c1, 0.8/c5
0.8/c2 c1, c5 0.8/c1 0.8/TSS, c3
0.6/BV, c5 0.8/TSS, c3 0.8/c5 c4
c4
LH, c1 0.6/TSS 0.6/BV MD
0.4/BV, c2 MD LH, 0.8/MD 0.6/TSS
0.2/BV, 0.8/LH, 0.8/MD, 0.4/TSS 0.4/BV, 0.8/LH, 0.6/MD, 0.4/TSS, c2
Fig. 4. L-concept lattice of movies, critics and ratings (form Fig. 1), factorized with respect
to an L-set of important objects X 0 = {0.8/BV, LH, MD, TSS} and L-set of important at-
tributes Y 0 = {c1, 0.8/c2, c3, c4, c5} (left) and with respect to an L-set of important objects
X 0 = {BV, LH, MD, TSS} and L-set of important attributes Y 0 = {c1, 0.6/c2, c3, c4, c5} (right).
concepts from B(X ↑ ,Y ↓ , I). These intents and extents are interpreted as “important”.
Now, let JX 0 ,Y 0 ∈ LX×Y be the minimal (with respect to L-set inclusion) block L-relation
of I such that both intent and extent of each formal L-concept from B(X ↑ ,Y ↓ , JX 0 ,Y 0 ) are
important (JX 0 ,Y 0 always exists because of Theorem 10(a); details are omitted). Using the
results of this paper (Theorem 12) we obtain that JX 0 ,Y 0 induces a complete L-tolerance
on the L-concept lattice B(X ↑ ,Y ↓ , I) and the corresponding factor completely lattice
L-ordered set is isomorphic to the L-concept lattice B(X ↑ ,Y ↓ , JX 0 ,Y 0 ).
Note that this approach contains the approach from [2] as a special case. The factor
completely lattice L-ordered set B(X ↑ ,Y ↓ , I)/a ≈ is isomorphic to B(X ↑ ,Y ↓ , JX 0 ,Y 0 ) for
X 0 = {a/x | x ∈ X} and Y 0 = {a/y | y ∈ Y }.
We apply the above considerations to our example. Suppose we consider the film
BV less important than the other films (perhaps because we have not seen BV) and the
critic c2 less important than the other critics (because we do not like his opinion on
MD). More precisely, set X 0 = {a/BV, LH, MD, TSS} and Y 0 = {c1, b/c2, c3, c4, c5},
where a, b ∈ L. In Fig. 4 we can see the resulting concept lattices in two cases: first
a = b = 0.8 and second a = 1 and b = 0.6.
6 Conclusions
We presented a generalization of the theory of complete tolerances on complete lattices
and the relationship of block relations on formal contexts and complete tolerances on
the corresponding concept lattices [6, 17, 7] to fuzzy setting. Our results can be used
for reducing the size of fuzzy concept lattices by means of factorization and offer a
greater degree of variability than the known approach from [2]. In the future we will
focus namely on the investigation of block relations in the isotone case and develop-
ing the theory of approximations in fuzzy concept lattices which would give a proper
theoretical background to our experiments from Sec. 5.
References
1. Belohlavek, R.: Concept lattices and order in fuzzy logic. Ann. Pure Appl. Log. 128(1-3),
277–298 (2004)
2. Belohlavek, R.: Similarity relations in concept lattices. J. Log. Comput. 10(6), 823–845
(2000)
3. Belohlavek, R.: Fuzzy Relational Systems: Foundations and Principles. Kluwer Academic
Publishers, Norwell, USA (2002)
4. Belohlavek, R., Konecny, J.: Operators and spaces associated to matrices with grades and
their decompositions, to appear, submitted to Fundamenta Informaticae
5. Belohlavek, R., Outrata, J., Vychodil, V.: Direct factorization by similarity of fuzzy concept
lattices by factorization of input data. In: Yahia, S.B., Nguifo, E.M., Belohlavek, R. (eds.)
CLA. Lecture Notes in Computer Science, vol. 4923, pp. 68–79. Springer (2006)
6. Czédli, G.: Factor lattices by tolerances. Acta Sci. Math. 44, 35–42 (1982)
7. Ganter, B., Wille, R.: Formal Concept Analysis – Mathematical Foundations. Springer
(1999)
8. Georgescu, G., Popescu, A.: Non-dual fuzzy connections. Arch. Math. Log. 43(8), 1009–
1039 (2004)
9. Hájek, P.: Metamathematics of Fuzzy Logic (Trends in Logic). Springer (November 2001)
10. Kelly, G.M.: Basic Concepts of Enriched Category Theory. Cambridge University Press
(1982)
11. Kohout, L. J.; Bandler, W.: Relational-product architectures for information processing. In-
formation Sciences 37(1-3), 25–37 (1985)
12. Krupka, M.: An alternative version of the main theorem of fuzzy concept lattices. In: Trappl,
R. (ed.) Cybernetics and Systems 2010. pp. 9–14. Austrian Society for Cybernetic Studies,
Vienna (2010), extended version submitted
13. Meschke, C.: Approximations in concept lattices. In: Kwuida, L., Sertkaya, B. (eds.) Formal
Concept Analysis, Lecture Notes in Computer Science, vol. 5986, pp. 104–123. Springer
Berlin / Heidelberg (2010)
14. Pollandt, S.: Fuzzy Begriffe: Formale Begriffsanalyse von unscharfen Daten. Springer–
Verlag, Berlin–Heidelberg (1997)
15. Stubbe, I.: Categorical structures enriched in a quantaloid: tensored and coten-
sored categories. Theory Appl. Categ. 16, No. 14, 283–306 (electronic) (2006),
http://www.ams.org/mathscinet-getitem?mr=2223039
16. Ward, M., Dilworth, R.P.: Residuated lattices. Transactions of the American Mathematical
Society 45, 335–354 (1939)
17. Wille, R.: Complete tolerance relations of concept lattices. In: Eigenthaler, G., et al. (eds.)
Contributions to General Algebra, vol. 3, pp. 397–415. Hölder-Pichler-Tempsky, Wien
(1985)
18. Zhao, H., Zhang, D.: Many valued lattices and their representations. Fuzzy Sets and Systems
159(1), 81–94 (Jan 2008)