In [4] we have presented a new common platform for different types of fuzzification of a concept lattice. Now we show a pendant of the basic theorem on clasical concept lattices for this generalization which characterizes (complete) lattices isomorphic to this generalized concept lattice. c V. Snsaeˇ´l, R. Belˇohal´vek (Eds.): CLA 2004, pp. 25-33, ISBN 80-248-0597-9. VSˇB - Technical University of Ostrava, Dept. of Computer Science, 2004.
There are some attempts have arisen which try to fuzzify the classical crisp
Ganter-Wille’s concept lattice, i.e. to consider the fuzzy values instead of 0’s/1’s
in a matrix. One of them is the natural (and symmetric) fuzzification given by
e.g. Bˇelohla´vek ([
Our paper [
In this paper we formulate the extend version of the basic theorem on such
generalized concept lattice which is the generalization of above-mentioned and
we proved this added extension (the simple version of it was proved in [
A generalized fuzzy concept lattice
Now we shortly repeat basic definitions and results from [
Let L be a poset, C and D be supremum-complete upper-semilattices (i.e. there exists sup X = X for each subset X of C or D). Let • : C × D → L be monotone and left-continuous in both their arguments, i.e.
Partially supported by grant 1/0385/03 of the Slovak grant agency VEGA. 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 ≤ holds for d ∈ D, ∈ L and for all c ∈ X ⊆ C, then sup X • d ≤ 2b) If c • d ≤ holds for c ∈ C, ∈ L and for all d ∈ Y ⊆ D, then c • sup Y ≤ . .
Let A and B be non-empty sets and let R be L-fuzzy relation on their Cartesian product, i.e. R : A × B → L.
Define the following mapping : BD → AC: If g : B → D then (g) : A → C is defined in the following way: (g)(a) = sup{c ∈ C : (∀ b ∈ B)c • g(b) ≤ if and only if c • d ≤
The proof of the part 1) is in [
We will need the following singleton functions: If T is an arbitrary set and U is a poset with the least element 0U , define StT,,uU : T → U in the following way:
We show a few basic properties of these functions.
Lemma 1.
StT,,uU (x) = u, if x = t, 0U , elsewhere.
f = sup{StT,,fU(t) : t ∈ T }.
Proof. Let x ∈ T . Because of pointwise defined supremum of a set of functions we have sup{St,f(t) : t ∈ T }(x) = sup{StT,,fU(t)(x) : t ∈ T }. For all t = x we have
T,U StT,,fU(t)(x) = 0U , hence sup{StT,,fU(t)(x) : t ∈ T } = SxT,,fU(x)(x) = f (x). So we obtain f (x) = sup{StT,,fU(t) : t ∈ T }(x) for all x ∈ T , q.e.d..
Lemma 2. a) For all a ∈ A, b ∈ B, c ∈ C b) For all a ∈ A, b ∈ B, d ∈ D (SaA,,cC )(b) = sup{d ∈ D : c • d ≤
R(a, b)}. (SbB,d,D)(a) = sup{c ∈ C : c • d ≤
R(a, b)}.
Proof. By the definition (SaA,,cC )(b) = sup{d ∈ D : (∀ x ∈ A)SaA,,cC (x) • d ≤ R(x, b)}. Because SaA,,cC (x) • d = 0C • d = 0L for every x = a, we obtain (∀ x ∈ A)SaA,,cC (x) • d ≤ R(x, b) iff S aA,,cC (a) • d ≤ R(a, b), i.e. c • d ≤ R(a, b) for all d ∈ D. But it means that {d ∈ D : (∀ a ∈ A)SaA,,cC (a) • d ≤ R(a, b)} = {d ∈ D : c • d ≤ R(a, b)} and (SaA,,cC )(b) = sup{d ∈ D : (∀ x ∈ A)SaA,,cC (x) • d ≤ R(x, b)} = sup{d ∈ D : c • d ≤ R(a, b)}, q.e.d..
The proof of the part b) is analogous.
Firstly we prove the theorem for the case V = L: Define α L(a, c) = β L(b, d) = (SaA,,cC ), ( (SaA,,cC )) , ( (SbB,d,D)), (SbB,d,D) .
Obviously both results are really concepts.
Claim 1 a) α L is non-increasing in the second argument. b) β L is non-decreasing in the second argument.
Proof. Let c1 ≤ c2 are from C, we want to prove that α L(a, c1) ≥ α L(a, c2) (for an arbitrary a ∈ A). It is enough to prove that (SaA,,cC1 ) ≥ (SaA,,cC2 ), i.e.
(SaA,,cC1 )(b) ≥ (SaA,,cC2 )(b) for all b ∈ B, which (by the previous lemma) means sup{d ∈ D : c1 • d ≤ R(a, b)} ≥ sup{d ∈ D : c2 • d ≤ R(a, b)}.
Because of monotoneity of ≤ in the first argument we have c1 • d ≤ c2 • d, so c2 • d ≤ R(a, b) implies c1 • d ≤ R(a, b). It means that {d ∈ D : c2 • d ≤ R(a, b)} ⊆ { d ∈ D : c1 • d ≤ R(a, b)}, which implies wanted sup{d ∈ D : c2 • d ≤ R(a, b)} ≤ sup{d ∈ D : c1 • d ≤ R(a, b)}, q.e.d..
The proof of the part b) is symmetrical.
Claim 2 α L(a, c) ≥ β L(b, d)
SaA,,cC (a) = c ≤ sup{k ∈ C : k • d ≤ obvious SaA,,cC (x) = 0C ≤ (SbB,d,D)(x), hence SaA,,cC ≤
R(a, b), then clearly c ∈ { k ∈ C : k • d ≤ R(a, b)}. It follows that
R(a, b)} = (SbB,d,D)(a). For x = a we have (SbB,d,D). Because of the Galois connection between and it follows that (SaA,,cC ) ≥ ( (SbB,d,D)), i.e. α L(a, c) ≥ β L(b, d).
Inversely, if x ∈ A, clearly u ∈ { k ∈ C : k • d ≤ R(x, b)} iff u • d ≤ R(x, b). Hence (using left-continuousness of • in the second argument) (SbB,d,D)(x) • d = sup{k ∈ C : k • d ≤ R(x, b)} • d ≤ and this implies d ∈ { m ∈ D : (∀ x ∈ d ≤ sup{m ∈ D : (∀ x ∈ A) (SbB,d,D)(x) • m ≤ the definition of ). Because α L(a, c) ≥ β L(b, d), i.e.
R(x, b). So (∀ x ∈ A) (SbB,d,D)(x) • d ≤ R(x, b),
A) (SbB,d,D)(x) • m ≤ R(x, b)}, hence
R(x, b)} = (SaA,,cC ) ≥ ( (SbB,d,D))(b) (by ( (SbB,d,D)), we obtain d ≤ ( (SbB,d,D))(b) ≤ (SaA,,cC )(b). Because w ∈ { m ∈ D : c • m ≤ R(a, b)} iff c • w ≤ R(a, b), by left-continuousness of • in the second argument we have c • sup{m ∈ D : c • m ≤ R(a, b)} ≤ R(a, b), i.e. (by the previous lemma) c • (SaA,,cC )(b) ≤ R(a, b). Because of monotonity of • in the second argument we obtain c • d ≤ c • (SaA,,cC )(b) ≤ R(a, b), q.e.d..
Claim 3 Let f : A →
C and g : B →
D and g, f be a concept. a) g, f = inf{α L(a, f(a)) : a ∈ A}. b) g, f = sup{β L(b, g(b)) : b ∈ B}.
A. Then SaA,,fC(a)(a) = f (a) and SaA,,fC(a)(x) = 0C ≤ f (x) for the other x = a, hence SaA,,fC(a) ≤ f is the intent of some concept, we obtain f . Because and
form a Galois connection and ( (SaA,,fC(a))) ≤ ( (f )) = f , so g, f ≤ so g, f ≤ inf{α L(a, f(a)) : a ∈ (SaA,,fC(a)), ( (SaA,,fC(a))) = α L(a, f(a)). This is true for all a ∈ A, ( ( a∈ A position
a∈ A α L(a, f(a)) SaA,,fC(a) ≤ ( (SaA,,fC(a))) = sup{ ( (SxA,,fC(x))) : x ∈ A} for all a ∈ (using lemma 1) that f = sup{SaA,,fC(a) : a ∈ A} ≤ sup{
Conversely, by the part 1) of the theorem we have inf{α L(a, f(a)) : a ∈ A} = = (SaA,,fC(a)), ( (SaA,,fC(a))) = (SaA,,fC(a)),
a∈ A a∈ A ( (SaA,,fC(a))))) . On the other hand, using the property of comand (following from a Galois connection between them) we have A. It means A} ≤ ( (sup{
( (SxA,,fC(x))) : x ∈ A})) = f ≤ ( ( a∈ A q.e.d..
The proof of the part b) is analogous.
( (SaA,,fC(a))))). Hence g, f ≥ ( ( x∈ A ( (SxA,,fC(x))) : x ∈ ( (SxA,,fC(x))))), i.e. inf{α L(a, f(a)) : a ∈
A}, Claim 4 a) α L[A × C] is infimum-dense in L. b) β L[B × D] is supremum-dense in L.
Proof. They are obvious consequences of the previous claim.
L →
We have proven the second part of the basic theorem for the special case V = L. Now we will prove it for another cases.
First we assume that V is a complete lattice isomorphic to our L. Let ϕ : V is a witness isomorphism. Define α (a, c) = ϕ (α L(a, c)), β (b, d) = ϕ (β L(b, d)).
We prove that these mapping fulfill appropriate properties: Claim 5 a) α is non-increasing in the second argument. b) β is non-decreasing in the second argument.
Proof. If c1 ≤ c2, we have (by the claim 1) α L(a, c1) ≥ α L(c, a2). Because ϕ is an isomorphism, we obtain ϕ (α L(a, c1)) ≥ ϕ (α L(c, a2)), i.e. α (a, c1) ≥ α (c, a2), q.e.d..
The proof of the part b) is analogous.
Claim 6 a) α [A × C] is infimum-dense. b) β [B × D] is supremum-dense.
Proof. If v ∈ V , let g, f ∈ L s.t. ϕ ( g, f ) = v (such v exists, because ϕ is a bijection). Then inf{α (a, f(a)) : a ∈ A} = inf{ϕ (α L(a, f(a))) : a ∈ A} = ϕ (inf{α L(a, f(a)) : a ∈ A}) (because ϕ is an isomorphism), = ϕ ( g, f ) (by claim 2) = v. Hence we can express an arbitrary element of V as the infimum of some subset of α [A × C], i.e. α [A × C] is infimum-dense, q.e.d..
The fact that β [B × D] is supremum-dense can be proven analogously. Claim 7 α (a, c) ≥ β (b, d) if and only if c • d ≤ R(a, b).
Proof. α (a, c) ≥ β (b, d) i.e. ϕ (α L(a, c)) ≥ ϕ (β L(b, d)) iff α L(a, c) ≥ β L(b, d) (because ϕ is an isomorphism), iff c • d ≤ R(a, b) (we have proven it above), q.e.d..
Now we have proven the first direction, we are going to show the opposite one. Let α and β have appropriate properties.
Claim 8 a) For all a ∈ A, c ∈ C and v ∈ V b) For all b ∈ B, d ∈ D and v ∈ V α (a, c) ≥ v β (b, d) ≤ v iff iff (∀ b ∈ B)(∀ d ∈ D)(β (b, d) ≤ v → α (a, c) ≥ β (b, d)).
(∀ a ∈ A)(∀ c ∈ C)(α (a, c) ≥ v → α (a, c) ≥ β (b, d)).
Proof. If α (a, c) ≥ v, then clearly β (b, d) ≤ v implies α (a, c) ≥ β (b, d) what means c • d ≤ R(a, b) by assumption on α and β .
Conversely, using supremum-density of β [B × D] our v can be expressed in a form v = sup{β (bi, di) : i ∈ I} for some set of pairs { bi, di : i ∈ I}. This implies that β (bi, di) ≤ v for all i ∈ I, hence (by our assumption) α (a, c) ≥ β (bi, di) for all i ∈ I. But it means that α (a, c) ≥ sup{β (bi, di) : i ∈ I} = v, q.e.d..
The proof of the part b) is symmetrical.
Now we can define the following function ϕ : L →
V in the following way: ϕ ( g, f ) = inf{α (a, f(a)) : a ∈ A} and show that it is a wanted isomorphism.
Claim 9 ϕ is order-preserving.
Proof. g1, f1 ≤ g2, f2 iff f1 ≥ f2 iff f1(a) ≥ f2(a) for all a ∈ A. Because α is non-increasing in the second argument, it implies α (a, f1(a)) ≤ α (a, f2(a)). So we have ϕ ( g1, f1 ) = inf{α (x, f1(x)) : x ∈ A} ≤ α (a, f2(a)) for all a ∈ A and (using the definition of an infimum) ϕ ( g1, f1 ) ≤ inf{α (a, f2(a)) : a ∈ A} = ϕ ( g2, f2 ), q.e.d..
Now we define the function ψ : L →
V by ψ (v) = gv, fv
such that fv(a) = sup{c ∈ C : α (a, c) ≥ v}, gv(b) = sup{d ∈ D : β (b, d) ≤ v} and show that ψ = ϕ −1.
First we prove that gv, fv is really concept: Claim 10 a) b) (fv) = gv.
(gv) = fv.
Proof. α (a, c) ≥ v is (by previous lemma) equivalent to (∀ b ∈ B)(∀ d ∈ D)(β (b, d) ≤ v → α (a, c) ≥ β (b, d)) and because of the relation between α , β and R, this is equivalent to (∀ b ∈ B)(∀ d ∈ D)(β (b, d) ≤ v → c • d ≤ R(a, b)). This can be replaced equivalently by (∀ b ∈ B)c • sup{d ∈ D : β (b, d) ≤ v} ≤ R(a, b) (one implication follows from the definition of a supremum, the second one from left-continuity of •), i.e. (∀ b ∈ B)c • gv(b) ≤ R(a, b). This gives the equality sup{c ∈ C : α (a, c) ≥ v} = sup{c ∈ C : (∀ b ∈ B)c • gv(b) ≤ R(a, b)}, i.e. fv(a) = (gv)(a) (by the definitions of fv and ) for all a ∈ A. It means that fv = (gv), q.e.d..
The proof of the part b) is symmetrical.
Claim 11 ψ is order-preserving.
Proof. If v1 ≤ v2 then clearly α (a, c) ≥ v2 implies α (a, c) ≥ v1. It follows that {c ∈ C : α (a, c) ≥ v2} ⊆ { c ∈ C : α (a, c) ≥ v1}, i.e. fv2 (a) = sup{c ∈ C : α (a, c) ≥ v2} ≤ sup{c ∈ C : α (a, c) ≥ v1} = fv1 (a) for all a ∈ A. This means that fv1 ≥ fv2 , i.e. ψ (v1) = gv1 , fv1 ≤ gv2 , fv2 = ψ (v2), q.e.d.. Claim 12 ϕ (ψ (v)) = v.
Proof. Using supremum-density of β [B × D] our v can be expressed in a form v = sup{β (bi, di) : i ∈ I} for some set of pairs { bi, di : i ∈ I}. This implies that β (bi, di) ≤ v for all i ∈ I. If a ∈ A and c ∈ C are such that α (a, c) ≥ v, we have β (bi, di) ≤ α (a, c) for all i ∈ I. Hence c • di ≤ R(a, bi), and using the left-continuousness of • in the first argument we obtain sup{c ∈ C : α (a, c) ≤ v}•di ≤ R(a, bi), i.e. (by the definition of fv) fv(a)•di ≤ R(a, bi) for all i ∈ I and a ∈ A. But it means that α (a, fv(a)) ≥ β (bi, di) and this implies α (a, fv(a)) ≥ sup{β (bi, di) : i ∈ I} = v. Hence ψ ( gv, fv ) = inf{α (a, fv(a)) : a ∈ A} ≥ v.
Conversely, using supremum-density of α [A × C] our v can be expressed in a form v = inf{α (ai, ci) : i ∈ I} for some set of pairs { ai, ci : i ∈ I}. Clearly α (ai, ci) ≥ v, therefore ci ∈ { c ∈ C : α (ai, c) ≥ v}, which implies ci ≤ sup{c ∈ C : α (ai, c) ≥ v} = fv(ai), for all i ∈ I. Because α is nonincreasing in the second argument, we obtain α (ai, ci) ≥ α (ai, fv(ai)) for all i ∈ I. And because α (ai, fv(ai)) ∈ { α (a, fv(a)) : a ∈ A}, we have α (ai, ci) ≥ α (ai, fv(ai)) ≥ inf{α (a, fv(a)) : a ∈ A} = ψ ( gv, fv ), for all i ∈ I. This implies v = inf{α (ai, ci) : i ∈ I} ≥ ψ ( gv, fv ), q.e.d..
Claim 13 ψ (ϕ ( g, f )) = g, f .
Proof. Let v = ϕ ( g, f ) = inf{α (a, f(a)) : a ∈ A}, it is enough to prove that g = gv.
Because (∀ a ∈ A)(f (a) • d ≤ R(a, b)) iff ( ∀ a ∈ A)(β (b, d) ≤ α (a, f(a))) (it is a property of α and β ), and this is (by the definition of a infimum) equivalent to β (b, d) ≤ inf{α (a, f(a)) : a ∈ A} = v, we obtain {d ∈ D : (∀ a ∈ A)f (a) • d ≤ R(a, b)} = {d ∈ D : β (b, d) ≤ v}, which implies (using the definitions of and gv) (f )(b) = sup{d ∈ D : (∀ a ∈ A)f (a) • d ≤ R(a, b)} = sup{d ∈ D : β (b, d) ≤ v} = gv(b). It is true for all b ∈ B, so g = (f ) = gv, q.e.d..
To conclude, we prove that both ϕ and ψ are order-preserving and both ϕ ◦ ψ and ψ ◦ ϕ are identities. All this means that really ψ = ϕ −1 and both ϕ : V → L and psi : L → V are isomorphisms. Quod erat demonstrandum.
As a bonus we prove next property of our mappings: Claim 14 a) b) α (a, sup{ci : i ∈ I}) = inf{α (a, ci) : i ∈ I}.
β (b, sup{di : i ∈ I}) = sup{α (b, di) : i ∈ I}.
Proof. β [B × D] is supremum-dense, so α (a, sup{ci : i ∈ I} = sup{β (bj, dj) : j ∈ J } for some { bj, dj : j ∈ J }. This implies α (a, sup{ci : i ∈ I} ≥ β (bj, dj), i.e. (by the definition) sup{ci : i ∈ I} • dj ≤ R(a, bj) for all j ∈ J . It follows that ci • dj ≤ R(a, bj), i.e. α (a, ci) ≥ β (bj, dj) for all i ∈ I, j ∈ J . By the definitions of a infimum and a supremum we obtain inf{α (a, ci) : i ∈ I} ≥ β (bj, dj) and inf{α (a, ci) : i ∈ I} ≥ sup{β (bj, dj) : j ∈ J } = α (a, sup{ci : i ∈ I}.
Conversely again from the supremum-density of β [B×D], we have inf{α (a, ci) : i ∈ I} = sup{β (bj, dj) : j ∈ J } for some { bj, dj : j ∈ J }. It follows that α (a, ci) ≥ sup{β (bj, dj) : j ∈ J } for all j ∈ J and α (a, ci) ≥ β (bj, dj), i.e. ci • dj ≤ R(a, bj) for all i ∈ I, j ∈ J . Again, it is equivalent sup{ci : i ∈ I} • dj ≤ R(a, bj), i.e. α (a, sup{ci : i ∈ I}) ≥ β (bj, dj) for all j ∈ J , hence α (a, sup{ci : i ∈ I}) ≥ sup{β (bj, dj) : j ∈ J } = inf{α (a, ci) : i ∈ I}, q.e.d..
The proof of the part b) is symmetrical, we use the infinum-density of the set α [A × C].
Yet one note on an asymmetry in the definition of ϕ . If we define the function ϕ : L → V in the following way (symmetrically to ϕ ):
ϕ ( g, f ) = sup{β (b, g(b)) : b ∈ B}, it can be proven (analogously to the claim 12) that ϕ (ψ (v)) = v. So for arbitrary concept g, f we take v = ψ −1( g, f ) and we obtain ϕ ( g, f ) = ϕ (ψ (v)) = v = ϕ (ψ (v)) = ϕ ( g, f ), i.e. ϕ = ϕ . Hence our asymmetry in the definition of ϕ is only seeming and
inf{α (a, f(a)) : a ∈ A} = sup{β (b, g(b)) : b ∈ B}. 3
In this paper we prove the extended version of the basic theorem on a generalized concept lattice, which is a common platform for till now known fuzzifications of a classical crisp concept lattice. The main idea of it is to use two different complete lattices, one for objects and maybe another for attributes.