الحساب من الدرجة الثانية

📅 آخر تحديث: ٢ أغسطس ٢٠٢٦
✍️ نُشر في: ٢ أغسطس ٢٠٢٦
📷 يحتوي على 42 صور
الموسوعة الحرة

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

قدم ديفيد هيلبرت وبول بيرنايز في كتابهما "أسس الرياضيات" (Grundlagen der Mathematik) مقدمةً للحساب من الدرجة الثانية تتضمن معاملات من الدرجة الثالثة . [ 1 ] ويُرمز إلى البديهيات القياسية للحساب من الدرجة الثانية بالرمز Z2 .

يشمل الحساب من الرتبة الثانية حساب بيانو من الرتبة الأولى ، ولكنه أقوى منه بكثير . على عكس حساب بيانو، يسمح الحساب من الرتبة الثانية بالتكميم على مجموعات الأعداد الطبيعية، بالإضافة إلى الأعداد نفسها. ولأن الأعداد الحقيقية يمكن تمثيلها كمجموعات ( غير منتهية ) من الأعداد الطبيعية بطرق معروفة، ولأن الحساب من الرتبة الثانية يسمح بالتكميم على هذه المجموعات، فمن الممكن صياغة الأعداد الحقيقية في الحساب من الرتبة الثانية. لهذا السبب، يُطلق على الحساب من الرتبة الثانية أحيانًا اسم " التحليل ". [ 2 ]

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

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

تعريف

بناء الجملة

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

تتكون الحدود الفردية من الثابت 0، والدالة الأحادية S ( دالة الخلف )، والعمليتين الثنائيتين + و⋅{\displaystyle \cdot }(الجمع والضرب). تضيف دالة التابع 1 إلى مُدخلها. تربط علاقتا = (المساواة) و < (مقارنة الأعداد الطبيعية) بين فردين، بينما تربط علاقة ∈ (الانتماء) بين فرد ومجموعة (أو فئة). وهكذا، تُعطى لغة الحساب من الدرجة الثانية في الترميز بالرمز .ل={0،S،+،⋅،=،<،∈}{\displaystyle {\mathcal {L}}=\{0,S,+,\cdot ,=,<,\in \}}.

على سبيل المثال،∀ن(ن∈X→Sن∈X){\displaystyle \forall n(n\in X\rightarrow Sn\in X)}، هي صيغة حسابية سليمة من الدرجة الثانية، وهي صيغة حسابية، ولها متغير مجموعة حر واحد X ومتغير فردي مقيد واحد n (ولكن ليس لها متغيرات مجموعة مقيدة، كما هو مطلوب من الصيغة الحسابية) — بينما∃X∀ن(ن∈X↔ن<SSSSSS0⋅SSSSSSS0){\displaystyle \exists X\forall n(n\in X\leftrightarrow n<SSSSSS0\cdot SSSSSSS0)}هي صيغة سليمة التكوين وليست حسابية، ولها متغير مجموعة محدود واحد X ومتغير فردي محدود واحد n .

علم الدلالة

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

البديهيات

أساسي

تُعرف البديهيات التالية بالبديهيات الأساسية ، أو أحيانًا بديهيات روبنسون. وتُعرف نظرية الرتبة الأولى الناتجة باسم حساب روبنسون ، وهي في جوهرها حساب بيانو بدون استقراء. مجال الخطاب للمتغيرات الكمية هو الأعداد الطبيعية ، والتي يُرمز إليها مجتمعةً بالرمز N ، بما في ذلك العضو المميز0{\displaystyle 0}، ويسمى " صفر ".

الدوال الأولية هي دالة الخلف الأحادية ، ويرمز لها بالبادئةS{\displaystyle S}و عمليتان ثنائيتان ، الجمع والضرب ، يُشار إليهما بالمعامل الوسطي "+" و "⋅{\displaystyle \cdot }"، على التوالي. هناك أيضًا علاقة ثنائية بدائية تسمى الترتيب ، ويرمز لها بالمعامل الوسطي "<".

البديهيات التي تحكم دالة الخلف والصفر :

  1. ∀م[Sم=0→⊥].{\displaystyle \forall m[Sm=0\rightarrow \bot ].}(العدد التالي للعدد الطبيعي لا يساوي الصفر أبدًا)
  2. ∀م∀ن[Sم=Sن→م=ن].{\displaystyle \forall m\forall n[Sm=Sn\rightarrow m=n].}(الدالة اللاحقة أحادية )
  3. ∀ن[0=ن∨∃م[Sم=ن]].{\displaystyle \forall n[0=n\lor \exists m[Sm=n]].}(كل عدد طبيعي هو إما صفر أو عدد لاحق له)

عملية الجمع المعرفة بشكل متكرر :

  2. ∀م[م+0=م].{\displaystyle \forall m[m+0=m].}
  3. ∀م∀ن[م+Sن=S(م+ن)].{\displaystyle \forall m\forall n[m+Sn=S(m+n)].}

عملية الضرب معرفة بشكل متكرر:

  2. ∀م[م⋅0=0].{\displaystyle \forall m[m\cdot 0=0].}
  3. ∀م∀ن[م⋅Sن=(م⋅ن)+م].{\displaystyle \forall m\forall n[m\cdot Sn=(m\cdot n)+m].}

البديهيات التي تحكم علاقة الترتيب "<":

  2. ∀م[م<0→⊥].{\displaystyle \forall m[m<0\rightarrow \bot ].}(لا يوجد عدد طبيعي أصغر من الصفر)
  3. ∀ن∀م[م<Sن↔(م<ن∨م=ن)].{\displaystyle \forall n\forall m[m<Sn\leftrightarrow (m<n\lor m=n)].}
  4. ∀ن[0=ن∨0<ن].{\displaystyle \forall n[0=n\lor 0<n].}(كل عدد طبيعي يساوي صفرًا أو أكبر من صفر)
  5. ∀م∀ن[(Sم<ن∨Sم=ن)↔م<ن].{\displaystyle \forall m\forall n[(Sm<n\lor Sm=n)\leftrightarrow m<n].}

جميع هذه البديهيات هي عبارات من الدرجة الأولى . أي أن جميع المتغيرات تقع ضمن نطاق الأعداد الطبيعية وليس مجموعات منها، وهي حقيقة أقوى من كونها حسابية. علاوة على ذلك، لا يوجد سوى مُكمِّم وجودي واحد ، في البديهية 3. تُشكِّل البديهيتان 1 و2، بالإضافة إلى مخطط بديهي للاستقراء، تعريف بيانو-ديديكيند المعتاد لـ N. إن إضافة أي نوع من مخططات البديهيات للاستقراء إلى هذه البديهيات يجعل البديهيات 3 و10 و11 زائدة عن الحاجة.

مخطط الاستقراء والفهم

إذا كانت φ ( n ) صيغة حسابية من الدرجة الثانية مع متغير فردي حر n وربما متغيرات فردية أو مجموعات حرة أخرى (مكتوبة m 1 ,..., m k و X 1 ,..., X l )، فإن بديهية الاستقراء لـ φ هي البديهية التالية:

∀م1...مك∀X1...Xل((φ(0)∧∀ن(φ(ن)→φ(Sن)))→∀نφ(ن)){\displaystyle \forall m_{1}\dots m_{k}\forall X_{1}\dots X_{l}((\varphi (0)\land \forall n(\varphi (n)\rightarrow \varphi (Sn)))\rightarrow \forall n\varphi (n))}

يتكون مخطط الاستقراء من الدرجة الثانية ( الكامل ) من جميع حالات هذه البديهية، على جميع الصيغ من الدرجة الثانية.

ومن الأمثلة المهمة بشكل خاص على مخطط الاستقراء عندما تكون φ هي الصيغة "ن∈X{\displaystyle n\in X}"التعبير عن حقيقة أن n عنصر من X ( حيث X متغير مجموعة حرة): في هذه الحالة، تكون بديهية الاستقراء لـ φ هي

∀X((0∈X∧∀ن(ن∈X→Sن∈X))→∀ن(ن∈X)){\displaystyle \forall X((0\in X\land \forall n(n\in X\rightarrow Sn\in X))\rightarrow \forall n(n\in X))}

تُسمى هذه الجملة بديهية الاستقراء من الدرجة الثانية .

إذا كانت φ ( n ) صيغة تحتوي على متغير حر n وربما متغيرات حرة أخرى، ولكن ليس المتغير Z ، فإن بديهية الفهم لـ φ هي الصيغة

∃Z∀ن(ن∈Z↔φ(ن)){\displaystyle \exists Z\forall n(n\in Z\leftrightarrow \varphi (n))}

هذه البديهية تجعل من الممكن تكوين المجموعةZ={ن|φ(ن)}{\displaystyle Z=\{n|\varphi (n)\}}من الأعداد الطبيعية التي تحقق φ ( n ). هناك قيد تقني يتمثل في أن الصيغة φ لا يجوز أن تحتوي على المتغير Z ، وإلا فإن الصيغةن∉Z{\displaystyle n\not \in Z}سيؤدي ذلك إلى بديهية الفهم

∃Z∀ن(ن∈Z↔ن∉Z){\displaystyle \exists Z\forall n(n\in Z\leftrightarrow n\not \in Z)}،

وهذا غير متسق. ويُفترض هذا الاتفاق في بقية هذا المقال.

الأنظمة الكاملة

تتألف النظرية الرسمية للحساب من الرتبة الثانية (بلغة الحساب من الرتبة الثانية) من البديهيات الأساسية، وبديهية الفهم لكل صيغة φ (حسابية أو غيرها)، وبديهية الاستقراء من الرتبة الثانية. تُسمى هذه النظرية أحيانًا بالحساب الكامل من الرتبة الثانية لتمييزها عن أنظمتها الفرعية، المُعرّفة أدناه. ولأن دلالات الحساب الكامل من الرتبة الثانية تعني وجود كل مجموعة ممكنة، يُمكن اعتبار بديهيات الفهم جزءًا من النظام الاستنتاجي عند استخدام دلالات الحساب الكامل من الرتبة الثانية. [ 3 ]

نماذج

يصف هذا القسم الحساب من الدرجة الثانية بدلالات من الدرجة الأولى. وبالتالي، نموذجم{\displaystyle {\mathcal {M}}}تتألف لغة الحساب من الدرجة الثانية من مجموعة M (التي تشكل مدى المتغيرات الفردية) بالإضافة إلى ثابت 0 (عنصر من M )، ودالة S من M إلى M ، وعمليتين ثنائيتين + و · ​​على M ، وعلاقة ثنائية < على M ، ومجموعة D من المجموعات الجزئية من M ، والتي تمثل مدى متغيرات المجموعة. يؤدي حذف D إلى نموذج للغة الحساب من الدرجة الأولى.

عندما تكون D هي مجموعة القوى الكاملة لـ M ، فإن النموذجم{\displaystyle {\mathcal {M}}}يُطلق عليه نموذج كامل . استخدام دلالات الرتبة الثانية الكاملة يُكافئ حصر نماذج الحساب من الرتبة الثانية في النماذج الكاملة. في الواقع، لا يوجد سوى نموذج كامل واحد لبديهيات الحساب من الرتبة الثانية. وينتج هذا عن حقيقة أن بديهيات بيانو مع بديهية الاستقراء من الرتبة الثانية لا يوجد لها سوى نموذج واحد في ظل دلالات الرتبة الثانية.

وظائف قابلة للتحديد

إن الدوال من الدرجة الأولى التي يمكن إثبات أنها كلية في الحساب من الدرجة الثانية هي نفسها تمامًا تلك التي يمكن تمثيلها في النظام F. [ 4 ] وبشكل مكافئ تقريبًا، فإن النظام F هو نظرية الدوال المقابلة للحساب من الدرجة الثانية بطريقة موازية لكيفية توافق نظام غودل T مع الحساب من الدرجة الأولى في تفسير ديالكتيكا .

أنواع أخرى من النماذج

عندما يمتلك نموذج لغة الحساب من الدرجة الثانية خصائص معينة، يمكن تسميته أيضاً بهذه الأسماء الأخرى:

  • عندما تكون M هي المجموعة المعتادة للأعداد الطبيعية مع عملياتها المعتادة،م{\displaystyle {\mathcal {M}}}يُطلق عليه نموذج ω . في هذه الحالة، يمكن تعريف النموذج بـ D ، وهي مجموعة مجموعات الأعداد الطبيعية الخاصة به، لأن هذه المجموعة كافية لتحديد نموذج ω بشكل كامل.ω{\displaystyle \omega }يُطلق على النموذج -، وهو المجموعة المعتادة للأعداد الطبيعية ببنيتها المعتادة وجميع مجموعاتها الجزئية، اسم النموذج المقصود أو القياسي للحساب من الدرجة الثانية. [ 5 ]
  • نموذجم{\displaystyle {\mathcal {M}}}يُطلق على نموذج لغة الحساب من الدرجة الثانية اسم نموذج بيتا إذام≺11P(ω){\displaystyle {\mathcal {M}}\prec _{1}^{1}{\mathcal {P}}(\omega )}أي عبارات Σ 1 1 ذات المعاملات منم{\displaystyle {\mathcal {M}}}الذين يرضون بـم{\displaystyle {\mathcal {M}}}وهي نفسها التي يحققها النموذج الكامل. [ 6 ] تتضمن بعض المفاهيم المطلقة فيما يتعلق بنماذج بيتا ما يلي:أ⊆ω×ω{\displaystyle A\subseteq \omega \times \omega }يشفر ترتيبًا جيدًا " [ 7 ] و"أ⊆ω×ω{\displaystyle A\subseteq \omega \times \omega }هي شجرة . [ 6 ]
  • تم توسيع النتيجة المذكورة أعلاه لتشمل مفهوم نموذج β n لـن∈شمال{\displaystyle n\in \mathbb {N} }، والذي له نفس التعريف المذكور أعلاه باستثناء≺11{\displaystyle \prec _{1}^{1}}يتم استبدالها بـ≺ن1{\displaystyle \prec _{n}^{1}}، أيΣ11{\displaystyle \Sigma _{1}^{1}}يتم استبدالها بـΣن1{\displaystyle \Sigma _{n}^{1}}[ 6 ] باستخدام هذا التعريف، فإن نماذج β 0 هي نفسها نماذج ω. [ 8 ]

الأنظمة الفرعية

توجد العديد من الأنظمة الفرعية المسماة للحساب من الدرجة الثانية.

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

الفهم الحسابي

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

تُعرَّف نظرية ACA 0 بأنها النظرية التي تتألف من البديهيات الأساسية، ونظام بديهيات الفهم الحسابي (أي بديهية الفهم لكل صيغة حسابية φ )، وبديهية الاستقراء من الدرجة الثانية العادية. ويُكافئ ذلك تضمين نظام بديهيات الاستقراء الحسابي بأكمله، أي تضمين بديهية الاستقراء لكل صيغة حسابية φ .

يمكن إثبات أن مجموعة S من المجموعات الجزئية من ω تحدد نموذج ω لـ ACA 0 إذا وفقط إذا كانت S مغلقة تحت قفزة تورينج، وقابلية اختزال تورينج ، وانضمام تورينج. [ 10 ]

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

يُعدّ النظام ACA 0 امتدادًا محافظًا للحساب من الرتبة الأولى (أو بديهيات بيانو من الرتبة الأولى)، ويُعرَّف بأنه البديهيات الأساسية، بالإضافة إلى مخطط بديهيات الاستقراء من الرتبة الأولى (لجميع الصيغ φ التي لا تتضمن أي متغيرات فئوية، سواء كانت مقيدة أم لا)، وذلك بلغة الحساب من الرتبة الأولى (التي لا تسمح بمتغيرات فئوية على الإطلاق). وعلى وجه الخصوص، يمتلك النظام نفس الترتيب البرهاني ε 0 الخاص بالحساب من الرتبة الأولى، نظرًا لمخطط الاستقراء المحدود.

التسلسل الهرمي الحسابي للصيغ

تُسمى الصيغة حسابية محدودة ، أو Δ 0 0 ، عندما تكون جميع مُكمِّماتها من الشكل ∀ n < t أو ∃ n < t (حيث n هو المتغير الفردي الذي يتم تحديده كميًا و t هو حد فردي)، حيث

∀ن<ت(⋯){\displaystyle \forall n<t(\cdots )}

يرمز إلى

∀ن(ن<ت→⋯){\displaystyle \forall n(n<t\rightarrow \cdots )}

و

∃ن<ت(⋯){\displaystyle \exists n<t(\cdots )}

يرمز إلى

∃ن(ن<ت∧⋯){\displaystyle \exists n(n<t\land \cdots )}.

تُسمى الصيغة Σ 0 1 (أو أحيانًا Σ 1 )، أو Π 0 1 (أو أحيانًا Π 1 ) عندما تكون على الصورة ∃ mφ ، أو ∀ mφ، حيث φ صيغة حسابية محدودة، و m متغير فردي (حر في φ ). وبشكل أعم، تُسمى الصيغة Σ 0 n ، أو Π 0 n، عندما تُستنتج بإضافة مُكمِّمات وجودية، أو شاملة، أو فردية إلى صيغة Π 0 n − 1 ، أو Σ 0 n − 1 (وتكون كل من Σ 0 0 وΠ 0 0 مساوية لـ Δ 0 0 ). بحكم التصميم، فإن جميع هذه الصيغ حسابية (لا يتم ربط أي متغيرات فئة على الإطلاق) وفي الواقع، من خلال وضع الصيغة في شكل Skolem prenex ، يمكن للمرء أن يرى أن كل صيغة حسابية مكافئة منطقيًا لصيغة Σ 0 n أو Π 0 n لجميع قيم n الكبيرة بما فيه الكفاية .

الفهم التكراري

يُعد النظام الفرعي RCA 0 نظامًا أضعف من ACA 0 ، ويُستخدم غالبًا كنظام أساسي في الرياضيات العكسية . ويتكون من: البديهيات الأساسية، ومخطط الاستقراء Σ 0 1 ، ومخطط الفهم Δ 0 1. المصطلح الأول واضح: مخطط الاستقراء Σ 0 1 هو بديهية الاستقراء لكل صيغة φ من صيغ Σ 0 1. أما مصطلح "فهم Δ 0 1 " فهو أكثر تعقيدًا، لأنه لا يوجد ما يُسمى بصيغة Δ 0 1. بدلًا من ذلك، يُؤكد مخطط الفهم Δ 0 1 بديهية الفهم لكل صيغة Σ 0 1 تُكافئ منطقيًا صيغة ψ من صيغ Π 0 1. يتضمن هذا المخطط، لكل صيغة φ من صيغ Σ 0 1 ولكل صيغة ψ من صيغ ψ من صيغ Π 0 1 ، البديهية التالية:

∀م∀X((∀ن(φ(ن)↔ψ(ن)))→∃Z∀ن(ن∈Z↔φ(ن))){\displaystyle \forall m\forall X((\forall n(\varphi (n)\leftrightarrow \psi (n)))\rightarrow \exists Z\forall n(n\in Z\leftrightarrow \varphi (n)))}

مجموعة النتائج من الدرجة الأولى لـ RCA 0 هي نفسها مجموعة النتائج للنظام الفرعي I Σ 1 من حساب بيانو، حيث يقتصر الاستقراء على صيغ Σ 0 1. وبدورها، تُعتبر I Σ 1 محافظة على الحساب التكراري البدائي (PRA) لـΠ20{\displaystyle \Pi _{2}^{0}}الجمل. علاوة على ذلك، فإن الترتيب البرهاني لـRجأ0{\displaystyle \mathrm {RCA} _{0}}هي ω ω ، وهي نفسها قيمة PRA.

يتضح أن مجموعة S من المجموعات الجزئية من ω تُحدد نموذج ω لـ RCA 0 إذا وفقط إذا كانت S مغلقة تحت اختزال تورينج وضم تورينج. على وجه الخصوص، تُعطي مجموعة جميع المجموعات الجزئية القابلة للحساب من ω نموذج ω لـ RCA 0. هذا هو الدافع وراء تسمية هذا النظام - إذا أمكن إثبات وجود مجموعة باستخدام RCA 0 ، فإن المجموعة تكون تكرارية (أي قابلة للحساب).

الأنظمة الأضعف

أحيانًا يُفضّل نظام أضعف من RCA 0. يُعرَّف أحد هذه الأنظمة كما يلي: يجب أولًا إضافة رمز الدالة الأسية إلى لغة الحساب (في الأنظمة الأقوى، يمكن تعريف الدالة الأسية بدلالة الجمع والضرب باستخدام الحيلة المعتادة، ولكن عندما يصبح النظام ضعيفًا جدًا، يصبح ذلك غير ممكن)، وإضافة البديهيات الواضحة التي تُعرّف الأسية استقرائيًا من الضرب إلى البديهيات الأساسية؛ ثم يتكون النظام من البديهيات الأساسية (المُثرية)، بالإضافة إلى فهم Δ 0 1 ، بالإضافة إلى الاستقراء Δ 0 0 .

أنظمة أقوى

في ACA 0 ، تُكافئ كل صيغة من صيغ الحساب من الرتبة الثانية صيغة Σ 1 n أو Π 1 n لجميع قيم n الكبيرة بما فيه الكفاية . نظام الفهم Π 1 1 هو النظام الذي يتكون من البديهيات الأساسية، بالإضافة إلى بديهية الاستقراء العادية من الرتبة الثانية وبديهية الفهم لكل صيغة Π 1 1 φ ( مُشار إليها بخط غامق [ 11 ] ) . هذا يُكافئ الفهم Σ 1 1 (من ناحية أخرى، يُعد الفهم Δ 1 1 ، المُعرّف بشكل مماثل للفهم Δ 0 1 ، أضعف).

الحتمية الإسقاطية

الحتمية الإسقاطية هي التأكيد على أن كل لعبة معلومات كاملة بين لاعبين ، حيث تكون الحركات أعدادًا طبيعية، وطول اللعبة ω، ومجموعة العوائد الإسقاطية ، هي لعبة محددة، أي أن أحد اللاعبين لديه استراتيجية رابحة. (يفوز اللاعب الأول إذا كانت حركته تنتمي إلى مجموعة العوائد؛ وإلا يفوز اللاعب الثاني). تكون المجموعة إسقاطية إذا وفقط إذا كان من الممكن التعبير عنها (كمسند) بصيغة في لغة الحساب من الرتبة الثانية، مع السماح بالأعداد الحقيقية كمعاملات، وبالتالي يمكن التعبير عن الحتمية الإسقاطية كمخطط في لغة Z² .

العديد من القضايا الطبيعية التي يمكن التعبير عنها بلغة الحساب من الرتبة الثانية مستقلة عن Z² وحتى ZFC ، ولكن يمكن إثباتها من خلال التحديد الإسقاطي. تشمل الأمثلة خاصية المجموعة الجزئية الكاملة التحليلية المشتركة ، وقابلية القياس، وخاصية باير لـΣ21{\displaystyle \Sigma _{2}^{1}}مجموعات،Π31{\displaystyle \Pi _{3}^{1}}التوحيد ، وما إلى ذلك. في نظرية أساسية ضعيفة (مثل RCA 0 )، يستلزم التحديد الإسقاطي الفهم ويوفر نظرية كاملة أساسًا للحساب من الدرجة الثانية - من الصعب العثور على عبارات طبيعية في لغة Z 2 مستقلة عن Z 2 مع التحديد الإسقاطي. [ 12 ]

ZFC + {هناك n من الأعداد الأصلية لـ Woodin : n عدد طبيعي} هي محافظة على Z 2 مع تحديد إسقاطي ، أي أن العبارة في لغة الحساب من الدرجة الثانية قابلة للإثبات في Z 2 مع تحديد إسقاطي إذا وفقط إذا كانت ترجمتها إلى لغة نظرية المجموعات قابلة للإثبات في ZFC + {هناك n من الأعداد الأصلية لـ Woodin: n ∈N}.

رياضيات البرمجة

تُضفي الحسابات من الرتبة الثانية طابعًا رسميًا مباشرًا على الأعداد الطبيعية ومجموعات الأعداد الطبيعية. ومع ذلك، فهي قادرة على إضفاء طابع رسمي على كائنات رياضية أخرى بشكل غير مباشر عبر تقنيات الترميز، وهي حقيقة لاحظها فايل لأول مرة . [ 13 ] يمكن إضفاء الطابع الرسمي على الأعداد الصحيحة والأعداد النسبية والأعداد الحقيقية في النظام الفرعي RCA 0 ، إلى جانب الفضاءات المترية القابلة للفصل الكاملة والدوال المتصلة بينها. [ 14 ]

يستخدم برنامج البحث في الرياضيات العكسية هذه الصياغات الرياضية في الحساب من الرتبة الثانية لدراسة بديهيات وجود المجموعات اللازمة لإثبات النظريات الرياضية. [ 15 ] على سبيل المثال، يمكن إثبات نظرية القيمة المتوسطة للدوال من الأعداد الحقيقية إلى الأعداد الحقيقية في RCA 0 ، [ 16 ] بينما تُكافئ نظرية بولزانو - فايرشتراس ACA 0 على RCA 0. [ 17 ]

يعمل الترميز المذكور آنفًا بشكل جيد مع الدوال المتصلة والكلية، بافتراض نظرية أساسية من الرتبة العليا بالإضافة إلى مبرهنة كونيغ الضعيفة . [ 18 ] وكما هو متوقع، فإن الترميز في حالة الطوبولوجيا لا يخلو من المشاكل. [ 19 ]

انظر أيضاً

مراجع

  1. ^ هيلبرت، د . بيرنيز، ص. (1934). Grundlagen der Mathematik . سبرينغر-فيرلاغ. السيد 0237246 . 
  2. ↑ سيغ، و. (2013). برامج هيلبرت وما بعدها . مطبعة جامعة أكسفورد. ص 291. ISBN  978-0-19-970715-7.
  3. 1 2 شابيرو، ستيوارت (1991). أسس بلا أسسية: حجة لصالح منطق الرتبة الثانية . أدلة أكسفورد المنطقية. المجلد 17. مطبعة كلارندون، مطبعة جامعة أكسفورد، نيويورك. الصفحات 66، 74-75 . ISBN   0-19-853391-8MR 1143781 .​ 
  4. ↑ جيرار، جان إيف (1987). البراهين والأنواع . ترجمة تايلور، بول. مطبعة جامعة كامبريدج. ص 122-123 . ISBN  0-521-37181-3.
  5. ↑ سيمبسون، إس جي (2009). الأنظمة الفرعية للحساب من الدرجة الثانية . منظورات في المنطق ( الطبعة الثانية). مطبعة جامعة كامبريدج. ص 3-4 . ISBN   978-0-521-88439-6MR 2517689 .​ 
  6. 1 2 3 ماريك، و. (1974-1975). "المجموعات المستقرة، توصيف نماذج β 2 للحساب من الرتبة الثانية الكاملة وبعض الحقائق ذات الصلة" . Fundamenta Mathematicae . 82 : 175-189 . doi : 10.4064/fm-82-2-175-189 . MR 0373897 . 
  7. ↑ ماريك، و. (1978). " نماذج ω للحساب من الرتبة الثانية والمجموعات المقبولة" . Fundamenta Mathematicae . 98 (2): 103–120 . doi : 10.4064/fm-98-2-103-120 . MR 0476490 . 
  8. ↑ ماريك، و. (1973). "ملاحظات حول الامتدادات الأولية لنماذج ω . الجزء الثاني". مجلة المنطق الرمزي . 38 : 227-231 . doi : 10.2307/2272059 . JSTOR 2272059. MR 0337612 .  
  9. ↑ فريدمان، هـ. (1976). "أنظمة الحساب من الرتبة الثانية مع الاستقراء المقيد، الجزء الأول والثاني". اجتماع جمعية المنطق الرمزي. مجلة المنطق الرمزي (ملخصات). 41 : 557-559 . JSTOR 2272259 . 
  10. ↑ سيمبسون 2009 ، ص 311-313.
  11. ↑ ويلش، ب. د. (2011). "أنظمة التحديد الضعيفة والتعريفات شبه الاستقرائية الحسابية" (ملف PDF) . مجلة المنطق الرمزي . 76 (2): 418-436 . doi : 10.2178/jsl/1305810756 . MR 2830409 . 
  12. ↑ وودين، دبليو إتش (2001). "فرضية الاستمرارية، الجزء الأول". إشعارات الجمعية الرياضية الأمريكية . 48 (6).
  13. ↑ سيمبسون 2009 ، ص 16.
  14. ↑ سيمبسون 2009 ، الفصل الثاني.
  15. ↑ سيمبسون 2009 ، ص 32.
  16. ↑ سيمبسون 2009 ، ص 87.
  17. ↑ سيمبسون 2009 ، ص 34.
  18. ↑ كولينباخ، أولريش (2002). "الاستخدامات التأسيسية والرياضية للأنواع العليا". تأملات في أسس الرياضيات: مقالات تكريمًا لسولومون فيفرمان، أوراق من الندوة التي عُقدت في جامعة ستانفورد، ستانفورد، كاليفورنيا، 11-13 ديسمبر 1998. سلسلة محاضرات في المنطق. المجلد 15. أوربانا، إلينوي: جمعية المنطق الرمزي. الصفحات 92-116 . ISBN   1-56881-169-1. MR 1943304 . 
  19. ↑ هنتر، جيمس (2008). الطوبولوجيا العكسية من الرتبة العليا (ملف PDF) (أطروحة دكتوراه). جامعة ماديسون-ويسكونسن.

للمزيد من القراءة