Module 2 Mathematical Relations

Course Outcome: Apply relation properties, equivalence classes, and

partial order concepts to construct Hasse diagrams, determine lattice
structures, and compute closures using Warshall’s algorithm
 Why to learn Relations?
• Modeling Real World Problems Understand and
represent relationships between entities.
– Example: In an e-commerce platform, customers (set
A) place orders (set B). A relation R = “placed” maps
customers to their orders. Helps in tracking purchases,
generating invoices, etc.
• Understanding Data Structures Core concept
behind graphs, trees, and databases.
– Example: In a social network graph, users are nodes
and friendship is a relation (edge). This relation helps
the platform suggest friends, detect communities, etc.
 Why to learn Relations?
• Foundation for Advanced Topics Forms the basis
for functions, lattices, automata, etc.
– Example: In compiler design, finite automata use
transitions between states, which are modeled using
relations. Similarly, functions are special types of
relations in math and programming.
• Logical Thinking & Abstraction Encourages
organized, step-wise thinking and classification
– Example: In school timetabling, classes (set A) must be
assigned to time slots (set B) without conflicts.
Thinking in terms of relations helps structure the
problem and find logical solutions.
 Relations: Definition
• A relation R from set A to set B is a subset of A
× B.
• It shows how elements of two sets are related.
• Example: A = {1,2}, B = {a,b}, R
• = {(1,a), (2,b)}.
 Example
• Sets:Set A (Students) = {Amit, Bhavna, Chirag}Set
B (Subjects) = {Math, English, Science}
• Define a Relation R: “is enrolled in”
• Say:
– Amit is enrolled in Math and Science
– Bhavna is enrolled in English
– Chirag is enrolled in Math and English
• 𝑅={(𝐴𝑚𝑖𝑡,𝑀𝑎𝑡ℎ),(𝐴𝑚𝑖𝑡,𝑆𝑐𝑖𝑒𝑛𝑐𝑒),(𝐵ℎ𝑎𝑣𝑛𝑎,𝐸𝑛𝑔𝑙𝑖
𝑠ℎ),(𝐶ℎ𝑖𝑟𝑎𝑔,𝑀𝑎𝑡ℎ),(𝐶ℎ𝑖𝑟𝑎𝑔,𝐸𝑛𝑔𝑙𝑖𝑠ℎ)}
 Representation of Relations
• Set of ordered pairs
• Matrix representation
• Digraph (Directed Graph) representation
 Example
• Relation Between Students and Their Favorite
Fruits
• Sets:
• Set A (Students) = {Riya, Om, Tara}
• Set B (Fruits) = {Apple, Banana, Mango}
• Define a relation R = "likes“
• Given:Riya likes Apple and BananaOm likes
BananaTara likes Mango and Apple
 Set of Ordered Pairs
• Each ordered pair shows a relation from Set A
to Set B.
• R={(Riya,Apple),(Riya,Banana),(Om,Banana),(T
ara,Mango),(Tara,Apple)}
 Matrix Representation
Apple Banana Mango
Riya 1 1 0
Om 0 1 0
Tara 1 0 1

• 1 indicates a relation exists (e.g., Riya likes

Apple).
• 0 means no relation.
Digraph (Directed Graph)
 Properties of Relations
• Reflexive: (a, a) ∈ R ∀ a ∈ A
• Symmetric: If (a, b) ∈ R ⇒ (b, a) ∈ R
• Transitive: If (a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈
R
• Antisymmetric: If (a, b) ∈ R and (b, a) ∈ R ⇒ a
=b
 Equivalence Relations
• A relation is an equivalence relation if it is:
• 1. Reflexive
• 2. Symmetric
• 3. Transitive
 Reflexive Relation
• A relation R on set A is reflexive if every element
is related to itself.
• Mathematically: ∀a ∈ A, (a, a) ∈ R
• Consider a set A={1,2,3} and
R={(1,1),(1,2),(2,2),(2,3),(3,3)}. (1,1), (2,2), (3,3)
are present in R. Hence, the relation is reflexive.
• Real-life example:"Every person knows
themselves. "So, for every person P, the relation
(P, P) holds true.
 Symmetric Relation
• A relation R on set A is symmetric if for every (a,
b) ∈ R, (b, a) is also in R.
• Consider a set A={1,2,3} and
R={(1,1),(1,2),(2,1),(2,3),(3,2)}. (1,1), (2,2), (3,3)
are present in R.
• (1,2) is present → check if (2,1) is also there
• (2,3) is present → (3,2) is also there
• So, the relation is symmetric.
• Real-life example: "If A is a friend of B, then B is
also a friend of A."
 Transitive Relation
• A relation R on set A is transitive if whenever
(a, b) ∈ R and (b, c) ∈ R, then (a, c) must also
be in R.
• Consider a set A={1,2,3} and
R={(1,2),(2,3),(1,3)}. So, the relation is
transitive.
• Real-life example:
"If A is an ancestor of B, and B is an ancestor
of C, then A is an ancestor of C."
 Equivalence Classes
• Given an equivalence relation R on set A, the
equivalence class of an element a∈A is
defined as: [a]={x∈A∣xRa}
• This means: the equivalence class of a is the
set of all elements in A that are equivalent to a
under the relation R.
Example
 Real-Life Interpretation
1. Students with Same Grade Set A = All
students in a class.
• Relation ~: "Has the same grade as".
• Then [Amit] = All students who got the same
grade as Amit.
• So, [Amit] is the equivalence class of students
who scored equally.
 Real-Life Interpretation
2. Same Birth Year
• Set A = All people.
• Relation ~: "Was born in the same year as".
• Then [Ajay] = All people born in the same year
as Ajay.
 Real-Life Interpretation
3. Congruent Angles
Set A = All angles.
Relation ~: "Has the same measure as".
Then [60°] = All angles that are 60°, no matter
their position or orientation.
 Closures of Relations
• In Discrete Mathematics, the closure of a relation
means extending a relation so that it satisfies a
specific property — such as reflexivity, symmetry,
or transitivity — without changing any existing
true relations.
• Reflexive Closure: Add (a, a) for all a ∈ A if
missing.
• Symmetric Closure: Add (b, a) if (a, b) ∈ R.
• Transitive Closure: Add (a, c) if (a, b) ∈ R and (b, c)
∈ R.
 Examples
• Let the set 𝐴={1,2,3} and the relation 𝑅={(1,2),(2,3)}
• Reflexive Closure: We must add all (a, a):
• 𝑅𝑟𝑒𝑓𝑙𝑒𝑥𝑖𝑣𝑒 = 𝑅 ∪ 1,1 , 2,2 , 3,3
• Symmetric Closure: For every (a, b), add (b, a) if not
already present:
• 𝑅𝑠𝑦𝑚𝑚𝑒𝑡𝑟𝑖𝑐 = 𝑅 ∪ 2,1 , 3,2
• Transitive Closure: Check for chains like (1,2) and (2,3)
⇒ Add (1,3):
• 𝑅𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑣𝑒 = 𝑅 ∪ 1,3
 Warshall’s Algorithm
• Used to compute transitive closure of a
relation.
• Based on adjacency matrix representation.
• Iterative algorithm updating paths between
nodes.
 Algorithm Steps
Steps:
1. Represent relation R using adjacency matrix
M (n × n).
2. For each k from 1 to n:
• For each i, j: if M[i][j] = 1 OR (M[i][k] = 1 AND
M[k][j] = 1), set M[i][j] = 1.
3. After n iterations, M gives transitive closure
R*.
 Applications of Warshall's Algorithm
• Finding reachability in directed graphs.
• Path analysis in computer networks.
• Database query optimization.
• AI and state-space exploration.
 Partial Order Relations
• A relation R on a set A is called a Partial Order
if:
– Reflexive: aRa for all a ∈ A
– Antisymmetric: if aRb and bRa, then a = b
– Transitive: if aRb and bRc, then aRc
 Example: Project Task Scheduling
• Imagine you are managing a project with these tasks:
– A: Collect requirements
– B: Design system
– C: Implement code
– D: Test system
• Here, not all tasks are comparable (e.g., "Collect
requirements" vs. "Test system" are not directly related),
but some tasks clearly depend on others:
– A must be done before B.
– B must be done before C.
– C must be done before D.
• This forms a partial order relation (denoted as "must be
completed before").
 Interpretation
• Project Task Scheduling (A → B → C → D)
• Relation: “must be completed before”
• Reflexive: Every task can be considered “before or at
the same stage as itself” (so 𝐴𝑅𝐴, 𝐵𝑅𝐵, etc.).
• Antisymmetric: If Task A must be done before Task B,
the reverse (Task B before Task A) cannot also be true,
unless A = B.
• Transitive: If A must be done before B, and B before C,
then A must be done before C.
• So it satisfies partial order definition.
 Example 1: Divisibility
• Set A = {1,2,3,6}
• Relation R = {(a,b) | a divides b}
– Reflexive: Every number divides itself
– Antisymmetric: If a divides b and b divides a → a =
b
– Transitive: If a divides b and b divides c → a
divides c
• Hence, R is a partial order.
 Example 2: Subset Relation
• Set A = {{1},{1,2},{1,2,3}}
• Relation R = ⊆ (subset of)
– Reflexive: A ⊆ A
– Antisymmetric: If A ⊆ B and B ⊆ A → A = B
– Transitive: If A ⊆ B and B ⊆ C → A ⊆ C
• Hence, ⊆ is a partial order.
 Feature Transitive Closure Partial Order Relation
Extending a relation to A relation that is reflexive,
Definition
make it transitive antisymmetric, transitive
Capture
Goal Capture all reachability
ordering/dependency
Must check if relation
Always transitive? Yes (by construction)
already satisfies 3 properties
Not necessarily (unless
Reflexive? reflexive–transitive Always reflexive
closure)
Antisymmetric? Not required Must hold
Task scheduling / “≤” in
Example Bus route reachability
numbers
Simple Analogy
•Transitive closure: “If you can travel step by step, then we mark the
destination as reachable.”
•Partial order: “If you arrange tasks or objects with ‘comes before’
relation, you get a hierarchy.”
 Poset
• A poset is a pair (A,R), where:
– A is a set of elements
– R is a partial order relation on A
• Examples of Posets
• Numbers with divisibility
– Set A={1,2,3,6}
– Relation: “divides” (∣|∣)
– 1∣2,1∣3,2∣6,3∣6
– This is a poset (A,∣).
• Subsets with inclusion
– Set A={{1},{1,2},{1,2,3}}
– Relation: “is a subset of” (⊆)
– Reflexive, antisymmetric, and transitive
– So (A,⊆) is a poset.
 Hasse Diagram
• A Hasse diagram is a graph for a partial
ordering that does not have loops or arcs that
imply transitivity and is drawn upward, thus,
eliminating the need for directional arrows.
• A Hasse diagram is a simple and visual way to
represent a partially ordered set (poset)
without cluttering it with all the redundant
information.
 Steps to Draw a Hasse Diagram
• Step 1: Create a directed graph from the
relation.
• Step 2: Remove all self-loops.
• Step 3: Remove all transitivity.
• Step 4: Remove orientation (directional
arrowheads).
Steps to Draw a Hasse Diagram
 Maximal Vs Minimal
• A maximal element in a partially ordered set is an element
that is greater than or equal to every element to which it is
comparable.
• A minimal element in a poset is an element that is less than or
equal to every element to which is comparable.
 Greatest vs Least element
• Greatest Element: In a poset (𝐴,≤), an element g∈A is the greatest
element if:𝑥≤𝑔for all 𝑥∈𝐴
– It is above everything else in the diagram.
– In a Hasse diagram, the greatest element appears at the very top (if it exists).
– Unique if it exists.
• Example: In divisibility on {1,2,3,6},6 is at the top → greatest
element.
• Least Element: An element 𝑙∈𝐴 is the least element if:𝑙≤𝑥
for all 𝑥∈𝐴
– It is below everything else in the diagram.
– In a Hasse diagram, the least element appears at the very bottom (if it exists).
– Unique if it exists.
• Example: In divisibility on {1,2,3,6},1 is at the bottom → least
element.
Maximal Vs Minimal
 Examples
• Exam Eligibility
– Course A: requires at least 60% in prior exam.
– Course B: requires at least 65%.
– To be eligible for both → need at least 65%.
– ✅ GLB = 65%.
• Wi-Fi Speed Requirement
– App A needs at least 10 Mbps.
– App B needs at least 15 Mbps.
– To run both smoothly → need at least 15 Mbps.
– ✅ GLB = 15 Mbps.
 Examples
• Weight Limit on Bridge
– Vehicle license says max 8 tons.
– Bridge board says max 10 tons.
– To be safe → actual limit = 8 tons.
– ✅ LUB = 8 tons.
• Sports Tournament Age Limit
– Tournament A allows ages up to 18 years.
– Tournament B allows ages up to 20 years.
– To play in both, you must be ≤ 18 years.
– ✅ LUB = 18 years.
 GLB (Greatest Lower Bound) and LUB
(Least Upper Bound)
• GLB (Greatest Lower Bound) in Hasse Diagram
• Also called meet.
• For two (or more) elements a and b:
– Look at all elements below both a and b.
– The highest among them is the GLB.
• LUB (Least Upper Bound) in Hasse Diagram
• Also called join.
• For two (or more) elements a and b:
– Look at all elements above both a and b.
– The lowest among them is the LUB.
 Example
• Poset 𝑃={1,2,3,6} with divisibility relation (𝑎≤𝑏 if 𝑎
divides 𝑏):
• GLB(2,3) = 1 (largest element below both).
• GLB(2,6) = 2
• LUB(2,3) = 6 (smallest element above both).
• LUB(2,6) = 6.
• Interpretation:
• GLB = meet point below (greatest common ancestor in
the diagram).
• LUB = join point above (least common successor in the
diagram).
 Totally ordered set
• A poset becomes a totally ordered set (or
linearly ordered set) if every pair of elements
is comparable.
Formally: For all 𝑎, 𝑏 ∈ 𝑃, either 𝑎 ≤ 𝑏or 𝑏 ≤
𝑎.
• Example: Natural Numbers with ≤:
{1, 2, 3, 4, …}
→ For any two numbers, one is smaller or
equal.
 Chain
• A chain in a poset is a subset of elements where
every pair of elements is comparable.
• i.e. for any two elements 𝑎,𝑏 either 𝑎≤𝑏 or 𝑏≤𝑎.
• Chain looks like a “straight path” from bottom to
top in the Hasse diagram.
• Consider the set {1, 2, 4, 8}, then {1, 2, 4, 8} is a
chain because each divides the next.
• Analogy: A chain is like students standing in a line
according to increasing height — everyone can be
compared by height.
 Antichains
• An antichain in a poset is a subset where no two
distinct elements are comparable.
• i.e. for any two elements 𝑎, 𝑏, neither 𝑎 ≤ 𝑏nor 𝑏 ≤ 𝑎.
• On a Hasse diagram, an antichain usually appears as
elements sitting at the same horizontal level (no edges
between them).
• Consider the set {2, 3, 5}, none divides the other, so
it’s an antichain.
• Analogy: An antichain is like students sitting in a row,
all different in talents (e.g., one sings, one paints, one
plays chess) but cannot be ranked against each other in
one dimension.
 Chain vs Antichain: Example
• Chain = hierarchy (boss → manager →
employee → intern).
• Antichain = equals with no hierarchy (all
interns at the same level, none manages
another).
 Lattice and Types of Lattices
• Lattice: Poset where any two elements have
• 1. Least Upper Bound (join)
• 2. Greatest Lower Bound (meet)
• Types: Distributive, Complemented, Bounded,
Modular
 Bounded lattice
• A bounded lattice is a lattice that has:
– a least element (denoted as 0) such that 0 ≤ 𝑎for
every element 𝑎in the lattice.
– a greatest element (denoted as 1) such that 𝑎 ≤
1for every element 𝑎in the lattice.
• In other words: A bounded lattice is a lattice
with a top element and a bottom element.
 Example
• Set: {1, 2, 3, 4, 6, 12}
• Ordered by “divides” relation.
– 0 (least element) = 1 (divides everything).
– 1 (greatest element) = 12 (everything divides it).
So, this is a bounded lattice.
 Contd..
• Consider the set of positive integers ℕ
= 1 2 3 4 … with the “divides” relation.
• This is a lattice because for any two numbers
𝑎, 𝑏: GLB and LUB exist
• But it is not bounded, because:
• Least element exists → 1 (it every element)
• There is no greatest element (1) → no
number is divisible by every natural number.
 Distributive Lattice
• A lattice 𝐿 ∨ ∧ is called a distributive lattice if
the operations meet (∧) and join (∨) distribute
over each other, i.e., for all 𝑎, 𝑏, 𝑐 ∈ 𝐿:
• 𝑎 ∧ 𝑏 ∨ 𝑐 = 𝑎 ∧ 𝑏 ∨ 𝑎 ∧ 𝑐 (Distributive Law
1)
• 𝑎 ∨ 𝑏 ∧ 𝑐 = 𝑎 ∨ 𝑏 ∧ 𝑎 ∨ 𝑐 (Distributive Law
2)
• If either law holds, the other follows
automatically
 Example
• Divisors of 30 under divisibility: Set:
1 2 3 5 6 10 15 30
Note: Meet ( ∧ ) = Greatest Lower
Bound (GLB) of two elements.
Join ( ∨ ) = Least Upper Bound
(LUB) of two elements.
For (2,3,5): Lets check
𝑎∧ 𝑏∨𝑐 = 𝑎∧𝑏 ∨ 𝑎∧𝑐
𝑎∨ 𝑏∧𝑐 = 𝑎∨𝑏 ∧ 𝑎∨𝑐
 Complemented lattice
• A complemented lattice is a bounded lattice (has
a least element 0 and a greatest element 1) in
which:
• For every element 𝑎, there exists an element
𝑏(called the complement of 𝑎) such that:
• 𝑎 ∧ 𝑏 = 0 and 𝑎 ∨ 𝑏 = 1
• 𝑎 ∧ 𝑏 = 0→ together they go “down” to the
bottom element.
• 𝑎 ∨ 𝑏 = 1→ together they go “up” to the top
element.
 Example
• Divisors of 30 under divisibility
• Least element = 1
• Greatest element = 30
Comp(1) = {30}
Comp(2) = {15}
Comp(3) = {10}
Comp(5) = {6}
 Modular Lattice
• A modular lattice is a lattice 𝐿 ∧ ∨ in which
the modular law holds:
• For all 𝑎, 𝑏, 𝑐 ∈ 𝐿, if 𝑎 ≤ 𝑐, then
• 𝑎∨ 𝑏∧𝑐 = 𝑎∨𝑏 ∧𝑐
 Example
• Divisors of 12under divisibility
• Set: 1 2 3 4 6 12
• Take 𝑎 = 2, 𝑏 = 3, 𝑐 = 6.
• Check a∨(b∧c)?=(a∨b)∧c
• Meet ∧ GLB
• Join ∨ LUB
 Sublattice
• A non-empty subset of a lattice which is itself
a lattice.
• A sublattice of a lattice 𝐿 ∧ ∨ is a subset 𝑆
⊆ 𝐿 such that:
• For every 𝑎, 𝑏 ∈ 𝑆, both
– 𝑎 ∧ 𝑏 ∈ 𝑆(their meet is also in 𝑆)
– 𝑎 ∨ 𝑏 ∈ 𝑆(their join is also in 𝑆)
• So a sublattice is a “closed” subset under both
meet and join.
 Example
• Divisors of 30 under divisibility: Set:
1 2 3 5 6 10 15 30
• Take subset: 𝑆 = 1 2 6
• Check closure:
• 2∧6=2∈S
• 2∨6=6∈𝑆
• 1 ∨ 2 = 2 ∈ 𝑆, 1 ∧ 2 = 1 ∈ 𝑆
• Thus 𝑆is a sublattice of 𝐿.