गणनांक

For other uses, see गणनांक (disambiguation).

सभी प्लेटोनिक ठोस के समुच्चय $S$ में 5 तत्व होते हैं। इस प्रकार $S$ का गणनांक 5 या, प्रतीकों में, $|S|=5$ है।

गणित में, किसी समुच्चय का गणनांक समुच्चय तत्वों की संख्या का माप है। उदाहरण के लिए, समुच्चय $A=\{2,4,6\}$ में 3 तत्व हैं, और इसलिए $A$ का गणनांक 3 है। 19वीं सदी के अंत में आरंभ करते हुए, इस अवधारणा को अनंत समुच्चयों के लिए सामान्यीकृत किया गया था, जो किसी को विभिन्न प्रकार के अनंत के मध्य अंतर करने और उन पर अंकगणित करने की अनुमति देता है। गणनांक के दो दृष्टिकोण हैं: जोद्विभाजन और अंतःक्षेपक का उपयोग करके स्पष्ट रुप से समुच्चयों की तुलना करते है, और दूसरा जो गणन संख्या का उपयोग करते है। किसी समुच्चय के गणनांक को उसका आकार भी कहा जाता है, जब आकार की अन्य धारणाओं के साथ कोई भ्रम संभव नहीं होता है।

समुच्चय $A$ के गणनांक को सामान्यतः $|A|$ दर्शाया जाता है, जिसमें प्रत्येक पृष्ठ एक ऊर्ध्वाधर पट्टी होती है; यह निरपेक्ष मूल्य के समान ही संकेतन है, और अर्थ संदर्भ पर निर्भर करता है। समुच्चय $A$ के गणनांक को वैकल्पिक रूप से $n(A)$, $A$ $\operatorname {card} (A)$, या $\#A$ द्वारा दर्शाया जा सकता है।

इतिहास

गणनांक की एक अपरिष्कृत भावना, एक जानकारी है कि वस्तु या घटनाओं के समूह की तुलना अन्य समूहों से अधिक, जिसमें अधिक, कम, या समान संख्या में उदाहरणों के द्वारा की जाती है, वर्तमान समय की विभिन्न पशु प्रजातियों में देखा गया है, जो लाखों साल पहले एक उत्पत्ति का सुझाव देता है। गणनांक की मानवीय अभिव्यक्ति 40000 साल पहले देखी गई थी, जिसमें एक समूह के आकार को अभिलिखित नौच के समूह, या अन्य वस्तु के प्रतिनिधि संग्रह, जैसे कि छड़ी और सीपियाँ के साथ समान किया गया था। एक संख्या के रूप में गणनांक की अमूर्तता 3000 ईसा पूर्व से सुमेरियन गणित में और वस्तु या घटनाओं के एक विशिष्ट समूह के संदर्भ के बिना संख्याओं के प्रहस्तन में स्पष्ट है।

छठी शताब्दी ईसा पूर्व से, ग्रीक दार्शनिकों के लेखन अनंत समुच्चयों का गणनांक का पहला संकेत मिलता है। जबकि वे अनंत की धारणा को क्रियाओं की एक अंतहीन श्रृंखला के रूप में मानते थे, जैसे कि किसी संख्या में बार-बार 1 जोड़ना, उन्होंने संख्याओं के अनंत समुच्चय के आकार को एक वस्तु नहीं माना है। अनंत की प्राचीन यूनानी धारणा ने वस्तु को बिना किसी सीमा के दोहराए गए भागों में विभाजित करने पर भी विचार किया था। यूक्लिड के तत्वों में, अनुरूपता को दो रेखा खंडों, a और b की लंबाई के अनुपात के रूप में तुलना करने की क्षमता के रूप में वर्णित किया गया था, जब तक एक तीसरा खंड था, चाहे वह कितना भी छोटा क्यों न हो, उसे a और b दोनों में एक से दूसरे अंत तक कई बार रखा जा सकता था। अपरिमेय संख्या के अनवेषण के साथ, यह देखा गया कि सभी परिमेय संख्याओं का अनंत समुच्चय भी प्रत्येक संभावित रेखाखंड की लंबाई का वर्णन करने के लिए पर्याप्त नहीं था। फिर भी, अनंत समुच्चय की ऐसी कोई अवधारणा नहीं थी, जिसमें गणनांक था।

अनंत समुच्चयों को श्रेष्ठतर समझने के लिए, समुच्चय सिद्धांत के प्रवर्तक जॉर्ज कैंटोर द्वारा 1880 के आसपास गणनांक की धारणा तैयार की गई थी। उन्होंने दो समुच्चयों को एक अद्वितीय संबंध के आधार पर दो समुच्चयों के तत्वों के मध्य प्रत्येक से अलग समानता के साथ समीकरण करने की प्रक्रिया की जांच की थी। 1891 में, कैंटर के विकर्ण तर्क के प्रकाशन के साथ उन्होंने प्रदर्शित किया कि संख्याओं के ऐसे समुच्चय हैं जिन्हें प्राकृतिक संख्याओं के समुच्चय के साथ प्रत्येक से अलग समानता में नहीं रखा जा सकता है, अर्थात अगणनीय समुच्चय जिनमें प्राकृतिक संख्याओं के अनंत समुच्चय की तुलना में अधिक तत्व होते हैं।

समुच्चय की तुलना

N से सम संख्याओं के समुच्चय E तक विशेषण फलन हैं। हालांकि E N का एक उचित उपसमुच्चय है, दोनों समुच्चयों का गणनांक समान है।

File:Diagonal argument powerset svg.svg

N का गणनांक उसके घात समुच्चय P(N) के समान नहीं है: N से P(N) तक प्रत्येक फलन f के लिए, समुच्चय T = {' 'n∈N: n∉f(n)}, fकी सीमा में प्रत्येक समुच्चय से असहमत है, इसलिए f विशेषण नहीं हो सकता है। चित्र एक उदाहरण f और संबंधित T दिखाता है; red: n∈f(n)\T, blue:n∈T\f(n)।

जबकि एक परिमित समुच्चय का गणनांक केवल उसके तत्वों की संख्या है, इस धारणा को अनंत समुच्चयों तक विस्तारित करना सामान्यतः स्वेच्छाचारी समुच्चय (जिनमें से कुछ संभवतः अनंत हैं) की तुलना की धारणा को परिभाषित करने के साथ प्रारंभ होता है।

परिभाषा 1: |A| = |B|

यदि A से B तक एक द्विभाजन (उर्फ, प्रत्येक से अलग समानता) उपस्तिथ है, तो दो समुच्चय A और B में समान गणनांक है, अर्थात A से B तक एक फलन जो अंतःक्षेपक औरविशेषण दोनों है। ऐसे समुच्चयों को समविभव, समान या समसंख्यक कहा जाता है। इस संबंध को A ≈ B या A ~ B से भी दर्शाया जा सकता है।

उदाहरण के लिए, गैर-ऋणात्मक सम संख्याओं के समुच्चय E = {0, 2, 4, 6, ...} में प्राकृतिक संख्याओं के समुच्चय N = {0, 1, 2, 3, ... } के समान गणनांक होता है, क्योंकि फलन f(n) = 2n N से E की ओर एक द्विभाजन है (चित्र देखें)।

परिमित समुच्चय A और B के लिए, यदि A से B तक कुछ द्विभाजन प्रस्तुत है, तो A से B तक प्रत्येक अंतःक्षेपक या विशेषण फलन एक द्विभाजन है। यह अब अनंत A और B के लिए यथार्थ नहीं है। उदाहरण के लिए, g(n) = 4n द्वारा परिभाषित N से E तक फलन g अंतःक्षेपक है, लेकिन विशेषण नहीं है, और N से E तक h, h(n) = n - (n mod 2) द्वारा परिभाषित विशेषण है, लेकिन अंतःक्षेपक नहीं है। g और h दोनों में से कोई भी |E| = |N| को चुनौती दे सकते हैं, जो कि f के अस्तित्व द्वारा स्थापित किया गया था।

परिभाषा 2: |A| ≤ |B|

यदि A से B में कोई अंतःक्षेपक फलन प्रस्तुत है, तो A का गणनांक B का गणनांक से कम या उसके समान है।

परिभाषा 3: |A| < |B|

यदि A से B तक कोई विशेषण फलन है, लेकिन कोई अंतःक्षेपक फलन नहीं है, तो A का गणनांक B का गणनांक से पूर्णतः कम है।

उदाहरण के लिए, सभी प्राकृतिक संख्याओं के समुच्चय N का गणनांक उसके घात समुच्चय P(N) से पूर्णतः कम है, क्योंकि g(n) = { n } N से P(N) तक एक अंतःक्षेपक फलन है, और यह दिखाया जा सकता है कि N से P(N) तक कोई भी फलन विशेषण नहीं हो सकता है (चित्र देखें)। इसी तर्क के अनुसार, N का गणनांक सभी वास्तविक संख्याओं के समुच्चय R का गणनांक से पूर्णतः कम है। प्रमाण के लिए, कैंटर का विकर्ण तर्क या कैंटर का पहला अगणनीय प्रमाण देखें।

यदि |A| ≤ |B| तथा |B| ≤ |A|, फिर |A| = |B| (एक तथ्य जिसे श्रोडर-बर्नस्टीन प्रमेय के नाम से जाना जाता है)। चयन का स्वयंसिद्ध इस कथन के समतुल्य है कि प्रत्येक A, B के लिए |A| ≤ |B| या |B| ≤ |A| है।

गणनसंख्या

Main article: गणनसंख्या

उपरोक्त खंड में, एक समुच्चय के गणनांक को फलनात्मक रूप से परिभाषित किया गया था। दूसरे शब्दों में, इसे एक विशिष्ट वस्तु के रूप में परिभाषित नहीं किया गया था। हालाँकि, ऐसी वस्तु को निम्नानुसार परिभाषित किया जा सकता है।

समान गणनांक होने के संबंध को समसंख्याकता कहा जाता है, और यह सभी समुच्चयों के वर्ग (समुच्चय थ्योरी) पर एक समतुल्यता संबंध है। इस संबंध के अंतर्गत समुच्चय A के समतुल्य वर्ग में वे सभी समुच्चय सम्मिलित होते हैं जिनका गणनांक A के समान होता है। समुच्चय के गणनांक को परिभाषित करने के दो प्रकार हैं:

1. किसी समुच्चय A के गणनांक को समसंख्यता के अंतर्गत उसके तुल्यता वर्ग के रूप में परिभाषित किया गया है।
2. प्रत्येक समतुल्य वर्ग के लिए एक प्रतिनिधि समुच्चय निर्दिष्ट किया गया है। सबसे सामान्य विकल्प उस कक्षा में प्रारंभिक क्रमसूचक है। इसे सामान्यतः स्वयंसिद्ध समुच्चय सिद्धांत में गणनसंख्या की परिभाषा के रूप में लिया जाता है।

चयन के स्वयंसिद्ध को मानते हुए, अनंत समुच्चयों का गणनांक को दर्शाया गया है।

$\aleph _{0}<\aleph _{1}<\aleph _{2}<\ldots .$

प्रत्येक क्रमसूचक $\alpha$ के लिए, $\aleph _{\alpha +1}$ $\aleph _{\alpha }$से बड़ी सबसे छोटी गणनसंख्या है।

प्राकृतिक संख्याओं का गणनांक को एलेफ-नल ($\aleph _{0}$) द्वारा दर्शाया जाता है, जबकि वास्तविक संख्याओं का गणनांक को ${\mathfrak {c}}$ (एक लोअरकेस फ्रैक्टूर आलेख ''c'') द्वारा दर्शाया जाता है, और इसे सांतत्यक के गणनांक के रूप में भी जाना जाता है। कैंटर के विकर्ण तर्क का उपयोग ${\mathfrak {c}}>\aleph _{0}$ दिखाया गया है। हम दिखा सकते हैं कि ${\mathfrak {c}}=2^{\aleph _{0}}$, यह प्राकृतिक संख्याओं के सभी उपसमुच्चयों के समुच्चय का गणनांक भी है।

सातत्य परिकल्पना कहती है कि $\aleph _{1}=2^{\aleph _{0}}$, अर्थात $2^{\aleph _{0}}$ $\aleph _{0}$ से बड़ी सबसे छोटी गणनसंख्या है, अर्थात ऐसा कोई समुच्चय नहीं है जिसका गणनांक पूर्णांकों और वास्तविक संख्याओं के मध्य है। सांतत्यक परिकल्पना ZFC से स्वतंत्र है, जो समुच्चय सिद्धांत का एक मानक स्वयंसिद्धकरण है; अर्थात्, ZFC से सातत्य परिकल्पना या उसके निषेध को सिद्ध करना असंभव है - परंतु ZFC संगत है। अधिक विवरण के लिए, नीचे § सातत्य का गणनांक देखें।

परिमित, गणनीय और अगणनीय समुच्चय

यदि चयन का स्वयंसिद्ध मान्य है, तो त्रिभाजन का नियम गणनांक के लिए मान्य है। इस प्रकार हम निम्नलिखित परिभाषाएँ बना सकते हैं:

• प्राकृतिक संख्याओं या | X | < | N | से कम गणनांक वाला कोई भी समुच्चय X, एक परिमित समुच्चय कहा जाता है।
• कोई भी समुच्चय X जिसमें प्राकृतिक संख्याओं के समुच्चय के समान गणनांक है, या | X | = | N | = $\aleph _{0}$, एक गणनीय अनंत समुच्चय कहा जाता है।
• प्राकृतिक संख्याओं से अधिक गणनांक वाला कोई भी समुच्चय X, या | X | > | N |, उदाहरण के लिए | R | = c> | N |, को अगणनीय कहा जाता है।

अनंत समुच्चय

उन्नीसवीं सदी के उत्तरार्ध में जॉर्ज कैंटर, थैंक गॉड फ्रीज, रिचर्ड डेडेकिंड और अन्य ने इस विचार को अस्वीकृत कर दिया कि पूरे भाग के आकार के समान नहीं हो सकता है। इसका एक उदाहरण हिल्बर्ट का ग्रैंड होटल का विरोधाभास है। वास्तव में, डेडेकाइंड ने एक अनंत समुच्चय को एक ऐसे रूप में परिभाषित किया है जिसे एक यथार्थ उपसमुच्चय के साथ प्रत्येक से अलग समतुल्यता में रखा जा सकता है (अर्थात, कैंटर के अर्थ में समान आकार वाला); अनंत की इस धारणा कोडेडेकाइंड अनंत कहा जाता है। कैंटर ने गणनसंख्या को प्रस्तावित किया, और दिखाया- आकार की उनकी द्विभाजन-आधारित परिभाषा के अनुसार- कि कुछ अनंत समुच्चय दूसरों की तुलना में अधिक हैं। सबसे छोटी अनंत गणनांक प्राकृतिक संख्या ($\aleph _{0}$) है।

सातत्य का गणनांक

Main article: सातत्य का गणनांक

कैंटर के सबसे महत्वपूर्ण परिणामों में से एक यह था कि सातत्य (${\mathfrak {c}}$) का गणनांक प्राकृतिक संख्याओं ($\aleph _{0}$) से अधिक है; अर्थात्, प्राकृतिक संख्या N की तुलना में अधिक वास्तविक संख्या R हैं। अर्थात्, कैंटर ने दिखाया कि ${\mathfrak {c}}=2^{\aleph _{0}}=\beth _{1}$ (बेथ एक देखें) संतुष्ट करता है:

$2^{\aleph _{0}}>\aleph _{0}$

(कैंटर का विकर्ण तर्क या कैंटर का पहला अगणनीय प्रमाण देखें)।

सातत्य परिकल्पना बताता है कि वास्तविक संख्याओं का गणनांक और प्राकृतिक संख्याओं के गणनांक के मध्य कोई गणनसंख्या नहीं है, अर्थात,

$2^{\aleph _{0}}=\aleph _{1}$

हालाँकि, यदिZFC सुसंगत है, तो इस परिकल्पना को व्यापक रूप से स्वीकृत ZFC स्वयंसिद्ध समुच्चय सिद्धांत के अंतर्गत न तो सिद्ध किया जा सकता है और न ही अस्वीकृत किया जा सकता है।

कार्डिनल अंकगणित का उपयोग न केवल यह दिखाने के लिए किया जा सकता है किवास्तविक संख्या रेखा में बिंदुओं की संख्या उस रेखा के किसी भी खंड में बिंदुओं की संख्या के समान है, लेकिन यह एक समतल और वास्तव में, किसी भी परिमित-विमीय समष्टि में बिंदुओं की संख्या के समान है। यह परिणाम अत्यधिक प्रतिकूल हैं, क्योंकि उनका तात्पर्य यह है कि अनंत समुच्चय S के उचित उपसमुच्चय और उचित अधिसमुच्चय उपस्थित हैं, जिनका आकार S के समान है, हालांकि S में ऐसे तत्व सम्मिलित हैं जो इसके उपसमुच्चय से संबंधित नहीं हैं, और S के अधिसमुच्चय में ऐसे तत्व सम्मिलित हैं जो इसमें सम्मिलित नहीं हैं।

इनमें से पहला परिणाम, उदाहरण के लिए, स्पर्शरेखा फलन पर विचार करके स्पष्ट होता है, जो अंतराल (-½π, ½π) और R के मध्य प्रत्येक से अलग समतुल्यता प्रदान करता है (ग्रैंड होटल के हिल्बर्ट विरोधाभास भी देखें) होटल)।

दूसरा परिणाम पहली बार 1878 में कैंटर द्वारा प्रदर्शित किया गया था, लेकिन यह 1890 में और अधिक स्पष