गणनीय सेट

में गणित , एक गणनीय सेट एक है सेट एक ही साथ प्रमुखता ( संख्या तत्वों के) कुछ के रूप में उप-समूह के सेट की प्राकृतिक संख्या । एक गणनीय समुच्चय या तो एक परिमित समुच्चय है या एक गणनीय अनंत समुच्चय है। चाहे परिमित हो या अनंत, एक गणनीय समुच्चय के तत्वों को हमेशा एक बार में गिना जा सकता है और—यद्यपि गिनती कभी समाप्त नहीं हो सकती—समुच्चय का प्रत्येक अवयव एक अद्वितीय प्राकृतिक संख्या से जुड़ा होता है।

कुछ लेखक गणनीय समुच्चय का उपयोग केवल गणनीय रूप से अनंत के लिए करते हैं। ^[1] इस अस्पष्टता से बचने के लिए, अवधि सबसे गणनीय पर जब परिमित सेट शामिल किए गए हैं इस्तेमाल किया जा सकता है और गणनीय अनंत , गणनीय , ^[2] या denumerable ^[3] अन्यथा।

जॉर्ज कैंटर ने काउंटेबल सेट शब्द की शुरुआत की , इसके विपरीत सेट जो उन लोगों के साथ गणनीय हैं जो बेशुमार हैं (यानी, गैर - संख्यात्मक या गैर - संख्यात्मक ^[4] )। आज, गणनीय समुच्चय गणित की एक शाखा की नींव बनाते हैं जिसे असतत गणित कहा जाता है ।

परिभाषा

एक सेट $एस$ है गणनीय यदि वहां मौजूद एक एकैकी फलन $च$ से $एस$ के लिए प्राकृतिक संख्या $एन = {0, 1, 2, 3, ...$ }। ^{[ उद्धरण वांछित ]}^[5]

यदि ऐसा $f$ पाया जा सकता है जो विशेषण (और इसलिए विशेषण ) भी है, तो $S$ को गणनीय अनंत कहा जाता है ।

दूसरे शब्दों में, एक समुच्चय गणनीय रूप से अनंत होता है यदि उसका प्राकृत संख्या समुच्चय $N के$ साथ एक-से-एक पत्राचार होता है । किस मामले में, सेट की कार्डिनैलिटी को निरूपित किया जाता है $\aleph _{0}$ ( एलेफ-नल ) - एलेफ नंबरों की श्रृंखला में पहला। ^[6]

यह शब्दावली सार्वभौमिक नहीं है। कुछ लेखक गणनीय का उपयोग इसका मतलब यह करने के लिए करते हैं कि यहाँ क्या कहा जाता है, और इसमें परिमित सेट शामिल नहीं हैं।

एक विशेषण फलन या एक विशेषण फलन के संदर्भ में परिभाषा के वैकल्पिक (समतुल्य) सूत्र भी दिए जा सकते हैं। ^[७] यह भी देखें बिना विवरण के औपचारिक अवलोकन ।

इतिहास

1874 में, अपने पहले सेट थ्योरी लेख में , कैंटर ने साबित किया कि वास्तविक संख्याओं का सेट बेशुमार है, इस प्रकार यह दर्शाता है कि सभी अनंत सेट गणनीय नहीं हैं। ^[८] १८७८ में, उन्होंने कार्डिनैलिटी को परिभाषित करने और तुलना करने के लिए एक-से-एक पत्राचार का इस्तेमाल किया। ^[९] १८८३ में, उन्होंने अपने अनंत ऑर्डिनल्स के साथ प्राकृतिक संख्याओं का विस्तार किया , और विभिन्न अनंत कार्डिनैलिटी वाले सेटों के अनंत का उत्पादन करने के लिए ऑर्डिनल्स के सेट का इस्तेमाल किया। ^[10]

परिचय

एक सेट का एक संग्रह है तत्वों , और कई मायनों में वर्णित किया जा सकता है। एक तरीका बस इसके सभी तत्वों को सूचीबद्ध करना है; उदाहरण के लिए, पूर्णांक 3, 4, और 5 वाले समुच्चय को {3, 4, 5} दर्शाया जा सकता है, जिसे रोस्टर रूप कहा जाता है। ^[११] हालांकि, यह केवल छोटे सेटों के लिए प्रभावी है; बड़े सेटों के लिए, यह समय लेने वाला और त्रुटि-प्रवण होगा। प्रत्येक एक तत्व को सूचीबद्ध करने के बजाय, कभी-कभी एक इलिप्सिस ("...") का उपयोग एक सेट में प्रारंभिक तत्व और अंतिम तत्व के बीच कई तत्वों का प्रतिनिधित्व करने के लिए किया जाता है, यदि लेखक का मानना है कि पाठक आसानी से अनुमान लगा सकता है कि क्या ... का प्रतिनिधित्व करता है ; उदाहरण के लिए, {1, 2, 3, ..., 100} संभवतः 1 से 100 तक के पूर्णांकों के समुच्चय को दर्शाता है। हालांकि, इस मामले में भी, सभी तत्वों को सूचीबद्ध करना अभी भी संभव है, क्योंकि इसमें तत्वों की संख्या सेट परिमित है।

कुछ सेट अनंत हैं ; इन सेटों में n से अधिक तत्व होते हैं जहाँ n कोई भी पूर्णांक है जिसे निर्दिष्ट किया जा सकता है। (कोई फर्क नहीं पड़ता कि निर्दिष्ट पूर्णांक n कितना बड़ा है, जैसे कि n = 9 × 10 ³² , अनंत सेट में n से अधिक तत्व होते हैं।) उदाहरण के लिए, प्राकृतिक संख्याओं का सेट, जिसे {0, 1, 2, 3, 4 से दर्शाया जा सकता है। , 5, ...}, में अपरिमित रूप से कई अवयव हैं, और हम इसका आकार देने के लिए किसी प्राकृत संख्या का उपयोग नहीं कर सकते हैं। फिर भी, यह पता चला है कि अनंत सेटों में आकार की एक अच्छी तरह से परिभाषित धारणा होती है (या अधिक ठीक से, कार्डिनैलिटी , एक सेट में तत्वों की संख्या के लिए तकनीकी शब्द), और सभी अनंत सेटों में समान कार्डिनैलिटी नहीं होती है।

पूर्णांक से सम संख्याओं तक विशेषण मानचित्रण

इसका क्या अर्थ है, यह समझने के लिए, हम पहले यह जाँचते हैं कि इसका क्या अर्थ नहीं है। उदाहरण के लिए, अपरिमित रूप से कई विषम पूर्णांक हैं, अपरिमित रूप से कई सम पूर्णांक हैं, और (इसलिए) कुल मिलाकर अपरिमित रूप से कई पूर्णांक हैं। हालांकि, यह पता चला है कि सम पूर्णांकों की संख्या, जो विषम पूर्णांकों की संख्या के समान है, कुल मिलाकर पूर्णांकों की संख्या के समान है। ऐसा इसलिए है क्योंकि हम चीजों को इस तरह व्यवस्थित कर सकते हैं कि प्रत्येक पूर्णांक के लिए एक अलग सम पूर्णांक हो:

\ldots \,-\!2\!\rightarrow \!-\!4,\,-\!1\!\rightarrow \!-\!2,\,0\!\rightarrow \!0, \,1\!\rightarrow \!2,\,2\!\rightarrow \!4\,\ldots

या, अधिक सामान्यतः,

n\rightarrow 2n

(तस्वीर देखो)। हमने यहां जो किया है वह पूर्णांक और सम पूर्णांकों को एक-से-एक पत्राचार (या आक्षेप ) में व्यवस्थित करता है , जो एक ऐसा कार्य है जो दो सेटों के बीच मानचित्र करता है जैसे कि प्रत्येक सेट का प्रत्येक तत्व दूसरे में एक तत्व से मेल खाता है सेट।

हालांकि, सभी अनंत सेटों में समान कार्डिनैलिटी नहीं होती है। उदाहरण के लिए, जॉर्ज कैंटर (जिन्होंने इस अवधारणा को पेश किया) ने प्रदर्शित किया कि वास्तविक संख्याओं को प्राकृतिक संख्याओं (गैर-ऋणात्मक पूर्णांक) के साथ एक-से-एक पत्राचार में नहीं रखा जा सकता है, और इसलिए वास्तविक संख्याओं के सेट की तुलना में अधिक कार्डिनैलिटी है प्राकृतिक संख्याओं का समुच्चय।

एक समुच्चय गणनीय होता है यदि: (१) यह परिमित हो, या (२) इसमें प्राकृतिक संख्याओं के समुच्चय (अर्थात, संख्यात्मक) के समान कार्डिनैलिटी (आकार) हो। ^[१२] समान रूप से, एक समुच्चय गणनीय होता है यदि उसमें प्राकृत संख्याओं के समुच्चय के कुछ उपसमुच्चय के समान कार्डिनैलिटी हो । अन्यथा, यह बेशुमार है ।

विवरण के बिना औपचारिक अवलोकन

परिभाषा के अनुसार, एक सेट एस है गणनीय यदि वहां मौजूद एक एकैकी फलन f : एस → एन से एस के लिए प्राकृतिक संख्या एन = {0, 1, 2, 3, ...}। इसका सीधा सा मतलब है कि S के प्रत्येक तत्व का N के एक अलग तत्व से पत्राचार है ।

सेट को अलग-अलग वर्गों में विभाजित करना स्वाभाविक लग सकता है: एक तत्व वाले सभी सेटों को एक साथ रखें; एक साथ दो तत्वों वाले सभी सेट; ...; अंत में, सभी अनंत सेटों को एक साथ रखें और उन्हें एक ही आकार के रूप में मानें। हालांकि, आकार की प्राकृतिक परिभाषा के तहत यह दृष्टिकोण मान्य नहीं है।

इसे विस्तृत करने के लिए, हमें एक आक्षेप की अवधारणा की आवश्यकता है । यद्यपि एक "आक्षेप" एक संख्या की तुलना में अधिक उन्नत अवधारणा लगता है, सेट सिद्धांत के संदर्भ में गणित का सामान्य विकास संख्याओं से पहले कार्यों को परिभाषित करता है, क्योंकि वे बहुत सरल सेट पर आधारित होते हैं। यह वह जगह है जहां एक आपत्ति की अवधारणा आती है: पत्राचार को परिभाषित करें

ए 1, बी 2, सी ↔ 3

चूँकि { a , b , c } के प्रत्येक अवयव को {1, 2, 3} के ठीक एक अवयव के साथ जोड़ा जाता है , और इसके विपरीत, यह एक द्विभाजन को परिभाषित करता है।

अब हम इस स्थिति का सामान्यीकरण करते हैं; हम परिभाषित करते हैं कि दो सेट एक ही आकार के होते हैं, यदि और केवल यदि उनके बीच एक आक्षेप है। सभी परिमित सेटों के लिए, यह हमें "समान आकार" की सामान्य परिभाषा देता है।

अनंत समुच्चयों के मामले में, समुच्चय A = {1, 2, 3, ...}, धनात्मक पूर्णांकों का समुच्चय , और B = {2, 4, 6, ...}, सम का समुच्चय पर विचार करें। सकारात्मक पूर्णांक। हम दावा करते हैं कि, हमारी परिभाषा के तहत, इन सेटों का आकार समान है, और इसलिए B गणनीय रूप से अनंत है। याद रखें कि इसे साबित करने के लिए हमें उनके बीच एक आपत्ति प्रदर्शित करने की आवश्यकता है। यह असाइनमेंट n ↔ 2 n का उपयोग करके प्राप्त किया जा सकता है , ताकि

1 2, 2 4, 3 6, 4 8, ....

जैसा कि पहले के उदाहरण में, ए के प्रत्येक तत्व को बी के ठीक एक तत्व के साथ जोड़ा गया है, और इसके विपरीत। इसलिए उनका आकार समान है। यह उसी आकार के समुच्चय का एक उदाहरण है जो उसके उचित उपसमुच्चयों में से एक है , जो परिमित समुच्चयों के लिए असंभव है।

इसी तरह, प्राकृतिक संख्याओं के सभी क्रमित युग्मों का समुच्चय (प्राकृतिक संख्याओं के दो सेटों का कार्टेशियन गुणनफल , N × N ) गणनीय रूप से अनंत है, जैसा कि चित्र में दिए गए पथ का अनुसरण करके देखा जा सकता है:

कैंटर आप युग्मन समारोह प्राकृतिक संख्या की प्रत्येक जोड़ी के लिए एक प्राकृतिक नंबर प्रदान करती है

परिणामी मानचित्रण निम्नानुसार आगे बढ़ता है:

0 (0, 0), 1 (1, 0), 2 (0, 1), 3 (2, 0), 4 (1, 1), 5 (0, 2), 6 ↔ (३, ०), ....

इस मैपिंग में ऐसे सभी ऑर्डर किए गए जोड़े शामिल हैं।

एक जोड़ी के रूप में व्यवहार किया जाता है तो अंश और भाजक एक की अभद्र अंश (के रूप में एक अंश एक / ख जहां एक और ख ≠ 0 पूर्णांक हैं), तो हर सकारात्मक अंश के लिए, हम एक अलग प्राकृतिक संख्या इसी के साथ आ सकते हैं इसके लिए। इस निरूपण में प्राकृत संख्याएँ भी शामिल हैं, क्योंकि प्रत्येक प्राकृत संख्या भी भिन्न N /1 होती है। अतः हम यह निष्कर्ष निकाल सकते हैं कि जितने धनात्मक पूर्णांक हैं उतने ही धनात्मक परिमेय संख्याएँ हैं। यह सभी परिमेय संख्याओं के लिए भी सही है, जैसा कि नीचे देखा जा सकता है।

कभी-कभी एक से अधिक मैपिंग उपयोगी होती है: एक सेट ए को गणनीय के रूप में दिखाया जाना एक-से-एक मैप किया जाता है (इंजेक्शन) दूसरे सेट बी के लिए, फिर ए को गिनने योग्य साबित किया जाता है यदि बी एक-से-एक मैप किया जाता है प्राकृतिक संख्या। उदाहरण के लिए, धनात्मक परिमेय संख्याओं के समुच्चय को प्राकृतिक संख्या युग्मों (2-टुपल्स) के समुच्चय में आसानी से एक-से-एक मैप किया जा सकता है क्योंकि p / q मानचित्र ( p , q ) के लिए है। चूंकि प्राकृतिक संख्या युग्मों का सेट एक-से-एक मैप किया गया है (वास्तव में एक-से-एक पत्राचार या आक्षेप) प्राकृतिक संख्याओं के सेट के लिए जैसा कि ऊपर दिखाया गया है, सकारात्मक परिमेय संख्या सेट गणनीय साबित होता है।

प्रमेय: कार्तीय उत्पाद परिमित कई गणनीय सेट की गणनीय है।

त्रिकोणीय मानचित्रण का यह रूप रिकर्सिवली को सामान्यीकृत n - tuples प्राकृतिक संख्या, यानी, (के एक ₁ , एक ₂ , एक ₃ , ..., एक _एन ) जहां एक _मैं और एन प्राकृतिक संख्या है, बार-बार पहले दो तत्वों मैप करके एक प्राकृतिक संख्या के लिए एक n -tuple की। उदाहरण के लिए, (0, 2, 3) को ((0, 2), 3) के रूप में लिखा जा सकता है। फिर (0, 2) 5 को मैप करता है ((0, 2), 3) मैप्स से (5, 3), फिर (5, 3) मैप्स से 39 तक। एक अलग 2-टुपल के बाद से, यह एक जोड़ी है जैसे कि ( ए , बी ), एक अलग प्राकृतिक संख्या के लिए मानचित्र, एक तत्व द्वारा दो एन-टुपल्स के बीच का अंतर यह सुनिश्चित करने के लिए पर्याप्त है कि एन-टुपल्स को विभिन्न प्राकृतिक संख्याओं में मैप किया जा रहा है। अतः, n -टुपल्स के समुच्चय से प्राकृत संख्या N के समुच्चय में एक इंजेक्शन सिद्ध होता है। कई अलग-अलग सेटों के कार्टेशियन उत्पाद द्वारा बनाए गए एन-टुपल्स के सेट के लिए, प्रत्येक ट्यूपल में प्रत्येक तत्व में एक प्राकृतिक संख्या के अनुरूप होता है, इसलिए प्रत्येक टपल को प्राकृतिक संख्याओं में लिखा जा सकता है, फिर प्रमेय को साबित करने के लिए एक ही तर्क लागू किया जाता है। .

निम्नलिखित प्रमेय अनगिनत अनंत सेटों के अनंत उपसमुच्चय से संबंधित है।

प्रमेय: गणनीय समुच्चय का प्रत्येक उपसमुच्चय गणनीय होता है। विशेष रूप से, एक अनंत अनंत सेट का प्रत्येक अनंत उपसमुच्चय गणनीय रूप से अनंत है। ^[13]

उदाहरण के लिए, n -वें अभाज्य संख्या को n में मैप करके, अभाज्य संख्याओं का समुच्चय गणनीय है :

2 नक्शे से 1
३ नक्शे से २
५ नक्शे से ३
७ नक्शे से ४
११ नक्शे से ५
१३ नक्शे से ६
१७ नक्शे से ७
19 नक्शे से 8
२३ नक्शे से ९
...

ऐसे सेट भी हैं जो " N से स्वाभाविक रूप से बड़े" हैं । उदाहरण के लिए, Z सभी पूर्णांकों का समुच्चय या Q , सभी परिमेय संख्याओं का समुच्चय , जो सहज रूप से N से बहुत बड़ा लग सकता है । लेकिन लगता है धोखा हो सकता है, क्योंकि हम दावा करते हैं:

प्रमेय: Z (सभी पूर्णांकों का समुच्चय) और Q (सभी परिमेय संख्याओं का समुच्चय) गणनीय हैं।

इसी प्रकार, बीजीय संख्याओं का समुच्चय गणनीय होता है। ^[14]

ये तथ्य आसानी से इस परिणाम से अनुसरण करते हैं कि बहुत से व्यक्ति गैर-सहज ज्ञान युक्त होते हैं।

प्रमेय: गणनीय समुच्चयों का कोई भी परिमित संघ गणनीय होता है।

यह जानने की दूरदर्शिता के साथ कि बेशुमार समुच्चय हैं, हम सोच सकते हैं कि इस अंतिम परिणाम को और आगे बढ़ाया जा सकता है या नहीं। उत्तर "हां" और "नहीं" है, हम इसे बढ़ा सकते हैं, लेकिन हमें ऐसा करने के लिए एक नया स्वयंसिद्ध ग्रहण करने की आवश्यकता है।

प्रमेय: ( गणनीय पसंद के स्वयंसिद्ध मानते हुए ) कई गणनीय सेटों का संघ गणनीय है।

उदाहरण के लिए, दिए गए गणनीय समुच्चय a , b , c , ...

गणनीय सेटों की गणनीय संख्या के लिए गणना

त्रिकोणीय गणना के एक प्रकार का उपयोग करके हमने ऊपर देखा:

a ₀ मानचित्र से 0 . तक
a ₁ मानचित्र से 1
बी ₀ मानचित्र से 2
ए ₂ मैप्स टू 3
ख ₁ मानचित्र से 4
सी ₀ मानचित्र से 5
a _३ नक्शे से ६
बी ₂ नक्शे से 7
c _१ मानचित्र से ८
d ₀ मानचित्र से 9 . तक
a _४ नक्शे से १०
...

यह केवल तभी कार्य करता है जब समुच्चय a , b , c , ... असंयुक्त हों । यदि नहीं, तो संघ और भी छोटा है और इसलिए पिछले प्रमेय द्वारा भी गिना जा सकता है।

हमें सभी समुच्चयों a , b , c , ... को एक साथ अनुक्रमित करने के लिए गणनीय विकल्प के अभिगृहीत की आवश्यकता है ।

प्रमेय: प्राकृत संख्याओं के सभी परिमित-लंबाई अनुक्रमों का समुच्चय गणनीय होता है।

यह सेट लंबाई -1 अनुक्रमों, लंबाई -2 अनुक्रमों, लंबाई -3 अनुक्रमों का संघ है, जिनमें से प्रत्येक एक गणनीय सेट (परिमित कार्टेशियन उत्पाद) है। तो हम गणनीय समुच्चयों के एक गणनीय संघ के बारे में बात कर रहे हैं, जो पिछले प्रमेय द्वारा गिनने योग्य है।

प्रमेय: प्राकृत संख्याओं के सभी परिमित उपसमुच्चयों का समुच्चय गणनीय होता है।

किसी भी परिमित उपसमुच्चय के तत्वों को एक परिमित अनुक्रम में क्रमबद्ध किया जा सकता है। केवल बहुत से परिमित अनुक्रम हैं, इसलिए भी केवल कई परिमित उपसमुच्चय हैं।

निम्नलिखित प्रमेय एक विशेषण फलन या एक विशेषण फलन के संदर्भ में समकक्ष सूत्रीकरण देता है । इस परिणाम का प्रमाण लैंग के पाठ में पाया जा सकता है। ^[३]

(मूल) प्रमेय: मान लीजिए S एक समुच्चय है। निम्न कथन समतुल्य हैं:

एस गणनीय है, यानी वहां मौजूद एक एकैकी फलन f : एस → एन ।
या तो S खाली है या एक विशेषण फलन मौजूद है g : N → S ।
या तो S परिमित है या वहाँ एक द्विभाजन h : N → S मौजूद है ।

उपफल: मान लीजिए S और T समुच्चय हैं।

यदि फलन f : S → T इंजेक्टिव है और T काउंटेबल है तो S काउंटेबल है।
यदि फलन g : S → T विशेषण है और S गणनीय है तो T गणनीय है।

कैंटर की प्रमेय का दावा है कि यदि ए एक सेट है और पी ( ए ) इसका पावर सेट है , यानी ए के सभी सबसेट का सेट है, तो ए से पी ( ए )तक कोई विशेषण कार्य नहीं है। लेख कैंटोर के प्रमेय में एक प्रमाण दिया गया है । इसके तत्काल परिणाम और उपरोक्त मूल प्रमेय के रूप में हमारे पास है:

प्रस्ताव: समुच्चय P ( N ) गणनीय नहीं है; यानी यह बेशुमार है ।

इस परिणाम के विस्तार के लिए कैंटर का विकर्ण तर्क देखें ।

वास्तविक संख्याओं का सेट बेशुमार है ( कैंटोर का पहला बेशुमार प्रमाण देखें ), और ऐसा ही प्राकृतिक संख्याओं के सभी अनंत अनुक्रमों का सेट है ।

कुछ तकनीकी विवरण

उपरोक्त खंड में बयानों के प्रमाण कुछ गुणों के साथ कार्यों के अस्तित्व पर निर्भर करते हैं। यह खंड आमतौर पर इस भूमिका में उपयोग किए जाने वाले कार्यों को प्रस्तुत करता है, लेकिन यह पुष्टि नहीं करता है कि इन कार्यों में आवश्यक गुण हैं। मूल प्रमेय और उसके उपफल का उपयोग अक्सर प्रमाणों को सरल बनाने के लिए किया जाता है। ध्यान दें कि उस प्रमेय में $N$ को किसी भी अनंत अनंत सेट से बदला जा सकता है।

प्रस्ताव: कोई भी परिमित समुच्चय गणनीय होता है।

उपपत्ति : मान लीजिए $S$ ऐसा समुच्चय है। दो मामलों पर विचार किया जाना है: या तो $S$ खाली है या नहीं। 1.) रिक्त समुच्चय सम ही प्राकृत संख्याओं का उपसमुच्चय है, इसलिए यह गणनीय है। 2.) यदि $S$ अरिक्त और परिमित है, तो परिमितता की परिभाषा के अनुसार $S$ और समुच्चय {1, 2, ..., $n$ } के बीच किसी धनात्मक प्राकृत संख्या $n के$ लिए एक द्विभाजन होता है । यह फ़ंक्शन $S$ से $N$ में एक इंजेक्शन है ।

प्रस्ताव: गणनीय समुच्चय का कोई भी उपसमुच्चय गणनीय होता है। ^[15]

सबूत: एक इंजेक्शन फ़ंक्शन का अपने डोमेन के सबसेट के लिए प्रतिबंध अभी भी इंजेक्शन है।

प्रस्ताव: यदि $S$ एक गणनीय समुच्चय है तो $S {x$ } गणनीय है। ^[16]

उपपत्ति: यदि $x S$ दिखाने के लिए कुछ नहीं है। अन्यथा मान लीजिए $f : S \to N$ एक इंजेक्शन है। $g : S {x} \to N$ को $g (x) = 0$ और $g (y) = f (y) + 1$ द्वारा $S$ में सभी $y के$ लिए परिभाषित करें । यह फ़ंक्शन $g$ एक इंजेक्शन है।

प्रस्ताव: तो $एक$ और $बी$ गणनीय सेट हैं तो $एक \cup बी$ गणनीय है। ^[17]

प्रमाण: मान लीजिए $f : A \to N$ और $g : B \to N$ इंजेक्शन हैं। एक नया इंजेक्शन परिभाषित $ज : एक \cup बी \to एन$ से $ज (एक्स) = 2 च (एक्स)$ यदि $एक्स$ में है $एक$ और $ज (एक्स) = 2 जी (x) + 1$ यदि $एक्स$ में है $बी$ लेकिन नहीं में $एक$ ।

प्रस्ताव: कार्तीय उत्पाद दो गणनीय सेट की $एक$ और $बी$ गणनीय है। ^[18]

प्रमाण: निरीक्षण करें कि $N \times N$ परिभाषा के परिणाम के रूप में गणनीय है क्योंकि $f$ $($ $m$ $,$ $n$ $) = 2$ $m$ $3$ $n$ द्वारा दिया गया फलन $f : N \times N \to N$ इंजेक्शन है। ^[१९] इसके बाद मूल प्रमेय और उपपत्ति से यह निष्कर्ष निकलता है कि किन्हीं दो गणनीय समुच्चयों का कार्तीय गुणनफल गणनीय होता है। यह इस प्रकार है क्योंकि यदि $A$ और $B$ गणनीय हैं तो वहाँ अनुमान $f$ $:$ $N$ $\to$ $A$ और $g$ $:$ $N$ $\to$ $B हैं$ । इसलिए

एफ \times जी : एन \times एन \to ए \times बी

गणनीय समुच्चय $N \times N$ से समुच्चय $A \times B पर$ $एक$ आक्षेप है और उपफल का अर्थ है कि $A$ $\times$ $B$ गणनीय है। यह परिणाम गणनीय सेटों के किसी भी परिमित संग्रह के कार्टेशियन उत्पाद को सामान्यीकृत करता है और संग्रह में सेटों की संख्या पर प्रेरण द्वारा प्रमाण का अनुसरण करता है।

प्रस्ताव: पूर्णांकों $जेड$ गणनीय हैं और तर्कसंगत संख्याओं $क्यू$ गणनीय हैं।

सबूत: पूर्णांकों $जेड$ गणनीय रहे हैं, क्योंकि समारोह $च : जेड \to एन$ द्वारा दिए गए $च (एन) = 2 n$ यदि $n$ गैर नकारात्मक और है $च (एन) = 3 - n$ यदि $n$ नकारात्मक है, एक एकैकी फलन है। परिमेय संख्याएँ $Q$ गणनीय हैं क्योंकि $g$ $($ $m$ $,$ $n$ $) =$ $m$ $/($ $n$ $+ 1)$ द्वारा दिया गया फलन $g : Z \times N \to Q$ गणनीय समुच्चय $Z$ $\times$ $N$ से परिमेय $Q पर$ एक आक्षेप है ।

प्रस्ताव: बीजीय संख्या $एक$ गणनीय हैं।

प्रमाण: परिभाषा के अनुसार, प्रत्येक बीजीय संख्या (सम्मिलित संख्याओं सहित) पूर्णांक गुणांक वाले बहुपद का मूल है। एक बीजीय संख्या दी गई है $\alpha$ , चलो $a_{0}x^{0}+a_{1}x^{1}+a_{2}x^{2}+\cdots +a_{n}x^{n}$ पूर्णांक गुणांकों वाला एक बहुपद हो जैसे कि $\alpha$ है कश्मीर बहुपद, जहां जड़ों बड़ा करने के लिए छोटे से निरपेक्ष मान द्वारा हल कर रहे हैं की वें जड़ है, तो बड़ा करने के लिए छोटे से तर्क के अनुसार क्रमबद्ध। हम एक इंजेक्शन (यानी एक-से-एक) फ़ंक्शन को परिभाषित कर सकते हैं $f : A \to Q$ द्वारा दिया गया $f(\alpha )=2^{k-1}\cdot 3^{a_{0}}\cdot 5^{a_{1}}\cdot 7^{a_{2}}\cdots {p_ {n+2}}^{a_{n}}$ , जबकि $p_{n}$ है n वें प्रधानमंत्री ।

प्रस्ताव: यदि $एक एन$ प्रत्येक के लिए एक गणनीय सेट है $n$ में $एन$ तो सभी का मिलन $एक n$ भी गणनीय है। ^[20]

उपपत्ति: यह इस तथ्य का परिणाम है कि प्रत्येक $n के$ लिए एक विशेषण फलन $होता है g n : N \to A n$ और इसलिए फलन

G:\mathbf {N} \times \mathbf {N} \to \bigcup _{n\in \mathbf {N} }A_{n},

$G (n, m) = g n (m)$ द्वारा दिया गया एक आक्षेप है। चूँकि $N \times N$ गणनीय है, इसलिए कोरोलरी का अर्थ है कि संघ गणनीय है। हम का उपयोग गणनीय पसंद का स्वयंसिद्ध इस सबूत में से प्रत्येक के लिए लेने के लिए $एन$ में $एन$ एक surjection $जी एन$ से surjections की गैर खाली संग्रह से $एन$ के लिए $एक n$ ।

वास्तविक संख्याओं की बेशुमारता के लिए एक टोपोलॉजिकल सबूत परिमित चौराहे संपत्ति पर वर्णित है ।

सेट सिद्धांत का न्यूनतम मॉडल गणनीय है

यदि कोई सेट है जो ZFC सेट सिद्धांत का एक मानक मॉडल ( आंतरिक मॉडल देखें ) है, तो एक न्यूनतम मानक मॉडल है ( कंस्ट्रक्टेबल ब्रह्मांड देखें )। Löwenheim-Skolem प्रमेय पता चलता है कि इस कम से कम मॉडल गणनीय है इस्तेमाल किया जा सकता। तथ्य यह है कि "बेशुमारता" की धारणा इस मॉडल में भी समझ में आती है, और विशेष रूप से इस मॉडल एम में ऐसे तत्व शामिल हैं जो हैं:

M के उपसमुच्चय , इसलिए गणनीय,
लेकिन एम के दृष्टिकोण से बेशुमार ,

सेट थ्योरी के शुरुआती दिनों में विरोधाभास के रूप में देखा गया था, अधिक के लिए स्कोलेम का विरोधाभास देखें ।

न्यूनतम मानक मॉडल में सभी बीजीय संख्याएं और सभी प्रभावी रूप से गणना योग्य अनुवांशिक संख्याएं , साथ ही साथ कई अन्य प्रकार की संख्याएं शामिल हैं।

कुल आदेश

गणनीय सेटों को पूरी तरह से विभिन्न तरीकों से ऑर्डर किया जा सकता है, उदाहरण के लिए:

अच्छी तरह से आदेश ( क्रमिक संख्या भी देखें ):
- प्राकृत संख्याओं का सामान्य क्रम (0, 1, 2, 3, 4, 5, ...)
- क्रम में पूर्णांक (0, 1, 2, 3, ...; −1, −2, −3, ...)
अन्य ( अच्छी तरह से आदेश नहीं ):
- पूर्णांकों का सामान्य क्रम (..., −3, −2, −1, 0, 1, 2, 3, ...)
- परिमेय संख्याओं का सामान्य क्रम (एक आदेशित सूची के रूप में स्पष्ट रूप से नहीं लिखा जा सकता है!)

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

यह सभी देखें

अलेफ नंबर
गिनती
हिल्बर्ट का ग्रैंड होटल का विरोधाभास
बेशुमार सेट

^ रुडिन 1976 , अध्याय 2
^ कामके १९५० , पृ. 2
^ ए बी लैंग 1993 , अध्याय I का .2 of
^ अपोस्टोल १९६९ , अध्याय १३.१ ९
^ चूंकि $एन$ और $एन$ $* = {1, 2, 3, ...$ } केबीचएक स्पष्ट विभाजन है , इससे कोई फर्क नहीं पड़ता कि कोई 0 को प्राकृतिक संख्या मानता है या नहीं। किसी भी मामले में, यह आलेख आईएसओ 31-11 और गणितीय तर्क में मानक सम्मेलन का पालन करता है , जो 0 को प्राकृतिक संख्या के रूप में लेता है।
^ "सेट थ्योरी सिंबल की व्यापक सूची" । मठ तिजोरी । 2020-04-11 । 2020-09-06 को लिया गया ।
^ हल्मोस १९६० , पृ. ९१, $एस को$ गणनीयकहते हैंयदि $एस$ और एन के सबसेट के बीच एक विशेषण मानचित्रणमौजूद है। कामके १९५० , पृ. 2, $S$ और N के बीच एक विशेषण मानचित्रण की आवश्यकता है।
^ स्टिलवेल, जॉन सी. (2010), रोड्स टू इन्फिनिटी: द मैथमेटिक्स ऑफ ट्रुथ एंड प्रूफ , सीआरसी प्रेस, पी. 10, आईएसबीएन 9781439865507, 1874 में कैंटर की बेशुमार सेटों की खोज गणित के इतिहास की सबसे अप्रत्याशित घटनाओं में से एक थी। १८७४ से पहले, अधिकांश लोगों द्वारा अनंत को एक वैध गणितीय विषय भी नहीं माना जाता था, इसलिए गणनीय और बेशुमार अनंत के बीच अंतर करने की आवश्यकता की कल्पना नहीं की जा सकती थी।
^ कैंटर १८७८, पृ. २४२.
^ फेरेइरोस २००७, पीपी २६८, २७२-२७३.
^ "सेट और रोस्टर फॉर्म क्या हैं?" . expii । 2021-05-09।
^ वीसस्टीन, एरिक डब्ल्यू। "काउंटेबल सेट" । मैथवर्ल्ड.वोल्फ्राम.कॉम । 2020-09-06 को लिया गया ।
^ "9.2: गणनीय सेट" । गणित लिब्रेटेक्स । 2017-09-20 । 2020-09-06 को लिया गया ।
^ Kamke 1950 , पृ। 3-4
^ हल्मोस १९६० , पृ. ९१
^ अवेल्सगार्ड १९९० , पृ. १७९
^ अवेल्सगार्ड १९९० , पृ. 180
^ हल्मोस १९६० , पृ. 92
^ अवेल्सगार्ड १९९० , पृ. १८२
^ फ्लेचर और पैटी 1988 , पृ. १८७

संदर्भ

अपोस्टोल, टॉम एम. (जून 1969), मल्टी-वेरिएबल कैलकुलस एंड लीनियर अलजेब्रा विद एप्लिकेशन , कैलकुलस, 2 (दूसरा संस्करण), न्यूयॉर्क: जॉन विले + संस, आईएसबीएन 978-0-471-00007-5
एवेल्सगार्ड, कैरल (1990), फ़ाउंडेशन फ़ॉर एडवांस्ड मैथमैटिक्स , स्कॉट, फ़ॉर्समैन एंड कंपनी, ISBN 0-673-38152-8
कैंटर, जॉर्ज (१८७८), "ऐन बेइट्रैग ज़ूर मैनिगफ़ल्टिगकेइट्सलेहर" , जर्नल फर डाई रेइन एंड एंजवेन्टे गणित , १८७८ (८४): २४२-२४८, दोई : १०.१५१५/क्रेल-१८७८-१८७८८४१३
फेरेइरोस, जोस (2007), लेबिरिंथ ऑफ थॉट: ए हिस्ट्री ऑफ सेट थ्योरी एंड इट्स रोल इन मैथमैटिकल थॉट (दूसरा संशोधित संस्करण), बिरखौसर, आईएसबीएन 978-3-7643-8349-7
फ्लेचर, पीटर; पैटी, सी. वेन (1988), फ़ाउंडेशन ऑफ़ हायर मैथमेटिक्स , बोस्टन: PWS-KENT पब्लिशिंग कंपनी, ISBN 0-87150-164-3
हल्मोस, पॉल आर. (1960), नाइव सेट थ्योरी , डी. वैन नोस्ट्रैंड कंपनी, इंक स्प्रिंगर-वेरलाग, न्यूयॉर्क, 1974 द्वारा पुनर्मुद्रित। ISBN 0-387-90092-6 (स्प्रिंगर-वेरलाग संस्करण)। मार्टिनो फाइन बुक्स, 2011 द्वारा पुनर्मुद्रित। आईएसबीएन 978-1-61427-131-4 (पेपरबैक संस्करण)।
कामके, एरिच (1950), थ्योरी ऑफ सेट्स , डोवर सीरीज इन मैथमेटिक्स एंड फिजिक्स, न्यूयॉर्क: डोवर, आईएसबीएन ९७८-०४८६६०१४१०
लैंग, सर्ज (1993), रियल एंड फंक्शनल एनालिसिस , बर्लिन, न्यूयॉर्क: स्प्रिंगर-वेरलाग, ISBN 0-387-94001-4
रुडिन, वाल्टर (1976), गणितीय विश्लेषण के सिद्धांत , न्यूयॉर्क: मैकग्रा-हिल, ISBN 0-07-054235-X

[Rudin-1] रुडिन 1976 , अध्याय 2

[2] कामके १९५० , पृ. 2

[Lang-3] ए बी लैंग 1993 , अध्याय I का .2 of

[Apostol-4] अपोस्टोल १९६९ , अध्याय १३.१ ९

[5] चूंकि $एन$ और $एन$ $* = {1, 2, 3, ...$ } केबीचएक स्पष्ट विभाजन है , इससे कोई फर्क नहीं पड़ता कि कोई 0 को प्राकृतिक संख्या मानता है या नहीं। किसी भी मामले में, यह आलेख आईएसओ 31-11 और गणितीय तर्क में मानक सम्मेलन का पालन करता है , जो 0 को प्राकृतिक संख्या के रूप में लेता है।

[6] "सेट थ्योरी सिंबल की व्यापक सूची" । मठ तिजोरी । 2020-04-11 । 2020-09-06 को लिया गया ।

[7] हल्मोस १९६० , पृ. ९१, $एस को$ गणनीयकहते हैंयदि $एस$ और एन के सबसेट के बीच एक विशेषण मानचित्रणमौजूद है। कामके १९५० , पृ. 2, $S$ और N के बीच एक विशेषण मानचित्रण की आवश्यकता है।

[8] स्टिलवेल, जॉन सी. (2010), रोड्स टू इन्फिनिटी: द मैथमेटिक्स ऑफ ट्रुथ एंड प्रूफ , सीआरसी प्रेस, पी. 10, आईएसबीएन 9781439865507, 1874 में कैंटर की बेशुमार सेटों की खोज गणित के इतिहास की सबसे अप्रत्याशित घटनाओं में से एक थी। १८७४ से पहले, अधिकांश लोगों द्वारा अनंत को एक वैध गणितीय विषय भी नहीं माना जाता था, इसलिए गणनीय और बेशुमार अनंत के बीच अंतर करने की आवश्यकता की कल्पना नहीं की जा सकती थी।

[9] कैंटर १८७८, पृ. २४२.

[10] फेरेइरोस २००७, पीपी २६८, २७२-२७३.

[11] "सेट और रोस्टर फॉर्म क्या हैं?" . expii । 2021-05-09।

[12] वीसस्टीन, एरिक डब्ल्यू। "काउंटेबल सेट" । मैथवर्ल्ड.वोल्फ्राम.कॉम । 2020-09-06 को लिया गया ।

[13] "9.2: गणनीय सेट" । गणित लिब्रेटेक्स । 2017-09-20 । 2020-09-06 को लिया गया ।

[14] Kamke 1950 , पृ। 3-4

[15] हल्मोस १९६० , पृ. ९१

[16] अवेल्सगार्ड १९९० , पृ. १७९

[17] अवेल्सगार्ड १९९० , पृ. 180

[18] हल्मोस १९६० , पृ. 92

[19] अवेल्सगार्ड १९९० , पृ. १८२

[20] फ्लेचर और पैटी 1988 , पृ. १८७

[1]