{"id":3082,"date":"2025-06-07T09:53:03","date_gmt":"2025-06-07T09:53:03","guid":{"rendered":"https:\/\/diznr.com\/?p=3082"},"modified":"2025-06-07T09:53:03","modified_gmt":"2025-06-07T09:53:03","slug":"part-08-discrete-mathematics-for-computer-science-transitive-relation-with-concept-basic","status":"publish","type":"post","link":"https:\/\/www.reilsolar.com\/pdf\/part-08-discrete-mathematics-for-computer-science-transitive-relation-with-concept-basic\/","title":{"rendered":"Part 08 – discrete mathematics for computer science-Transitive Relation with basic concept."},"content":{"rendered":"

Part 08 – discrete mathematics for computer science-Transitive Relation with basic concept.<\/p>\n

[fvplayer id=”243″]<\/p>\n

Discrete Mathematics for Computer Science<\/strong><\/h3>\n

\u00a0Part 08: Transitive Relation \u2013 Basic Concept<\/strong><\/h3>\n

\u00a0What is a Transitive Relation?<\/strong><\/h3>\n

A relation RR<\/span>R<\/span><\/span><\/span><\/span> on a set AA<\/span>A<\/span><\/span><\/span><\/span> is called transitive<\/strong> if:<\/p>\n

\u2200a,b,c\u2208A,\u00a0if\u00a0(a,b)\u2208R\u00a0and\u00a0(b,c)\u2208R,\u00a0then\u00a0(a,c)\u2208R.\\forall a, b, c \\in A, \\text{ if } (a, b) \\in R \\text{ and } (b, c) \\in R, \\text{ then } (a, c) \\in R.<\/span>\u2200<\/span>a<\/span>,<\/span>b<\/span>,<\/span>c<\/span>\u2208<\/span><\/span>A<\/span>,<\/span>\u00a0if\u00a0<\/span><\/span>(<\/span>a<\/span>,<\/span>b<\/span>)<\/span>\u2208<\/span><\/span>R<\/span>\u00a0and\u00a0<\/span><\/span>(<\/span>b<\/span>,<\/span>c<\/span>)<\/span>\u2208<\/span><\/span>R<\/span>,<\/span>\u00a0then\u00a0<\/span><\/span>(<\/span>a<\/span>,<\/span>c<\/span>)<\/span>\u2208<\/span><\/span>R<\/span>.<\/span><\/span><\/span><\/span><\/span><\/p>\n

In simple terms, if a is related to b, and b is related to c, then a must also be related to c.<\/strong><\/p>\n

\u00a0Example of a Transitive Relation<\/strong><\/h3>\n

Let A = {1, 2, 3}<\/strong> and the relation R = {(1,2), (2,3), (1,3)}<\/strong>
\u00a0Since (1,2) \u2208 R<\/strong> and (2,3) \u2208 R<\/strong>, we also have (1,3) \u2208 R<\/strong>.
\u00a0Hence, R is transitive<\/strong>.<\/p>\n

\u00a0Example of a Non-Transitive Relation<\/strong><\/h3>\n

Let A = {1, 2, 3}<\/strong> and R = {(1,2), (2,3)}<\/strong>
\u00a0Since (1,2) \u2208 R<\/strong> and (2,3) \u2208 R<\/strong>, but (1,3) \u2209 R<\/strong>, this relation is NOT transitive<\/strong>.<\/p>\n

\u00a0How to Check if a Relation is Transitive?<\/strong><\/h3>\n

\u00a0List all pairs in the relation R<\/strong>.
\u00a0Check if whenever (a, b) \u2208 R<\/strong> and (b, c) \u2208 R<\/strong>, then (a, c) \u2208 R<\/strong>.
\u00a0If the condition holds for all elements, the relation is transitive. Otherwise, it is not.<\/p>\n

\u00a0Real-Life Examples of Transitive Relations<\/strong><\/h3>\n

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

\u00a0Quick Practice:<\/strong><\/h3>\n

Determine if the following relation is transitive:
={(1,2),(2,3),(3,4),(1,3),(2,4)}R = \\{(1, 2), (2, 3), (3, 4), (1, 3), (2, 4)\\}<\/span>R<\/span>=<\/span><\/span>{(<\/span>1<\/span>,<\/span>2<\/span>)<\/span>,<\/span>(<\/span>2<\/span>,<\/span>3<\/span>)<\/span>,<\/span>(<\/span>3<\/span>,<\/span>4<\/span>)<\/span>,<\/span>(<\/span>1<\/span>,<\/span>3<\/span>)<\/span>,<\/span>(<\/span>2<\/span>,<\/span>4<\/span>)}<\/span><\/span><\/span><\/span><\/p>\n

\u00a0Comment your answer below! Need more explanation? Let\u2019s discuss!<\/strong><\/p>\n

Part 08 – discrete mathematics for computer science-Transitive Relation with basic concept.<\/a><\/h3>\n

DISCRETE MATHEMATICS FOR COMPUTER SCIENCE<\/a><\/h3>\n

Notes on Discrete Mathematics<\/a><\/h3>\n

Here is a clear and easy explanation of Transitive Relations<\/strong> from Discrete Mathematics \u2013 Part 08<\/strong>, especially useful for Computer Science, GATE, BSc, or B.Tech students<\/strong>.<\/p>\n

\n

\ud83d\udcd8 Part 08 \u2013 Discrete Mathematics for Computer Science<\/strong><\/h2>\n

\ud83d\udd17 Transitive Relation \u2013 Basic Concept (In Hindi + English)<\/strong><\/h2>\n
\n

\u2705 Definition (\u092a\u0930\u093f\u092d\u093e\u0937\u093e):<\/strong><\/h3>\n

A relation R<\/strong> on a set A<\/strong> is called transitive<\/strong> if:<\/p>\n

\n

(a, b) \u2208 R<\/strong> and (b, c) \u2208 R<\/strong> \u27f9 (a, c) \u2208 R<\/strong><\/p>\n<\/blockquote>\n

Hindi \u092e\u0947\u0902:<\/strong>
\u092f\u0926\u093f \u0915\u093f\u0938\u0940 \u0938\u0902\u092c\u0902\u0927 R \u092e\u0947\u0902<\/p>\n

\n

\u0905\u0917\u0930 (a, b) \u0914\u0930 (b, c) \u0936\u093e\u092e\u093f\u0932 \u0939\u094b\u0902,
\u0924\u094b (a, c) \u092d\u0940 \u0909\u0938 \u0938\u0902\u092c\u0902\u0927 \u092e\u0947\u0902 \u0939\u094b\u0928\u093e \u091a\u093e\u0939\u093f\u090f \u2014
\u0924\u094b \u0935\u0939 \u0938\u0902\u092c\u0902\u0927 Transitive Relation<\/strong> \u0915\u0939\u0932\u093e\u0924\u093e \u0939\u0948\u0964<\/p>\n<\/blockquote>\n

\n

\ud83e\udde0 Understanding With Example (\u0909\u0926\u093e\u0939\u0930\u0923 \u0938\u0947 \u0938\u092e\u091d\u0947\u0902):<\/strong><\/h3>\n

\u2714\ufe0f Example 1:<\/h4>\n

Let R = { (1, 2), (2, 3), (1, 3) }<\/p>\n

Check for Transitivity:
(1, 2) \u2208 R and (2, 3) \u2208 R \u2192 (1, 3) \u092d\u0940 R \u092e\u0947\u0902 \u0939\u0948 \u2705
\u27a1\ufe0f So, R is Transitive<\/strong><\/p>\n

\n

\u274c Example 2:<\/h4>\n

Let R = { (1, 2), (2, 3) }
(1, 2) \u2208 R and (2, 3) \u2208 R \u2192 But (1, 3) is not<\/strong> in R \u274c
\u27a1\ufe0f So, R is not Transitive<\/strong><\/p>\n

\n

\ud83d\udd01 Transitive Relation in Real Life (\u0935\u093e\u0938\u094d\u0924\u0935\u093f\u0915 \u091c\u0940\u0935\u0928 \u092e\u0947\u0902):<\/strong><\/h3>\n
\n
\n\n\n\n\n\n\n
Relation Type<\/th>\nTransitive?<\/th>\nExample<\/th>\n<\/tr>\n<\/thead>\n
“is ancestor of”<\/td>\n\u2714\ufe0f Yes<\/td>\nA is ancestor of B, B of C \u2192 A of C<\/td>\n<\/tr>\n
“is friend of”<\/td>\n\u274c No<\/td>\nA is friend of B, B of C \u2192 Not necessary A of C<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
\n
<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

\ud83d\udd04 Summary Chart:<\/strong><\/h3>\n
\n
\n\n\n\n\n\n\n\n
Property<\/th>\nSymbolic Rule<\/th>\nExample<\/th>\n<\/tr>\n<\/thead>\n
Reflexive<\/td>\n(a, a) \u2208 R<\/td>\n(1,1), (2,2)<\/td>\n<\/tr>\n
Symmetric<\/td>\n(a, b) \u2208 R \u21d2 (b, a) \u2208 R<\/td>\n(2,3), (3,2)<\/td>\n<\/tr>\n
Transitive<\/strong><\/td>\n(a, b) \u2208 R & (b, c) \u2208 R \u21d2 (a, c) \u2208 R<\/td>\n(1,2), (2,3), (1,3)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
\n
<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

\ud83d\udcdd Practice Exercise:<\/strong><\/h3>\n

Given R = { (1, 2), (2, 3), (3, 4), (1, 3), (1, 4) }<\/p>\n

Q:<\/strong> Is this relation Transitive?<\/p>\n

Answer:<\/strong>
Yes!
(1, 2) & (2, 3) \u21d2 (1, 3) \u2705
(2, 3) & (3, 4) \u21d2 (2, 4) \u274c Not present
\u27a1\ufe0f So, R is not fully transitive<\/strong> \u274c<\/p>\n

\n

\ud83d\udccc Tips for GATE & Exams:<\/strong><\/h3>\n