اللمة القطرية

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

في المنطق الرياضي ، تثبت اللمة القطرية (المعروفة أيضًا باسم لمة القطرنة ، أو لمة الإشارة الذاتية ، أو نظرية النقطة الثابتة ) وجود جمل مرجعية ذاتية في بعض النظريات الرسمية.

استُخدمت حالة خاصة من مبرهنة القطر من قِبل كورت غودل عام 1931 لبناء برهانه على نظريات عدم الاكتمال، وكذلك من قِبل تارسكي عام 1933 لإثبات مبرهنته على عدم التعريف . وفي عام 1934، كان كارناب أول من نشر مبرهنة القطر بمستوى معين من العمومية. [ 1 ] سُميت مبرهنة القطر نسبةً إلى حجة كانتور القطرية في نظرية المجموعات ونظرية الأعداد .

تنطبق مبرهنة القطر على أي نظرية قوية بما يكفي قادرة على تمثيل الدالة القطرية. وتشمل هذه النظريات حساب بيانو من الدرجة الأولىPأ{\displaystyle {\mathsf {PA}}}، حساب روبنسون الأضعفسؤال{\displaystyle {\mathsf {Q}}}بالإضافة إلى أي نظرية تحتوي علىسؤال{\displaystyle {\mathsf {Q}}}(أي التي تفسرها). [ 2 ] يفترض بيان شائع للّمة (كما هو موضح أدناه) افتراضًا أقوى مفاده أن النظرية يمكنها تمثيل جميع الدوال القابلة للحساب (الكلي) ، ولكن جميع النظريات المذكورة لديها هذه القدرة أيضًا.

خلفية

ترقيم غودل

تتطلب اللمة القطرية أيضًا ترقيم غودلα{\displaystyle \alpha }نكتبα(φ){\displaystyle \alpha (\varphi )}بالنسبة للرمز المخصص لـφ{\displaystyle \varphi }حسب الترقيم. لـن¯{\displaystyle {\overline {n}}}، الرقم القياسي لـن{\displaystyle n}(أي0¯=دو0{\displaystyle {\overline {0}}=_{df}{\mathsf {0}}}ون+1¯=دوS(ن¯){\displaystyle {\overline {n+1}}=_{df}{\mathsf {S}}({\overline {n}})})، يترك ⌜φ⌝{\displaystyle \ulcorner \varphi \urcorner }ليكن الرقم القياسي لرمزφ{\displaystyle \varphi }(أي⌜φ⌝{\displaystyle \ulcorner \varphi \urcorner }يكونα(φ)¯{\displaystyle {\overline {\alpha (\varphi )}}}نفترض استخدام ترقيم غودل القياسي

نظرية التمثيل

يتركشمال{\displaystyle \mathbb {N} }لتكن مجموعة الأعداد الطبيعية . نظرية من الدرجة الأولىتي{\displaystyle T}بلغة الحساب التي تحتويسؤال{\displaystyle {\mathsf {Q}}}يمثل​ك{\displaystyle k}دالة قابلة للحساب من الرتبة -ary (الكلية)و:شمالك→شمال{\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }إذا كانت هناك صيغةφو(x1،...،xك،y){\displaystyle \varphi _{f}(x_{1},\dots ,x_{k},y)}بلغةتي{\displaystyle T}بحيث يكون ذلك لجميعم1،...،مك∈شمال{\displaystyle m_{1},\dots ,m_{k}\in \mathbb {N} }، لوو(م1،...،مك)=ن{\displaystyle f(m_{1},\dots ,m_{k})=n}ثمتي⊢∀y(φو(م1¯،...،مك¯،y)↔y=ن¯){\displaystyle T\vdash \forall y(\varphi _{f}({\overline {m_{1}}},\dots ,{\overline {m_{k}}},y)\leftrightarrow y={\overline {n}})}.

إن نظرية التمثيل صحيحة، أي أن كل دالة قابلة للحساب يمكن تمثيلها فيتي{\displaystyle T}[ 3 ]​

اللمة القطرية وبرهانها

اللمة القطرية : ليكنتي{\displaystyle T}أن تكون نظرية من الدرجة الأولى تحتوي علىسؤال{\displaystyle {\mathsf {Q}}}( حساب روبنسون ) وليكنψ(x){\displaystyle \psi (x)}أي صيغة في لغةتي{\displaystyle T}فقطx{\displaystyle x}كمتغير حر. ثم هناك جملةφ{\displaystyle \varphi }بلغةتي{\displaystyle T}بحيثتي⊢φ↔ψ(⌜φ⌝){\displaystyle T\vdash \varphi \leftrightarrow \psi (\ulcorner \varphi \urcorner )}.

بشكل بديهي،φ{\displaystyle \varphi }هي جملة ذاتية الإشارة تقول عن نفسها إنها تمتلك الخاصيةψ{\displaystyle \psi }"

البرهان : ليكندأناأزتي:شمال→شمال{\displaystyle diag_{T}:\mathbb {N} \to \mathbb {N} }لتكن الدالة القابلة للحساب التي تربط رمز كل صيغةφ(x){\displaystyle \varphi (x)}مع متغير حر واحد فقطx{\displaystyle x}بلغةتي{\displaystyle T}باستخدام رمز الصيغة المغلقةφ(⌜φ⌝){\displaystyle \varphi (\ulcorner \varphi \urcorner )}(أي استبدال⌜φ⌝{\displaystyle \ulcorner \varphi \urcorner }داخلφ{\displaystyle \varphi }لx{\displaystyle x}) و0{\displaystyle 0}ولحجج أخرى. (حقيقة أندأناأزتي{\displaystyle diag_{T}}يعتمد حسابها على اختيار ترقيم غودل، وهو الترقيم القياسي هنا .

بحسب نظرية التمثيل،تي{\displaystyle T}يمثل كل دالة قابلة للحساب. وبالتالي، توجد صيغةدلتا(x،y){\displaystyle \delta (x,y)}يمثلدأناأزتي{\displaystyle diag_{T}}وخاصة لكلφ(x){\displaystyle \varphi (x)}،تي⊢دلتا(⌜φ⌝،y)↔y=⌜φ(⌜φ⌝)⌝{\displaystyle T\vdash \delta (\ulcorner \varphi \urcorner ,y)\leftrightarrow y=\ulcorner \varphi (\ulcorner \varphi \urcorner )\urcorner }.

يتركψ(x){\displaystyle \psi (x)}كن صيغة اعتباطية تحتوي فقط علىx{\displaystyle x}كمتغير حر. سنعرّف الآنχ(x){\displaystyle \chi (x)}مثل∃y(دلتا(x،y)∧ψ(y)){\displaystyle \موجود y(\delta (x,y)\land \psi (y))}ودعφ{\displaystyle \varphi }يكونχ(⌜χ⌝){\displaystyle \chi (\ulcorner \chi \urcorner )}ثم يمكن إثبات المكافئات التالية فيتي{\displaystyle T}:

φ↔χ(⌜χ⌝)↔∃y(دلتا(⌜χ⌝،y)∧ψ(y))↔∃y(y=⌜χ(⌜χ⌝)⌝∧ψ(y))↔∃y(y=⌜φ⌝∧ψ(y))↔ψ(⌜φ⌝){\displaystyle \varphi \leftrightarrow \chi (\ulcorner \chi \urcorner )\leftrightarrow \exists y(\delta (\ulcorner \chi \urcorner ,y)\land \psi (y))\leftrightarrow \exists y(y=\ulcorner \chi (\ulcorner \chi \urcorner )\urcorner \land \psi (y))\leftrightarrow \exists y(y=\ulcorner \chi (\ulcorner \chi \urcorner )\urcorner \land \psi (y))\leftrightarrow \exists y(y=\ulcorner \varphi \urcorner \land \psi (y))\leftrightarrow \psi (\ulcorner \varphi \urcorner )}.

بعض التعميمات

توجد تعميمات متعددة لفرضية القطر. نعرض بعضًا منها فقط؛ وعلى وجه الخصوص، فإن دمج التعميمات الثلاثة الأولى أدناه يُنتج تعميمات جديدة. [ 4 ] ليكنتي{\displaystyle T}أن تكون نظرية من الدرجة الأولى تحتوي علىسؤال{\displaystyle {\mathsf {Q}}}( حساب روبنسون ).

اللمة القطرية ذات المعاملات

يتركψ(x،y1،...،yن){\displaystyle \psi (x,y_{1},\dots ,y_{n})}أي صيغة ذات متغيرات حرةx،y1،...،yن{\displaystyle x,y_{1},\dots ,y_{n}}.

ثم هناك صيغةφ(y1،...yن){\displaystyle \varphi (y_{1},\dots y_{n})}مع متغيرات حرةy1،...،yن{\displaystyle y_{1},\dots ,y_{n}}بحيثتي⊢φ(y1،...،yن)↔ψ(⌜φ(y1،...،yن)⌝،y1،...،yن){\displaystyle T\vdash \varphi (y_{1},\dots ,y_{n})\leftrightarrow \psi (\ulcorner \varphi (y_{1},\dots ,y_{n})\urcorner ,y_{1},\dots ,y_{n})}.

معضلة القطر المنتظم

يتركψ(x،y1،...،yن){\displaystyle \psi (x,y_{1},\dots ,y_{n})}أي صيغة ذات متغيرات حرةx،y1،...،yن{\displaystyle x,y_{1},\dots ,y_{n}}.

ثم هناك صيغةφ(y1،...yن){\displaystyle \varphi (y_{1},\dots y_{n})}مع متغيرات حرةy1،...،yن{\displaystyle y_{1},\dots ,y_{n}}بحيث يكون ذلك لجميعم1،...،من∈شمال{\displaystyle m_{1},\dots ,m_{n}\in \mathbb {N} }،تي⊢φ(م1¯،...،من¯)↔ψ(⌜φ(م1¯،...،من¯)⌝،م1¯،...،من¯){\displaystyle T\vdash \varphi ({\overline {m_{1}}},\dots ,{\overline {m_{n}}})\leftrightarrow \psi (\ulcorner \varphi ({\overline {m_{1}}},\dots ,{\overline {m_{n}}})\urcorner ,{\overline {m_{1}}},\dots ,{\overline {m_{n}}})}.

اللمة القطرية المتزامنة

يتركψ1(x1،x2){\displaystyle \psi _{1}(x_{1},x_{2})}وψ2(x1،x2){\displaystyle \psi _{2}(x_{1},x_{2})}صيغ ذات متغيرات حرةx1{\displaystyle x_{1}}وx2{\displaystyle x_{2}}.

ثم هناك جملةφ1{\displaystyle \varphi _{1}}وφ2{\displaystyle \varphi _{2}}بحيثتي⊢φ1↔ψ1(⌜φ1⌝،⌜φ2⌝){\displaystyle T\vdash \varphi _{1}\leftrightarrow \psi _{1}(\ulcorner \varphi _{1}\urcorner ,\ulcorner \varphi _{2}\urcorner )}وتي⊢φ2↔ψ2(⌜φ1⌝،⌜φ2⌝){\displaystyle T\vdash \varphi _{2}\leftrightarrow \psi _{2}(\ulcorner \varphi _{1}\urcorner ,\ulcorner \varphi _{2}\urcorner )}.

القضية معن{\displaystyle n}العديد من الصيغ متشابهة.

اللمة القطرية القوية

يتركψ(x){\displaystyle \psi (x)}أي صيغة في لغةتي{\displaystyle T}فقطx{\displaystyle x}كمتغير حر. ثم هناك مصطلحت{\displaystyle t}بلغةتي{\displaystyle T}بحيثتي⊢ت=⌜ψ(ت)⌝{\displaystyle T\vdash t=\ulcorner \psi (t)\urcorner }.

وبشكل بديهي، فإنّ اللمة القطرية تتبع من اللمة القطرية القوية (خذφ(x){\displaystyle \varphi (x)}يكونψ(ت){\displaystyle \psi (t)}لاحظ مع ذلك أن اللمة القطرية القوية تعتمد على لغةتي{\displaystyle T}وخاصة فيما يتعلق بوجود مثل هذا المصطلحت{\displaystyle t}عادةً، تفشل مبرهنة القطر القوي في النظريات المكتوبة باللغة الأساسية للحساب (مثلسؤال{\displaystyle {\mathsf {Q}}}أوPأ{\displaystyle {\mathsf {PA}}})، لكنها تنطبق على الحساب التكراري البدائيPRأ{\displaystyle {\mathsf {PRA}}}والتي تحتوي على رمز دالة لكل دالة تكرارية أولية. [ 5 ]

تاريخ

تُسمى هذه اللمة "قطرية" لأنها تُشبه إلى حد ما حجة كانتور القطرية . [ 6 ] لم يرد مصطلحا "اللمة القطرية" أو "النقطة الثابتة" في مقالة كورت غودل عام 1931 أو في مقالة ألفريد تارسكي عام 1936 .

في عام 1934، كان رودولف كارناب أول من نشر مبرهنة القطر في مستوى معين من العمومية، والتي تنص على أنه لأي صيغةψ(x){\displaystyle \psi (x)}معx{\displaystyle x}إذا اعتبرنا متغيرًا حرًا (في لغة معبرة بما فيه الكفاية)، فستوجد جملةφ{\displaystyle \varphi }بحيثφ↔ψ(⌜φ⌝){\displaystyle \varphi \leftrightarrow \psi (\ulcorner \varphi \urcorner )}صحيح (في نموذج معياري ما). [ 7 ] صِيغَ عمل كارناب من حيث الصدق لا من حيث إمكانية الإثبات (أي دلاليًا لا نحويًا). [ 8 ] علاوة على ذلك، لم يكن مفهوم الدوال القابلة للحساب قد طُوِّر بعد في عام 1934.

ترتبط مبرهنة القطر ارتباطًا وثيقًا بمبرهنة كلين للاستدعاء الذاتي في نظرية الحوسبة ، وتتشابه براهينهما. [ 9 ] في عام 1952، تساءل ليون هينكين عما إذا كانت الجمل التي تُبين إمكانية إثباتها قابلة للإثبات. وقد أدى سؤاله إلى تحليلات أكثر عمومية لمبرهنة القطر، لا سيما فيما يتعلق بمبرهنة لوب ومنطق إمكانية الإثبات . [ 10 ]

انظر أيضاً

ملحوظات

  1. ↑ انظر سمورينسكي 2022، القسم 3.
  2. ↑ انظر هاجيك وبودلاك 2016، الفصل. ثالثا.
  3. ↑ انظر هينمان 2005، الفصل 4.6 لمزيد من التفاصيل وبرهان هذه النظرية.
  4. ^ انظر سمورينسكي 2022، ثانية. 3 أو هاجيك وبودلاك 2016، III.2.a
  5. ↑ انظر على سبيل المثال جيروسلو 1973، القسم 1. لمزيد من التفاصيل حول اللمة القطرية القوية وأحد برهانها.
  6. ↑ انظر، على سبيل المثال، غايفمان (2006).
  7. ↑ انظر كارناب، 1934، وغودل، 1986، ص 363، حاشية 23.
  8. ↑ انظر سمورينسكي 2022، القسم 3.
  9. ↑ انظر Gaifman، 2006 أو Smoryński 2022، القسم 3.
  10. ↑ انظر سمورينسكي 2022، القسم 3.

مراجع

  • روبرت ج. جيروسلو، 1973. "التكرارات في شروط اشتقاق هيلبرت-بيرنايز لنظرية عدم الاكتمال الثانية لغودل". مجلة المنطق الرمزي ، 38.3: 359-367.
  • بيتر هاجيك وبافل بودلاك، 2016 (الطبعة الأولى 1998). الرياضيات الوصفية للحساب من الدرجة الأولى. سبرينغر فيرلاغ.