प्राथमिक तुल्यता: Difference between revisions
Line 1: | Line 1: | ||
[[मॉडल सिद्धांत]] में, [[गणितीय तर्क]] की | [[मॉडल सिद्धांत]] में, [[गणितीय तर्क]] की शाखा, एक ही प्रतीक σ की दो संरचनाएं ''M'' और ''N'' को प्राथमिक रूप से समतुल्य कहा जाता है यदि वे समान प्रथम-क्रम σ-वाक्यों को संतुष्ट करते हैं। | ||
यदि ''N, M'' की एक उपसंरचना है, तो | यदि ''N, M'' की एक उपसंरचना है, तो प्रायः प्रबल स्थिति की आवश्यकता होती है। इस स्तिथि में ''N'' को ''M'' का प्रारंभिक उपसंरचना कहा जाता है यदि प्रत्येक प्रथम-क्रम σ-सूत्र ''φ''(''a''<sub>1</sub>, …, ''a<sub>n</sub>'') पैरामीटर ''a''<sub>1</sub>, …, ''a<sub>n</sub>'' के साथ ''N'' में सत्य है यदि और केवल यदि यह ''M'' में सत्य है। यदि ''N, M'' का प्राथमिक उपसंरचना है, तो ''M'' को ''N'' का प्रारंभिक विस्तार कहा जाता है। एम्बेडिंग ''h'': ''N'' → ''M'' को ''M'' में ''N'' का प्रारंभिक एम्बेडिंग कहा जाता है यदि ''h(N) M'' का एक प्रारंभिक उपसंरचना है। | ||
''M'' | ''M'' की उपसंरचना ''N'' प्राथमिक है यदि और केवल अगर यह टार्स्की-वॉथ परीक्षण पास करता है: ''N'' में पैरामीटर के साथ प्रत्येक प्रथम-क्रम सूत्र ''φ''(''x'', ''b''<sub>1</sub>, …, ''b<sub>n</sub>'') जिसका ''M'' में समाधान होता है, ''M'' में मूल्यांकन करने पर ''N'' में भी एक समाधान होता है। कोई यह साबित कर सकता है कि दो संरचनाएं मूल रूप से एहरनफेक्ट-फ्रैस्से खेलों के बराबर हैं। | ||
रैंक-टू-रैंक सहित बड़े कार्डिनल्स के अध्ययन में प्राथमिक एम्बेडिंग का उपयोग किया जाता है। | रैंक-टू-रैंक सहित बड़े कार्डिनल्स के अध्ययन में प्राथमिक एम्बेडिंग का उपयोग किया जाता है। | ||
Line 13: | Line 13: | ||
प्रथम-क्रम सिद्धांत तभी पूर्ण होता है जब इसके कोई भी दो मॉडल प्राथमिक रूप से समकक्ष हों। | प्रथम-क्रम सिद्धांत तभी पूर्ण होता है जब इसके कोई भी दो मॉडल प्राथमिक रूप से समकक्ष हों। | ||
उदाहरण के लिए, | उदाहरण के लिए, बाइनरी रिलेशन सिंबल '<' वाली भाषा पर विचार करें। अपने सामान्य क्रम के साथ वास्तविक संख्याओं का मॉडल '''R''' और अपने सामान्य क्रम के साथ परिमेय संख्याओं का मॉडल '''Q''' मौलिक रूप से समतुल्य हैं क्योंकि वे दोनों '<' को असीमित घने रैखिक क्रम के रूप में व्याख्या करते हैं। यह प्राथमिक तुल्यता सुनिश्चित करने के लिए पर्याप्त है, क्योंकि असीमित घने रैखिक क्रम का सिद्धांत पूरा हो गया है, जैसा कि लोश-वॉच परीक्षण द्वारा दिखाया जा सकता है। | ||
अधिक सामान्यतः, अनंत मॉडल वाले किसी भी प्रथम-क्रम सिद्धांत में गैर-आइसोमोर्फिक, प्राथमिक रूप से समकक्ष मॉडल होते हैं, जिन्हें लोवेनहेम-स्कोलेम प्रमेय के माध्यम से प्राप्त किया जा सकता है। इस प्रकार, उदाहरण के लिए, पीनो अंकगणित के गैर-मानक मॉडल हैं, जिनमें केवल संख्या 0, 1, 2, आदि के अलावा अन्य वस्तुएं | अधिक सामान्यतः, अनंत मॉडल वाले किसी भी प्रथम-क्रम सिद्धांत में गैर-आइसोमोर्फिक, प्राथमिक रूप से समकक्ष मॉडल होते हैं, जिन्हें लोवेनहेम-स्कोलेम प्रमेय के माध्यम से प्राप्त किया जा सकता है। इस प्रकार, उदाहरण के लिए, पीनो अंकगणित के गैर-मानक मॉडल हैं, जिनमें केवल संख्या 0, 1, 2, आदि के अलावा अन्य वस्तुएं सम्मिलित हैं, और फिर भी वे मानक मॉडल के मूल रूप से समकक्ष हैं। | ||
==प्राथमिक उपसंरचनाएं और प्रारंभिक विस्तार== | ==प्राथमिक उपसंरचनाएं और प्रारंभिक विस्तार== | ||
''N, M'' का | ''N, M'' का '''प्राथमिक उपसंरचना''' या '''प्राथमिक उपमॉडल''' है यदि ''N'' और ''M'' ही प्रतीक σ की संरचनाएं हैं जैसे कि सभी प्रथम-क्रम σ-सूत्रों ''φ''(''x''<sub>1</sub>, …, ''x<sub>n</sub>'') के लिए मुक्त चर ''x''<sub>1</sub>, …, ''x<sub>n</sub>'', और सभी अवयवों ''a''<sub>1</sub>, …, ''a''<sub>n</sub> N का ''φ''(''a''<sub>1</sub>, …, ''a''<sub>n</sub>) ''N'' में रहता है यदि और केवल अगर यह ''M'' में रहता है: | ||
<math display="block">N \models \varphi(a_1, \dots, a_n) \text{ if and only if } M \models \varphi(a_1, \dots, a_n).</math> | <math display="block">N \models \varphi(a_1, \dots, a_n) \text{ if and only if } M \models \varphi(a_1, \dots, a_n).</math><br />यह परिभाषा सबसे पहले टार्स्की, वाउट (1957) में दिखाई देती है।<ref>E. C. Milner, [https://www.sciencedirect.com/science/article/pii/0012365X9590789N The use of elementary substructures in combinatorics] (1993). Appearing in ''Discrete Mathematics'', vol. 136, issues 1--3, 1994, pp.243--252.</ref> इससे यह निष्कर्ष निकलता है कि ''N, M'' की उपसंरचना है। | ||
यदि ''N, M'' की उपसंरचना है, तो N और M दोनों को प्रतीक ''σ<sub>N</sub>'' में संरचनाओं के रूप में व्याख्या किया जा सकता है, जिसमें N के प्रत्येक अवयव के लिए नए स्थिर प्रतीक के साथ σ सम्मिलित है। तब ''N, M'' का प्राथमिक उपसंरचना है यदि और केवल यदि ''N, M'' का उपसंरचना है और ''N'' और ''M'' मूल रूप से ''σ<sub>N</sub>''-संरचनाओं के बराबर हैं। | |||
यदि ''N, M'' का प्राथमिक उपसंरचना है, तो कोई N ⪯ M लिखता है और कहता है कि ''M'', ''N: M ⪰ N'' का '''प्रारंभिक विस्तार''' है। | यदि ''N, M'' का प्राथमिक उपसंरचना है, तो कोई N ⪯ M लिखता है और कहता है कि ''M'', ''N: M ⪰ N'' का '''प्रारंभिक विस्तार''' है। | ||
नीचे की ओर लोवेनहेम-स्कोलेम प्रमेय अधिकतम गणनीय प्रतीक में किसी भी अनंत प्रथम-क्रम संरचना के लिए | नीचे की ओर लोवेनहेम-स्कोलेम प्रमेय अधिकतम गणनीय प्रतीक में किसी भी अनंत प्रथम-क्रम संरचना के लिए गणनीय प्राथमिक उप-संरचना देता है; उर्ध्वगामी लोवेनहेम-स्कोलेम प्रमेय मनमाने ढंग से बड़ी कार्डिनैलिटी की किसी भी अनंत प्रथम-क्रम संरचना का प्रारंभिक विस्तार देता है। | ||
==टार्स्की-वाउट टेस्ट== | ==टार्स्की-वाउट टेस्ट== | ||
'''टार्स्की- | '''टार्स्की-वाउट परीक्षण''' (या '''टार्स्की-वाउट मानदंड''') संरचना ''M'' के उपसंरचना ''N'' के प्राथमिक उपसंरचना होने के लिए आवश्यक और पर्याप्त शर्त है। यह किसी बड़ी संरचना की प्रारंभिक उपसंरचना के निर्माण के लिए उपयोगी हो सकता है। | ||
मान लीजिए कि ''M'' प्रतीक σ की | मान लीजिए कि ''M'' प्रतीक σ की संरचना है और ''N, M'' की उपसंरचना है। तब ''N, M'' की प्राथमिक उपसंरचना है यदि और केवल यदि प्रत्येक प्रथम-क्रम सूत्र ''φ''(''x'', ''y''<sub>1</sub>, …, ''y<sub>n</sub>'') के लिए σ से अधिक और सभी अवयव ''b''<sub>1</sub>, …, ''b<sub>n</sub>'' N से, यदि M<math>\models</math>{{exist}}''x'' ''φ''(''x'', ''b''<sub>1</sub>, …, ''b<sub>n</sub>''),, तो ''N'' में अवयव ''a'' है जैसे कि M <math>\models</math>φ(a, b1, …, bn)। | ||
==प्राथमिक एम्बेडिंग== | ==प्राथमिक एम्बेडिंग== | ||
समान प्रतीक σ की संरचना ''M'' में संरचना ''N'' का प्रारंभिक एम्बेडिंग | समान प्रतीक σ की संरचना ''M'' में संरचना ''N'' का प्रारंभिक एम्बेडिंग मानचित्र ''h: N → M'' है, जैसे कि प्रत्येक प्रथम-क्रम σ-सूत्र ''φ''(''x''<sub>1</sub>, …, ''x<sub>n</sub>'') और N के सभी अवयव ''a''<sub>1</sub>, …, ''a''<sub>n</sub> के लिए, | ||
:''N'' <math>\models</math> ''φ''(''a''<sub>1</sub>, …, ''a<sub>n</sub>'') यदि और केवल ''M'' ''φ''(''h''(''a''<sub>1</sub>), …, ''h''(''a<sub>n</sub>'')). | :''N'' <math>\models</math> ''φ''(''a''<sub>1</sub>, …, ''a<sub>n</sub>'') यदि और केवल ''M'' ''φ''(''h''(''a''<sub>1</sub>), …, ''h''(''a<sub>n</sub>'')). | ||
प्रत्येक प्रारंभिक एम्बेडिंग | प्रत्येक प्रारंभिक एम्बेडिंग प्रबल समरूपता है, और इसकी छवि प्राथमिक उपसंरचना है। | ||
मॉडल सिद्धांत में प्राथमिक एंबेडिंग्स सबसे महत्वपूर्ण मानचित्र हैं। सेट सिद्धांत में, प्राथमिक एंबेडिंग्स जिसका डोमेन ''V'' (सेट सिद्धांत का ब्रह्मांड) है, बड़े कार्डिनल्स के सिद्धांत में एक महत्वपूर्ण भूमिका निभाते हैं (क्रिटिकल पॉइंट भी देखें)। | मॉडल सिद्धांत में प्राथमिक एंबेडिंग्स सबसे महत्वपूर्ण मानचित्र हैं। सेट सिद्धांत में, प्राथमिक एंबेडिंग्स जिसका डोमेन ''V'' (सेट सिद्धांत का ब्रह्मांड) है, बड़े कार्डिनल्स के सिद्धांत में एक महत्वपूर्ण भूमिका निभाते हैं (क्रिटिकल पॉइंट भी देखें)। |
Revision as of 23:16, 23 July 2023
मॉडल सिद्धांत में, गणितीय तर्क की शाखा, एक ही प्रतीक σ की दो संरचनाएं M और N को प्राथमिक रूप से समतुल्य कहा जाता है यदि वे समान प्रथम-क्रम σ-वाक्यों को संतुष्ट करते हैं।
यदि N, M की एक उपसंरचना है, तो प्रायः प्रबल स्थिति की आवश्यकता होती है। इस स्तिथि में N को M का प्रारंभिक उपसंरचना कहा जाता है यदि प्रत्येक प्रथम-क्रम σ-सूत्र φ(a1, …, an) पैरामीटर a1, …, an के साथ N में सत्य है यदि और केवल यदि यह M में सत्य है। यदि N, M का प्राथमिक उपसंरचना है, तो M को N का प्रारंभिक विस्तार कहा जाता है। एम्बेडिंग h: N → M को M में N का प्रारंभिक एम्बेडिंग कहा जाता है यदि h(N) M का एक प्रारंभिक उपसंरचना है।
M की उपसंरचना N प्राथमिक है यदि और केवल अगर यह टार्स्की-वॉथ परीक्षण पास करता है: N में पैरामीटर के साथ प्रत्येक प्रथम-क्रम सूत्र φ(x, b1, …, bn) जिसका M में समाधान होता है, M में मूल्यांकन करने पर N में भी एक समाधान होता है। कोई यह साबित कर सकता है कि दो संरचनाएं मूल रूप से एहरनफेक्ट-फ्रैस्से खेलों के बराबर हैं।
रैंक-टू-रैंक सहित बड़े कार्डिनल्स के अध्ययन में प्राथमिक एम्बेडिंग का उपयोग किया जाता है।
प्राथमिक रूप से समतुल्य संरचनाएँ
एक ही प्रतीक σ की दो संरचनाएँ M और N प्राथमिक रूप से समतुल्य हैं यदि σ पर प्रत्येक प्रथम-क्रम वाक्य (मुक्त चर के बिना सूत्र) M में सत्य है यदि और केवल यदि यह N में सत्य है, अर्थात यदि M और N में समान पूर्ण प्रथम-क्रम सिद्धांत है। यदि M और N मूलतः समतुल्य हैं, तो कोई M ≡ N लिखता है।
प्रथम-क्रम सिद्धांत तभी पूर्ण होता है जब इसके कोई भी दो मॉडल प्राथमिक रूप से समकक्ष हों।
उदाहरण के लिए, बाइनरी रिलेशन सिंबल '<' वाली भाषा पर विचार करें। अपने सामान्य क्रम के साथ वास्तविक संख्याओं का मॉडल R और अपने सामान्य क्रम के साथ परिमेय संख्याओं का मॉडल Q मौलिक रूप से समतुल्य हैं क्योंकि वे दोनों '<' को असीमित घने रैखिक क्रम के रूप में व्याख्या करते हैं। यह प्राथमिक तुल्यता सुनिश्चित करने के लिए पर्याप्त है, क्योंकि असीमित घने रैखिक क्रम का सिद्धांत पूरा हो गया है, जैसा कि लोश-वॉच परीक्षण द्वारा दिखाया जा सकता है।
अधिक सामान्यतः, अनंत मॉडल वाले किसी भी प्रथम-क्रम सिद्धांत में गैर-आइसोमोर्फिक, प्राथमिक रूप से समकक्ष मॉडल होते हैं, जिन्हें लोवेनहेम-स्कोलेम प्रमेय के माध्यम से प्राप्त किया जा सकता है। इस प्रकार, उदाहरण के लिए, पीनो अंकगणित के गैर-मानक मॉडल हैं, जिनमें केवल संख्या 0, 1, 2, आदि के अलावा अन्य वस्तुएं सम्मिलित हैं, और फिर भी वे मानक मॉडल के मूल रूप से समकक्ष हैं।
प्राथमिक उपसंरचनाएं और प्रारंभिक विस्तार
N, M का प्राथमिक उपसंरचना या प्राथमिक उपमॉडल है यदि N और M ही प्रतीक σ की संरचनाएं हैं जैसे कि सभी प्रथम-क्रम σ-सूत्रों φ(x1, …, xn) के लिए मुक्त चर x1, …, xn, और सभी अवयवों a1, …, an N का φ(a1, …, an) N में रहता है यदि और केवल अगर यह M में रहता है:
यह परिभाषा सबसे पहले टार्स्की, वाउट (1957) में दिखाई देती है।[1] इससे यह निष्कर्ष निकलता है कि N, M की उपसंरचना है।
यदि N, M की उपसंरचना है, तो N और M दोनों को प्रतीक σN में संरचनाओं के रूप में व्याख्या किया जा सकता है, जिसमें N के प्रत्येक अवयव के लिए नए स्थिर प्रतीक के साथ σ सम्मिलित है। तब N, M का प्राथमिक उपसंरचना है यदि और केवल यदि N, M का उपसंरचना है और N और M मूल रूप से σN-संरचनाओं के बराबर हैं।
यदि N, M का प्राथमिक उपसंरचना है, तो कोई N ⪯ M लिखता है और कहता है कि M, N: M ⪰ N का प्रारंभिक विस्तार है।
नीचे की ओर लोवेनहेम-स्कोलेम प्रमेय अधिकतम गणनीय प्रतीक में किसी भी अनंत प्रथम-क्रम संरचना के लिए गणनीय प्राथमिक उप-संरचना देता है; उर्ध्वगामी लोवेनहेम-स्कोलेम प्रमेय मनमाने ढंग से बड़ी कार्डिनैलिटी की किसी भी अनंत प्रथम-क्रम संरचना का प्रारंभिक विस्तार देता है।
टार्स्की-वाउट टेस्ट
टार्स्की-वाउट परीक्षण (या टार्स्की-वाउट मानदंड) संरचना M के उपसंरचना N के प्राथमिक उपसंरचना होने के लिए आवश्यक और पर्याप्त शर्त है। यह किसी बड़ी संरचना की प्रारंभिक उपसंरचना के निर्माण के लिए उपयोगी हो सकता है।
मान लीजिए कि M प्रतीक σ की संरचना है और N, M की उपसंरचना है। तब N, M की प्राथमिक उपसंरचना है यदि और केवल यदि प्रत्येक प्रथम-क्रम सूत्र φ(x, y1, …, yn) के लिए σ से अधिक और सभी अवयव b1, …, bn N से, यदि Mx φ(x, b1, …, bn),, तो N में अवयव a है जैसे कि M φ(a, b1, …, bn)।
प्राथमिक एम्बेडिंग
समान प्रतीक σ की संरचना M में संरचना N का प्रारंभिक एम्बेडिंग मानचित्र h: N → M है, जैसे कि प्रत्येक प्रथम-क्रम σ-सूत्र φ(x1, …, xn) और N के सभी अवयव a1, …, an के लिए,
- N φ(a1, …, an) यदि और केवल M φ(h(a1), …, h(an)).
प्रत्येक प्रारंभिक एम्बेडिंग प्रबल समरूपता है, और इसकी छवि प्राथमिक उपसंरचना है।
मॉडल सिद्धांत में प्राथमिक एंबेडिंग्स सबसे महत्वपूर्ण मानचित्र हैं। सेट सिद्धांत में, प्राथमिक एंबेडिंग्स जिसका डोमेन V (सेट सिद्धांत का ब्रह्मांड) है, बड़े कार्डिनल्स के सिद्धांत में एक महत्वपूर्ण भूमिका निभाते हैं (क्रिटिकल पॉइंट भी देखें)।
संदर्भ
- ↑ E. C. Milner, The use of elementary substructures in combinatorics (1993). Appearing in Discrete Mathematics, vol. 136, issues 1--3, 1994, pp.243--252.
- Chang, Chen Chung; Keisler, H. Jerome (1990) [1973], Model Theory, Studies in Logic and the Foundations of Mathematics (3rd ed.), Elsevier, ISBN 978-0-444-88054-3.
- Hodges, Wilfrid (1997), A shorter model theory, Cambridge: Cambridge University Press, ISBN 978-0-521-58713-6.
- Monk, J. Donald (1976), Mathematical Logic, Graduate Texts in Mathematics, New York • Heidelberg • Berlin: Springer Verlag, ISBN 0-387-90170-1