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

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

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

मुख्य विचार

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

खेल निश्चित संख्या में चरणों तक चलता है $\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}}$ यदि डुप्लिकेटर एन-मूव गेम जीतता है $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$) हेलोइस और एबेलार्ड के बाद, विल्फ्रिड होजेस द्वारा अपनी पुस्तक मॉडल थ्योरी, या वैकल्पिक रूप से ईव और एडम में पेश की गई एक नामकरण योजना।

अग्रिम पठन

Chapter 1 of Poizat's model theory text contains an introduction to the Ehrenfeucht–Fraïssé game, and so do Chapters 6, 7, and 13 of Rosenstein's book on linear orders. A simple example of the Ehrenfeucht–Fraïssé game is given in one of Ivars Peterson's MathTrek columns.

Phokion Kolaitis' slides and Neil Immerman's book chapter on Ehrenfeucht–Fraïssé games discuss applications in computer science, the methodology for proving inexpressibility results, and several simple inexpressibility proofs using this methodology.

Ehrenfeucht–Fraïssé games are the basis for the operation of derivative on modeloids. Modeloids are certain equivalence relations and the derivative provides for a generalization of standard model theory.

संदर्भ

• 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)