HOME JOURNALS CONTACT

Journal of Applied Sciences

Year: 2007 | Volume: 7 | Issue: 20 | Page No.: 2988-2996
DOI: 10.3923/jas.2007.2988.2996
Algebraic Structure of Lattices of SK Partitions
Shanaz Ansari Wahid, Norris Sookoo and Ashok Sahai

Abstract: In the context of Complexity Reduction in Lattice-Based Information Retrieval, the reduction process must preserve the algebraic structure of a lattice. The SK (Sharma-Kaushik)-Lattices are known to be of high applicational value. Hence the present study is aimed at detailing the `Algebraic Structure of SK-Lattice. In the context of Information-Theoretic approach to coding, the n-tuples of integers are relevant. Therefore, the Algebraic properties are obtained for lattices of SK-partitions, which are characterized as n-tuples of integers. Such lattices are shown to satisfy the Jordan-Dedekind chain condition and the modular-identity. Right residuals and deficits are also considered.

Fulltext PDF Fulltext HTML

How to cite this article
Shanaz Ansari Wahid, Norris Sookoo and Ashok Sahai, 2007. Algebraic Structure of Lattices of SK Partitions. Journal of Applied Sciences, 7: 2988-2996.

Keywords: Jordan-Dedekind chain condition, algebraic structure of a lattice, Lattice-based information retrieval, Modular identity and Sharma-Kaushik partition lattices

INTRODUCTION

In the context of Complexity Reduction in Lattice-Based Information Retrieval (Ming and Wang, 2005), the reduction process must preserve the algebraic structure of a lattice (Kalinin and Spatzier, 2005; Karen and Vogel, 2005). The SK (Sharma-Kaushik)-Lattices are known to be of high applicational value. Hence the present study is aimed at detailing the algebraic structure of SK-lattice. In the context of Information-Theoretic approach to coding, the n-tuples of integers are relevant. Therefore, the Algebraic properties are obtained for lattices of SK-partitions, which are characterized as n-tuples of integers.

Lattices of sets have been studied to a significant extent. Lachlan (1968) investigated the lattice of recursively enumerable sets and characterized the hh-simple sets as co-infinite r.e. sets whose r.e. sets form a Boolean algebra. The lattice of partitions of a set is also a topic of interest. Haiman (1994) presented a construction realising a continuous partition lattice as a lattice of measurable partitions.

SK-partitions were introduced by Sharma and Kaushik (1977), in connection with metrics in Coding Theory. SK-partitions can be characterized as n-tuples of integers and so a lattice of SK-partitions can hence be considered to be a lattice of sets of n-tuples. We show that a lattice of SK-partitions satisfy the well-known Modular Identity and Jordan-Dedekind Chain Condition (Stern, 1999) and is a cl-semigroup. We also obtain conditions satisfied by the right-residual and deficit of SK-partitions and present a condition for the existence of a certain right residual. Most of these results are obtained directly by considering the structure of SK-partitions.

DEFINITIONS AND NOTATION

The following definitions and notations are found in Lattice Theory by Birkhoff (1967).

Definition: If a and b are elements of a partially ordered set P, then a is said to cover b if a < b and a > x > b is not satisfied by any x in P.

Notation: 0 denotes the least element and 1 the greatest element of P.

Definition: An element which covers 0 is called an atom.

Definition: If a ≥ b in a partially ordered set P, the set of x satisfying a ≥ x ≥ b is called the closed interval [b, a]. The elements x satisfying a ≥ x ≥ b are said to be between a and b.

Definition: Intervals which can be written as [x ∧ y, x] and [y, x ∨ y] are called transposes.

Definition: A lattice having the property that every non-empty bounded set has a greatest lower bound and a least upper bound is called conditionally complete.

Definition: The modular identity is: If x ≤ z, x ∨ (y ∧ x) = (x ∨ y) ∧ x for elements x, y, z of a lattice L.

Definition: Jordan-Dedekind chain condition: All finite connected chains between fixed end-points have the same length.

Definition: An element of a lattice L is called join irreducible if x ∨ y = a ⇒ x = a or y = a ∀ x, y ∈ L.

Definition: A multiplicative lattice or m-lattice is a lattice L with a binary operation satisfying a(b∨ c) = ab ∨ ac and (a ∨ b) c = ac ∨ bc.

A zero of an m-lattice L is an element 0 satisfying 0 ∧ x= 0x = x0 = 0∀ x ∈ L.
A unity of L is an element e satisfying ex = xe = x∀ x ∈ L.
An infinity of L is an element I satisfying I ∨ x = Ix = xI = I∀ x ∈ L.
L is called commutative if xy = yx ∀ x, y ∈ L. L is called associative if x(yz) = (xy) z ∀ x, y, z ∈ L.

If L is conditionally complete and satisfies the unrestricted distributive laws a ∨ ba = ∨ (aba) and (∨aa)b = ∨(aab), it is called a complete m-lattice, or cm-lattice. An associative lattice with unity is called a lattice-ordered semigroup or l-semigroup and if complete it is called a cl-semigroup.

Definition: Let G be any m-lattice. The right-residual h:k of h by k is the largest x (if it exists) satisfying xk ≤ h; the left-residual h:k of h by k is the largest y satisfying ky ≤ h.

We will also require the following notations.

Notation: We denote the SK-partition P = {B0, B1,…, Bm-1} by ((1,b1,b2,…,bm-1)), where bi = |Bi| = number of elements of Bi; i = 1,2,…, m-1.

Notation: The set of all SK-partitions will be denoted by FP and the set of SK-partitions with m classes will be denoted by FP,m.

Definition: The dimension function d is defined on Fp by

THE MODULAR IDENTITY AND JORDAN-DEDEKIND CHAIN CONDITION

Lemma 1: Let x, y, a ∈ FP,m ý x and y cover a and x ≠ y. Then x ∨ y covers x and y.

Proof: Let

a = ((1,a1,a2,…,am-1)).
x = ((1,x1,x2,…,xm-1)).
y = ((1,y1,y2,…,ym-1)).

and

xi = ai = zi, i ≠ u, v ; xi = ai+ 2 zi, i = u; xi + 2 = ai + 2 = zi, i = v. Hence x ∨ y covers x. Similarly, x ∨ y covers y.

Lemma 2: Let x, y, a p FP,m ^ a cover x and y and x ≠ y. Then x and y cover x ∧ y.

Proof: Let



xi = ai = zi, i ≠ u, v ; xi = ai- 2 = zi, i = u; xi = ai = zi + 2,, i = v. Hence x covers x ∧ y. Similarly, y covers x ∧ y.

Theorem 1: (FP,m, ≤s) satisfies the modular identity and the Jordan-Dedekind chain condition.

Proof: This follows immediately from Theorem 1 of Lattice Theory by Birkhoff.

TRANSPOSES

Theorem 2: Let [l, x] and [y, n] be intervales ∋

And

Where, a1,a2,…,ar are fixed elements of {1,2,…,m-1}. Then, [1,x] and [y,u] are transposes.

Proof: For i ∈ {1,2,…,m-1} ý i ≠ a1,a2,…,ar, lj = xi ≤ yi.

(1)

For i = a1,a2,…am-1; 1i = yi ≤ ui = xi

(2)

From Eq. 1 and 2, l = x ∧ y. For i ∈ {1,2,…m-1}ý
i ≠ a1,a2,…,ar with ui = yi ≥ xi

(3)

For i ∈ {1,2,…,m-1} ý i = a1,a2,…,am-1; ui = xi1i = yi

(4)

From Eq. 3 and 4, u = x ∨ y.

JOIN-IRREDUCIBLE ELEMENTS

Theorem 3: Each join-irreducible element of (FP, ms) is of the form ((1,2,2,…,2,a,…,a)), where a ∈ {2,4,6,…}.

Proof: Let ((1,2,2,…,2,a1,a2,…,as)) be any join-irreducible element of Fp,m. Suppose that a1 < a2.

So, ((1,2,2,…,2,a1,a2,…,as)) is not join-irreducible, contradiction. Hence, a1 = a2.

Similarly, it can be established that a2 = a3 = … as. Any element of Fp,m can be expressed is terms of join-irreducible elements of F p,m, as shown in the following theorem.

Theorem 4: Let be an arbitrary element of Fp,m.

Then,

Where:

Proof: Obvious.

MULTIPLICATION AND THE RIGHT-RESIDUAL

Definition: Multiplication in FP,m defined by;

Theorem 5: (FP,m, ≤s) is a cl-semigroup.

Proof:

Clearly the unity e of (FP,m, ≤s) is ((1,2,2,…,2)).
(FP,m, ≤s) is associative.
(FP,m, ≤s) satisfies the unrestrictive distributive laws.
(FP,m, ≤s)is conditionally complete, since if A is a bounded subset of FP,m, then is the least upper bound of A and is the greatest lower bound of A.

Theorem 6: ∀ P, Q ∈ (Fp,m,≤s), (P ∧ Q)(P ∨ Q) = PQ

Proof: Let

P = ((1,a1,a2,…,am-1))
Q = ((1,b1,b2,…,bm-1)).

We assume that ai < bi, i ∈ {1,2,…,m-1}.
Then the (i+1) th entry of (P ∧ Q)(P ∨ Q) = 1/2(ai)(bi) = (i + 1)th entry of PQ (I)
Similarly, if ai > bi or ai = bi (I) can still be shown to be true.

Theorem 7: Let

P = ((1,a1,a2,…,am-1))
Q = ((1,a1,a2,…,am-1)) be elements of Fp,m. Then if and only if

Q ≤s P
bj is a divisor of 2aj; j = 1,2,…,m-1

Proof: Let Suppose P = QR, where R = ((1,c1,c2,…,cm-1))

Then, ((1,a1,a2,…,am-1)) = ((1,b1,b2,…,bm-1))((1,c1,c2,…,cm-1))


Clearly Q ≤ P.

Conversely, suppose that the three conditions are true.

Where:

Then, clearly R ∈ Fp,m and P = QR.

Theorem 8: Let P, Q be as in the above theorem. If ai = kbi, k ∈ {2,3,…}, then QR = P, where R = ((1,c1,c2,…,cm-1)) and ci = 2k.

Proof: If QR = P, then

Hence, ci = 2k.

Theorem 9: Let P, Q, R be as in the above theorem. If ai = bin (n = 2,3,…) and QR = P, then ci = 2bin-1.

Proof: If QR = P, then

Hence, ci = 2bin-1.

THE RIGHT RESIDUAL

Theorem 10: Let

be elements of (Fp,m, ≤s). Then (∧ Pk): Q exists if and only if

(5)

Proof: Suppose (∧ Pk:Q) exists. Then ∃ positive, even integers c1,c2,…,cm-1 such that R = ((1,c1,c2,…,cm-1) and

Conversely, suppose Eq. 5 is true. Then,

Where:

Hence, (∧ Pk: Q) exists.

Theorem 11:

Proof: Since R = (∧ Pi): Q, QR ≤ P1∧P2∧…∧Pu and c1,c2,…,cm-1 are the largest positive, even integers satisfying:

Also, since

are the largest positive even integers satisfying

Let

We will show that:

(6)

(7)

(m+4)

(m+5)

and that d1,d2,…,dm-1 are the largest positive, even integers that satisfy Eq. 6, 7,…, m+5.

Equation (m+5) is obviously true.

Let D1,D2,…,Dm-1 be positive even integers satisfying d1 ≤ D1, d2 ≤ D2,…,dm-1≤ Dm-1.

We show by contradiction, that d1 = D1, d2 = D2,…,dm-1 = Dm-1

Suppose that c1(m-1) < Dm-1.


This means that: Dm-2 = dm-2. Continuing like this, we can establish that di = Di, ∀i ∈ {1,2,…,m-1}.
Thus, the values we have chosen for d1,d2,…,dm-1 are the largest positive, even integers satisfying Eq. 6, 7,…,(m+5).

Theorem 12:

Proof:

THE DEFICIT

Definition: We define the deficit h •C k of h by k as the smallest x, if it exists, satisfying h ≤ xk.

Theorem 13:

Proof :




(α1)

(α2)


We claim that d1,d2,…,dm-1 are the smallest positive even integers satisfying the same inequalities as r1,…rm-1, namely α1,α2,…,α(m-1).

Suppose ∃ positive even integers

(β1)

(β2)



Theorem 14:

Proof:


(λ1)

(λ2)



CONCLUSIONS

The details characterizing the Algebraic Structures of the SK-Lattices are of immense usefulness in the context of the recently-growing interest in the area of the contemporarily modern Approach to Image Retrieval Based on Concept Lattices, as also in useful reference to Complexity reduction in Lattice-based information retrieval, which requires that the reduction process must preserve the algebraic structure of a lattice (Kalinin and Spatzier, 2005; Karen and Vogel, 2005).

REFERENCES

  • Birkhoff, G.D., 1967. Lattice Theory. 3rd Edn., American Mathematical Society, Colloguim Publications, Rhode Island, New Delhi.


  • Haiman, M., 1994. On realization of Bjorner`s continuous partition lattice by measurable partitions. Trans. Am. Math. Soc., 343: 695-711.


  • Kalinin, B. and R. Spatzier, 2005. Rigidity of the measurable structure for algebraic actions of higher-rank abelian groups. Ergodic Theory Dyn. Syst., 25: 175-200.
    Direct Link    


  • Karen, C. and D. Vogel, 2005. Complexity reduction in Lattice-based information retrieval. Inform. Retrieval, 8: 285-299.
    Direct Link    


  • Lachlan, A.H., 1968. On the lattice of recursively enumerable sets. Trans. Am. Math. Soc., 130: 1-37.


  • Ming, L. and T. Wang, 2005. An approach to image retrieval based on concept lattices and rough set theory. Proceedings of the 6th International Conference on Parallel and Distributed Computing, Applications and Technologies, December 5-8, 2005, IEEE Xplore, pp: 845-849.


  • Sharma, B.D. and M.L. Kaushik, 1977. Error correcting codes through a new metric. Proceedings of 41st Annual Conference Int. Stat. Inst., New Delhi.


  • Stern, M., 1999. Semimodular Lattices. Cambridge University Press, Cambridge, UK

  • © Science Alert. All Rights Reserved