कॉम्पैक्टनेस प्रमेय

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

प्रस्तावक गणना के लिए कॉम्पैक्टनेस प्रमेय टाइकोनॉफ़ के प्रमेय का परिणाम है (जो कहता है कि कॉम्पैक्ट जगह का उत्पाद टोपोलॉजी कॉम्पैक्ट है) कॉम्पैक्ट पत्थर की जगह पर लागू होता है, इसलिए प्रमेय का नाम। इसी तरह, यह टोपोलॉजिकल स्पेस में कॉम्पैक्टनेस के परिमित चौराहे की विशेषता के अनुरूप है: एक कॉम्पैक्ट स्पेस में बंद सेट के संग्रह में एक खाली सेट होता है। गैर-रिक्त चौराहा (सेट सिद्धांत) यदि प्रत्येक परिमित उपसंहार में एक गैर-खाली चौराहा होता है।

कॉम्पैक्टनेस प्रमेय दो प्रमुख गुणों में से एक है, साथ ही डाउनवर्ड लोवेनहेम-स्कोलेम प्रमेय, जिसका उपयोग लिंडस्ट्रॉम के प्रमेय में प्रथम-क्रम तर्क को चिह्नित करने के लिए किया जाता है। हालांकि कॉम्पैक्टनेस प्रमेय के गैर-प्रथम-क्रम लॉजिक्स के लिए कुछ सामान्यीकरण हैं, बहुत सीमित संख्या में उदाहरणों को छोड़कर, कॉम्पैक्टनेस प्रमेय स्वयं उनमें नहीं है।

इतिहास

कर्ट गोडेल ने 1930 में काउंटेबल कॉम्पैक्टनेस प्रमेय को साबित किया। अनातोली माल्टसेव ने 1936 में बेशुमार मामले को साबित किया।

अनुप्रयोग

कॉम्पैक्टनेस प्रमेय के मॉडल सिद्धांत में कई अनुप्रयोग हैं; कुछ विशिष्ट परिणाम यहाँ दर्शाए गए हैं।

रॉबिन्सन का सिद्धांत

कॉम्पैक्टनेस प्रमेय का तात्पर्य निम्नलिखित परिणाम से है, जिसे अब्राहम रॉबिन्सन ने अपने 1949 के शोध प्रबंध में कहा था।

रॉबिन्सन का सिद्धांत: यदि प्रथम-क्रम का वाक्य विशेषता (बीजगणित) के प्रत्येक क्षेत्र (गणित) में शून्य रखता है, तो एक स्थिरांक मौजूद होता है $p$ ऐसा है कि वाक्य विशेषता के हर क्षेत्र से बड़ा है $p.$ इसे इस प्रकार देखा जा सकता है: मान लीजिए $\varphi$ एक ऐसा वाक्य है जो विशेषता शून्य के प्रत्येक क्षेत्र में धारण करता है। फिर उसका निषेध $\lnot \varphi ,$ एक साथ क्षेत्र के स्वयंसिद्ध और वाक्यों के अनंत क्रम के साथ

$$1+1\neq 0,\;\;1+1+1\neq 0,\;\ldots$$

संतुष्टि नहीं है (क्योंकि विशेषता 0 का कोई क्षेत्र नहीं है जिसमें $\lnot \varphi$ धारण करता है, और वाक्यों का अनंत अनुक्रम सुनिश्चित करता है कि कोई भी मॉडल विशेषता 0 का क्षेत्र होगा)। इसलिए, एक परिमित उपसमुच्चय है $A$ इन वाक्यों में से जो संतोषजनक नहीं है। $A$ शामिल होना चाहिए $\lnot \varphi$ क्योंकि अन्यथा यह संतोषजनक होगा। क्योंकि इसमें और वाक्य जोड़े जा रहे हैं $A$ असंतोष नहीं बदलता है, हम यह मान सकते हैं $A$ कुछ के लिए फ़ील्ड स्वयंसिद्ध और, शामिल हैं $k,$ पहला $k$ रूप के वाक्य $1+1+\cdots +1\neq 0.$ होने देना $B$ के सभी वाक्य शामिल हैं $A$ के अलावा $\lnot \varphi .$ फिर से अधिक विशेषता वाला कोई भी क्षेत्र $k$ का एक मॉडल है $B,$ और $\lnot \varphi$ के साथ साथ $B$ संतोषप्रद नहीं है। इस का मतलब है कि $\varphi$ के हर मॉडल में धारण करना चाहिए $B,$ जिसका अर्थ ठीक यही है $\varphi$ से अधिक विशेषता के हर क्षेत्र में रखती है $k.$ यह प्रमाण को पूरा करता है।

स्थानांतरण सिद्धांत के पहले उदाहरणों में से एक, लेफ्शेट्ज़ सिद्धांत, इस परिणाम का विस्तार करता है। प्रथम श्रेणी का वाक्य $\varphi$ रिंग (गणित) की भाषा में सत्य है some (या समकक्ष, में every) विशेषता 0 के बीजगणितीय रूप से बंद क्षेत्र (जैसे कि उदाहरण के लिए जटिल संख्याएं) अगर और केवल अगर असीम रूप से कई अभाज्य मौजूद हैं $p$ जिसके लिए $\varphi$ में सत्य है some विशेषता के बीजगणितीय रूप से बंद क्षेत्र $p,$ कौनसे मामलेमें $\varphi$ में सत्य है all पर्याप्त रूप से बड़े गैर-0 विशेषता वाले बीजगणितीय रूप से बंद क्षेत्र $p.$ एक परिणाम एक्स-ग्रोथेंडिक प्रमेय का निम्नलिखित विशेष मामला है: सभी अंतःक्षेपी नक्शा सम्मिश्र संख्या बहुपद $\mathbb {C} ^{n}\to \mathbb {C} ^{n}$ विशेषण मानचित्र हैं (वास्तव में, यह भी दिखाया जा सकता है कि इसका व्युत्क्रम भी एक बहुपद होगा)। वास्तव में, किसी भी अंतःक्षेपी बहुपद के लिए आक्षेपकता निष्कर्ष सही रहता है $F^{n}\to F^{n}$ कहां $F$ एक परिमित क्षेत्र या ऐसे क्षेत्र का बीजगणितीय समापन है।

ऊपर की ओर लोवेनहेम-स्कोलेम प्रमेय

कॉम्पैक्टनेस प्रमेय का एक दूसरा अनुप्रयोग दर्शाता है कि कोई भी सिद्धांत जिसमें मनमाने ढंग से बड़े परिमित मॉडल हैं, या एक अनंत मॉडल है, में मनमाने ढंग से बड़े प्रमुखता के मॉडल हैं (यह अपवर्ड लोवेनहेम-स्कोलेम प्रमेय है)। उदाहरण के लिए, पीनो अंकगणित के गैर-मानक मॉडल हैं जिनमें अनगिनत 'प्राकृतिक संख्याएं' हैं। इसे प्राप्त करने के लिए, चलो $T$ प्रारंभिक सिद्धांत हो और चलो $\kappa$ कोई भी बुनियादी संख्या हो। की भाषा में जोड़ें $T$ के प्रत्येक तत्व के लिए एक स्थिर प्रतीक $\kappa .$ फिर जोड़ें $T$ वाक्यों का एक संग्रह जो कहता है कि नए संग्रह से किन्हीं दो अलग-अलग स्थिर प्रतीकों द्वारा दर्शाई गई वस्तुएँ अलग हैं (यह एक संग्रह है $\kappa ^{2}$ वाक्य)। चूंकि प्रत्येक finite इस नए सिद्धांत का सबसेट पर्याप्त रूप से बड़े परिमित मॉडल द्वारा संतुष्ट है $T,$ या किसी अनंत मॉडल द्वारा, संपूर्ण विस्तारित सिद्धांत संतोषजनक है। लेकिन विस्तारित सिद्धांत के किसी भी मॉडल में कम से कम कार्डिनैलिटी होती है $\kappa$.

अमानक विश्लेषण

कॉम्पैक्टनेस प्रमेय का एक तीसरा अनुप्रयोग वास्तविक संख्याओं के गैर-मानक विश्लेषण का निर्माण है, जो कि वास्तविक संख्याओं के सिद्धांत का निरंतर विस्तार है जिसमें अपरिमेय संख्याएँ होती हैं। इसे देखने के लिए, आइए $\Sigma$ वास्तविक संख्याओं के सिद्धांत का प्रथम-क्रम स्वयंसिद्ध होना। एक नया अचर प्रतीक जोड़कर प्राप्त सिद्धांत पर विचार करें $\varepsilon$ भाषा और उससे सटे $\Sigma$ स्वयंसिद्ध $\varepsilon >0$ और स्वयंसिद्ध $\varepsilon <{\tfrac {1}{n}}$ सभी सकारात्मक पूर्णांकों के लिए $n.$ स्पष्ट रूप से, मानक वास्तविक संख्याएँ $\mathbb {R}$ इन स्वयंसिद्धों के प्रत्येक परिमित उपसमुच्चय के लिए एक मॉडल हैं, क्योंकि वास्तविक संख्याएँ सभी को संतुष्ट करती हैं $\Sigma$ और, उपयुक्त विकल्प द्वारा $\varepsilon ,$ के बारे में स्वयंसिद्धों के किसी परिमित उपसमुच्चय को संतुष्ट करने के लिए बनाया जा सकता है $\varepsilon .$ कॉम्पैक्टनेस प्रमेय द्वारा, एक मॉडल है ${}^{*}\mathbb {R}$ जो संतुष्ट करता है $\Sigma$ और इसमें एक अतिसूक्ष्म तत्व भी होता है $\varepsilon .$ इसी तरह का तर्क, इस बार स्वयंसिद्धों से जुड़ा हुआ है $\omega >0,\;\omega >1,\ldots ,$ आदि से पता चलता है कि असीम रूप से बड़े परिमाण के साथ संख्याओं के अस्तित्व को किसी भी स्वयंसिद्धता से इंकार नहीं किया जा सकता है $\Sigma$ असली का। यह दिखाया जा सकता है कि अति वास्तविक संख्या ${}^{*}\mathbb {R}$ स्थानांतरण सिद्धांत को संतुष्ट करें: पहले क्रम का वाक्य सत्य है $\mathbb {R}$ अगर और केवल अगर यह सच है ${}^{*}\mathbb {R} .$

प्रमाण

गोडेल की पूर्णता प्रमेय का उपयोग करके कॉम्पैक्टनेस प्रमेय को सिद्ध किया जा सकता है, जो यह स्थापित करता है कि वाक्यों का एक सेट संतोषजनक है अगर और केवल अगर इससे कोई विरोधाभास सिद्ध नहीं किया जा सकता है। चूंकि सबूत हमेशा परिमित होते हैं और इसलिए दिए गए वाक्यों में से केवल बहुत ही सूक्ष्म रूप से शामिल होते हैं, कॉम्पैक्टनेस प्रमेय का पालन होता है। वास्तव में, कॉम्पैक्टनेस प्रमेय गोडेल की पूर्णता प्रमेय के बराबर है, और दोनों बूलियन प्रधान आदर्श प्रमेय के बराबर हैं, पसंद के स्वयंसिद्ध का एक कमजोर रूप। गोडेल ने मूल रूप से सघनता प्रमेय को इसी तरह से सिद्ध किया था, लेकिन बाद में सघनता प्रमेय के कुछ विशुद्ध अर्थ संबंधी प्रमाण पाए गए; अर्थात्, ऐसे प्रमाण जो संदर्भित करते हैं truth लेकिन नहीं provability. उन प्रमाणों में से एक ultraproduct्स पर निर्भर करता है जो पसंद के स्वयंसिद्ध पर निर्भर करता है:

सबूत: पहले क्रम की भाषा को ठीक करें $L,$ और जाने $\Sigma$ एल-वाक्यों का एक संग्रह हो जैसे कि हर परिमित उपसंग्रह $L$-वाक्य, $i\subseteq \Sigma$ इसका एक मॉडल है ${\mathcal {M}}_{i}.$ भी जाने दो ${\textstyle \prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}}$ संरचनाओं का प्रत्यक्ष उत्पाद हो और $I$ के परिमित उपसमूहों का संग्रह हो $\Sigma .$ प्रत्येक के लिए $i\in I,$ होने देना $A_{i}=\{j\in I:j\supseteq i\}.$ इन सभी सेटों का परिवार $A_{i}$ एक उचित फ़िल्टर (सेट सिद्धांत) उत्पन्न करता है, इसलिए एक अल्ट्राफ़िल्टर (सेट सिद्धांत) है $U$ फॉर्म के सभी सेट युक्त $A_{i}.$ अब किसी भी सूत्र के लिए $\varphi$ में $\Sigma :$

• सेट $A_{\{\varphi \}}$ में है $U$
• जब भी $j\in A_{\{\varphi \}},$ तब $\varphi \in j,$ इसलिए $\varphi$ में रखता है ${\mathcal {M}}_{j}$
• सभी का सेट $j$ उस संपत्ति के साथ $\varphi$ में रखता है ${\mathcal {M}}_{j}$ का सुपरसेट है $A_{\{\varphi \}},$ इसलिए भी में $U$

अल्ट्राप्रोडक्ट#लॉश का प्रमेय|लॉश का प्रमेय अब इसका तात्पर्य है $\varphi$ अल्ट्राप्रोडक्ट में रखता है ${\textstyle \prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}/U.}$ तो यह अल्ट्राप्रोडक्ट सभी फॉर्मूलों को संतुष्ट करता है $\Sigma .$

यह भी देखें

• Barwise compactness theorem
• Herbrand's theorem
• List of Boolean algebra topics
• Löwenheim–Skolem theorem

संदर्भ

• Boolos, George; Jeffrey, Richard; Burgess, John (2004). Computability and Logic (fourth ed.). Cambridge University Press.
• Chang, C.C.; Keisler, H. Jerome (1989). Model Theory (third ed.). Elsevier. ISBN 0-7204-0692-7.
• Dawson, John W. junior (1993). "The compactness of first-order logic: From Gödel to Lindström". History and Philosophy of Logic. 14: 15–37. doi:10.1080/01445349308837208.
• Hodges, Wilfrid (1993). Model theory. Cambridge University Press. ISBN 0-521-30442-3.
• Goldblatt, Robert (1998). Lectures on the Hyperreals. New York: Springer Verlag. ISBN 0-387-98464-X.
• Gowers, Timothy; Barrow-Green, June; Leader, Imre (2008). The Princeton Companion to Mathematics. Princeton: Princeton University Press. pp. 635–646. ISBN 978-1-4008-3039-8. OCLC 659590835.
• Marker, David (2002). Model Theory: An Introduction. Graduate Texts in Mathematics. Vol. 217. Springer. ISBN 978-0-387-98760-6. OCLC 49326991.
• Robinson, J. A. (1965). "A Machine-Oriented Logic Based on the Resolution Principle". Journal of the ACM. Association for Computing Machinery (ACM). 12 (1): 23–41. doi:10.1145/321250.321253. ISSN 0004-5411. S2CID 14389185.
• Truss, John K. (1997). Foundations of Mathematical Analysis. Oxford University Press. ISBN 0-19-853375-6.

इस पेज में लापता आंतरिक लिंक की सूची

• मॉडल (मॉडल सिद्धांत)
• गाढ़ापन
• परिमित चौराहा संपत्ति
• अंगूठी (गणित)
• इंजेक्शन नक्शा
• पियानो अंकगणित
• पसंद का स्वयंसिद्ध
• अल्ट्राफिल्टर (सेट सिद्धांत)

बाहरी कड़ियाँ

• Compactness Theorem, Internet Encyclopedia of Philosophy.