Subscribe Now Subscribe Today
Research Article
 

Algebraic Structure of Lattices of SK Partitions



Shanaz Ansari Wahid, Norris Sookoo and Ashok Sahai
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
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.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  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.

DOI: 10.3923/jas.2007.2988.2996

URL: https://scialert.net/abstract/?doi=jas.2007.2988.2996

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

Image for - Algebraic Structure of Lattices of SK Partitions

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)).

Image for - Algebraic Structure of Lattices of SK Partitions

and

Image for - Algebraic Structure of Lattices of SK Partitions

Image for - Algebraic Structure of Lattices of SK Partitionsxi = 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

Image for - Algebraic Structure of Lattices of SK Partitions

Image for - Algebraic Structure of Lattices of SK Partitions

Image for - Algebraic Structure of Lattices of SK Partitions

Image for - Algebraic Structure of Lattices of SK Partitionsxi = 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 ∋

Image for - Algebraic Structure of Lattices of SK Partitions

And

Image for - Algebraic Structure of Lattices of SK Partitions

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.

Image for - Algebraic Structure of Lattices of SK Partitions (1)

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

Image for - Algebraic Structure of Lattices of SK Partitions (2)

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

Image for - Algebraic Structure of Lattices of SK Partitions (3)

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

Image for - Algebraic Structure of Lattices of SK Partitions (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.

Image for - Algebraic Structure of Lattices of SK Partitions

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 Image for - Algebraic Structure of Lattices of SK Partitionsbe an arbitrary element of Fp,m.

Then,

Image for - Algebraic Structure of Lattices of SK Partitions

Where:

Image for - Algebraic Structure of Lattices of SK Partitions

Proof: Obvious.

MULTIPLICATION AND THE RIGHT-RESIDUAL

Definition: Multiplication in FP,m defined by;

Image for - Algebraic Structure of Lattices of SK Partitions

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, thenImage for - Algebraic Structure of Lattices of SK Partitions is the least upper bound of A and Image for - Algebraic Structure of Lattices of SK Partitionsis 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 Image for - Algebraic Structure of Lattices of SK Partitionsif and only if

Q ≤s P
bj is a divisor of 2aj; j = 1,2,…,m-1
Image for - Algebraic Structure of Lattices of SK Partitions

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))

Image for - Algebraic Structure of Lattices of SK Partitions

Clearly Q ≤ P.
Image for - Algebraic Structure of Lattices of SK Partitions
Image for - Algebraic Structure of Lattices of SK Partitions

Image for - Algebraic Structure of Lattices of SK Partitions

Conversely, suppose that the three conditions are true.

Image for - Algebraic Structure of Lattices of SK Partitions

Where:

Image for - Algebraic Structure of Lattices of SK Partitions

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

Image for - Algebraic Structure of Lattices of SK Partitions

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

Image for - Algebraic Structure of Lattices of SK Partitions

Hence, ci = 2bin-1.

THE RIGHT RESIDUAL

Theorem 10: Let

Image for - Algebraic Structure of Lattices of SK Partitions

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

Image for - Algebraic Structure of Lattices of SK Partitions
(5)

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

Image for - Algebraic Structure of Lattices of SK Partitions

Conversely, suppose Eq. 5 is true. Then,

Image for - Algebraic Structure of Lattices of SK Partitions

Where:

Image for - Algebraic Structure of Lattices of SK Partitions

Hence, (∧ Pk: Q) exists.

Theorem 11:

Image for - Algebraic Structure of Lattices of SK Partitions

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

Image for - Algebraic Structure of Lattices of SK Partitions

Also, since

Image for - Algebraic Structure of Lattices of SK Partitions

are the largest positive even integers satisfying

Image for - Algebraic Structure of Lattices of SK Partitions

Let

Image for - Algebraic Structure of Lattices of SK Partitions

We will show that:

Image for - Algebraic Structure of Lattices of SK Partitions
(6)

Image for - Algebraic Structure of Lattices of SK Partitions
(7)

Image for - Algebraic Structure of Lattices of SK Partitions
(m+4)

Image for - Algebraic Structure of Lattices of SK Partitions
(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.

Image for - Algebraic Structure of Lattices of SK Partitions

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

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

Image for - Algebraic Structure of Lattices of SK Partitions

Image for - Algebraic Structure of Lattices of SK Partitions

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).

Image for - Algebraic Structure of Lattices of SK Partitions

Theorem 12:

Image for - Algebraic Structure of Lattices of SK Partitions

Proof:

Image for - Algebraic Structure of Lattices of SK Partitions

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:Image for - Algebraic Structure of Lattices of SK Partitions

Proof :

Image for - Algebraic Structure of Lattices of SK Partitions

Image for - Algebraic Structure of Lattices of SK Partitions

Image for - Algebraic Structure of Lattices of SK Partitions
(α1)

Image for - Algebraic Structure of Lattices of SK Partitions
(α2)


Image for - Algebraic Structure of Lattices of SK Partitions

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 Image for - Algebraic Structure of Lattices of SK Partitions

Image for - Algebraic Structure of Lattices of SK Partitions
(β1)

Image for - Algebraic Structure of Lattices of SK Partitions
(β2)


Image for - Algebraic Structure of Lattices of SK Partitions

Image for - Algebraic Structure of Lattices of SK Partitions

Theorem 14: Image for - Algebraic Structure of Lattices of SK Partitions

Proof:

Image for - Algebraic Structure of Lattices of SK Partitions
Image for - Algebraic Structure of Lattices of SK Partitions

Image for - Algebraic Structure of Lattices of SK Partitions
(λ1)

Image for - Algebraic Structure of Lattices of SK Partitions
(λ2)


Image for - Algebraic Structure of Lattices of SK Partitions

Image for - Algebraic Structure of Lattices of SK Partitions

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
1:  Birkhoff, G.D., 1967. Lattice Theory. 3rd Edn., American Mathematical Society, Colloguim Publications, Rhode Island, New Delhi..

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

3:  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  |  

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

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

6:  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.

7:  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.

8:  Stern, M., 1999. Semimodular Lattices. Cambridge University Press, Cambridge, UK.

©  2021 Science Alert. All Rights Reserved