Part 08 – discrete mathematics for computer science-Transitive Relation with basic concept.

Part 08 – discrete mathematics for computer science-Transitive Relation with basic concept.

Discrete Mathematics for Computer Science

 Part 08: Transitive Relation – Basic Concept

 What is a Transitive Relation?

A relation $R$ on a set $A$ is called transitive if:

$$\forall a,b,c\in A,\text{ if }(a,b)\in R\text{ and }(b,c)\in R,\text{ then }(a,c)\in R.$$

In simple terms, if a is related to b, and b is related to c, then a must also be related to c.

 Example of a Transitive Relation

Let A = {1, 2, 3} and the relation R = {(1,2), (2,3), (1,3)}
 Since (1,2) ∈ R and (2,3) ∈ R, we also have (1,3) ∈ R.
 Hence, R is transitive.

 Example of a Non-Transitive Relation

Let A = {1, 2, 3} and R = {(1,2), (2,3)}
 Since (1,2) ∈ R and (2,3) ∈ R, but (1,3) ∉ R, this relation is NOT transitive.

 How to Check if a Relation is Transitive?

 List all pairs in the relation R.
 Check if whenever (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.
 If the condition holds for all elements, the relation is transitive. Otherwise, it is not.

 Real-Life Examples of Transitive Relations

“Is Ancestor Of” Relation: If A is an ancestor of B and B is an ancestor of C, then A is an ancestor of C ( Transitive).
“Is Greater Than” Relation: If a > b and b > c, then a > c ( Transitive).
“Is Friend Of” Relation: If A is a friend of B and B is a friend of C, it does NOT necessarily mean that A is a friend of C ( Not Transitive).

 Quick Practice:

Determine if the following relation is transitive:
$R=\{(1,2),(2,3),(3,4),(1,3),(2,4)\}$

 Comment your answer below! Need more explanation? Let’s discuss!

Part 08 – discrete mathematics for computer science-Transitive Relation with basic concept.

DISCRETE MATHEMATICS FOR COMPUTER SCIENCE

Notes on Discrete Mathematics