حساب سكوليم

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

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

نُعرّف الاختصارات التالية.

$${\displaystyle {\begin{aligned}a\mid b&:=\exists n\;(a\cdot n=b)\\\operatorname {One} (e)&:=\forall n\;(n\cdot e=n)\\\operatorname {Prime} (p)&:=\lnot \operatorname {One} (p)\land \forall a\;(a\mid p\to (\operatorname {One} (a)\lor a=p))\\\operatorname {PrimePower} (p,P)&:=\operatorname {Prime} (p)\land p\mid P\land \forall q\;(\operatorname {Prime} (q)\land \lnot (q=p)\to \lnot (q\mid P))\\\operatorname {InvAdicAbs} (p,n,P)&:=\operatorname {PrimePower} (p,P)\land P\mid n\land \forall Q\;((\operatorname {PrimePower} (p,Q)\land Q\mid n)\to Q\mid P)\\\operatorname {AdicAbsDiff} _{n}(p,a,b)&:=\operatorname {Prime} (p)\land p\mid ab\land \exists P\,\exists Q\;(\operatorname {InvAdicAbs} (p,a,P)\land \operatorname {InvAdicAbs} (p,b,Q)\land Q=p^{n}P)\end{aligned}}}$$ بعبارات بسيطة:

• ${\displaystyle \operatorname {InvAdicAbs} (p,n,P)}$يتحقق إذا وفقط إذا${\displaystyle P}$هو أكبر قوة عددية صحيحة لـ${\displaystyle p}$ذلك يقسم${\displaystyle n}$بالضبط.

• ${\displaystyle \operatorname {AdicAbsDiff} _{n}(p,a,b)}$يتحقق ذلك إذا وفقط إذا كان التقييم p-adic لـ${\displaystyle b}$^{[ 3 ]} يتجاوز التقييم p-adic لـ${\displaystyle a}$بالضبط${\displaystyle n}$، أي${\displaystyle v_{p}(b)=v_{p}(a)+n}$.

بديهيات حساب سكوليم هي: ^{[ 4 ]}

1. ${\displaystyle \forall a\,\forall b\;(ab=ba)}$
2. ${\displaystyle \forall a\,\forall b\,\forall c\;((ab)c=a(bc))}$
3. ${\displaystyle \exists e\;\operatorname {One} (e)}$
4. ${\displaystyle \forall a\,\forall b\;(\operatorname {One} (ab)\to \operatorname {One} (a)\land \operatorname {One} (b))}$
5. ${\displaystyle \forall a\,\forall b\,\forall c\;(ac=bc\to a=b)}$
6. ${\displaystyle \forall a\,\forall b\;(a^{n}=b^{n}\to a=b){\text{ for each integer }}n>0}$
7. ${\displaystyle \forall x\,\exists a\,\exists r\;(x=ar^{n}\land \forall b\,\forall s\;(x=bs^{n}\to a\mid b)){\text{ for each integer }}n>0}$
8. ${\displaystyle \forall a\,\exists p\;(\operatorname {Prime} (p)\land \lnot (p\mid a))}$^{[ 5 ]}
9. ${\displaystyle \forall p\,\forall P\,\forall Q\;((\operatorname {PrimePower} (p,P)\land \operatorname {PrimePower} (p,Q))\to (P\mid Q\lor Q\mid P))}$
10. ${\displaystyle \forall p\,\forall n\;(\operatorname {Prime} (p)\to \exists P\;\operatorname {InvAdicAbs} (p,n,P))}$
11. ${\displaystyle \forall n\,\forall m\;\left(n=m\leftrightarrow \forall p\;(\operatorname {Prime} (p)\to \exists P\;(\operatorname {InvAdicAbs} (p,n,P)\land \operatorname {InvAdicAbs} (p,m,P)))\right)}$^{[ 6 ]}
12. ${\displaystyle \forall p\,\forall n\,\forall m\;\left(\operatorname {Prime} (p)\to \exists P\,\exists Q\;(\operatorname {InvAdicAbs} (p,n,P)\land \operatorname {InvAdicAbs} (p,m,Q)\land \operatorname {InvAdicAbs} (p,nm,PQ))\right)}$^{[ 7 ]}
13. ${\displaystyle \forall a\,\forall b\;\left(\forall p\;(\operatorname {Prime} (p)\to \exists P\,\exists Q\;(\operatorname {InvAdicAbs} (p,a,P)\land \operatorname {InvAdicAbs} (p,b,Q)\land P\mid Q))\to a\mid b\right)}$^{[ 8 ]}
14. ${\displaystyle \forall a\,\forall b\,\exists c\,\forall p\;\left(\operatorname {Prime} (p)\to \left((p\mid a\to \exists P\;(\operatorname {InvAdicAbs} (p,b,P)\land \operatorname {InvAdicAbs} (p,c,P)))\land (p\mid b\to p\mid a)\right)\right)}$^{[ 9 ]}
15. ${\displaystyle \forall a\,\exists b\,\forall p\;\left(\operatorname {Prime} (p)\to \left(\exists P\;(\operatorname {InvAdicAbs} (p,a,P)\land \operatorname {InvAdicAbs} (p,b,pP))\right)\land (p\mid b\to p\mid a)\right)}$^{[ 10 ]}
16. ${\displaystyle \forall a\,\forall b\,\exists c\,\forall p\;\left(\operatorname {Prime} (p)\to \left((\operatorname {AdicAbsDiff} _{n}(p,a,b)\to \operatorname {InvAdicAbs} (p,c,p))\land (p\mid c\to \operatorname {AdicAbsDiff} _{n}(p,a,b))\right)\right)}$^{[ 11 ]}

يمكن لمنطق الرتبة الأولى، الذي يتضمن المساواة وضرب الأعداد الصحيحة الموجبة، أن يعبر عن العلاقة ${\displaystyle c=a\cdot b}$باستخدام هذه العلاقة والمساواة، يمكننا تعريف العلاقات التالية على الأعداد الصحيحة الموجبة:

• قابلية القسمة:${\displaystyle b|c\ \Leftrightarrow \ \exists a(c=a\cdot b)}$
• القاسم المشترك الأكبر :${\displaystyle d=\gcd(a,b)\ \Leftrightarrow \ d|a\land d|b\land \forall d'((d'|a\land d'|b)\Rightarrow d'|d)}$
• المضاعف المشترك الأصغر :${\displaystyle m=\mathrm {lcm} (a,b)\ \Leftrightarrow \ a|m\land b|m\land \forall m'((a|m'\land b|m')\Rightarrow m|m')}$
• الثابت${\displaystyle 1}$:${\displaystyle \forall a(1|a)}$
• العدد الأولي :${\displaystyle \mathrm {prime} (p)\ \Leftrightarrow \ p\neq 1\land \forall a(a|p\Rightarrow (a=1\lor a=p))}$
• رقم${\displaystyle b}$هو منتج من${\displaystyle k}$الأعداد الأولية (لعدد ثابت)${\displaystyle k}$):${\displaystyle \exists a_{1},...a_{k}(\ \mathrm {prime} (a_{1})\land \ldots \land \mathrm {prime} (a_{k})\land b=a_{1}\cdot \ldots \cdot a_{k})}$
• رقم${\displaystyle b}$هي قوة لعدد أولي ما:${\displaystyle \mathrm {ppower} (b)\ \Leftrightarrow \ \exists p(\mathrm {prime} (p)\land \forall a((a\neq 1\land a|b)\Rightarrow p|a))}$
• رقم${\displaystyle b}$هو نتاج بالضبط${\displaystyle k}$القوى الرئيسية:${\displaystyle \exists a_{1},...a_{k}(\ \mathrm {ppower} (a_{1})\land \ldots \land \mathrm {ppower} (a_{k})\land b=a_{1}\cdot \ldots \cdot a_{k})}$

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

بتفصيل أكثر، وفقًا للنظرية الأساسية في الحساب ، فإن العدد الصحيح الموجب${\displaystyle a>1}$يمكن تمثيلها كناتج ضرب قوى أولية:

${\displaystyle a=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots }$

إذا كان عددًا أوليًا${\displaystyle p_{k}}$إذا لم يظهر كعامل، فإننا نحدد أسه${\displaystyle a_{k}}$أن تكون صفرًا. وبالتالي، فإن عددًا محدودًا فقط من الأسس غير صفري في المتتالية اللانهائية${\displaystyle a_{1},a_{2},\ldots }$. نرمز إلى هذه المتتاليات من الأعداد الصحيحة غير السالبة بـ${\displaystyle N^{*}}$.

والآن، لننظر في تحليل عدد موجب آخر،

${\displaystyle b=p_{1}^{b_{1}}p_{2}^{b_{2}}\cdots }$

الضرب${\displaystyle ab}$يتوافق ذلك مع الجمع النقطي للأسس:

${\displaystyle ab=p_{1}^{a_{1}+b_{1}}p_{2}^{a_{2}+b_{2}}\cdots }$

عرّف عملية الجمع النقطي المقابلة على المتتاليات كما يلي:

${\displaystyle (a_{1},a_{2},\ldots ){\bar {+}}(b_{1},b_{2},\ldots )=(a_{1}+b_{1},a_{2}+b_{2},\ldots )}$

وبالتالي، لدينا تماثل بين بنية الأعداد الصحيحة الموجبة مع عملية الضرب،${\displaystyle (N,\cdot )}$وجمع متواليات الأعداد الصحيحة غير السالبة نقطة بنقطة، والتي لا تحتوي إلا على عدد محدود من العناصر غير الصفرية،${\displaystyle (N^{*},{\bar {+}})}$.

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

قام فيرانتي وراكوف (1979 ، الفصل 5) بوضع طريقة، باستخدام ألعاب إهرنفويشت-فرايسي ، لإثبات حدود عليا لتعقيد مسألة القرار للقوى المباشرة الضعيفة للنظريات. وقد طبقا هذه الطريقة للحصول على تعقيد مكاني أسي ثلاثي لـ${\displaystyle (N^{*},{\bar {+}})}$وبالتالي، من حساب سكوليم.

يثبت غرادل (1989 ، القسم 5) أن مشكلة الإرضاء للجزء الخالي من المحددات الكمية من حساب سكوليم تنتمي إلى فئة تعقيد NP .

بفضل الاختزال المذكور أعلاه باستخدام نظرية فيفرمان-فوت، يمكننا الحصول على نظريات من الدرجة الأولى تُعرّف صيغها المفتوحة مجموعة أكبر من العلاقات إذا قمنا بتعزيز نظرية المجموعات المتعددة للعوامل الأولية. على سبيل المثال، لننظر في العلاقة التالية:${\displaystyle a\sim b}$هذا صحيح إذا وفقط إذا${\displaystyle a}$و${\displaystyle b}$لها نفس العدد من العوامل الأولية المختلفة:

${\displaystyle |\{p\mid \mathrm {prime} (p)\land (p|a)\}|\ =\ |\{p\mid \mathrm {prime} (p)\land (p|b)\}|}$

على سبيل المثال،${\displaystyle 2^{10}\cdot 3^{100}\sim 5^{8}\cdot 19^{9}}$لأن كلا الجانبين يشيران إلى عدد له عاملان أوليان مختلفان.

إذا أضفنا العلاقة${\displaystyle \sim }$بالنسبة لحسابات سكوليم، تظل المسألة قابلة للتقرير. وذلك لأن نظرية مجموعات المؤشرات تظل قابلة للتقرير في وجود عامل التساوي العددي على المجموعات، كما هو موضح في نظرية فيفرمان-فوت .

امتداد لحسابات سكوليم مع مسند اللاحق،${\displaystyle succ(n)=n+1}$يمكن تعريف علاقة الجمع باستخدام متطابقة تارسكي: ^{[ 13 ] [ 14 ]}

${\displaystyle (c=0\lor c=a+b)\Leftrightarrow (ac+1)(bc+1)=c^{2}(ab+1)+1}$

وتحديد العلاقة${\displaystyle c=a+b}$على الأعداد الصحيحة الموجبة بواسطة

${\displaystyle \mathrm {succ} (ac)\,\mathrm {succ} (bc)=\mathrm {succ} (c^{2}\mathrm {succ} (ab))}$

لأنها تستطيع التعبير عن كل من الضرب والجمع، فإن النظرية الناتجة غير قابلة للتقرير.

إذا كان لدينا دالة ترتيب على الأعداد الطبيعية (أصغر من،${\displaystyle <}$يمكننا التعبير عن${\displaystyle \mathrm {succ} }$بواسطة

${\displaystyle \mathrm {succ} (a)=b\ \ \Leftrightarrow \ \ a<b\land \forall c.{\big (}a<c\Rightarrow (b=c\lor b<c){\big )}}$

لذا فإن الامتداد مع${\displaystyle <}$وهو أيضاً غير قابل للحسم.

• حساب بريسبرغر
• حساب روبنسون
• حذف المُكمِّم