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

Here is a clear and easy explanation of Transitive Relations from Discrete Mathematics – Part 08, especially useful for Computer Science, GATE, BSc, or B.Tech students.

Part 08 – Discrete Mathematics for Computer Science

Transitive Relation – Basic Concept (In Hindi + English)

Definition (परिभाषा):

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

(a, b) ∈ R and (b, c) ∈ R ⟹ (a, c) ∈ R

Hindi में:
यदि किसी संबंध R में

अगर (a, b) और (b, c) शामिल हों,
तो (a, c) भी उस संबंध में होना चाहिए —
तो वह संबंध Transitive Relation कहलाता है।

Understanding With Example (उदाहरण से समझें):

Example 1:

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

Check for Transitivity:
(1, 2) ∈ R and (2, 3) ∈ R → (1, 3) भी R में है
So, R is Transitive

Example 2:

Let R = { (1, 2), (2, 3) }
(1, 2) ∈ R and (2, 3) ∈ R → But (1, 3) is not in R
So, R is not Transitive

Transitive Relation in Real Life (वास्तविक जीवन में):

Relation Type	Transitive?	Example
“is ancestor of”	Yes	A is ancestor of B, B of C → A of C
“is friend of”	No	A is friend of B, B of C → Not necessary A of C

Summary Chart:

Practice Exercise:

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

Q: Is this relation Transitive?

Answer:
Yes!
(1, 2) & (2, 3) ⇒ (1, 3)
(2, 3) & (3, 4) ⇒ (2, 4) Not present
So, R is not fully transitive

Tips for GATE & Exams:

• Check all pairs (a, b) and (b, c), then see if (a, c) is in the relation.

• Use Hasse Diagrams or Matrix representation if helpful.

Would you like:

• A worksheet on Transitive Relations?

• A video explanation in Hindi?

• Or a comparison chart of All Relation Properties (Reflexive, Symmetric, Anti-Symmetric, Transitive)?

Let me know — I can prepare anything you need!

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

DISCRETE MATHEMATICS