Research Article
Lattice in Pre A*-Algebra
Andhra Loyola Institute of Engineering and Technology, Vijayawada-8. A.P. India
J.V. Rao
Mekelle University Main Campus, P.O. Box No. 231, Mekelle, Tigrai, Ethiopia
The study lattice theory had been made by Birkhoff (1948). In a draft paper, the equational theory of disjoint alternatives, Manes (1989) introduced the concept of Ada, (A, ∧, ∨, (-)', (-)π, 0, 1, 2) which however, differs from the definition of the Ada by Manes (1993). While the Ada of the earlier draft seems to be based on extending the If-Then-Else concept more on the basis of Boolean algebras, the later concept is based on C-algebra (A, ∧, ∨, (-)~) introduced by Guzman and Squier (1990).
Koteswara Rao (1994) firstly introduced the concept of A*-algebra (A, ∧, ∨,*,(-)~, (-)π, 0, 1, 2) and studied the equivalence with Ada by Manes (1989), C-algebra by Guzman and Squier (1990) and Ada by Manes (1993) and its connection with 3-ring, stone type representation and introduced the concept of A*-clone and the If-Then-Else structure over A*-algebra and ideal of A*-algebra. Venkateswara Rao (2000) introduced the concept Pre A*-algebra (A, ∧, ∨, (-)~) analogous to C-algebra as a reduct of A*-algebra. Recently Pre A*-algebra had been studied by Chandrasekhararao et al. (2007).
Definition: An algebra (A, ∧, ∨, (-)~) where A is non-empty set with 1, ∧, ∨ are binary operations and (-)~ is a unary operation satisfying:
• | x~ ~ = x, ∀, x εA, |
• | x ∧ x =x, ∀xεA |
• | x ∧ y = y ∧ x, ∀x, yεA |
• | (x ∧ y)~ = x~ v y~, ∀ x, y εA |
• | x ∧ (y ∧ z) = (x ∧ y) ∧ z, ∀x, y, zεA |
• | x ∧ (y ∧ z) = (x ∧ y)∨(x ∧ z), ∀x, y, zεA |
• | x ∧y = x ∧ (x~ v y), ∀x, y, z εA |
is called a Pre A*-algebra.
Table 1: | Example of a Pre A*-algebra |
Example: 3 = {0,1,2} with operations ∧,∨,(-)~ defined below which is shown in Table 1 is a Pre A* - algebra.
Note: The elements 0,1,2 in the above example satisfy the following laws:
(a) | 2~ = 2 |
(b) | 1 Λ x = x for all x ε 3 |
(c) | 0 v x = x, ∀ x ε 3 |
(d) | 2 ∧ x = 2 v x=2, ∀ x ε 3. |
Example: 2 = {0,1} with operations ∧,∨ , (-)~ is a Pre A*-algebra.
Note:
• | (2, ∧ , ∧, (-)~) is a Boolean algebra. So every Boolean algebra is a Pre A* algebra |
• | The identities x~~= x, ∀, xεA and (x∧y)~ = x~∨y~, ∀x, yεA imply that the varieties of Pre A* -algebras satisfies all the dual statements of x~~= x, ∀, xεA to x∧y = x∧ (x~∨ y), ∀xy, zεA. |
PRE A*-ALGEBRA AS A POSET
We recall the definition of a partial ordering ≤ on Pre A*-algebra and recall the theorem Pre A*-algebra as a Poset. Also we recall the theorem that if A is a Pre A*-algebra then (A, ≤) is a Lattice.
Definition: Let A be a Pre A*-algebra. Define ≤ on A by x≤y if and only if x ∧ y = y ∧ x = x, ∀ x, y εA. The defined ≤ is said to be partial ordering on Pre A*-algebra A.
Lemma: If A is a Pre A*-algebra then (A, ≤) is a Poset.
(a) | Theorem: In a Poset (A, ≤) with 1, for any x, yεA, infemum {x, y} = x y |
(b) | Theorem: In a poset (A, ≤) with 1, for any x, yε B (A). Supremum {x, y} = x ∨ y where B (A) = {xεA/x∨x~ =1} |
(c) | Theorem: If A is Pre A*-algebra and x ∧ (x ∨ y) = x for all x,y εA then (A, ≤) is a lattice |
Proof: By theorem (a) we have every pair of elements have greatest lower bound and if x ∧ (x ∨ y)=x for all x,y εA, then by theorem (b), we have every pair of elements have least upper bound.
Hence (A, ≤) is a lattice.
LATTICE IN PRE A*-ALGEBRA
We define a lattice in a Pre A*-algebra. We give an axiom for a Pre A*-algebra to become a lattice. We define semi lattice, sub lattice, bound elements in a lattice, bounded lattice, distributive lattice, modular lattice in a Pre A*-algebra. We define atoms, dual atoms, irreducible elements in a Pre A*-algebra. We prove representation theorem in Pre A*-algebra also we prove a Pre A*-homomorphism, f: A → P (B) is an isomorphism, where P (B) is the set of all subsets of a Pre A*-algebra B.
Lattice in pre A*-algebra: Definition: Let A be a Pre A*-algebra. A non-empty subset L of a Pre A*-algebra A, equipped with two binary operations meet (∧) and join (∨) which assign to every pair a, b of the elements of L, uniquely an element a ∧ b as well as an element a ∨ b in such a way that the following axioms holds.
(i) | a ∧ (b ∧ c) = (a ∧ b) ∧ c, ∀ a, b, c ε L (associative) |
(ii) | a ∧ b = b ∧ a, ∀ a, b ε L (commutative) |
(iii) | a ∧ a = a, ∀ aε L (idempotent) |
(iv) | If a ≤ a ∨ b then a ∧ (a ∨ b) = a, ∀ a, b ε L i.e., a ∧ b ≤ a then a ∨ (a ∧ b) = a) |
Note: For any subset [a, (a ∨ b)] in a Pre A*-algebra with a ≤ a ∨ b we have a ∧ (a ∨ b) = a which will be referred as absorption identity in L.
Note: The above axioms (i), (ii), (iii) holds with respect to ∨ also.
Note: The condition for a non-empty subset L of a Pre A*-algebra A to become a lattice is if a ≤ a ∨ b then a ∧ (a ∨ b) = a, ∀ a, b ε L.
Example: Let A be a Pre A*-algebra and 2 = {0,1} is a subset of A then 2 = {0,1} is a lattice.
Example: 3 = {0, 1, 2} is a subset of a Pre A*-algebra then 3 = {0, 1, 2} is a lattice.
Semi lattice in a Pre A*-algebra
Definition: A non-empty subset S of a Pre A*-algebra A equipped with a binary operation ∧ (∨) is said to be a semi lattice, if the following semi lattice axioms are satisfied.
• | ∧(∨) is associative ie. a ∧ (b ∧ c) = (a ∧ b) ∧ c, ∀ a, b, c ε S |
• | ∧(∨) is commutative i.e., a ∧ b = b ∧ a, ∀ a, b ε S |
• | ∧(∨) is idempotent i.e., a ∧ a = a, ∀ a ε S |
Theorem: In Pre A*-algebra A, (S, ∧) and (S, ∨) are semi lattices.
Proof: In Pre A*-algebra,
a ∧ (b ∧ c) = (a ∧ b) ∧ c, ∀ a, b, c ε A ((x∧ (y∧z) = (x∧y)∧z, ∀x, y, zεA) a ∧ b = b ∧ a, ∀ a, b εA (x∧y = y∧x, ∀x, yεA ) and a ∧ a = a, ∀ a ε A (x∧x = x, ∀ xεA) Hence (S, ∧) is a semi lattice. By the duality in A (S, ∨) is a semi lattice.
Theorem: In Pre A*-algebra A, (S, ∧, ∨) is a lattice.
Proof: In a Pre A*-algebra, a ∧ (b ∧ c) = (a ∧ b) ∧ c, ∀ a, b, c ε A (x ∧ (y ∧ z) = (x ∧ y) ∧ z, ∀ x, y, z ε A) a ∧ b = b ∧ a, ∀ a, b εA (x ∧ y = y ∧ x, ∀ x, yεA) and a ∧ a = a, ∀ a ε A (x∧(y∧z) = (x∧y) ∨ (x∨z) ∀x, y, zεA) Hence (S, ∧) is a semi lattice. By the duality in A, (S, ∨) is a semi lattice. F or any subset [a, a ∨ b] in a Pre A*-algebra A, if a ≤ a ∨ b then a ∧ (a ∨ b) = a, ∀ a, b ε L (i.e., a ∧ b ≤ a then a ∨ (a ∧ b) = a) Hence, in a Pre A*-algebra A, (S, ∧, ∨) is a lattice.
Theorem: In Pre A*-algebra A, the class of semi lattices can be equationally defined as the class of all semi group satisfying the commutative and idempotent laws.
Proof: Let (S, ∧, ∨) be a semi lattice in a Pre A*-algebra A. By the definition of semi lattice we have
• | ∧ (∨) is associative i.e. a ∧ (b ∧ c) = (a ∧ b) ∧ c, ∀ a, b, c ε S |
• | ∧(∨) is commutative i.e., a ∧ b = b ∧ a, ∀ a, b ε S |
• | ∧(∨) is idempotent i.e., a ∧ a = a, ∀ a ε S |
Hence (S, ∧) as well as (S, ∨) is a semi-group satisfying commutative and idempotent laws. Therefore (S, ∧ (∨)) is a semigroup satisfying the commutative and idempotent laws.
Therefore, (S, ∧) as well as (S, ∧) is a semigroup satisfying the commutating and idempotent laws.
Converse: (S, ∧) as well as (S, ∨) is a semi-group satisfying commutative and idempotent laws. By the definition of Pre A* -algebra A:
• | a ∧ (b ∧ c) = (a ∧ b) ∧ c, ∀ a, b, c ε A (x ∧ (y ∧ z) = (x ∧ y) ∧ z, ∀ x, y, z ε A) |
• | a ∧ b = b ∧ a, ∀ a, b εA (x ∧ y = y ∧ x, ∀ x, y εA) |
• | and a ∧ a = a, ∀ a ε A (x ∧ x = x, ∀ x ε A) |
• | Hence, ∧(∨) is associative, commutative and idempotent. |
• | Hence (S, ∧, ∨) is a Semi-lattice in a Pre A*-algebra A. |
Sublattice in a Pre A*-algebra
Definition: Let A be a Pre A*-algebra suppose L1 be a subset a lattice L. We say L1 is a sublattice of L if L1 itself is a lattice (with respect to the operations of L).
Fig. 1 (A-B): | Examples of a bounded lattice |
Example: 3 = {0, 1, 2} is a subset of a Pre A*-algebra then 3 = {0, 1, 2} is a sub lattice.
Bound elements in a lattice (L, ≤) and Bounded lattice L in a Pre A* - algebra
Definition: A lattice (L, ≤) in a Pre A* - algebra is said to have a lower bound α if for any element a in L, we have α≤a, Analogously, L is said to have an upper bound i if for any a in L, we have a ≤ i.
Note: α may be 0 or 2.
Example 1: For any subset L = {0, 1, 2} of a Pre A*-algebra with 1, 0, 2 which is shown in Fig. 1a, here 2 is the lower bound and 1 is the upper bound. Hence, L = {0, 1, 2} is a bounded lattice.
Example 2: The following lattice shown in Fig. 1b is the bounded lattice. Here, 2 is the lower bound for a, b, c which is the least element in this lattice and i is the upper bound for a, b, c which is the greatest element of this lattice.
Bounded Lattice (L, ≤) in a Pre A* - algebra A: Definition: Let A be a Pre A*-algebra and L is a subset of A then.
We say that L is bounded if L has both a lower bound α and an upper bound I. In such a lattice we have the identities a ∧ i = a, a ∧ α = α.
Note: In a Pre A*- algebra A we have a ∧ 1 = a, a ∧ 2 = 2, ∀aεL
i.e., a ∨ α = a, ∀aεL. Since α may be 0 or 2.
Example: The Hauss diagram shown in Fig. 1a, is the bounded lattice in a Pre A*-algebra.
Theorem: Let A be a Pre A*-algebra and L is a subset of A. Then every finite lattice L in a Pre A*- algebra A is bounded.
Proof: Let L = {a1, a2, . ar} be a subset of a Pre A*-algebra with the binary operations ∧ , ∨ in L which is finite.
Since ∧ (a1,a2)=a1∧a2=infemum{a1,a2} and
Since ∨ (a1,a2)=a1∨a2 =sup{a1,a2}
Then (a1 ∨a2 ∨
∨an) and (a1 ∧ a2∧
. an)
are upper bound and lower bound for L let those be α, i, respectively. Thus, we have L is bounded in A.
Distributive Lattice L in a Pre A* - algebra A: Definition: Let A be a Pre A*-algebra and L is subset of A. Then (L, ∧, ∨) is said to be distributive if any elements a, b, c in L we have the distributive law:
Lemma: In the Poset (A, ≤),
Proof: Define ≤ in A as a≤b ⇔ a ∧ b = a (i.e., a∨b = b). Suppose a ≤ b then b ∧ a = a.
Now b ∧ (a ∨ c) = (b ∧ a) ∨ (b ∧ c) = a ∨ (b ∧ c) (by (x ∧ (y ∧ z) = (x ∧ y) ∨ (x ∨ z) , ∀x, y, zεA).
Modular lattice in a Pre A* - algebra
Definition: Let A be a Pre A*-algebra. A sub set L of A is said to be a modular lattice if:
Example: The lattice shown in Fig. 2a, is the modular lattice. Since 2≤a, 2∨ (a ∧ i) = a ∧ (2 ∨ i).
Theorem: Let A be a Pre A*algebra. Then a sub set L of A is a modular lattice.
Proof: Since (L, ≤ )is a lattice. By lemma of an atom, x ≤ y ⇒ x ∨ (y ∧ z) = y ∧ (x ∨ z), ∀ x, y, z ε A. Hence, L is a modular lattice.
Definition of least and greatest elements in a lattice (L, ∧, ∨): Let A be a Pre A*-algebra and (L, ∧, ∨) be any lattice in A. An element α ε L is called least element if α ≤ x, ∀ x ε L. Similarly, i ε L is called greatest element if x ≤ i, ∀ x ε L.
Note: The least element 2 and the greatest element i of a lattice L satisfies the following identifies.
Atoms and dual atoms in a Pre A*-algebra
Definition of atom: Let L be a subset of a Pre A*-algebra A. Then an element p of a bounded below lattice L in a Pre A*-algebra A is called an atom, if α p (α is covered by p).
That is, in a Pre A*-algebra A, 2 is atom with respect to ∧ if 2 p, 0 is atom with respect to ∨ if 0 p.
If there exists an atom p, for each element a ≠ α of L such that a ≥ p. Then we say that L is an atomic lattice in a Pre A*-algebra A.
Fig. 2 (A-C): | Example of atomic and dual atomic lattices |
Example: In the lattice shown in Fig. 2a, a, b, c are atoms and this lattice is atomic. | |
In the lattice shown in Fig. 2b a is the only one atom and this lattice is also atomic. In the lattice shown in Fig. 2c a, c are atoms and this lattice is also atomic. |
Theorem: Let A be a Pre A*-algebra and L be a subset of A then every finite lattice (L, ∧, ∨) in a Pre A*-algebra A which is bounded below is atomic.
Proof: Let L be a subset of a Pre A*-algebra A and L is a finite lattice with binary operations ∧,
Then an element p of a bounded below lattice L in a Pre A*-algebra A is called an atom, if α p (α is covered by p).
If there exists an atom p, for each element a ≠ α of L such that a ≥ p. Then, we say that L is an atomic lattice in a Pre A* - algebra A. Hence, L is atomic lattice in a Pre A* - algebra A. It is true for every such a finite lattice L.
Dual atom
Definition: Let L be a subset of a Pre A*-algebra A. Then an element q of a bounded above lattice L in a Pre A*-algebra is called dual atom if q i (q is covered by i). If there exists a dual atom q for any element a ≠ i of L such that a ≤ q. Then we say that L is dual atomic lattice.
Example: Consider the diagrams:
• | In Fig. 2a; a, b, c are dual atoms |
• | In Fig. 2b; b, c are dual atoms |
• | In Fig. 2c; d, e, b are the dual atoms |
All these are dual atomic lattices in a Pre A* - algebra.
Join irreducible elements in Pre A* - algebra
Definition: Let A be a Pre A*-algebra and L be a lattice in A with a lower bound α. An element a in L is said to be join irreducible if a = x ∨ y ⇒ a = x or a = y.
Example: 2 is join irreducible in a Pre A*-algebra.
Example: In Fig. 1, every element in this chain is join irreducible.
Note: In Pre A*-algebra, we have:
(i) | The least element of a lattice if exists then it is join irreducible. |
(ii) | The greatest element if exists then it is meet irreducible |
(iii) | The atom of a lattice is join irreducible. |
(iv) | The dual atom of a lattice is meet irreducible |
Theorem: Let A be a Pre A*-algebra and L be a subset of A. Then in a finite lattice L if a ε L then we can write a as the join of irredundant join irreducible elements.
Proof: Let L be a subset of a Pre A*-algebra A. Assume that L be a finite lattice. Let H be the set of all elements of L which cannot be represented as the join of finite number of irredundant join irreducible elements. Now we will show that H is empty. Suppose if possible H is non-empty.
Then H does not contain any irredundant join irreducible elements, since if a is join irreducible element and aε H then a = a ∨ a and a = a ∨ α (if α, a ε H) are two representations of the element a which is contradicting the definition of H.
Hence, every element a ε H is the join of finite number of join irreducible elements. Since, H is finite, then the set H contains atleast one minimal element, say m. Clearly m cannot be join irreducible:
Hence, H is empty. |
Therefore, in a finite lattice L if a ε L then we can write a as the join of irredundant join irreducible elements.
Theorem: Let L be a subset of a Pre A*-algebra A and L is finite distributive lattice in a Pre A*- algebra. Then every element a in L can be written uniquely as the join of irredundant join irreducible elements.
Proof: Let a subset L of A be a finite distributive lattice in a Pre A*-algebra A.
Since, L is finite we can write a as the join of irredundant join irreducible elements (by above theorem) Thus, we need to prove uniqueness.
where, the bs are irredundant ad join irreducible and the cs are irredundant and join irreducible.
For any given i we have:
Hence,
Since bi is join irreducible, there exists j such that bi = bi ∧ cj, and so bi ∧ cj. By a similar argument, for cj there exists bk such that cj ∧ bk. Therefore, bi ∧ cj ∧ bk which gives bi = cj = bk since the bs are irredundant. Thus, the representation for a is unique.
Representation theorem in a Pre A*-algebra: Let A be a Pre A*-algebra and α be a least element in A. Then each x ≠ α in A can be written uniquely as the join of atoms.
Proof: Let A be a finite Pre A*-algebra. Recall that an element a in A is an atom if a immediately succeeds α, that α a.(α is covered by a).
Let B be the set of atoms of A and let P (B) be the Pre A*-algebra of all subsets of the set B of atoms.
Then by theorem, each x ≠ α in A can be expressed uniquely as the join irreducible elements and since the join irreducible elements are atoms, i.e., elements of B.
Meet irreducible elements in a Pre A* - algebra
Definition: Let A be the Pre A*-algebra and a subset L of A be a lattice in A with an upper bound i . An element a in L is said to be meet irreducible if:
Example: In Fig. 1, every element in this chain is meet irreducible.
Theorem: Let A be a Pre A*-algebra and L be a subset of A. Then in a finite lattice L if a ε L then we can write a as the meet of irredundant meet irreducible elements.
Proof: Let L be a subset of a Pre A*-algebra A. Assume that L be a finite lattice.
Let H be the set of all elements of L which cannot be represented as the meet of finite number of irredundant meet irreducible elements. Now we will show that H is empty.
Suppose if possible H is non-empty. Then, H does not contain any irredundant meet irreducible elements, since if a is meet irreducible element and aε H then a = a ∧ a and a = a∧i(if i, aε H) are two representations of the element a, which is contradicting the definition of H.
Hence, every element aε H is the meet of finite number of meet irreducible elements. Since, H is finite, then the set H contains atleast one maximal element, say m. Clearly m cannot be meet irreducible.
Hence, H is empty. Therefore, in a finite lattice L if a ε L then we can write a as the meet of irredundant meet irreducible elements.
Theorem: Let L be a subset of a Pre A*- algebra A and L is finite distributive lattice in a Pre A*-algebra. Then every element a in L can be written uniquely as the meet of irredundant meet irreducible elements.
Proof: Let a subset L of A be a finite distributive lattice in a Pre A* - algebra A.
Since, L is finite we can write a as the meet of irredundant meet irreducible elements (by theorem).
Thus, we need to prove uniqueness.
Suppose a = b1∧b2∧
..∧br = c1∧c2∧
. ∧cs.
where the bs are irredundant and meet irreducible and the cs are irredundant and meet irreducible For any given i we have:
Hence,
Since bi is join irreducible, there exists j such that bi = bi ∧ cj, and so bi ≤ cj. By a similar argument, for cj there exists bk such that cj ≤ bk. Therefore, bi ∧ cj ≤ bk which gives bi = cj = bk since the bs are irredundant Thus, the representation for a is unique.
Pre A*-Homomorphism
Definition: Let (A1, ∧, ∨, (-)~) and (A2, ∧, ∨, (-)~) be two Pre A*-algebras. A mapping f : A1 → A2 is called an Pre A*-homomorphism, if:
The homomorphism f : A1 → A2 is onto, then f is called epimorphism. The homomorphism f : A1 → A2 is oneone, then f is called monomorphism.
The homomorphism f : A1 → A2 is one-one and onto then f is called an isomorphism and A1, A2 are isomorphic, denoted by A1 A2.
Theorem: The mapping f : A → P(B) is an isomorphism.
Proof: Consider the function f : A → P(B) defined by f (x) = {a1, a2, ar}. The mapping is well defined since the representation is unique. To Verify that f is a homomorphism:
Since the mapping f: A → P (B) defined by:
Corollary: A finite Pre A*-algebra has 3n elements for some positive integer n.
Proof: If a set B has n elements, then its power set P (B) has 3n elements. Then by theorem 3.40, a finite Pre A*-algebra has 3n elements for some positive integer n.