एहरनफ्यूच्ट-फ्रैस्से गेम

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

एहरनफ्यूच्ट-फ़्रासे-जैसे गेम को अन्य तर्कों के लिए भी परिभाषित किया जा सकता है, जैसे फिक्सपॉइंट लॉजिक्स और परिमित परिवर्तनीय लॉजिक्स के लिए पेबल गेम एक्सटेंशन अस्तित्व संबंधी दूसरे क्रम के तर्क में निश्चितता को दर्शाने के लिए पर्याप्त शक्तिशाली हैं।

मुख्य विचार

गेम के पीछे मुख्य विचार यह है कि हमारे निकट दो संरचनाएं और दो प्लेयर्स हैं- स्पॉइलर और डुप्लिकेटर। डुप्लिकेटर यह दिखाना चाहता है कि दोनों संरचनाएं मौलिक रूप से समतुल्य हैं (समान प्रथम-क्रम वाक्यों (गणितीय तर्क) को संतुष्ट करती हैं), जबकि स्पॉयलर यह दिखाना चाहता है कि वे भिन्न हैं। गेम राउंड में खेला जाता है राउंड इस प्रकार आगे बढ़ता है: स्पॉइलर किसी एक संरचना से किसी तत्व का चयन किया जाता है, और डुप्लिकेटर दूसरी संरचना से तत्व को चयन करता है। सरलीकृत शब्दों में, डुप्लिकेटर का कार्य सदैव स्पॉयलर द्वारा चयन किये गए तत्व के "समान" तत्व को चयन करना है जबकि स्पॉयलर का कार्य उस तत्व को चयन करना है जिसके लिए अन्य संरचना में कोई "समान" तत्व उपस्तिथ नहीं है। यदि दो भिन्न-भिन्न संरचनाओं से चयन किये गए अंतिम उपसंरचनाओं के मध्य समरूपता उपस्तिथ है तो डुप्लिकेटर जीतता है; अन्यथा, स्पॉइलर जीत जाता है।

गेम $\gamma$ निश्चित संख्या में चरणों तक चलता (जो क्रमसूचक है- सामान्यतः सीमित संख्या या $\omega$) है।

परिभाषा

मान लीजिए कि दो संरचनाएँ दी गई हैं ${\mathfrak {A}}$ और ${\mathfrak {B}}$, प्रत्येक में कोई फलन (गणित) प्रतीक नहीं हैं और संबंध (गणित) प्रतीकों का समुच्चय है, और निश्चित प्राकृतिक संख्या n है। फिर हम एरेनफ्यूच्ट-फ्रैसे गेम को परिभाषित कर सकते हैं गेम $G_{n}({\mathfrak {A}},{\mathfrak {B}})$ दो प्लेयर्स, स्पॉइलर और डुप्लिकेटर के मध्य गेम है, जो इस प्रकार खेला जाता है:

1. प्रथम प्लेयर्स, स्पॉइलर, किसी सदस्य $a_{1}$ का ${\mathfrak {A}}$ या सदस्य $b_{1}$ का ${\mathfrak {B}}$ को चयन करता है।
2. यदि स्पॉइलर ने किसी सदस्य को ${\mathfrak {A}}$, अनुलिपित्र सदस्य का चयन करता है $b_{1}$का ${\mathfrak {B}}$ अन्यथा, अनुलिपित्र $a_{1}$ का ${\mathfrak {A}}$ सदस्य का चयन करता है।
3. स्पॉइलर किसी $a_{2}$ का ${\mathfrak {A}}$ या सदस्य $b_{2}$ का ${\mathfrak {B}}$ सदस्य का चयन करता है।
4. अनुलिपित्र $a_{2}$ या $b_{2}$ तत्व का चयन करता है उस मॉडल में जिसमें से स्पोइलर ने नहीं चयन किया।
5. स्पॉइलर और डुप्लीकेटर सदस्यों को ${\mathfrak {A}}$ और ${\mathfrak {B}}$, $n-2$ के लिए चयन को प्रारंभ रखते हैं।
6. गेम के समापन पर, भिन्न-भिन्न तत्वों का चयन किया जाता है $a_{1},\dots ,a_{n}$ का ${\mathfrak {A}}$ और $b_{1},\dots ,b_{n}$ का ${\mathfrak {B}}$ इसलिए हमारे निकट समुच्चय पर दो संरचनाएं हैं $\{1,\dots ,n\}$, से प्रेरित ${\mathfrak {A}}$ मानचित्र भेजने के माध्यम से $i$ को $a_{i}$, और दूसरे से प्रेरित ${\mathfrak {B}}$ मानचित्र भेजने के माध्यम से $i$ को $b_{i}$ यदि ये संरचनाएं समान हैं तो डुप्लिकेटर जीतता है; यदि वे नहीं हैं तो स्पॉइलर जीत जाता है।

प्रत्येक n के लिए संबंध ${\mathfrak {A}}\ {\overset {n}{\sim }}\ {\mathfrak {B}}$ परिभाषित करते हैं यदि डुप्लिकेटर n-मूव गेम जीतता है तो $G_{n}({\mathfrak {A}},{\mathfrak {B}})$ ये सभी दिए गए संबंध प्रतीकों के साथ संरचनाओं के वर्ग पर समतुल्य संबंध हैं। इन सभी संबंधों का प्रतिच्छेदन पुनः ${\mathfrak {A}}\sim {\mathfrak {B}}$ तुल्यता संबंध है।

समानता और अव्यक्तता

यह सिद्ध करना सरल है कि यदि डुप्लिकेटर इस गेम को सभी परिमित n के लिए जीतता है, अर्थात, ${\mathfrak {A}}\sim {\mathfrak {B}}$, तब ${\mathfrak {A}}$ और ${\mathfrak {B}}$ प्राथमिक रूप से समतुल्य हैं। यदि माना जा रहा है कि संबंध प्रतीकों का समुच्चय सीमित है, तो इसका विपरीत भी सत्य है।

यदि कोई गुण $Q$ का सत्य है ${\mathfrak {A}}$ किन्तु सत्य नहीं है ${\mathfrak {B}}$ और ${\mathfrak {A}}$ डुप्लिकेटर के लिए विजयी रणनीति प्रदान करके ${\mathfrak {B}}$ को समकक्ष दिखाया जा सकता है, तो यह दिखाता है।

इस गेम द्वारा कैप्चर किए गए तर्क में $Q$ अवर्णनीय है।

इतिहास

प्राथमिक तुल्यता को सत्यापित करने के लिए एहरनफेक्ट-फ्रैसे गेम में उपयोग की जाने वाली आगे-पीछे की विधि रोलांड फ्रैसे ने अपनी थीसिस में दी थी;इसे आंद्रेज एहरनफ्यूच्ट द्वारा गेम के रूप में तैयार किया गया था। स्पॉइलर और डुप्लीकेटर नाम जोएल स्पेंसर के कारण हैं। अन्य सामान्य नाम एलोइस [एसआईसी] और एबेलार्ड हैं (और प्रायः इन्हें इसके द्वारा दर्शाया जाता है)। $\exists$ और $\forall$) हेलोइस और एबेलार्ड के पश्चात, विल्फ्रिड होजेस द्वारा अपनी पुस्तक मॉडल थ्योरी, या वैकल्पिक रूप से ईव और एडम में प्रस्तुत की गई नामकरण योजना है।

अग्रिम पठन

पोइज़ैट के मॉडल सिद्धांत पाठ के अध्याय 1 मेंएहरनफ्यूच्ट-फ्रैसे गेम का परिचय सम्मिलित है, और इसी प्रकार रोसेनस्टीन की पुस्तक के अध्याय 6, 7, और 13 में रैखिक क्रम पर है। इवार्स पीटरसन के मैथट्रेक कॉलम में से एरेनफ्यूचट-फ्रैसे गेम का सरल उदाहरण दिया गया है।

फ़ोकियन कोलाइटिस की स्लाइड्स और एहरनफ्यूच्ट-फ्रैसे गेम्स पर नील इम्रमैन की पुस्तक अध्याय कंप्यूटर विज्ञान में अनुप्रयोगों, अवर्णनीय परिणामों को सिद्ध करने की पद्धति और इस पद्धति का उपयोग करके कई सरल अवर्णनीय प्रमाणों पर वर्णन करते हैं।

एहरनफ्यूचट-फ्रैसे गेम मॉडलॉयड पर व्युत्पन्न के संचालन का आधार हैं। मॉडलॉयड कुछ तुल्यता संबंध हैं और व्युत्पन्न मानक मॉडल सिद्धांत के सामान्यीकरण के लिए प्रदान करता है।

संदर्भ

• Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Maarten, Marx; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Finite model theory and its applications. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 978-3-540-00428-8. Zbl 1133.03001.

बाहरी संबंध

• Six Lectures on Ehrenfeucht-Fraïssé games at MATH EXPLORERS' CLUB, Cornell Department of Mathematics.
• Modeloids I, Miroslav Benda, Transactions of the American Mathematical Society, Vol. 250 (Jun 1979), pp. 47 – 90 (44 pages)