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

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

एहरनफ्यूच्ट-फ़्रासे-जैसे गेम को अन्य तर्कों के लिए भी परिभाषित किया जा सकता है, जैसे [[ फिक्सपॉइंट तर्क |फिक्सपॉइंट लॉजिक्स]]<ref>{{cite book | title=Computer Science Logic: 6th Workshop, CSL'92, San Miniato, Italy, September 28 - October 2, 1992. Selected Papers | volume=702 | series=Lecture Notes in Computer Science | editor1-first=Egon | editor1-last=Börger | publisher=[[Springer-Verlag]] | year=1993 | zbl=0808.03024 | isbn=3-540-56992-8 | pages=100–114 | first=Uwe | last=Bosse | chapter=An Ehrenfeucht–Fraïssé game for fixpoint logic and stratified fixpoint logic |chapter-url=https://link.springer.com/content/pdf/10.1007/3-540-56992-8_8.pdf| doi=10.1007/3-540-56992-8_8 }}</ref> और परिमित परिवर्तनीय लॉजिक्स के लिए [[कंकड़ खेल|पेबल गेम]] एक्सटेंशन अस्तित्व संबंधी दूसरे क्रम के तर्क में निश्चितता को दर्शाने के लिए पर्याप्त शक्तिशाली हैं।

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

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

== परिभाषा ==
मान लीजिए कि हमें दो संरचनाएँ दी गई हैं <math>\mathfrak{A}</math> और <math>\mathfrak{B}</math>, प्रत्येक में कोई [[फ़ंक्शन (गणित)|फलन (गणित)]] प्रतीक नहीं हैं और [[संबंध (गणित)]] प्रतीकों का समुच्चय है, और निश्चित प्राकृतिक संख्या n है। फिर हम एरेनफ्यूच्ट-फ्रैसे गेम को परिभाषित कर सकते हैं गेम <math>G_n(\mathfrak{A},\mathfrak{B})</math> दो खिलाड़ियों, स्पॉइलर और डुप्लिकेटर के मध्य गेम है, जो इस प्रकार खेला जाता है:
# प्रथम प्लेयर्स, स्पॉइलर, किसी सदस्य <math>a_1</math> का <math>\mathfrak{A}</math> या सदस्य <math>b_1</math> का <math>\mathfrak{B}</math> को चयन करता है।
# यदि स्पॉइलर ने किसी सदस्य को <math>\mathfrak{A}</math>, अनुलिपित्र सदस्य का चयन करता है <math>b_1</math>का <math>\mathfrak{B}</math>; अन्यथा, अनुलिपित्र <math>a_1</math> का <math>\mathfrak{A}</math> सदस्य का चयन करता है।
# स्पॉइलर किसी <math>a_2</math> का <math>\mathfrak{A}</math> या सदस्य <math>b_2</math> का <math>\mathfrak{B}</math> सदस्य का चयन करता है।
# अनुलिपित्र <math>a_2</math> या <math>b_2</math> तत्व का चयन करता है उस मॉडल में जिसमें से स्पोइलर ने नहीं चयन किया।
# स्पॉइलर और डुप्लीकेटर सदस्यों को <math>\mathfrak{A}</math> और <math>\mathfrak{B}</math>, <math>n-2</math> के लिए चयन को प्रारंभ रखते हैं।
# गेम के समापन पर, भिन्न-भिन्न तत्वों का चयन किया जाता है <math>a_1, \dots, a_n</math> का <math>\mathfrak{A}</math> और <math>b_1, \dots, b_n</math> का <math>\mathfrak{B}</math> इसलिए हमारे निकट समुच्चय पर दो संरचनाएं हैं <math>\{1, \dots,n\}</math>, से प्रेरित <math>\mathfrak{A}</math> मानचित्र भेजने के माध्यम से <math>i</math> को <math>a_i</math>, और दूसरे से प्रेरित <math>\mathfrak{B}</math> मानचित्र भेजने के माध्यम से <math>i</math> को <math>b_i</math> यदि ये संरचनाएं समान हैं तो डुप्लिकेटर जीतता है; यदि वे नहीं हैं तो स्पॉइलर जीत जाता है।

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

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

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

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

== इतिहास ==

प्राथमिक तुल्यता को सत्यापित करने के लिए एहरनफेक्ट-फ्रैसे गेम में उपयोग की जाने वाली [[आगे-पीछे की विधि]] रोलांड फ्रैसे ने अपनी थीसिस में दी थी;<ref>''Sur une nouvelle classification des systèmes de relations'', Roland Fraïssé, ''Comptes Rendus'' '''230''' (1950), 1022&ndash;1024.</ref><ref>''Sur quelques classifications des systèmes de relations'', Roland Fraïssé, thesis, Paris, 1953;
published in ''Publications Scientifiques de l'Université d'Alger'', series A '''1''' (1954), 35&ndash;182.</ref>इसे [[आंद्रेज एहरनफ्यूच्ट]] द्वारा गेम के रूप में तैयार किया गया था।<ref>[http://matwbn.icm.edu.pl/ksiazki/fm/fm49/fm4919.pdf An application of games to the completeness problem for formalized theories], A. Ehrenfeucht, ''Fundamenta Mathematicae'' '''49''' (1961), 129&ndash;141.</ref> स्पॉइलर और डुप्लीकेटर नाम [[जोएल स्पेंसर]] के कारण हैं।<ref>[http://plato.stanford.edu/entries/logic-games/ Stanford Encyclopedia of Philosophy, entry on Logic and Games.]</ref> अन्य सामान्य नाम एलोइस [एसआईसी] और एबेलार्ड हैं (और प्रायः इन्हें इसके द्वारा दर्शाया जाता है)। <math>\exists</math> और <math>\forall</math>) [[हेलोइस और एबेलार्ड]] के पश्चात, [[विल्फ्रिड होजेस]] द्वारा अपनी पुस्तक मॉडल थ्योरी, या वैकल्पिक रूप से ईव और एडम में प्रस्तुत की गई नामकरण योजना है।

== अग्रिम पठन ==

[[Bruno Poizat|पोइज़ैट]] के मॉडल सिद्धांत पाठ के अध्याय 1 में<ref>''A Course in Model Theory'', Bruno Poizat, tr. Moses Klein, New York: 
Springer-Verlag, 2000.</ref>एहरनफ्यूच्ट-फ्रैसे गेम का परिचय सम्मिलित है, और इसी प्रकार रोसेनस्टीन की पुस्तक के अध्याय 6, 7, और 13 में [[Linear ordering|रैखिक क्रम]] पर है।<ref>''Linear Orderings'', Joseph G. Rosenstein, New York: Academic Press, 1982.</ref> इवार्स पीटरसन के मैथट्रेक कॉलम में से एरेनफ्यूचट-फ्रैसे गेम का सरल उदाहरण दिया गया है।<ref>[https://www.sciencenews.org/article/subtle-logic-winning-game Example of the Ehrenfeucht-Fraïssé game.]</ref>

फ़ोकियन कोलाइटिस की स्लाइड्स<ref>[http://www.cs.ucsc.edu/~kolaitis/talks/essllif.ps Course on combinatorial games in finite model theory by Phokion Kolaitis (.ps file)]</ref> और एहरनफ्यूच्ट-फ्रैसे गेम्स पर [[Neil Immerman|नील इम्रमैन]] की पुस्तक अध्याय<ref name="Immerman1999">{{cite book|author=Neil Immerman|title=Descriptive Complexity|title-link=Descriptive Complexity|contribution=Chapter 6: Ehrenfeucht–Fraïssé Games|contribution-url=https://books.google.com/books?id=kWSZ0OWnupkC&pg=PA91|year=1999|publisher=Springer|isbn=978-0-387-98600-5|pages=91–112}}</ref> कंप्यूटर विज्ञान में अनुप्रयोगों, अवर्णनीय परिणामों को सिद्ध करने की पद्धति और इस पद्धति का उपयोग करके कई सरल अवर्णनीय प्रमाणों पर वर्णन करते हैं।

एहरनफ्यूचट-फ्रैसे गेम [https://www.jstor.org/stable/1998979 मॉडलॉयड] पर व्युत्पन्न के संचालन का आधार हैं। मॉडलॉयड कुछ तुल्यता संबंध हैं और व्युत्पन्न मानक मॉडल सिद्धांत के सामान्यीकरण के लिए प्रदान करता है। 

== संदर्भ ==
<references />
* {{cite book | last1=Grädel | first1=Erich | last2=Kolaitis | first2=Phokion G. | last3=Libkin | first3=Leonid | last4=Maarten | first4=Marx | last5=Spencer | first5=Joel | author5-link=Joel Spencer | last6=Vardi | first6=Moshe Y. | author6-link=Moshe Y. Vardi | last7=Venema | first7=Yde | last8=Weinstein | first8=Scott | title=Finite model theory and its applications | zbl=1133.03001 | series=Texts in Theoretical Computer Science. An EATCS Series | location=Berlin | publisher=[[Springer-Verlag]] | isbn=978-3-540-00428-8 | year=2007 }}


==बाहरी संबंध==
* [http://pi.math.cornell.edu/~mec/Summer2009/Raluca/index.html Six Lectures on Ehrenfeucht-Fraïssé games] at MATH EXPLORERS' CLUB, Cornell Department of Mathematics.
*[https://www.jstor.org/stable/1998979 Modeloids] I, Miroslav Benda, Transactions of the American Mathematical Society, Vol. 250 (Jun 1979), pp.&nbsp;47 – 90 (44 pages)

{{DEFAULTSORT:Ehrenfeucht-Fraisse Game}}[[Category: मॉडल सिद्धांत]] 



[[Category: Machine Translated Page]]
[[Category:Created On 07/07/2023]]