Lattices

6.3 Lattices 6.3.1. Lattice Ordered Sets In this section we define lattice ordered sets and see some examples. A poset (L, ≤ ) is called lattice ordered set if for every pair of elements x, y ∈ L, the sup (x, y) and inf (x, y) exist in L.

Example 1: Let S be a nonempty set. Then (P(S), ⊆ ) is a lattice ordered set. For (P (S), ⊆ ) is a poset. Further for any subsets A, B of S, inf (A, B) = A ∩ B ∈ P(S) and sup (A, B) = A ∪B ∈ P(S). Example 2: Every totally ordered set is a lattice ordered set (Prove !). Example 3: Consider the set of all positive integer Z+ with divisor as a relation, i.e., a ≤ b if and only if a⏐b. Then (Z+ , ⏐) is a poset. For, if a, b Z+, then inf (a, b) = GCD(a, b) Z+ and sup (a, b) = LCM(a, b) Z+. Thus, inf (a, b) and sup (a,b) exist in Z+ for any two element a, b ∈ Z+. Hence (Z+ , ⏐) is a lattice ordered set. In fact (Dn , ⏐) ( Dn denotes the set of all positive divisors of positive number n ) is also a lattice ordered set.

Example 4: Consider the set B, where Bn = {(l1, l2, … , ln) / li = 0 or 1, for 1 ≤r ≤n}. Define the relation ≤' by (i1, i2, … , in) ≤' (j1, j2, … , jn) if and only if ir ≤jr , 1 ≤r ≤n. Note that here in the expression ir ≤ jr, ≤ is usual less than or equal to. We have already seen in Example 7 of Section 6.2.1 that (Bn, ≤') is a poset. Observe that inf [ (i1, i2, ….. ,in), (j1, j2, … , jn)] = (min (i1, j1), min (i2,j2), …. , min (in, jn) ) and sup [ (i1, i2, … , in), (j1, j2, … , jn)] = (max (i1, j1), max (i2,j2), …. , max (in, jn) ) Since min (ir, jr) and max (ir, jr) is either 0 or 1, so, inf { (i1, i2,… , in), (j1,j2, .. ,jn) } and sup { (i1, i2, … , in), (j1, j2, … , jn) } exist in B. Thus, (Bn, ≤ ) is a lattice ordered set. Example 5: Poset represented by the Hasse diagram is not a lattice ordered set since inf (a, b) does not exist.

Example 6: Poset represented by the Hasse diagram is not a lattice ordered set as sup (f, g) does not exist.

Exercise : 1. Prove that if (L, ≤ ) and (M, ≤' ) are lattice ordered sets. Then (L × M, R) is a lattice ordered set, where (a, b) R (x, y) if and only if a ≤ x in L and b ≤' y in M.

2. Check whether the poset represented by the following Hasse diagram that is lattice ordered set or not?

Remark 1: Let (L, ≤ ) be a lattice ordered set and let x, y ∈ L. Then the following are equivalent. (i) x ≤ y (ii) sup (x, y) = y (iii) inf (x, y) = x Proof: (i) ( ii ) Let x ≤ y …… (1) We have, y ≤ y , for all y ∈ L. …… (2) From (1) and (2), we have y is an upper bound of (x, y). Therefore, sup (x, y ) ≤ y (by definition of superimum). But, y ≤ sup (x, y). Therefore, y = sup (x, y) (since ≤ is anti - symmetric). ( iii ) ( ii ) Given that sup (x, y) = y. Therefore we have x ≤y. Also, we have x ≤ x. Therefore, x is a lower bound for x and y. Thus, x ≤ inf (x, y). But, we have inf (x, y) ≤ x. Hence, x = inf (x, y) ( since ≤ is anti-symmetric). ( iii ) (i) Given that x = inf (x, y). Therefore, by the definition of infimum, x ≤ y. 6.3.2 Algebraic Lattice In this section we define algebraic lattice by using two binary operations * (meet) and ⊕ (join). Then we shall prove that lattice ordered sets and algebraic lattices are equivalent.

An algebraic lattice (L, *, ⊕) is a non empty set L with two binary operations * (meet) and ⊕ (join), which satisfy the following conditions for all x, y, z

L.

L1. x * y = y * x, x ⊕ y = y ⊕ x (Commutative) L2. x * (y*z) = (x * y) * z, x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z (Associative) L3. x * (x ⊕y) = x, x ⊕ (x * y) = x (Absorption) L4. x * x = x, x ⊕ x = x (Idempotent)

Theorem 3.2.1: Let (L, ≤) be a lattice ordered set. If we define x * y = inf (x, y), x ⊕ y = sup (x, y) then (L, *, ⊕) is an algebraic lattice.

Proof: Given that (L, ≤ ) is a lattice ordered set and x * y = inf (x, y) and x ⊕ y = sup (x, y). Now we shall prove that * and ⊕ satisfy the commutative, associative, absorption and idempotent laws.

Commutative: x * y = inf (x, y) = inf (y, x) = y * x. x ⊕y = sup (x, y) = sup (y, x) = y ⊕ x.

Associative: x * (y * z) = inf (x, (y * z)) = inf (x, inf (y,z)) = inf (x,y,z) = inf ( inf (x, y), z)) = inf ((x*y), z) = (x*y) *z.

Now, x ⊕ (y ⊕ z) = sup (x, (y ⊕ z)) = sup (x, sup (y,z)) = sup (x, y,z) = sup (sup (x,y), z) = sup ((x ⊕ y), z) = (x ⊕ y) ⊕ z.

Absorption: Now, x * (x ⊕ y) = inf (x, x ⊕ y) = inf (x, sup (x, y)) = x [since x ≤ sup (x, y)] and x ⊕ (x * y) = sup (x, x * y) = sup (x, inf (x, y)) = x [since inf (x, y) ≤ x ].

Idempotent: We have, x * x = inf (x, x) = x and x ⊕ x = sup (x, x) = x. Hence (L, * , ⊕) is an algebraic lattice.

Theorem 3.2.2: Let (L, *, ⊕ ) be an algebraic lattice. If we define x ≤ y x≤y

x * y = x or

x ⊕ y = y, then (L, ≤ ) is a lattice ordered set.

Proof: Given that (L, *, ⊕ ) is an algebraic lattice and x ≤ y

x * y = x or x ⊕ y = y.

We shall now prove that (L, ≤ ) is a poset and inf (x, y) and sup (x, y) exist in L, for all x, y in L.

≤ is reflexive

Since x * x = x, for all x

L (by indempotent of *).

We have by definition of ≤ , x ≤ x, for all x ∈ L. Therefore, ≤ is reflexive.

≤ is anti-symmetric If x ≤ y and y ≤ x in L, then by definition of ≤ , we have x * y = x and y * x = y. But * satisfies commutative law, so, we have x * y = y * x. Therefore, x = y. Hence, ≤ is anti-symmetric.

≤ is transitive If x ≤ y and y ≤ z, then by the definition of ≤ , we have x * y = x and y * z = y. Therefore, x * z = (x * y) * z = x * (y * z) [by associativity of *] = x * y [by definition ≤ )] = x [by definition of ≤ ] Hence, by definition of ≤ , we have x ≤ z. Thus, ≤ is transitive.

sup (x, y) and inf (x, y) exist in L We shall now show that inf (x, y) = x * y and sup (x, y) = x ⊕ y. Now by absorption law, we have x = x * (x ⊕y) and y = y * (x ⊕ y) Then by the definition of ≤ , we have x ≤ x ⊕ y and y ≤ x ⊕ y Therefore, x ⊕ y is an upper bound for x and y. Let z be any upper bound for x and y in L. Then x ≤ z and y ≤ z. So, by definition of ≤ , we have x ⊕ z = z and y ⊕ z = z …… ( 1 ) Therefore, (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z) [by associative law] = x ⊕z [by ( 1 )]

= z [by ( 1 )]. Thus, by definition of ≤ , we have x ⊕ y ≤ z. that is, x ⊕ y is related to every upper bound of x and y. Hence sup (x, y) = x ⊕ y. Similarly, we can show that inf (x, y) = x * y. Thus, x * y and x ⊕ y exists for every x, y ∈ L. Hence, we have (L, ≤ ) is lattice ordered set.

Remark 1: From the Theorem 3.2.1 and the Theorem 3.2.2, we see that if we have lattice ordered set (L, ≤ ) then we can get an algebraic lattice (L, *, ⊕ ) and conversely. Hence, we conclude that the algebraic lattice and a lattice ordered sets are equivalent system. Thus, here after we shall say simply lattice to mean both.

In an algebraic system it is better convenience for imposing further conditions on the binary operations. Hence developing structural concepts will be much easier than the ordered system. In fact, it is one of the motivation to view a lattice ordered set as an algebraic lattice.

6.3.3 Sublattice, Direct Product and Homomorphism

In this section we discuss sublattices of a lattice, direct product of two lattices and omomorphism between two lattices.

6.3.3.1 Sublattices

Substructure helps to know more about the whole structure. So, here we discuss about sublattice of a lattice. Let (L, *, ⊕ ) be a lattice and let S be subset of L. The substructure (S, *, ⊕) is a sublattice of (L, *, ⊕ ) if and only if S is closed under both operations * and ⊕.

Remark 1: A subset S in a lattice (L, *, ⊕ ) is said to be sublattice, for a, b a ⊕ b = d in L, then c, d must necessary exist in S also.

S, if a * b = c in L and

Example 1: Consider the lattice L represented by the following Hasse diagram.

Here the substructure S1 represented by the Hasse diagram given below is not a sublattice, for inf (a, b) = 0 in L, which does not belong to S1.

It is clear that the substructure S2 represented by the Hasse diagram given below is sublattice of L.

It is interesting to note that the substructure S3 of L represented by the in the following Hasse diagram is not a sublattice but it is a lattice on its own. So, it is a lattice without being a sublattice.

6.3.3.2 Direct Product of Lattices

From given two lattices, we can always construct a new lattice by taking Cartesian product of the given two lattices. So, in this section we discuss about product of two lattices.

Let (L, *, ⊕ ) and (M, ,

) be two lattices. Consider the Cartesian product of L and M, that

is,L × M = {(x, y) / x ∈ L, y ∈ M}. Define operations Δ and ∇ in L × M, by (x, y) Δ (a, b) = (x * a, y

b) and (x, y) ∇ (a, b) =

(x ⊕ a, y b), then we shall prove that ( L × M, Δ ,∇ ) is a lattice.

Δ and ∇ are commutative. By definition (x, y) Δ (a, b) = (x * a, y = (a * x, b

b) y) (since * and

are commutative)

= (a, b) Δ (x, y) (by definition Δ ). Similarly, (x, y) ∇ (a, b) = (x ⊕ a, y = (a ⊕ x, b

b) y)

= (a, b) ∇ (x, y). Hence, commutative law holds good for both operations Δ and ∇ . Δ and ∇ are associative [ ( x, y) Δ (a, b) ) Δ (u, v)] = [ (x * a, y

b) ] Δ (u, v) (by definition of Δ )

= [ (x * a ) * u, (y = [ x * (a * u), y = [ (x, y) Δ (a * u, b

v] (again by definition of Δ )

b) (b

v) ] (since * and

are associative)

v) ] (by definition of Δ )

= [ (x, y) Δ [ (a, b) Δ (u, v) ] (by definition of Δ )

Similarly we can show that [ (x, y) ∇ (a, b) ] ∇ (u, v) = (x, y) ∇ [ (a, b) ∇ (u, v) ] Thus, associative law hold good for both operations and ∇ in L × M.

Absorption (x, y) Δ [ (x, y) ∇ (a, b) ] = (x, y) Δ [ x ⊕ a, y = [ x * (x ⊕ a), y

(y

b] b) ] (by definition of Δ and ∇ )

= (x, y ) (by absorption law in L and M). Therefore, absorption law hold good in L × M.

Idempotent (x, y) Δ (x, y) = [ x * x, y

y]

= (x, y) (since * and

satisfy idempotent law)

Similarly, (x, y) ∇ (x, y) = (x, y). Hence, (L × M, Δ , ∇ ) is an algebraic lattice. Thus, (L × M, Δ , ∇ ) is a lattice. Remark 1: If (L, *, ⊕ ) is a lattice, then L² = L x L is a lattice. In general one can show that Ln = L × L × L × …. × L (n times) is a lattice. In the finite lattices, Bn is a very important lattices, where B = {0,1}, which has rich structural property and will play very important role in the applications. Let (L, ≤ ) and (M, ≤' ) be two lattices, then we have already seen that (L × M, R) where (x1, y1) R (x2, y2) if and only if x1 ≤ x2 and y1 ≤' y2, is a poset. It can be proved that (L × M, R) is a lattice ordered set.

6.3.3.3 Homomorphism

In this section to understand the structural similarity between two lattices we define homomorphism between two lattices and we discuss about it.

Let (L, *, ⊕ ) and (M,

,

) be two lattices. A function f : L→ M is called a Lattice

homomorphism if f (a * b) = f (a)

f (b) and

f (a ⊕ b) = f (a)

f (b), for all a, b ∈ L,

and it is called order preserving if x ≤ y in L implies f (x) relation in L and

' f (y), where ≤ is an order

' is an order relation in M.

A bijecitve homomorphism is called isomorphism.

Example 1: Consider the lattices D6 = {1,2,3,6} and D30 = {1,2,3,5,6,10,15,30}. We can show that there exist a homomorphism f between D6 and D30. Define a mapping f from D6 into D30 by f (1) = 1, f(2) = 6, f (3) = 15 and f (6) = 30.

Then f (1 * 2) = f(1) = 1. f (1) * f(2) = 1 * 6 = 1. [Note that in both D6 and D30 a * b and a ⊕b are GCD and LCM of two element a, b] Similarly, f (1 * 3) = f(1) = f(1) * f(3). f(1 * 6) = f(1) * f (6) = f(1). f(2 * 3) = f(2) * f(3) = f(1). f(2 * 6) = f(2) * f(6) = f(2). f(3 * 6) = f(3) * f(6) = f(3).

Similarly we can prove that f (x ⊕y) = f (x) ⊕ f (y) for all x, y

D6 .

Thus, f is homomorphism. Note that f is not onto but f is one-one. Hence f is not an isomorphism.

Exercise 1: It is very interesting to prove that the mapping f defined from Bn into P(An), where An = {1,2, …. , n} by f (i1, i2, …. , in) = { k / ik ≠0} is a homomorphism.

6.3.3.4 Special Lattices

In this section we shall discuss some of the special types of lattices which in turn help to define the Boolean algebra.

6.3.3.4.1 Isotone, Distributive and Modular Inequalities In this subsection we shall prove that in every lattice the operation * and ⊕ are isotone and distributive and modular inequalities holds good. Lemma 3.4.1.1: In every lattice L the operation * and ⊕ are isotone, i.e., if y ≤ z ⇒ x * y ≤ x * z and x ⊕ y ≤ x ⊕ z.

Proof: x * y = (x * x) * (y * z) (since x * x = x and since y ≤ z, y * z = y) = (x * y) * (x * z) (by associative and commutative of *). x * y ≤ x * z (since a ≤ b Also, x ⊕ z = (x ⊕ x) ⊕ (y ⊕ z) = (x ⊕ y) ⊕ (x ⊕ z) x ⊕ y ≤ x ⊕ z. Hence the lemma.

a * b = a).

Theorem 3.4.1.2: The elements of an arbitrary lattice satisfy the following inequalities i. ii.

x * (y ⊕ z) ≥ (x * y) ⊕ (x * z) x ⊕ (y * z) ≤ (x ⊕ y) * (x ⊕ z) (distributive inequalities.) x * (y ⊕ z) ≥ (x * y) ⊕ (x * z) = (x * y) ⊕ z x≥z x ≤z x ⊕ (y * z) ≤ (x ⊕ y) * (x ⊕ z) = (x ⊕ y) * x (modular inequalities.)

Proof: Claim: Distributive inequalities are true in a lattice. By definition of ⊕,y ≤y ⊕z and z ≤y ⊕z. By isotone property we have x * y ≤x * (y ⊕z) ............... (1) and x * z ≤x * (y ⊕z) ............... (2) From (1) and (2) we observe that x * (y ⊕ z) is an upper bound for x * y and x * z. Hence, (x * y) ⊕ (x * z) ≤ x * (y ⊕ z). By duality principle, we have (x ⊕ y) * (x ⊕ z) ≥ x ⊕ (y * z). ii) It is given that z ≤ x, then by Theorem 3.2.2 z * x = z. From the inequality ( i ) we have x* (y ⊕z) ≥ (x*y)⊕ (x∗z). Therefore, x * (y ⊕ z) ≥ (x * y) ⊕ z. Since x ≤ z, we have x ⊕ z = z. Thus, from the inequality x ⊕ (y * z) ≤ (x ⊕ y) * (x ⊕ z), we have x ⊕ (y * z) ≤ (x ⊕ y) * z. Hence the theorem.

6.3.3.4.2 Modular Lattices

In this section we shall define and discuss about the modular lattices. A lattice L is said to be modular if for all x, y, z ∈ L, x≤ z ⇒ x * (y ⊕ z) = (x * y) ⊕ z. Example 1: (P(A), ∩ , ∪ ) is a modular lattice [ Proof left as an exercise].

Example 2: The set of all normal subgroups of a group form a modular lattice. [Recall that a subgroup H of a group G is said to be normal if gHg-1 = H, for all g ∈ G]. It can be easily

shown that M, the set of normal subgroups of a group G, with `set inclusion' relation is a poset.

Now for any two normal subgroups H1 and H2 of G, we have H1 * H2 = inf (H1, H2) = H1 ∩ H2 and H1 ⊕ H2 = sup (H1, H2) = H1H2. Since H1 ∩ H2 and H1H2 are normal subgroups if both H1 and H2 are normal subgroups. Therefore, (M, ⊆ ) is a lattice ordered set. Hence (M, *, ⊕) is an algebraic lattice. Let H1, H2, H3, ∈ M such that H1 ⊆ H3. Since in every lattice modular inequality holds good, we have H1 (H2 * H3) ⊆ (H1 ⊕ H2) * H3 ………. (1) Now we shall prove that (H1 ⊕ H2) * H3 ⊆ H1 ⊕ (H2 * H3). Let a ∈ (H1 ⊕ H2) * H3 i.e., a ∈ (H1 H2) ∩ H3 a ∈ H1 H2 and a ∈ H3 a = h1h2 and a = h3, for some h1 ∈ H1 ,h2 ∈ H2 and h3 ∈ H3. Therefore, h1h2 = h3 h2 = h1-1 h3 ∈ H3 [ h3 ∈ H3 and h1∈ H1 ⊆ H3 , therefore, h1-1 h3∈ H3] h2∈ H2 and h2∈ H3 Thus, h2 ∈ H2 ∩ H3 ……… (2) Since a = h1h2, we have a ∈ H1(H2 ∩ H3) (by (2)) That is, a∈ H1 ⊕ (H2 * H3) That is, (H1 ⊕ H2) * H3 ⊆ H1 ⊕ (H2 * H3) ………. (3) From (1) and (3) we have H1 ⊕ (H2 * H3) = (H1 ⊕ H2) * H3. Hence (M, *,⊕ ) is a modular lattice. Theorem 3.4.2.1: A lattice L is modular if and only if x, y, z ∈ L , x ⊕ (y * (x ⊕ z)) = (x ⊕ y) * (x ⊕ z). Proof : Let (L, *, ⊕ ) be a modular lattice

Then, if x ≤ z implies x ⊕ (y * z) = (x ⊕ y) * z ……… (1) But, for all x , z ∈ L, x ≤ x ⊕ z, So, by (1) we have x ⊕ (y * (x ⊕ z)) = (x ⊕ y) * (x ⊕ z), for all x, y, z ∈ L Conversely, suppose x ⊕ (y * (x ⊕ z)) = (x ⊕ y) * (x ⊕ z). ……… ( 2 )

Then we shall prove that L is modular. If x ≤ z then x ⊕ z = z ………. (3) Substitute (3) in (2), we have if x ≤ z ⇒ x ⊕ (y * z) = (x ⊕ y) * z Thus, (L, *, ⊕ ) is modular.

If we have a characteristic result in terms of Hasse diagram for the modular lattice then it would effectively help in deciding a given lattice is modular or not. So, we shall prove the following lemma.

Lemma 3.4.2.1: The "Pentagon Lattice" represented by the Hasse diagram given below is not modular.

Proof: From the structure of the pentagon lattices we see that c ≤ a. Now c ⊕ (b * a) = c ⊕ 0 = c. On the other hand, (c ⊕ b) * a = 1 * a = a. Definitely c ≠ a, thus, pentagon lattice is not a modular lattice.

On the other hand, it can be proved that if any lattice whose substructure is isomorphic to a pentagon lattice cannot be a modular lattice. So, we have the following theorem.

Theorem 3.4.2.2: A lattice L is modular if and only if none of its sublattice is isomorphic to the "pentagon lattice" [ for the detailed proof refer [2]]

6.3.4.3 Distributive Lattices

In this section we will define and discuss distributive lattices. A lattice (L, *, ⊕) is called a distributive lattice if for any a, b, c ∈ L, (i) a * (b ⊕ c) = (a * b) ⊕ (a * c) and (ii) a ⊕ (b * c) = (a ⊕b)*(a ⊕ c) Example 1: (P(A), ∩ , ∪ ) is a distributive lattice. Example 2: Every totally ordered set is a distributive lattice. Proof: In a totally ordered set (T, ≤) for any two elements a, b in T, we have either a ≤b or b≤a. Therefore, for any three elements a, b, c in T, the following are the possible situations in the structure of (T, ≤).

All these possible choices can be covered in the following two cases. Case 1: a ≤ b or a ≤ c [ the first four choices ] Case 2: a ≥b and a ≥ c [ the last two choices ]

For the case 1, we have, a*(b ⊕ c) = a and (a * b) ⊕ (a * c) = a ⊕ a = a For the case 2, we have, a*(b ⊕ c ) = b ⊕ c and (a * b) ⊕ (a * c) = b ⊕ c Hence any totally ordered set (T, ≤ ) is a distributive lattice.

Example 3: The set of all positive integers Z+, ordered by divisibility is a distributive lattice. Proof: We know that (Z+, ⏐ ) is lattice, where x * y = GCD(x, y) and x ⊕ y = LCM(x, y), for x, y ∈ Z+. Since every positive integer can be expressed as product of powers of primes,

Let x =

,y=

and z =

Note that xi , yi , zi may be zero also.

Now , y * z =

x ⊕ (y * z) =

=

.

=

*

= (x ⊕ y) * (x ⊕ z) Remark 1: It is clear from the definition of distributive lattice that if a ≥ c then a * c = c and a ⊕ c = a. Therefore, a * (b ⊕ c) = (a * b) ⊕ (a * c) = (a * b) ⊕ c. If a ≤c then a * c = a and a ⊕ c = c. Therefore we have a ⊕ (b * c) = (a ⊕ b) * (a ⊕ c) = (a ⊕ b) * c.

Thus, every distributive lattice is modular.

On the other hand every modular lattice need not be distributive. For example, the following modular lattice called diamond lattice is not distributive lattice.

Diamond Lattice:

For, a ⊕ (b * c) = a ⊕ 0 = a (a ⊕ b) * (a ⊕ c) = 1 * 1 = 1 Therefore, a⊕ (b * c) ≠ (a ⊕ b) * (a ⊕ c).

Hence, a diamond lattice is not a distributive lattice.

It is interesting to observe that if a lattice is not modular it cannot be a distributive lattice. It follows from the Theorem 3.4.2.2. and the above Remark1, we have the following theorem which will effectively decide the given lattice is distributive or not.

Theorem 3.4.3.1: A lattice is distributive iff none of its sublattice is isomorphic to either the pentagon lattice or diamond lattice. [ For the proof refer [ 2 ] ]

Exercise: Prove that the direct product of two distributive lattices is a distributive lattice. Theorem 3.4.3.2: Let (L, *, ⊕ ) be a distributive lattice. Then for any a, b, c ∈ L, a * b = a * c and a ⊕ b = a ⊕ c ⇒ b = c [cancellation law]. Proof: (a * b) ⊕ c = (a * c) ⊕ c = c (since a * b = a * c and by absorption law, (a * c) ⊕ c = c) Now, (a * b) ⊕ c = (a ⊕ c) * (b ⊕ c) (by distributive law) = (a ⊕ b) * (b ⊕ c) (since a ⊕ c = a ⊕ b) = b ⊕ (a * c) (by distributive law) = b ⊕ (a * b) (since a * c = a * b) = b (by absorption law) Hence, b = c .

6.3.4.4 Complemented Lattices In a lattice (L, *, ⊕), the greatest element of the lattice is denoted by 1 and the least element is denoted by 0. If a lattice (L, *,⊕) has 0 and 1, then we have, x * 0 = 0, x ⊕ 0 = x, x * 1 = x, x ⊕ 1 = 1, for all x ∈ L.

A lattice L with 0 and 1 is complemented if for each x in L there exists atleast one y ∈ L such that x * y = 0 and x ⊕ y = 1 and such element y is called complement of x.

Note: It is customary to denote complement of x by x'.

Remark 1: It is clear that complement of 1 is 0 and vice versa. Example 1: Consider the lattice (P(A), ⊆ ) Here 0 = φ and 1 = A. Then, for every S ∈ P(A), that is, S ⊆ A, complement of S is A\ S, i.e. S'.

Example 2: Consider the lattice L described in the Hasse diagram given below.

Here, c does not have a complement. For, c * 0 = 0, but, c ⊕ 0 = c. Therefore, 0 can not be a complement of c. Since a ⊕ c = c, therefore, a can not be a complement of c.

Further, since c * b = c, b is not a complement of c. Also, c * 1 = c, 1 is not a complement of c. Hence, c does not have any complement in L. Therefore, L is not a complemented lattice.

Example 3: In a totally ordered set, except 0 and 1, all the other elements do not have complements.

Example 4: Consider the lattice L described by the Hasse diagram given below.

Here, for c, we have, c * a = 0 and c ⊕ a =1 and also, c * b = 0 and c ⊕ b = 1. Thus, c has a and b as its complements. From this example, it is clear that complement of an element in a complemented lattice need not be unique.

Theorem 3.4.5.1: In a distributive lattice L with 0 and 1, if a complement of an element exists then it is unique. Proof: Let L be a distributive lattice with 0 and 1. Let a∈L. Suppose a' and a" be two complement of a. Then by the definition of complement of an element, we have a * a' = 0 and a ⊕ a' = 1 a ⊕ a" = 0 and a ⊕ a" = 1 Therefore, a * a' = a * a" and a ⊕ a' = a ⊕ a". Therefore by cancellation law in a distributive lattice, we have a' = a". Thus, complement of an element in a distributive lattice is unique.