معضلة كونيغ

تُعرف مبرهنة كونيغ، أو مبرهنة كونيغ للانهائية، بأنها نظرية في علم المخططات، ويعود الفضل في نشرها إلى عالم الرياضيات المجري دينيس كونيغ عام 1927. ^{[ 1 ]} تُقدم هذه المبرهنة شرطًا كافيًا لوجود مسار لانهائي في مخطط لانهائي. وقد خضعت جوانب قابلية الحساب لهذه المبرهنة لدراسة معمقة من قِبل باحثين في المنطق الرياضي ، ولا سيما في نظرية قابلية الحساب . كما تلعب هذه المبرهنة دورًا هامًا في الرياضيات البنائية ونظرية البرهان .

يترك${\displaystyle G}$ليكن G رسمًا بيانيًا متصلًا ، محدودًا محليًا ، وغير محدود . هذا يعني أنه يمكن ربط كل رأسين بمسار محدود، وأن كل رأس مجاور لعدد محدود فقط من الرؤوس الأخرى، وأن الرسم البياني يحتوي على عدد غير محدود من الرؤوس.${\displaystyle G}$يحتوي على شعاع : مسار بسيط (مسار بدون رؤوس مكررة) يبدأ من رأس واحد ويمتد منه عبر عدد لا نهائي من الرؤوس. ويمكن صياغة النظرية بطريقة أخرى: "إذا لم ينقرض الجنس البشري، فإن أحد الأحياء اليوم سيكون له نسل لن ينقرض أبدًا". ^{[ 2 ]}

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

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

شجرة فرعية من${\displaystyle \أوميغا ^{<\أوميغا }}$تُسمى الشجرة التي تحتوي كل سلسلة فيها على عدد محدود من الامتدادات المباشرة (أي أن الشجرة لها درجة محدودة عند النظر إليها كرسم بياني) شجرة متفرعة بشكل محدود . ليس كل شجرة فرعية لانهائية من${\displaystyle \أوميغا ^{<\أوميغا }}$يحتوي على مسار لانهائي، لكن مبرهنة كونيغ تُظهر أن أي شجرة فرعية لانهائية ذات تفرع محدود يجب أن تحتوي على مثل هذا المسار.

لأي شجرة فرعية${\displaystyle T}$ل${\displaystyle \أوميغا ^{<\أوميغا }}$الترميز${\displaystyle \operatorname {Ext} (T)}$يشير إلى مجموعة العقد الخاصة بـ${\displaystyle T}$والتي يوجد من خلالها مسار لا نهائي. حتى عندما${\displaystyle T}$مجموعة قابلة للحساب${\displaystyle \operatorname {Ext} (T)}$قد لا يكون قابلاً للحساب. كلما كانت الشجرة الفرعية${\displaystyle T}$ل ${\displaystyle \أوميغا ^{<\أوميغا }}$إذا كان المسار لانهائيًا، فيمكن حساب المسار من${\displaystyle \operatorname {Ext} (T)}$خطوة بخطوة، يختار بجشع خليفة له في${\displaystyle \operatorname {Ext} (T)}$في كل خطوة. التقييد على${\displaystyle \operatorname {Ext} (T)}$يضمن ذلك عدم تعطل هذه العملية الجشعة.

توجد أشجار فرعية قابلة للحساب ذات تفرعات غير منتهية من${\displaystyle \أوميغا ^{<\أوميغا }}$التي لا تحتوي على مسار حسابي ، بل ولا تحتوي على مسار حسابي فائق . ^{[ 3 ]} ومع ذلك، فإن كل شجرة فرعية قابلة للحساب من${\displaystyle \أوميغا ^{<\أوميغا }}$يجب أن يكون للمسار مسار قابل للحساب من O لكلين ، وهو المسار المتعارف عليه.${\displaystyle \Pi _{1}^{1}}$مجموعة كاملة. وذلك لأن المجموعة${\displaystyle \operatorname {Ext} (T)}$هو دائماً${\displaystyle \سيجما _{1}^{1}}$(للاطلاع على معنى هذه الرموز، انظر التسلسل الهرمي التحليلي ) عندما${\displaystyle T}$قابل للحساب.

أُجري تحليل أدق للأشجار المحدودة حسابيًا. شجرة فرعية من${\displaystyle \أوميغا ^{<\أوميغا }}$يُطلق عليها اسم محدودة حسابيًا أو محدودة بشكل متكرر إذا كانت هناك دالة قابلة للحساب${\displaystyle f}$من${\displaystyle \omega }$ل${\displaystyle \omega }$بحيث يكون لكل متتالية في الشجرة ولكل عدد طبيعي${\displaystyle n}$، ال${\displaystyle n}$العنصر رقم n من المتتالية هو على الأكثر${\displaystyle f(n)}$. هكذا${\displaystyle f}$يُحدد هذا حدًا أقصى لعرض الشجرة. تنطبق نظريات الأساس التالية على الأشجار الفرعية اللانهائية، والمحدودة حسابيًا، والقابلة للحساب.${\displaystyle \أوميغا ^{<\أوميغا }}$.

• أي شجرة من هذا القبيل لها مسار قابل للحساب من${\displaystyle 0'}$، مجموعة تورينج الكاملة المتعارف عليها التي يمكنها حل مشكلة التوقف .
• أي شجرة من هذا القبيل تحتوي على مسار منخفض . وهذا ما يُعرف بنظرية الأساس المنخفض .
• أي شجرة من هذا القبيل تحتوي على مسار خالٍ من المناعة المفرطة . وهذا يعني أن أي دالة قابلة للحساب من المسار تهيمن عليها دالة قابلة للحساب.
• لأي مجموعة فرعية غير قابلة للحساب${\displaystyle X}$ل${\displaystyle \omega }$تحتوي الشجرة على مسار لا يمكن حسابه ${\displaystyle X}$.

تنصّ مبرهنة كونيغ الضعيفة على أن لكل شجرة ثنائية لانهائية فرعًا لانهائيًا. وتُستخدم هذه المبرهنة لتعريف النظام الفرعي WKL ₀ للحساب من الرتبة الثانية . يلعب هذا النظام الفرعي دورًا هامًا في الرياضيات العكسية . في هذا السياق، تُعرَّف الشجرة الثنائية بأنها تلك التي يكون فيها كل حد من حدود كل متتالية في الشجرة إما 0 أو 1، أي أن الشجرة محدودة حسابيًا بواسطة الدالة الثابتة 2.

على RCA ₀ ، فإن ليمّة كونيغ الضعيفة غير قابلة للإثبات، لذا فإن النظام WKL ₀ ، الذي تم الحصول عليه عن طريق إضافة ليمّة كونيغ الضعيفة إلى RCA ₀ ، هو أقوى بشكل صارم.

في WKL ₀ ، لا يمكن إثبات الشكل الكامل لـ Kőnig's lemma، ولكنه مكافئ للنظام الفرعي الأقوى ACA ₀ .

تنصّ مبرهنة كونيغ الضعيفة على أن كل شجرة ثنائية لا نهائية سميكة لها فرع لا نهائي. يُطلق على النظام الناتج عن إضافة هذا الفرع إلى الفرع الآخر اسم WWKL _0. تقع قوته بين RCA ₀ و WKL _0. الشجرة الثنائية اللانهائية السمينة هي شجرة ثنائية لا نهائية، بحيث${\displaystyle \liminf _{n}{\frac {1}{2^{n}}}|\#({\text{العقد في المستوى }}n)|>0}$بمعنى آخر، فإن نسبة العقد في الشجرة عند المستوى n لا تنخفض أبدًا عن الحد الأدنى، بغض النظر عن مدى عمق الشجرة.

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

تُعدّ نظرية المروحة لـ LEJ Brouwer ( 1927 ) ، من وجهة نظر كلاسيكية، نقيضًا لصيغة من ليمّة كونيغ. مجموعة جزئية S من ${\displaystyle \{0,1\}^{<\أوميغا }}$يُطلق عليه اسم شريط إذا كانت أي دالة من${\displaystyle \omega }$إلى المجموعة${\displaystyle \{0,1\}}$تحتوي على جزء ابتدائي في S. يكون الشريط قابلاً للفصل إذا كانت كل متتالية إما داخل الشريط أو خارجه (هذا الافتراض ضروري لأن النظرية تُدرس عادةً في حالات لا يُفترض فيها قانون الوسط المرفوع ). يكون الشريط منتظمًا إذا كان هناك عدد ما${\displaystyle N}$بحيث يمكن لأي دالة من${\displaystyle \omega }$ل${\displaystyle \{0,1\}}$يحتوي الشريط على جزء ابتدائي لا يزيد طوله عن${\displaystyle N}$تنص نظرية المروحة لبروير على أن أي قضيب قابل للفصل يكون منتظمًا.

يمكن إثبات ذلك في سياق كلاسيكي من خلال اعتبار الشريط غطاءً مفتوحًا للفضاء الطوبولوجي المضغوط${\displaystyle \{0,1\}^{\أوميغا }}$تمثل كل متتالية في الشريط مجموعة مفتوحة أساسية لهذا الفضاء، وتغطي هذه المجموعات المفتوحة الأساسية الفضاءَ بافتراض. وبسبب خاصية التراص، فإن هذا الغطاء له غطاء فرعي محدود. يمكن اعتبار N في نظرية المروحة طول أطول متتالية تقع مجموعتها المفتوحة الأساسية ضمن الغطاء الفرعي المحدود. يمكن استخدام هذا البرهان الطوبولوجي في الرياضيات الكلاسيكية لإثبات صحة الصيغة التالية لفرضية كونيغ: لأي عدد طبيعي k ، أي شجرة فرعية لانهائية من الشجرة${\displaystyle \{0,\ldots ,k\}^{<\omega }}$له مسار لا نهائي.

يمكن اعتبار لِمّة كونيغ مبدأً للاختيار؛ إذ يُبيّن البرهان الأول أعلاه العلاقة بين اللمة وبديهية الاختيار التابع . في كل خطوة من خطوات الاستقراء، يجب اختيار رأس ذي خاصية معينة. مع أنه ثبت وجود رأس مناسب واحد على الأقل، إلا أنه في حال وجود أكثر من رأس مناسب، فقد لا يكون هناك اختيار معياري. في الواقع، لا حاجة إلى كامل قوة بديهية الاختيار التابع؛ فكما هو موضح أدناه، تكفي بديهية الاختيار القابل للعد .

إذا كان الرسم البياني قابلاً للعد، فإن رؤوسه تكون مرتبة ترتيبًا جيدًا، ويمكن اختيار أصغر رأس مناسب بشكل معياري. في هذه الحالة، يمكن إثبات مبرهنة كونيغ في الحساب من الدرجة الثانية باستخدام الفهم الحسابي ، ومن باب أولى، في نظرية مجموعات ZF (بدون اختيار).

تُعتبر لِمّة كونيغ في جوهرها تقييداً لبديهية الاختيار التابع على العلاقات الكاملة${\displaystyle R}$بحيث يكون لكل${\displaystyle x}$عددهم محدود${\displaystyle z}$بحيث${\displaystyle xRz}$على الرغم من أن بديهية الاختيار، بشكل عام، أقوى من مبدأ الاختيار التابع، فإن هذا التقييد للاختيار التابع يُكافئ تقييدًا لبديهية الاختيار. وبالتحديد، عندما يتم التفرع عند كل عقدة على مجموعة جزئية منتهية من مجموعة عشوائية غير مفترضة أنها قابلة للعد، فإن صيغة لِمّة كونيغ التي تنص على أن "لكل شجرة متفرعة نهائية لانهائية مسارًا لانهائيًا" تُكافئ مبدأ أن لكل مجموعة قابلة للعد من المجموعات المنتهية دالة اختيار، أي بديهية الاختيار القابل للعد للمجموعات المنتهية. ^{[ 4 ]} هذه الصيغة من بديهية الاختيار (وبالتالي من لِمّة كونيغ) غير قابلة للإثبات في نظرية مجموعات ZF.

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

• شجرة أرونزاجن ، من أجل إمكانية وجود أمثلة مضادة عند تعميم اللمة إلى أعداد أكبر.
• درجة مساعد طبيب

• بروير، إل إي جيه (1927)، حول مجالات تعريف الدوال. نشرت في فان هيجنورت، جان، أد. (1967)، من فريجه إلى جودل
• فرانشيلا، ميريام (1997)، "حول أصول معضلة اللانهاية لدينيس كونيغ"، أرشيف تاريخ العلوم الدقيقة ، 51 (51(1)3:2-3): 3-27 ، doi : 10.1007/BF00376449 ، S2CID 117198918 
• هوارد، بول؛ روبين، جان (1998)، نتائج بديهية الاختيار ، دراسات وبحوث رياضية، المجلد  59، بروفيدنس، رود آيلاند: الجمعية الرياضية الأمريكية
• كونيغ، د. (1927)، “Über eine Schlussweise aus dem Endlichen ins Unendliche” ، Acta Sci. الرياضيات. (زيجيد) (بالألمانية)، 3 ( 2– 3): 121–130 ، تم استرجاعه في 23/12/2014{{citation}}: CS1 maint: deprecated archiveal service ( link )
• ليفي، عزريل (1979)، نظرية المجموعات الأساسية ، سبرينغر، ISBN 3-540-08417-7، MR 0533962 طبعة مُعاد طباعتها، دوفر، 2002، رقم ISBN 0-486-42079-5.
• روغرز، هارتلي الابن (1967)، نظرية الدوال المتكررة والحسابية الفعالة ، ماكجرو هيل، MR 0224462 
• تروس، ج. (1976)، "بعض حالات ليمّة كونيغ"، في ماريك، ف. فيكتور؛ سريبرني، ماريان؛ زاراش، أندريه (محررون)، نظرية المجموعات ونظرية التسلسل الهرمي: تكريمًا لأندريه موستوفسكي ، سلسلة محاضرات في الرياضيات، المجلد  537، سبرينغر، الصفحات 273-284 ، doi : 10.1007/BFb0096907 ، ISBN  978-3-540-07856-2، MR 0429557 
• كنوت، دونالد (1968)، فن برمجة الحاسوب، المجلد 1: الخوارزميات الأساسية ، ص  382، ISBN 978-0-201-03801-9

• سينزر، دوغلاس (1999)، "${\displaystyle \Pi _{1}^{0}}$"الفئات في نظرية الحوسبة"، دليل نظرية الحوسبة ، إلسيفير، الصفحات 37-85 ، doi : 10.1016/S0049-237X(99)80018-4 ، ISBN  0-444-89882-4MR 1720779​ 
• Kőnig، D. (1926)، “Sur les مراسلات multivoques des ensembles” (PDF) ، Fundamenta Mathematicae (بالفرنسية)، 8 (8): 114–134 ، دوى : 10.4064 / fm-8-1-114-134
• كونيج، د. (1936)، Theorie der Endlichen und Unendlichen Graphen: Kombinatorische Topologie der Streckenkomplexe (في المانيا)، لايبزيغ: Akad. فيرلاغ
• سيمبسون، ستيفن ج. (1999)، الأنظمة الفرعية للحساب من الدرجة الثانية ، منظورات في المنطق الرياضي، سبرينغر، ISBN 3-540-64882-8MR 1723993​ 
• سواري، روبرت آي. (1987)، المجموعات والدرجات القابلة للتعداد بشكل متكرر: دراسة للدوال القابلة للحساب والمجموعات المولدة حسابيًا ، وجهات نظر في المنطق الرياضي، سبرينغر، ISBN 3-540-15299-7، MR 0882921 

• موسوعة ستانفورد للفلسفة: الرياضيات البنائية
• قام مشروع Mizar بصياغة وتأكيد برهان نسخة من ليمّة كونيغ بشكل كامل وتلقائي في الملف TREES_2 .