نظرية ω-المتسقة

الموسوعة الحرة

في المنطق الرياضي ، تُعرف النظرية المتسقة ω (أو المتسقة أوميغا ، أو المنفصلة عدديًا ) [ 1 ] بأنها نظرية (مجموعة من الجمل ) لا تقتصر على كونها متسقة (نحويًا) [ 2 ] [ 3 ] (أي أنها لا تثبت تناقضًا )، بل تتجنب أيضًا إثبات بعض التراكيب اللانهائية للجمل التي تبدو متناقضة بديهيًا. ويُعزى هذا الاسم إلى كورت غودل ، الذي قدم هذا المفهوم أثناء إثباته لنظرية عدم الاكتمال . [ 4 ]

تعريف

يقال إن النظرية T تفسر لغة الحساب إذا كان هناك ترجمة لصيغ الحساب إلى لغة T بحيث تكون T قادرة على إثبات البديهيات الأساسية للأعداد الطبيعية في ظل هذه الترجمة.

تُعتبر نظرية T التي تُفسر الحساب غير متسقة من النوع ω إذا كانت، بالنسبة لخاصية P للأعداد الطبيعية (المُعرّفة بصيغة في لغة T )، تُثبت T صحة P (0)، و P (1)، و P (2)، وهكذا (أي، لكل عدد طبيعي قياسي n ، تُثبت T صحة P ( n ))، ولكنها تُثبت أيضًا وجود عدد طبيعي n بحيث لا تتحقق P ( n ) . [ 2 ] قد لا يُؤدي هذا إلى تناقض داخل T لأن T قد لا تتمكن من إثبات عدم تحقق P ( n ) لأي قيمة مُحددة من n ، بل فقط إثبات وجود مثل هذا العدد n . على وجه الخصوص، يكون هذا العدد n بالضرورة عددًا صحيحًا غير قياسي في أي نموذج لـ T ( لذا أطلق كواين على هذه النظريات اسم "غير قابلة للفصل العددي"). [ 5 ]

تكون T متسقة مع ω إذا لم تكن غير متسقة مع ω.

هناك خاصية أضعف ولكنها وثيقة الصلة بمفهوم سلامة Σ 1. تُوصف النظرية T بأنها سليمة Σ 1 (أو متسقة 1 ، بتعبير آخر) [ 6 ] إذا كانت كل جملة Σ 0 1 [ ملاحظة 1 ] قابلة للإثبات في T صحيحة في النموذج القياسي للحساب N (أي بنية الأعداد الطبيعية المعتادة مع الجمع والضرب). إذا كانت T قوية بما يكفي لصياغة نموذج معقول للحساب ، فإن سلامة Σ 1 تُكافئ اشتراط أنه كلما أثبتت T أن آلة تورينج C تتوقف، فإن C تتوقف بالفعل. كل نظرية متسقة ω هي سليمة Σ 1 ، ولكن ليس العكس.

بشكلٍ أعم، يُمكننا تعريف مفهومٍ مُشابهٍ للمستويات العليا من التسلسل الهرمي الحسابي . إذا كانت Γ مجموعةً من الجمل الحسابية (عادةً Σ ∈ ℝⁿ لبعض n )، فإنّ النظرية T تُوصف بأنّها سليمةٌ وفقًا لـ Γ إذا كانت كلّ جملةٍ من Γ قابلةٍ للإثبات في T صحيحةً في النموذج القياسي. عندما تكون Γ مجموعة جميع الصيغ الحسابية، يُطلق على سلامة Γ اسم السلامة (الحسابية) ببساطة . إذا كانت لغة T تتكوّن فقط من لغة الحساب (على عكس، على سبيل المثال، نظرية المجموعات )، فإنّ النظام السليم هو النظام الذي يُمكن اعتبار نموذجه المجموعة ω، وهي المجموعة المعتادة للأعداد الطبيعية الرياضية. تختلف حالة T العامة؛ انظر منطق ω أدناه.

إن Σ n -soundness له التفسير الحسابي التالي: إذا أثبتت النظرية أن البرنامج C باستخدام Σ n −1 - oracle يتوقف، فإن C يتوقف بالفعل.

أمثلة

النظريات المتسقة، غير المتسقة مع ω

اكتب PA للدلالة على نظرية حساب بيانو ، وCon(PA) للدلالة على عبارة الحساب التي تُضفي الطابع الرسمي على الادعاء "PA متسقة". يمكن أن تكون Con(PA) على الصورة التالية: "لا يوجد عدد طبيعي n هو عدد غودل لإثبات في PA أن 0=1". [ ملاحظة 2 ] الآن، اتساق PA يستلزم اتساق PA  +  ¬Con(PA). في الواقع، إذا كانت PA  +  ¬Con(PA) غير متسقة، فإن PA وحدها ستثبت ¬Con(PA)→0=1، وسيؤدي البرهان بالتناقض في PA إلى إثبات Con(PA). وفقًا لنظرية عدم الاكتمال الثانية لغودل ، ستكون PA غير متسقة.

لذا، بافتراض أن PA متسقة، فإن PA  +  ¬Con(PA) متسقة أيضًا. مع ذلك، لن تكون متسقة من النوع ω. والسبب هو أنه لأي قيمة معينة لـ n ، فإن PA، وبالتالي PA  +  ¬Con(PA)، تثبت أن n ليس عدد غودل لإثبات أن 0=1. بينما تثبت PA  +  ¬Con(PA) أنه بالنسبة لعدد طبيعي n ، فإن n هو عدد غودل لمثل هذا الإثبات (وهذه مجرد إعادة صياغة مباشرة للادعاء ¬Con(PA)).

في هذا المثال، البديهية ¬Con(PA) هي Σ 1 ، وبالتالي فإن النظام PA  +  ¬Con(PA) هو في الواقع Σ 1 -غير سليم، وليس فقط ω-غير متسق.

نظريات سليمة حسابيًا وغير متسقة مع ω

ليكن T هو PA مع البديهيات c  ≠ n لكل عدد طبيعي n ، حيث c ثابت جديد يُضاف إلى اللغة. عندئذٍ يكون T سليمًا حسابيًا (إذ يمكن توسيع أي نموذج غير قياسي لـ PA إلى نموذج لـ T )، ولكنه غير متسق ω (كما يثبت ذلك). ∃xج=x{\displaystyle \exists x\,c=x}، و c  ≠ n لكل عدد n ). 

يمكن بناء نظريات Σ 1 -صوت غير متسقة مع ω باستخدام لغة الحساب فقط على النحو التالي. ليكن I Σ n النظرية الفرعية لـ PA مع تقييد مخطط الاستقراء إلى Σ n- صيغ، لأي n  >  0. النظرية I Σ n  +  1 قابلة للتحديد البديهي بشكل نهائي، ولتكن A بديهيتها الوحيدة، ولنعتبر النظرية T  = I Σ n + ¬ A. يمكننا افتراض أن A هي حالة من مخطط الاستقراء، الذي يأخذ الشكل التالي:   

∀w[ب(0،w)∧∀x(ب(x،w)→ب(x+1،w))→∀xب(x،w)].{\displaystyle \forall w\,[B(0,w)\land \forall x\,(B(x,w)\to B(x+1,w))\to \forall x\,B(x,w)].}

إذا رمزنا إلى الصيغة

∀w[ب(0،w)∧∀x(ب(x،w)→ب(x+1،w))→ب(ن،w)]{\displaystyle \forall w\,[B(0,w)\land \forall x\,(B(x,w)\to B(x+1,w))\to B(n,w)]}

بناءً على P ( n )، فإنه لكل عدد طبيعي n ، تثبت النظرية T (بل وحتى حساب التفاضل والتكامل المجرد) P ( n ). من جهة أخرى، تثبت T الصيغة التالية:∃x¬P(x){\displaystyle \exists x\,\neg P(x)}، لأنه مكافئ منطقياً للبديهية ¬ أ . لذلك، فإن T غير متسق مع ω.

من الممكن إثبات أن T سليمة من الدرجة Π n  +  3. في الواقع، هي محافظة من الدرجة Π n + 3  على  النظرية السليمة (بشكل واضح) I Σ n . الحجة أكثر تعقيدًا (فهي تعتمد على إمكانية إثبات مبدأ الانعكاس من الدرجة Σ n + 2 لـ I Σ n في I Σ n + 1 ).    

نظريات غير سليمة حسابيًا ومتسقة مع ω

لنفترض أن ω-Con(PA) هي الجملة الحسابية التي تُصاغ عبارة "PA متسقة ω". عندئذٍ، تكون النظرية PA  +  ¬ω-Con(PA) غير سليمة (غير سليمة Σ 3 تحديدًا)، ولكنها متسقة ω. الحجة مشابهة للمثال الأول: صيغة مناسبة من شروط اشتقاق هيلبرت-بيرنايز-لوب تنطبق على "مسند الإثبات" ω-Prov( A )  =  ¬ω-Con(PA  +  ¬A ) ، وبالتالي فهي تُحقق نظيرًا لنظرية عدم الاكتمال الثانية لغودل.

منطق ω

يُجسّد منطق ω مفهوم نظريات الحساب التي تكون أعدادها الصحيحة هي الأعداد الرياضية الحقيقية . [ ملاحظة 3 ] لنفترض أن T نظرية في لغة قابلة للعد تتضمن رمزًا أحاديًا N يُقصد به تمثيل الأعداد الطبيعية فقط، بالإضافة إلى أسماء محددة 0، 1، 2، ...، اسم لكل عدد طبيعي (قياسي) (قد تكون هذه الأسماء ثوابت منفصلة، ​​أو حدودًا ثابتة مثل 0، 1، 1+1، 1+1+1، ...، إلخ). تجدر الإشارة إلى أن T نفسها قد تشير إلى كائنات أكثر عمومية، مثل الأعداد الحقيقية أو المجموعات؛ وبالتالي، في نموذج T، فإن الكائنات التي تحقق N ( x ) هي تلك التي تفسرها T على أنها أعداد طبيعية، وليس بالضرورة أن تحمل جميعها أحد الأسماء المحددة.

يتضمن نظام منطق ω جميع البديهيات والقواعد الخاصة بمنطق المسند من الدرجة الأولى المعتاد ، بالإضافة إلى قاعدة ω لانهائية من الشكل التالي لكل صيغة T P ( x ) مع متغير حر محدد x :

منP(0)،P(1)،P(2)،...{\displaystyle P(0),P(1),P(2),\ldots }استدلال∀x(شمال(x)→P(x)){\displaystyle \forall x\,(N(x)\to P(x))}.

أي، إذا كانت النظرية تؤكد (أي تثبت) P ( n ) بشكل منفصل لكل عدد طبيعي n معطى باسمه المحدد، فإنها تؤكد أيضًا P بشكل جماعي لجميع الأعداد الطبيعية دفعة واحدة من خلال النظير الواضح والمحدود والمُكمّم عالميًا لعدد لا نهائي من مقدمات القاعدة. بالنسبة لنظرية حسابية، أي تلك التي يكون مجالها المقصود هو الأعداد الطبيعية مثل حساب بيانو ، فإن المسند N زائد ويمكن حذفه من اللغة، مع تبسيط نتيجة القاعدة لكل P إلى∀xP(x){\displaystyle \forall x\,P(x)}.

النموذج ω لـ T هو نموذج لـ T يشمل نطاقه الأعداد الطبيعية، وتُفسَّر أسماؤه ورمزه N تفسيرًا قياسيًا، على التوالي، على أنها تلك الأعداد والمسند الذي يقتصر نطاقه على تلك الأعداد فقط (وبالتالي لا توجد أعداد غير قياسية). إذا كان N غائبًا عن اللغة، فيجب أن يكون نطاق النموذج هو نطاق N ، أي أن النموذج يحتوي على الأعداد الطبيعية فقط. (قد تُفسِّر نماذج أخرى لـ T هذه الرموز تفسيرًا غير قياسي؛ فنطاق N قد لا يكون قابلًا للعد، على سبيل المثال). هذه الشروط تجعل قاعدة ω صحيحة في كل نموذج ω. وكنتيجة لنظرية حذف الأنواع ، فإن العكس صحيح أيضًا: تمتلك النظرية T نموذج ω إذا وفقط إذا كانت متسقة في منطق ω.

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

العلاقة بمبادئ الاتساق الأخرى

إذا كانت النظرية T قابلة للتحديد البديهي بشكل متكرر ، فإن الاتساق ω له الخصائص التالية، وذلك بفضل كريج سمورينسكي : [ 8 ]

تكون T متسقة مع ω إذا وفقط إذاتي+RFشمالتي+تيحΠ20(شمال){\displaystyle T+\mathrm {RFN} _{T}+\mathrm {Th} _{\Pi _{2}^{0}}(\mathbb {N} )}متسق.

هنا،تيحΠ20(شمال){\displaystyle \mathrm {Th} _{\Pi _{2}^{0}}(\mathbb {N} )}هي مجموعة جميع الجمل Π 0 الصالحة في النموذج القياسي للحساب، وRFشمالتي{\displaystyle \mathrm {RFN} _{T}}هو مبدأ الانعكاس المنتظم لـ T ، والذي يتكون من البديهيات

∀x(Pرovتي(⌜φ(x˙)⌝)→φ(x)){\displaystyle \forall x\,(\mathrm {Prov} _{T}(\ulcorner \varphi ({\dot {x}})\urcorner )\to \varphi (x))}

لكل صيغةφ{\displaystyle \varphi }مع متغير حر واحد. على وجه الخصوص، تكون النظرية T القابلة للتحديد البديهي المحدود في لغة الحساب متسقة ω إذا وفقط إذا كانت T  +  PAΣ20{\displaystyle \Sigma _{2}^{0}}-صوت.

ملحوظات

  1. ↑ صيغة Σ 0 n هي صيغة من الدرجة الأولى (صيغة تقتصر فيها المتغيرات على فضاء الخطاب ، مثل الأعداد الطبيعية، ولا تشمل المسندات ) تبدأ ببعض المحددات الوجودية وتتناوب n − 1 مرة بين سلاسل من المحددات الوجودية والشمولية ، أو صيغة مكافئة لها. للاطلاع على التعريف الكامل، انظر التسلسل الهرمي الحسابي .
  2. ↑ تستخدم هذه الصيغة 0=1 بدلاً من التناقض المباشر؛ وهذا يعطي نفس النتيجة، لأن PA تثبت بالتأكيد ¬0=1، لذلك إذا أثبتت 0=1 أيضًا فسيكون لدينا تناقض، ومن ناحية أخرى، إذا أثبتت PA تناقضًا، فإنها تثبت أي شيء ، بما في ذلك 0=1.
  3. ↑ يتم تعريف منطق ω في باروايز [ 7 ] على أنه منطق من الدرجة الأولى ثنائي التصنيف، مع تفسير ثابت للنوع الثاني على أنه الأعداد الطبيعية (§5.2، ص.42)؛ بينما تناقش هذه المقالة الاستبطان أحادي التصنيف عبر مسند أحادي N (تمت مناقشته أيضًا في §5.1).

مراجع

  1. ↑ WVO Quine (1971)، نظرية المجموعات ومنطقها .
  2. 1 2 إس. سي. كلين ، مقدمة في ما وراء الرياضيات (1971)، ص. 207.
  3. ↑ مكتبة الرياضيات: سلسلة من الدراسات المتخصصة في الرياضيات البحتة والتطبيقية، المجلد الأول، وولترز-نوردوف، شمال هولندا، رقم ISBN 0-7204-2103-9رقم ISBN الخاص بدار النشر Elsevier 0-444-10088-1.
  4. ↑ سمورينسكي (1977)، "نظريات عدم الاكتمال"، كتيب المنطق الرياضي ، ص 851.
  5. ↑ فلويد، بوتنام (2000)، "ملاحظة حول فقرة فيتجنشتاين الشهيرة حول نظرية غودل"
  6. ↑ هـ. فريدمان (2023)، "مغامرات في عدم اكتمال غودل" ، ص 14. تم الاطلاع عليه في 12 سبتمبر 2023.
  7. ↑ J. Barwise , ed. (1977), Handbook of Mathematical Logic , North-Holland, Amsterdam.
  8. ↑ سمورينسكي، كريغ (1985). الإحالة الذاتية والمنطق الموجه . برلين: سبرينغر. ISBN 978-0-387-96209-2.تمت مراجعته في: Boolos, G.; Smorynski, C. (1988). "الإحالة الذاتية والمنطق الموجه". مجلة المنطق الرمزي . 53 : 306. doi : 10.2307/2274450 . JSTOR 2274450 . 

فهرس