حساب روبنسون

في الرياضيات ، يعتبر حساب روبنسون جزءًا من حساب بيانو من الدرجة الأولى (PA) ذو بديهيات محدودة ، وقد تم وضعه لأول مرة بواسطة رافائيل م. روبنسون في عام 1950. ^[¹^] ويرمز إليه عادة بـ Q.

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

البديهيات

تعتمد منطق Q الأساسي على منطق الرتبة الأولى مع عنصر محايد ، ويُرمز له بالرمز '='. تُسمى الأفراد، وهي الأعداد الطبيعية ، أعضاءً في مجموعة تُسمى N، ولها عنصر مميز هو 0 ، ويُسمى الصفر . توجد ثلاث عمليات على N :

عملية أحادية تسمى العملية اللاحقة ويرمز لها بالبادئة S ؛
عمليتان ثنائيتان ، الجمع والضرب ، ويرمز لهما بالرمز + و · على التوالي.

البديهيات التالية لـ Q هي Q1–Q7 في بورغيس (2005 ، ص 42) (انظر أيضًا بديهيات الحساب من الدرجة الأولى ). المتغيرات غير المقيدة بمحدد كمي وجودي مقيدة بمحدد كمي كلي ضمني .

Sx ≠ 0
- الصفر ليس العدد التالي لأي عدد.
( Sx = Sy ) → x = y
- إذا كان العنصر التالي لـ x مطابقًا للعنصر التالي لـ y ، فإن x و y متطابقان. تُعطي المعادلتان (1) و(2) الحد الأدنى من الحقائق حول N (مجموعة غير منتهية محدودة بـ 0) و S (دالة أحادية مجالها N ) اللازمة لعدم التافهة . وينتج عكس ( 2 ) من خصائص التطابق .
y = 0 ∨ ∃ x ( Sx = y )
- كل عدد إما أن يكون صفرًا أو العدد التالي لعدد ما. إن مخطط البديهيات في الاستقراء الرياضي الموجود في الحساب، والذي يفوق قوة Q، يحول هذه البديهية إلى نظرية.
x + 0 = x
x + Sy = S ( x + y )
- (4) و (5) هما التعريف التكراري للجمع .
x · 0 = 0
x·Sy = ( x·y ) + x
- (6) و (7) هما التعريف التكراري للضرب .

البديهيات المتغيرة

البديهيات الواردة في كتاب روبنسون (1950) هي (1)–(13) في كتاب مندلسون (2015 ، الصفحات 202–203) . ولا تُشترط البديهيات الست الأولى من بديهيات روبنسون الثلاث عشرة إلا عندما لا يتضمن المنطق الأساسي، على عكس الحالة الراهنة، مبدأ الهوية.

يمكن تعريف الترتيب الكلي الصارم المعتاد على N ، "أصغر من" (يرمز له بـ "<")، بدلالة الجمع من خلال القاعدة x < y ↔ ∃ z ( Sz + x = y ) . وبالمثل، نحصل على امتداد تعريفي محافظ لـ Q باعتبار "<" عملية أولية وإضافة هذه القاعدة كمسلمة ثامنة؛ ويُطلق على هذا النظام اسم " حساب روبنسون R " في Boolos وBurgess و Jeffrey (2002 ، القسم 16.4) .

يتم الحصول على امتداد مختلف لـ Q ، والذي نسميه مؤقتًا Q+ ، إذا أخذنا "<" كعنصر أولي وأضفنا (بدلاً من البديهية التعريفية الأخيرة) البديهيات الثلاث التالية إلى البديهيات (1)–(7) من Q : ^{[ 2 ]}

¬( x < 0)
س < سي ↔ ( س < ص ∨ س = ص )
x < y ∨ x = y ∨ y < x

لا تزال Q+ امتدادًا محافظًا لـ Q ، بمعنى أن أي صيغة قابلة للإثبات في Q+ لا تحتوي على الرمز "<" قابلة للإثبات بالفعل في Q. (إضافة أول بديهيتين فقط من البديهيات الثلاث المذكورة أعلاه إلى Q تعطي امتدادًا محافظًا لـ Q مكافئًا لما يسميه بورغيس (2005 ، ص 56) بـ Q* . انظر أيضًا بورغيس (2005 ، ص 230، حاشية 24) ، ولكن لاحظ أن البديهية الثانية من البديهيات الثلاث المذكورة أعلاه لا يمكن استنتاجها من "الامتداد التعريفي البحت" لـ Q الذي تم الحصول عليه بإضافة البديهية x < y ↔ ∃ z ( Sz + x = y ) فقط ).

من بين البديهيات (1) إلى (7) في Q ، تحتاج البديهية (3) إلى مُكمِّم وجودي داخلي. يقدم شوينفيلد (1967 ، ص 22) نظامًا بديهيًا يحتوي فقط على مُكمِّمات كلية خارجية (ضمنية)، وذلك بالاستغناء عن البديهية (3) من Q وإضافة البديهيات الثلاث المذكورة أعلاه مع اعتبار < عنصرًا أساسيًا. أي أن نظام شوينفيلد هو Q+ ناقص البديهية (3)، وهو أضعف من Q+ ، لأن البديهية (3) مستقلة عن البديهيات الأخرى (على سبيل المثال، الأعداد الترتيبية الأصغر من $\أوميغا ^{\أوميغا }$ يشكل نموذجًا لجميع البديهيات باستثناء (3) عندما تُفسَّر Sv على أنها v + 1. يظهر نظام شوينفيلد أيضًا في بولوس، بورغيس وجيفري (2002 ، القسم 16.2) ، حيث يُطلق عليه اسم " الحساب الأدنى " (ويُرمز إليه أيضًا بـ Q ). يمكن إيجاد نظام بديهي وثيق الصلة، يستخدم "≤" بدلًا من "<"، في ماتشوفر (1996 ، الصفحات 256-257) .

الرياضيات الفوقية

للاطلاع على ما وراء الرياضيات في Q، انظر: Boolos, Burgess & Jeffrey (2002 ، الفصل 16) ، Tarski, Mostowski & Robinson (1953) ، Smullyan (1991) ، Mendelson (2015 ، الصفحات 202-203)، و Burgess (2005 ، الفقرتان 1.5a و2.2) . التفسير المقصود لـ Q هو الأعداد الطبيعية وعملياتها الحسابية المعتادة، حيث يكون للجمع والضرب معناهما المتعارف عليه، والعنصر المحايد هو المساواة ، وSx = x + 1، و 0 هو العدد الطبيعي الصفر .

أي نموذج (بنية) يحقق جميع بديهيات Q باستثناء البديهية (3) ربما، له نموذج فرعي فريد ("الجزء القياسي") متماثل مع الأعداد الطبيعية القياسية ( N ، +، ·، S، 0) . (لا يشترط تحقق البديهية (3)؛ على سبيل المثال، تشكل كثيرات الحدود ذات المعاملات الصحيحة غير السالبة نموذجًا يحقق جميع البديهيات باستثناء (3).)

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

من أبرز خصائص لغة Q غياب مخطط الاستقراء البديهي . لذا، يُمكن في كثير من الأحيان إثبات كل حالة محددة من حقائق الأعداد الطبيعية في Q ، ولكن ليس النظرية العامة المرتبطة بها. على سبيل المثال، يُمكن إثبات 5 + 7 = 7 + 5 في Q ، بينما لا يُمكن إثبات العبارة العامة x + y = y + x . وبالمثل، لا يُمكن إثبات العبارة العامة Sx ≠ x . ^{[ 3 ]} يتم الحصول على نموذج لـ Q لا يفي بالعديد من الحقائق القياسية عن طريق إضافة عنصرين جديدين مختلفين a و b إلى النموذج القياسي للأعداد الطبيعية وتعريف Sa = a و Sb = b و x + a = b و x + b = a لجميع قيم x ، و a + n = a و b + n = b إذا كان n عددًا طبيعيًا قياسيًا، و x · 0 = 0 لجميع قيم x ، و a · n = b و b · n = a إذا كان n عددًا طبيعيًا قياسيًا غير صفري، و x · a = a لجميع قيم x باستثناء x = a ، و x · b = b لجميع قيم x باستثناء x = b ، و a · a = b ، و b · b = a . ^{[ 4 ]}

يمكن تفسير Q في جزء من نظرية المجموعات البديهية لزيرميلو ، والتي تتألف من الامتداد ، ووجود المجموعة الفارغة ، وبديهية الاقتران . هذه النظرية هي S' في تارسكي، موستوفسكي ، وروبنسون (1953 ، ص 34) وST في بورغيس (2005 ، ص 90-91، 223) . انظر نظرية المجموعات العامة لمزيد من التفاصيل.

Q هي نظرية من الدرجة الأولى ذات بديهيات محدودة ، وهي أضعف بكثير من حساب بيانو (PA)، وتحتوي بديهياتها على مُكمِّم وجودي واحد فقط . ومع ذلك، فهي، مثل حساب بيانو، غير مكتملة وغير قابلة للاكتمال وفقًا لنظريات عدم الاكتمال لغودل ، وغير قابلة للتقرير أساسًا. استنتج روبنسون (1950) بديهيات Q (1)–(7) المذكورة أعلاه من خلال تحديد بديهيات حساب بيانو المطلوبة ^{[ 5 ]} لإثبات أن كل دالة قابلة للحساب قابلة للتمثيل في حساب بيانو. ^{[ 6 ]} الاستخدام الوحيد لهذا البرهان لمخطط بديهيات حساب بيانو للاستقراء هو إثبات عبارة البديهية (3) أعلاه، وبالتالي، فإن جميع الدوال القابلة للحساب قابلة للتمثيل في Q. ^{[ 7 ]}^{[ 8 ]}^{[ 9 ]} تنطبق نتيجة نظرية عدم الاكتمال الثانية لغودل أيضًا على Q : لا يمكن لأي امتداد متسق ومُؤَسَّس بشكل متكرر لـ Q أن يثبت اتساقه، حتى لو قمنا بتقييد عدد براهين غودل إلى قطع قابل للتحديد. ^{[ 10 ]}^{[ 11 ]}^{[ 12 ]}

تنطبق نظرية عدم الاكتمال الأولى فقط على الأنظمة البديهية التي تُعرّف حسابات كافية لتنفيذ عمليات الترميز اللازمة (والتي يُعدّ ترقيم غودل جزءًا منها). وقد اختيرت بديهيات Q تحديدًا لضمان قوتها الكافية لهذا الغرض. وبالتالي، يمكن استخدام البرهان المعتاد لنظرية عدم الاكتمال الأولى لإثبات أن Q غير مكتملة وغير قابلة للتقرير. وهذا يُشير إلى أن عدم اكتمال PA وعدم قابليتها للتقرير لا يُمكن إرجاعهما إلى الجانب الوحيد الذي يُميّزها عن Q ، ألا وهو مخطط بديهيات الاستقراء .

لا تنطبق نظريات غودل عند حذف أيٍّ من البديهيات السبع المذكورة أعلاه. تبقى هذه الأجزاء من Q غير قابلة للتقرير، لكنها لم تعد غير قابلة للتقرير جوهريًا: إذ لها امتدادات متسقة قابلة للتقرير، بالإضافة إلى نماذج غير مثيرة للاهتمام (أي نماذج ليست امتدادات نهائية للأعداد الطبيعية القياسية).

انظر أيضاً

مراجع

↑ روبنسون 1950 .
↑ تورلاكيس 2022 ، ص 345، 12.6 حساب روبنسون.
↑ بورغيس 2005 ، ص 56.
↑ Boolos, Burgess & Jeffrey 2002 , القسم 16.4.
↑ ميندلسون 2015 ، ص 188، الاقتراح 3.24.
↑ دالة $f$ ويُقال إنه قابل للتمثيل في $\operatorname {PA}$ إذا كانت هناك صيغة $\phi$ بحيث يكون ذلك لجميع $x_{1},\cdots ,x_{k},y$
$f({\vec {x}})=y\Longleftrightarrow \operatorname {PA} \vdash \phi ({\vec {x}},y),$
$f({\vec {x}})\neq y\Longleftrightarrow \operatorname {PA} \vdash \lnot \phi ({\vec {x}},y).$
↑ أوديفردي 1989 .
↑ مندلسون 2015 ، ص 203، الاقتراح 3.33.
↑ راوتنبرغ 2010 ، ص 246.
↑ بيزبورواه وشيبيردسون 1976 .
↑ بودلاك 1985 .
^ هاجيك وبودلاك 1993 ، ص. 387.

فهرس

بيزبورواه، أ.؛ شيبردسون، جون س. (يونيو 1976). "نظرية غودل الثانية لعدم الاكتمال لـ Q". مجلة المنطق الرمزي . 41 (2): 503-512 . doi : 10.2307/2272251 . JSTOR 2272251 .
بولوس، جورج ؛ بورغيس، جون ب .؛ جيفري، ريتشارد (2002). الحوسبة والمنطق (الطبعة الرابعة ). مطبعة جامعة كامبريدج . ISBN 0-521-00758-5.
بورغيس، جون ب. (يوليو 2005). إصلاح فريجه . مطبعة جامعة برينستون . ISBN 978-0691122311.
Hajek, بيتر ; بودلاك، بافيل (1993). الرياضيات الوصفية للحساب من الدرجة الأولى ( الطبعة الثانية). سبرينغر-فيرلاغ .
جونز، جيمس ب. شيفردسون، جون سي. (1983). “المتغيرات من نظرية روبنسون غير القابلة للتقرير بشكل أساسيR”. أرشيف المنطق الرياضي و Grundlagenforschung . 23 : 61 – 64. دوى : 10.1007 / BF02023013 . S2CID 2659126 .
لوكاس، جون ر. الجذور المفاهيمية للرياضيات . روتليدج.
ماتشوفر، موشيه (1996). نظرية المجموعات، والمنطق، وحدودهما . مطبعة جامعة كامبريدج .
مندلسون، إليوت (2015). مقدمة في المنطق الرياضي ( الطبعة السادسة). تشابمان وهول. ISBN 9781482237726.
أوديفردي، بييرجيورجيو (1989). نظرية الاستدعاء الذاتي الكلاسيكية، المجلد 1 (نظرية الدوال ومجموعات الأعداد الطبيعية) . دراسات في المنطق وأسس الرياضيات. المجلد 125. نورث هولاند. ISBN 9780444894830.
بودلاك، بافيل (يونيو 1985). "القطع، وبيانات الاتساق ، والتفسيرات". مجلة المنطق الرمزي . 50 (2): 423-441 . doi : 10.2307/2274231 . JSTOR 2274231. S2CID 30289163 .
راوتنبرغ، وولفغانغ (2010). مقدمة موجزة في المنطق الرياضي ( الطبعة الثالثة). نيويورك: سبرينغر ساينس + بيزنس ميديا . doi : 10.1007/978-1-4419-1221-3 . ISBN 978-1-4419-1220-6..
روبنسون، رافائيل م. (1950). "نظام بديهي غير قابل للتقرير أساساً". وقائع المؤتمر الدولي للرياضيات . الصفحات 729-730 . LCCN 52001808 .
شوينفيلد، جوزيف ر. (1967). المنطق الرياضي . أديسون ويسلي. (أعيد طبعه بواسطة جمعية المنطق الرمزي و أ. ك. بيترز في عام 2000).
سموليان، ريموند (1991). نظريات عدم الاكتمال لغودل . مطبعة جامعة أكسفورد .
تارسكي، ألفريد ؛ موستوفسكي، أندريه ؛ روبنسون، رافائيل م. (1953). النظريات غير القابلة للتقرير . نورث هولاند.
تورلاكيس، جورج (2022). قابلية الحوسبة . تشام، سويسرا: سبرينغر. ISBN 978-3-030-83202-5.
فوغت، روبرت ل. (1966). "حول نظرية لكوبهام تتعلق بالنظريات غير القابلة للتقرير". المنطق، المنهجية، وفلسفة العلوم: وقائع المؤتمر الدولي لعام 1960. دراسات في المنطق وأسس الرياضيات. المجلد 44. شركة نورث هولاند للنشر. الصفحات 14-25 . doi : 10.1016/S0049-237X(09)70566-X . ISBN 9780804700962.

[FOOTNOTERobinson1950-1] روبنسون 1950 .

[FOOTNOTETourlakis202234512.6_Robinson's_Arithmetic-2] تورلاكيس 2022 ، ص 345، 12.6 حساب روبنسون.

[FOOTNOTEBurgess200556-3] بورغيس 2005 ، ص 56.

[FOOTNOTEBoolosBurgessJeffrey2002Sec_16.4-4] Boolos, Burgess & Jeffrey 2002 , القسم 16.4.

[FOOTNOTEMendelson2015188Proposition_3.24-5] ميندلسون 2015 ، ص 188، الاقتراح 3.24.

[6] دالة $f$ ويُقال إنه قابل للتمثيل في $\operatorname {PA}$ إذا كانت هناك صيغة $\phi$ بحيث يكون ذلك لجميع $x_{1},\cdots ,x_{k},y$
$f({\vec {x}})=y\Longleftrightarrow \operatorname {PA} \vdash \phi ({\vec {x}},y),$
$f({\vec {x}})\neq y\Longleftrightarrow \operatorname {PA} \vdash \lnot \phi ({\vec {x}},y).$

[FOOTNOTEOdifreddi1989-7] أوديفردي 1989 .

[FOOTNOTEMendelson2015203Proposition_3.33-8] مندلسون 2015 ، ص 203، الاقتراح 3.33.

[FOOTNOTERautenberg2010246-9] راوتنبرغ 2010 ، ص 246.

[FOOTNOTEBezboruahShepherdson1976-10] بيزبورواه وشيبيردسون 1976 .

[FOOTNOTEPudlák1985-11] بودلاك 1985 .

[FOOTNOTEHájekPudlák1993387-12] هاجيك وبودلاك 1993 ، ص. 387.

[

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗