गणनीय समुच्चय: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 9: | Line 9: | ||
यद्यपि यहां परिभाषित गणनीय और गणनीय अनंत शब्द अधिक सामान्य हैं, किन्तु शब्दावली सार्वभौमिक नहीं है।<ref>{{cite book |last1=Manetti |first1=Marco |title=टोपोलॉजी|date=19 June 2015 |publisher=Springer |isbn=978-3-319-16958-3 |page=26 |url=https://books.google.com/books?id=89zyCQAAQBAJ&pg=PA26 |language=en}}</ref> वैकल्पिक शैली में गणनीय का उपयोग उस अर्थ के लिए किया जाता है जिसे यहां गणनीय रूप से अनंत कहा जाता है, और अधिक से अधिक गणनीय का उपयोग उस अर्थ के लिए किया जाता है जिसे यहां गणनीय कहा जाता है।<ref name="Rudin">{{Harvard citation no brackets|Rudin|1976|loc=Chapter 2}}</ref><ref>{{harvnb|Tao|2016|p=181}}</ref> अस्पष्टता से बचने के लिए, व्यक्ति अपने आप को अधिकतम गणनीय और गणनीय अनंत शब्दों तक सीमित कर सकता है, चूँकि संक्षेपण के संबंध में यह दोनों संसारो में सबसे अनुपयुक्त है।{{cn|date=September 2021}} पाठक को राय दी जाती है कि साहित्य में गणनीय शब्द का सामना करते समय उपयोग में आने वाली परिभाषा का परिक्षण करें। | यद्यपि यहां परिभाषित गणनीय और गणनीय अनंत शब्द अधिक सामान्य हैं, किन्तु शब्दावली सार्वभौमिक नहीं है।<ref>{{cite book |last1=Manetti |first1=Marco |title=टोपोलॉजी|date=19 June 2015 |publisher=Springer |isbn=978-3-319-16958-3 |page=26 |url=https://books.google.com/books?id=89zyCQAAQBAJ&pg=PA26 |language=en}}</ref> वैकल्पिक शैली में गणनीय का उपयोग उस अर्थ के लिए किया जाता है जिसे यहां गणनीय रूप से अनंत कहा जाता है, और अधिक से अधिक गणनीय का उपयोग उस अर्थ के लिए किया जाता है जिसे यहां गणनीय कहा जाता है।<ref name="Rudin">{{Harvard citation no brackets|Rudin|1976|loc=Chapter 2}}</ref><ref>{{harvnb|Tao|2016|p=181}}</ref> अस्पष्टता से बचने के लिए, व्यक्ति अपने आप को अधिकतम गणनीय और गणनीय अनंत शब्दों तक सीमित कर सकता है, चूँकि संक्षेपण के संबंध में यह दोनों संसारो में सबसे अनुपयुक्त है।{{cn|date=September 2021}} पाठक को राय दी जाती है कि साहित्य में गणनीय शब्द का सामना करते समय उपयोग में आने वाली परिभाषा का परिक्षण करें। | ||
गिनती योग्य शर्तें<ref>{{Harvard citation no brackets|Kamke|1950|page=2}}</ref> और संख्यात्मक<ref name="Lang">{{Harvard citation no brackets|Lang|1993|loc=§2 of Chapter I}}</ref><ref name="Apostol">{{Harvard citation no brackets|Apostol|1969|loc=Chapter 1.14|p=23}}</ref> का भी उपयोग किया जा सकता है, दाहरण के लिए क्रमशः गणनीय और गणनीय अनंत का विचार करते हुए I<ref>{{cite book |last1=Thierry |first1=Vialar |title=गणित की पुस्तिका|date=4 April 2017 |publisher=BoD - Books on Demand |isbn=978-2-9551990-1-5 |page=24 |url=https://books.google.com/books?id=RkepDgAAQBAJ&pg=PA24 |language=en}}</ref> किन्तु चूँकि परिभाषाएँ भिन्न-भिन्न होती हैं, इसलिए पाठक को | गिनती योग्य शर्तें<ref>{{Harvard citation no brackets|Kamke|1950|page=2}}</ref> और संख्यात्मक<ref name="Lang">{{Harvard citation no brackets|Lang|1993|loc=§2 of Chapter I}}</ref><ref name="Apostol">{{Harvard citation no brackets|Apostol|1969|loc=Chapter 1.14|p=23}}</ref> का भी उपयोग किया जा सकता है, दाहरण के लिए क्रमशः गणनीय और गणनीय अनंत का विचार करते हुए I<ref>{{cite book |last1=Thierry |first1=Vialar |title=गणित की पुस्तिका|date=4 April 2017 |publisher=BoD - Books on Demand |isbn=978-2-9551990-1-5 |page=24 |url=https://books.google.com/books?id=RkepDgAAQBAJ&pg=PA24 |language=en}}</ref> किन्तु चूँकि परिभाषाएँ भिन्न-भिन्न होती हैं, इसलिए पाठक को पुनः उपयोग में आने वाली परिभाषा का परिक्षण करने की राय दी जाती है।<ref>{{cite book |last1=Mukherjee |first1=Subir Kumar |title=वास्तविक विश्लेषण में पहला कोर्स|date=2009 |publisher=Academic Publishers |isbn=978-81-89781-90-3 |page=22 |url=https://books.google.com/books?id=n5AhsN5UQ8IC&pg=PA22 |language=en}}</ref> | ||
==परिभाषा== | ==परिभाषा== | ||
समुच्चय <math>S</math> गणनीय है यदि: | |||
* इसकी प्रमुखता <math>|S|</math> से कम या बराबर है <math>\aleph_0</math> ([[aleph-अशक्त]]), [[प्राकृतिक संख्या]]ओं के | * इसकी प्रमुखता <math>|S|</math> से कम या बराबर है, <math>\aleph_0</math> ([[aleph-अशक्त]]), [[प्राकृतिक संख्या]]ओं के समुच्चय की कार्डिनैलिटी <math>\N</math> <ref name=Yaqub/> <math>S</math> को <math>\N</math> से अन्तःक्षेपण फलन उपस्थित है I<ref name=Singh>{{cite book |last1=Singh |first1=Tej Bahadur |title=टोपोलॉजी का परिचय|date=17 May 2019 |publisher=Springer |isbn=978-981-13-6954-4 |page=422 |url=https://books.google.com/books?id=UQiZDwAAQBAJ&pg=PA422 |language=en}}</ref><ref name=Katzourakis>{{cite book |last1=Katzourakis |first1=Nikolaos |last2=Varvaruca |first2=Eugen |title=आधुनिक विश्लेषण का एक उदाहरणात्मक परिचय|date=2 January 2018 |publisher=CRC Press |isbn=978-1-351-76532-9 |url=https://books.google.com/books?id=jBFFDwAAQBAJ&pg=PT15 |language=en}}</ref> | ||
* <math>S</math> खाली है या वहां से कोई [[विशेषण फलन]] | * <math>S</math> खाली है या वहां से कोई [[विशेषण फलन]] उपस्थित है I <ref name=Katzourakis/> <math>\N</math> से <math>S</math> के बीच विशेषण मानचित्रण <math>S</math> और <math>\N</math> का उपसमुच्चय उपस्थित है I<ref>{{harvnb|Halmos|1960|loc=p. 91}}</ref> | ||
* <math>S</math> या तो परिमित समुच्चय | * <math>S</math> या तो परिमित समुच्चय (<math>|S|<\aleph_0</math>) है, या गणनीय रूप से अनंत समुच्चय है।<ref name="Lang"/> ये सभी परिभाषाएँ समतुल्य हैं। | ||
समुच्चय <math>S</math> गणनीय रूप से [[अनंत सेट|अनंत समुच्चय]] है यदि: | |||
* इसकी प्रमुखता <math>|S|</math> बिलकुल है <math>\aleph_0</math>.<ref name=Yaqub/> | * इसकी प्रमुखता <math>|S|</math> बिलकुल है <math>\aleph_0</math>.<ref name=Yaqub/> विशेषण और विशेषण (और इसलिए आक्षेप) के बीच मानचित्रण है <math>S</math> और <math>\N</math>. | ||
* <math>S</math> के साथ [[एक-एक पत्राचार]] | * <math>S</math> के साथ [[एक-एक पत्राचार]] है <math>\N</math>.<ref>{{harvnb|Kamke|1950|loc=p. 2}}</ref> | ||
* के तत्व <math>S</math> अनंत क्रम में व्यवस्थित किया जा सकता है <math>a_0, a_1, a_2, \ldots</math>, कहाँ <math>a_i</math> से भिन्न है <math>a_j</math> के लिए <math>i\neq j</math> और प्रत्येक तत्व <math>S</math> सूचीबद्ध है।<ref>{{cite book |last1=Dlab |first1=Vlastimil |last2=Williams |first2=Kenneth S. |title=Invitation To Algebra: A Resource Compendium For Teachers, Advanced Undergraduate Students And Graduate Students In Mathematics |date=9 June 2020 |publisher=World Scientific |isbn=978-981-12-1999-3 |page=8 |url=https://books.google.com/books?id=l9rrDwAAQBAJ&pg=PA8 |language=en}}</ref><ref>{{harvnb|Tao|2016|p=182}}</ref> | * के तत्व <math>S</math> अनंत क्रम में व्यवस्थित किया जा सकता है <math>a_0, a_1, a_2, \ldots</math>, कहाँ <math>a_i</math> से भिन्न है <math>a_j</math> के लिए <math>i\neq j</math> और प्रत्येक तत्व <math>S</math> सूचीबद्ध है।<ref>{{cite book |last1=Dlab |first1=Vlastimil |last2=Williams |first2=Kenneth S. |title=Invitation To Algebra: A Resource Compendium For Teachers, Advanced Undergraduate Students And Graduate Students In Mathematics |date=9 June 2020 |publisher=World Scientific |isbn=978-981-12-1999-3 |page=8 |url=https://books.google.com/books?id=l9rrDwAAQBAJ&pg=PA8 |language=en}}</ref><ref>{{harvnb|Tao|2016|p=182}}</ref> | ||
समुच्चय [[बेशुमार|अपरिमित]] है यदि वह गणनीय नहीं है, अर्थात उसकी प्रमुखता इससे अधिक है <math>\aleph_0</math>.<ref name=Yaqub>{{cite book |last1=Yaqub |first1=Aladdin M. |title=मेटालॉजिक का एक परिचय|date=24 October 2014 |publisher=Broadview Press |isbn=978-1-4604-0244-3 |url=https://books.google.com/books?id=cyljCAAAQBAJ&pg=PT187 |language=en}}</ref> | |||
==इतिहास== | ==इतिहास== | ||
1874 में, जॉर्ज कैंटर के | 1874 में, जॉर्ज कैंटर के प्रथम समुच्चय सिद्धांत लेख में, कैंटर ने सिद्ध किया कि वास्तविक संख्याओं का समुच्चय अपरिमित है, इस प्रकार सभी अपरिमित समुच्चय गणनीय नहीं हैं।<ref>{{citation|title=Roads to Infinity: The Mathematics of Truth and Proof|first=John C.|last=Stillwell|author-link=John Stillwell|publisher=CRC Press|year=2010| isbn=9781439865507|page=10|url=https://books.google.com/books?id=XvPRBQAAQBAJ&pg=PA10|quote=Cantor's discovery of uncountable sets in 1874 was one of the most unexpected events in the history of mathematics. Before 1874, infinity was not even considered a legitimate mathematical subject by most people, so the need to distinguish between countable and uncountable infinities could not have been imagined.}}</ref> 1878 में, उन्होंने कार्डिनैलिटी को परिभाषित करने और तुलना करने के लिए अनेक पत्राचार का उपयोग किया।<ref>Cantor 1878, p. 242.</ref> 1883 में, उन्होंने अपनी अनंत [[क्रमसूचक संख्या]] के साथ प्राकृतिक संख्याओं का विस्तार किया, और भिन्न-भिन्न अपरिमित कार्डिनलिटी वाले अपरिमित समुच्चयों का उत्पादन करने के लिए क्रमसूचकों के समुच्चय का उपयोग किया।<ref>Ferreirós 2007, pp. 268, 272–273.</ref> | ||
==परिचय== | ==परिचय== | ||
समुच्चय (गणित) तत्वों का संग्रह होता है, और इसे कई तरीकों से वर्णित किया जा सकता है। एक तरीका बस इसके सभी तत्वों को सूचीबद्ध करना है; उदाहरण के लिए, पूर्णांक 3, 4 और 5 से युक्त समुच्चय को दर्शाया जा सकता है <math>\{3, 4, 5\}</math>, जिसे रोस्टर फॉर्म कहा जाता है।<ref>{{Cite web|date=2021-05-09|title=What Are Sets and Roster Form?|url=https://www.expii.com/t/what-are-sets-and-roster-form-4300| url-status=live|website=expii|archive-url=https://web.archive.org/web/20200918224155/https://www.expii.com/t/what-are-sets-and-roster-form-4300 |archive-date=2020-09-18 }}</ref> हालाँकि, यह केवल छोटे समुच्चयों के लिए प्रभावी है; बड़े समुच्चयों के लिए, यह समय लेने वाला और त्रुटि-प्रवण होगा। हर एक तत्व को सूचीबद्ध करने के बजाय, कभी-कभी किसी समुच्चय में प्रारंभिक तत्व और अंतिम तत्व के बीच कई तत्वों को दर्शाने के लिए एक दीर्घवृत्त (...) का उपयोग किया जाता है, यदि लेखक का मानना है कि पाठक आसानी से अनुमान लगा सकता है कि ... क्या दर्शाता है; उदाहरण के लिए, <math>\{1, 2, 3, \dots, 100\}</math> संभवतः 1 से 100 तक [[पूर्णांक]]ों के समुच्चय को दर्शाता है। हालाँकि, इस मामले में भी, सभी तत्वों को सूचीबद्ध करना अभी भी संभव है, क्योंकि समुच्चय में तत्वों की संख्या सीमित है। यदि हम समुच्चय के तत्वों को 1, 2, इत्यादि तक क्रमांकित करते हैं <math>n</math>, यह हमें आकार के समुच्चय की सामान्य परिभाषा देता है <math>n</math>. | |||
[[File:Aplicación 2 inyectiva sobreyectiva02.svg|thumb|x100px|पूर्णांक से सम संख्याओं तक विशेषण मानचित्रण]]कुछ समुच्चय अनंत हैं; इन | [[File:Aplicación 2 inyectiva sobreyectiva02.svg|thumb|x100px|पूर्णांक से सम संख्याओं तक विशेषण मानचित्रण]]कुछ समुच्चय अनंत हैं; इन समुच्चयों में इससे भी अधिक है <math>n</math> तत्व कहाँ <math>n</math> कोई पूर्णांक है जिसे निर्दिष्ट किया जा सकता है। (कोई फर्क नहीं पड़ता कि निर्दिष्ट पूर्णांक कितना बड़ा है <math>n</math> है, जैसे <math>n=10^{1000}</math>, अनंत समुच्चय से अधिक है <math>n</math> तत्व।) उदाहरण के लिए, प्राकृतिक संख्याओं का समुच्चय, द्वारा निरूपित <math>\{0, 1, 2, 3, 4, 5,\dots\}</math>,{{efn|name=ZeroN|Since there is an obvious [[bijection]] between <math>\N</math> and <math>\N^*=\{1,2,3,\dots\}</math>, it makes no difference whether one considers 0 a natural number or not. In any case, this article follows [[ISO 31-11]] and the standard convention in [[mathematical logic]], which takes 0 as a natural number.}} में अनंत रूप से कई तत्व हैं, और हम इसका आकार देने के लिए किसी प्राकृतिक संख्या का उपयोग नहीं कर सकते हैं। समुच्चयों को अलग-अलग वर्गों में विभाजित करना स्वाभाविक लग सकता है: एक तत्व वाले सभी समुच्चयों को एक साथ रखें; सभी समुच्चय जिनमें दो तत्व एक साथ हैं; ...; अंत में, सभी अनंत समुच्चयों को एक साथ रखें और उन्हें समान आकार का मानें। यह दृश्य अनगिनत अनंत समुच्चयों के लिए अच्छा काम करता है और जॉर्ज कैंटर के काम से पहले यह प्रचलित धारणा थी। उदाहरण के लिए, अपरिमित रूप से अनेक विषम पूर्णांक, अपरिमित रूप से अनेक सम पूर्णांक और कुल मिलाकर अपरिमित रूप से अनेक पूर्णांक होते हैं। हम इन सभी समुच्चयों को एक ही आकार का मान सकते हैं क्योंकि हम चीजों को इस तरह व्यवस्थित कर सकते हैं कि, प्रत्येक पूर्णांक के लिए, एक अलग सम पूर्णांक हो: | ||
<math display="block">\ldots \, -\! 2\! \rightarrow \! - \! 4, \, -\! 1\! \rightarrow \! - \! 2, \, 0\! \rightarrow \! 0, \, 1\! \rightarrow \! 2, \, 2\! \rightarrow \! 4 \, \cdots</math> | <math display="block">\ldots \, -\! 2\! \rightarrow \! - \! 4, \, -\! 1\! \rightarrow \! - \! 2, \, 0\! \rightarrow \! 0, \, 1\! \rightarrow \! 2, \, 2\! \rightarrow \! 4 \, \cdots</math> | ||
या, अधिक सामान्यतः, <math>n \rightarrow 2n</math> (तस्वीर देखने)। हमने यहां जो किया है वह पूर्णांकों और सम पूर्णांकों को एक-से-एक पत्राचार (या आक्षेप) में व्यवस्थित करना है, जो एक [[फ़ंक्शन (गणित)]] है जो दो | या, अधिक सामान्यतः, <math>n \rightarrow 2n</math> (तस्वीर देखने)। हमने यहां जो किया है वह पूर्णांकों और सम पूर्णांकों को एक-से-एक पत्राचार (या आक्षेप) में व्यवस्थित करना है, जो एक [[फ़ंक्शन (गणित)]] है जो दो समुच्चयों के बीच मैप करता है जैसे कि प्रत्येक समुच्चय का प्रत्येक तत्व एक ही तत्व से मेल खाता है दूसरे समुच्चय में. आकार, कार्डिनलिटी की यह गणितीय धारणा यह है कि दो समुच्चय एक ही आकार के होते हैं यदि और केवल तभी जब उनके बीच कोई आपत्ति हो। हम उन सभी समुच्चयों को अनंत कहते हैं जो पूर्णांकों के साथ एक-से-एक पत्राचार में हैं और कहते हैं कि उनमें कार्डिनैलिटी है <math>\aleph_0</math>. | ||
जॉर्ज कैंटर ने दिखाया कि सभी अनंत | जॉर्ज कैंटर ने दिखाया कि सभी अनंत समुच्चय गणनीय रूप से अनंत नहीं हैं। उदाहरण के लिए, वास्तविक संख्याओं को प्राकृतिक संख्याओं (गैर-नकारात्मक पूर्णांक) के साथ एक-से-एक पत्राचार में नहीं रखा जा सकता है। वास्तविक संख्याओं के समुच्चय में प्राकृतिक संख्याओं के समुच्चय की तुलना में अधिक प्रमुखता होती है और इसे बेशुमार कहा जाता है। | ||
==औपचारिक सिंहावलोकन== | ==औपचारिक सिंहावलोकन== | ||
परिभाषा के अनुसार, एक | परिभाषा के अनुसार, एक समुच्चय <math>S</math> यदि बीच में कोई आपत्ति मौजूद है तो गणनीय है <math>S</math> और प्राकृतिक संख्याओं का एक उपसमुच्चय <math>\N=\{0,1,2,\dots\}</math>. उदाहरण के लिए, पत्राचार को परिभाषित करें | ||
<math display=block> | <math display=block> | ||
a \leftrightarrow 1,\ b \leftrightarrow 2,\ c \leftrightarrow 3 | a \leftrightarrow 1,\ b \leftrightarrow 2,\ c \leftrightarrow 3 | ||
| Line 41: | Line 41: | ||
चूँकि प्रत्येक तत्व <math>S=\{a,b,c\}</math> के ठीक एक तत्व के साथ जोड़ा गया है <math>\{1,2,3\}</math>, और इसके विपरीत, यह एक आक्षेप को परिभाषित करता है, और उसे दिखाता है <math>S</math> गणनीय है. इसी प्रकार हम दिखा सकते हैं कि सभी परिमित समुच्चय गणनीय हैं। | चूँकि प्रत्येक तत्व <math>S=\{a,b,c\}</math> के ठीक एक तत्व के साथ जोड़ा गया है <math>\{1,2,3\}</math>, और इसके विपरीत, यह एक आक्षेप को परिभाषित करता है, और उसे दिखाता है <math>S</math> गणनीय है. इसी प्रकार हम दिखा सकते हैं कि सभी परिमित समुच्चय गणनीय हैं। | ||
जहाँ तक अनंत समुच्चयों की बात है, एक समुच्चय <math>S</math> यदि बीच में कोई आपत्ति है तो यह गणनीय रूप से अनंत है <math>S</math> और सभी <math>\N</math>. उदाहरण के तौर पर, | जहाँ तक अनंत समुच्चयों की बात है, एक समुच्चय <math>S</math> यदि बीच में कोई आपत्ति है तो यह गणनीय रूप से अनंत है <math>S</math> और सभी <math>\N</math>. उदाहरण के तौर पर, समुच्चय पर विचार करें <math>A=\{1,2,3,\dots\}</math>, धनात्मक पूर्णांकों का समुच्चय, और <math>B=\{0,2,4,6,\dots\}</math>, सम पूर्णांकों का समुच्चय। हम प्राकृतिक संख्याओं पर आपत्ति प्रदर्शित करके यह दिखा सकते हैं कि ये समुच्चय गणनीय रूप से अनंत हैं। इसे असाइनमेंट का उपयोग करके हासिल किया जा सकता है <math>n \leftrightarrow n+1</math> और <math>n \leftrightarrow 2n</math>, ताकि | ||
<math display=block>\begin{matrix} | <math display=block>\begin{matrix} | ||
0 \leftrightarrow 1, & 1 \leftrightarrow 2, & 2 \leftrightarrow 3, & 3 \leftrightarrow 4, & 4 \leftrightarrow 5, & \ldots \\[6pt] | 0 \leftrightarrow 1, & 1 \leftrightarrow 2, & 2 \leftrightarrow 3, & 3 \leftrightarrow 4, & 4 \leftrightarrow 5, & \ldots \\[6pt] | ||
| Line 49: | Line 49: | ||
{{math theorem | math_statement = A subset of a countable set is countable.<ref>{{harvnb|Halmos|1960|page=91}}</ref>}} | {{math theorem | math_statement = A subset of a countable set is countable.<ref>{{harvnb|Halmos|1960|page=91}}</ref>}} | ||
प्राकृतिक संख्याओं के सभी [[क्रमित युग्म]]ों का समुच्चय (प्राकृतिक संख्याओं के दो | प्राकृतिक संख्याओं के सभी [[क्रमित युग्म]]ों का समुच्चय (प्राकृतिक संख्याओं के दो समुच्चयों का [[कार्तीय गुणन]]फल, <math>\N\times\N</math> is countably infinite, as can be seen by following a path like the one in the picture: [[File:Pairing natural.svg|thumb|300px|[[कैंटर युग्मन फ़ंक्शन]] प्राकृतिक संख्याओं के प्रत्येक जोड़े को एक प्राकृतिक संख्या निर्दिष्ट करता है]]परिणामी [[मानचित्र (गणित)]] इस प्रकार आगे बढ़ता है: | ||
<math display=block> | <math display=block> | ||
0 \leftrightarrow (0, 0), 1 \leftrightarrow (1, 0), 2 \leftrightarrow (0, 1), 3 \leftrightarrow (2, 0), 4 \leftrightarrow (1, 1), 5 \leftrightarrow (0, 2), 6 \leftrightarrow (3, 0), \ldots | 0 \leftrightarrow (0, 0), 1 \leftrightarrow (1, 0), 2 \leftrightarrow (0, 1), 3 \leftrightarrow (2, 0), 4 \leftrightarrow (1, 1), 5 \leftrightarrow (0, 2), 6 \leftrightarrow (3, 0), \ldots | ||
| Line 55: | Line 55: | ||
यह मैपिंग ऐसे सभी ऑर्डर किए गए जोड़े को कवर करती है। | यह मैपिंग ऐसे सभी ऑर्डर किए गए जोड़े को कवर करती है। | ||
त्रिकोणीय मानचित्रण पुनरावर्तन का यह रूप सामान्यीकृत होता है <math>n</math>-प्राकृतिक संख्याओं का समूह, अर्थात्, <math>(a_1,a_2,a_3,\dots,a_n)</math> कहाँ <math>a_i</math> और <math>n</math> के पहले दो तत्वों को बार-बार मैप करके, प्राकृतिक संख्याएँ हैं <math>n</math>-एक प्राकृतिक संख्या में ट्यूपल करें। उदाहरण के लिए, <math>(0, 2, 3)</math> के रूप में लिखा जा सकता है <math>((0, 2), 3)</math>. तब <math>(0, 2)</math> 5 तक मानचित्र <math>((0, 2), 3)</math> के लिए मानचित्र <math>(5, 3)</math>, तब <math>(5, 3)</math> 39 तक मैप करता है। चूंकि एक अलग 2-टुपल, वह एक जोड़ी है जैसे <math>(a,b)</math>, एक अलग प्राकृतिक संख्या के लिए मैप, एक ही तत्व द्वारा दो एन-टुपल्स के बीच का अंतर यह सुनिश्चित करने के लिए पर्याप्त है कि एन-टुपल्स को अलग-अलग प्राकृतिक संख्याओं के लिए मैप किया जा रहा है। तो, के | त्रिकोणीय मानचित्रण पुनरावर्तन का यह रूप सामान्यीकृत होता है <math>n</math>-प्राकृतिक संख्याओं का समूह, अर्थात्, <math>(a_1,a_2,a_3,\dots,a_n)</math> कहाँ <math>a_i</math> और <math>n</math> के पहले दो तत्वों को बार-बार मैप करके, प्राकृतिक संख्याएँ हैं <math>n</math>-एक प्राकृतिक संख्या में ट्यूपल करें। उदाहरण के लिए, <math>(0, 2, 3)</math> के रूप में लिखा जा सकता है <math>((0, 2), 3)</math>. तब <math>(0, 2)</math> 5 तक मानचित्र <math>((0, 2), 3)</math> के लिए मानचित्र <math>(5, 3)</math>, तब <math>(5, 3)</math> 39 तक मैप करता है। चूंकि एक अलग 2-टुपल, वह एक जोड़ी है जैसे <math>(a,b)</math>, एक अलग प्राकृतिक संख्या के लिए मैप, एक ही तत्व द्वारा दो एन-टुपल्स के बीच का अंतर यह सुनिश्चित करने के लिए पर्याप्त है कि एन-टुपल्स को अलग-अलग प्राकृतिक संख्याओं के लिए मैप किया जा रहा है। तो, के समुच्चय से एक इंजेक्शन <math>n</math>-प्राकृतिक संख्याओं के समुच्चय के ट्यूपल्स <math>\N</math> सिद्ध है. के समुच्चय के लिए <math>n</math>- कार्टेशियन उत्पाद द्वारा परिमित रूप से कई अलग-अलग समुच्चयों से बने टुपल्स, प्रत्येक टुपल में प्रत्येक तत्व का एक प्राकृतिक संख्या के साथ पत्राचार होता है, इसलिए प्रत्येक टुपल को प्राकृतिक संख्याओं में लिखा जा सकता है, फिर प्रमेय को साबित करने के लिए उसी तर्क को लागू किया जाता है। | ||
{{math theorem | math_statement = The [[Cartesian product]] of finitely many countable sets is countable.<ref>{{Harvard citation no brackets|Halmos|1960|page=92}}</ref>{{efn|'''Proof:''' Observe that <math>\N\times\N</math> is countable as a consequence of the definition because the function <math>f:\N\times\N\to\N</math> given by <math>f(m,n)=2^m\cdot3^n</math> is injective.<ref>{{Harvard citation no brackets|Avelsgaard|1990|page=182}}</ref> It then follows that the Cartesian product of any two countable sets is countable, because if <math>A</math> and <math>B</math> are two countable sets there are surjections <math>f:\N\to A</math> and <math>g:\N\to B</math>. So <math>f\times g:\N\times\N\to A\times B</math> | {{math theorem | math_statement = The [[Cartesian product]] of finitely many countable sets is countable.<ref>{{Harvard citation no brackets|Halmos|1960|page=92}}</ref>{{efn|'''Proof:''' Observe that <math>\N\times\N</math> is countable as a consequence of the definition because the function <math>f:\N\times\N\to\N</math> given by <math>f(m,n)=2^m\cdot3^n</math> is injective.<ref>{{Harvard citation no brackets|Avelsgaard|1990|page=182}}</ref> It then follows that the Cartesian product of any two countable sets is countable, because if <math>A</math> and <math>B</math> are two countable sets there are surjections <math>f:\N\to A</math> and <math>g:\N\to B</math>. So <math>f\times g:\N\times\N\to A\times B</math> | ||
| Line 67: | Line 67: | ||
इसी प्रकार, [[बीजगणितीय संख्या]]ओं का समुच्चय गणनीय होता है।<ref>{{Harvard citation no brackets|Kamke|1950|pages=3–4}}</ref>{{efn|1='''Proof:''' Per definition, every algebraic number (including complex numbers) is a root of a polynomial with integer coefficients. Given an algebraic number <math>\alpha</math>, let <math>a_0x^0 + a_1 x^1 + a_2 x^2 + \cdots + a_n x^n</math> be a polynomial with integer coefficients such that <math>\alpha</math> is the <math>k</math>-th root of the polynomial, where the roots are sorted by absolute value from small to big, then sorted by argument from small to big. We can define an injection (i. e. one-to-one) function <math>f:\mathbb{A}\to\Q</math> given by <math>f(\alpha) = 2^{k-1} \cdot 3^{a_0} \cdot 5^{a_1} \cdot 7^{a_2} \cdots {p_{n+2}}^{a_n}</math>, where <math>p_n</math> is the <math>n</math>-th [[prime number|prime]].}} | इसी प्रकार, [[बीजगणितीय संख्या]]ओं का समुच्चय गणनीय होता है।<ref>{{Harvard citation no brackets|Kamke|1950|pages=3–4}}</ref>{{efn|1='''Proof:''' Per definition, every algebraic number (including complex numbers) is a root of a polynomial with integer coefficients. Given an algebraic number <math>\alpha</math>, let <math>a_0x^0 + a_1 x^1 + a_2 x^2 + \cdots + a_n x^n</math> be a polynomial with integer coefficients such that <math>\alpha</math> is the <math>k</math>-th root of the polynomial, where the roots are sorted by absolute value from small to big, then sorted by argument from small to big. We can define an injection (i. e. one-to-one) function <math>f:\mathbb{A}\to\Q</math> given by <math>f(\alpha) = 2^{k-1} \cdot 3^{a_0} \cdot 5^{a_1} \cdot 7^{a_2} \cdots {p_{n+2}}^{a_n}</math>, where <math>p_n</math> is the <math>n</math>-th [[prime number|prime]].}} | ||
कभी-कभी एक से अधिक मैपिंग उपयोगी होती है: एक | कभी-कभी एक से अधिक मैपिंग उपयोगी होती है: एक समुच्चय <math>A</math> गणनीय के रूप में दिखाया जाना एक-से-एक को दूसरे समुच्चय में मैप (इंजेक्शन) करना है <math>B</math>, तब <math>A</math> गणनीय सिद्ध होता है यदि <math>B</math> प्राकृतिक संख्याओं के समुच्चय पर एक-से-एक मैप किया जाता है। उदाहरण के लिए, सकारात्मक परिमेय संख्याओं के समुच्चय को प्राकृतिक संख्या जोड़े (2-टुपल्स) के समुच्चय पर आसानी से एक-से-एक मैप किया जा सकता है क्योंकि <math>p/q</math> के लिए मानचित्र <math>(p,q)</math>. चूँकि प्राकृतिक संख्या युग्मों का समुच्चय प्राकृतिक संख्याओं के समुच्चय के लिए एक-से-एक मैप (वास्तव में एक-से-एक पत्राचार या आक्षेप) है, जैसा कि ऊपर दिखाया गया है, सकारात्मक तर्कसंगत संख्या समुच्चय गणनीय साबित होता है। | ||
{{math theorem | math_statement = Any finite [[union (set theory)|union]] of countable sets is countable.<ref>{{Harvard citation no brackets|Avelsgaard|1990|page=180}}</ref><ref>{{Harvard citation no brackets|Fletcher|Patty|1988|page=187}}</ref>{{efn|1='''Proof:''' If <math>A_i</math> is a countable set for each <math>i</math> in <math>I=\{1,\dots,n\}</math>, then for each <math>n</math> there is a surjective function <math>g_i:\N\to A_i</math> and hence the function | {{math theorem | math_statement = Any finite [[union (set theory)|union]] of countable sets is countable.<ref>{{Harvard citation no brackets|Avelsgaard|1990|page=180}}</ref><ref>{{Harvard citation no brackets|Fletcher|Patty|1988|page=187}}</ref>{{efn|1='''Proof:''' If <math>A_i</math> is a countable set for each <math>i</math> in <math>I=\{1,\dots,n\}</math>, then for each <math>n</math> there is a surjective function <math>g_i:\N\to A_i</math> and hence the function | ||
| Line 74: | Line 74: | ||
}}}} | }}}} | ||
यह जानने की दूरदर्शिता के साथ कि अनगिनत | यह जानने की दूरदर्शिता के साथ कि अनगिनत समुच्चय हैं, हम आश्चर्यचकित हो सकते हैं कि क्या इस अंतिम परिणाम को और आगे बढ़ाया जा सकता है या नहीं। इसका उत्तर हाँ और नहीं है, हम इसे बढ़ा सकते हैं, लेकिन ऐसा करने के लिए हमें एक नया सिद्धांत मानने की आवश्यकता है। | ||
{{math theorem | math_statement = (Assuming the [[axiom of countable choice]]) The union of countably many countable sets is countable.{{efn|1='''Proof''': As in the finite case, but <math>I=\N</math> and we use the [[axiom of countable choice]] to pick for each <math>i</math> in <math>\N</math> a surjection <math>g_i</math> from the non-empty collection of surjections from <math>\N</math> to <math>A_i</math>.<ref>{{cite book |last1=Hrbacek |first1=Karel |last2=Jech |first2=Thomas |title=Introduction to Set Theory, Third Edition, Revised and Expanded |date=22 June 1999 |publisher=CRC Press |isbn=978-0-8247-7915-3 |page=141 |url=https://www.google.com/books/edition/Introduction_to_Set_Theory_Third_Edition/Er1r0n7VoSEC?hl=en&gbpv=1&pg=PA141 |language=en}}</ref> Note that since we are considering the surjection <math>G : \mathbf{N} \times \mathbf{N} \to \bigcup_{i \in I} A_i</math>, rather than an injection, there is no requirement that the sets be disjoint.}}}} | {{math theorem | math_statement = (Assuming the [[axiom of countable choice]]) The union of countably many countable sets is countable.{{efn|1='''Proof''': As in the finite case, but <math>I=\N</math> and we use the [[axiom of countable choice]] to pick for each <math>i</math> in <math>\N</math> a surjection <math>g_i</math> from the non-empty collection of surjections from <math>\N</math> to <math>A_i</math>.<ref>{{cite book |last1=Hrbacek |first1=Karel |last2=Jech |first2=Thomas |title=Introduction to Set Theory, Third Edition, Revised and Expanded |date=22 June 1999 |publisher=CRC Press |isbn=978-0-8247-7915-3 |page=141 |url=https://www.google.com/books/edition/Introduction_to_Set_Theory_Third_Edition/Er1r0n7VoSEC?hl=en&gbpv=1&pg=PA141 |language=en}}</ref> Note that since we are considering the surjection <math>G : \mathbf{N} \times \mathbf{N} \to \bigcup_{i \in I} A_i</math>, rather than an injection, there is no requirement that the sets be disjoint.}}}} | ||
[[File:Countablepath.svg|thumb|300px|गणनीय समुच्चयों की गणनीय संख्या की गणना]]उदाहरण के लिए, गणनीय समुच्चय दिए गए हैं <math>\textbf{a},\textbf{b},\textbf{c},\dots</math>, हम पहले प्रत्येक | [[File:Countablepath.svg|thumb|300px|गणनीय समुच्चयों की गणनीय संख्या की गणना]]उदाहरण के लिए, गणनीय समुच्चय दिए गए हैं <math>\textbf{a},\textbf{b},\textbf{c},\dots</math>, हम पहले प्रत्येक समुच्चय के प्रत्येक तत्व को एक टुपल निर्दिष्ट करते हैं, फिर हम ऊपर देखे गए त्रिकोणीय गणना के एक प्रकार का उपयोग करके प्रत्येक टुपल को एक सूचकांक निर्दिष्ट करते हैं: | ||
<math display=block> | <math display=block> | ||
\begin{array}{ c|c|c } | \begin{array}{ c|c|c } | ||
| Line 96: | Line 96: | ||
\end{array} | \end{array} | ||
</math> | </math> | ||
हमें सभी | हमें सभी समुच्चयों को अनुक्रमित करने के लिए गणनीय विकल्प के सिद्धांत की आवश्यकता है <math>\textbf{a},\textbf{b},\textbf{c},\dots</math> इसके साथ ही। | ||
{{math theorem | math_statement = The set of all finite-length [[sequence]]s of natural numbers is countable.}} | {{math theorem | math_statement = The set of all finite-length [[sequence]]s of natural numbers is countable.}} | ||
यह | यह समुच्चय लंबाई-1 अनुक्रम, लंबाई-2 अनुक्रम, लंबाई-3 अनुक्रमों का संघ है, जिनमें से प्रत्येक एक गणनीय समुच्चय (परिमित कार्टेशियन उत्पाद) है। तो हम गणनीय समुच्चयों के गणनीय संघ के बारे में बात कर रहे हैं, जो पिछले प्रमेय के अनुसार गणनीय है। | ||
{{math theorem | math_statement = The set of all finite [[subset]]s of the natural numbers is countable.}} | {{math theorem | math_statement = The set of all finite [[subset]]s of the natural numbers is countable.}} | ||
| Line 110: | Line 110: | ||
# If the function <math>g:S\to T</math> is surjective and <math>S</math> is countable then <math>T</math> is countable.}} | # If the function <math>g:S\to T</math> is surjective and <math>S</math> is countable then <math>T</math> is countable.}} | ||
ये इंजेक्शन/विशेषण फलन के रूप में गणनीय | ये इंजेक्शन/विशेषण फलन के रूप में गणनीय समुच्चय की परिभाषाओं का अनुसरण करते हैं।{{efn|'''Proof''': For (1) observe that if <math>T</math> is countable there is an injective function <math>h:T\to\N</math>. Then if <math>f:S\to T</math> is injective the composition <math>h\circ f:S\to \N</math> is injective, so <math>S</math> is countable. | ||
For (2) observe that if <math>S</math> is countable, either <math>S</math> is empty or there is a surjective function <math>h:\N\to S</math>. Then if <math>g:S\to T</math> is surjective, either <math>S</math> and <math>T</math> are both empty, or the composition <math>g\circ h:\N\to T</math> is surjective. In either case <math>T</math> is countable. | For (2) observe that if <math>S</math> is countable, either <math>S</math> is empty or there is a surjective function <math>h:\N\to S</math>. Then if <math>g:S\to T</math> is surjective, either <math>S</math> and <math>T</math> are both empty, or the composition <math>g\circ h:\N\to T</math> is surjective. In either case <math>T</math> is countable. | ||
}} | }} | ||
कैंटर का प्रमेय इस बात पर जोर देता है कि यदि <math>A</math> एक | कैंटर का प्रमेय इस बात पर जोर देता है कि यदि <math>A</math> एक समुच्चय है और <math>\mathcal{P}(A)</math> इसका [[ सत्ता स्थापित ]] है, यानी सभी उपसमुच्चय का समुच्चय <math>A</math>, तो कोई विशेषण फलन नहीं है <math>A</math> को <math>\mathcal{P}(A)</math>. कैंटर के प्रमेय लेख में एक प्रमाण दिया गया है। इसके तत्काल परिणाम और उपरोक्त मूल प्रमेय के रूप में हमारे पास है: | ||
{{math theorem | name = Proposition | math_statement = The set <math>\mathcal{P}(\N)</math> is not countable; i.e. it is [[uncountable]].}} | {{math theorem | name = Proposition | math_statement = The set <math>\mathcal{P}(\N)</math> is not countable; i.e. it is [[uncountable]].}} | ||
| Line 122: | Line 122: | ||
वास्तविक संख्याओं का समुच्चय अगणनीय है,{{efn|See [[Cantor's first uncountability proof]], and also [[Finite intersection property#Applications]] for a topological proof.}} और प्राकृतिक संख्याओं के सभी अनंत [[अनुक्रम]]ों का समुच्चय भी ऐसा ही है। | वास्तविक संख्याओं का समुच्चय अगणनीय है,{{efn|See [[Cantor's first uncountability proof]], and also [[Finite intersection property#Applications]] for a topological proof.}} और प्राकृतिक संख्याओं के सभी अनंत [[अनुक्रम]]ों का समुच्चय भी ऐसा ही है। | ||
== | ==समुच्चय सिद्धांत का न्यूनतम मॉडल गणनीय है== | ||
यदि कोई | यदि कोई समुच्चय है जो ZFC समुच्चय सिद्धांत का एक मा | ||