समुच्चय, फलन और संबंध

उद्देश्य और दायरा

इस पाठ में membership और inclusion का अंतर, set operations, function का domain और codomain, injective/surjective/bijective functions तथा सीमित समुच्चय पर relation के मूल गुण सीखेंगे। पूर्वज्ञान: सामान्य अंकगणित और तार्किक शर्तें। यह आधारभूत पाठ है, पूरा विषय नहीं। Partial orders, Hasse diagrams, lattices, algebraic structures और अनंत cardinality के तर्क इसमें शामिल नहीं हैं।

1. समुच्चय में क्रम और दोहराव नहीं होता

समुच्चय अपने तत्वों से तय होता है। इसलिए {1,2,2} = {2,1} = {1,2}। x ∈ A का अर्थ है x, A का तत्व है। A ⊆ B का अर्थ है A का हर तत्व B में है। रिक्त समुच्चय ∅ में कोई तत्व नहीं और वह हर समुच्चय का subset है: ऐसा कोई तत्व नहीं जो subset की शर्त तोड़े। {∅} रिक्त नहीं है; उसका एक तत्व रिक्त समुच्चय है।

A = {1,2} के लिए 1 ∈ A और {1} ⊆ A सही हैं, लेकिन {1} ∉ A। Proper subset A ⊊ B के लिए A ⊆ B तथा A ≠ B चाहिए। समान समुच्चय एक-दूसरे के subset होते हैं। Cardinality |A| अलग तत्व गिनती है, इसलिए |{1,1,2}| = 2 और |{∅}| = 1।

Power set P(A), A के सभी subsets का समुच्चय है। A = {a,b} के लिए P(A) = {∅,{a},{b},{a,b}}। n तत्वों में हर तत्व के दो स्वतंत्र विकल्प हैं: शामिल करें या छोड़ें। इसलिए सीमित n-तत्व वाले समुच्चय के 2^n subsets हैं। रिक्त subset और पूरा समुच्चय दोनों गिनें।

2. Set operations का हल किया उदाहरण

Universe U = {1,2,3,4,5,6}, A = {1,2,4} और B = {2,3,4} लें।

• A ∪ B = {1,2,3,4}: कम-से-कम एक समुच्चय में मौजूद।
• A ∩ B = {2,4}: दोनों में मौजूद।
• A \ B = {1}: A में, लेकिन B में नहीं।
• B \ A = {3}: difference commutative नहीं है।
• Aᶜ = U \ A = {3,5,6}: complement के लिए universe बताना आवश्यक है।

|A ∪ B| = |A| + |B| − |A ∩ B| = 3 + 3 − 2 = 4। साझा तत्वों की दूसरी गिनती घटाते हैं; तत्वों को पूरी तरह नहीं हटाते। Sets के De Morgan नियम हैं (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ और (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ। सभी complements एक ही U के सापेक्ष होने चाहिए।

Cartesian product में ordered pairs होते हैं: A × B = {(a,b): a ∈ A, b ∈ B}। X = {1,2}, Y = {u,v,w} के लिए X × Y में छह pairs हैं; |X × Y| = 2×3। सामान्यतः X × Y और Y × X अलग हैं; (1,u) और (u,1) समान नहीं।

3. Function एक विशेष relation है

A से B का relation, A × B का कोई भी subset है। Function f:A→B में A के हर तत्व का B में ठीक एक output होना चाहिए। अलग inputs का एक ही output हो सकता है। कोई input छूट जाए या एक input के दो अलग outputs हों, तो दिए domain पर वह function नहीं है।

Domain A है, codomain घोषित लक्ष्य B है और image f(A) वास्तव में मिले outputs का समुच्चय है। Function injective यानी one-to-one है यदि अलग inputs के outputs हमेशा अलग हों। Surjective यानी onto B है यदि image पूरा codomain हो। Bijective में दोनों शर्तें सही होती हैं। Injection inputs को एक output में नहीं मिलाता; surjection कोई target नहीं छोड़ता।

उदाहरण: f:{1,2,3}→{a,b,c,d}, जहाँ f(1)=a, f(2)=c, f(3)=d, injective है लेकिन surjective नहीं, क्योंकि b छूट गया। केवल codomain को {a,c,d} कर दें तो उन्हीं assignments से bijection बन जाता है। इसलिए codomain जाने बिना arrows देखकर onto होने का निर्णय नहीं कर सकते। सीमित sets में injection के लिए |A|≤|B| और surjection के लिए |A|≥|B| आवश्यक हैं; केवल आकार की ये शर्तें किसी खास function का गुण सिद्ध नहीं करतीं।

4. Composition और inverse का उदाहरण

f:{1,2}→{a,b} में 1 का output b और 2 का a लें। g:{a,b}→{0,1} में a का output 0 और b का 1 लें। Composition g∘f में पहले f लगाएँ: (g∘f)(1)=g(b)=1 और (g∘f)(2)=g(a)=0। इसका domain {1,2} और codomain {0,1} है। बीच के outputs, g के वैध inputs होने चाहिए। यहाँ g के domain पर f∘g परिभाषित नहीं है, क्योंकि g का output 0, f के domain {1,2} में नहीं है। Output 1 उस domain में है, लेकिन composition को g के हर input पर परिभाषित होना चाहिए।

Bijection f:A→B का inverse function f⁻¹:B→A हर assignment उलटता है। उदाहरण में f⁻¹(a)=2 और f⁻¹(b)=1। यदि f दो inputs को मिलाता है, तो arrows उलटने पर एक input के दो outputs मिलेंगे; inverse function नहीं बनेगा। यदि codomain का तत्व छूटा है, तो उलटा function वहाँ परिभाषित नहीं होगा। इसलिए पूरे घोषित codomain पर inverse function के लिए bijection चाहिए।

5. एक समुच्चय पर relation के गुण अलग-अलग जाँचें

A पर relation R, A × A का subset है। (a,b) ∈ R को aRb भी लिखते हैं।

• Reflexive: हर a ∈ A के लिए (a,a) मौजूद हो।
• Symmetric: (a,b) मौजूद हो तो (b,a) भी मौजूद हो।
• Antisymmetric: (a,b) और (b,a) दोनों मौजूद हों तो a=b हो। अलग तत्वों के बीच दोतरफ़ा links मना हैं; diagonal pairs स्वीकार्य हैं।
• Transitive: (a,b) और (b,c) मौजूद हों तो (a,c) भी मौजूद हो।

Antisymmetric का अर्थ “symmetric नहीं” नहीं है। Equality relation दोनों होता है। जहाँ लागू होने वाली कोई दो-कड़ी chain ही न हो, वहाँ transitivity vacuously सही है। दिए underlying set के सभी तत्वों के संदर्भ में जाँचें; यह set बदलने से reflexivity बदल सकती है।

6. Relation की जाँच का हल किया उदाहरण

A={1,2,3} पर R={(1,1),(2,2),(3,3),(1,2),(2,1)} लें। सभी diagonal pairs हैं, इसलिए R reflexive है। हर off-diagonal pair का reverse है, इसलिए symmetric है। यह antisymmetric नहीं: 1≠2 लेकिन दोनों दिशाएँ मौजूद हैं। यह transitive है: {1,2} के भीतर हर pair मौजूद है, {3} में loop मौजूद है और इन समूहों के बीच कोई link नहीं। इसलिए हर दो-कड़ी chain का आवश्यक shortcut मिलता है।

Reflexive, symmetric और transitive relation को equivalence relation कहते हैं। R, A को equivalence classes {1,2} और {3} में बाँटता है। हर तत्व ठीक एक class में है। Reflexivity तत्व को खुद से जोड़ती है, symmetry संबंध को दोनों दिशाओं में रखती है और transitivity जुड़े तत्वों को एक class में रखती है।

इसके विपरीत, A पर S={(1,2),(2,3)} transitive नहीं: दिए pairs से (1,3) आवश्यक है, जो मौजूद नहीं। S antisymmetric है क्योंकि किसी अलग pair की दोनों दिशाएँ मौजूद नहीं। गुण अलग जाँचें हैं, एक-दूसरे से प्रतिस्पर्धा करने वाले नाम नहीं।

झटपट संदर्भ और सामान्य गलतियाँ

• तत्व: x∈A। Subset: X⊆A। ∅ और {∅} अलग हैं।
• सीमित sets में |P(A)|=2^|A| और |A×B|=|A||B|।
• Function: हर domain element का ठीक एक output।
• Injection: कोई collision नहीं। Surjection: codomain में कोई छूटा तत्व नहीं। Bijection: दोनों।
• g∘f में पहले f; पूरे codomain पर inverse function के लिए bijection चाहिए।
• Equivalence relation: reflexive + symmetric + transitive।

Cardinality निकालते समय याद रखें कि set में दोहराया तत्व पहले से केवल एक बार है। Image और codomain को न मिलाएँ। सीमित sets के आकार समान होने से हर function bijective नहीं हो जाता। Transitivity गलत सिद्ध करने के लिए दो वास्तविक links और उनका गायब shortcut दिखाएँ। दो-link premise के बिना कोई एक missing pair पर्याप्त नहीं।

7. Functions की गिनती और सीमा-स्थितियाँ

A में m और B में n तत्व हों, जहाँ m,n धनात्मक पूर्णांक हैं। A→B के n^m functions हैं: हर input स्वतंत्र रूप से n outputs में से एक चुनता है। A से B के 2^(mn) relations हैं, क्योंकि mn ordered pairs में से हर pair शामिल या बाहर किया जा सकता है। दोनों गिनतियाँ अलग हैं: सामान्य relation में हर input का ठीक एक output होना आवश्यक नहीं।

A={1,2} और B={a,b,c} के लिए 3²=9 functions और 2⁶=64 relations हैं। ठीक 3×2=6 functions injective हैं। कोई function पूरे B पर surjective नहीं हो सकता, क्योंकि दो inputs से तीन अलग targets नहीं मिल सकते। सीमित domain और codomain के आकार समान होने से हर function bijective नहीं होता। हालाँकि, ऐसे दो sets के बीच किसी function के लिए injective और surjective समतुल्य शर्तें हैं। Collision होने पर कोई target छूटता है और target छूटने पर collision होना आवश्यक है।

गैर-रिक्त set पर empty relation symmetric, antisymmetric और transitive है: कोई pair या chain इन शर्तों का उल्लंघन नहीं करती। यह reflexive नहीं है, क्योंकि आवश्यक diagonal pairs मौजूद नहीं हैं। Underlying set रिक्त हो तो यही relation reflexive भी है। Relation जाँचने से पहले underlying set स्पष्ट करें।

मौलिक अभ्यास: छह single-correct MCQ

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

C01. A={1,2} के लिए कौन-सा कथन असत्य है?

A. ∅⊆A B. {1}⊆A C. {1}∈A D. 1∈A

उत्तर: C

A: रिक्त set हर set का subset है, इसलिए यह कथन सत्य है।

B: {1} का हर तत्व A में है, इसलिए कथन सत्य है।

C: A के तत्व संख्याएँ 1 और 2 हैं, set {1} नहीं; यह असत्य है।

D: संख्या 1 स्पष्ट रूप से A का तत्व है, इसलिए कथन सत्य है।

C02. A={a,b,c} हो तो |P(A)| क्या है?

A. 3 B. 6 C. 9 D. 8

उत्तर: D

A: तीन A के तत्व गिनता है, subsets नहीं।

B: छह यानी 3! क्रम गिनता है, subsets नहीं।

C: नौ यानी 3^2, A×A के ordered pairs की संख्या है।

D: तीनों तत्वों को शामिल या बाहर रखने के दो-दो विकल्प हैं; 2^3=8 subsets।

C03. f:{1,2,3}→{a,b,c,d} के outputs क्रमशः a,c,d हैं। f किस प्रकार का है?

A. Injective, surjective नहीं B. Surjective, injective नहीं C. Bijective D. न injective, न surjective

उत्तर: A

A: सभी outputs अलग हैं, लेकिन codomain का b छूटता है; इसलिए केवल injective है।

B: Collision नहीं है और b छूटता है, इसलिए इस वर्णन के दोनों भाग गलत हैं।

C: Bijection को b भी प्राप्त करना चाहिए; surjectivity नहीं है।

D: अलग inputs के outputs अलग हैं, इसलिए injection सही है।

C04. f(1)=b, f(2)=a और g(a)=0, g(b)=1 हों तो (g∘f)(2) क्या है?

A. a B. 0 C. 1 D. b

उत्तर: B

A: a बीच का परिणाम f(2) है, g लगाने के बाद का अंतिम output नहीं।

B: पहले f: f(2)=a; फिर g(a)=0।

C: एक g(b) है, लेकिन f(2)=a है, b नहीं।

D: b, f(1) का output है; यहाँ input 2 है और g भी लगाना है।

C05. {1,2} पर R={(1,1),(2,2)} लें। कौन-सा वर्णन सही है?

A. Symmetric, antisymmetric नहीं B. Antisymmetric, symmetric नहीं C. न symmetric, न antisymmetric D. Symmetric और antisymmetric दोनों

उत्तर: D

A: हर pair का reverse वही है; साथ ही अलग तत्वों की दोतरफ़ा जोड़ी नहीं, इसलिए antisymmetry भी सही है।

B: Antisymmetry सही है, लेकिन हर loop का reverse भी मौजूद है, इसलिए symmetry भी सही है।

C: दोनों गुण सही हैं; relation में केवल diagonal pairs हैं।

D: Loops अपने ही reverse हैं, इसलिए symmetry; अलग तत्वों की दोतरफ़ा जोड़ी नहीं, इसलिए antisymmetry।

C06. {1,2,3} पर S={(1,2),(2,3)} में कौन-सा missing pair सीधे transitivity की विफलता दिखाता है?

A. (1,3) B. (3,1) C. (2,1) D. (1,1)

उत्तर: A

A: मौजूद chain 1→2→3 से 1→3 चाहिए, जो अनुपस्थित है।

B: 3 से 1 की ऐसी मौजूद chain नहीं जो इस pair को अनिवार्य करे।

C: इसका न होना symmetry की समस्या दिखाता है, दी हुई chain का shortcut नहीं।

D: Missing diagonal reflexivity गलत करता है, लेकिन यहाँ कोई दो-कड़ी chain (1,1) नहीं माँगती।

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

यह आधारभूत पाठ आधिकारिक GATE 2027 CS पाठ्यक्रम के Section 1 में Discrete Mathematics से जुड़ा है। यह पूरे विषय या पूरे पाठ्यक्रम की समाप्ति नहीं है। स्रोत विषय की प्रासंगिकता बताता है; उदाहरण और अभ्यास प्रश्न मौलिक हैं।

Official GATE 2027 CS syllabus (verified 2026-10-14).