الحساب الحقيقي

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

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

الهيكل​${\displaystyle {\mathcal {N}}}$يُعرَّف بأنه نموذج لحسابات بيانو على النحو التالي.

• مجال الخطاب هو المجموعة${\displaystyle \mathbb {N} }$من الأعداد الطبيعية،
• يُفسَّر الرمز 0 على أنه الرقم 0،
• تُفسَّر رموز الدوال على أنها العمليات الحسابية المعتادة على${\displaystyle \mathbb {N} }$،
• تُفسَّر رموز علاقة المساواة وعلاقة أصغر من على أنها علاقة المساواة والترتيب المعتادة.${\displaystyle \mathbb {N} }$.

يُعرف هذا الهيكل بالنموذج القياسي أو التفسير المقصود للحساب من الدرجة الأولى.

يُقال إن الجملة المكتوبة بلغة الحساب من الدرجة الأولى صحيحة في${\displaystyle {\mathcal {N}}}$إذا كان ذلك صحيحًا في البنية المحددة للتو. الترميز${\displaystyle {\mathcal {N}}\models \varphi }$تُستخدم للإشارة إلى أن الجملة${\displaystyle \varphi }$صحيح في${\displaystyle {\mathcal {N}}.}$

يُعرَّف الحساب الحقيقي بأنه مجموعة جميع الجمل في لغة الحساب من الدرجة الأولى التي تكون صحيحة في${\displaystyle {\mathcal {N}}}$، مكتوب Th(${\displaystyle {\mathcal {N}}}$) . هذه المجموعة، بشكل مكافئ، هي النظرية (الكاملة) للبنية${\displaystyle {\mathcal {N}}}$[ ^{2 ]​}

النتيجة المركزية في الحساب الحقيقي هي نظرية عدم التعريف لألفريد تارسكي (1936). تنص هذه النظرية على أن المجموعة Th(${\displaystyle {\mathcal {N}}}$لا يمكن تعريفها حسابيًا. هذا يعني أنه لا توجد صيغة لها.${\displaystyle \varphi (x)}$في لغة الحساب من الدرجة الأولى بحيث، لكل جملة θ في هذه اللغة،

${\displaystyle {\mathcal {N}}\models \theta \quad {\text{إذا وفقط إذا}}\quad {\mathcal {N}}\models \varphi ({\underline {\#(\theta )}}).}$

هنا${\displaystyle {\underline {\#(\theta )}}}$يمثل الرقم العددي لرقم غودل القانوني للجملة θ .

تُعدّ نظرية بوست نسخةً أكثر دقةً من نظرية عدم التعريف، والتي تُظهر علاقةً بين قابلية تعريف Th(${\displaystyle {\mathcal {N}}}$) ودرجات تورينج ، باستخدام التسلسل الهرمي الحسابي . لكل عدد طبيعي n ، ليكن Th _n (${\displaystyle {\mathcal {N}}}$) لتكن مجموعة جزئية من Th(${\displaystyle {\mathcal {N}}}$) تتكون فقط من الجمل التي${\displaystyle \Sigma _{n}^{0}}$أو أدنى في التسلسل الهرمي الحسابي. تُظهر نظرية بوست أنه لكل n ، فإن Th _n (${\displaystyle {\mathcal {N}}}$يمكن تعريف ) حسابيًا، ولكن فقط بصيغة ذات تعقيد أعلى من${\displaystyle \Sigma _{n}^{0}}$وبالتالي، لا يمكن لأي صيغة واحدة أن تحدد Th(${\displaystyle {\mathcal {N}}}$) ، لأن

${\displaystyle {\mbox{Th}}({\mathcal {N}})=\bigcup _{n\in \mathbb {N} }{\mbox{Th}}_{n}({\mathcal {N}})}$

لكن لا توجد صيغة واحدة يمكنها تعريف Th _n (${\displaystyle {\mathcal {N}}}$) لقيم n كبيرة بشكل تعسفي .

كما نوقش أعلاه، Th(${\displaystyle {\mathcal {N}}}$لا يمكن تعريفها حسابيًا، وفقًا لنظرية تارسكي. وتثبت نتيجة لنظرية بوست أن درجة تورينج لـ Th (${\displaystyle {\mathcal {N}}}$) يساوي 0 ^(ω) ، وبالتالي Th(${\displaystyle {\mathcal {N}}}$) ليس قابلاً للتقرير ولا قابلاً للتعداد بشكل متكرر .

ذ(${\displaystyle {\mathcal {N}}}$) يرتبط ارتباطًا وثيقًا بنظرية Th(${\displaystyle {\mathcal {R}}}$) من درجات تورينج القابلة للتعداد بشكل متكرر ، في توقيع الترتيبات الجزئية . ^{[ 3 ]} على وجه الخصوص، توجد دوال قابلة للحساب S و T بحيث:

• لكل جملة φ في توقيع الحساب من الدرجة الأولى، فإن φ تنتمي إلى Th(${\displaystyle {\mathcal {N}}}$) إذا وفقط إذا كان S ( φ ) ينتمي إلى Th(${\displaystyle {\mathcal {R}}}$) .
• لكل جملة ψ في توقيع الترتيبات الجزئية، فإن ψ تنتمي إلى Th(${\displaystyle {\mathcal {R}}}$) إذا وفقط إذا كان T ( ψ ) في Th(${\displaystyle {\mathcal {N}}}$) .

الحساب الحقيقي نظرية غير مستقرة ، وكذلك${\displaystyle 2^{\kappa }}$نماذج لكل عدد من الأعداد الأصلية التي لا تعد.${\displaystyle \kappa }$بما أن هناك أنواعًا عديدة متصلة على المجموعة الفارغة، فإن الحساب الحقيقي يحتوي أيضًا على${\displaystyle 2^{\aleph _{0}}}$ النماذج القابلة للعد. بما أن النظرية كاملة ، فإن جميع نماذجها متكافئة بشكل أساسي .

تتألف النظرية الحقيقية للحساب من الدرجة الثانية من جميع الجمل في لغة الحساب من الدرجة الثانية التي يحققها النموذج القياسي للحساب من الدرجة الثانية، والذي يمثل الجزء من الدرجة الأولى منه البنية${\displaystyle {\mathcal {N}}}$ويتكون الجزء من الدرجة الثانية من كل مجموعة جزئية من${\displaystyle \mathbb {N} }$.

النظرية الحقيقية للحساب من الدرجة الأولى، Th(${\displaystyle {\mathcal {N}}}$) هي مجموعة فرعية من النظرية الحقيقية للحساب من الدرجة الثانية، و Th(${\displaystyle {\mathcal {N}}}$يمكن تعريف ) في حساب الرتبة الثانية. ومع ذلك، فإن تعميم نظرية بوست على التسلسل الهرمي التحليلي يُظهر أن النظرية الحقيقية لحساب الرتبة الثانية لا يمكن تعريفها بأي صيغة واحدة في حساب الرتبة الثانية.

أظهر سيمبسون (1977) أن النظرية الحقيقية للحساب من الدرجة الثانية قابلة للتفسير الحسابي مع نظرية الترتيب الجزئي لجميع درجات تورينج ، في إشارة الترتيبات الجزئية، والعكس صحيح .

• بولوس، جورج ؛ بورغيس، جون ب .؛ جيفري، ريتشارد سي. (2002)، الحوسبة والمنطق (الطبعة الرابعة  )، مطبعة جامعة كامبريدج، رقم ISBN 978-0-521-00758-0.
• بوفيكين، أندريه؛ كاي، ريتشارد (2001)، "حول أنواع ترتيب نماذج الحساب"، في تشانغ، يي (محرر)، المنطق والجبر ، الرياضيات المعاصرة، المجلد  302، الجمعية الرياضية الأمريكية، الصفحات 275-285 ، ISBN  978-0-8218-2984-4.
• شور، ريتشارد (2011)، "الدرجات القابلة للتعداد التكراري"، في غريفور، إي آر (محرر)، دليل نظرية الحوسبة ، دراسات في المنطق وأسس الرياضيات، المجلد  140، نورث هولاند (نُشر عام 1999)، الصفحات 169-197 ، ISBN  978-0-444-54701-9.
• سيمبسون، ستيفن ج. (1977)، "نظرية الرتبة الأولى لدرجات عدم قابلية الحل التكراري"، حوليات الرياضيات ، السلسلة الثانية، 105 (1)، حوليات الرياضيات: 121-139 ، doi : 10.2307/1971028 ، ISSN 0003-486X ، JSTOR 1971028 ، MR 0432435   
• تارسكي، ألفريد (1936)، "مفهوم الحقيقة في اللغات الرسمية". تظهر ترجمة إنجليزية بعنوان "مفهوم الحقيقة في اللغات الرسمية" في كتاب كوركوران، ج. (محرر) (1983)، المنطق، الدلالات، وما وراء الرياضيات: أوراق بحثية من 1923 إلى 1938 ( الطبعة الثانية)، شركة هاكيت للنشر، رقم ISBN  978-0-915144-75-4

• وايسشتاين، إريك دبليو. "الحساب" . عالم الرياضيات .
• وايسشتاين، إريك دبليو. "حساب البيانو" . عالم الرياضيات .
• وايسشتاين، إريك دبليو. "نظرية تارسكي" . عالم الرياضيات .