1

Lattices - Finite Boolean algebras

Posets

Denition 1. Partial ordering. A binary relation ( ) on a set is called a

partial ordering of when it is
reexive ( for all ),
antisymmetric ( and imply = ), and
transitive ( and imply ).
Example 1. Example for partial ordering. The relation is a partial ordering
of the set of all positive integers.
( for all ;
and imply = ; and
and imply . )
Example 2. Example for partial ordering. The relation (meaning that
is a divisor of ) is a partial ordering of the set of all positive integers.
( for all ;
and imply = (since and are positive); and
and imply . )
Example 3. Example for partial ordering. For any set , consider the power
set ( ), the set of all subsets of . The relation is a partial ordering of ( ).
( for all ;
and imply = ; and
and imply . )
Denition 2. Poset. A set with a partial order relation dened on it is
called a partially ordered set or a poset, i.e., it is a pair [, ].
Remark 1. The converse of any partial ordering is again a partial ordering,
called the dual of , and denoted . Thus, if and only if .

2
Denition 3. Duality Principle.
We can replace the relation in any theorem about posets by the relation
throughout, without aecting its truth. This theorem about theorems is called the
duality principle of the theory of posets.
Example 4. (, ) and (, ).
Consider the poset [, ] of all positive integers under the divisibility relation.
The greatest common divisor = (, ) of any two positive integers and
has the following properties:
(i) , , and
(ii) if and , then .
The least common multiple = (, ) of any two positive integers and
has the following properties:
(i) , , and
(ii) if and , then .
We shall now generalize these concepts.
Denition 4. Lower bound, Upper bound, Greatest lower bound, Least
upper bound.
Let be a subset of a poset .
1. We dene to be a lower bound of when for all .
2. We dene to be an upper bound of when for all .
3. We dene to be the greatest lower bound of when
(i) is a lower bound of and
(ii) for any other lower bound of .
We write = .
4. We dene to be the least upper bound of when
(i) is an upper bound of and
(ii) for any other upper bound of .
We write = .

Denition 5. (, ) and (, ).
Let [, ] be any poset and let , be given.
An element is called the greatest lower bound of and when
(i) , , and
(ii) if and , then .
We write = (, ).
An element is called the least upper bound of and when
(i) , , and
(ii) if and , then .
We write = (, ).
Denition 6. Chain. Let [, ] be a poset. A chain ( or totally ordered or simply
ordered set) is a subset of in which every pair of elements are comparable. i.e.,
given and , either or .

Lattices

Denition A. Lattice. A is a poset in which any two elements and

have a called the and a called the .
Remark 2. Symbols: is called wedge and is called vee.
(or ) is called the meet of and or the product of and .
(or ) is called the join of and or the sum of and .
Every poset in which {, } and {, } exist for all , can be
regarded as a lattice by dening = {, } and = {, }.
Theorem 1. Let [, , ] be a lattice. For all , , , the following laws are
satised
L1. Idempotent laws
= ,
= .

4
L2. Commutative laws
= ,
= .
L3. Associative laws
( ) = ( ) ,
( ) = ( ) .
L4. Absorption laws
( ) = ,
( ) = .
Proof. By the duality principle, which interchanges and , it suces to prove
one of the two identities in each of 1, 2, 3, 4.
Proof of L1. Idempotent laws: = , = .
We have to show that = .
i.e., to show that {, } = .
i.e., to show that (i) , , and (ii) if and , then .
It is clearly true.
Proof of L2. Commutative laws: = , = .
We have to show that = .
= {, } = {, } = .
Proof of L3. Associative laws: ( ) = ( ) , ( ) = ( ) .
We have to show that ( ) = ( ) .
( ) = {, {, }} = {, , } = { {, }, } = ( ) .
Proof of L4. Absorption laws: ( ) = , ( ) = .
We have to show that ( ) = .
i.e., to show that {, } = .
i.e., to show that {, {, }} = .
i.e., to show that
(i) , {, }, and
(ii) if and {, }, then .
{, } follows from the denition of .

5
Theorem 2. Let [, , ] be a lattice. For any , , .
= = .
Proof.
(i) Proof of = .
I. Assume that to prove = .
i.e., to prove and .
Clearly, . (by denition of GLB)
Since and . (lower bound greatest lower bound)
II. Conversly, assume that = .
It is possible only when .
i.e., = .
(ii) Proof of = .
Follows from the duality principle.
(iii) Proof of = = .
Assume that = to prove = .
Consider ( ) = ( ) = ( )
But ( ) = (by absorption)
Thus = = .

Denition 7. A lattice is called distributive when it satises the two distributive

laws
( ) = ( ) ( ) and
( ) = ( ) ( ).
Otherwise it is called nondistributive.
Example 12. The distributive laws are satised by any sets under intersection
and union; hence they are identities in the lattice ( ), the power set ( ) of all
subsets of any set .
.........................................................................................
Theorem 4. In any lattice, the following distributive inequalities hold.
( ) ( ) ( )

6
( ) ( ) ( )
Proof.
(i) Proof of ( ) ( ) ( ).
I. and
is an upper bound of and
the least upper bound of and is, clearly,
i.e., ( ) ( ) .
II. and .
and .
and
is an upper bound of and .
the least upper bound of and is, clearly,
i.e., ( ) ( ) .
III. ( ) ( ) and ( ) ( )
( ) ( ) is a lower bound of and
the greatest lower bound of and is, clearly, ( ) ( )
i.e., ( ) ( ) ( )
(ii) Proof of ( ) ( ) ( ).
Follows from the duality principle.
Lemma 3. In any distributive lattice
= and = together imply = .
Proof. Assume that = and = .
= ( ) (by absorption law)
= ( ) (by assumption)
= ( ) ( ) (by distributive law)
= ( ) ( ) (by assumption)
= ( ) ( ) (by commutative law)
= ( ) (by distributive law)
= ( ) (by assumption)
= (by absorption law).

Theorem 4. In any lattice, the modular inequalities hold.

if ( ) ( )
if ( ) ( )
Proof.
(i) Proof of ( ) ( ) .
Since any lattice satises distributive inequality,
( ) ( ) ( ).
Since = (by theorm ?)
Thus ( ) ( ) .
(ii) Proof of if ( ) ( ) .
Follows from the duality principle.

Denition 18. A lattice is called modular

if , then ( ) = ( ) .

Lemma 5. In any modular lattice, each of the two identities hold.

[ ( )] = ( ) ( ),
[ ( )] = ( ) ( )
Proof. I. Assume that: If , then ( ) = ( ) .
We show that [ ( )] = ( ) ( ).
For, take = , = and = .
Since , we have, by assumption, [ ( )] = ( ) ( ).
II. Assume that: If , then ( ) = ( ) .
We show that [ ( )] = ( ) ( ).
Follows, by duality principle.

Remark 8. In any lattice [, , ], the relation is a partial ordering of .

Proof.

8
1. Reexive: for all .
i.e., to show that = for all . It is 1.
2. Antisymmetric: and imply = .
i.e., to show that = and = imply = .
= = = .
3. Transitive: and imply .
i.e., to show that = and = imply = .
= = ( ) = ( ) = .

Sublattices; direct products; homomorphism

Denition 14. A sublattice of a lattice is a subset such that

, and .
Example 10. Consider the power set ( ) of all subsets of a given set . ( )
is a lattice. A family of subsets of which contains with any and also
and is called a ring of sets.
i.e., , , .
Thus a ring of sets is a sublattice of a power set ( ).
Denition 15. Let and be lattices.
= {(, ) : , }.
We dene, in ,
(1 , 1 ) (2 , 2 ) = (1 2 , 1 2 ) and
(1 , 1 ) (2 , 2 ) = (1 2 , 1 2 ).
The direct product is a lattice. Since
1 : (, ) (, ) = ( , ) = (, ).
2 : (1 , 1 ) (2 , 2 ) = (1 2 , 1 2 ) = (2 1 , 2 1 ) = (2 , 2 ) (1 , 1 ).
3 : ((1 , 1 ) (2 , 2 )) (3 , 3 )
= (1 2 , 1 2 ) (3 , 3 )
= ((1 2 ) 3 , (1 2 ) 3 )
= (1 (2 3 ), 1 (2 3 ))
= (1 , 1 ) (2 3 , 2 3 )

9
= (1 , 1 ) ((2 , 2 ) (3 , 3 )).
4 : (, ) ((, ) (, ))
= (, ) ( , )
= ( ( ), ( ))
= (, ).
Example 11. ( ) = ( ) ( ).
If ( ) and ( ) are the power sets of all subsets of two given sets and ,
considered as lattices under the operations of set intersection and set union ,
then ( ) is isomorphic to the direct product of the two lattices ( ) and
( ).
( is the disjoint sum of and . )
Denition 19. A complemented lattice is a lattice with universal bounds and
in which every element has at least one complement , with = and
= .
( and are universal bounds means that = , = , = ,
= for all . )
Denition 20. A Boolean lattice is a lattice which is both complemented and
distributive.
Theorem 6. In any Boolean lattice,
( ) = ,
( ) = , ( ) = (de Morgans laws).
Proof. Let be a Boolean lattice.
is the complement of = and = .
( ) is the complement of ( ) = and ( ) = .
Hence = ( ) and = ( ) .
Thus = ( ) and = ( ) .
As a Boolean lattice is a distributive lattice, we have ( ) = .
Dene a function : by () = , for every .
Claim 1. The inverse of is .
(()) = ( ) = ( ) = .

10
Claim 2. is a bijection.
Follows from Claim 1.
Claim 3. inverts order.
i.e., to show that if , then () ().
= = .
= = ( ) = ( ) ( ) = ( ) = .
i.e., = .
.
() ().
By Claim 3, inverts order and hence inverts glb and lub.
Thus ( ) = ( ) = () () = .
Similarly, ( ) =
Denition 21. A function : from a lattice to a lattice is called
a homomorphism of lattices when for all , ,
( ) = () () and ( ) = () ()
in .
Remark 10. Homomorphism of lattices is necessarily order-preserving.
Proof. If in , then = , and hence ( ) = ().
Since is a morphism of lattice, ( ) = () ().
Hence () () = ().
() ().
Example 14. Example of an order-preserving map which is not a homomorphism
of lattices.
Let = [, ] be any poset.
For each , dene () = { : }.
Clearly, () is a subset of . i.e., () .
In other words, () (), where () is the power set of .
Dene : () by () = (), .
Claim 1. is order-preserving.
i.e., to show that if in , then () () in ().

11
For, if (), then () and hence .
and implies that .
Hence (). i.e., ().
Claim 2. If is a lattice, then ( ) = () ().
( )
( )

and
() and ()
() ()
() ().
Claim 3. If is a lattice, then () () ( ).
() ()
() ()
() or ()
or

( )
( ).
Claim 4. If is a lattice, then in general () () = ( ).
Consider the lattice 5 dened by {, , , , } and , , ,
, , . () = {, }, () = {, }, () () = {, , },
and ( ) = () = {, , , , }.
Hence, is not a homomorphism of lattices.

Boolean algebras

Denition 11. Boolean algebra.

A = [, , ,, , ] is a set with two binary operations
, , two universal bounds , , and one unary operation such that for all

12
, , ,
L1. Idempotent laws
= ,
= .
L2. Commutative laws
= ,
= .
L3. Associative laws
( ) = ( ) ,
( ) = ( ) .
L4. Absorption laws
( ) = ,
( ) = .
L5. Modularity laws
[ ( )] = ( ) ( ),
[ ( )] = ( ) ( ).
L6. Distributive laws
( ) = ( ) ( ),
( ) = ( ) ( ).
L7. Universal bounds
= ,
= ,
= ,
= .
L8. Complements
= ,
= .
L9. Involution
( ) = .
L10. de Morgan laws

13
( ) = ,
( ) = .
Remark 6. Any Boolean algebra = [, , ,, , ] is clearly a lattice.
Example 8. Example of a Boolean algebra. For any positive integer , let
= {1, 2, . . . , }. Let
= [( ), , , , , ]
consists of
the power set of all subsets of the set ,
with taken as set intersection,
with taken as set union,
with

as set complement,

with as the empty set and

with as the set .
is a Boolean algebra with 2 elements.
Denition 22. A function : from a Boolean algebra to a Boolean
algebra is called a Boolean morphism when for all , ,
( ) = () (), ( ) = () () and ( ) = (())
in .