الحتمية

أول نوع من الألعاب التي سنتناولها هو لعبة اللاعبين الاثنين ذات المعلومات الكاملة بطول ω ، حيث يلعب اللاعبون بأعداد طبيعية . تُسمى هذه الألعاب غالبًا بألعاب غيل - ستيوارت. ^{[ 2 ]}

في هذا النوع من الألعاب ، يوجد لاعبان، يُطلق عليهما غالبًا اسمي الأول والثاني ، يتناوبان على لعب الأعداد الطبيعية، ويبدأ الأول أولًا. يستمر اللعب "إلى ما لا نهاية"؛ أي أن ترتيب لعبهما مُفهرس بالأعداد الطبيعية. عند انتهاء اللعب، يُحدد شرط مُسبق الفائز. لا يشترط أن يكون هذا الشرط مُحددًا بقاعدة مُعينة ؛ فقد يكون ببساطة جدول بحث (طويل جدًا) يُحدد الفائز بناءً على تسلسل مُعين من اللعبات.

بصورة أكثر رسمية، لنفترض مجموعة جزئية A من فضاء باير ؛ تذكر أن هذا الأخير يتكون من جميع متواليات ω للأعداد الطبيعية. في اللعبة G _A ، يلعب اللاعب I عددًا طبيعيًا a ≠ ₀ ، ثم يلعب اللاعب II العدد ₁ ، ثم يلعب اللاعب I العدد ₂ ، وهكذا. يفوز اللاعب I باللعبة إذا وفقط إذا

${\displaystyle \langle a_{0},a_{1},a_{2},\ldots \rangle \in A}$

وإلا يفوز الخيار الثاني . ويُطلق على المجموعة أ اسم مجموعة العوائد للمجموعة ج _أ .

يفترض أن كل لاعب يستطيع رؤية جميع الحركات التي تسبق كل حركة من حركاته، ويعرف أيضاً شرط الفوز.

بصورة غير رسمية، تُعرَّف استراتيجية اللاعب بأنها أسلوب لعب تُحدَّد فيه تحركاته بالكامل بناءً على التحركات السابقة. ومرة ​​أخرى، لا يشترط أن يكون هذا "الأسلوب" قابلاً للتفسير من خلال أي "قاعدة" محددة، بل قد يكون مجرد جدول مرجعي.

بصورة أدق، تُعرَّف استراتيجية اللاعب الأول (في لعبةٍ بالمعنى الوارد في القسم الفرعي السابق) بأنها دالة تقبل كمعامل أي سلسلة منتهية من الأعداد الطبيعية، ذات طول زوجي، وتُرجع عددًا طبيعيًا. إذا كانت σ استراتيجيةً من هذا القبيل، وكانت < a₀ _, ..., _aₙ₋₁ > سلسلة من الحركات، فإن σ ( < a₀ , ..., _aₙ₋₁ > ) هي الحركة التالية التي سأقوم بها، إذا كنتُ أتبع الاستراتيجية σ . أما استراتيجيات اللاعب _الثاني فهي مماثلة، مع استبدال "الزوجي" بـ "فردي".

لاحظ أننا لم نتطرق بعد إلى ما إذا كانت الاستراتيجية جيدة أم لا . قد تدفع الاستراتيجية اللاعب إلى اتخاذ خطوات سيئة عدوانية، ومع ذلك تظل استراتيجية. في الواقع، ليس من الضروري حتى معرفة شروط الفوز في اللعبة لمعرفة الاستراتيجيات المتاحة لها.

تكون الاستراتيجية رابحة إذا كان اللاعب الذي يتبعها سيفوز حتمًا، بغض النظر عما يلعبه خصمه. على سبيل المثال، إذا كانت σ استراتيجية للاعب I ، فإن σ تكون استراتيجية رابحة للاعب I في لعبة G _A إذا كان، لأي سلسلة من الأعداد الطبيعية التي سيلعبها اللاعب II ، ولتكن < a1 _, a3 , _a5 , ... > ، سلسلة الحركات التي تنتجها σ عندما يلعب اللاعب II على النحو التالي، هي _:

${\displaystyle \langle \sigma (\langle \rangle ),a_{1},\sigma (\langle \sigma (\langle \rangle ),a_{1}\rangle ),a_{3},\ldots \rangle }$

هو عنصر من عناصر المجموعة أ .

تُحدد اللعبة (أو فئة منها) إذا وُجدت استراتيجية رابحة لأحد اللاعبين في جميع مراحلها (ليس بالضرورة نفس اللاعب في كل مرحلة). ^{[ 3 ]} لا يمكن أن توجد استراتيجية رابحة لكلا اللاعبين في اللعبة نفسها، لأنه لو وُجدت، لأمكن تطبيق الاستراتيجيتين ضد بعضهما. وبالتالي، ستكون النتيجة، بحسب الفرضية، فوزًا لكلا اللاعبين، وهو أمر مستحيل. ^{[ 4 ]}

يستنتج من وجود عدد أصلي قابل للقياس أن كل لعبة تحليلية (وتسمى أيضًا لعبة Σ ¹ ₁ ) محددة، أو بصورة مكافئة أن كل لعبة تحليلية مشتركة (أو Π ¹ ₁ ) محددة. (انظر التسلسل الهرمي الإسقاطي للاطلاع على التعريفات).

في الواقع، يكفي وجود عدد أصلي قابل للقياس. مبدأ أضعف - وهو وجود 0 ^{# -} يكفي لإثبات الحتمية التحليلية المشتركة، وأكثر من ذلك بقليل: النتيجة الدقيقة هي أن وجود 0 ^# يكافئ حتمية جميع مستويات التسلسل الهرمي للفرق أسفل المستوى ω2 ^، أي حتمية ω·n ^- Π1 _لكل${\displaystyle n}$.

^{انطلاقًا من عدد أصلي قابل للقياس} _، يمكننا تحسين هذا بشكل طفيف جدًا إلى حتمية ω² ^{- Π¹¹} . ومن خلال وجود المزيد من الأعداد الأصلية القابلة للقياس، يمكن إثبات حتمية المزيد من مستويات التسلسل الهرمي للفرق _على Π¹¹ .

إذا وُجد عددٌ من أعداد وودين الأصلية مع عددٍ أصلي قابل للقياس فوقه، فإن شرط التحديد Π ¹ ₂ يتحقق. وبشكلٍ أعم، إذا وُجدت n أعدادًا أصلية من أعداد وودين الأصلية مع عددٍ أصلي قابل للقياس فوقها جميعًا، فإن شرط التحديد Π ¹ _n+1 يتحقق. ومن شرط التحديد Π ¹ _n+1 ، يتبين وجود نموذجٍ داخلي متعدٍّ يحتوي على n عددًا أصليًا من أعداد وودين الأصلية.

${\displaystyle \Delta _{2}^{1}}$إن حتمية (الوجه الفاتح) متسقة مع عدد وودين الأصلي. إذا${\displaystyle \Delta _{2}^{1}}$إذا تحققت خاصية الحتمية، فبالنسبة لمخروط تورينج لـ x (أي لكل عدد حقيقي x ذي درجة تورينج عالية بما فيه الكفاية )، فإن L[ x ] تحقق خاصية الحتمية OD (أي حتمية الألعاب على الأعداد الصحيحة ذات الطول ω والعائد القابل للتحديد الترتيبي)، وفي HOD ^{L[ x ]}${\displaystyle \omega _{2}^{L[x]}}$هو طائر الكاردينال وودين.

إذا كان عدد أعداد وودين الأصلية لا نهائيًا، فإن خاصية التحديد الإسقاطي تتحقق؛ أي أن كل لعبة يكون شرط فوزها مجموعة إسقاطية تكون محددة. ومن التحديد الإسقاطي، يتبين أنه لكل عدد طبيعي n ، يوجد نموذج داخلي متعدٍّ يحقق وجود n من أعداد وودين الأصلية.

تؤكد بديهية الحتمية ، أو AD ، أن كل لعبة ثنائية اللاعبين ذات معلومات كاملة بطول ω، حيث يلعب اللاعبون أدوارًا طبيعية، تكون محددة.

من الممكن إثبات خطأ AD من ZFC؛ وباستخدام بديهية الاختيار ، يمكن إثبات وجود لعبة غير محددة. مع ذلك، إذا كان هناك عدد لا نهائي من أعداد وودين الأصلية التي لها قيمة قابلة للقياس فوقها جميعًا، فإن L(R) هو نموذج لـ ZF يحقق AD.

إذا كانت A مجموعة جزئية من فضاء باير بحيث تكون لعبة باناش-مازور لـ A محددة، فإما أن يكون لدى II استراتيجية رابحة، وفي هذه الحالة تكون A ضئيلة ، أو أن يكون لدى I استراتيجية رابحة، وفي هذه الحالة تكون A متقاربة في جوار مفتوح ما.

هذا لا يعني بالضرورة أن A لها خاصية باير ، لكنها تقترب من ذلك: يُظهر تعديل بسيط للحجة أنه إذا كانت Γ فئة نقاط كافية بحيث يتم تحديد كل لعبة في Γ، فإن كل مجموعة من الأعداد الحقيقية في Γ لها خاصية باير.

في الواقع، هذه النتيجة ليست مثالية؛ فبدراسة لعبة باناخ-مازور غير المطوية، يمكننا إثبات أن حتمية Γ (لـ Γ ذات خصائص إغلاق كافية) تستلزم أن كل مجموعة من الأعداد الحقيقية، التي تمثل إسقاطًا لمجموعة في Γ، تتمتع بخاصية باير. فعلى سبيل المثال، وجود عدد أصلي قابل للقياس يستلزم _حتمية ^Π ، والتي بدورها تستلزم أن كل مجموعة من _{الأعداد} ^{الحقيقية} Σ تتمتع بخاصية باير.

من خلال النظر في ألعاب أخرى، يمكننا أن نبين أن حتمية Π ¹ _n تعني أن كل مجموعة Σ ¹ _{n +1} من الأعداد الحقيقية لها خاصية باير، وقابلة للقياس وفقًا لليبيغ (في الواقع قابلة للقياس عالميًا ) ولها خاصية المجموعة الكاملة .

• تنص نظرية الدورية الأولى على أنه بالنسبة لكل عدد طبيعي n ، إذا تحققت خاصية التحديد Δ ¹ _{2 n +1 ، فإن} Π ¹ _{2 n +1} و Σ ¹ _{2 n +2} لهما خاصية الترتيب المسبق الجيد (وأن Σ ¹ _{2 n +1} و Π ¹ _{2 n +2} ليس لهما خاصية الترتيب المسبق الجيد، بل لهما خاصية الفصل ).
• تنص نظرية الدورية الثانية على أنه لكل عدد طبيعي n ، إذا تحققت خاصية التحديد Δ ¹ _{2 n +1 ، فإن} Π ¹ _{2 n +1} و Σ ¹ _{2 n} تتمتعان بخاصية المقياس . ^{[ 7 ]} وعلى وجه الخصوص، إذا تحققت خاصية التحديد الإسقاطي، فإن كل علاقة إسقاطية لها توحيد إسقاطي .
• تُعطي نظرية الدورية الثالثة شرطًا كافيًا لكي يكون للعبة استراتيجية فوز محددة.

في عام 1969، أثبت مايكل أو. رابين أن نظرية الرتبة الثانية الأحادية لـ n من الخلفاء ( S2S لـ n = 2) قابلة للتقرير . ^{[ 8 ]} يتطلب أحد المكونات الرئيسية للإثبات إظهار حتمية ألعاب التكافؤ ، والتي تقع في المستوى الثالث من التسلسل الهرمي لبوريل .

حتمية وادج هي القول بأن لعبة وادج G(A, B) محددة لكل زوج من المجموعات الجزئية A و B في فضاء باير. وبالمثل، بالنسبة لفئة النقاط Γ ، فإن حتمية وادج هي القول بأن لعبة وادج G( A , B ) محددة لكل مجموعتين A و B في Γ .

يستلزم مبدأ التحديد في نظام وادج مبدأ الترتيب شبه الخطي لهذا النظام . ومن النتائج الأخرى لهذا المبدأ خاصية المجموعة الكاملة .

بشكل عام، يُعدّ تحديد مجموعة Γ نتيجةً لتحديد التوليفات المنطقية للمجموعات في Γ. في التسلسل الهرمي الإسقاطي ، يُكافئ تحديد مجموعة Π ¹ _{1 تحديد مجموعة} Π ¹ ₁ ، كما أثبت ذلك ليو هارينغتون . وقد وسّع هيورث هذه النتيجة ليُثبت أن تحديد مجموعة Π ¹ ₂ (وفي الواقع، مبدأ الترتيب شبه الخطي لمجموعة Π ¹ ₂ ) يستلزم بالفعل تحديد مجموعة Π ¹ ₂ .

إن حتمية الألعاب على الأعداد الترتيبية ذات العائد القابل للتحديد ترتيبيًا والطول ω تعني أنه لكل عدد أصلي منتظم κ > ω، لا توجد مجموعات فرعية ثابتة منفصلة قابلة للتحديد ترتيبيًا من κ مكونة من أعداد ترتيبية ذات نهاية مشتركة ω. قوة اتساق فرضية الحتمية غير معروفة، ولكن من المتوقع أن تكون عالية جدًا.

إن وجود أعداد وودين ω ₁ يعني أنه لكل عدد ترتيبي قابل للعد α، تكون جميع الألعاب على الأعداد الصحيحة ذات الطول α والعائد الإسقاطي محددة. وبصورة تقريبية، فإن أعداد وودين α تتوافق مع حتمية الألعاب على الأعداد الحقيقية ذات الطول α (مع مجموعة عوائد بسيطة). بافتراض وجود حد لأعداد وودين κ حيث o( κ ) ​​= κ ⁺⁺ وأعداد وودين ω أكبر من κ ، فإن الألعاب ذات الطول المتغير القابل للعد، حيث تنتهي اللعبة بمجرد أن يصبح طولها مقبولاً بالنسبة لخط اللعب، وذات العائد الإسقاطي، تكون محددة. بافتراض إمكانية إثبات تخمين معين حول قابلية التكرار، فإن وجود عدد وودين قابل للقياس يعني حتمية الألعاب المفتوحة ذات الطول ω ₁ والعائد الإسقاطي. (في هذه الألعاب، يتم تفعيل شرط الفوز للاعب الأول في مرحلة قابلة للعد، لذلك يمكن ترميز العائد كمجموعة من الأعداد الحقيقية.)

بالنسبة إلى حد وودين لأعداد وودين الأصلية وكمية قابلة للقياس أعلى منها، من المتسق أن كل لعبة على أعداد صحيحة بطول ω ₁ وعائد قابل للتحديد ترتيبيًا تكون محددة. يُفترض أن فرضية التحديد متسقة مع حد وودين لأعداد وودين الأصلية. ω ₁ هي القيمة القصوى حيث توجد ألعاب غير محددة على أعداد صحيحة بطول ω ₁ + ω وعائد قابل للتحديد ترتيبيًا.

في أي لعبة مثيرة للاهتمام ذات معلومات غير كاملة ، ستكون الاستراتيجية الرابحة استراتيجية مختلطة : أي أنها ستعطي احتمالية معينة لاستجابات مختلفة لنفس الموقف. إذا كانت الاستراتيجيات المثلى لكلا اللاعبين استراتيجيات مختلطة، فلن تكون نتيجة اللعبة حتمية بشكل قاطع (كما هو الحال بالنسبة للاستراتيجيات البحتة ، لأنها حتمية ). ولكن يمكن حساب التوزيع الاحتمالي للنتائج للاستراتيجيات المختلطة المتعارضة. تُعرَّف اللعبة التي تتطلب استراتيجيات مختلطة بأنها حتمية إذا وُجدت استراتيجية تُحقق قيمة متوقعة دنيا (على الاستراتيجيات المضادة الممكنة) تتجاوز قيمة معينة. وبناءً على هذا التعريف، فإن جميع ألعاب المجموع الصفري المحدودة ذات اللاعبين تكون حتمية بشكل واضح. ومع ذلك، فإن حتمية الألعاب اللانهائية ذات المعلومات غير الكاملة (ألعاب بلاكويل) أقل وضوحًا. ^{[ 9 ]}

في عام 1969، أثبت ديفيد بلاكويل أن بعض "الألعاب اللانهائية ذات المعلومات غير الكاملة" (المعروفة الآن باسم "ألعاب بلاكويل") محددة، وفي عام 1998، أثبت دونالد أ. مارتن أن التحديد العادي (لعبة المعلومات الكاملة) لفئة نقاط محددة مسبقًا يستلزم تحديد بلاكويل لتلك الفئة. هذا، بالإضافة إلى نظرية بوريل للتحديد لمارتن، يعني أن جميع ألعاب بلاكويل ذات دوال عائد بوريل محددة. ^{[ 10 ] [ 11 ]} افترض مارتن أن التحديد العادي وتحديد بلاكويل للألعاب اللانهائية متكافئان بشكل كبير (أي أن تحديد بلاكويل لفئة نقاط محددة مسبقًا يستلزم بدوره التحديد العادي لتلك الفئة)، ولكن حتى عام 2010، لم يُثبت أن تحديد بلاكويل يستلزم تحديد لعبة المعلومات الكاملة. ^{[ 12 ]}