Relations

Dr. Mitesh S. Joshi.

January 28, 2022

1
Contents
1 Introduction 3

2 Relations 3

3 Properties of a Binary Relations 6

4 Relation Matrix and the Graph of a Relation 8

4.1 Graphs of relations . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.2 Properties of Graphs . . . . . . . . . . . . . . . . . . . . . . . . 9
4.3 Partition and Covering of a set . . . . . . . . . . . . . . . . . . . 10

5 Equivalence Relations 11
5.1 Compatibility Relations . . . . . . . . . . . . . . . . . . . . . . . 13

6 Composition of Binary Relation 14

7 Partial Ordering 16
7.1 Partially ordered set: Representation and Associated Terminology 18

8 Lattices 24
8.1 Definition and Examples . . . . . . . . . . . . . . . . . . . . . . 24
8.2 Some properties of Lattices . . . . . . . . . . . . . . . . . . . . . 25
8.3 Lattices as an algebraic systems . . . . . . . . . . . . . . . . . . 25
8.4 Sub-lattice, Direct product and Homomorphism . . . . . . . . . . 26
8.5 Some special Lattices . . . . . . . . . . . . . . . . . . . . . . . . 27
8.6 Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . 28
8.7 Sub-algebra, Direct product and Homomorphism . . . . . . . . . 29

2
1 Introduction

2 Relations
Definition 2.1. Any set of ordered pairs defines a Binary Relations.

Illustrations:

(a) The relations ”greater than” and ”less than” defined on the set of real num-
bers R defines a Binary relation.

> or <= {(x, y)|x, y are real numbers and x > y or x < y}

(b) The relation of ”Father to his child” defines a Binary relation on the set of
males
F = {(x, y)|x is a father of y}

(c) The relation S defined as follows is a Binary relation.

S = {(2, 4), (1, 3), (λ, 6), (John, µ)}

(d) The relations Q as ”square of real numbers” defined on R is a Binary rela-

tion.
Q = (x, x2 )|x ∈ R


Definition 2.2. Let S be a binary relation. The set D(S) of all objects x such that
for some y, (x, y) ∈ S is called domain of S, that is
   

D(S) = x(∃y) (x, y) ∈ S

Similarly,
Definition 2.3. The set R(S) of all objects y such that x, (x, y) ∈ S is called the
range of S, that is    

R(S) = y (∃x) (x, y) ∈ S


Illustration: For the relation S defined Illustration[(c)]

D(S) = {2, 1, λ, John} R(S) = {4, 3, 6, µ}

Definition 2.4. Let X and Y be two sets. A subset of the Cartesian product X ×Y
defines a relation, say C. For any such relation C, we have D(C) ⊆ X and
R(C) ⊆ Y , and the relation C is said to be a relation from X to Y . If Y = X,
then C is said to be a relation from X to X. In such a case, C is called the relation
in X.

3
Definition 2.5. Any relation in X is a subset of X × X. The set X × X defines a
relation in X and is called Universal relation in X, while the empty set which is
also subset of X × X is called a void relation in X.

Definition 2.6. Let R and S be two relations such that

x(R ∩ S)y ⇔ xRy ∧ xSy

x(R ∪ S)y ⇔ xRy ∨ xSy
x(R − S)y ⇐⇒ xRy ∧ ¬(xSy)
x(¬R)y ⇐⇒ x(¬R)y

Problem 2.7. Let X = {1, 2, 3, 4}. If

  

R = (x, y)x ∈ X ∧ y ∈ Y ∧ (x − y) is an integral non-zero multiple of 2


= {(1, 3), (3, 1), (2, 4), (4, 2)}

  

S = (x, y)x ∈ X ∧ y ∈ Y ∧ (x − y) is an integral non-zero multiple of 3


= {(1, 4), (4, 1)}

(a) Find R ∪ S and R ∩ S.

(b) If X = {1, 2, 3, 4, . . . . . .} then obtain R ∩ S.

Solution 2.8. The solution may given as follows.

(a) R ∪ S = {(1, 3), (3, 1), (2, 4), (4, 2), (1, 4), (4, 1)} and R ∩ S = φ.
  

(b) R∩S = (x, y)x ∈ X ∧ y ∈ Y ∧ (x − y) is an integral non-zero multiple of 6


Problem 2.9. Consider the following three relations

  

R1 = (x, y)(x, y) ∈ (R × R) ∧ (x ∗ y) ≥ 1

  
 2 2
R2 = (x, y)(x, y) ∈ (R × R) ∧ x + y ≤ 9

  
 2
R3 = (x, y)(x, y) ∈ (R × R) ∧ y < x


Then obtain the following relations graphically.

(a) R4 = R1 ∩ R2 ∩ R3

(b) R5 = R2 ∩ (R1 ∪ R3 ) ∩ ¬(R1 ∩ R3 )

(c) R6 = R1 ∩ ¬R2 ∩ R3

(d) R7 = ¬(R1 ∪ R3 ) ∩ R2

Solution 2.10. The graphical representation of the relations R1 , R2 and R3 is

given by

4
 Figure 1: Graphical presentation of the relations R1 , R2 and R3 .

The relations R4 , R5 , R6 and R7 as set representations can be given by

  
 2 2 2
R4 = R1 ∩R2 ∩R3 = (x, y)(x, y) ∈ (R × R) ∧ (x ∗ y) ≥ 1 ∧ x + y ≤ 9 ∧ y < x

R5 = R2 ∩ (R1 ∪ R2 ) ∩ ¬(R1 ∩ R3 )
  
 2 2 2

2


= (x, y)(x, y) ∈ (R × R) ∧ x + y ≤ 9 ∧ x ∗ y ≥ 1 ∨ y < x ¬ x ∗ y ≥ 1 ∧ y < x
  
 2 2

2
R6 = R1 ∩¬R2 ∩R3 = (x, y)(x, y) ∈ (R × R) ∧ (x ∗ y) ≥ 1 ∧ ¬ x + y ≤ 9 ∧ y < x
  
 2

2 2
R7 = ¬(R1 ∪R3 )∩R2 = (x, y)(x, y) ∈ (R × R) ∧ ¬ (x ∗ y) ≥ 1 ∨ y < x ∧ x + y ≤ 9

Now, the newly defined relations R4 , R5 , R6 and R7 can be pictorially defined as,

Figure 2: Graphical presentation of the relations R4 , R5 , R6 and R7 .

5
3 Properties of a Binary Relations
Definition 3.1. A relation R in a set X is reflexive if, for every x ∈ X, xRx, that
is (x, x) ∈ R or

R is reflexive in X ⇐⇒ (x) (x ∈ X → xRx) (1)

Illustrations:

1. The relation ≤ or ≥ is reflexive on the set of real numbers.

2. The relation inclusion or superset is reflexive on the family of all subsets of

a universal set.

3. The relation of equality of sets is reflexive.

4. The relation < and > are not reflexive on the set of real numbers.

5. The relation proper inclusion in not reflexive on the family of all subsets of
a universal set.

Definition 3.2. A relation R in a set X is symmetric if, for every x, y ∈ X,

whenever xRy, then yRx. That is

R is symmetric in X ⇐⇒ (x)(y) (x ∈ X ∧ y ∈ X ∧ xRy → yRx) (2)

Illustrations:

1. The relation of equality(=) is symmetric on the set of real numbers.

2. The relation of similarity of triangles is both reflexive and symmetric in

the set of triangles.

3. The relation ≤, < and ≥, > are not symmetric on the set of real numbers.

4. The relation of being a brother is not symmetric in the set of all people
but is symmetric in the set of all males.

Definition 3.3. A relation R in a set X is transitive if, for every x, y and z in X,

whenever xRy and yRz then xRz. That is

R is transitive in X ⇐⇒ (x)(y)(z) (x ∈ X ∧ y ∈ X ∧ z ∈ X ∧ xRy ∧ yRz → xRz)

(3)

Illustrations:

1. The relation ≤, <, = and ≥, >, = are all transitive on the set of real num-
bers.

2. The relation ⊆, ⊂, = are all transitive in the family of subsets of a universal

set.

3. The relation of similarity of triangles in a plane is transitive.

6
 4. The relation of being a mother is not transitive.

Definition 3.4. A relation R in a set X is irreflexive if, for every x ∈ X, xRx,

that is (x, x) ∈
/ R or

R is reflexive in X ⇐⇒ (x) (x ∈ X → (x, x) ∈

/ X) (4)

Illustrations:

1. The relations < and > are irreflexive on the set of real numbers.

2. The relation of proper inclusion (⊂) is irreflexive in the family of all non-
empty subsets of a universal set.

Remark:

Note that Any relation which is not reflexive is not necessarily irreflexive.

Let X = {1, 2, 3} and consider the following relation S,

S = {(1, 1), (1, 2), (3, 2), (2, 3), (3, 3)}

This relation S is neither reflexive nor irreflexive.

Definition 3.5. A relation R in a set X is Anti-symmetric if, for every x, y ∈ X,

whenever xRy and Y Rx, then x = y. Symbolically,

R is anti-symmetric in X ⇐⇒ (x)(y) (x ∈ X ∧ y ∈ X ∧ xRy ∧ yRx → x = y)

(5)

Remark:
Not that it is possible to have a relation which is both symmetric and anti-
symmetric. This is the case when each element is either related to itself or not
related to any element. Let X = {1, 2, 3}, then the following relation S is both
symmetric and anti-symmetric.

S = {(1, 1), (2, 2), (3, 3)}

Illustrations:

1. The relation > and < on the set of real numbers R is both irreflexive and
transitive.

2. The relation equality (=) in R is reflexive, symmetric and transitive.

3. Let X be the set of all courses offered at university, and for all x ∈ X and
y ∈ X, xRy if x is prerequisite of y. This relation is of being prerequisite
is irreflexive and transitive.

4. Let X be the set of all male Canadians and let xRy, where x ∈ X and
y ∈ X denote the relation ”x is brother of y”. This relation R is irreflexive
and symmetric and not transitive.

7
 5. Let X be the collection of the subsets a universal set. The relation of inclu-
sion (⊆) in X is reflexive,anti-symmetric and transitive.

6. Let X be the collection of the subsets a universal set. The relation inclusion
(⊂) in X is irreflexive,anti-symmetric and transitive.

Remark:
In general, any relation which is irreflexive and symmetric cannot be transitive.

4 Relation Matrix and the Graph of a Relation

Definition 4.1. A relation R from a finite set X in a finite set Y can also be repre-
sented by a matrix called the relation matrix of R. Let X = {x1 , x2 , . . . . . . , xm }
and Y = {y1 , y2 , . . . . . . , yn } and R be a relation from X to Y , the relation matrix
MR of order m × n is defined as,
(
1 if (xi , yj ) ∈ R
MR = [rij ]m×n where, rij = (6)
0 if (xi , yj ) ∈
/R

Illustration: Let X = {x1 , x2 , x3 } and Y = {y1 , y2 } and R be the relation from

X to Y is defined as,

R = {(x1 , y1 ), (x2 , y1 ), (x2 , y2 ), (x3 , y2 )}

The corresponding relation matrix MR of order 3 × 2 is given by,

 
1 0
MR = 1 1
0 1

A relation can also be represented pictorially by drawing its graph. Let R be a

relation in a set X = {x1 , x2 , . . . , xm }. The elements of X are represented by
points or circles called nodes and the elements in R are represented by directed
edge corresponding to an ordered pair (xi , yj ) ∈ R.Following figures shows the
pictorial representation of relations.

4.1 Graphs of relations

Figure 3: Graphs of relations.

8
4.2 Properties of Graphs

Figure 4: Symmetric and Anti-relations.

Figure 5: Transitive relations.

  

Problem 4.2. Let X = {1, 2, 3, 4} and R = (x, y)x > y . Draw the graph of

R and also give its maatrix.
  

Solution 4.3. Since, X = {1, 2, 3, 4} and R = (x, y)x > y , we have


R = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}

Hence, the corresponding relation matrix MR is given by

 
0 0 0 0
1 0 0 0
MR = 1 1 0 0


1 1 1 0

The corresponding digraph of the relation R is given by,

9
 Figure 6: Digraph of relation R.

Problem 4.4. Let A = {a, b, c} and denote the subset of A by B0 , B1 , . . . . . . , B7 .

Then B0 = φ, B1 = {c}, B2 = {b}, B3 = {b, c}, B4 = {a}, B5 = {a, c},
B6 = {a, b} and B7 = {a, b, c}. If R is the relation proper inclusion on the
subsets B0 , B1 , . . . . . . , B7 , then give the matrix of the relation R.

Solution 4.5. The correspoding relation matrix MR is given by,

 
0 1 1 1 1 1 1 1
0 0 0 1 0 1 0 1 
 
0 0 0 1 0 0 1 1 
 
0 0 0 0 0 0 0 1 
MR =  0 0 0 0 0 1 1 1 

 
0 0 0 0 0 0 0 1 
 
0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0

4.3 Partition and Covering of a set

Definition 4.6. Let S be a given set and A = {A1 , A2 , . . . . . . , Am } where each
Ai ⊂ S for i = 1, 2, . . . , m and

∪m
i=1 Ai = S (7)

Then the set A is called covering of S and the sets A1 , A2 , . . . , Am are said to
cover S.

Definition 4.7. Let S be a given set and A = {A1 , A2 , . . . , Am } where each

Ai ⊂ S for i = 1, 2, . . . , m and

∪m m
i=1 Ai = Sand ∩i=1 Ai = φ (8)

Then the set A is called partition of S and the sets A1 , A2 , . . . , Am are called the
blocks of S.

10
Illustration: Let S = {a, b, c} and consider the following collection of subsets of
S.
A = {{a, b}, {b, c}} , B = {{a}, {a, c}} , C = A = {{a}, {b, c}}
and
D = {a, b, c} , E = {{a}, {b}, {c}} , F = {{a}, {a, b}, {a, c}}
Remark:

1. The sets A and F are covering of S while C, D and E are partitions of S.

2. The set B is neither a partition nor a covering of S.
3. The partition D has one block while E has three blocks.
4. Every partition is also a covering of a set.

5 Equivalence Relations
Definition 5.1. A relation R in a set X is called an equivalence relation if it is
reflexive, symmetric and transitive.

Illustrations:

1. Equality of numbers on a set of real numbers

2. Equality of subsets of a universal set
3. Similarity of triangles on the set of triangles
4. Relation of lines being parallel on a set of lines in a plane
5. Relation of living in the same town on the set persons living in Canada.
Problem 5.2. Let X = {1, 2, 3, 4} and R = {(1, 1), (1, 4), (4, 1), (4, 4), (2, 2), (2, 3), (3, 2), (3, 3)}.
Write the matrix of R and sketch its graph.
Solution 5.3. The corresponding graph is given by The corresponding relation

Figure 7: Digraph of relation R.

matrix MR is given by,  

1 0 0 1
0 1 1 0
MR = 
0

1 1 0
1 0 0 1

11
   

Problem 5.4. Let X = {1, 2, 3, 4, 5, 6, 7} and R = (x, y)(x − y)is divisible by 3 .

Show R is an equivalence relation. Draw the graph of R.

Solution 5.5. We can prove R as an equivalence relation in the following way.

(1) Let a ∈ X, (a − a) = 0 · 3 ⇒ (a − a) is divisible by 3. Hence, aRa or R is

reflexive.
 
 
(2) Let a, b ∈ X, (a − b) = 3 · k k ∈ Z ⇒ (b − a) = 3 · (−k)(−k) ∈ Z. This
shows that (b − a) is divisible by 3. Hence, if aRb then bRa. Therefore R is
Symmetric.

(3) Let a, b, c ∈ X, Let aRb ⇒ (a − b) = 3k1 and bRc ⇒ (b − c) = 3k2 . Hence

(a − c) = (a − b) + (b − c)
= 3k1 + 3k2
⇒ (a − c) = 3(k1 + k2 ) ⇒ aRc

Hence, R is an equivalence relation.

The corresponding graph is given by

Figure 8: Digraph of relation R.

Problem 5.6. Let I denote the set of all positive integers and m ∈ I. For x, y ∈ I,
the relation R is defined as,
  

R = (x, y)(x − y)is divisible by m


Show that R is an equivalence relation.

Definition 5.7. Let R be an equivalence relation on a set X. For any x ∈ X, the

set [x]R ⊆ X given by,
 
[x]R = y y ∈ X ∧ xRy (9)

is called an R−equivalence class generated by x ∈ X.

Theorem 5.8. Every equivalence relation on a set generates a unique partition of

the set. The blocks of this partition correspond to the R−equivalence classes.

12
Definition 5.9. The R−equivalence class generated by an element x ∈ X by [x]r
or x/R and the family of equivalence classes by X/R, which is also written as
X modulo R or in short XmodR. X/R is called the quotient set of X by R.

Problem 5.10. Let Z be the set of integers and let R be the relation called ”con-
gruence modulo 3” defined by,
  

R = (x, y)x ∈ Z ∧ y ∈ Z ∧ (x − y) is divisible by 3

Determine the equivalence classes generated by the elements of Z.

Solution 5.11. The equivalence classes are

[0]R = {. . . , −6, −3, 0, 3, 6, . . .}

[1]R = {. . . , −5, −2, 1, 4, 7, . . .}
[2]R = {. . . , −4, −1, 2, 5, 8, . . .}

The quotient set is given by,

 
Z/R = [0]R , [1]R , [2]R .

 
Problem 5.12. Let X = {a, b, c, d, e} and let C = {a, b}, {c}, {d, e} . Show
that the partition of C defines an equivalence relation in X.

Solution 5.13.
 
R = (a, a), (b, b), (a, b), (b, a), (c, c), (d, d), (e, e), (d, e), (e, d)

5.1 Compatibility Relations

Definition 5.14. A relation R in X is said to be a compatibility relation if it is
reflexive and symmetric.
 
Illustrations: Let X = ball, bed, dog, let, egg and let the relation R is given
by,
  

R = (x, y)x, y ∈ X ∧ xRy if x and y contain some common letter


Definition 5.15. Let X be the set and ≈ a compatibility relation on X. A subset

A ⊆ X is called a maximal compatibility block if any element of A is compatible
to every other element of A and no element of X − A is compatible to all the
elements of A.

13
6 Composition of Binary Relation
Definition 6.1. Let R be a relation from X to Y and S be a relation from Y to Z.
Then a relation written as R ◦ S is called a composite relation of R and S where
  

R◦S = (x, z)x ∈ X ∧z ∈ Z ∧(∃y) (y ∈ Y ∧ (x, y) ∈ R ∧ (y, z) ∈ S) (10)


Remarks:

(1) The composite operation (◦) is not commutative, that is R ◦ S 6= S ◦ R.

(2) The composite operation (◦) is associative, that (R ◦ S) ◦ P = R ◦ (S ◦ P ).
   
Problem 6.2. Let R = (1, 2), (3, 4), (2, 2) and S = (4, 2), (2, 5), (3, 1), (1, 3) .
Find R ◦ S, S ◦ R, R ◦ (S ◦ R), (R ◦ S) ◦ R, R ◦ R, S ◦ S, R ◦ R ◦ R.
Solution 6.3.
 
R ◦ S = (1, 5), (3, 2), (2, 5)
 
S ◦ R = (4, 2), (3, 2), (1, 4) 6= R ◦ S
 
(R ◦ S) ◦ R = (3, 2)
 
R ◦ (S ◦ R) = (3, 2) = (R ◦ S) ◦ R
 
R ◦ R = (1, 2), (2, 2)
 
S ◦ S = (4, 5), (3, 3), (1, 1)
 
R ◦ R ◦ R = (1, 2), (2, 2)

Problem 6.4. Let R and S be two relations on a set of positive integers I :

     
 
R = (x, 2x)x ∈ I S = (x, 7x)x ∈ I

Find R ◦ S, R ◦ R, R ◦ R ◦ R and R ◦ S ◦ R.
Solution 6.5.
  

R ◦ S = (x, 14x)x ∈ I = S ◦ R
  

R ◦ R = (x, 4x)x ∈ I

  

R ◦ R ◦ R = (x, 8x)x ∈ I

  

R ◦ S ◦ R = (x, 28x)x ∈ I


14
    
Problem 6.6. Let R = (1, 2), (3, 4), (2, 2) and S = (4, 2), (2, 5), (3, 1), (1, 3) .
Then obtain MR , MS , M(R◦S) and M(S◦R) .
 
Solution 6.7. Since, R = (1, 2), (3, 4), (2, 2) the matrix of a relation R is
given by,  
0 1 0 0 0
0 1 0 0 0
 
0
MR =  0 0 1 0 
0 0 0 0 0
0 0 0 0 0
 
Since, S = (4, 2), (2, 5), (3, 1), (1, 3) , the matrix of a relation S is given by,
 
0 0 1 0 0
0 0 0 0 1
 
MS =  1 0 0 0 0 

0 1 0 0 0
0 0 0 0 0
 
Since, R ◦ S = (1, 5), (3, 2), (2, 5) , the matrix of a relation is
    
0 1 0 0 0 0 0 1 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0 1 0 0 0 0 1
    
MR◦S = 
0 0 0 1 0  1 0 0 0 0 = 0 1 0 0 0
   
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 
Since, S ◦ R = (4, 2), (3, 2), (1, 4) 6= R ◦ S, the matrix of a relation is
    
0 0 1 0 0 0 1 0 0 0 0 0 0 1 0
0 0 0 0 1 0
  1 0 0 0 0
  0 0 0 0
 
MS◦R 1
= 0 0 0 0 0 0 0 1 0 = 0 1 0 0 0
 

0 1 0 0 0 0
 0 0 0 0  0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Definition 6.8. Given a relation R from X to Y , a relation R̄ from Y to X is

called converse of R, where the ordered pair of R̄ are obtained by interchanging
the members in each ordered pairs of R. This means x ∈ X and y ∈ Y , that
xRy ⇐⇒ yRx.

Remark: MR̄ = T ransposeof MR .

Problem 6.9. Given the matrices MR and MS , find MR◦S , MR̄ , MS̄ , MR◦S
¯ and
show that MR◦S
¯ = MS̄◦R̄ .

Solution 6.10.  
1 0 1
MR = 1 1 0
1 1 1

15
and  
1 0 0 1 0
MS = 1 0 1 0 1
0 1 0 1 0
The matrices MR̄ and MS̄ are given by,
 
1 1 1
MR̄ = 0 1 1
1 0 1

and  
1 1 0
0 0 1
 
0
MS̄ =  1 0

1 0 1
0 1 0
The matrices MR◦S , MR◦S
¯ and MS̄◦R̄ are given by,
 
1 1 0 1 0
MR◦S = 1 0 1 1 1
1 1 1 1 1
 
1 1 1
1 0 1
 
MR◦S
¯ 0
= 1 1

1 1 1
0 1 1
 
1 1 1
1 0 1
 
MS̄◦R̄ 0
= 1 1
 = MR◦S
¯
1 1 1
0 1 1
Definition 6.11. Let X be any finite set and R be a relation in X. The relation
R+ = R ∪ R2 ∪ R3 . . . is called transitive closer of R in X.

Theorem 6.12. The transitive closer R+ of a relation R in a finite set X is transi-

tive. Also for any transitive relation P in X such that R ⊆ P , we have R+ ⊆ P .
In this case R+ is the smallest transitive relation containing R.

Proof. The proof of the above theorem can be given as follows.

7 Partial Ordering
Definition 7.1. A binary relation R in a set P is called a partial order relation or
partial ordering if P iff R is reflexive, anti-symmetric and transitive.

Remark: It is convenient to denote a partial ordering by the symbol ≤.

16
Definition 7.2. If ≤ is partial ordering on P , then the ordered pair (P, ≤) is
called a partially ordered set or poset.
Definition 7.3. Let (P, ≤) be a partially ordered set. If for every x, y ∈ P we
have either x ≤ y ∨ y ≤ x, then ≤ is called a simple ordering or linear ordering
on P , and (P, ≤) is called a totally ordered or simply ordered set or chain.

Remark:

1. It is necessary to have x ≤ y and y ≤ x for every x and y in a Poset.

2. If x and y are not related then x and y are called incomparable.
3. For every x, y ∈ P , x < y ⇐⇒ x ≤ y ∧ x 6= y.
4. For every x, y ∈ P , x > y ⇐⇒ x ≥ y ∧ x 6= y.
Definition 7.4. Let R be a partial ordering ≤ on P , then R̄ be a dual relation ≥
on partial ordered set. If (P, ≤) be a partially ordered set (POSET) then (P, ≥)
is called a dual partially ordered set of (P, ≤).

Illustrations:

(1) Let R be the relation ”less than or equal to” or ”greater than or equal to”
on the real set P. Since these relations are reflexive, anti-symmetric and
transitive R is partial ordering on real set,. The (P, ≤) and (P, ≥) are
Posets.
(2) Let A 6= φ and ρ(A) = X be the power set of A, since the relation ⊆
is reflexive, anti-symmetric and transitive R is partial ordering on X,
(X, ⊆) is a poset. But the relation ⊂ is irreflexive, anti-symmetric and
transitive, it is not partial ordering.
 
Let A = a, b, c . Then
 
X = ρ(A) = φ, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, A

(3) For a, b ∈ N the relation ”a divides b” defined as

a|b ⇐⇒ b = ac for c ∈ N

The relation b is called integral multiple of a. These two relations divides

and integral multiple of are partial ordering on set of positive integers N .
 
For example let X = 2, 3, 6, 8 and let ≤ be the relation ”divides” on X.
Then  
≤= (2, 2), (3, 3), (6, 6), (8, 8), (2, 8), (2, 6), (3, 6)

The relation ”integral multiple of”, written as ≥, is given by

 
≥= (2, 2), (3, 3), (6, 6), (8, 8), (8, 2), (6, 2), (6, 3)

17
7.1 Partially ordered set: Representation and Associated Ter-
minology
Definition 7.5. Let (P, ≤) be a poset, an element y ∈ P is said to cover an
element x ∈ P if x < y then there does not exist any element z ∈ P such that
x ≤ z and z ≤ y; that is
 
y covers x ⇐⇒ x ≤ z ∧ (x ≤ z ≤ y ⇒ x = z ∨ z = y) (11)

Definition 7.6. A partially ordering ≤ of a set P can be represented by means

of a diagram known as a Hasse diagram or a partially ordered set diagram of
(P, ≤). In such a diagram, each element is represented by small circle or dot. The
circle for x ∈ P is drawn below the circle y ∈ P if x < y, and a line is drawn
between x and y if y covers x. If x < y but y does not covers x, then x and y are
not directly connected by a single line, but are connected by more than one line.
 
Problem 7.7. Let P = 1, 2, 3, 4 and ≤ be the relation ”less than or equal to”
then draw the Hasse diagram of (P, ≤).
 
Problem 7.8. Let P = φ, {a}, {b}, {a, b}4 and ≤ be the relation ”inclusion
(⊆)” then draw the Hasse diagram of (P, ⊆).

Solution 7.9. The corresponding Hasse diagram of above two problems is given
as follows.

Figure 9: Hasse diagram of poset (P, ≤).

 
Problem 7.10. Let X = 2, 3, 6, 12, 24, 36 and the relation ≤ be such that
x ≤ y if x divides y. Draw the Hasse diagram of (X, ≤).

Solution 7.11. The Hasse diagram is given as follows.

18
 Figure 10: Hasse diagram of (X, ≤) of relation R.

Problem 7.12. Let A be a given finite set and ρ(A) its power set. Let ⊆ be the
inclusion relation on the elements of ρ(A). Draw Hasse diagram of (ρ(A), ⊆) for

(a) A = {a} (c) A = {a, b, c}

(b) A = {a, b} (d) A = {a, b, c, d}

Solution 7.13. The Hasse diagram is given as follows.

v
v

Figure 11: Hasse diagram of (X, ≤) of relation R.

v v
v v

Figure 12: Hasse diagram of (X, ≤) of relation R.

19
Problem 7.14. Let A be the set of factors of a particular integer m and ≤ be the
relation divides, that is
  

≤= (x, y)x ∈ A ∧ y ∈ A ∧ (x divides y)


Draw the Hasse diagram for

(a) m = 2 (c) m = 30 (e) m = 12

(b) m = 6 (d) m = 210 (f) m = 45

Solution 7.15. The Hasse diagram is given as follows.

v
v

v v
v v

Figure 13: Hasse diagram of (X, ≤) for m = 2, 6, 30, 12, 45, 210.

20
Definition 7.16. Let (P, ≤) be a poset.

(1) If there exists an element y ∈ P such that y ≤ x for all x ∈ P , then y is

called the least member in P relative to partial ordering ≤.
(2) Similarly, if there exists an element y ∈ P such that x ≤ y for all x ∈ P ,
then y is called the greatest member in P relative to ≤.

Illustrations:

(a) The least element for the problem-7.11 is 1 and φ.

(b) The greatest element for the poblem-7.11 is 4 and {a, b}.
Definition 7.17. Let (P, ≤) be a poset.

(1) An element y ∈ P is called minimal member of P relative to a partial

ordering ≤ if for no x ∈ P is x < y.
(2) Similarly, An element y ∈ P is called maximal member of P relative to a
partial ordering ≤ if for no x ∈ P is y < x.

Illustrations:

(a) A minimal member / maximal member need not be unique.

(b) Distinct minimal members / maximal members are incomparable.
Definition 7.18. Let (P, ≤) be partially ordered set and A ⊆ P . Then

(1) An element x ∈ P is an upper bound for A if for all a ∈ A, a ≤ x.

(2) Similarly, an element x ∈ P is a lower bound for A if for all a ∈ A, x ≤ a.

Illustrations:

(a) A minimal member / maximal member need not be unique.

(b) Distinct minimal members / maximal members are incomparable.
Definition 7.19. Let (P, ≤) be partially ordered set and A ⊆ P . Then

(1) An element x ∈ P is a least upper bound or supremum, for A and x ≤ y

where y is an upper bound of for A.
(2) Similarly, the greatest lower bound or infimum, for A is an element x ∈ P
such that x is a lower bound and y ≤ x for all lower bounds y.

Illustrations:

(a) A minimal member / maximal member need not be unique.

(b) Distinct minimal members / maximal members are incomparable.
Definition 7.20. A partially ordered set is called well-ordered if every non-empty
subset of it has a least member.

21
 Solve the followoing problems.

Ex-1 What are the ranges of the relations

     

2 

S = (x, x )x ∈ N T = (x, 2x)x ∈ N


Where N = {0, 1, 2, . . .}? Find R ∪ S and R ∩ S.

Ex-2 Let L denotes the relation ”Less than or equal to (≤)” and D denotes the
relation ”divides” where xDy means ”x divides y”. Both L and D are
defined on the set {1, 2, 3, 6}. Write L and D as sets and find L ∩ D.

Ex-3 Give an example of relation which is neither reflexive nor irreflexive.

Ex-4 Give an example of a relation which is both symmetric and anti-symmetric.

Ex-5 If R and S are both reflexive, then show that R ∪ S and R ∩ S are also
reflexive.

Ex-6 Show that the following relations are transitive:

  
R1 = (1, 1) , R2 = (1, 2), (2, 2) , R3 = (1, 2), (2, 3), (1, 3), (2, 1)

Ex-7 Given S = 1, 2, 3, 4 and a relation R on S defined by

R = (1, 2), (4, 3), (2, 2), (2, 1), (3, 1)

Show that R is transitive. Find a relation R1 ⊇ R such that R1 is transitive.

Can you find another relation R2 ⊇ R which is also transitive?

Ex-9 Given S = 1, 2, . . . , 10 and a relation R on S where
 
R = (x, y)x + y = 10

What are the properties of R?

Ex-10 Let R denote a relation on the set of ordered pairs of positive integers such
that (x, y)R(u, v) iff xv = yu. Show that R is an equivalence relation.

Ex-11 S
 = 1, 2, 3, 4, 5 find the equivalence relation S which generates partition
,
{1, 2}, {3}, {4, 5} . Draw the graph of the relation.

Ex-12 Prove that the relation ”congruence modulo m” is given by,

 
≡= (x, y)(x − y) is divisible by m

over the set of positive integers is an equivalence relation. Show that x1 ≡

y1 and x2 ≡ y2 , then (x1 + y1 ) ≡ (x2 + y2 ).

Ex-13 Given a covering of the set S = A1 , A2 , . . . , An , show that we can write
a compatibility relation which defines this covering.

Ex-14 Let the compatibility relation on a set x1 , x2 , x3 , x4 , x5 , x6 be given by
the matrix. Draw the graph and find the maximal compatibility block of the
relation.

22
 
Ex-15 Given the relation matrix MR of a relation R on the set a, b, c , find the
relation R̄, R2 = R ◦ R, R3 = R ◦ R ◦ R and R ◦ R̄.
 
1 0 1
MR = 1 1 0
1 1 1

Ex-16 Two equivalence relations R and S are given by their relation matrices MR
and MS . Show that R ◦ S is not an equivalence relation.
   
1 1 0 1 1 0
MR = 1 1 0 MS = 1 1 1
0 0 1 0 1 1

Obtain equivalence relations R1 and R2 on 1, 2, 3 such that R1 ◦ R2 is
also an equivalence relation.

Ex-17 Draw the Hasse diagrams of the following sets under the partial ordering
relation ”divides” and indicate those which are totally ordered.
   
2, 6, 24 , 3, 5, 15 , 2, 4, 8, 16 , 3, 9, 27, 54

Ex-18 If R is a partial ordering relation on a set X and A ⊆ X, show that R ∪

(A × A) is a partial ordering relation on A.

Ex-19 Hasse diagram of the poset (P, R), where P = x1 , x2 , x3 , x4 , x5 is given
below, then answer the following.

Figure 14: Hasse diagram of (X, ≤) of relation R.

(a) Find the least and greatest members in P if they exist.

(b) Find the maximal and minimal elements of P .
  
(c) Find the upper and lower bound of x2 , x3 , x4 , x3 , x4 , x5 and x1 , x2 , x3 .
Also indicate the LUB and GLB of these subset if they exist.

23
8 Lattices

8.1 Definition and Examples

Definition 8.1. A lattice is partially ordered set (L, ≤) in which every pair of
elements a, b ∈ L has greatest lower bound and a least upper bound.

Definition 8.2. Following are the two important definitions related with lattices.

(a) The greatest lower bound of a subset a, b ⊆ L is denoted by a ? b and is
defined as, 
a ? b = GLB a, b (12)

(b) The least upper bound of a subset a, b ⊆ L is denoted by a ? b and is
defined as, 
a ⊕ b = LU B a, b (13)

Remark:

1. Other symbols ∧ and ∨ or · and + are used to denote the meet and join of
two elements respectively.

2. In certain cases, the symbols ∩ and ∪ are used to denote the meet and join
of two elements respectively.

3. Totally ordered set is trivially a lattice, but not all partially ordered sets are
lattices.

Illustrations:

(a) Let S be non-empty set and ρ(S) be its power set. The partially ordered set
(ρ(S), ⊆) is a lattice in which the meet and join are defined as

A ? B = A ∩ B = GLB A, B (14)

A ⊕ B = A ∪ B = LU B A, B (15)

(b) Let I+ be the set of all positive integers and D denote the relation of ”di-
vision” in such that for any two a, b ∈ I+ , aDb ⇐⇒ a divides b. Then
(I+ , D) is a lattice in which two operations meet and join are defined as,
 
a ? b = GLB a, b = GCD a, b (16)
 
a ⊕ b = LU B a, b = LCM a, b (17)

(c) Let n be the positive

integer
 and Sn be the set of all divisors of n;. Let
S6 = 1, 2, 3, 6 , S24 = 1, 2, 3, 4, 6, 8, 12, 24 and let D be the relation of
”division” and hence (S6 , D), (S8 , D), (S24 , D) and (S30 , D) are all lattices.

(d) Let S be any non-empty set and q(S) be the set of all partitions of S. Two
binary operations ? and ⊕ are defined as product and sum of partitions.
The partial ordering relation ≤ on q(S) such that for q1 , q2 ∈ q(S), q1 ≤

24
 q2 ⇐⇒ every block of q1 is a subsetof some block in q2 . Then (q(S), ≤
) is a lattice. In particular let q(S) = q1 , q2 , q3 , q4 , q5
 
q1 = {a, b, c} , q2 = {a, b}, {c} , q3
  
= {a, c}, {b} , q4 a, {b, c} , q5 = {a}, {b}, {c}

Definition 8.3. The operations ? and ⊕ are called duals of each other as
are the relations ≤ and ≥. Similarly, the lattices (L, ≤) and (L, ≥) are
called duals of each other.

8.2 Some properties of Lattices

Let (L, ≤) is a lattice. Define two binary two operations ? and ⊕ are defined on
(L, ≤). For any a, b, c ∈ L

(L-1) a ? a = a (L-1)’ a ⊕ a = a (Idempotent)

(L-2) a ? b = b ? a (L-2)’ a ⊕ b = b ⊕ a (Commutative)

(L-3)’ (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c) (Asso-
(L-3) (a ? b) ? c = a ? (b ? c) ciative)

(L-4) a ? (a ⊕ b) = a (L-4)’ a ⊕ (a ? b) = a (Absorption)

Theorem 8.4. Let (L, ≤) be a lattice in which ? and ⊕ denote the operations of
meet and join respectively. For a, b ∈ L,

a ≤ b ⇐⇒ a ? b = a ⇐⇒ a ⊕ b = b (18)

Theorem 8.5. Let (L, ≤) be a lattice. For a, b, c ∈ L, the following properties

called isotonicity hold.
(
a?b≤a?c
b≤c⇒ (19)
a⊕b≤a⊕c

Theorem 8.6. Let (L, ≤) be a lattice. For a, b, c ∈ L, the following properties

called distributive inequalities hold.

a ⊕ (b ? c) ≤ (a ⊕ b) ? (a ⊕ c) (20)
a ? (b ⊕ c) ≤ (a ? b) ⊕ (a ? c) (21)

Theorem 8.7. Let (L, ≤) be a lattice. For a, b, c ∈ L, the following property hold.

a ≤ c ⇐⇒ a ⊕ (b ? c) ≤ (a ⊕ b) ? c (22)

8.3 Lattices as an algebraic systems

Definition 8.8. A lattice is an algebraic system (L, ?, ⊕) with two binary op-
erations ? and ⊕ on L which are both commutative, associative and satisfy the
absorption laws.

25
8.4 Sub-lattice, Direct product and Homomorphism
Let (L, ?, ⊕) be a lattice and S ⊆ L be a subset of L. The algebra (S, ?, ⊕) is a
sub-lattice of (L, ?, ⊕) iff S is closed under both operations ? and ⊕.

Illustrations:
(a) The lattices (Sn , D) is a sub-lattice of a lattice (I+ , D). Where ”D” is a
relation divides.

(b) Let S be any set and ρ(S) be its power set and (ρ(S), ⊆) is a lattice. Then
(R(S), ⊆) is a sub-lattice. Where R(S) is called ring of subsets of S.

Definition 8.9. Let (L, ?, ⊕) and (S, ∧, ∨) be two lattices. The algebraic system
(L × S, ·, +) in which two binary operations + and · on L × S are such that for
any (a1 , b1 ) and (a2 , b2 ) in L × S

(a1 , b1 ) · (a2 , b2 ) = (a1 ? a2 , b1 ∧ b2 ) (23)

(a1 , b1 ) + (a2 , b2 ) = (a1 ⊕ a2 , b1 ∨ b2 ) (24)

is called the direct product of (L, ?, ⊕) and (S, ∧, ∨).

Illustrations:

(a) Let (L, ≤) be a lattice, where L = 0, 1 , then (L2 , ≤) and (L3 , ≤) be
lattice.

Definition 8.10. Let (L, ?, ⊕) and (S, ∧, ∨) be two lattices. A mapping g : L → S

is called lattice homomorphism from the lattice (L, ?, ⊕) to (S, ∧, ∨) if for any
a, b ∈ L,

g(a ? b) = g(a) ∧ g(b) and g(a ⊕ b) = g(a) ∨ g(b) (25)

Definition 8.11. If a homomorphism g : L → S of two lattices (L, ?, ⊕) and

(S, ∧, ∨) is bijective, i.e,one-to-one, onto then g is called an isomorphism.

Definition 8.12. If a homomorphism g : L → L, where (L, ?, ⊕) is a lattice is

called an endomorphism. If g : L → L is an isomorphism then g is called an
automorphism.
0
Definition 8.13. Let (P, ≤) and (Q, ≤ ) be two partially ordered sets. A mapping
0
f : P → Q is said to be order-preserving relative to the ordering ≤ in P and ≤
0
in Q iff for any a, b ∈ P such that a ≤ b, f (a) ≤ f (b) in Q.
0
If (P, ≤) and (Q, ≤ ) are lattices and g : P → Q is a lattice homomorphism, then
g is order-preserving.
0
Definition 8.14. Two partially ordered sets (P, ≤) and (Q, ≤ ) are called order-
isomorphic if there exists a mapping f : P → Q which is bijective and if both f
and f −1 are order-preserving.

26
8.5 Some special Lattices
Definition
 8.15. Let (L, ?, ⊕) be a lattice and S ⊆ L be a finite subset of L where
S = a1 , a2 , . . . , an . The greatest lower bound and the least upper bound on S
can be expressed as

GLB(S) = ?ni=1 ai and LU B(S) = ⊕ni=1 ai (26)

Where
?ni=1 = a1 ? a2 ? . . . , ?an and ⊕ni=1 = a1 ⊕ a2 ⊕ . . . , ⊕an (27)

Definition 8.16. A lattice is called complete if each of its non-empty subsets has
a least upper bound and a greatest lower bound.

Remark:

1. Every finite lattice must be complete.

2. A lattice which has elements 0 and 1 is called a bounded lattice.


3. For a lattice (L, ?, ⊕), where L = a1 , a2 , . . . , an

?ni=1 ai = 0 and ⊕ni=1 ai = 1

4. The bounds 0 and 1 of a lattice (L, ?, ⊕, 0, 1) satisfy the following identities.

For any a ∈ L

a⊕0=a a?1=a (28)

a⊕1=1 a?0=0 (29)

Definition 8.17. In a bounded lattice (L, ?, ⊕, 0, 1), an element b ∈ L is called a

complement of an element a ∈ L if

a ? b = 0 and a ⊕ b = 1 (30)

Remark:

1. From the identities, 0 ? 1 = 0 and 0 ⊕ 1 = 1.

2. If c 6= 1 is a complement of 0 and c ∈ L; then 0 ? c = 0 and 0 ⊕ c = 1.

Definition 8.18. A lattice (L, ?, ⊕, 0, 1) is said to be a complemented lattice if

every element of L has at least one complement.

Illustrations:

(a) The lattice (Ln , ≤n ) be the complemented lattice. For a lattice (L3 , ≤) the
bounds are given by, (0, 0, 0) and (1, 1, 1) and the complement of an element
(1, 0, 1) is (0, 1, 0).

(b) The lattice (ρ(S), ⊆) is a complemented lattice with bounds φ and A re-
spectively.

27
Definition 8.19. A lattice (L, ?, ⊕) is called a distributive lattice if for any a, b, c ∈
L,

a ? (b ⊕ c) = (a ? b) ⊕ (a ? c) (31)
a ⊕ (b ? c) = (a ⊕ b) ? (a ⊕ c) (32)

Theorem 8.20. Every chain is a distributive lattice.

Theorem 8.21. Direct product of two distributive lattices is a distributive lattice.

Theorem 8.22. Let (L, ?, ⊕) be a distributive lattice. For a, b, c ∈ L

(a ? b = a ? c) ∧ (a ⊕ b = a ⊕ c) ⇒ b = c (33)

Definition 8.23. A lattice is modular if

a ≤ c ⇒ a ⊕ (b ? c) = (a ⊕ b) ? c (34)

8.6 Boolean Algebra

Definition 8.24. A Boolean algebra is a complemented distributive lattice.

A Boolean algebra (B, ?, ⊕,0 , 0, 1) satisfies the following properties in which

a, b, c ∈ B.

(1) (B, ?, ⊕) is a lattice in which ? and ⊕ satisfy the following identities.

(L-1) a ? a = a (L-1)’ a ⊕ a = a
(L-2) a ? b = b ? a (L-2)’ a ⊕ b = b ⊕ a
(L-3) (a ? b) ? c = a ? (b ? c) (L-3)’ (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)
(L-4) a ? (a ⊕ b) = a (L-4)’ a ⊕ (a ? b) = a

(2) (B, ?, ⊕) is a distributive lattice and satisfy these identities.

D-1 a ? (b ⊕ c) = (a ? b) ⊕ (a ? c)
D-2 a ⊕ (b ? c) = (a ⊕ b) ? (a ⊕ c)
D-3 (a ? b) ⊕ (b ? c) ⊕ (c ? a) = (a ⊕ b) ? (b ⊕ c) ? (c ⊕ a)
D-4 (a ? b = a ? c) ∧ (a ⊕ b = a ⊕ c) ⇒ b = c

(3) (B, ?, ⊕, 0, 1) is a bounded lattice in which for any a ∈ B, the following

holds.

B-1 0 ≤ a ≤ 1
0
B-2 a ? 0 = 0 (B − 2) a ⊕ 1 = 1
0
B-3 a ? 1 = a (B − 3) a ⊕ 0 = a

(4) (B, ?, ⊕,0 , 0, 1) is uniquely complemented lattice in which the complement

0
of any element a ∈ B is denoted by a ∈ B and satisfy the following
identities.

28
 0 0
(C-1) a ? a = 0 (C-1)’ 1 = 0
0 0
(C-2) 0 = 1 (C-2)’ 1 = 0
0 0 0 0 0 0
(C-3) (a ? b) = a ⊕ b (C-3)’ (a ⊕ b) = a ? b

(5) There exists a partial ordering relation ≤ on B such that

(P − 1)0 a ⊕ b = LU B a, b
 
(P-1) a ? b = GLB a, b
(P-2) a ≤ b ⇐⇒ a ? b = a ⇐⇒ a ⊕ b = b
0 0 0 0
(P-3) a ≤ b ⇐⇒ a ? b = 0 ⇐⇒ b ≤ a ⇐⇒ a ⊕ b = 1

Illustrations:

(a) 
The algebra
(B, ?, ⊕,0 , 0, 1) is two-element Boolean-algebra. Where B =
0, 1 .

(b) The algebra (ρ(S), ∩, ∪,0 , φ, S) is a Boolean algebra.

8.7 Sub-algebra, Direct product and Homomorphism

Definition 8.25. Let (B, ?, ⊕,0 , 0, 1) be a Boolean algebra and S ⊆ B, if S con-
tains the elements 0 and 1 and is closed under the operations ?, ⊕ and 0 is called
sub-Boolean algebra.

29
 Solve the following problems.

Ex-1 Draw the the diagrams of lattices (Sn , D) for n = 4, 6, 10, 12, 15, 45, 60, 75, 210.
For what values of n do you expect (Sn , D) to be a chain?

Ex-2 Let S = a, b, c . Draw the diagram of (ρ(S), ⊆).

Ex-3 Let R be the set of real numbers in [0, 1] and ≤ be the usual operation of
”less than or equal to” on R. Show that (R, ≤) is a lattice. What are the
operations of meet and join on this lattice?

Ex-4 Let S0 , S1 , S − 2, S3 , S4 , S5 , S6 , S7 be given by,

   
S0 = a, b, c, d, e, f , S1 = a, b, c, d, e , S2 = a, b, c, e, f , S3 = a, b, c, e
   
S4 = a, b, c , S5 = a, b , S6 = a, c , S7 = a

Draw the diagram of (L, ⊆) where L = S = S0 , S1 , S2 , S3 , S4 , S5 , S6 , S7 .

Ex-5 Let (L, ≤) be a lattice in which ? and ⊕ denote the operations of meet and
join respectively. For a, b ∈ L,

a ≤ b ⇐⇒ a ? b = a ⇐⇒ a ⊕ b = b

Ex-6 Show that in a lattice a ≤ b ≤ c, then

a⊕b=b?c
(a ? b) ⊕ (b ? c) = b = (a ⊕ b) ? (a⊕)

Ex-7 Show that in a lattice if a ≤ b and c ≤ d, then a ? c ≤ b ? d.

Ex-8 In a lattice show that

(a ? b) ⊕ (c ? d) ≤ (a ⊕ c) ? (b ⊕ d)
(a ? b) ⊕ (b ? c) ⊕ (c ? a) ≤ (a ⊕ b) ? (b ⊕ c) ? (c ⊕ a)

Ex-9 Show that a lattice with three or fewer elements is a chain.

Ex-10 Find all the sub-lattices of the lattice (Sn , D) for n = 12.

Ex-11 Show the diagram of a lattice which is the direct product of five-element
lattice and a two element chain.

Ex-12 Show that the lattice (Sn , D) for n = 216 isomorphic to the direct product
of lattices for n = 8 and n = 27.

Ex-13 Find the complements of every element of the lattice (Sn , D) for n = 75.

Ex-14 Show that in a lattice with two or more elements, no element is its own
complement.

Ex-15 Show that a chain or three or more elements is not complemented.

Ex-16 Which of the two lattices (Sn , D) for n = 30 and n = 45 are complemented
? Are these lattices distributive ?

30
Ex-17 Show that D’ Morgan’s laws, given by,
0 0 0 0 0 0
(a ? b) = a ⊕ b and (a ⊕ b) = a ? b

Ex-18 Show that in a complemented, distributive lattice

0 0 0 0
a ≤ b ⇐⇒ a ? b = 0 ⇐⇒ a ⊕ b = 1 ⇐⇒ b ≤ a

Ex-19 Show that a lattice is distributive iff

(a ? b) ⊕ (b ? c) ⊕ (c ? b)⊕ = (a ⊕ b) ? (b ⊕ c) ? (c ⊕ a)

Ex-20 Show that in a distributive lattice, the distributive laws can be generalized
as
a ? (⊕ni=1 bi ) = ⊕ni=1 (a ? bi ) and a ⊕ (?ni=1 bi ) = ?ni=1 (a ⊕ bi )

Ex-21 Show that in a bounded distributive lattice, the elements which have com-
plements forms a sub-lattice.
Ex-22 A lattice is modular if
a ≤ c ⇒ a ⊕ (b ? c) = (a ⊕ b) ? c
Show that every distributive lattice is modular, but not conversely.
Ex-23 Prove the following Boolean identities.
0
(a) a ⊕ (a ? b) = (a ⊕ b)
0
(b) a ? (a ⊕ b) = (a ? b)
0
(c) (a ? b) ⊕ (a ? b ) = a
(d) (a ? b ? c) ⊕ (a ? b) = (a ? b)
Ex-24 In a Boolean algebra, show that
0 0
(a) a = b ⇐⇒ ab + a b = 0
0 0
(b) a = 0 ⇐⇒ ab + a b = b
0 0 0 0 0 0
(c) (a + b )(b + c )(c + a ) = (a + b)(b + c)(c + a)
(d) a ≤ b ⇒ a + bc = b(a + c)
Ex-25 Simply the boolean expression
0 0
(a) (a ? b) ⊕ (a ⊕ b)
0 0 0 0 0
(b) (a ? b ? c) ⊕ (a ? b ? c) ⊕ (a ? b ? c )
 0 
(c) (a ? c) ⊕ c ⊕ (b ⊕ b ) ? e
0
(d) (1 ? a) ⊕ (0 ? a )
Ex-26 Let (B, ?, ⊕,0 , 0, 1) be a Boolean algebra. Define the operations + and · on
the elements of B by
0 0
a + b = (a ? b ) ⊕ (a ? b)
a·b=a?b
Show that (B, +, ·, 1) is a Boolean ring with identity 1.

31
Ex-27 For the operation + defined problem-26 show that

(a) (a + b) + b = ab
(b) a · (b + c) = (a · b) + (a · a) = 0
(c) (a + 0) = a
0
(d) (a + 1) = a

Ex-28

Ex-29

Ex-30

References
[1] Engineering Mathematics Vol.-I and II. A.P Verma and M. N. Mehta. Stu-
dent manual SVNIT, Surat.

[2] Erwin Kreyszig: Advanced Engineering Mathematics, 8th edition, John

Wiley and Sons, (2008).

[3] George B. Thomas, Jr. Ross L. Finley: Calculus with analytical Geometry,
9th edition Addison-Wesley Publishing Company. (2004)

[4] Howard Anton: Calculus, A new horizon, 6th edition, John Willey and
Sons, (2006)

[5] Michael D. Greenberg. Advanced Engineering Mathematics. Prentice-Hall

International, Inc. NJ.

Acknowledgment
I am very much thankful to Prof. P. A. Gajjar, Head of the department, Nottingham
university, Kazakhstan for his valuable guidance for the preparation of this topic.

32