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

Latest revision as of 10:11, 28 July 2023

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

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

मुख्य विचार

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

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

परिभाषा

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

प्रथम प्लेयर्स, स्पॉइलर, किसी सदस्य $a_{1}$ का ${\mathfrak {A}}$ या सदस्य $b_{1}$ का ${\mathfrak {B}}$ को चयन करता है।
यदि स्पॉइलर ने किसी सदस्य को ${\mathfrak {A}}$ , अनुलिपित्र सदस्य का चयन करता है $b_{1}$ का ${\mathfrak {B}}$ अन्यथा, अनुलिपित्र $a_{1}$ का ${\mathfrak {A}}$ सदस्य का चयन करता है।
स्पॉइलर किसी $a_{2}$ का ${\mathfrak {A}}$ या सदस्य $b_{2}$ का ${\mathfrak {B}}$ सदस्य का चयन करता है।
अनुलिपित्र $a_{2}$ या $b_{2}$ तत्व का चयन करता है उस मॉडल में जिसमें से स्पोइलर ने नहीं चयन किया।
स्पॉइलर और डुप्लीकेटर सदस्यों को ${\mathfrak {A}}$ और ${\mathfrak {B}}$ , $n-2$ के लिए चयन को प्रारंभ रखते हैं।
गेम के समापन पर, भिन्न-भिन्न तत्वों का चयन किया जाता है $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$ अवर्णनीय है।

इतिहास

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

अग्रिम पठन

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

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

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

संदर्भ

↑ Bosse, Uwe (1993). "An Ehrenfeucht–Fraïssé game for fixpoint logic and stratified fixpoint logic" (PDF). In Börger, Egon (ed.). Computer Science Logic: 6th Workshop, CSL'92, San Miniato, Italy, September 28 - October 2, 1992. Selected Papers. Lecture Notes in Computer Science. Vol. 702. Springer-Verlag. pp. 100–114. doi:10.1007/3-540-56992-8_8. ISBN 3-540-56992-8. Zbl 0808.03024.
↑ Sur une nouvelle classification des systèmes de relations, Roland Fraïssé, Comptes Rendus 230 (1950), 1022–1024.
↑ 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–182.
↑ An application of games to the completeness problem for formalized theories, A. Ehrenfeucht, Fundamenta Mathematicae 49 (1961), 129–141.
↑ Stanford Encyclopedia of Philosophy, entry on Logic and Games.
↑ A Course in Model Theory, Bruno Poizat, tr. Moses Klein, New York: Springer-Verlag, 2000.
↑ Linear Orderings, Joseph G. Rosenstein, New York: Academic Press, 1982.
↑ Example of the Ehrenfeucht-Fraïssé game.
↑ Course on combinatorial games in finite model theory by Phokion Kolaitis (.ps file)
↑ Neil Immerman (1999). "Chapter 6: Ehrenfeucht–Fraïssé Games". Descriptive Complexity. Springer. pp. 91–112. ISBN 978-0-387-98600-5.

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)

[1] Bosse, Uwe (1993). "An Ehrenfeucht–Fraïssé game for fixpoint logic and stratified fixpoint logic" (PDF). In Börger, Egon (ed.). Computer Science Logic: 6th Workshop, CSL'92, San Miniato, Italy, September 28 - October 2, 1992. Selected Papers. Lecture Notes in Computer Science. Vol. 702. Springer-Verlag. pp. 100–114. doi:10.1007/3-540-56992-8_8. ISBN 3-540-56992-8. Zbl 0808.03024.

[2] Sur une nouvelle classification des systèmes de relations, Roland Fraïssé, Comptes Rendus 230 (1950), 1022–1024.

[3] 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–182.

[4] An application of games to the completeness problem for formalized theories, A. Ehrenfeucht, Fundamenta Mathematicae 49 (1961), 129–141.

[5] Stanford Encyclopedia of Philosophy, entry on Logic and Games.

[6] A Course in Model Theory, Bruno Poizat, tr. Moses Klein, New York: Springer-Verlag, 2000.

[7] Linear Orderings, Joseph G. Rosenstein, New York: Academic Press, 1982.

[8] Example of the Ehrenfeucht-Fraïssé game.

[9] Course on combinatorial games in finite model theory by Phokion Kolaitis (.ps file)

[Immerman1999-10] Neil Immerman (1999). "Chapter 6: Ehrenfeucht–Fraïssé Games". Descriptive Complexity. Springer. pp. 91–112. ISBN 978-0-387-98600-5.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 1: / Line 1: @@
-[[मॉडल सिद्धांत]] के गणित अनुशासन में, एरेनफ्यूच्ट-फ्रैसे गेम (जिसे आगे-पीछे का खेल भी कहा जाता है)
+[[मॉडल सिद्धांत]] के गणित नियम में, '''एरेनफ्यूच्ट-फ्रैसे गेम''' (जिसे बैक-एंड-फ़ॉरवर्ड गेम भी कहा जाता है) यह निर्धारित करने के लिए [[खेल शब्दार्थ|गेम शब्दार्थ]] पर आधारित तकनीक है कि क्या दो [[संरचना (गणितीय तर्क)]] [[मौलिक रूप से समतुल्य|मौलिक रूप से]] [[मौलिक रूप से समतुल्य|समतुल्य]] हैं। एरेनफ्यूच्ट-फ़्राइसे गेम्स का मुख्य अनुप्रयोग [[प्रथम-क्रम तर्क]] में कुछ गुणों की अवर्णनीयता को सिद्ध करना है। वास्तव में, एरेनफ्यूच्ट-फ्रैसे गेम प्रथम-क्रम तर्क के लिए अव्यक्तता परिणामों को सिद्ध करने के लिए संपूर्ण पद्धति प्रदान करते हैं। इस भूमिका में, ये गेम [[परिमित मॉडल सिद्धांत]] और कंप्यूटर विज्ञान (विशेष रूप से [[औपचारिक सत्यापन|कंप्यूटर एडेड सत्यापन]] और [[डेटाबेस सिद्धांत]]) में इसके अनुप्रयोगों में विशेष महत्व रखते हैं, एरेनफुचट-फ्रैसे गेम मॉडल सिद्धांत की कुछ तकनीकों में से हैं जो संदर्भ में मान्य हैं परिमित मॉडल का अवर्णनीयता परिणामों को सिद्ध करने के लिए अन्य व्यापक रूप से उपयोग की जाने वाली तकनीकें, जैसे [[सघनता प्रमेय|सघनता]] [[सघनता प्रमेय|प्रमेय]], परिमित मॉडल में कार्य नहीं करती हैं।
-दो [[संरचना (गणितीय तर्क)]] का निर्धारण करने के लिए [[खेल शब्दार्थ]] पर आधारित एक तकनीक है
-[[मौलिक रूप से समतुल्य]] हैं। एरेनफ्यूच्ट-फ़्राइसे गेम्स का मुख्य अनुप्रयोग [[प्रथम-क्रम तर्क]] में कुछ गुणों की अवर्णनीयता को साबित करना है। वास्तव में, एरेनफ्यूच्ट-फ्रैसे गेम प्रथम-क्रम तर्क के लिए अव्यक्तता परिणामों को साबित करने के लिए एक संपूर्ण पद्धति प्रदान करते हैं। इस भूमिका में, ये गेम [[परिमित मॉडल सिद्धांत]] और कंप्यूटर विज्ञान (विशेष रूप से [[औपचारिक सत्यापन]] और [[डेटाबेस सिद्धांत]]) में इसके अनुप्रयोगों में विशेष महत्व रखते हैं, क्योंकि एहरनफुचट-फ्रैसे गेम मॉडल सिद्धांत की कुछ तकनीकों में से एक हैं जो के संदर्भ में मान्य हैं। परिमित मॉडल. अवर्णनीयता परिणामों को साबित करने के लिए अन्य व्यापक रूप से उपयोग की जाने वाली तकनीकें, जैसे [[सघनता प्रमेय]], परिमित मॉडल में काम नहीं करती हैं।
-एरेनफ्यूच्ट-फ़्रासे-जैसे गेम को अन्य तर्कों के लिए भी परिभाषित किया जा सकता है, जैसे [[ फिक्सपॉइंट तर्क ]]्स<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> और परिमित परिवर्तनीय तर्क के लिए [[कंकड़ खेल]]; एक्सटेंशन अस्तित्व संबंधी दूसरे क्रम के तर्क में निश्चितता को दर्शाने के लिए पर्याप्त शक्तिशाली हैं।
+एहरनफ्यूच्ट-फ़्रासे-जैसे गेम को अन्य तर्कों के लिए भी परिभाषित किया जा सकता है, जैसे [[ फिक्सपॉइंट तर्क |फिक्सपॉइंट लॉजिक्स]]<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>\gamma</math> निश्चित संख्या में चरणों तक चलता (जो क्रमसूचक है- सामान्यतः सीमित संख्या या <math>\omega</math>) है।
 == परिभाषा ==
-मान लीजिए कि हमें दो संरचनाएँ दी गई हैं <math>\mathfrak{A}</math> और <math>\mathfrak{B}</math>, प्रत्येक में कोई [[फ़ंक्शन (गणित)]] प्रतीक नहीं हैं और [[संबंध (गणित)]] प्रतीकों का एक ही सेट है,
+मान लीजिए कि दो संरचनाएँ दी गई हैं <math>\mathfrak{A}</math> और <math>\mathfrak{B}</math>, प्रत्येक में कोई [[फ़ंक्शन (गणित)|फलन (गणित)]] प्रतीक नहीं हैं और [[संबंध (गणित)]] प्रतीकों का समुच्चय है, और निश्चित प्राकृतिक संख्या n है। फिर हम एरेनफ्यूच्ट-फ्रैसे गेम को परिभाषित कर सकते हैं गेम <math>G_n(\mathfrak{A},\mathfrak{B})</math> दो प्लेयर्स, स्पॉइलर और डुप्लिकेटर के मध्य गेम है, जो इस प्रकार खेला जाता है:
-और एक निश्चित प्राकृत संख्या n. फिर हम एरेनफ्यूच्ट-फ्रैस्से को परिभाषित कर सकते हैं
+# प्रथम प्लेयर्स, स्पॉइलर, किसी सदस्य <math>a_1</math> का <math>\mathfrak{A}</math> या सदस्य <math>b_1</math> का <math>\mathfrak{B}</math> को चयन करता है।
-खेल <math>G_n(\mathfrak{A},\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_1</math> का <math>\mathfrak{A}</math> या एक सदस्य <math>b_1</math> का <math>\mathfrak{B}</math>.
+# अनुलिपित्र <math>a_2</math> या <math>b_2</math> तत्व का चयन करता है उस मॉडल में जिसमें से स्पोइलर ने नहीं चयन किया।
-# यदि स्पॉइलर ने किसी सदस्य को चुना <math>\mathfrak{A}</math>, अनुलिपित्र एक सदस्य चुनता है <math>b_1</math> का <math>\mathfrak{B}</math>; अन्यथा, अनुलिपित्र एक सदस्य चुनता है <math>a_1</math> का <math>\mathfrak{A}</math>.
+# स्पॉइलर और डुप्लीकेटर सदस्यों को <math>\mathfrak{A}</math> और <math>\mathfrak{B}</math>, <math>n-2</math> के लिए चयन को प्रारंभ रखते हैं।
-# स्पॉइलर किसी एक सदस्य को चुनता है <math>a_2</math> का <math>\mathfrak{A}</math> या एक सदस्य <math>b_2</math> का <math>\mathfrak{B}</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> यदि ये संरचनाएं समान हैं तो डुप्लिकेटर जीतता है; यदि वे नहीं हैं तो स्पॉइलर जीत जाता है।
-# डुप्लीकेटर एक तत्व चुनता है <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> यदि डुप्लिकेटर एन-मूव गेम जीतता है <math>G_n(\mathfrak{A},\mathfrak{B})</math>. ये सभी दिए गए संबंध प्रतीकों के साथ संरचनाओं के वर्ग पर समतुल्य संबंध हैं। इन सभी संबंधों का प्रतिच्छेदन पुनः एक तुल्यता संबंध है <math>\mathfrak{A} \sim \mathfrak{B}</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> मौलिक रूप से समतुल्य हैं। यदि माना जा रहा संबंध प्रतीकों का सेट सीमित है, तो इसका विपरीत भी सत्य है।
+यह सिद्ध करना सरल है कि यदि डुप्लिकेटर इस गेम को सभी परिमित 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> इस गेम द्वारा कैप्चर किए गए तर्क में यह अवर्णनीय है।{{explain|reason=How does the game "capture" the logic? Isn't the logic instead _used_ by the game?|date=June 2021}}
+यदि कोई गुण <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;
-उनकी थीसिस में;<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>) [[हेलोइस और एबेलार्ड]] के पश्चात, [[विल्फ्रिड होजेस]] द्वारा अपनी पुस्तक मॉडल थ्योरी, या वैकल्पिक रूप से ईव और एडम में प्रस्तुत की गई नामकरण योजना है।
-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>) [[हेलोइस और एबेलार्ड]] के बाद, [[विल्फ्रिड होजेस]] द्वारा अपनी पुस्तक मॉडल थ्योरी, या वैकल्पिक रूप से ईव और एडम में पेश की गई एक नामकरण योजना।
 == अग्रिम पठन ==
-Chapter 1 of [[Bruno Poizat|Poizat]]'s model theory text<ref>''A Course in Model Theory'', Bruno Poizat, tr. Moses Klein, New York:
+[[Bruno Poizat|पोइज़ैट]] के मॉडल सिद्धांत पाठ के अध्याय 1 में<ref>''A Course in Model Theory'', Bruno Poizat, tr. Moses Klein, New York:
-Springer-Verlag, 2000.</ref> contains an introduction to the Ehrenfeucht–Fraïssé game, and so do Chapters 6, 7, and 13 of Rosenstein's book on [[Linear ordering|linear orders]].<ref>''Linear Orderings'', Joseph G. Rosenstein, New York: Academic Press, 1982.</ref>  A simple example of the Ehrenfeucht–Fraïssé game is given in one of Ivars Peterson's MathTrek columns.<ref>[https://www.sciencenews.org/article/subtle-logic-winning-game Example of the Ehrenfeucht-Fraïssé game.]</ref>
+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>
-Phokion Kolaitis' slides<ref>[http://www.cs.ucsc.edu/~kolaitis/talks/essllif.ps Course on combinatorial games in finite model theory by Phokion Kolaitis (.ps file)]</ref> and [[Neil Immerman]]'s book chapter<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> 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. [https://www.jstor.org/stable/1998979 Modeloids] are certain equivalence relations and the derivative provides for a generalization of standard model theory.
+फ़ोकियन कोलाइटिस की स्लाइड्स<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 मॉडलॉयड] पर व्युत्पन्न के संचालन का आधार हैं। मॉडलॉयड कुछ तुल्यता संबंध हैं और व्युत्पन्न मानक मॉडल सिद्धांत के सामान्यीकरण के लिए प्रदान करता है।
 == संदर्भ ==
@@ Line 55: / Line 49: @@
 *[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: मॉडल सिद्धांत]]
+{{DEFAULTSORT:Ehrenfeucht-Fraisse Game}}
-[[Category: Machine Translated Page]]
+[[Category:Created On 07/07/2023|Ehrenfeucht-Fraisse Game]]
-[[Category:Created On 07/07/2023]]
+[[Category:Machine Translated Page|Ehrenfeucht-Fraisse Game]]
+[[Category:Templates Vigyan Ready|Ehrenfeucht-Fraisse Game]]
+[[Category:मॉडल सिद्धांत|Ehrenfeucht-Fraisse Game]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 10:11, 28 July 2023

Contents

मुख्य विचार

परिभाषा

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

इतिहास

अग्रिम पठन

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 10:11, 28 July 2023

मुख्य विचार

परिभाषा

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

इतिहास

अग्रिम पठन

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories