التسلسل الهرمي للودج

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

يفترض${\displaystyle A}$و${\displaystyle B}$هي مجموعات جزئية من فضاء باير ω ^ω . إذن${\displaystyle A}$هل يمكن تخفيض الأجر إلى${\displaystyle B}$أو${\displaystyle A}$≤ _W${\displaystyle B}$ إذا كانت هناك دالة متصلة${\displaystyle f}$على ω ^ω مع${\displaystyle A=f^{-1}[B]}$ترتيب وادج هو الترتيب الجزئي أو شبه الترتيب على المجموعات الجزئية من فضاء باير. تُسمى فئات التكافؤ للمجموعات تحت هذا الترتيب الجزئي درجات وادج ، وهي درجة المجموعة.${\displaystyle A}$يُرمز إليه بـ [${\displaystyle A}$] _W . تسمى مجموعة درجات Wadge المرتبة حسب ترتيب Wadge بالتسلسل الهرمي لـ Wadge .

تشمل خصائص درجات وادج اتساقها مع مقاييس التعقيد المُعبر عنها من حيث قابلية التعريف. على سبيل المثال، إذا${\displaystyle A}$≤ _W${\displaystyle B}$و${\displaystyle B}$إذا كان تقاطعًا قابلاً للعد للمجموعات المفتوحة ، فإن كذلك${\displaystyle A}$وينطبق الأمر نفسه على جميع مستويات التسلسل الهرمي لبوريل والتسلسل الهرمي للفرق . ويلعب التسلسل الهرمي لوادج دورًا هامًا في نماذج بديهية الحتمية . كما يبرز اهتمامٌ إضافي بدرجات وادج من علوم الحاسوب ، حيث أشارت بعض الأبحاث إلى أن درجات وادج ذات صلة بالتعقيد الخوارزمي .

تنصّ ليمّة وادج على أنه بموجب بديهية الحتمية ( AD )، لأي مجموعتين جزئيتين${\displaystyle A,B}$من مساحة باير،${\displaystyle A}$≤ _W${\displaystyle B}$أو${\displaystyle B}$≤ _W ω ^ω \${\displaystyle A}$[ ^{1 ] إن التأكيد على صحة} ليمّة وادج للمجموعات في Γ هو مبدأ الترتيب شبه الخطي لـ Γ أو SLO(Γ). أييُعرّف الترتيب شبه الخطي ترتيبًا خطيًا على فئات التكافؤ بتردد المكملات. يمكن تطبيق ليمّة وادج محليًا على أي فئة نقطية Γ، على سبيل المثال مجموعات بوريل ، ومجموعات Δ ¹ _n ، ومجموعات Σ ¹ _n ، أو مجموعات Π ¹ _n . وينتج ذلك من حتمية فروق المجموعات في Γ. وبما أن حتمية بوريل مُثبتة في ZFC ، فإن ZFC تستلزم ليمّة وادج لمجموعات بوريل.

تتشابه معضلة وادج مع معضلة المخروط من نظرية الحوسبة.

لعبة وادج هي لعبة بسيطة لا نهائية تُستخدم لدراسة مفهوم الاختزال المستمر لمجموعات جزئية من فضاء باير. كان وادج قد حلل بنية التسلسل الهرمي لوادج لفضاء باير باستخدام الألعاب بحلول عام 1972، لكنه لم ينشر هذه النتائج إلا لاحقًا في أطروحته للدكتوراه. في لعبة وادج${\displaystyle G(A,B)}$يلعب اللاعب الأول واللاعب الثاني، كلٌّ على حدة، بأعداد صحيحة، وتُحدَّد نتيجة اللعبة بالتحقق مما إذا كانت المتتاليتان x و y اللتان يُولِّدهما اللاعبان الأول والثاني موجودتين في المجموعتين A و B على التوالي. يفوز اللاعب الثاني إذا كانت النتيجة متطابقة لكلا اللاعبين، أي${\displaystyle x}$هو في${\displaystyle A}$إذا وفقط إذا${\displaystyle y}$هو في${\displaystyle B}$يفوز اللاعب الأول إذا كانت النتيجة مختلفة. تُسمى هذه اللعبة أحيانًا بلعبة ليبشيتز ، أما النسخة التي يكون فيها للاعب الثاني خيار التمرير عددًا محدودًا من المرات فتُسمى لعبة وادج.

لنفترض أن اللعبة محددة . إذا كان لدى اللاعب الأول استراتيجية رابحة، فإن هذا يُعرّف خريطة متصلة (حتى ليبشيتز ) تُختزل${\displaystyle B}$إلى جانب${\displaystyle A}$أما إذا كان لدى اللاعب الثاني استراتيجية رابحة، فستحصل على تخفيض في${\displaystyle A}$ل${\displaystyle B}$على سبيل المثال، لنفترض أن اللاعب الثاني لديه استراتيجية رابحة. قم بربط كل متتالية x بالمتتالية y التي يلعب بها اللاعب الثاني.${\displaystyle G(A,B)}$إذا لعب اللاعب الأول التسلسل x ، واتبع اللاعب الثاني استراتيجيته الفائزة، فإن هذا يُعرّف دالة متصلة f بحيث يكون x في${\displaystyle A}$إذا وفقط إذا كانت f ( x ) تنتمي إلى${\displaystyle B}$.

أثبت مارتن ومونك في عام 1973 أن نظرية الرتبة المزدوجة (AD) تستلزم أن يكون ترتيب وادج لفضاء باير مؤسسًا جيدًا . وبالتالي، في ظل نظرية الرتبة المزدوجة، تشكل فئات وادج، بترددات مكملاتها، ترتيبًا جيدًا. رتبة وادج لمجموعة ما${\displaystyle A}$هو نوع ترتيب مجموعة درجات وادج modulo complements بشكل صارم أدناه [${\displaystyle A}$] _W. لقد ثبت أن طول التسلسل الهرمي لـ Wadge هو Θ . كما أثبت Wadge أن طول التسلسل الهرمي لـ Wadge المقيد بمجموعات Borel هو φ _{ω 1} (1) (أو φ _{ω 1} (2) اعتمادًا على الترميز)، حيث φ _γ هي دالة Veblen ^رقم γ للأساس ω ₁ (بدلاً من ω المعتادة).

أما بالنسبة لفرضية وادج، فإن هذا ينطبق على أي فئة نقطية Γ، بافتراض بديهية التحديد . إذا ربطنا بكل مجموعة${\displaystyle A}$مجموعة جميع المجموعات المذكورة أدناه${\displaystyle A}$في التسلسل الهرمي لـ Wadge، يشكل هذا فئة نقطية. وبالمثل، لكل ترتيب α  ≤  θ، فإن مجموعة Wα _من المجموعات التي تظهر قبل المرحلة α هي فئة نقطية . وعلى العكس من ذلك، فإن كل فئة نقطية تساوي بعض${\displaystyle W}$_α . يُقال إن فئة النقاط ذاتية التناظر إذا كانت مغلقة تحت التتميم. يمكن إثبات أن W _α ذاتية التناظر إذا وفقط إذا كانت α إما 0، أو عددًا ترتيبيًا زوجيًا لاحقًا ، أو عددًا ترتيبيًا حديًا ذا نهاية مشتركة قابلة للعد .

تنشأ مفاهيم مماثلة للاختزال والدرجة باستبدال الدوال المتصلة بأي فئة من الدوال F التي تحتوي على دالة التطابق وتكون مغلقة تحت التركيب . اكتب${\displaystyle A}$≤ _F${\displaystyle B}$لو${\displaystyle A=f^{-1}[B]}$لبعض الوظائف${\displaystyle f}$في F. أي فئة من هذه الدوال تحدد ترتيبًا جزئيًا على المجموعات الجزئية من فضاء باير. تُسمى الدرجات المُعطاة بواسطة دوال ليبشيتز درجات ليبشيتز ، والدرجات المُعطاة بواسطة دوال بوريل درجات بوريل-وادج .

• التسلسل الهرمي التحليلي – مفهوم في المنطق الرياضي ونظرية المجموعات 
• التسلسل الهرمي الحسابي – تسلسل هرمي لفئات التعقيد للصيغ التي تحدد المجموعات 
• بديهية الحتمية – بديهية محتملة لنظرية المجموعات 
• علاقة بوريل المكافئة
• التسلسل الهرمي لبوريل – التسلسل الهرمي للمنطق الرياضي 
• الحتمية – فرع من فروع نظرية المجموعات 
• مفهوم فئة النقاط – مفهوم نظرية المجموعات الوصفية 
• اختزال Weihrauch – فكرة من قابلية الحساب 

• ألكسندر س. كيكريس ؛ بينيديكت لوي؛ جون ر. ستيل، محرران. (ديسمبر 2011). درجات الوتد والأعداد الترتيبية الإسقاطية: ندوة الكابال، المجلد الثاني . سلسلة محاضرات في المنطق. مطبعة جامعة كامبريدج. ISBN 9781139504249.
• أندريتا، أليساندرو (2007). "مبدأ SLO وهرمية وادج". في: بولد، ستيفان؛ بينيديكت لوي؛ راش، ثورالف؛ وآخرون  (محررون). الألعاب اللانهائية، أوراق مؤتمر "أسس العلوم الصورية الخامس" المنعقد في بون، 26-29 نوفمبر 2004. دراسات في المنطق. المجلد  11. منشورات الكلية. الصفحات 1-38 . ISBN  9781904987758..
• كاناموري ، أكيهيرو (2000). اللانهائي الأعلى (الطبعة الثانية  ). سبرينغر. رقم ISBN 3-540-00384-3.
• كيكريس، ألكسندر س. (1995). نظرية المجموعات الوصفية الكلاسيكية . سبرينغر. ISBN 0-387-94374-9.
• وادج، ويليام دبليو. (1983). قابلية الاختزال والتحديد في فضاء باير (ملف PDF) (أطروحة دكتوراه). جامعة كاليفورنيا، بيركلي.

• أندريتا، أليساندرو ومارتن، دونالد (2003). "درجات بوريل وادج" . أساسيات الرياضيات . 177 (2): 175– 192. دوى : 10.4064 / fm177-2-5 .
• سينزر، دوغلاس (1984). " الاختزال الرتيب وعائلة المجموعات اللانهائية". مجلة المنطق الرمزي . 49 (3). رابطة المنطق الرمزي: 774-782 . doi : 10.2307/2274130 . JSTOR 2274130. S2CID 37813340 .  
• دوبارك، جاك (2001). "التسلسل الهرمي للوادج والتسلسل الهرمي لفيبلن. الجزء الأول: مجموعات بوريل ذات الرتبة المحدودة". مجلة المنطق الرمزي . 66 (1): 55-86 . doi : 10.2307/2694911 . JSTOR 2694911. S2CID 17703130 .  
• سيلفانوف، فيكتور ل. (2006). "نحو نظرية مجموعات وصفية للهياكل الشبيهة بالمجالات" . علوم الحاسوب النظرية . 365 (3): 258-282 . doi : 10.1016/j.tcs.2006.07.053 . ISSN 0304-3975 . 
• سيلفانوف، فيكتور ل. (2008). "قابلية الاختزال باستخدام طريقة وادج والحسابات اللانهائية". الرياضيات في علوم الحاسوب . 2 (1): 5-36 . doi : 10.1007/s11786-008-0042-x . ISSN 1661-8270 . S2CID 38211417 .  
• هاري بليس (2006). لعبة الشجرة لدوال بوريل (نسخة أولية). جامعة أمستردام، منشورات ILLC الأولية PP-2006-24 . تاريخ الاسترجاع: 12 أغسطس 2007 .