The most general algebraic structure of truth-values considered in the theory of fuzzy concept analysis to evaluate the attributes and objects has been a lattice. However, in some examples arises the necessity of a more general structure. In this paper we investigate the use of multilattices as underlying set of truth-values for these attributes and objects.
The study of reasoning methods to work out with uncertainty, imprecise data or incomplete information has been a trending topic in the recent years in order to explain, in a better way, observed facts, specify statements, reasoning and/or execute programs.
One important and powerful mathematical tool that has been used for this purpose at theoretical level is fuzzy logic. From the applicative side, neural networks have a massively parallel architecture-based dynamics which are inspired by the structure of human brain, adaptation capabilities, and fault tolerance. The recent paradigm of soft computing promotes the use and integration of different approaches for the problem solving.
Formal concept analysis, introduced by Wille in [
There has been many approaches in order to generalise the classical
concept lattices given by Ganter and Wille [
Recently, a new approach has been proposed by Medina et al in [
On the other hand, the theory of multilattices arose trying to weaken the
restrictions imposed on a (complete) lattice, namely, the “existence of least upper
bounds and greatest lower bounds” is relaxed to “existence of minimal upper
bounds and maximal lower bounds”. In this direction, several definitions have
been proposed in the mathematical literature of the structure so-called
multilattice [
Later on, an alternative notion of multilattice, with better properties
regarding substructures than the previous definitions, has been introduced [
Multilattices, in the sense of the paragraph above, also arise in a natural
manner in the research area concerning fuzzy extensions of logic programming [
The main result introduced here is the presentation of multilattices as underlying set where to evaluate the attributes, the objects and the relation in a fuzzy environment to formal concept analysis, indeed, this leads us to see that the set of “multilattice concepts” is a multilattice. We can see as well that if we evaluate the objects or the attributes in a lattice and the other in a multilattice what we have again a lattice not a multilattice as we could think at first.
The idea of using multilattices as underlying set of truth values arises us since in real life many thigns are ordered in a way that we we know that some objects are better than others but sometimes we can not choose which is the best of them because they can have different properties. This idea can be seen in the example we give in the last section of this paper where we consider a group of hotels. It is logical to think that four-star hotels are better than three star hotel, but sometimes we can not decide if a four-star hotel is better than another four-star hotel since these can have different properties to be considered like acommodation, location, price, etc., and one can be better in one property and worse in other. This, as we have already said, is what have lead up to consider multilattices because this structure deals better with objects which are uncomparable.
The plan of this paper is the following: in Section 2 we present the main definitions and results to understand the paper. Section 3 presents the formal concept multilattice; we also provide an example where this new structure can be used in Section 4; the paper ends with some conclusions and prospects for future work. 2
In this first section we will set the basic notions required to the complete understanding of the paper. We will start with a bit of lattice and multilattice theory and finished with concept lattice analysis.
One of the most structures used when hanging with fuzziness is a lattice, this has been a very suitable in order to develop many theories. Although the following definitions are well known, we will recall them here in order to make this paper as selfcontained as possible. The definition of a lattice is given bellow. Definition 1. By a complete lattice is understood a poset, (L, ), where every subset of L has supremum and infimum.
When instead of the existence of both supremum and infimum for every subset we only ask for the existence of one of them the notion of semilattice arised.
Definition 2. By a complete lower semilattice is understood a poset, (L, ), where every non-empty subset of L has infimum.
Definition 3. By a complete upper semilattice is a poset, (L, ), where every non-empty subset of L has supremum.
Nevertheless, there is a closed relationship between lattices and semilattices, indeed, if we have the existence of a top element in lower semilattices or a bottom element in upper semilattices we have that they become lattices as the following theorem states.
Theorem 1. A complete upper (lower) semilattice (L, ) with a minimum element (maximum element ) is a complete lattice.
Once we have reminded the notions of lattice and semilattice we will pass to define what a multilattice is. To get this we will start with some preliminaries notions.
Definition 4. Let (P, ≤) be a poset and K ⊆ P , we say that: – K is called a chain if for every two elements x, y ∈ K we have that x ≤ y or y ≤ x. – K is called an antichain if none of its elements are comparable, i.e., for every x, y ∈ K we have that x y and y x. Definition 5. A poset (P, ≤) is called coherent if every chain has supremum and infimum.
Once we have introduced these notions we can give the definition of a complete multilattice.
Definition 6. A complete multilattice is a coherent poset without infinite antichains, (M, ≤), where for each subset, the set of its upper (lower) bounds has minimal (maximal) elements.
Each minimal(maximal) element of the upper (lower) bounds of a subset is called multisupremum(multinfimum). The set of all multisuprema(multinfima) will be denoted by multisup(multinf).
Example 1. An example of a multilattice is given in figure 1.
⊤ •❅
❅ a •❅ c •❍✟❍✟❍✟❍✟❍✟❅❍✟• d
• b ❅ ❅•
⊥
Fig. 1. Multilattice M6
In this multilattice we have that if we consider the subset {a, b} we have that multinf{a, b} = ⊥ and multisup{a, b} = {c, d} while if we consider as subset {c, d} we have that multinf{c, d} = {a, b} and multisup{a, b} = ⊤
We will remind now the notion of adjoint pair we will use later [
Now, we will pass to introduce a bit of fuzzy concept analysis. We will remind
first the notions of Galois connection and concept [
Definition 8. Let ↓ : P → Q and ↑ : Q → P be two maps between the posets (P, ≤) and (Q, ≤). The pair (↑, ↓) is called a Galois connection if: – p1 ≤ p2 implies p2↓ ≤ p1↓ for every p1, p2 ∈ P ; – q1 ≤ q2 implies q2↑ ≤ q1↑ for every q1, q2 ∈ Q; – p ≤ p↑↓ and q ≤ q↓↑ for all p ∈ P and q ∈ Q;
An interesting property of a Galois connection (↑, ↓) is that ↓ = ↓↑↓ and ↑ = ↑↓↑.
Definition 9. A pair (p, q) is called a concept if p↓ = q and q↑ = p.
If P and Q are lattices we have as well the following result:
Theorem 2. [
With all this notions now we can pass to the following section where we will present concept multilattices. 3
When working in concept analysis theory we always have two sets A and B representing the attributes and the objects together with a relation between them. In order to reach the concept multilattices these ones will be evaluated in complete multilattices.
The first result we obtain concerning concept analysis in multilattices will be crucial for our purpose. We will denote by M1A and M2B the sets of all mappings from A to M1 and from B to M2 respectively.
Theorem 3. Let (M1, ≤1) and (M2, ≤2) be two complete multilattices, A and B two sets and (↑, ↓) a Galois connection between M1A and M2B. If {(gi, fi)}i∈I is a set of concepts we have that multinf{fi↓ | i ∈ I} ⊆ (multisup{fi | i ∈ I})↓ multinf{gi↑ | i ∈ I} ⊆ (multisup{gi | i ∈ I})↑ (1) (2) where (multisup{fi | i ∈ I})↓ = {f m↓ult | fmult ∈ multisup{fi | i ∈ I}} and (multisup{gi | i ∈ I})↑ is given similarly. Proof. We will prove (1). Item (2) is proved in a similar way.
decreasing we have that fi↓↑ ≤2 g↑, but the pair (↑, ↓) is a Galois connection so we have that: Then there is fmult ∈ multisup{fi | i ∈ I} such that fmult ≤2 g↑. As ↓ is ↓ decreasing we have that g↑↓ ≤1 fmult using again that (↑, ↓) is a Galois connection we obtain that: fi ≤2 (fi)↓↑ ≤2 g↑
↓ g ≤1 g↑↓ ≤1 fmult (3) On the other hand, we have that fmult ∈ multisup{fi | i ∈ I}, so fi ≤2 fmult for every i ∈ I then, as ↓ is decreasing fmult ≤1 fi↓, for every i ∈ I, then fmult is a ↓ ↓ ↓ lower bound of the set {fi↓ | i ∈ I}, but g ∈ multinf{fi↓ | i ∈ I} and g ≤1 fmult, ↓ by (3). Therefore, by maximality of g we have that g = fmult.
multisup{fi | i ∈ I} such that g = f m↓ult, which leads us to the result. ⊔⊓
We cannot get always the equality in this theorem as we can see in the next example: Example 2. If we consider the multilattice of Fig. 1 and the folowing Galois connection, ↑ = ↓ : M 6 → M 6 defined as:
⊥↑ = ⊤ ; a↑ = b↑ = c↑ = c ; d↑ = ⊥ ; ⊤↑ = ⊥ It is routine to prove that the pair (↑, ↓) is a Galois connection.
On one hand, we obtain that
multinf{a↑, b↑} = multinf{c} = c However, on the other hand:
(multisup{a, b})↑ = ({c, d})↑ = {c↑, d↑} = {c, ⊥} which proves that we cannot get the equality always.
As a consequence of the previous theorem, we have that, given the set of all concepts C = {(g, f ) | f ∈ M1A, g ∈ M2B, g↑ = f, f ↓ = g}, and the ordering defined as (g1, f1) ≤ (g2, f2) if and only if g1 ≤1 g2 (if and only if f2 ≤2 f1), then (C, ≤) is a complete multilattice which is a result similar to Theorem 2, but now with respect to multilattices.
Theorem 4. If (M1, ≤1) and (M2, ≤2) be two complete multilattices, A and B two sets and (↑, ↓) a Galois connection between M1A and M2B, then we have that (C, ≤) is a complete multilattice where for every set of concepts {(gi, fi)}i∈I : multinf{(gi, fi)} = (multinf{gi}, (multinf{gi})↑) multisup{(gi, fi)} = ((multinf{fi})↓, multinf{fi}) (4) (5) Proof. If we prove that they are concepts, then it is obvious that they are the multisuprema and the multinfima due to the definition of the ordering in C.
By Theorem 3, we have that multinf{gi} ⊆ (multisup{fi})↓ (6) Hence, given g ∈ multinf{gi}, there exist f ∈ multisup{fi}, such that g = f ↓. Therefore, since (↑, ↓) is a Galois connection, g↑↓ = f ↓↑↓ = f ↓ = g.
Consequently, it is trivial that they are concepts. For the multisuprema the proof is similar. The proof of coherence and the non-existence of anti-chains comes directly from the definition of the ordering consider. ⊔⊓
At this point we could think what would happen whether the set of objects or the set of attributes are evaluated in a lattice while the other in a multilattice. The answer to this is given by the following corollary.
Proposition 1. Considering the framework of the previous theorem, if M1 or M2 is a lattice, then we have that C is a lattice.
Proof. If M1 is a lattice in the first equality of (4) the multinfimum becomes a singleton so it is indeed an infimum. Hence, every set has an infimum and so (C, ≤) is a complete lower semilattice. Therefore, we only have to prove that there is a maximum element ⊤C in C.
element ⊤ of M1 and consider the pair (g⊤, g⊤↑). If we prove that it is a concept then we have finished, since it is obvious that this element would be the maximum element in C.
We only have to prove that g⊤ = g⊤↑↓. As (↑, ↓) a Galois connection we have that g⊤ ≤1 g⊤↑↓ and, as g⊤(a) = ⊤ for every element a ∈ A, we have that the equality holds, i.e., g⊤ = g⊤↑↓.
The proof for M2 being a lattice is similar. ⊔⊓ The following section introduces a simple and particular context where we can get a Galois connection from an adjoint pair what allows us to obtain a concept multilattice. 4
The multilattice considered for the calculation in this example is the one given in Fig. 2 together with the following adjoint pair (&, ←).
x x & y = y
⊥ a if y = ⊤ if x = ⊤ if x ∈ {⊥, b} or y ∈ {⊥, b} otherwise ⊤ • • e ❅
❅ a •❅ c •❍✟❍✟❍✟❍✟❍✟❅❍✟• d
• b ❅ ❅•
⊥ It is routine calculation that (&, ←) is, indeed, an adjoint pair, in which & is commutative.
Imagine that we are going to travel to a city and we have to decide which hotel is the best for us. In this example, in order to no complicate the calculation we will taking into account seven different hotels, as objects, and two attributes, which will be price and situation. Hence, we have as set of objects B = {H1, H2, H3, H4, H5, H6, H7} and as set of attributes A = {price, situation}, both evaluated in M 6∗ and the M 6-fuzzy relation, R : A × B → M 6∗, between them, defined in Table 1
R H1 H2 H3 H4 H5 H6 H7
Evaluating the hotels in a multilattice comes from the idea that the hotels are ordered thinking of the number of stars they have. We can state, for example that any four-star hotel is better than any three-star hotel, but if both hotels are four-star ones we cannot distinguish between them at the beginning.
In the case of the situation, we have that we can say one situations are better than other but we cannot compare a situations that are for example one kilometer from the downtown but in different directions.
In the case of prizes, happens more or less the same because we cannot distinguish between prizes which are very similar.
If we see the relationship we have that R(H5, price) = b, R(H6, price) = a means that the fifth and the sixth hotels have more or less the same prices but we cannot decide which is best taking into account only their prizes.
For these reasons we have chosen multilattices for their evaluation.
We are trying to choose a hotel to stay in according to our preferences in prizes and situation.
It is easy to check that for the adjoint pair (&, ←) and for any mapping f : A → M 6∗ or g : B → M 6∗ the following sets has infimum.
Hence, we can define the next Galois connection {R(a, b) ← g(b) | b ∈ B} {R(a, b) ← f (a) | a ∈ A} g↑(a) = inf{R(a, b) ← g(b) | b ∈ B} f ↓(b) = inf{R(a, b) ← f (a) | a ∈ A} The proof of (↓, ↑) being a Galois connection follows directly from the existence of the infimum of these sets, that & is commutative and that the implication are decreasing in the second argument.
Therefore, from Theorem 4 we have an fuzzy concept multilattice and if our preferences are the following g(price) = a and g(situation) = d we have that for H1.
g↑(H1) = inf{d ← a, ⊥ ← d} = inf{⊤, b} = b And for the others: g↑(H2) = e , g↑(H3) = b , g↑(H4) = ⊤ , g↑(H5) = b , g↑(H6) = b , g↑(H7) = e On the other hand we have that f ↓↑(price) = inf{d ← b, c ← e, ⊤ ← b , a ← ⊤ b ← b, a ← b, a ← e} = inf{⊤, ⊤, a, ⊤, e, e} = a In a similar way we obtain that
f ↓↑(situation) = d Thus, according to out preference stablished by f , we have that our best choice is H4, although H2 and H7 are really good ones too.
A first approach to fuzzy formal concept multilattices has been presented. This paradigm arises as a more flexible setting than formal concept analysis framework, as the introduced motivating example shows.
Moreover, several properties have been proved. For example, we have checked that the concepts in the new framework form a complete multilattice and that if we impose that one of the set of attributes or objects are evaluated in a lattice and the other in a multilattice, then we obtain a complete lattice.
In the future, we will study general Galois connections which allows us to get more concept multilattices. We will focus as well, when we have these Galois connections, on getting a representation theorem for them to be able to get which multilattices are isomorphic to concept multilattices.