Discrete Mathematics Notes - DMS: August 2008

Lattices

In this section we introduce lattices as special type of partial ordered set and we discuss basic properties of lattices and some
important type of special 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 (D_n, ½) ( D_n denotes the set of all positive divisors of positive number n ) is also
a lattice ordered set.

Example 4:
Consider the set B, where Bⁿ= {(l₁, l₂, … , l_n) / l_i = 0 or 1, for 1 £ r £ n}.
Define the relation £ ' by (i₁, i₂, … , i_n) £ ' (j₁, j₂, … , j_n) if and only if i_r £ j_r , 1 £ r £ n.
Note that here in the expression i_r £ j_r, £ is usual less than or equal to.
We have already seen in Example 7 of Section 6.2.1 that (B_n, £ ') is a poset.

Observe that
inf [ (i₁, i₂, ….. ,i_n), (j₁, j₂, … , j_n)] = (min (i₁, j₁), min (i₂,j₂), …. , min (i_n, j_n) ) and
sup [ (i₁, i₂, … , i_n), (j₁, j₂, … , j_n)] = (max (i₁, j₁), max (i₂,j₂), …. , max (i_n, j_n) )

Since min (i_r, j_r) and max (i_r, j_r) is either 0 or 1,
so, inf { (i₁, i₂,… , i_n), (j₁,j₂, .. ,j_n) } and sup { (i₁, i₂, … , i_n), (j₁, j₂, … , j_n) } exist in B.
Thus, (B_n, £ ) 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 :

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.
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).
( ii ) ( iii )
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 or x £ y 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 homomorphism 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 S, if a * b = c in L and a Å b = d in L, then c, d must
necessary exist in S also.

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

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

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

It is interesting to note that the substructure ₃ 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.

Exercise:ind all the sub lattices of (D₃₀, ½).

Let L be a lattice and let a < style="font-family: Symbol;">Î L / a £ x £ b }. Prove
that [a,b] is 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 D and Ñ in L ´ M, by (x, y) D (a, b) = (x * a, y b) and (x, y) Ñ (a, b) = (x Å a, yb), then we shall prove
that ( L ´ M, D ,Ñ ) is a lattice.

D and Ñ are commutative.

By definition (x, y) D (a, b) = (x * a, y b)
= (a * x, b y) (since * and are commutative)
= (a, b) D (x, y) (by definition D ).

Similarly, (x, y) Ñ (a, b) = (x Å a, y b)
= (a Å x, b y)
= (a, b) Ñ (x, y).

Hence, commutative law holds good for both operations D and Ñ .

D and Ñ are associative

[ ( x, y) D (a, b) ) D (u, v)] = [ (x * a, y b) ] D (u, v) (by definition of D )
= [ (x * a ) * u, (y b) v] (again by definition of D )
= [ x * (a * u), y (b v) ] (since * and are associative)
= [ (x, y) D (a * u, b v) ] (by definition of D )
= [ (x, y) D [ (a, b) D (u, v) ] (by definition of D )

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) D [ (x, y) Ñ (a, b) ] = (x, y) D [ x Å a, y b]
= [ x * (x Å a), y (y b) ] (by definition of D and Ñ )
= (x, y ) (by absorption law in L and M).
Therefore, absorption law hold good in L ´ M.

Idempotent

(x, y) D (x, y) = [ x * x, y y]
= (x, y) (since * and satisfy idempotent law)
Similarly, (x, y) Ñ (x, y) = (x, y).

Hence, (L ´ M, D , Ñ ) is an algebraic lattice.
Thus, (L ´ M, D , Ñ ) is a lattice.

Remark 1:

If (L, *, Å ) is a lattice, then L² = L x L is a lattice. In general one can show that
Lⁿ = L ´ L ´ L ´ …. ´ L (n times) is a lattice.

In the finite lattices, Bⁿ 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 (x₁, y₁) R (x₂, y₂) if and only if
x₁£ x₂ and y₁ £ ' y₂, is a poset. It can be proved that

(L ´ M, R) is a lattice ordered set. [ Prove !]

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) ' f (y), where £is an order relation in L and ' is an order
relation in M.

A bijecitve homomorphism is called isomorphism.

Example 1:

Consider the lattices D₆ = {1,2,3,6} and D₃₀ = {1,2,3,5,6,10,15,30}. We can show that there exist a homomorphism f
between D₆ and D₃₀.

Define a mapping f from D₆ into D₃₀ 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 D₆ and D₃₀ 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 D₆ .

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 Bⁿ into P(A_n), where

A_n = {1,2, …. , n} by f (i₁, i₂, …. , i_n) = { k / i_k ¹ 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 a * b = a).

Also, x Å z = (x Å x) Å (y Å z)
= (x Å y) Å (x Å z)
x Å y £ x Å z.
Hence the lemma.

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

x * (y Å z) ³ (x * y) Å (x * z)
x Å (y * z) £ (x Å y) * (x Å z) (distributive inequalities.)
x ³ z x * (y Å z) ³ (x * y) Å (x * z) = (x * y) Å 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 H₁ and H₂ of G, we have
H₁ * H₂ = inf (H₁, H₂) = H₁ Ç H₂ and
H₁ ÅH₂ = sup (H₁, H₂) = H₁H₂.

Since H₁ Ç H₂ and H₁H₂ are normal subgroups if both H₁ and H₂ are normal subgroups. Therefore, (M, Í ) is a lattice ordered
set. Hence (M, *, Å ) is an algebraic lattice. Let H₁, H₂, H₃, Î M such that H₁ Í H₃. Since in every lattice modular inequality
holds good, we have H₁(H₂ * H₃) Í (H₁ Å H₂) * H₃ ………. (1)

Now we shall prove that (H₁ Å H₂) * H₃ Í H₁ Å (H₂ * H₃).
Let a Î (H₁ Å H₂) * H₃i.e., a Î (H₁ H₂) Ç H₃a Î H₁ H₂ and a Î H₃a = h₁h₂ and a = h₃, for some h₁ Î H₁ ,h₂ Î H₂ and h₃ Î H₃.
Therefore, h₁h₂ = h₃ h₂ = h₁^-1h₃ Î H₃ [ h₃ Î H₃ and h₁Î H₁ Í H₃ , therefore, h₁^-1 h₃Î H₃]
h₂Î H₂ and h₂Î H₃
Thus, h₂ Î H₂ Ç H₃ ……… (2)
Since a = h₁h₂, we have a Î H₁(H₂ Ç H₃) (by (2))
That is, aÎ H₁ Å(H₂ * H₃)
That is, (H₁ ÅH₂) * H₃ Í H₁ Å(H₂ * H₃) ………. (3)
From (1) and (3) we have
H₁ Å (H₂ * H₃) = (H₁ Å H₂) * H₃.
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]]

Exercise 1:
Prove that the intervals [x, x Åy] and [ x * y, y] are isomorphic in a modular lattice. [ By interval [u ,v] we mean the set
{ t Î L / u £ t £ v }]

Exercise 2:
Prove that if a ³ b and if there exists c Î L with a Å c = b Å c and a * c = b * c then a = b.

6.3.4.3 Distributive LatticesIn this section we will define and discuss distributive lattices.

A lattice (L, *, Å) is called a distributive lattice if for any a, b, c Î L,
a * (b Å c) = (a * b) Å (a * c)
a Å (b * c) = (a Å b)*(a Å c)

Example 1:
(P(A), Ç , È ) is a distributive lattice. [ For proof refer Section1.2]

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 x_i, y_i , z_imay 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,Å(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 .
3.4.4 Complemented Lattices

In this section we shall define complemented lattices and discuss briefly.

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 = f 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.

Exit Quiz Questions:

Is the poset A = {2, 3, 6, 12, 24, 36, 72} under the relation of divisibility a lattice.
If L₁ and L₂ are the lattices shown in the following figure, draw the Hasse diagram.of L₁´ L₂ with product partial order.

Show that a subset of a totally ordered set is a sublattice.
Find all the sublattices of D₂₄ that contains at least five elements.
Shows that sublattice of a distributive lattice is distributive.
Show that the lattice given below is not a distributive lattice but modular.

Find the complement of each element of D₄₂.
Determine whether the lattice given below is distributive, complemented or both.

Discrete Mathematics Notes - DMS

Tuesday, August 12, 2008

Boolean Algebra

Lattices

Labels