स्कोलेम सामान्य रूप

गणितीय तर्क में, प्रथम-क्रम तर्क का एक सुगठित_सूत्र स्कोलेम सामान्य रूप में होता है यदि यह केवल सार्वभौमिक परिमाणीकरण|सार्वभौमिक प्रथम-क्रम परिमाणकों के साथ प्रीनेक्स सामान्य रूप में होता है।

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

उदाहरण

स्कोलेमाइज़ेशन का सबसे सरल रूप अस्तित्वगत रूप से परिमाणित चर के लिए है जो एक सार्वभौमिक परिमाणक के दायरे (तर्क) के अंदर नहीं हैं। इन्हें केवल नए स्थिरांक बनाकर प्रतिस्थापित किया जा सकता है। उदाहरण के लिए, $\exists xP(x)$ में बदला जा सकता है $P(c)$, कहाँ $c$ एक नया स्थिरांक है (सूत्र में कहीं और नहीं होता है)।

अधिक सामान्यतः, स्कोलेमाइज़ेशन प्रत्येक अस्तित्वगत परिमाणित चर को प्रतिस्थापित करके किया जाता है $y$ एक शब्द के साथ $f(x_{1},\ldots ,x_{n})$ जिसका कार्य चिह्न $f$ नया है। इस पद के चर इस प्रकार हैं. यदि सूत्र प्रीनेक्स सामान्य रूप में है, तो $x_{1},\ldots ,x_{n}$ वे चर हैं जो सार्वभौमिक रूप से परिमाणित हैं और जिनके परिमाणक उससे पहले हैं $y$. सामान्य तौर पर, वे ऐसे चर होते हैं जिन्हें सार्वभौमिक रूप से परिमाणित किया जाता है (हम मानते हैं कि हम क्रम में अस्तित्व संबंधी परिमाणकों से छुटकारा पा लेते हैं, इसलिए पहले सभी अस्तित्वगत परिमाणकों $\exists y$ हटा दिए गए हैं) और ऐसे $\exists y$ उनके परिमाणकों के दायरे में होता है। कार्यक्रम $f$ इस प्रक्रिया में पेश किए गए को स्कोलेम फ़ंक्शन कहा जाता है (या स्कोलेम स्थिरांक यदि यह शून्य एरिटी का है) और शब्द को स्कोलेम शब्द कहा जाता है।

उदाहरण के तौर पर सूत्र $\forall x\exists y\forall z.P(x,y,z)$ स्कोलेम सामान्य रूप में नहीं है क्योंकि इसमें अस्तित्वगत परिमाणक शामिल है $\exists y$. स्कोलेमाइजेशन प्रतिस्थापित करता है $y$ साथ $f(x)$, कहाँ $f$ एक नया फ़ंक्शन प्रतीक है, और परिमाणीकरण को हटा देता है $y$. परिणामी सूत्र है $\forall x\forall z.P(x,f(x),z)$. स्कोलेम शब्द $f(x)$ रोकना $x$, लेकिन नहीं $z$, क्योंकि क्वांटिफायर को हटाया जाना है $\exists y$ के दायरे में है $\forall x$, लेकिन उसमें नहीं $\forall z$; चूँकि यह सूत्र प्रीनेक्स सामान्य रूप में है, यह कहने के बराबर है कि, परिमाणकों की सूची में, $x$ पछाड़ $y$ जबकि $z$ नहीं करता। इस परिवर्तन द्वारा प्राप्त सूत्र तभी संतोषजनक है जब मूल सूत्र हो।

स्कोलेमाइज़ेशन कैसे काम करता है

स्कोलेमाइज़ेशन प्रथम-क्रम संतुष्टि की परिभाषा के साथ दूसरे-क्रम तर्क|दूसरे-क्रम तुल्यता को लागू करके काम करता है। तुल्यता एक अस्तित्वगत परिमाणक को सार्वभौमिक परिमाणक से पहले ले जाने का एक तरीका प्रदान करती है।

$\forall x\exists yR(x,y)\iff \exists f\forall xR(x,f(x))$

कहाँ

$f(x)$ एक फ़ंक्शन है जो मैप करता है $x$ को $y$.

सहज रूप से, प्रत्येक के लिए वाक्य $x$ वहाँ एक मौजूद है $y$ ऐसा है कि $R(x,y)$समतुल्य रूप में परिवर्तित होने पर वहां एक फ़ंक्शन मौजूद होता है $f$ हर मैपिंग $x$ में $y$ ऐसा कि, हर किसी के लिए $x$ उसके पास होता है $R(x,f(x))$.

यह तुल्यता उपयोगी है क्योंकि प्रथम-क्रम संतुष्टि की परिभाषा अंतर्निहित रूप से फ़ंक्शन प्रतीकों के मूल्यांकन पर परिमाण निर्धारित करती है। विशेष रूप से, प्रथम-क्रम सूत्र $\Phi$ यदि कोई मॉडल मौजूद है तो यह संतोषजनक है $M$ और एक मूल्यांकन $\mu$ सूत्र के मुक्त चर जो सूत्र का सही मूल्यांकन करते हैं। मॉडल में सभी फ़ंक्शन प्रतीकों का मूल्यांकन शामिल है; इसलिए, स्कोलेम फ़ंक्शन अंतर्निहित रूप से अस्तित्वगत रूप से परिमाणित हैं। उपरोक्त उदाहरण में, $\forall x.R(x,f(x))$ यह तभी संतोषजनक है जब कोई मॉडल मौजूद हो $M$, जिसमें एक मूल्यांकन शामिल है $f$, ऐसा है कि $\forall x.R(x,f(x))$ इसके मुक्त चर के कुछ मूल्यांकन के लिए सत्य है (इस मामले में कोई नहीं)। इसे दूसरे क्रम में इस प्रकार व्यक्त किया जा सकता है $\exists f\forall x.R(x,f(x))$. उपरोक्त तुल्यता से, यह की संतुष्टि के समान है $\forall x\exists y.R(x,y)$.

मेटा-स्तर पर, प्रथम-क्रम तर्क#शब्दार्थ|किसी सूत्र की प्रथम-क्रम संतुष्टि $\Phi$ संकेतन के थोड़े दुरुपयोग के साथ लिखा जा सकता है $\exists M\exists \mu ~.~(M,\mu \models \Phi )$, कहाँ $M$ एक मॉडल है, $\mu$ मुक्त चर का मूल्यांकन है, और $\models$ मतलब कि $\Phi$ में सच है $M$ अंतर्गत $\mu$. चूँकि प्रथम-क्रम मॉडल में सभी फ़ंक्शन प्रतीकों का मूल्यांकन होता है, कोई भी स्कोलेम फ़ंक्शन $\Phi$ इसमें निहित रूप से अस्तित्वगत रूप से परिमाणित किया गया है $\exists M$. परिणामस्वरूप, सूत्र के सामने के कार्यों पर अस्तित्वगत परिमाणकों को चर के स्थान पर अस्तित्वगत परिमाणकों से बदलने के बाद, इन अस्तित्वगत परिमाणकों को हटाकर सूत्र को अभी भी प्रथम-क्रम वाले के रूप में माना जा सकता है। इलाज का यह अंतिम चरण $\exists f\forall x.R(x,f(x))$ जैसा $\forall x.R(x,f(x))$ पूरा किया जा सकता है क्योंकि कार्यों को अंतर्निहित रूप से अस्तित्वगत रूप से परिमाणित किया जाता है $\exists M$ प्रथम-क्रम संतुष्टि की परिभाषा में।

स्कोलेमाइज़ेशन की शुद्धता को उदाहरण सूत्र पर दिखाया जा सकता है $F_{1}=\forall x_{1}\dots \forall x_{n}\exists yR(x_{1},\dots ,x_{n},y)$ निम्नलिखित नुसार। यह सूत्र मॉडल_सिद्धांत#प्रथम-क्रम_तर्क से संतुष्ट है $M$ यदि और केवल यदि, के लिए प्रत्येक संभावित मान के लिए $x_{1},\dots ,x_{n}$ मॉडल के डोमेन में, के लिए एक मान मौजूद है $y$ उस मॉडल के क्षेत्र में जो बनाता है $R(x_{1},\dots ,x_{n},y)$ सत्य। पसंद के सिद्धांत के अनुसार, एक फ़ंक्शन मौजूद है $f$ ऐसा है कि $y=f(x_{1},\dots ,x_{n})$. परिणामस्वरूप, सूत्र $F_{2}=\forall x_{1}\dots \forall x_{n}R(x_{1},\dots ,x_{n},f(x_{1},\dots ,x_{n}))$ संतोषजनक है, क्योंकि इसमें मूल्यांकन जोड़कर प्राप्त मॉडल है $f$ को $M$. इससे पता चलता है कि $F_{1}$ तभी संतुष्ट है जब $F_{2}$ संतोषजनक भी है. इसके विपरीत, यदि $F_{2}$ संतोषजनक है, तो एक मॉडल मौजूद है $M'$ जो उसे संतुष्ट करता है; इस मॉडल में फ़ंक्शन के लिए मूल्यांकन शामिल है $f$ ऐसा कि, के हर मूल्य के लिए $x_{1},\dots ,x_{n}$, सूत्र $R(x_{1},\dots ,x_{n},f(x_{1},\dots ,x_{n}))$ धारण करता है. नतीजतन, $F_{1}$ एक ही मॉडल से संतुष्ट है क्योंकि कोई भी प्रत्येक मूल्य के लिए चुन सकता है $x_{1},\ldots ,x_{n}$, मूल्य $y=f(x_{1},\dots ,x_{n})$, कहाँ $f$ के अनुसार मूल्यांकन किया जाता है $M'$.

स्कोलेमाइज़ेशन के उपयोग

स्कोलेमाइज़ेशन के उपयोगों में से एक स्वचालित प्रमेय सिद्ध करना है। उदाहरण के लिए, विश्लेषणात्मक झांकी की विधि में, जब भी कोई सूत्र जिसका प्रमुख परिमाणक अस्तित्वगत होता है, तो स्कोलेमाइजेशन के माध्यम से उस परिमाणक को हटाकर प्राप्त सूत्र उत्पन्न किया जा सकता है। उदाहरण के लिए, यदि $\exists x.\Phi (x,y_{1},\ldots ,y_{n})$ एक झांकी में होता है, जहां $x,y_{1},\ldots ,y_{n}$ के मुक्त चर हैं $\Phi (x,y_{1},\ldots ,y_{n})$, तब $\Phi (f(y_{1},\ldots ,y_{n}),y_{1},\ldots ,y_{n})$ झांकी की उसी शाखा में जोड़ा जा सकता है। यह जोड़ झांकी की संतुष्टि में कोई बदलाव नहीं करता है: पुराने फॉर्मूले के प्रत्येक मॉडल को उपयुक्त मूल्यांकन जोड़कर बढ़ाया जा सकता है $f$, नए फॉर्मूले के एक मॉडल के लिए।

स्कोलेमाइजेशन का यह रूप शास्त्रीय स्कोलेमाइजेशन की तुलना में एक सुधार है, जिसमें केवल वेरिएबल जो सूत्र में मुक्त हैं, उन्हें स्कोलेम शब्द में रखा गया है। यह एक सुधार है क्योंकि झांकी के शब्दार्थ सूत्र को कुछ सार्वभौमिक रूप से परिमाणित चर के दायरे (प्रोग्रामिंग) में अंतर्निहित रूप से रख सकते हैं जो सूत्र में ही नहीं हैं; ये चर स्कोलेम शब्द में नहीं हैं, जबकि वे स्कोलेमाइज़ेशन की मूल परिभाषा के अनुसार होंगे। एक और सुधार जिसका उपयोग किया जा सकता है वह उन सूत्रों के लिए समान स्कोलेम फ़ंक्शन प्रतीक को लागू करना है जो परिवर्तनीय नामकरण तक समान हैं। एक अन्य उपयोग प्रथम-क्रम तर्क के लिए Resolution_(logic)#Resolution_in_first_order_logic|resolution विधि में है, जहां सूत्रों को सार्वभौमिक रूप से परिमाणित समझे जाने वाले खंड (तर्क) के सेट के रूप में दर्शाया जाता है। (उदाहरण के लिए पीने वाला विरोधाभास देखें।)

मॉडल सिद्धांत में एक महत्वपूर्ण परिणाम लोवेनहेम-स्कोलेम प्रमेय है, जिसे सिद्धांत को स्कोलेमाइज़ करके और परिणामी स्कोलेम कार्यों के तहत बंद करके सिद्ध किया जा सकता है।

स्कोलेम सिद्धांत

सामान्य तौर पर, यदि $T$ एक सिद्धांत (गणितीय तर्क) है और प्रत्येक सूत्र के लिए मुक्त चर हैं $x_{1},\dots ,x_{n},y$ एक फ़ंक्शन प्रतीक है $F$ यह संभवतः एक स्कोलेम फ़ंक्शन है $y$, तब $T$ स्कोलेम सिद्धांत कहा जाता है। प्रत्येक स्कोलेम सिद्धांत मॉडल पूर्ण सिद्धांत है, अर्थात मॉडल की प्रत्येक उपसंरचना (गणित) एक प्रारंभिक तुल्यता है। स्कोलेम सिद्धांत टी के एक मॉडल एम को देखते हुए, एक निश्चित सेट ए वाले सबसे छोटे उपसंरचना को ए का 'स्कोलेम हल' कहा जाता है। ए का स्कोलेम हल ए के ऊपर एक परमाणु मॉडल (गणितीय तर्क) प्रमुख मॉडल है।

इतिहास

स्कोलेम सामान्य रूप का नाम दिवंगत नॉर्वेजियन गणितज्ञ थोरल्फ़ स्कोलेम के नाम पर रखा गया है।

यह भी देखें

• हरब्रांडीकरण, स्कोलेमाइज़ेशन का दोहरा
• विधेय फ़ैक्टर तर्क

संदर्भ

• Hodges, Wilfrid (1997), A Shorter Model Theory, Cambridge University Press, ISBN 978-0-521-58713-6

बाहरी संबंध

• "Skolem function", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Skolemization on PlanetMath.org
• Skolemization by Hector Zenil, The Wolfram Demonstrations Project.
• Weisstein, Eric W. "SkolemizedForm". MathWorld.