Finite promise games and greedy clique sequences
محدود وعدے کے کھیل ریاضیاتی کھیلوں کا ایک مجموعہ ہے جو امریکی ریاضی دان ہاروی فریڈمین نے 2009 میں تیار کیا تھا جو تیزی سے بڑھتے ہوئے افعال کے خاندان کو تیار کرنے کے لیے استعمال ہوتے ہیں۔ لالچی گروہ کی ترتیب ایک گراف تھیوری کا تصور ہے، جسے فریڈمین نے بھی 2010 میں تیار کیا تھا، جو تیزی سے بڑھتے ہوئے افعال کو تیار کرنے کے لیے استعمال ہوتے ہیں، اور۔ ZFC پلس کے نظریہ کی نمائندگی کرتا ہے، ہر ایک کے لیے، "ایک مضبوطی سے-ماہلو کارڈینل ہے"، اور ZFC پلس کے نظریہ کی نمائندگی کرتا ہے "ہر ایک کے لیے، ایک مضبوطی سے-ماہلو کارڈینل ہے"۔ ZFC پلس کے نظریہ کی نمائندگی کرتا ہے، ہر ایک کے لیے، "ایک-اسٹیشنری رمسی کارڈینل ہے"، اور ZFC پلس کے نظریہ کی نمائندگی کرتا ہے "ہر ایک کے لیے، ایک مضبوطی سے-اسٹیشنری رمسی کارڈینل ہے"۔ ZFC پلس کے نظریہ کی نمائندگی کرتا ہے، ہر ایک کے لیے، "ایک بہت بڑا کارڈینل ہے"، اور ZFC پلس کے نظریہ کی نمائندگی کرتا ہے "ہر ایک کے لیے، ایک بہت بڑا کارڈینل ہے"۔ ہر کھیل محدود ہے، لمبائی میں پہلے سے طے شدہ ہے، اور اس میں دو کھلاڑی (ایلس اور باب) ہیں۔ ہر موڑ پر، ایلس ایک عدد یا متعدد عدد (ایک پیشکش) کا انتخاب کرتی ہے اور باب کو اپنے مستقبل کی ممکنہ چالوں کو محدود کرنے والے دو قسم کے وعدوں میں سے ایک کرنا ہوتا ہے۔ تمام کھیلوں میں، باب صرف اس صورت میں جیتتا ہے جب باب نے اپنے تمام وعدے پورے کیے ہوں۔ محدود ٹکڑے ٹکڑے لکیری کاپی/الٹا کھیل یہاں، انٹیجرز کا مجموعہ ہے، اور غیر منفی انٹیجرز کا مجموعہ ہے۔ یہاں تمام حروف انٹیجرز کی نمائندگی کرتے ہیں۔ ہم کہتے ہیں کہ نقشہ ٹکڑے ٹکڑے لکیری ہوتا ہے اگر اس کی تعریف مختلف افائن افعال کے ذریعے کی جا سکتی ہے جس میں ہر ایک پر انٹیجر کوفیشنٹس ہوتے ہیں، جہاں ہر ٹکڑے کی تعریف انٹیجر کوفیشنٹس کے ساتھ لکیری عدم مساوات کے ایک محدود سیٹ کے ذریعے کی جاتی ہے۔ کچھ ٹکڑے ٹکڑے لکیری نقشے کے لیے، کا-الٹ کچھ ایسا ہوتا ہے۔ اس کے بعد ہم نان زیرو کے لیے گیم کی وضاحت کرتے ہیں۔ راؤنڈ ہوتے ہیں، اور ایلس اور باب کے درمیان باری باری ہوتے ہیں۔ کھیل کے ہر مرحلے پر، ایلس کو کھیلنے کی ضرورت ہوتی ہے، جسے اس کی پیشکش کہا جاتا ہے، جو یا تو شکل کا ہے یا، جہاں اور انٹیجر ہیں جو پہلے باب نے کھیلے تھے۔ اس کے بعد باب کو دونوں میں سے کسی ایک کو قبول کرنے کی ضرورت ہوتی ہے، اس طرح کھیلنا اور وعدہ کرنا کہ باب کے ذریعے کھیلے گئے انٹیجرز میں کوئی تبدیلی نہیں ہوگی۔ یہ وعدہ کھیل کے تمام ماضی، حال اور مستقبل کے کھیلوں پر لاگو ہوتا ہے۔ مسترد کریں، اس طرح باب کی طرف سے کبھی نہیں ادا کیا جاتا ہے کہ کا ایک الٹ اور وعدہ کھیلتے ہیں. آر سی اے 0 میں، یہ ثابت کیا جا سکتا ہے کہ باب کے پاس ہمیشہ کسی بھی کھیل کے لیے جیت کی حکمت عملی ہوتی ہے۔ یہ گیم ایک ترمیم شدہ ورژن ہے جہاں باب کو ایلس کی تمام فیکٹوریئل پیشکشوں کو قبول کرنے پر مجبور کیا جاتا ہے۔ باب کے پاس ہمیشہ کافی بڑے کے لیے جیتنے کی حکمت عملی ہوتی ہے، حالانکہ یہ کسی بھی مستقل ٹکڑے میں ثابت نہیں کیا جا سکتا، اور صرف۔ فنکشن اس طرح کا سب سے چھوٹا ہے کہ باب کسی بھی ایسی چیز کے لیے جیت سکتا ہے جو اس سے زیادہ یا اس کے برابر ہو اور مندرجہ ذیل تمام اقدار اس سے کم ہیں: (کا ڈومین ہے) غیر مساوات کے کوفشنٹس کی مطلق اقدار کے ٹکڑوں کی تعداد میں فینیٹ کثیر الجہتی کاپی/الٹا کھیلوں میں افائن افعال کے کوفشنٹس کی مطلق اقدار۔ ایک خاص-الٹ میں اس طرح پر مشتمل ہوتا ہے۔ اب ہم نان زیرو کے لیے گیم کی وضاحت کرتے ہیں، جہاں انٹیجر کوفشنٹس کے ساتھ کثیر الجہتی ہوتے ہیں۔ یہ ایلس اور باب کے باری باری ڈراموں پر مشتمل ہے۔ کھیل کے ہر مرحلے پر، ایلس کو اس شکل میں کھیلنے کی ضرورت ہوتی ہے، یا، جہاں پہلے باب کے ذریعے کھیلے گئے انٹیجرز کا ایک-ٹپل ہوتا ہے۔ اس کے بعد باب کو یا تو: قبول کرنے کی ضرورت ہوتی ہے، اس طرح کھیلنا اور وعدہ کرنا کہ باب کے ذریعہ کھیلے گئے انٹیجرز میں سے کوئی خاص-یا-الٹ نہیں ہوگا۔ یہ وعدہ کھیل کے تمام ماضی، حال اور مستقبل کے کھیلوں پر لاگو ہوتا ہے۔ مسترد کریں، اس طرح ایک خاص-یا-الٹ اور وعدہ کرنا جو باب نے کبھی نہیں کھیلا ہے۔ آئیے انٹیجر کوفشنٹس کے ساتھ کثیر الجہتی ہوں۔ آر سی اے 0 میں، یہ ثابت کیا جا سکتا ہے کہ باب کے پاس ہمیشہ کسی بھی کھیل کے لیے جیت کی حکمت عملی ہوتی ہے۔ اگر کافی بڑے ہیں تو باب جیت جاتا ہے، جہاں باب ایلس کی طرف سے پیش کردہ تمام ڈبل فیکٹوریئلز کو قبول کرنے پر مجبور ہوتا ہے۔ تاہم، ایک بار پھر، یہ کسی بھی مستقل ٹکڑے میں، اور صرف ثابت نہیں کیا جا سکتا۔ فنکشن اس طرح کا سب سے چھوٹا ہے کہ باب کسی بھی ایسی چیز کے لیے جیت سکتا ہے جو اس سے زیادہ یا اس کے برابر ہو اور مندرجہ ذیل تمام اقدار اس سے کم ہیں: (کثیر الجہتی کا ڈومین ہے) ڈگری اور کوفیشنٹس کی مطلق اقدار اور لکیری کاپی/الٹا گیمز کو ختم کریں ہم کہتے ہیں کہ اضافی طور پر مساوی ہیں اگر اور صرف اگر۔ غیر صفر انٹیجرز کے لیے اور، ہم اس کھیل کی وضاحت کرتے ہیں جو ایلس اور باب کے درمیان باری باری راؤنڈز پر مشتمل ہوتا ہے۔ کھیل کے ہر مرحلے پر، ایلس کو فارم کا ایک انٹیجر کھیلنے کی ضرورت ہوتی ہے یا جہاں پہلے باب کے ذریعے کھیلے جانے والے انٹیجر ہوتے ہیں۔ اس کے بعد باب کو یا تو کرنا پڑتا ہے: قبول کریں، اس طرح کھیلنا اور وعدہ کرنا جسے اس طرح نہیں لکھا جا سکتا، جہاں اضافی طور پر کچھ کے مساوی ہے، اور مختلف اوقات میں باب کے ذریعہ کھیلے جانے والے عدد ہیں۔ مسترد کریں، اس طرح کھیلنا، کہاں اور اضافی طور پر کچھ کے مساوی ہے، اور وعدہ کرتا ہے جو باب نے کبھی نہیں ادا کیا ہے۔ جانے دیں۔ آر سی اے 0 میں، یہ ثابت کیا جا سکتا ہے کہ باب کے پاس ہمیشہ کسی بھی کھیل کے لیے جیت کی حکمت عملی ہوتی ہے۔ جانے دیں۔ اگر کافی بڑا ہے، تو باب جیت جاتا ہے، جہاں باب ایلس کی طرف سے پیش کردہ تمام فیکٹوریلز کو قبول کرتا ہے۔ تاہم، ایک بار پھر، یہ کسی بھی مستقل ٹکڑے میں، اور صرف ثابت نہیں کیا جا سکتا۔ فنکشن اس طرح کا سب سے چھوٹا ہے کہ باب کسی بھی ایسی چیز کے لیے جیت سکتا ہے جو اس سے زیادہ یا اس کے برابر ہو، مثبت ہو اور مندرجہ ذیل تمام اقدار اس سے کم ہوں: فنکشنز میں ہر ویکٹر کے اجزاء کی تعداد جیسا کہ فریڈمین نے دکھایا ہے، تینوں فنکشنز، اور انتہائی تیزی سے بڑھ رہے ہیں، بالآخر کسی بھی فنکشن پر غالب ہوتے ہیں جو کسی بھی مستقل ٹکڑے (ان میں سے ایک ZFC ہے) میں ثابت طور پر بار بار ہوتے ہیں، لیکن وہ قابل حساب اور ثابت طور پر کل ہوتے ہیں۔ لالچی گروہ کے سلسلے عقلی اعداد کے تمام ٹپل کے سیٹ کی نشاندہی کرتے ہیں۔ ہم سبسکرپٹس کا استعمال انڈیکس کو ٹپل (1 سے شروع ہونے والے) اور اینگل بریکٹ میں ظاہر کرنے کے لیے کرتے ہیں تاکہ ٹپل کے ارتکاز کو ظاہر کیا جا سکے، مثال کے طور پر۔ ۔ دی گئی ہے، ہم کی اوپری شفٹ کی وضاحت کرتے ہیں، جو اس کے تمام غیر منفی اجزاء میں 1 کو شامل کرنے کا نتیجہ ہے۔ دی گئی، ہم یہ کہتے ہیں اور۔ آرڈر کو مساوی کہا جاتا ہے اگر اور صرف اس صورت میں جب ان کی لمبائی ایک جیسی ہو اور سب کے لیے، آئی ایف ایف۔ ایک سیٹ تمام آرڈر کے مساوی اور، کے لیے آرڈر غیر متغیر آئی ایف ایف ہے۔ آئیے ایک گراف جس میں عمودی نقاط ہوں۔ سیٹ کو اس طرح بیان کیا جائے: اندر کے ہر کنارے کے لیے، ان کا امتزاج اندر ہوتا ہے۔ پھر اگر آرڈر غیر متغیر ہے، تو ہم کہتے ہیں کہ یہ آرڈر غیر متغیر ہے۔ آرڈر کب غیر متغیر ہوتا ہے، اس کے کنارے لامحدود ہوتے ہیں۔ ہمیں دیا گیا ہے، اور ایک سادہ گراف (یا اوپری شفٹ لالچی نیچے کلیک کے سلسلے کی صورت میں ایک ڈیگراف) جس میں عمودی حصے ہیں۔ ہم ایک ترتیب کو غیر خالی ٹپل کے طور پر بیان کرتے ہیں۔ یہ ٹپل نہیں بلکہ ٹپل کا ٹپل ہے۔ جب، ایک اوپری شفٹ لالچی گروہ کی ترتیب کہا جاتا ہے اگر یہ مندرجہ ذیل کو مطمئن کرتا ہے: صرف صفر پر مشتمل ہوتا ہے۔ اگر ہم لامحدود ترتیبات کی اجازت دیتے ہیں تو ایک انٹیجر کو اس طرح، یا ایک مثبت انٹیجر ہونے دیں۔ اور جانے دیں۔ پھر، اور کا کنارہ نہیں ہے۔ میں ایک گروہ ہے، یعنی۔ ایک کنارے کے طور پر عمودی کے ہر جوڑے پر مشتمل ہے۔ جب، لالچی گروہ کے سلسلے میں ایک اوپری شفٹ کہا جاتا ہے اگر یہ مندرجہ ذیل کو مطمئن کرتا ہے: صرف صفر پر مشتمل ہوتا ہے۔ اگر ہم لامحدود ترتیبات کی اجازت دیتے ہیں تو ایک انٹیجر کو اس طرح، یا ایک مثبت انٹیجر ہونے دیں۔ اور جانے دیں۔ پھر، یا اور کا کنارہ نہیں ہے ؛ اور۔ ایک ڈاؤن کلک ہے، یعنی۔ سب کے لیے اور، کا ایک کنارے ہے۔ جب، لالچی گروہ کے سلسلے میں ایک انتہائی اوپری شفٹ کہا جاتا ہے اگر یہ مندرجہ ذیل کو مطمئن کرتا ہے: صرف صفر پر مشتمل ہوتا ہے۔ اگر ہم لامحدود ترتیبات کی اجازت دیتے ہیں تو ایک انٹیجر کو اس طرح، یا ایک مثبت انٹیجر ہونے دیں۔ اور جانے دیں۔ پھر، یا اور کا کنارہ نہیں ہے ؛ اور۔ اگر، تب۔ اگر، تب۔ اگر اور، تو اس میں ایک نیچے کا گروہ ہے تھریڈ آف ایک تسلسل ہے جس کی وضاحت اس طرح کی گئی ہے: ایک تھریڈ کو دیکھتے ہوئے، ہم کہتے ہیں کہ اگر کھلا ہے۔ اس کا استعمال کرتے ہوئے ہاروی فریڈمین نے تین انتہائی طاقتور افعال کی وضاحت کی: کیا سب سے چھوٹا ایسا ہے کہ ہر سادہ، آرڈر غیر متغیر گراف میں زیادہ سے زیادہ لمبائی میں اوپری شفٹ لالچی گروہ کی ترتیب ہوتی ہے جس میں ایک کھلا دھاگہ ہوتا ہے۔ یہ سب سے چھوٹا ہے کہ ہر آرڈر غیر متغیر ڈیگراف میں ایک اوپری شفٹ لالچی نیچے کلیک ترتیب ہوتی ہے جس کی لمبائی زیادہ سے زیادہ کھلی دھاگے کے ساتھ ہوتی ہے۔ یہ سب سے چھوٹا ہے کہ ہر آرڈر غیر متغیر ڈیگراف میں ایک کھلی دھاگے کے ساتھ زیادہ سے زیادہ لمبائی میں انتہائی اوپری شفٹ لالچی نیچے کلیک ترتیب ہوتی ہے۔ اور بالآخر تمام افعال پر غالب ہوتے ہیں جو ثابت طور پر بار بار ہوتے ہیں، لیکن خود ثابت طور پر بار بار ہوتے ہیں۔ آخر کار تمام افعال پر غالب ہوتا ہے جو ثابت طور پر بار بار ہوتے ہیں، لیکن خود ثابت طور پر مکمل ہوتے ہیں۔ حوالہ جات ریاضیاتی کھیل ریاضیاتی تصورات