Finite promise games and greedy clique sequences
फाइनाइट प्रॉमिस गेम्स 2009 में अमेरिकी गणितशास्त्री हार्वे फ्रीडमैन द्वारा विकसित गणितीय खेलों का एक संग्रह है जिसका उपयोग तेजी से बढ़ते कार्यों के एक परिवार को विकसित करने के लिए किया जाता है। लालची गुट अनुक्रम एक ग्राफ सिद्धांत अवधारणा है, जिसे 2010 में फ्रीडमैन द्वारा भी विकसित किया गया था, जिसका उपयोग तेजी से बढ़ते कार्यों को विकसित करने के लिए किया जाता है। जेडएफसी प्लस के सिद्धांत का प्रतिनिधित्व करता है, प्रत्येक के लिए, "एक दृढ़ता से-माहलो कार्डिनल है", और जेडएफसी प्लस के सिद्धांत का प्रतिनिधित्व करता है "प्रत्येक के लिए, एक दृढ़ता से-माहलो कार्डिनल है"। जेडएफसी प्लस के सिद्धांत का प्रतिनिधित्व करता है, प्रत्येक के लिए, "एक-स्थिर रैमसे कार्डिनल है", और जेडएफसी प्लस के सिद्धांत का प्रतिनिधित्व करता है "प्रत्येक के लिए, एक दृढ़ता से-स्थिर रैमसे कार्डिनल है"। जेडएफसी प्लस के सिद्धांत का प्रतिनिधित्व करता है, प्रत्येक के लिए, "एक-विशाल कार्डिनल है", और जेडएफसी प्लस के सिद्धांत का प्रतिनिधित्व करता है "प्रत्येक के लिए, एक मजबूत-विशाल कार्डिनल है"। प्रत्येक खेल सीमित है, लंबाई में पूर्व निर्धारित है, और इसमें दो खिलाड़ी (एलिस और बॉब) हैं। प्रत्येक मोड़ पर, एलिस एक पूर्णांक या कई पूर्णांक (एक प्रस्ताव) चुनती है और बॉब को अपने भविष्य की संभावित चालों को सीमित करने वाले दो प्रकार के वादों में से एक करना होता है। सभी खेलों में, बॉब तभी जीतता है जब बॉब ने अपने सभी वादे पूरे किए हों। यहाँ, पूर्णांकों का समुच्चय है, और गैर-नकारात्मक पूर्णांकों का समुच्चय है। यहाँ, सभी अक्षर पूर्णांक का प्रतिनिधित्व करते हैं। हम कहते हैं कि एक नक्शा टुकड़ों में रैखिक है यदि इसे सीमित रूप से कई टुकड़ों में से प्रत्येक पर पूर्णांक गुणांक के साथ विभिन्न एफ़ाइन कार्यों द्वारा परिभाषित किया जा सकता है, जहां प्रत्येक टुकड़े को पूर्णांक गुणांक के साथ रैखिक असमानताओं के एक सीमित सेट द्वारा परिभाषित किया जाता है। कुछ टुकड़ों में रैखिक मानचित्र के लिए, का एक-व्युत्क्रम कुछ ऐसा है। फिर हम गैर-शून्य के लिए खेल को परिभाषित करते हैं। इसमें राउंड होते हैं, और एलिस और बॉब के बीच बारी-बारी से होते हैं। खेल के प्रत्येक चरण में, एलिस को खेलने की आवश्यकता होती है, जिसे उसकी पेशकश कहा जाता है, जो या तो रूप का होता है या, जहां और पूर्णांक होते हैं जो पहले बॉब द्वारा खेले जाते थे। बॉब को तब दोनों में से किसी एक को स्वीकार करने की आवश्यकता होती है, जिससे वह खेलता है और वादा करता है कि बॉब द्वारा कभी खेले गए पूर्णांकों में से कोई-व्युत्क्रम नहीं होगा। यह वादा खेल में सभी पिछले, वर्तमान और भविष्य के खेलों पर लागू होता है। अस्वीकार करें, इस प्रकार एक-व्युत्क्रम और आशाजनक खेल खेलते हैं जो बॉब द्वारा कभी नहीं खेला जाता है। आरसीए0 में, यह साबित किया जा सकता है कि बॉब के पास हमेशा किसी भी खेल के लिए जीतने की रणनीति होती है। खेल एक संशोधित संस्करण है जहाँ बॉब को एलिस द्वारा सभी फैक्टोरियल प्रस्तावों को स्वीकार करने के लिए मजबूर किया जाता है। बॉब के पास हमेशा पर्याप्त रूप से बड़े के लिए एक जीत की रणनीति होती है, हालांकि यह किसी भी निरंतर टुकड़े में साबित नहीं किया जा सकता है, और केवल। फलन सबसे छोटा ऐसा होता है कि बॉब किसी भी ऐसे के लिए जीत सकता है जो उससे बड़ा या बराबर होता है और निम्नलिखित सभी मान इससे कम होते हैंः (का क्षेत्र) सीमित बहुपद प्रतिलिपि/व्युत्क्रम खेलों में एफ़ाइन फलन के गुणांकों के निरपेक्ष मूल्यों में असमानताओं के गुणांकों के निरपेक्ष मूल्यों के टुकड़ों की संख्या। एक विशेष-व्युत्क्रम में ऐसा होता है। अब हम गैर-शून्य के लिए खेल को परिभाषित करते हैं, जहाँ पूर्णांक गुणांक वाले बहुपद हैं। इसमें एलिस और बॉब के बारी-बारी से नाटक शामिल हैं। खेल के प्रत्येक चरण में, एलिस को उस रूप में खेलना आवश्यक है, या, जहां पहले बॉब द्वारा खेले गए पूर्णांकों का एक-टुपल है। बॉब को तब दोनों में से किसी एक को स्वीकार करने की आवश्यकता होती है, जिससे वह खेलता है और वादा करता है कि बॉब द्वारा खेले गए पूर्णांकों में से कोई विशेष-या-व्युत्क्रम नहीं होगा। यह वादा खेल में सभी पिछले, वर्तमान और भविष्य के खेलों पर लागू होता है। अस्वीकार करें, जिससे एक विशेष-या-व्युत्क्रम और आशाजनक खेल खेलते हैं जो बॉब द्वारा कभी नहीं खेला जाता है। मान लीजिए कि पूर्णांक गुणांक वाले बहुपद हैं। आरसीए0 में, यह साबित किया जा सकता है कि बॉब के पास हमेशा किसी भी खेल के लिए जीतने की रणनीति होती है। यदि पर्याप्त रूप से बड़े हैं तो बॉब जीत जाता है, जहां बॉब को एलिस द्वारा दिए गए सभी दोहरे फैक्टोरियल को स्वीकार करने के लिए मजबूर किया जाता है। हालांकि, एक बार फिर, यह किसी भी दिए गए सुसंगत टुकड़े में और केवल साबित नहीं किया जा सकता है। फलन सबसे छोटा ऐसा है कि बॉब किसी भी ऐसे के लिए जीत सकता है जो उससे बड़ा या बराबर है और निम्नलिखित सभी मान इससे कम हैंः (बहुपदों का क्षेत्र है) गुणांक की डिग्री और निरपेक्ष मान और सीमित रैखिक प्रतिलिपि/व्युत्क्रम खेल हम कहते हैं कि योगात्मक रूप से समतुल्य हैं यदि और केवल यदि। गैर-शून्य पूर्णांकों के लिए और, हम उस खेल को परिभाषित करते हैं जिसमें एलिस और बॉब के बीच बारी-बारी से दौर होते हैं। खेल के प्रत्येक चरण में, एलिस को रूप का एक पूर्णांक खेलना आवश्यक है या, जहां पहले बॉब द्वारा खेले गए पूर्णांक हैं। बॉब को तब दोनों में से किसी एक को स्वीकार करने की आवश्यकता होती है, जिससे खेलना और वादा करना जिसे इस रूप में नहीं लिखा जा सकता है, जहां कुछ के अतिरिक्त समतुल्य है, और विभिन्न समय पर बॉब द्वारा खेले जाने वाले पूर्णांक हैं। अस्वीकार करें, जिससे खेलना, कहाँ और अतिरिक्त रूप से कुछ के बराबर है, और वादा करता है जो बॉब द्वारा कभी नहीं खेला जाता है। जाने दीजिए। आरसीए0 में, यह साबित किया जा सकता है कि बॉब के पास हमेशा किसी भी खेल के लिए जीतने की रणनीति होती है। जाने दीजिए। यदि पर्याप्त रूप से बड़ा है, तो बॉब जीत जाता है, जहां बॉब एलिस द्वारा दिए गए सभी फैक्टोरियल को स्वीकार करता है। हालांकि, एक बार फिर, यह किसी भी दिए गए सुसंगत टुकड़े में और केवल साबित नहीं किया जा सकता है। फलन सबसे छोटा ऐसा है कि बॉब किसी भी ऐसे कार्य के लिए जीत सकता है जो उससे बड़ा या बराबर है, सकारात्मक है और निम्नलिखित सभी मान उससे कम हैंः कार्य में प्रत्येक सदिश के घटकों की संख्या जैसा कि फ्रीडमैन द्वारा दिखाया गया है, तीन कार्य, और बेहद तेजी से बढ़ रहे हैं, अंततः किसी भी कार्य पर हावी होते हैं जो किसी भी सुसंगत टुकड़े में पुनरावर्ती साबित होते हैं (इनमें से एक जेडएफसी है), लेकिन वे गणना योग्य और कुल में सिद्ध होते हैं। लालची गुट अनुक्रम परिमेय संख्याओं के सभी टुपलों के समूह को दर्शाते हैं। हम अनुक्रमणिकाओं को टुपल्स (1 से शुरू) और कोण कोष्ठकों में निरूपित करने के लिए अभिलिखियों का उपयोग करते हैं, जैसे कि टुपल्स के संयोजन को निरूपित करने के लिए। .. दिए गए, हम के ऊपरी बदलाव को परिभाषित करते हैं, जिसे इसके सभी गैर-नकारात्मक घटकों में 1 जोड़ने का परिणाम माना जाता है। दिए गए, हम कहते हैं कि और। इन्हें क्रम समतुल्य कहा जाता है यदि और केवल तभी जब उनकी लंबाई समान हो और सभी के लिए, आई. एफ. एफ। एक समुच्चय सभी क्रम समतुल्य और, के लिए क्रम अपरिवर्तनीय आई. एफ. एफ है। मान लीजिए कि यह एक ग्राफ है जिसमें शीर्ष हैं। मान लीजिए कि सेट को निम्नानुसार परिभाषित किया गया हैः प्रत्येक किनारे के लिए, उनका संयोजन में होता है। फिर यदि क्रम अपरिवर्तनीय है, तो हम कहते हैं कि यह क्रम अपरिवर्तनीय है। जब क्रम अपरिवर्तनीय होता है, तो उसके अनंत किनारे होते हैं। हमें दिया गया है, और शीर्षों के साथ एक सरल ग्राफ (या ऊपरी पारी लालची नीचे गुट अनुक्रमों के मामले में एक डिग्राफ)। हम एक अनुक्रम को एक गैर-खाली टुपल के रूप में परिभाषित करते हैं। यह एक टुपल नहीं है, बल्कि टुपल का एक टुपल है। जब, को एक ऊपरी पारी लालची गुट अनुक्रम कहा जाता है यदि यह निम्नलिखित को संतुष्ट करता हैः इसमें केवल शून्य होते हैं। मान लीजिए कि यह एक पूर्णांक है, या एक सकारात्मक पूर्णांक है यदि हम अनंत अनुक्रमों की अनुमति देते हैं। और जाने दीजिए। फिर, और का किनारा नहीं है। में एक गुट है, अर्थात। शीर्षों की प्रत्येक जोड़ी एक किनारे के रूप में होती है। जब, लालची गुट अनुक्रम में एक ऊपरी बदलाव कहा जाता है यदि यह निम्नलिखित को संतुष्ट करता हैः इसमें केवल शून्य होते हैं। मान लीजिए कि यह एक पूर्णांक है, या एक सकारात्मक पूर्णांक है यदि हम अनंत अनुक्रमों की अनुमति देते हैं। और जाने दीजिए। फिर, या और का एक किनारा नहीं है; और। एक डाउन क्लीक है, अर्थात। सभी के लिए और, का एक किनारा है। जब, लालची गुट अनुक्रम में एक चरम ऊपरी बदलाव कहा जाता है यदि यह निम्नलिखित को संतुष्ट करता हैः इसमें केवल शून्य होते हैं। मान लीजिए कि यह एक पूर्णांक है, या एक सकारात्मक पूर्णांक है यदि हम अनंत अनुक्रमों की अनुमति देते हैं। और जाने दीजिए। फिर, या और का एक किनारा नहीं है; और। अगर, तो। अगर, तो। अगर और, तो एक डाउन क्लीक है द थ्रेड ऑफ एक अनुगामी है जिसे प्रेरक रूप से इस तरह परिभाषित किया गया हैः एक धागे को देखते हुए, हम कहते हैं कि खुला है यदि। इसका उपयोग करते हुए हार्वे फ्रीडमैन ने तीन बहुत शक्तिशाली कार्यों को परिभाषित कियाः सबसे छोटा ऐसा है कि प्रत्येक सरल, क्रम अपरिवर्तनीय ग्राफ में एक खुले धागे के साथ अधिकतम लंबाई में एक ऊपरी पारी लालची गुट अनुक्रम होता है। सबसे छोटा ऐसा है कि प्रत्येक क्रम अपरिवर्तनीय डिग्राफ में एक खुले धागे के साथ अधिकतम लंबाई में एक ऊपरी शिफ्ट लालची नीचे गुट अनुक्रम होता है। सबसे छोटा ऐसा है कि प्रत्येक क्रम अपरिवर्तनीय डिग्राफ में एक खुले धागे के साथ अधिकतम लंबाई में एक अत्यधिक ऊपरी पारी लालची नीचे गुट अनुक्रम होता है। और अंततः सभी कार्यों पर हावी हो जाते हैं जो प्रमाणित रूप से पुनरावर्ती होते हैं, लेकिन स्वयं प्रमाणित रूप से पुनरावर्ती होते हैं। अंततः सभी कार्यों पर हावी हो जाता है जो प्रमाणित रूप से पुनरावर्ती होते हैं, लेकिन अपने आप में सिद्ध रूप से कुल होते हैं। संदर्भ गणितीय खेल गणितीय अवधारणाएँ