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.
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
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
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 = xi ≥ 1i = yi
(4) |
JOIN-IRREDUCIBLE ELEMENTS
Theorem 3: Each join-irreducible element of (FP, m ≤s) 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
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 |
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
• | 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).