Indian Institute of Information Technology

Design and Manufacturing, Kancheepuram

Chennai 600 127, India Instructor
An Autonomous Institute under MHRD, Govt of India N.Sadagopan
An Institute of National Importance Scribe: P.Renjith
www.iiitdm.ac.in
COM205T Discrete Structures for Computing-Lecture Notes

Relations
Objective: In this module, we shall introduce sets, their properties, and relationships among
their elements. We shall also look at in detail the properties of relations. Further we also count
sets that satisfy specific properties.

Basic Definitions

A set (universe of discourse) is a well defined collection of distinct objects.

Cross Product
Let A and B be two sets. The cross product A × B is a set, defined as A × B = {(a, b) | a ∈
A, b ∈ B}.
In general, given the sets A1 , A2 , . . . , An , we can define A1 ×A2 ×. . .×An = {(x1 , x2 , . . . , xn ) | xi ∈
Ai , 1 ≤ i ≤ n}.
Note that if |A| = n, then |A × A| = n2 , and |A1 × A2 × . . . × An | = m1 · m2 · · · mn where
|Ai | = mi , 1 ≤ i ≤ n.
Note: Empty set φ is not well defined. If B = φ, then A × B = φ, is also not well defined. Hence,
the only relation possible is empty relation.

Relation

Let A and B be two sets. A binary relation R from A to B is a set, defined as R ⊆ A × B. For
a set A and the cross product A × A, a binary relation R defined on A is such that R ⊆ A × A.
A ternary relation R on A is such that R ⊆ A × A × A. In general, an n-ary relation R on A is
such that R ⊆ A × A × . . . × A (n times). Interestingly, unary relation exists and it is a subset
of A. That is, an unary relation R on A is such that R ⊆ A. Note that any binary relation is a
subset of A × A and a ternary relation is a subset of A × A × A.

Example 1.
Let A = {1, 2, 3}. R0 is an example unary relation. R1 to R4 are binary relations defined on A.
R0 = {2, 3}
R1 = {(1, 1), (2, 2), (3, 3)} R2 = {(1, 1), (2, 1), (3, 2)}
R3 = φ R4 = A × A
Example 2.
S = {dm,dsa,alg,oop,c++,java}.
R5 = {(x, y) | x, y ∈ S and x is a prerequisite for y}.
R5 = {(dsa,alg), (dm,alg), (dm,oop), (oop,c++)}.
Example 3. Let I = {i1 , i2 , . . . , im } be the items in a supermarket. A ternary relation R3 on I is
defined as R3 = {(i1 , i4 , i3 ), (i2 , i1 , i7 ), (i7 , i8 , i9 )}, R3 ⊆ I × I × I.

Remark: Familiar examples for relations are tables in databases or a spreadsheet (excel sheet).
A row (or the entire spreadsheet) corresponds to an element in the underlying cross product
of items (columns) and each row is a relation R by defintion and each row is an element in R.
Further, each row is a transaction.

Claim Consider a set A with |A| = n. The size of the powerset (the set of all subsets) is
2n .
Proof 1: By definition, the set of all subsets of A include subsets of size ’0’, ’1’, ’2’, and so on.
The number of subsets of size i is ni . Therefore, the total number of subsets is i=n n

P

i=0 i =
n n n n




0 + 1 + . . . + n , which is precisely 2 .

Proof 2: Consider a subset B, observe that each element of A is either present or not in
B. Thus, to get all subsets, there are two possibilities (present or not) for each element in A.
Therefore, 2n subsets.

Proof 3: Note that there are 2n possible binary strings of length n. Further, the binary string
’1101’ corresponds to the set {4, 3, 1}, i.e., the presence of ’1’ indicates the presence of the cor-
responding element in the subset and ’0’ otherwise. This shows that there is one-one mapping
between the set of binary strings and the set of all subsets. Thus, there are 2n subsets.

Proof 4: Proof by mathematical induction on n. n = 0. For an empty set, the powerset is

also an empty set and the cardinality of powerset is one. Therefore, 20 = 1 is true. Assume
a set of size n has 2n subsets. Consider a set {a1 , . . . , an , an+1 } of size (n + 1). By induction
hypothesis the set {a1 , . . . , an } has 2n subsets and all of which will remain subsets for the set
{a1 , . . . , an , an+1 }. In addition, we obtain new subsets by augmenting the element an+1 to each
subset of {a1 , . . . , an }. Thus, there are 2n subsets not containing an+1 and 2n subsets containing
an+1 . Overall, 2n+1 subsets and therefore, the claim follows.

Claim. Consider a set A with |A| = n. The maximum number of binary relations on A is
2
2n .

Proof. Let A × A = {x1 , x2 , . . . , xn2 }. A relation is a subset of A × A. The number of subsets of

2
a set of size n2 is 2n . Thus, the claim follows. t
u

A Unary relation R on A is R ⊆ A. The maximum number of unary relations is 2n .

Properties of Relations

Consider a binary relation R ⊆ A × A, we define the following on R

(1) R is reflexive iff ∀a ∈ A, ((a, a) ∈ R)
(2) R is symmetric iff ∀a, b ∈ A, ((a, b) ∈ R → (b, a) ∈ R)
(3) R is transitive iff ∀a, b, c ∈ A, ((a, b) ∈ R and (b, c) ∈ R → (a, c) ∈ R)
(4) R is asymmetric iff ∀a, b ∈ A, ((a, b) ∈ R → (b, a) ∈ / R)

2
(5) R is antisymmetric iff ∀a, b ∈ A, [((a, b) ∈ R ∧ (b, a) ∈ R) → a = b]
(6) R is irreflexive iff ∀a ∈ A, ((a, a) ∈
/ R)

Let us understand the definition of reflexivity in detail. Consider a set A and a binary rela-
tion R ⊆ A × A, R is said to be a reflexive relation if for each a ∈ A, (a, a) ∈ R and if there
exists a ∈ A, (a, a) ∈
/ R, then R is not reflexive. That is,

R is reflexive if and only if ∀a(a, a) ∈ R.

Note that the definition says, [∀a ∈ A, (a, a) ∈ R] → R is reflexive and [∃a ∈ A, (a, a) ∈ / R] → R
is not reflexive. The first part of the definition is ’if part’ of ’iff’ and the contrapositive of second
part of the definition is ’only if’ of ’iff’.

Further, the definition of symmetricity says, if (a, b) ∈ R, then (b, a) ∈ R. Since, this is condi-
tional, the empty relation is symmetric. That is, a relation not containing both (a, b) and (b, a).
Similarly, for transitivity, if a relation contains just (a, b) ∈ R but not (b, c), then R is transitive.
Also, reflexivity and irreflexivity is defined with respect to the elements of the set A and all
other properties are defined with respect to elements of R ⊆ A × A.

Example 4. Let A = {1, 2, 3}. Identify which of the following relations defined on A are re-
flexive, symmetric and transitive.

R1 = {(1, 1), (2, 2), (3, 3)} R2 = {(1, 1), (1, 2), (1, 3)}
R3 = φ R4 = A × A
R5 = {(2, 2), (3, 3), (1, 2)} R6 = {(2, 3), (1, 2)}

Property R1 R2 R3 R4 R5 R6
Reflexive X X X X X X
Symmetric X X X X X X
Transitive X X X X X X
1. R2 is not reflexive as (2, 2), (3, 3) ∈
/ R2 .
2. R6 is not symmetric as (3, 2), (2, 1) ∈ / R6 .
3. R6 is not transitive as (1, 2), (2, 3) ∈ R6 but (1, 3) ∈
/ R6 .

Example 5. A = {1, 2, 3, 4}. Identify the properties of relations.

R1 = {(1, 1), (2, 2), (3, 3), (2, 1), (4, 3), (4, 1), (3, 2)}
R2 = A × A, R3 = φ, R4 = {(1, 1), (2, 2), (3, 3), (4, 4)}
R5 = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 1), (4, 3), (3, 4)}

Relation Reflexive Symmetric Asymmetric Antisymmetric Irreflexive Transitive

R1 × × × X × ×
R2 X X × × × X
R3 × X X X X X
R4 X X × X × X
R5 X X × × × X

3
Example 6. Let R = {(a, b) | a, b ∈ N and a ≤ b}.
Since for all a in natural number set, a ≤ a, (a, a) ∈ R. Therefore, R is reflexive. R is not
symmetric as 1 ≤ 2 but not 2 ≤ 1. If a ≤ b and b ≤ c, then it follows that a ≤ c. Therefore, R
is transitive. Since R is reflexive, R is not asymmetric. Since R does not contain both (a, b) and
(b, a), a 6= b, R is antisymmetric. Since R is reflexive, R is not irreflexive.

Example 7. R7 = {(a, b) | a, b ∈ I and a divides b}.

Proof. Since 0 does not divide 0, (0, 0) ∈/ R7 . R7 is not reflexive. For all a, b, c ∈ I, if (a, b) ∈ R
and (b, c) ∈ R, then we prove that (a, c) ∈ R. Let ab = c1 ≥ 1 and cb = c2 ≥ 1. This implies
b = c1 · a and c = c2 · b. Therefore, c = c2 · c1 · a = c3 · a where c3 = c2 · c1 . Thus, ac = c3 ≥ 1
and a divides c, (a, c) ∈ R7 . Note: R7 is not symmetric as (1, 3) ∈ R and (3, 1) ∈ / R. Also, it is
antisymmetric, and it is not asymmetric and irreflexive t
u
Example 8. R = {(a, b) | a, b ∈ R and a divides b}.

Note (0, 0) ∈
/ R, (0.25, 0.75) ∈ R, (1, 4) ∈ R. R is not reflexive. Also, (1, x) ∈ R, for any
real number x but (x, 1) ∈
/ R for some x. Therefore, R is not symmetric. Using the argument
given in Example 7, we can establish that R is transitive. Also, it is antisymmetric, and it is not
asymmetric and irreflexive.

Remarks:
1. R is not reflexive does not imply R is irreflexive. Counter example: A = {1, 2, 3}, R = {(1, 1)}.

2. R is asymmetric implies that R is irreflexive. By definition, for all a, b ∈ A, (a, b) ∈ R and

(b, a) ∈
/ R. This implies that for all (a, b) ∈ R, a 6= b. Thus, for all a ∈ A, (a, a) ∈
/ R. Therefore,
R is irreflexive.

3. R is not symmetric does not imply R is antisymmetric. Counter example: A = {1, 2, 3}, R =
{(1, 2), (2, 3), (3, 2)}.

4. R is not symmetric does not imply R is asymmetric. Counter example: A = {1, 2, 3}, R =
{(1, 2), (2, 2)}.

5. R is not antisymmetric does not imply R is symmetric. Counter example: A = {1, 2, 3}, R =
{(1, 2), (2, 3), (3, 2)}.

6. R is reflexive implies that R is not asymmetric. By definition, for all a ∈ A, (a, a) ∈ R.

This implies that, both (a, b) and (b, a) are in R when a = b. Thus, R is not asymmetric.

7. R is asymmetric and antisymmetric implies that R is transitive. Counter example: A =

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

Counting Special Relations

We shall now count relations satisfying specific properties such as reflexivity, symmetricity, etc.
Let A = {a1 , a2 , . . . , an } and we represent A × A as a matrix such that ith row j th column
represents (ai , aj ), 1 ≤ i, j ≤ n. Observe that the matrix has n2 elements.

4
Claim: The number of reflexive binary relations possible on A is 2n(n−1) .

Proof: By definition of reflexivity, observe that the diagonal elements of the matrix must be
present in any reflexive binary relation. Therefore, the diagonal elements along with any subset
from the remaining n2 − n elements is still a reflexive relation. So, the number of such sets is
2n(n−1) . Therefore, the number of reflexive binary relations is 2n(n−1) .

Claim: The number of symmetric binary relations possible on A is 2(n(n+1))/2 .

Proof: Consider the elements other than the diagonal elements (off diagonal), we divide them
into lower triangle elements (i > j) and upper triangle elements (i < j). Notice that in any sym-
metric relation, if there exists an element, say (ai , aj ) from the lower triangle, then the element
(aj , ai ) from the upper triangle is also in the relation (this element is forced into the relation).
Thus, if a subset from lower triangle element set is chosen, then its counter part from the upper
triangle element set is also chosen ((a, b) is a counter part of (b, a), and vice versa). There are
2
n2 − n such pairs of elements in lower triangle set and the number of subsets is 2(n −n)/2 . Also, it
is to be noted that any subset of the diagonal elements is symmetric, and together with a subset
from lower triangle (or upper triangle) is also a symmetric relation. Therefore, the number of
2 2
symmetric relations is 2n · 2(n −n)/2 = 2(n +n)/2 .

Approach 2: Consider the matrix A × A, let us find out how many elements in A × A are
candidate elements for a symmetric relation. The candidate set must contain diagonal elements
and either upper triangle or lower triangle elements. From Row 1, there are n elements and they
are {(1, 1), (1, 2), . . . , (1, n)}. From Row 2, it is (n − 1) and the set is {(2, 2), (2, 3), . . . , (2, n)}. In
general, the Row i contributes (n − i + 1) to the candidate set. Thus, the size of the candidate set
is n+n−1+. . .+1 = n(n+1) 2 elements, and any subset of the candidate element set is symmetric.

Approach 3: The candidate set for counting symmetric relations is B = {(a, a) | a ∈ A} ∪

{(a, b) | a 6= b, a, b ∈ A}. The cardinality of B is n + n(n−1)
2 = n(n+1)
2 . Any subset of B along
with its counter part is a symmetric relation, and therefore, the number of symmetric binary
relations possible in A is 2(n(n+1))/2 .
2 −n)/2
Claim: The number of antisymmetric binary relations possible in A is 2n · 3(n .

Proof: Consider an antisymmetric binary relation R and note that, if there exists an element,
say (ai , aj ) from the lower triangle of the matrix, then the element (aj , ai ) from the upper tri-
angle should not be present in R and vice versa. Therefore, there exists three possibilities for
each (ai , aj ) pair. That is, either (ai , aj ) is in the relation, or (aj , ai ) is in the relation, or none of
(ai , aj ), (aj , ai ) is in the relation. There are (n2 − n)/2 pairs for (ai , aj ) such that i 6= j. There-
2
fore, there exists 3(n −n)/2 antisymmetric binary relations. Also, observe that any subset of the
diagonal elements is also an antisymmetric relation. Therefore, the number of antisymmetric
2
binary relations is 2n · 3(n −n)/2 .

Claim: The number of binary relations on A which are both symmetric and antisymmetric is 2n .

Proof: Suppose (ai , aj ), i 6= j is in the relation R, then due to symmetricity of R, (aj , ai )

is also in the relation. However, this violates antisymmetric property. Therefore, for all i 6= j,
(ai , aj ) is not in the relation. Thus, the only possible elements for consideration are the diagonal

5
elements. Observe that any subset of the diagonal elements is symmetric and antisymmetric.
Therefore, the number of binary relations which are both symmetric and antisymmetric is 2n .

Claim: The number of binary relations on A which are both symmetric and asymmetric is
one.

Proof: Let R be a symmetric and asymmetric binary relation on any A. For all a ∈ A, none
of the (a, a) elements is in the relation as R is asymmetric. Clearly, off diagonal elements (a, b),
where a 6= b are not present in R. Therefore, there does not exist any of the diagonal and off
diagonal elements in R, and it follows that R = φ, which is symmetric and asymmetric.

Claim: The number of binary relations which are both reflexive and antisymmetric in the
2
set A is 3(n −n)/2 .

Proof: Since all diagonal elements are part of the reflexive relation and there are 3 possibilities
2
for each of the remaining (n2 − n)/2 elements. Thus, we get 3(n −n)/2 binary relations which are
reflexive and antisymmetric.
2 −n)/2
Claim: The number of asymmetric binary relations possible on the set A is 3(n .
2
Proof: Similar to the argument for antisymmetric relations, note that there exists 3(n −n)/2
asymmetric binary relations, as none of the diagonal elements are part of any asymmetric bi-
nary relations.

Note:
1. If A = φ then R = φ. R is reflexive and irreflexive. This is the only set and the relation having
this property.

2. Counting transitive relations precisely is a challenging task. However, we can obtain good
lower bounds and upper bounds. Any subset of the set of diagonal elements is an example tran-
sitive relation and thus, there are at least 2n transitive relations (lower bound). A trivial upper
2
bound is 2n . To obtain a good upper bound, we focus on non-transitive relations. If we get a
good lower bound for non-transitive relations, then total number of relations minus the lower
bound gives a good upper bound for transitive relations. For example, irreflexive symmetric
n2 −n
relations (except empty relation) are non-transitive relations, and there are at least 2 2 −1
2 n2 −n
non-transitive relations. Therefore, a good upper bound for transitive relations is 2n −2 2 +1.

Definitions:

R is an Equivalence relation, if R satisfies Reflexivity, Symmetricity and Transitivity. (RST

properties)
R is a Partial Order, if R is Reflexive, Antisymmetric and Transitive. (RAT properties)

Operations on relations:

R1 − R2 = {(a, b) | (a, b) ∈ R1 and (a, b) ∈

/ R2 }
R2 − R1 = {(a, b) | (a, b) ∈ R2 and (a, b) ∈
/ R1 }

6
R1 ∪ R2 = {(a, b) | (a, b) ∈ R1 or (a, b) ∈ R2 }
R1 ∩ R2 = {(a, b) | (a, b) ∈ R1 and (a, b) ∈ R2 }

Example 7. Let A be a set on integers and R1 , R2 ⊆ A × A where R1 = {(a, b) | a < b}

and R2 = {(a, b) | a > b}. Check whether the following relations satisfy the properties of rela-
tions.

Note that R1 ∪ R2 = {(a, b) | a < b or a > b}. R1 ∩ R2 = φ

Relation Reflexive Symmetric Asymmetric Antisymmetric Transitive
R1 × × X X X
R2 × × X X X
R1 ∪ R2 × X × × ×
R1 ∩ R2 × X X X X
R1 − R2 × × X X X
R2 − R1 × × X X X
R1 ∪ R2 is not transitive. Consider (−1, 2) ∈ R1 and (2, −1) ∈ R2 , and hence, (−1, 2) ∈ R1 ∪ R2
and (2, −1) ∈ R1 ∪ R2 . However, (−1, −1) ∈ / R1 ∪ R2 as −1 6< −1.
For the following theorems, we work with a set A and R1 , R2 ⊆ A × A.

Theorem 1. If R1 and R2 are reflexive, and symmetric, then R1 ∪ R2 is reflexive, and sym-
metric.

Proof. Clearly, for each a ∈ A, there exists (a, a) ∈ R1 and thus, (a, a) ∈ R1 ∪ R2 . Therefore,
R1 ∪ R2 is reflexive. We can claim that if (a, b) ∈ R1 ∪ R2 , then (b, a) ∈ R1 ∪ R2 . Case 1: if
(a, b) ∈ R1 , then (b, a) ∈ R1 as R1 is symmetric and this implies that (b, a) ∈ R1 ∪ R2 . Case
2: if (a, b) ∈ R2 , then (b, a) ∈ R2 as R2 is symmetric and this implies that (b, a) ∈ R1 ∪ R2 .
Therefore, we can conclude that R1 ∪ R2 is symmetric and thus the theorem follows.
t
u

Remark: If R1 is transitive and R2 is transitive, then R1 ∪ R2 need not be transitive.

Minimal counter example: Let A = {1, 2} such that R1 = {(1, 2)} and R2 = {(2, 1)}. R1 ∪ R2 =
{(1, 2), (2, 1)} and (1, 1) ∈
/ R1 ∪ R2 implies that R1 ∪ R2 is not transitive.

Note: From the above claim and theorem, it follows that if R1 and R2 are equivalence re-
lations, then R1 ∪ R2 need not be an equivalence relation. Is R1 ∩ R2 an equivalence relation ?

Theorem 2. If R1 and R2 are equivalence relations, then R1 ∩ R2 is an equivalence relation.

Proof. Clearly, for each a ∈ A, there exists (a, a) ∈ R1 and (a, a) ∈ R1 . Therefore, for all a ∈ A,
(a, a) ∈ R1 ∩ R2 . Therefore, R1 ∩ R2 is reflexive. We now claim that if (a, b) ∈ R1 ∩ R2 , then
(b, a) ∈ R1 ∩R2 . Note that (a, b) ∈ R1 and (a, b) ∈ R2 . Since R1 and R2 are symmetric (b, a) ∈ R1
and (b, a) ∈ R2 . Therefore (b, a) ∈ R1 ∩ R2 . If (a, b), (b, c) ∈ R1 ∩ R2 , then (a, b), (b, c) ∈ R1 and
(a, b), (b, c) ∈ R2 . Since R1 is transitive, (a, c) ∈ R1 . Similarly, since R2 is transitive, (a, c) ∈ R2 .
This implies that (a, c) ∈ R1 ∩ R2 . Therefore, we can conclude that R1 ∪ R2 is transitive and
thus, the theorem follows. t
u

7
Remark:
If R1 and R2 are equivalence relations on A,

1. R1 − R2 is not an equivalence relation (reflexivity fails).

2. R1 − R2 is not a partial order (since R1 − R2 is not reflexive).
3. R1 ⊕R2 = R1 ∪R2 −(R1 ∩R2 ) is neither equivalence relation nor partial order (reflexivity fails)

Remark: If R1 is antisymmetric and R2 is antisymmetric, then R1 ∪ R2 need not be antisym-

metric.
Minimal counter example: Let A = {1, 2} such that R1 = {(1, 2)} and R2 = {(2, 1)}. (1, 2), (2, 1) ∈
R1 ∪ R2 and 1 6= 2 implies that R1 ∪ R2 is not antisymmetric.

Note: From the above claim it follows that if R1 , R2 are partial order, then R1 ∪ R2 need
not be a partial order. Is R1 ∩ R2 a partial order ?

Theorem 3. If R1 and R2 are partial order, then R1 ∩ R2 is a partial order.

Proof. From the proof of Theorem 2, if R1 and R2 are reflexive, transitive, then R1 ∩ R2 is
reflexive, transitive. Now we shall show that if R1 and R2 are antisymmetric, then R1 ∩ R2
is antisymmetric. On the contrary, assume that R1 ∩ R2 is not antisymmetric. I.e., there exist
(a, b), (b, a) ∈ R1 ∩ R2 such that a 6= b. Note that (a, b), (b, a) ∈ R1 and (a, b), (b, a) ∈ R2
and it follows that R1 and R2 are not antisymmetric, which is a contradiction. Therefore, our
assumption is wrong and R1 ∩ R2 is antisymmetric. This implies that R1 ∩ R2 is a partial order.
This completes the proof of the theorem. t
u

Questions:
Mysterious 22 [1]
1. Count the number of transitive relations in the set A.
2. Count the number of equivalence relations and partial ordered Select any three-digit number with all
sets in the set A. digits different from one another.
2 2
3. Prove using mathematical induction that 2n · 3(n −n)/2 ≤ 2n . Write all possible two-digit numbers
4. Prove or disprove: If A 6= φ and R ⊆ A × A, then R cannot that can be formed from the three-digits
be both reflexive and irreflexive. Give an example for which selected earlier. Then divide their sum
R is neither reflexive nor irreflexive.
by the sum of the digits in the original
5. Count the number of relations which are neither reflexive nor
three-digit number. See the result!!!
irreflexive.

Composition of Relations

Let R1 ⊆ A × B and R2 ⊆ B × C, Composition of R2 on R1 ,

denoted as R1 ◦ R2 or simply R1 R2 is defined as R1 ◦ R2 =
{(a, c) | a ∈ A, c ∈ C∧∃b ∈ B such that ((a, b) ∈ R1 , (b, c) ∈ R2 )}.
Note: If R1 ⊆ A × B and R2 ⊆ C × D, then R1 ◦ R2 is undefined.
Let R1 ⊆ A × B, R2 , R3 ⊆ B × C, R4 ⊆ C × D.

Theorem 4. R1 (R2 ∪ R3 ) = R1 R2 ∪ R1 R3

8
Proof. Consider (a, c) ∈ R1 (R2 ∪ R3 ) ⇐⇒ by definition, ∃b ∈ B such that (a, b) ∈ R1 ∧ (b, c) ∈
R2 ∪ R3 .
⇐⇒ ∃b[(a, b) ∈ R1 ∧ ((b, c) ∈ R2 ∨ (b, c) ∈ R3 )]
⇐⇒ ∃b[((a, b) ∈ R1 ∧ (b, c) ∈ R2 ) ∨ ((a, b) ∈ R1 ∧ (b, c) ∈ R3 )] (distribution law)
⇐⇒ ∃b[((a, b) ∈ R1 ∧ (b, c) ∈ R2 )] ∨ ∃b[((a, b) ∈ R1 ∧ (b, c) ∈ R3 )]
⇐⇒ (a, c) ∈ R1 R2 ∨ (a, c) ∈ R1 R3 ⇐⇒ (a, c) ∈ R1 R2 ∪ R1 R3 t
u

Theorem 5. R1 (R2 ∩ R3 ) ⊂ R1 R2 ∩ R1 R3

Proof. Let (a, c) ∈ R1 (R2 ∩ R3 ) by definition, ∃b((a, b) ∈ R1 ∧ (b, c) ∈ R2 ∩ R3 )

⇐⇒ ∃b[(a, b) ∈ R1 ∧ (b, c) ∈ R2 ∧ (b, c) ∈ R3 ]
⇐⇒ ∃b[(a, b) ∈ R1 ∧ (b, c) ∈ R2 ∧ (a, b) ∈ R1 ∧ (b, c) ∈ R3 ]
=⇒ ∃b[(a, b) ∈ R1 ∧ (b, c) ∈ R2 ] ∧ ∃b[(a, b) ∈ R1 ∧ (b, c) ∈ R3 ]
Note that, the biconditional operator is changed to implication as existential quantifier respects
implication with respect to ’and’ operator.
=⇒ (a, c) ∈ R1 R2 ∧ (a, c) ∈ R1 R3 =⇒ (a, c) ∈ R1 R2 ∩ R1 R3 t
u

Theorem 6. R1 ⊆ A × B, R2 ⊆ B × C, R3 ⊆ C × D. (R1 R2 )R3 = R1 (R2 R3 )

Proof. Let (a, d) ∈ (R1 R2 )R3 by definition, ∃c((a, c) ∈ R1 R2 ∧ (c, d) ∈ R3 )

⇐⇒ ∃c [∃b[(a, b) ∈ R1 ∧ (b, c) ∈ R2 ] ∧ (c, d) ∈ R3 ]
⇐⇒ ∃c ∃b [(a, b) ∈ R1 ∧ (b, c) ∈ R2 ∧ (c, d) ∈ R3 ]
⇐⇒ ∃b ∃c [(a, b) ∈ R1 ∧ (b, c) ∈ R2 ∧ (c, d) ∈ R3 ]
⇐⇒ ∃b [(a, b) ∈ R1 ∧ ∃c [(b, c) ∈ R2 ∧ (c, d) ∈ R3 ]]
⇐⇒ ∃b [(a, b) ∈ R1 ∧ (b, d) ∈ R2 R3 ]
⇐⇒ (a, d) ∈ R1 (R2 R3 ) t
u

Claim: If R1 and R2 are both reflexive, then R1 ◦ R2 is reflexive.

Note that for all a, (a, a) ∈ R1 , and (a, a) ∈ R2 .
This implies that for all a, (a, a) ∈ R1 ◦ R2 .
t
u
Remarks:

Verify the following using examples.

– If R1 and R2 are both symmetric, then R1 ◦ R2 need not be symmetric.

R1 = {(1, 2), (2, 1)}, R2 = {(2, 3), (3, 2)} =⇒ R1 ◦ R2 = {(1, 3)}

– If R1 and R2 are both antisymmetric, then R1 ◦ R2 need not be antisymmetric.

R1 = {(1, 2), (3, 4)}, R2 = {(2, 3), (4, 1)} =⇒ R1 ◦ R2 = {(1, 3), (3, 1)}

– If R1 and R2 are both transitive, then R1 ◦ R2 need not be transitive.

R1 = {(1, 2), (3, 4)}, R2 = {(2, 3), (4, 1)} =⇒ R1 ◦ R2 = {(1, 3), (3, 1)}

– If R1 and R2 are both irreflexive, then R1 ◦ R2 need not be irreflexive.

R1 = {(1, 2)}, R2 = {(2, 1)} =⇒ R1 ◦ R2 = {(1, 1)}

9
Closure of a Relation

Let R ⊆ A × A be a non reflexive relation. To make R a reflexive relation, one can add the
elements from R0 = (A × A)\R to R so that R ∪ R0 (⊆ A × A) is reflexive. An interesting question
is what will be the minimum cardinality of the set R0 such that R ∪ R0 is a reflexive relation.
Closure operation deals with such minimum cardinality sets.

Let A be a finite set and R ⊆ A × A.

Reflexive closure of R, denoted as r(R) is a relation R0 ⊆ A × A such that

(i) R0 ⊇ R
(ii) R0 is reflexive.
(iii) For any reflexive relation R00 (6= R0 ) such that R00 ⊃ R, then R00 ⊃ R0 .

Similarly, we can define symmetric closure s(R) of R and transitive closure t(R) of R.

Note:
r(R) = R ∪ E where E = {(x, x) | x ∈ A}.
s(R) = R ∪ Rc where Rc = {(a, b) | (b, a) ∈ R}.
r(R) is a minimal superset of R which is reflexive and s(R) is a minimal superset of R which is
symmetric.

Example

A = {1, 2, 3} r(R) s(R) t(R)

R1 = {(1, 1), (2, 2), (3, 3)} R1 R1 R1
R2 = {(1, 1), (2, 1)} {(1, 1), (2, 1), (2, 2), (3, 3)} {(1, 1), (2, 1), (1, 2)} R2
R3 = φ {(1, 1), (2, 2), (3, 3)} R3 R3
R4 = A × A R4 R4 R4
R5 = {(1, 1), (2, 1), (2, 3)} {(1, 1), (2, 1), (2, 3), (2, 2), (3, 3)} {(1, 1), (2, 1), (2, 3), (1, 2), (3, 2)} R5
Some more examples
A = {1, 2, 3, 4} R6 = {(1, 2), (2, 1), (2, 3), (3, 4)}
t(R6 ) = {(1, 2), (2, 1), (2, 3), (3, 4), (1, 1), (2, 4), (1, 4), (1, 3), (2, 2)}

A = {1, 2, 3, 4, 5} R7 = {(1, 2), (3, 4), (4, 5), (5, 3), (2, 1)}
t(R7 ) = {(1, 2), (3, 4), (4, 5), (5, 3), (2, 1), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (4, 3), (3, 5), (5, 4)}

Relation as a graph

Note that each binary relation can be expressed as a directed graph. An example is illustrated
below.
A = {1, 2, 3, 4} and R = {(1, 2), (2, 1), (2, 3), (3, 4)}

We define R2 = R ◦ R and for all i > 2, Ri is composition of R on Ri−1 . i.e., Ri = Ri−1 ◦ R.

Ri = {(a, b) | (a, c) ∈ Ri−1 ∧ (c, b) ∈ R}
Using the above definition iteratively, we get

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

10
 1 2 3 4

Fig. 1. Directed graph corresponding to R

R3 = {(1, 2), (2, 1), (2, 3), (1, 4)}
R4 = {(1, 1), (2, 2), (1, 3), (2, 4)}
R5 = {(1, 2), (2, 1), (2, 3), (1, 4)}
Here R4 = R2 , R5 = R3 .
Note that R is not transitive, R∪R2 is also not transitive. However, R∪R2 ∪R3 is transitive. This

1 2 3 4

Fig. 2. Directed graph corresponding to R3

is the smallest relation which is a superset of R and transitive. Therefore, t(R) = R ∪ R2 ∪ R3 .

i
Rj is transitive. A natural
S
Thus, t(R) can be formulated as t(R) = minimum i such that R ∪
j=2
question is to find out the upper bound on i.
2
Observe that for a finite set of size n there are at most 2n distinct relations, therefore t(R) in
2
the worst case contain all 2n relations which is A × A. Otherwise, t(R) ⊂ A × A.

Questions:
1. Prove: (R2 ∪ R3 )R4 = R2 R4 ∪ R3 R4 Amazing 1089 [1]
2. Prove: (R2 ∩ R3 )R4 ⊂ R2 R4 ∩ R3 R4
Select a non-palindrome 3 digit number
xyz. Find their difference, say
abc = xyz − zyx. See the value of
abc + cba!!!

11
More on Transitive Closure

Given a relation R, a transitive closure of R is a minimal super-

set of R that is transitive. One approach to find t(R) is to check
whether R1 ∪ R2 is transitive. If not, check R1 ∪ R2 ∪ R3 is tran-
sitive and so on. It is certain that this approach terminates after
some time. In fact, if the underlying directed graph is connected,
then the longest path between any two nodes can not exceed n
and due to which in the worst case R1 ∪R2 ∪. . .∪Rn is transitive.
For the example given in Figure 1, t(R) = R1 ∪ R2 ∪ R3 . However, if the underlying directed
graph is disconnected, then we observe the following. Consider the illustration given in Figure
3. R1 = {(1, 2), (2, 1), (3, 4), (4, 5), (5, 3)}. Note that the graph corresponding to R1 is discon-
nected and has two components. It is a convention that R0 denotes the pure reflexive relation.
Transitive closure is t(R) = R1 ∪ R2 ∪ R3 , which is max(m,n) where m and n are the number
of nodes in the two components.

3 3

R0 R4
1 2 5 4 1 2 5 4
3 3

R5
R1 4 1 2 5 4
1 2 5
3 3

R2 R6
1 2 5 4 2 5 4
1
3 3

R3 R7
1 2 5 4 1 2 5 4

Fig. 3. R1 to R7 of R = R1

Also, note that R0 refers to equality relation or pure reflexive relation. Further, the smallest
integers x, y such that Rx = Ry in the graph is x = 0, and y = 6. In general, it is LCM(m,n).

Remark: Let us consider the relation R = {(a, b) | b = a + 1, a, b ∈ R}. Note that the re-
∞
Ri . Transitive closure of an infinite set is infinite.
S
lation is infinite and t(R) =
i=1

∞
Ri .
S
Theorem 7. Let R be an infinite relation. t(R) =
i=1

12
Proof. By definition t(R) is transitive. Observe that if (a, b) ∈ Rm and (b, c) ∈ Rn , then (a, c) ∈
∞
Rm+n . To show that Ri is transitive, we use the above observation. Since t(R) is minimal,
S
i=1
transitive, and it contains R, t(R) will be a subset of any transitive superset. I.e., R is such that
∞ ∞
Ri ⊃ R, clearly t(R) ⊂ Ri .
S S
t(R) ⊃ R and
i=1 i=1
∞
Ri ⊂ t(R) by induction. Base case: t(R) ⊃ R1 . Induction hypothesis: Assume
S
We prove
i=1
k
Ri . Anchor step: Let (a, b) ∈ Rk+1
S
that for k >= 1, t(R) ⊃ =⇒ there exists c such
i=1
that (a, c) ∈ Rk and (c, b) ∈ R. Notice that (a, c) ∈ t(R) from the induction hypothesis and
(c, b) ∈ t(R) from the base case and by transitivity, it follows that (a, b) ∈ t(R). Therefore,
k ∞
Ri for all k ≥ 1. It can be concluded that t(R) = Ri
S S
t(R) ⊃ t
u
i=1 i=1

Equivalence Class

We shall revisit equivalence relation in this section and introduce equivalence classes. We also
explore paritition of a set and its connection to equivalence classes.

Consider the following equivalence relations defined on A = {1, 2, 3, 4, 5}.

R1 = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)}
R2 = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (2, 1), (1, 2)}
R3 = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 3), (3, 1), (2, 4), (4, 2)}
R4 =A×A

Definition: Equivalence class of a ∈ A is defined as [a]R = {x | (x, a) ∈ R}. If R is clear

from the context, we drop the subscript R and shall denote the equivalence class of a as [a]

[1]R1 = {1} [1]R2 = {1, 2} [1]R3 = {1, 3}

[2]R1 = {2} [2]R2 = {1, 2} [2]R3 = {2, 4}
[3]R1 = {3} [3]R2 = {3} [3]R3 = {1, 3}
[4]R1 = {4} [4]R2 = {4} [4]R3 = {2, 4}
[5]R1 = {5} [5]R2 = {5} [5]R3 = {5}
Remark: The notion equivalence class is defined for each a ∈ A, independent of whether R
is an equivalence relation. For our discussion, we shall focus on R which are equivalence rela-
tions.
Properties: We consider an equivalence relation R defined on a set A.
S
1. [a] = A
∀a∈A
2. For every a, b ∈ A such that a ∈ [b], a 6= b, it follows that [a] = [b].
P
3. |[x]| = |R|.
∀x∈A
4. For any two equivalence class [a] and [b], either [a] = [b] or [a] ∩ [b] = φ.
5. For all a, b ∈ A, if a ∈ [b] then b ∈ [a].
6. For all a, b, c ∈ A, if a ∈ [b] and b ∈ [c], then a ∈ [c].
7. For all a ∈ A, [a] 6= φ.

13
Theorem 8. If [a] ∩ [b] 6= φ, then [a] = [b]

Proof. Given [a] ∩ [b] 6= φ. There exists c ∈ [a] ∩ [b]. i.e., c ∈ [a] and c ∈ [b] and by definition
a ∈ [a], b ∈ [b]. We observe the following.
(1) (c, a), (c, b) ∈ R definition
(2) (a, c), (b, c) ∈ R (1) and symmetricity
(3) (a, b), (b, a) ∈ R (1), (2) and transitivity
Consider an arbitrary element x ∈ [a]. By definition (x, a) ∈ R. Since (x, a) ∈ R and from (3)
(a, b) ∈ R, by transitivity it follows that (x, b) ∈ R. This implies x ∈ [b] and thus [a] ⊆ [b].
Similarly, consider an arbitrary element y ∈ [b]. By definition (y, b) ∈ R. Since (y, b) ∈ R and
from (3) (b, a) ∈ R, by transitivity it follows that (y, a) ∈ R. This implies y ∈ [a] and thus
[b] ⊆ [a]. Therefore, we conclude [a] = [b]. t
u
S
Theorem 9. [x] = A
x∈A
S S
Proof. Let y ∈ [x]. Clearly, y ∈ [y] and since [y] ⊆ A, y ∈ A. This implies [x] ⊂ A.
x∈A S S x∈A
Consider y ∈ A. y ∈ [c] for some c ∈ A. Since [c] ⊂ [x], y ∈ [x] and it follows that
S S x∈A x∈A
A⊂ [x]. Therefore we conclude [x] = A. t
u
x∈A x∈A

Remarks:
1. The proof of the theorem ’If [a] ∩ [b] 6= φ, then [a] = [b]’ does not make use of the property
of R being reflexive, and hence the theorem is overstated. That is, with symmetricity and tran-
sitivity, one can claim [a] = [b]. Thus, the claim ’If R is symmetric and transitive, then for any
two equivalence classes a, b ∈ A, either [a] = [b] or [a] ∩ [b] = φ.

2. Property 5 is true as R is symmetric. By definition, a ∈ [b] implies that (a, b) ∈ R. Since

R is symmetric, (b, a) ∈ R, and therefore, b ∈ [a].

3. Property 6 is true as R is transitive. By definition, (a, b), (b, c) ∈ R. Since R is transitive,

(a, c) ∈ R and therefore, a ∈ [c].

4. Property 7 is true as R is reflexive. a ∈ [a] and therefore, [a] 6= φ

5. Proof of Property 2: Suppose, there exists c ∈ [a] and c ∈ / [b]. By definition, (c, a) ∈ R.
Since a ∈ [b], (c, b) ∈ R and hence, c ∈ [b]. This is a contradiction. Therefore, [a] = [b].

Definition: Clique is a completely connected subgraph of a graph. Given an equivalence

relation and its directed graph representation, we observe that the vertices corresponding to
equivalence classes induce a clique.

Questions:

1. Prove using counting technique and PHP (Pigeon hole principle) or use mathematical in-
duction: Let R be a finite relation and G be the directed graph corresponding to R.
n
Ri , where Ri = Ri−1 R, 1 ≤ i ≤ n and n is the length of longest path in
S
t(R) =
i=1
G.
2. Find R1 to R16 for the figure shown below.

14
 1 4

8 5

3 2 7 6

Counting Equivalence Relations

In this section, we shall ask; How many equivalence relations are
Math Wonders [1]
possible on a set A?
Find the digit corresponding to each
Definition: letter
For a set A, the partition of A is {A1 , . . . , Ak } such that
send
(i) Each Ai ⊆ A
+ more
(ii) For any two Ai , Aj , Ai ∩ Aj = ∅
(iii) ∪i=k =money
i=1 Ai = A.
For example, A = {1, 2, 3, 4}, a partition of A is {{1, 2}, {3}, {4}}.
Another example of partition of A is {{1}, {2, 3, 4}}.

Observations:
1. The number of equivalence relations on A is same as the number of ways of listing all possible
sets of equivalence classes of A
2. Each set of equivalence classes corresponds to a partition of the set A.
3. Listing all possible sets of equivalence classes of A is same as listing all partitions of A.
4. Counting the number of equivalence relations on A is equivalent to counting the number of
partitions of A.

Consider the set A = {1, 2, 3}, the possible equivalence relations, equivalence classes and parti-
tion are listed below;
Equivalence Relation Equivalence Class Partition
R1 = {(1, 1), (2, 2), (3, 3)} [1] = {1}, [2] = {2}, [3] = {3} {{1}, {2}, {3}}
R2 = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)} [1] = {1, 2}, [2] = {1, 2}, [3] = {3} {{1, 2}, {3}}
R3 = {(1, 1), (2, 2), (3, 3), (1, 3), (3, 1)} [1] = {1, 3}, [2] = {2}, [3] = {1, 3} {{1, 3}, {2}}
R4 = {(1, 1), (2, 2), (3, 3), (2, 3), (3, 2)} [1] = {1}, [2] = {2, 3}, [3] = {2, 3} {{2, 3}, {1}}
R5 = A × A [1] = {1, 2, 3}, [2] = {1, 2, 3}, [3] = {{1, 2, 3}}
{1, 2, 3}
If A = {1, 2}, then there are two sets of equivalence classes; (i) [1] = {1}, [2] = {2} (ii)
[1] = [2] = {1, 2}, and the associated partitions are (i) {{1}, {2}}, (ii) {{1, 2}}. One can generate
the partitions of {1, 2, 3} from {1, 2}. Consider the element 0 30 .
From the partition {{1}, {2}}, we obtain the partitions {{1}, {2}, {3}}, {{1, 3}, {2}}, {{1}, {2, 3}}
and from the partition {{1, 2}}, we obtain the partitions {{1, 2}, {3}}, {{1, 2, 3}}. Thus, all five
partitions of the set {1, 2, 3} can be obtained from the set {1, 2}. Since each partition corre-
sponds to an equivalence relation, we generate all equivalence relations of the set {1, 2, 3} using
this approach.
This approach also indicates that one can obtain a recursive formula to obtain all partitions of

15
the set {1, 2, . . . , n}. The following counting argument was discoverd by the mathematician Bell.
Let Bn be the number of partitions (equivalence relations) possible on a set A of n elements. We
now present a recurrence relation which will count the number Bn . The approach is to generate
all partitions using a specific partition of the same set under consideration. Consider a partition
of n elements, say for example, P = {{1, 2}, {3, 4, 5}, {6, . . . , n}}. Using this partition, we recur-
sively generate all other partitions.
In general P = {A1 , A2 , . . . , Ap } and Ai ⊆ {1, . . . , n} and each Ai is distinct. In P , consider Ai
containing the element n and assume that k = |Ai \ {n}|. These k elements of
Ai can be any sub-
set in {1, . . . , n−1}. Therefore, the number of such possible sets for Ai is n−1 k , k ∈ {0, . . . , n−1}.
Now to establish a recursive relation we focus on the remaining n − k − 1 elements which are
distributed among A1 , . . . , Ai−1 , Ai+1 , . . . , An . Interestingly, there are Bn−k−1 partitions among
n−1
P n−1

n − k − 1 elements. Thus, we get Bn = k Bn−k−1 .
k=0

Note: B
1 = 1, B
2 = 2, B
3 = 5, B
4 = 15.

B5 = 40 B4 + 41 B3 + 42 B2 + 43 B1 + 44 B0 = 15 + 20 + 12 + 4 + 1 = 52.
The number Bn is known as the Bell’s number in the literature.

Rank of an equivalence relation is the number of distinct equivalence classes.

For example, consider the relations R1 to R4 given below, their ranks are;
R1 = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)}
R2 = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (2, 1), (1, 2)}
R3 = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 3), (3, 1), (2, 4), (4, 2)}
R4 = A × A

Relation Rank
R1 5
R2 4
R3 3
R4 1
In general, A × A has the least rank (one) and the pure reflexive relation (equality relation) has
the highest rank (n).

Revisit: Partial Order

In this section, we shall revisit partial order and discuss some

more properties and special relations in detail. Recall, a relation
R is a partial order if it satisfies reflexivity, antisymmetricity, and
transitivity. Further, R is a Quasi order if R is transitive and ir-
reflexive.
Trichotomy Property: For all elements a, b ∈ A, exactly one of
the following holds:
(i). (a, b) ∈ R. (ii). (b, a) ∈ R. (iii). (a = b).
A binary relation is a total order if it is a partial order and sat-
isfies the trichotomy property. R = {(a, b) | a, b ∈ N, a ≤ b} is a
partial order as well as total order.

16
Graphical Representation of Partial order relations: Hasse Diagram
Consider a partial order R and the associated graphical representation G of R. In G, we make
the following changes to obtain a graph H. The changes are (i) remove reflexivity arcs (ii) re-
move transitivity arcs (iii) make antisymmetric arcs undirected. The resultant graph is known
as Hasse diagram. An interesting observation is that Hasse diagram (diagram representing
just antisymmetric arcs) brings an ordering (hierarchy) among elements. That is, arcs such
as (1, 2), (1, 3), (2, 3) can be represented as 2 above 1 and 3 above 2, and the transitive arc (1, 3)
is ignored.

8 8 12 {a,b,c}

4 6 9 {a,b}
4 6
{a,c} {b,c}

{c}
2 3 5 7 2 3 {a} {b}

1 1 {}
Ex: 1 Ex: 5 Ex: 6

Fig. 4. Hasse diagram of Examples 1,5 and 6

Example 1: Consider the relation R: a divides b on the set A = {1, 2, . . . , 9}.

Example 5: Let A = {1, 2, . . . , 6} and R = {(a, b) | a divides b}
Example 6: R = {(A, B) | A ⊆ B}
In all of the above examples, we see that there is an ordering among elements of A. The arc
(x, y) is represented by positioning y above x.
Example 1: Consider the relation R: a divides b on the set A = {1, 2, . . . , 9}. R is a partial
order and not a total order as the elements (3, 5), (6, 9) ∈
/ R.
Example 2: (Z, ≥) is a partial order and a total order.
Example 3: (Z, >) is a not a partial order as reflexivity fails.
Example 4: (Z + , |) (| denotes ’divides’) is a partial order but not a total order.
Example 5: Let A = {1, 2, . . . , 6} and R = {(a, b) | a divides b} is a partial order but not a
total order as (3, 8), (8, 3) ∈
/R
Example 6: R = {(A, B) | A ⊆ B} on the power set of {a, b, c} is a partial order but not a
total order as ({a, c}, {b, c}), ({b, c}, {a, c}) ∈
/R

Question 1 Let A = {1, 2, 3, 4} and R = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 3), (1, 3)}. Find
a minimum augmentation relation R0 such that R ∪ R0 is a total order.
Ans: R0 = {(3, 4), (2, 4), (1, 4)}
Question 2 Let A = {1, 2}, P (A) = {φ, {1}, {2}, {1, 2}} and R = {(A, B) | A ⊆ B, A, B ∈
P (A)}. This is a partial order and can not be converted into a total order by augmenting mini-
mum pairs. Not all partial orders can be converted into a total order.

Since there is an ordering among elements of a poset, one can identify special elements in a
poset.
Definition:
Let (A, ) be a poset and B ⊆ A. (  means some relation )

17
1. An element b ∈ B is the greatest element of B if for every b0 ∈ B, b0  b.
2. An element b ∈ B is the least element of B if for every b0 ∈ B, b  b0 .
For Example 6,
Set B greatest element least element
{{a}, {a, c}} {a, c} {a}
P ({a, b, c}) {a, b, c} {}
{{a}, {b}, {c}, {}} nil {}
{{a}, {b}, {c}, {a, b}} nil nil
{{a, b}, {a, c}, {b, c}, {a, b, c}} {a, b, c} nil
Theorem 10. The greatest and least elements in a poset are
unique.

Proof. Let R ⊂ A×A be a partial order relation. On the contrary,

assume that there exist two greatest elements g1 , g2 ∈ A such
that g1 6= g2 . Since g1 is a greatest element, g1  g, ∀g ∈ A and it
follows that g1  g2 . Similarly, since g2 is a greatest element, g2 
g1 . It follows that (g1 , g2 ) ∈ R and (g2 , g1 ) ∈ R. This contradicts
the fact that R is antisymmetric. Similar argument can be made
for the fact that there exists a unique least element.
t
u
Definition: (A, ) is a well order if (A, ) is a total order and
for all A0 ⊆ A, A0 6= φ, A0 has a least element.

Note: Every finite totally ordered set is well ordered. For a

finite set which is a partial order and total order, clearly, for
any non-empty subset, the least element exists. Observe that the
Hasse diagram of a total order is a path graph (linear chain)
on n nodes. Any non-empty subset of a total order is equivalent
to any sub-path in the Hasse diagram which has the least ele-
ment.

Example:
Relation Total order Well-order
(R, ≤) X ×
(N, ≤) X X
(I, ≤) X ×
Remark: If we consider a subset A0 ⊆ A such that A0 = I or A0 = I− , then (A0 , ≤) does
not have a least element. Also, there does not exist a least element for (R+ , ≤).

Note: Mathematical induction can be applied only to well ordered sets as there is a least
element for every non-empty subset which implicitly gives an ordering among elements. This
shows that, proving claims on well-ordered sets using mathematical induction proof technique
is appropriate. Further, for well-ordered sets, the successor is well defined for each element. For
sets with no proper definition for successor of an element (for example, real numbers), the math-
ematical induction can not be used to prove claims on such sets.

Remark: Consider a set A such that |A| = n. Since each total order on A is a path (lin-
ear chain), the number of total orders possible on A is the number of path like Hasse diagrams

18
 on n nodes. Note that this is equal to the number of permutations on n nodes, which is n!. i.e.,
# total orders = # path like Hasse diagrams = # permutations = n!

Special Elements in a poset

Definition: Let (A, ) be a poset, B ⊆ A
1. An element b ∈ B is a maximal element of B if b ∈ B and there
does not exist b0 ∈ B such that b 6= b0 and b  b0 . Similarly,
minimal elements of B can be defined.
2. An element b ∈ A is upper bound for B if for every element
b0 ∈ B, b0  b. Similarly, lower bound of B can be defined.
3. An element b ∈ A is a least upper bound (lub) for B if b is an
upper bound and for every upper bound b0 of B, b  b0 .
4. An element b ∈ A is a greatest lower bound (glb) for B if b is a
lower bound and for every lower bound b0 of B, b0  b.
For Figure 4 associated with Example 5
Set B minimal elements maximal elements Lower bound Upper bound
A {1} {8, 12} {1} nil
{2, 3, 4} {2, 3} {3, 4} {1} {12}

h
g f

d e

b c

Fig. 5. Hasse diagram 2

For Figure 5
Set B minimal elements maximal elements Lower bound Upper bound lub glb
A {a} {h} {a} {h} {h} {a}
{b, c, d, e} {b, c} {d, e} {a} {f, h} {f } {a}
{a, b, c} {a} {b, c} {a} {e, f, h} {e} {a}
{d, e} {d, e} {d, e} {b, a} {f, h} {f } {b}

Lexicographic and Standard orderings

In this section, we introduce an ordering among elements of a set.
We first introduce lexicographic ordering:
P P
Given : finite alphabet, for example = {a, b}

If x, y ∈ ∗ , thenP
P
x ≤ y in the lexicographic ordering
(x precedes y) of ∗ if
(i) x is a prefix of y (or)

19
 (ii) x = zu and y = zv where z ∈ ∗ is the longest prefix com-
P
mon to x and y and u precedes v in the lexicographic ordering.

P P∗
P = {a} = {a, aa, aaa, . . .} is a partial, total and well ordered set.
P ∗
= {a, b} = {a, aa, aaa, . . . , aa . . . ab, aa . . . ba, . . . , b, ba, baa, . . .} is a partial, and to-
tal ordered set but not a well ordered. For example, there is no least element for the set
B = {b, ab, aab, aaaab, aa . . . ab}.

StandardP ordering
: alphabet and ∗ is the set of all strings over . ||x|| is the length of string
P P
Notation:
P∗
x∈
Definition:
x ≤ y if
(i) ||x|| < ||y|| or
(ii) ||x|| = ||y|| and x precedes y in the lexicographic ordering of ∗
P

P∗
Note that standard ordering is a poset, total and well ordered set as we can order as
(a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, . . .)

Acknowledgements: Lecture contents presented in this module

and subsequent modules are based on the text books mentioned
at the reference and most importantly, lectures by discrete mathe-
matics exponents affiliated to IIT Madras; Prof P.Sreenivasa Ku-
mar, Prof Kamala Krithivasan, Prof N.S.Narayanaswamy, Prof
S.A.Choudum, Prof Arindama Singh, and Prof R.Rama. Author
sincerely acknowledges all of them. Special thanks to Teaching
Assistants Mr.Renjith.P and Ms.Dhanalakshmi.S for their sincere
and dedicated effort and making this scribe possible. This lecture
scribe is based on the course ’Discrete Structures for Comput-
ing’ offered to B.Tech COE 2014 batch during Aug-Nov 2015. The author greatly benefited by
the class room interactions and wishes to appreciate the following students: Mr.Vignesh Sairaj,
Ms.Kritika Prakash, and Ms.Lalitha. Finally, author expresses sincere gratitude to Ms.Lalitha
for thorough proof reading and valuable suggestions for improving the presentation of this arti-
cle. Her valuable comments have resulted in a better article.

Reading
1. Bell numbers.
2. H. Hasse (1898-1979) and Hasse diagrams

References
1. Alfred S. Posamentier: Math Wonders to Inspire Teachers and Students ,
ASCD (2003).
2. K.H.Rosen, Discrete Mathematics and its Applications, McGraw Hill, 6th
Edition, 2007
3. D.F.Stanat and D.F.McAllister, Discrete Mathematics in Computer Sci-
ence, Prentice Hall, 1977.

20
4. C.L.Liu, Elements of Discrete Mathematics, Tata McGraw Hill, 1995

21