خدعة روسر

في المنطق الرياضي ، تُعدّ حيلة روسر طريقةً لإثبات صيغةٍ معدّلةٍ من نظريات عدم الاكتمال لغودل، دون الاعتماد على افتراض أن النظرية قيد الدراسة متسقةٌ من النوع ω (سمورينسكي 1977، ص  840؛ مندلسون 1977، ص  160). وقد قدّم هذه الطريقة ج. باركلي روسر عام 1936، كتحسينٍ لبرهان غودل الأصلي لنظريات عدم الاكتمال الذي نُشر عام 1931.

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

تبدأ حيلة روسر بافتراضات نظرية عدم الاكتمال لغودل. وهي نظرية${\displaystyle T}$يتم اختيار ما هو فعال ومتسق ويتضمن جزءًا كافيًا من الحساب الأساسي .

يُظهر برهان غودل أنه لأي نظرية من هذا القبيل توجد صيغة${\displaystyle \operatorname {Proof} _{T}(x,y)}$وهو ما يعني أن${\displaystyle y}$هو رمز عدد طبيعي (عدد غودل) لصيغة رياضية و${\displaystyle x}$يمثل عدد غودل لبرهان، انطلاقاً من بديهيات${\displaystyle T}$، من الصيغة المشفرة بواسطة${\displaystyle y}$(في بقية هذا المقال، لا يوجد تمييز بين العدد${\displaystyle y}$والصيغة المشفرة بواسطة${\displaystyle y}$، والرقم الذي يرمز إلى الصيغة${\displaystyle \phi }$يُشار إليه بـ${\displaystyle \#\phi }$.) علاوة على ذلك، الصيغة${\displaystyle \operatorname {Pvbl} _{T}(y)}$يُعرَّف بأنه${\displaystyle \exists x\operatorname {Proof} _{T}(x,y)}$يهدف ذلك إلى تحديد مجموعة الصيغ القابلة للإثبات من${\displaystyle T}$.

الافتراضات المتعلقة${\displaystyle T}$أظهر أيضًا أنها قادرة على تعريف دالة النفي${\displaystyle {\text{neg}}(y)}$، مع الخاصية التي إذا${\displaystyle y}$هو رمز لصيغة رياضية${\displaystyle \phi }$ثم${\displaystyle {\text{neg}}(y)}$هو رمز للصيغة${\displaystyle \neg \phi }$قد تأخذ دالة النفي أي قيمة على الإطلاق للمدخلات التي ليست رموزًا أو صيغًا.

جملة غودل في النظرية${\displaystyle T}$هي صيغة${\displaystyle \phi }$، ويشار إليه أحيانًا بـ${\displaystyle G_{T}}$بحيث${\displaystyle T}$يثبت${\displaystyle \phi }$ ↔${\displaystyle \neg \operatorname {Pvbl} _{T}(\#\phi )}$يُظهر برهان غودل أنه إذا${\displaystyle T}$إذا كانت النظرية متسقة، فلا يمكنها إثبات جملة غودل الخاصة بها؛ ولكن لإثبات أن نفي جملة غودل غير قابل للإثبات أيضًا، من الضروري إضافة افتراض أقوى مفاده أن النظرية متسقة من النوع ω ، وليست متسقة فحسب. على سبيل المثال، النظرية${\displaystyle T={\text{PA}}+\neg {\text{G}}_{PA}}$، حيث تمثل PA بديهيات بيانو ، يثبت${\displaystyle \neg G_{T}}$. قام روسر (1936) بإنشاء جملة مرجعية ذاتية مختلفة يمكن استخدامها لاستبدال جملة غودل في برهان غودل، مما يزيل الحاجة إلى افتراض الاتساق ω.

لنظرية حسابية ثابتة${\displaystyle T}$، يترك${\displaystyle \operatorname {Proof} _{T}(x,y)}$و${\displaystyle {\text{neg}}(x)}$ليكن المسند البرهاني ودالة النفي المرتبطة به.

مسند إثبات معدل${\displaystyle \operatorname {Proof} _{T}^{R}(x,y)}$يُعرَّف على النحو التالي:

$${\displaystyle \operatorname {Proof} _{T}^{R}(x,y)\equiv \operatorname {Proof} _{T}(x,y)\land \lnot \exists z\leq x[\operatorname {Proof} _{T}(z,\operatorname {neg} (y))],}$$

وهذا يعني أن

$${\displaystyle \lnot \operatorname {Proof} _{T}^{R}(x,y)\equiv \operatorname {Proof} _{T}(x,y)\to \exists z\leq x[\operatorname {Proof} _{T}(z,\operatorname {neg} (y))].}$$

تُستخدم هذه الصيغة المُعدَّلة للإثبات لتعريف صيغة مُعدَّلة لإثبات قابلية الإثبات.${\displaystyle \operatorname {Pvbl} _{T}^{R}(y)}$:

$${\displaystyle \operatorname {Pvbl} _{T}^{R}(y)\equiv \exists x\operatorname {Proof} _{T}^{R}(x,y).}$$

بشكل غير رسمي،${\displaystyle \operatorname {Pvbl} _{T}^{R}(y)}$الادعاء هو أن${\displaystyle y}$يمكن إثبات ذلك من خلال برهان مشفر.${\displaystyle x}$بحيث لا يوجد برهان مشفر أصغر لنفي${\displaystyle y}$بافتراض أن${\displaystyle T}$متسق، لكل صيغة${\displaystyle \phi }$الصيغة${\displaystyle \operatorname {Pvbl} _{T}^{R}(\#\phi )}$سيبقى ساريًا إذا وفقط إذا${\displaystyle \operatorname {Pvbl} _{T}(\#\phi )}$يثبت ذلك، لأنه إذا كان هناك رمز لإثبات${\displaystyle \phi }$ثم (تبعًا لتناسق${\displaystyle T}$لا يوجد رمز لإثبات ذلك${\displaystyle \neg \phi }$. لكن،${\displaystyle \operatorname {Pvbl} _{T}(\#\phi )}$و${\displaystyle \operatorname {Pvbl} _{T}^{R}(\#\phi )}$لها خصائص مختلفة من وجهة نظر إمكانية الإثبات في${\displaystyle T}$.

من النتائج المباشرة لهذا التعريف أنه إذا${\displaystyle T}$إذا تضمن ذلك ما يكفي من العمليات الحسابية، فإنه يمكن إثبات ذلك لكل صيغة${\displaystyle \phi }$،${\displaystyle \operatorname {Pvbl} _{T}^{R}(\phi )}$يشير إلى${\displaystyle \neg \operatorname {Pvbl} _{T}^{R}({\text{neg}}(\phi )})$وذلك لأنه بخلاف ذلك، سيكون هناك رقمان${\displaystyle n,m}$، برمجة لإثباتات${\displaystyle \phi }$و${\displaystyle \neg \phi }$، على التوالي، بما يفي بالغرضين${\displaystyle n<m}$و${\displaystyle m<n}$. (في الحقيقة${\displaystyle T}$يكفي إثبات أن مثل هذا الوضع لا يمكن أن ينطبق على أي عددين، بالإضافة إلى تضمين بعض المنطق من الدرجة الأولى .

باستخدام مبرهنة القطر ، ليكن${\displaystyle \rho }$لتكن صيغة بحيث${\displaystyle T}$يثبت${\displaystyle \rho \iff \neg \operatorname {Pvbl} _{T}^{R}(\#\rho )}$الصيغة${\displaystyle \rho }$هي جملة روسر للنظرية${\displaystyle T}$.

يترك${\displaystyle T}$أن تكون نظرية فعالة ومتسقة تتضمن قدراً كافياً من العمليات الحسابية، مع جملة روسر${\displaystyle \rho }$ثم ينطبق ما يلي (مندلسون 1977، ص  160):

1. ${\displaystyle T}$لا يثبت${\displaystyle \rho }$
2. ${\displaystyle T}$لا يثبت${\displaystyle \neg \rho }$

لإثبات ذلك، يجب أولاً إثبات أنه بالنسبة لصيغة ما${\displaystyle y}$وعدد${\displaystyle e}$، لو${\displaystyle \operatorname {Proof} _{T}^{R}(e,y)}$ثم يمسك${\displaystyle T}$يثبت${\displaystyle \operatorname {Proof} _{T}^{R}(e,y)}$. وقد تم توضيح ذلك بطريقة مماثلة لما تم في برهان غودل لنظرية عدم الاكتمال الأولى:${\displaystyle T}$يثبت${\displaystyle \operatorname {Proof} _{T}(e,y)}$، وهي علاقة بين عددين طبيعيين محددين؛ ثم يتم استعراض جميع الأعداد الطبيعية${\displaystyle z}$أصغر من${\displaystyle e}$واحداً تلو الآخر، ولكل واحد${\displaystyle z}$،${\displaystyle T}$يثبت${\displaystyle \neg \operatorname {Proof} _{T}(z,{\text{(neg}}(y))}$مرة أخرى، علاقة بين رقمين محددين.

الافتراض أن${\displaystyle T}$يتضمن ما يكفي من العمليات الحسابية (في الواقع، المطلوب هو منطق الرتبة الأولى الأساسي) ويضمن ذلك${\displaystyle T}$ويثبت ذلك أيضاً${\displaystyle \operatorname {Pvbl} _{T}^{R}(y)}$في هذه الحالة.

علاوة على ذلك، إذا${\displaystyle T}$متسق ويثبت${\displaystyle \phi }$ثم هناك عدد${\displaystyle e}$الترميز لإثبات ذلك في${\displaystyle T}$ولا يوجد ترميز رقمي لإثبات نفي${\displaystyle \phi }$في${\displaystyle T}$. لذلك${\displaystyle \operatorname {Proof} _{T}^{R}(e,y)}$يحمل، وبالتالي${\displaystyle T}$يثبت${\displaystyle \operatorname {Pvbl} _{T}^{R}(\#\phi )}$.

إن برهان (1) مشابه لبرهان غودل لنظرية عدم الاكتمال الأولى: افترض${\displaystyle T}$يثبت${\displaystyle \rho }$ثم يترتب على ذلك، من خلال التوضيح السابق، أن${\displaystyle T}$يثبت${\displaystyle \operatorname {Pvbl} _{T}^{R}(\#\rho )}$. هكذا${\displaystyle T}$ويثبت ذلك أيضاً${\displaystyle \neg \rho }$لكننا افترضنا${\displaystyle T}$يثبت${\displaystyle \rho }$وهذا مستحيل إذا${\displaystyle T}$متسق. نحن مضطرون إلى استنتاج أن${\displaystyle T}$لا يثبت${\displaystyle \rho }$.

يستخدم برهان (2) أيضًا الشكل الخاص لـ${\displaystyle \operatorname {Proof} _{T}^{R}}$. يفترض${\displaystyle T}$يثبت${\displaystyle \neg \rho }$ثم يترتب على ذلك، من خلال التوضيح السابق، أن${\displaystyle T}$يثبت${\displaystyle \operatorname {Pvbl} _{T}^{R}({\text{neg}}\#(\rho ))}$ولكن بالنتيجة المباشرة لتعريف محمول إثبات روسر، المذكور في القسم السابق، يترتب على ذلك ما يلي:${\displaystyle T}$يثبت${\displaystyle \neg \operatorname {Pvbl} _{T}^{R}(\#\rho )}$. هكذا${\displaystyle T}$ويثبت ذلك أيضاً${\displaystyle \rho }$لكننا افترضنا${\displaystyle T}$يثبت${\displaystyle \neg \rho }$وهذا مستحيل إذا${\displaystyle T}$متسق. نحن مضطرون إلى استنتاج أن${\displaystyle T}$لا يثبت${\displaystyle \neg \rho }$.

• مندلسون (1977)، مقدمة في المنطق الرياضي
• سمورينسكي (1977)، "نظريات عدم الاكتمال"، في كتاب "دليل المنطق الرياضي" ، جون باروايز ، محرر، نورث هولاند، 1982، ISBN 0-444-86388-5
• باركلي روسر (سبتمبر 1936). " توسيعات لبعض نظريات غودل وتشرش" . مجلة المنطق الرمزي . 1 (3): 87-91 . doi : 10.2307/2269028 . JSTOR 2269028. S2CID 36635388 .  

• Avigad (2007)، " قابلية الحوسبة وعدم الاكتمال "، ملاحظات المحاضرة.