Relation composition, equivalence classes और closures

उद्देश्य और पूर्वज्ञान

पहले पाठ में relation की properties जाँची गई थीं। यहाँ arbitrary relations का composition, equivalence relation और partition का परस्पर संबंध, तथा न्यूनतम reflexive, symmetric और transitive extensions बनाएँगे। गणना finite sets पर होगी। Relation में एक input के शून्य, एक या कई outputs हो सकते हैं; उसे function मानकर न चलें।

1. Composition में बीच का element मिलाना

R⊆A×B और S⊆B×C के लिए S∘R={(a,c): किसी b∈B के लिए (a,b)∈R तथा (b,c)∈S}। पहले R, फिर S लागू होता है। कुछ पुस्तकों की notation उलटी होती है; यहाँ यही परिभाषा लागू है। कई witnesses b मिलने पर भी endpoint pair केवल एक बार गिनेंगे।

A={1,2}, B={u,v}, C={x,y}; R={(1,u),(1,v),(2,v)}, S={(u,x),(v,x),(v,y)} लें। 1 से u होकर x और v होकर x,y मिलते हैं: (1,x),(1,y)। 2 से v होकर x,y: (2,x),(2,y)। इसलिए S∘R=A×C में चार pairs हैं, पाँच paths नहीं। इन typed relations के लिए R∘S का intermediate set उपयुक्त नहीं है।

एक ही carrier पर भी composition commutative नहीं। {1,2,3} पर R={(1,2)}, S={(2,3)} लें। S∘R={(1,3)}, पर R∘S=∅। Composition associative है: T∘(S∘R) और (T∘S)∘R दोनों में ऐसे b,c चाहिए कि aRb, bSc, cTd। Grouping बदल सकती है, operation का क्रम नहीं।

A पर R²=R∘R, R³=R∘R²। Transitivity की सही शर्त R²⊆R है, R²=R नहीं। {1,2} पर R={(1,2)} में R²=∅; फिर भी R transitive है।

2. Equivalence classes ही partition के blocks हैं

Equivalence relation ~ के लिए [a]={x∈A:a~x}। Reflexivity से a∈[a]; इसलिए classes nonempty हैं और पूरा A cover करती हैं। यदि [a] तथा [b] में साझा x है, तो a~x और b~x से symmetry तथा transitivity द्वारा a~b। अब y∈[a] के लिए b~a~y, इसलिए y∈[b]। उलटी दिशा में भी यही तर्क देने से [a]=[b]। अतः classes समान होंगी या disjoint होंगी।

Partition nonempty, pairwise-disjoint blocks का परिवार है जिनका union A हो। उलटी दिशा में partition से x~y तब परिभाषित करें जब दोनों एक ही block में हों। हर element स्वयं के साथ block साझा करता है, इसलिए reflexivity। Same-block संबंध symmetric है। x,y एक block में और y,z दूसरे में हों तो साझा y और disjointness से दोनों blocks समान, इसलिए x,z भी साथ: transitivity। दोनों constructions एक-दूसरे को वापस देती हैं। Quotient A/~ distinct classes का set है; यह केवल representatives की कोई सूची नहीं है।

A={0,1,2,3,4,5,6,7} पर x~y iff 3, x−y को divide करता है। Classes {0,3,6}, {1,4,7}, {2,5} हैं। [0]=[3]=[6] को तीन अलग blocks न गिनें। Relation में 3²+3²+2²=22 pairs हैं, क्योंकि हर block अपने साथ Cartesian product देता है। सामान्यतः block sizes n₁,…,nₖ हों तो pairs की संख्या Σnᵢ² है; loops भी शामिल हैं।

3. Closure न्यूनतम आवश्यक extension है

Closure में मूल R के सभी pairs रहते हैं, माँगी गई property पूरी होती है, और वह हर दूसरे ऐसे extension का subset होता है। Pairs हटाकर property ठीक करना closure नहीं। Underlying A स्थिर रखें। I_A={(a,a):a∈A} तथा R⁻¹={(b,a):(a,b)∈R} लिखें।

• Reflexive closure R∪I_A: हर reflexive extension को missing loops जोड़ने होंगे।
• Symmetric closure R∪R⁻¹: हर symmetric extension में reverse pairs होने चाहिए।
• Transitive closure R⁺=R∪R²∪R³∪⋯: endpoints के बीच positive-length directed walk हो।
• Reflexive-transitive closure R*=I_A∪R⁺: zero-length walk भी मान्य।

R⁺ न्यूनतम क्यों है? दो positive walks जोड़ने से फिर positive walk मिलती है, इसलिए R⁺ transitive है। किसी transitive extension में walk length पर induction से हर R-walk का endpoint pair होना अनिवार्य है। इसलिए उसमें R⁺ शामिल है। Cycle अपने-आप diagonal pairs बाध्य कर सकता है, भले reflexivity न माँगी हो। Isolated element का loop R⁺ में नहीं जुड़ता।

4. Cycle और isolated element वाला trace

A={1,2,3,4} पर R={(1,2),(2,1),(2,3)} लें। R²={(1,1),(1,3),(2,2)}। इन्हें जोड़ने पर छह pairs हैं: (1,1),(1,2),(1,3),(2,1),(2,2),(2,3)। Longer walks के endpoints पहले से मौजूद हैं, इसलिए यही R⁺ है। 3 और 4 से कोई original outgoing edge नहीं; (3,3),(4,4) अनुपस्थित हैं। R* ये दो loops जोड़कर आठ pairs देता है।

इस R का symmetric closure केवल (3,2) जोड़ता है। वह स्वतः (1,3) या missing loops नहीं जोड़ता। R को contain करने वाला सबसे छोटा equivalence relation बनाने के लिए पहले reverses और loops जोड़ें, फिर transitive closure लें। Blocks {1,2,3} तथा {4} होंगे, और भीतर के सभी ordered pairs से 9+1=10 pairs मिलेंगे। तीन closures अलग-अलग लेकर केवल union कर देना पर्याप्त नहीं हो सकता: नए reverse edges से बनने वाले paths भी पूरे करने होंगे।

5. Matrix विधि में Boolean arithmetic

M[i,j]=1 iff iRj रखें। Row-source convention में (M_R M_S)[i,k]=∨ⱼ(M_R[i,j]∧M_S[j,k]) relation S∘R देता है। यह Boolean multiplication है। सामान्य arithmetic product witnesses की संख्या देता है; Boolean product केवल existence बताता है।

Transitive closure हेतु W=M से शुरू करें। k=1,…,n के हर चरण में सभी i,j के लिए W[i,j]←W[i,j]∨(W[i,k]∧W[k,j])। Stage k के बाद वे positive-length walks दर्ज हैं जिनके internal vertices {1,…,k} से आते हैं। नया walk या k को avoid करता है, या k पर दो पहले से अनुमत हिस्सों में टूटता है। यही invariant update और O(n³) समय समझाता है। Standard in-place updates मान्य हैं। शुरुआत में सभी diagonal entries 1 केवल reflexive-transitive closure के लिए करें; R⁺ चाहिए तो वास्तविक cycles को loops बनाने दें।

गलतियाँ और जाँच

Carrier और composition convention पहले लिखें। Intermediate witnesses से endpoint pairs निकालें और duplicates हटाएँ। Classes में समान blocks को merge करें। Closure के लिए R का inclusion, माँगी property और minimality तीनों जाँचें। R⁺ को चुपचाप R* न बनाएँ। केवल एक shortcut pass हमेशा पर्याप्त नहीं। Transitivity से बिना path के reverse edge नहीं मिलता।

मौलिक अभ्यास: छह एकल-सही-विकल्प MCQs

ये मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में केवल एक सही विकल्प चुनें।

RC01. {1,2,3,4} पर R={(1,2),(1,3)}, S={(2,4),(3,4)} हैं। R पहले लगाने पर S∘R क्या है?

A. {(1,4)} B. {(1,2),(1,3)} C. ∅ D. (1,4) की दो अलग copies

उत्तर: A

A: दोनों witnesses एक ही endpoint pair देते हैं; वह एक बार आएगा।

B: ये R के pairs हैं; S अभी लगाना है।

C: 2 तथा 3 दोनों से compatible chains हैं।

D: Relation set है, duplicate pair अलग element नहीं।

RC02. छह elements के equivalence relation में block sizes 1,2,3 हैं। कितने ordered pairs हैं?

A. 6 B. 11 C. 14 D. 36

उत्तर: C

A: यह elements की संख्या है, block के भीतर pairs की नहीं।

B: कुछ pairs छूटे हैं; हर block size का square देता है।

C: Loops सहित 1²+2²+3²=14।

D: 36 होने पर सब परस्पर related होते और एक block होता।

RC03. {a,b,c} पर R={(a,b),(b,a)}। कौन सा pair R⁺ में है पर R में नहीं?

A. (c,c) B. (a,c) C. (c,a) D. (a,a)

उत्तर: D

A: Isolated c से positive-length walk नहीं।

B: a से c तक walk नहीं।

C: c से कोई walk शुरू नहीं होता।

D: a→b→a की दो-edge walk यह loop बाध्य करती है।

RC04. A पर R को contain करने वाला सबसे छोटा symmetric relation कौन सा है?

A. R∩R⁻¹ B. R∪R⁻¹ C. R∪I_A D. R²

उत्तर: B

A: Intersection मूल pairs हटा सकता है; R का inclusion नहीं बचता।

B: ठीक missing reverses जोड़ें; symmetry के लिए और pairs नहीं चाहिए।

C: Loops reflexivity देते हैं, symmetry अनिवार्य नहीं।

D: Two-step endpoints reverses नहीं देते और R भी छूट सकता है।

RC05. A पर R की transitivity के समतुल्य कौन सी शर्त है?

A. हमेशा R²=R B. R⊆R² C. R²⊆R D. R=R⁻¹

उत्तर: C

A: Equality अधिक मजबूत है; अकेला edge transitive है पर square खाली।

B: यह हर edge का two-step factorization माँगता है, अलग property है।

C: हर मौजूद two-step chain का shortcut R में होना चाहिए।

D: यह symmetry है।

RC06. {1,2,3,4} पर R={(1,2),(3,2)} है। इसे contain करने वाले सबसे छोटे equivalence relation में कितने pairs हैं?

A. 10 B. 6 C. 8 D. 16

उत्तर: A

A: Reverses और transitivity से {1,2,3} साथ, {4} अलग; 3²+1²=10।

B: 1,2,3 के सभी pairs और isolated loop पूरे नहीं हैं।

C: केवल loops और reverses से 8; (1,3),(3,1) छूटते हैं।

D: इसमें 4 को अनावश्यक जोड़ा गया है; minimal नहीं।

स्रोत और दायरा

यह सीमित विस्तार GATE 2026 CS syllabus के Section 1 में relations, lattices या groups की गहराई बढ़ाता है। यह संपूर्ण Discrete Mathematics coverage का दावा नहीं है। परिभाषाएँ, उदाहरण, प्रमाण और अभ्यास मौलिक प्रस्तुति हैं।

Official GATE 2026 CS syllabus, Section 1

स्रोत जाँचा गया: 2026-10-14।