UnEncrypted

Proceedings of the 12th International Conference on Computational and Mathematical Methods in Science and Engineering, CMMSE 2012 July, 2-5, 2012.

On algebraic properties of residuated multilattices and the adequate definition of filter

I.P. Cabrera1, P. Cordero1, G. Guti´errez1, J. Mart´ınez1 and

M.Ojeda-Aciego1

1 Department of Applied Mathematics, University of M´alaga, Spain

emails: ipcabrera@uma.es, pcordero@uma.es, ggutierrez@uma.es, jmartinezd@uma.es, aciego@uma.es

Abstract

We continue the exploration of the residuated operations in the framework of multilattices. New algebraic properties of residuated multilattices are obtained, together with a study of the di erent possible approaches to the notion of filter of a residuated multilattice, and propose an adequate definition which combines the requirements associated to the underlying structures of pocrim and multilattice.

Key words: hyperstructures, pocrim, multilattices, filter, residuation.

1Introduction and preliminary definitions

We continue our study of the algebraic structure of residuated multilattice initiated in [3]. In this paper, we will introduce new algebraic results that allow us to generalize the main properties of residuated lattices, as those introduced in [4]. Moreover, due to the fact that any residuated multilattice combines the structures of multilattice and pocrim, it is possible to use the notion of filter on the multilattice, filter on the pocrim, or give a new definition that combines both. These new properties play an important role so that we can obtain a suitable generalization of the concept of filter.

In order to make this paper as self-contained as possible, we will recall a commonly considered algebraic structure, that is, a partially ordered commutative residuated integral monoid (pocrim) [2].

Algebraic properties of residuated multilattices and the definition of filter

Definition 1 A tuple A = (A, ≤, , →, ) is said to be a partially ordered commutative residuated integral monoid, briefly a pocrim, if, for every a, b, c A, the following properties hold:

• (A, , ) is a commutative monoid with neutral element

• (A, ≤) is a partially ordered set with maximum .

• the operations and → satisfy the adjointness condition, that is a c ≤ b if and only if c ≤ a → b.

A pocrim A is said to be a residuated lattice if (A, ≤) is a lattice. Moreover, a residuated lattice in which coincides with the meet operation is said to be a Heyting algebra.

Monotonicity of the ordering relation ≤ wrt follows as a consequence of the definition. Specifically, it holds that x ≤ y implies x z ≤ y z.

It is well-known that residuated lattices are considered to be the algebraic structures of substructural logics [6, 8, 12], which are logics without some of the structural rules of logic: weakening, contraction, or associativity.

We focus here on some extensions of the previously defined notions, by considering a partially-ordered set together with two non-deterministic operations which generalize the supremum and the infimum by weakening the restrictions imposed on a (complete) lattice, namely, the “existence of least upper bounds and greatest lower bounds” is relaxed to the “existence of minimal upper bounds and maximal lower bounds”. Specifically, a multisupremum of a and b is defined as a minimal element of the set of upper bounds of a and b, we write a b to refer to the set of all the multi-suprema of a and b; the notion of multiinfimum a b is introduced similarly. Now, we can proceed with the formal definition of multilattice and related structures.

Definition 2

• A poset (M, ≤) is said to be a multilattice if for all a, b, x M with a ≤ x and b ≤ x, there exists1 z a b, such that z ≤ x; and, similarly, for all a, b, x M with a ≥ x and b ≥ x, there exists z a b, such that z ≥ x.

• A multilattice is said to be full if a b = and a b = for all a, b M.

The notion of multilattice was introduced originally by Benado [1], and further studied by Hansen [7], who proposed an algebraic equivalent definition of multilattice. More recently, another algebraic formalisation of the notion of multilattice was introduced in [9,10]

1Note that the definition is consistent with the existence of two incomparable elements without any multisupremum. In other words, a b, and also a b, can be empty.

I.P. Cabrera, P. Cordero, G. Gutierrez,´ J. Mart´ınez, M. Ojeda-Aciego

as a theoretical tool to deal with some problems in the theory of mechanised deduction in temporal logics. Multilattices arise as well in other research areas, such as fuzzy extensions of logic programming [11]: for instance, one of the hypotheses of the main termination result for sorted multi-adjoint logic programs [5] can be weakened only when the underlying set of truth-values is a multilattice (the question of providing a counter-example on a lattice remains open).

Definition 3 A residuated multilattice is a pocrim whose underlying poset is a multilattice. If, in addition, there exists a bottom element, we say that the residuated multilattice is bounded.

Notice that every residuated multilattice is full: for all a, b M we have that a, b ≤ and, therefore, a b = . Furthermore, a b ≤ a, and a b ≤ b, hence a b = .

It is convenient to remark that any finite poset is actually a multilattice, hence the only proper examples of pocrims which are not multilattices have to be infinite.

2Algebraic properties of residuated multilattices

Let us recall that if (A, ≤) is a poset, we will denote by ↑ and ↓ the upper and lower closure operators respectively. That is, for all B A

So, we can generalize in terms of residuated multilattice the properties of residuated lattices presented in [4]:

Lemma 1 Let M be a residuated multilattice, then the following items hold:

1. (x y) (x z) = minimals{x (y z)} for all x, y, z M.

2.x y (x y)↓ for all x, y M.

3.x (x → y) (x y)↓ for all x, y M.

4.x → y [x → (x y)] for all x, y M.

The following result relates to the operators and .

Proposition 1 Let M a residuated multilattice, then the following holds for all x, y, z M:

1. z (x y) [(z x) (z y)]↓

Algebraic properties of residuated multilattices and the definition of filter

2. [(x y) (x z)] x (y z) [(x y) (x z)]↑ The result below relates → to the operators and .

Proposition 2 Let M a residuated multilattice, the following holds for all x, y, z M:

1.[(x → z) (y → z)] (x y) → z [(x → z) (y → z)]↓

2.[(z → x) (z → y)] z → (x y) [(z → x) (z → y)]↓

3.[(x → y) (y → x)] (x y) → (x y) [(x → y) (y → x)]↓

The last result in this section has no counterpart in the case of residuated lattices.

Proposition 3 Let M a residuated multilattice, then the following holds for all x, y, z M:

1.(x y) → z [(x → z) (y → z)]↑

2.z → (x y) [(z → x) (z → y)]↑

3The structure of filter in a residuated multilattice

Concerning applications in logic and artificial intelligence, the notions of filter and deductive system [13], closely related to modus ponens, deserve to be studied in depth.

Definition 4 Given A = (A, ≤, , →, ) a pocrim, a non-empty subset F A is said to be a filter if the following conditions hold:

i)if a, b F , then a b F

ii)if a ≤ b and a F , then b F .

Definition 5 Given A = (A, ≤, , →, ) a pocrim, a non-empty subset F A is said to be a deductive system if

i)F and

ii)a → b F and a F imply b F .

Proposition 4 The definitions of filter and deductive system are equivalent.

Proof:

I.P. Cabrera, P. Cordero, G. Gutierrez,´ J. Mart´ınez, M. Ojeda-Aciego

1.Firstly, let us assume that F is a filter. Let x F . As x ≤ , then F .

Moreover, if a F and a → b F , then a (a → b) F . As a (a → b) ≤ b, then b F .

2. Now let us assume that F is a deductive system. a ≤ b a → b = . As F , a → b F and a F we have that b F .

Moreover let a, b F . As a b ≤ a b b ≤ a → (a b) and b F then a → (a b) F . Now, as a F we have that a b F .

There exist several ways to give a definition for the notion of filter of a multilattice. In this section, we introduce the one which is more suitable for extending the classical results about congruences and homomorphisms.

Definition 6 Let (M, , ) be a multilattice. A non-empty set F M is said to be a filter if the following conditions hold:

1.a, b F implies = a b F .

2.a F implies a b F for all b M.

3.For all a, b M, if (a b) ∩ F = then a b F .

Due to the fact that any residuated multilattice combines the structures of multilattice and pocrim, it is possible to use the notion of filter on the multilattice, filter on the pocrim, or give a new definition that combines both. These three notions are not equivalent. To distinguish them, we will write p-filter to denote a filter of the pocrim and m-filter, a filter of the multilattice. We introduce now the notion of filter in a residuated multilattice.

Definition 7 Let M be a residuated multilattice. A non-empty subset F M is said to be a filter if it is a deductive system and the following condition hold: a → b F implies a b → b F and a → a b F .

Theorem 1 Let M be a residuated multilattice and F a deductive system. Then, F is a filter if and only if F is an m-filter and the following conditions hold:

i) for all x, y a b, if x → y F then y → x F .

ii) for all x, y a b, if x → y F then y → x F .

Algebraic properties of residuated multilattices and the definition of filter

Proof: Suppose that F is a filter and let a, b F . As a ≤ b → a, then b → a F . Therefore, b → a b F . So, given x a b, as b → x F and b F , then x F . On the other hand, suppose that there exists x (a b) ∩ F . If a b is a singleton, then, trivially,

a b F . Otherwise, let y a b such that x = y. As a, b ≤ x, y, there exist two di erent elements a , b x y such that a ≤ a and b ≤ b . Observe that = a → x = a → y F .

As x F and x ≤ y → x, then y → x F . Thus, y → x y F which implies that y → a , y → b F . From y ≥ a , we obtain y → b ≤ a → b and so, a → b F .

Therefore, a b → b F , which leads to x → b F . As also = b → y F , then x → y F . Finally, as x F , so y F .

Suppose now that F is an m-filter in which both conditions i) and ii) hold and let a, b M such that a → b F . By 2, item [i)], it holds

[(a → b) (b → b)] (a b) → b

thus, there exists x1 a b such that a → b = x1 → b. If a b is a singleton, the proof is over. Otherwise, given x2 a b, since = b → x2 F and x1 → b F , we have that x1 → x2 F . Using hypothesis, it implies that also x2 → x1 F and again with x1 → b F , we obtain that x2 → b F .

4Conclusions and future work

We have introduced new properties that allow us to obtain a suitable generalization of the concept of filter. As future work, on the one hand, we will focus on the study of homomorphism and congruence in order to guarantee that the classical relationship between these three concepts still holds in the framework of residuated multilattices. On the other hand, the specific form of the new properties introduced in Section 2 strongly suggests a possible interpretation in terms of rough sets, which will be studied later.

Acknowledgements

Partially supported by projects TIN2009-14562-C05-01 (Science Ministry of Spain), and P09-FQM-5233 (Junta de Andaluc´ıa).

References

[1] M. Benado. Les ensembles partiellement ordonn´es et le th´eor`eme de ra nement de

ˇ ˇ

Schreier. I. Cehoslovack. Mat. Z., 4(79):105–129, 1954.

I.P. Cabrera, P. Cordero, G. Gutierrez,´ J. Mart´ınez, M. Ojeda-Aciego

[2]W. J. Blok and J. G. Raftery. Varieties of commutative residuated integral pomonoids and their residuation subreducts. Journal of Algebra, 190:280–328, 1997.

[3]I. P. Cabrera, P. Cordero, G. Guti´errez, J. Mart´ınez, and M. Ojeda-Aciego. Residuated operations in hyperstructures: residuated multilattices. In J. Vigo-Aguiar, editor,

Proceedings of the 11th International Conference on Computational and Mathematical Methods in Science and Engineering., volume 1, pages 259–266, 2011.

[4]L. C. Ciungu. On the lattice of congruence filters of a residuated lattice. Annals of University of Craiova, 33:189–207, 2006.

[5]C. Dam´asio, J. Medina, and M. Ojeda-Aciego. Termination of logic programs with imperfect information: applications and query procedure. Journal of Applied Logic, 5(3):435–458, 2007.

[6]N. Galatos, P. Jipsen, T. Kowalski, and H. Ono. Residuated lattices: an algebraic glimpse at substructural logics, volume 151 of Studies in Logic and the Foundations of Mathematics. Elsevier, 2007.

[7]D. J. Hansen. An axiomatic characterization of multilattices. Discrete Math., 33(1):99– 101, 1981.

[8]T. Kowalski and H. Ono. Fuzzy logics from substructural perspective. Fuzzy Sets and Systems, 161(3):301–310, 2010.

[9]J. Mart´ınez, G. Guti´errez, I. P. de Guzm´an, and P. Cordero. Generalizations of lattices via non-deterministic operators. Discrete Math., 295(1-3):107–141, 2005.

[10]J. Mart´ınez, G. Guti´errez, I. P. de Guzm´an, and P. Cordero. Multilattices via multisemilattices. In Topics in applied and theoretical mathematics and computer science, Math. Comput. Sci. Eng., pages 238–248. WSEAS, Athens, 2001.

[11]J. Medina, M. Ojeda-Aciego, and J. Ruiz-Calvi˜no. Fuzzy logic programming via multilattices. Fuzzy Sets and Systems, 158(6):674–688, 2007.

[12]H. Ono. Substructural logics and residuated lattices—an introduction in trends in logic: 50 years of studia logica. Studia Logica, 50:177–212, 2003.

ˇ

[13] J. Rach˚unek and D. Salounov´. Filter theory of bounded residuated lattice ordered monoids. Journal of Multiple-Valued Logic and Soft Computing, 16(3-5):449–465, 2010.

Proceedings of the 12th International Conference on Computational and Mathematical Methods in Science and Engineering, CMMSE 2012 July, 2-5, 2012.

Graph operations and Lie algebras

Jos´e C´aceres1, Manuel Ceballos2, Juan N´u˜nez2, Mar´ıa Luz Puertas1 and

1 Departamento de Estad´ıstica y Matem´atica Aplicada, Universidad de Almer´ıa.

2 Departamento de Geometr´ıa y Topolog´ıa, Facultad de Matem´aticas. Universidad de Sevilla.

3 Dpto. de Econom´ıa, M´etodos Cuantitativos e Historia Econ´omica, Escuela Polit´ecnica Superior. Universidad Pablo de Olavide.

emails: jcaceres@ual.es, mceballos@us.es, jnvaldes@us.es, mpuertas@ual.es, aftenorio@upo.es

Abstract

In this paper, we deal with vertex amalgamation on graphs and combinatorial structures in order to obtain some criteria to determine when there exists a Lie algebra associated with a combinatorial structure arising from this operation. Moreover, we show an algorithmic method to implement it.

Key words: Digraph, Combinatorial structure, Lie algebra, Combinatorial operations, Algorithm.

MSC 2000: 17B60, 05C25, 05C20, 05C90, 68W30, 68R10, 05C85.

1 Introduction

Finding relations between di erent fields of Mathematics is an important goal in mathematical research. Both Lie Theory and Graph Theory are running in a high level due to their several applications in Engineering, Physics and Applied Mathematics, in addition to their theoretical study. There exists a close relation between both theories. For example, graphs have been used to study semisimple Lie algebras, since trees perform an important

Graph operations and Lie algebras

role to determine the Dynkin diagrams associated to such algebras [8]. Graph Theory is also applied to study the representation of finite-dimensional algebras [7].

Our main goal is to make progress in the link between Lie algebras and combinatorial structures. Hence, we are proceeding with previous works [1, 2, 3, 4, 6] in the literature opening this research line. This time, we study the translation of vertex amalgamation on graphs and combinatorial structures into the language of Lie algebras.

The structure of this paper is the following: after reviewing some well-known results on Lie and Graph Theory in Section 2, Section 3 recalls the mapping introduced in [1] to associate combinatorial structures with Lie algebras. Next, in Section 4 we study the vertex amalgamation studying some criteria under which structures obtained from this operation are associated with Lie algebras. Finally, Section 5 presents an algorithmic method related to this operation checking if the graph obtained is associated with a Lie algebra.

2Preliminaries

For a general overview on Lie algebras and graph theory, the reader can consult [9, 5].

Definition 1 A Lie algebra g is a vector space with a second bilinear inner composition law ([·, ·]) called the bracket product or Lie bracket, which satisfies [X, X] = 0, X g and [[X, Y ], Z] + [[Y, Z], X] + [[Z, X], Y ] = 0, X, Y, Z g. The last expression is called the Jacobi identity.

Given a basis {ei}ni=1 of g, its structure (or Maurer-Cartan) constants are defined by

[ei, ej ] = chi,j eh, for 1 ≤ i < j ≤ n.

Definition 2 Given a Lie algebra g, its center is Z(g) = {X g | [X, Y ] = 0, Y g}.

Definition 3 A graph is a ordered pair G = (V, E), where V is a non-empty set of vertices and E is a set of unordered pairs (edges) of two vertices. If the edges are ordered pairs of vertices, then the graph is named digraph.

Definition 4 Let G = (V, E) be a graph. For a vertex v V , the (open) neighbourhood of v in G is the vertex subset N(v) = {w V | (v, w) E}. Two vertices u, v V are twins if they have the same neighbourhoods; i.e. N(u) = N(v).

Definition 5 Given a digraph G = (V, E), a vertex v V is a sink (resp. a source) if all the edges incident with v are oriented towards v (resp. oriented from v). This definition is illustrated in Figure 1.

J. Caceres,´ M. Ceballos, J. Nu´nez,˜ M.L. Puertas, A. F.Tenorio

Figure 1: Example of sinks and sources, respectively.

Definition 6 Given n N, Pn is a weighted digraph of n vertices alternating sources with sinks.

3Associating combinatorial structures with Lie algebras

structure built according to the following steps in the method introduced in [1]

a)Draw vertex i for each ei B.

b)Given three vertices i < j < k, draw the full triangle ijk if and only if (cki,j , cij,k, cji,k) = (0, 0, 0). Then, the edges ij, jk and ik have weights cki,j , cij,k and cji,k, respectively.

b1) Use a discontinuous line (named ghost edge) for edges with weight zero.

b2) If two triangles ijk and ijl with 1 ≤ i < j < k < l ≤ n satisfy cki,j = cli,j , draw only one edge between vertices i and j shared by both triangles (see Figure 2).

c)Given two vertices i and j with 1 ≤ i < j ≤ n and such that cii,j = 0 (resp. cji,j = 0), draw a directed edge from j to i (resp. from i to j), as can be seen in Figure 3.