Tutorial 4
September 4th , 2025
1. Construct a relation R over S = {1, 2, 3, 4, 5}, such that it is an equivalence
relation as well as a partial order.
2. Let Re be an equivalence relation on a set S, and let Rp be a partial order
on the same set.
(a) Is the composite relation of applying Re first and then Rp next, an
equivalence relation, a partial order, both or neither?
(b) Is the composite relation of applying Rp first and then Re next, an
equivalence relation, a partial order, both or neither?
(c) Is the composite relation of applying Re twice, in succession, an
equivalence relation, a partial order, both or neither?
(d) Is the composite relation of applying Rp twice, in succession, an
equivalence relation, a partial order, both or neither?
3. (a) Consider
a a relation R over the set N of positive integers, such that
b
If 10 < 10 , then (a, b) in R and if
a b
10 = 10 , then if a%10 > b%10, then (a, b) in R. Is this relation
a partial order?
(b) is the relation defined above an upper lattice, a lower lattice, a lattice
or neither?
(c) If the set on which the above relation is defined is extended to all
integers, address the above two questions.
4. Consider a set of sets. We define a relation over this set where two elements
are related if and only if their intersection is of size at least 5.
(a) This relation is reflexive if and only if
(b) Is this relation symmetric, anti-symmetric or neither, in general?
(c) Is this relation transitive, in general?
1
5. Consider a generic relation defined over any list of positive integers, which
says that (x, y) ∈ R if and only if,
(((x < y) ∧ ((y − x) ≤ 200)) ∨ ((x − y) ≥ 150))
This can be instantiated by considering any finite subset of the integers of
your choice. When considered over all positive integers determine whether
this relation is:
(a) reflexive/irreflexive or neither
(b) symmetric/anti-symmetric or neither
(c) transitive
6. Suppose an equivalence relation over a set S contains exactly 79 ordered
pairs. Give the minimum and maximum possible value of |S| and also
state which values in this range are possible.
7. We know that a set is a collection of well defined, distinct objects, and
there is no further restriction. Thus we could have a set of sets (that is
the elements of the set are each sets, which are distinct). Consider such
a set A of sets {S1 , . . . , Sn }. Let us define a relation R over A where
(Si , Sj ) ∈ R if and only if Si ⊆ Sj . Is the relation R:
(a) Reflexive, irreflexive or neither?
(b) Symmetric, anti-symmetric or neither?
(c) Transitive?
8. Let S = {1, . . . , 100}, the set of the first 100 positive integers. Define a
relation R where (x, y) ∈ R if and only if
((x = y) ∨ ((|x − y| ≤ 15) ∧ (|x − y| ≥ 5)))
Find the cardinality of the largest subset X of S, such that the relation
R restricted to the subset X is an equivalence relation. How many such
subsets are there in S?