الدليل الأصلي على نظرية اكتمال جودل

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

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

نحن نفترض المنطق الكلاسيكي (على عكس المنطق الحدسي على سبيل المثال).

لقد قمنا بإصلاح بعض البديهيات (أي نظام إثبات قائم على بناء الجملة وقابل للإدارة بواسطة الآلة) لحساب المسندات: البديهيات المنطقية وقواعد الاستدلال. أي من البديهيات المكافئة المعروفة العديدة سوف تفي بالغرض. افترض إثبات جودل الأصلي نظام إثبات هيلبرت-أكيرمان .

نحن نفترض دون إثبات جميع النتائج الأساسية المعروفة حول شكليتنا التي نحتاجها، مثل نظرية الشكل الطبيعي أو نظرية السلامة .

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

وفيما يلي، نذكر شكلين متكافئين للنظرية، ونبين تكافؤهما.

لاحقًا، نثبت النظرية. ويتم ذلك بالخطوات التالية:

1. اختزال النظرية إلى جمل (صيغ بدون متغيرات حرة) في صيغة prenex ، أي مع جميع المحددات ( ∀ و ∃ ) في البداية. علاوة على ذلك، نختزلها إلى صيغ يكون محددها الكمي الأول هو ∀ . هذا ممكن لأنه لكل جملة، هناك جملة مكافئة في صيغة prenex يكون محددها الكمي الأول هو ∀ .
2. اختزال النظرية إلى جمل من النموذج ∀ x ₁  ∀ x ₂  ... ∀ x _k  ∃ y ₁  ∃ y ₂  ... ∃ y _m φ ( x ₁  ...  x _k , y ₁  ...  y _m ) . وفي حين أننا لا نستطيع القيام بذلك بمجرد إعادة ترتيب المحددات الكمية، فإننا نظهر أنه لا يزال كافياً لإثبات النظرية للجمل من هذا النموذج.
3. وأخيرًا أثبتنا نظرية الجمل بهذا الشكل.
   • يتم ذلك من خلال ملاحظة أولاً أن جملة مثل B = ∀ x ₁ ∀ x ₂ ... ∀ x _k ∃ y ₁ ∃ y ₂ ... ∃ y _m φ( x ₁ ... x _k , y ₁ ... y _m ) إما أن تكون قابلة للدحض (نفيها صحيح دائمًا) أو قابلة للرضا، أي أن هناك نموذجًا ما تكون فيه صحيحة (قد تكون صحيحة دائمًا، أي تكرار)؛ هذا النموذج يعين ببساطة قيم الحقيقة للافتراضات الفرعية التي بُنيت منها B. والسبب في ذلك هو اكتمال المنطق القياسي ، مع عدم لعب الكميات الوجودية أي دور.
   • نقوم بتوسيع هذه النتيجة لتشمل جملًا أكثر تعقيدًا وطولًا، D _n ( n  = 1,2... )، مبنية على B ، بحيث يكون أي منها قابلًا للدحض وبالتالي يكون الأمر كذلك بالنسبة لـ φ ، أو لا يمكن دحضها جميعًا وبالتالي ينطبق كل منها على نموذج ما.
   • وأخيرًا، نستخدم النماذج التي يكون فيها D _n صحيحًا (في حالة عدم إمكانية دحض جميعها) من أجل بناء نموذج يكون فيه φ صحيحًا.

هذا هو الشكل الأكثر أساسية لنظرية الاكتمال. نعيد صياغتها على الفور في شكل أكثر ملاءمة لأغراضنا: عندما نقول "كل الهياكل"، من المهم تحديد أن الهياكل المعنية هي تفسيرات كلاسيكية (تارسكيانية) I، حيث I = <U,F> (U هي مجموعة غير فارغة (ربما لا نهائية) من الكائنات، بينما F هي مجموعة من الدوال من تعبيرات الرمزية المفسرة إلى U). [على النقيض من ذلك، تسمح ما يسمى "المنطق الحر" بمجموعات فارغة محتملة لـ U. لمزيد من المعلومات حول المنطق الحر، راجع عمل كارل لامبرت.]

" φ قابلة للدحض" تعني حسب التعريف "¬ φ قابلة للإثبات".

إذا كانت النظرية 1 صحيحة، ولم يكن φ قابلاً للإشباع في أي بنية، فإن ¬φ صحيحة في جميع البنيات وبالتالي يمكن إثباتها، وبالتالي فإن φ قابلة للدحض وتكون النظرية 2 صحيحة. من ناحية أخرى، إذا كانت النظرية 2 صحيحة وكانت φ صالحة في جميع البنيات، فإن ¬φ غير قابلة للإشباع في أي بنية وبالتالي يمكن دحضها؛ إذن فإن ¬¬φ قابلة للإثبات وبالتالي فإن φ كذلك، وبالتالي تكون النظرية 1 صحيحة.

نقترب من إثبات النظرية 2 من خلال تقييد فئة جميع الصيغ φ التي نحتاج إلى إثبات "أن φ إما قابلة للدحض أو قابلة للإشباع". في البداية، نحتاج إلى إثبات ذلك لجميع الصيغ φ الممكنة في لغتنا. ومع ذلك، افترض أنه لكل صيغة φ هناك بعض الصيغ ψ مأخوذة من فئة أكثر تقييدًا من الصيغ C ، بحيث "أن ψ إما قابلة للدحض أو قابلة للإشباع" → "أن φ إما قابلة للدحض أو قابلة للإشباع". بعد ذلك، بمجرد إثبات هذا الادعاء (المعبر عنه في الجملة السابقة)، سيكون كافيًا إثبات "أن φ إما قابلة للدحض أو قابلة للإشباع" فقط بالنسبة لـ φ التي تنتمي إلى الفئة C. إذا كان φ مكافئًا لـ ψ بشكل يمكن إثباته ( أي أن ( φ  ≡  ψ ) يمكن إثباته)، فإن هذه هي الحالة بالفعل حيث "ψ إما قابلة للدحض أو قابلة للإرضاء" → " φ إما قابلة للدحض أو قابلة للإرضاء" ( نظرية السلامة ضرورية لإظهار ذلك).

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

بعد ذلك، نفكر في صيغة عامة φ (لم تعد تستخدم رموز الدالة أو الثوابت) ونطبق نظرية الشكل السابق لإيجاد صيغة ψ في الشكل الطبيعي بحيث φ  ≡  ψ ( كون ψ في الشكل الطبيعي يعني أن جميع المحددات الكمية في ψ ، إن وجدت، توجد في بداية ψ ). ويترتب على ذلك الآن أننا نحتاج فقط إلى إثبات النظرية 2 للصيغ φ في الشكل الطبيعي.

بعد ذلك، نستبعد جميع المتغيرات الحرة من φ من خلال تحديد كميتها وجوديًا: إذا، على سبيل المثال، x ₁ ... x _n حرة في φ ، فإننا نشكل . إذا كان ψ قابلاً للإشباع في بنية M ، فمن المؤكد أن φ كذلك وإذا كان ψ قابلاً للدحض، فإن يمكن إثباته، ومن ثم فإن ¬ φ كذلك ، وبالتالي فإن φ قابل للدحض. نرى أنه يمكننا تقييد φ ليكون جملة ، أي صيغة بدون متغيرات حرة. ${\displaystyle \psi =\يوجد x_{1}\cdots \يوجد x_{n}\varphi }$${\displaystyle \neg \psi =\لكل x_{1}\cdots \لكل x_{n}\neg \varphi }$

أخيرًا، نود، لأسباب تتعلق بالراحة الفنية، أن تبدأ بادئة φ (أي سلسلة المحددات الكمية في بداية φ ، والتي تكون في شكل طبيعي) بمحدد كمية عالمي وتنتهي بمحدد كمية وجودي. لتحقيق ذلك بالنسبة لـ φ عام ( خاضع للقيود التي أثبتناها بالفعل)، نأخذ رمز علاقة مكان واحد F غير مستخدم في φ ، ومتغيرين جديدين y و z .. إذا كان φ = (P)Φ ، حيث تمثل (P) بادئة φ وΦ للمصفوفة (الجزء المتبقي الخالي من المحددات الكمية من φ ) فإننا نشكل . نظرًا لأنه يمكن إثباته بوضوح، فمن السهل أن نرى أن يمكن إثباته. ${\displaystyle \psi =\forall y(P)\exists z(\Phi \wedge [F(y)\vee \neg F(z)])}$${\displaystyle \forall y\exists z(F(y)\vee \neg F(z))}$${\displaystyle \varphi =\psi }$

الآن أصبحت صيغتنا العامة φ عبارة عن جملة في صيغة عادية، وتبدأ بادئتها بكمية عالمية وتنتهي بكمية وجودية. فلنطلق على فئة كل هذه الصيغ اسم R. نحن نواجه إثبات أن كل صيغة في R إما قابلة للدحض أو قابلة للإرضاء. بالنظر إلى صيغتنا φ، نقوم بتجميع سلاسل من الكميات من نفس النوع معًا في كتل:

${\displaystyle \varphi =(\لكل x_{1}\cdots \لكل x_{k_{1}})(\يوجد x_{k_{1}+1}\cdots \يوجد x_{k_{2}})\cdots (\لكل x_{k_{n-2}+1}\cdots \لكل x_{k_{n-1})(\يوجد x_{k_{n-1}+1}\cdots \يوجد x_{k_{n}})(\Phi )}$

نُعرِّف درجة لتكون عدد كتل الكميات الشاملة، المفصولة بكتل الكميات الوجودية كما هو موضح أعلاه، في البادئة . إن الفرضية التالية، التي اقتبسها جودل من إثبات سكوليم لنظرية لوينهايم-سكوليم ، تسمح لنا بتقليل تعقيد الصيغة العامة التي نحتاجها لإثبات النظرية بشكل حاد: ${\displaystyle \varphi }$${\displaystyle \varphi }$${\displaystyle \varphi }$

المبرهنة . دع k  ≥ 1. إذا كانت كل صيغة في R من الدرجة k قابلة للدحض أو قابلة للإرضاء، فإن كل صيغة في R من الدرجة k  + 1 قابلة للدحض أيضًا.

تعليق : خذ صيغة φ من الدرجة k  + 1 من الشكل ، حيث هو الباقي من (وبالتالي فهو من الدرجة k  − 1). تنص φ على أنه لكل x يوجد ay بحيث ... (شيء ما). كان من الجيد أن يكون لدينا مسند Q' بحيث يكون Q ′( x , y ) لكل x صحيحًا إذا وفقط إذا كان y هو المطلوب لجعل (شيء ما) صحيحًا. عندئذٍ كان بإمكاننا كتابة صيغة من الدرجة k ، والتي تعادل φ ، وهي . هذه الصيغة تعادل φ بالفعل لأنها تنص على أنه لكل x، إذا كان هناك ay يلبي Q'(x,y)، فإن (شيء ما) صحيح، وعلاوة على ذلك، نعلم أن هناك ay، لأنه لكل x'، يوجد y' يلبي Q'(x',y'). لذلك، يتبع φ من هذه الصيغة. ومن السهل أيضًا إظهار أنه إذا كانت الصيغة خاطئة، فإن φ خاطئة أيضًا. لسوء الحظ ، لا يوجد بشكل عام مسند من هذا القبيل Q'. ومع ذلك، يمكن فهم هذه الفكرة كأساس للدليل التالي على المبرهنة.${\displaystyle \varphi =(\لكل x)(\يوجد y)(\لكل u)(\يوجد v)(P)\psi }$${\displaystyle (P)\psi }$${\displaystyle \varphi }$${\displaystyle (\forall x')(\forall x)(\forall y)(\forall u)(\exists v)(\exists y')(P)Q'(x',y')\wedge (Q'(x,y)\rightarrow \psi )}$

الإثبات. ليكن φ صيغة من الدرجة k  + 1؛ إذن يمكننا كتابتها على النحو التالي:

${\displaystyle \varphi =(\forall x)(\exists y)(\forall u)(\exists v)(P)\psi }$

حيث (P) هو باقي البادئة (وبالتالي فهو من الدرجة k  – 1) وهو مصفوفة خالية من الكميات لـ . x و y و u و v تشير هنا إلى مجموعات من المتغيرات بدلاً من المتغيرات الفردية؛ حيث يمثل eg حقًا حيث توجد بعض المتغيرات المميزة. ${\displaystyle \varphi }$${\displaystyle \psi }$${\displaystyle \varphi }$ ${\displaystyle (\forall x)}$${\displaystyle \forall x_{1}\forall x_{2}\cdots \forall x_{n}}$${\displaystyle x_{1}\ldots x_{n}}$

لنفترض الآن أن x' و y' عبارة عن مجموعات من المتغيرات غير المستخدمة سابقًا بنفس طول x و y على التوالي، ولنفترض أن Q عبارة عن رمز علاقة غير مستخدم سابقًا يأخذ عددًا من الحجج يساوي مجموع أطوال x و y ؛ نعتبر الصيغة

${\displaystyle \Phi =(\forall x')(\exists y')Q(x',y')\wedge (\forall x)(\forall y)(Q(x,y)\rightarrow (\forall u)(\exists v)(P)\psi )}$

من الواضح أنه يمكن إثبات ذلك. ${\displaystyle \Phi \rightarrow \varphi }$

الآن، بما أن سلسلة المحددات الكمية لا تحتوي على متغيرات من x أو y ، فمن السهل إثبات التكافؤ التالي بمساعدة أي صيغة نستخدمها: ${\displaystyle (\forall u)(\exists v)(P)}$

${\displaystyle (Q(x,y)\rightarrow (\forall u)(\exists v)(P)\psi )\equiv (\forall u)(\exists v)(P)(Q(x,y)\rightarrow \psi )}$

وبما أن الصيغتين متكافئتين، فإذا استبدلنا الأولى بالثانية داخل Φ، نحصل على الصيغة Φ' بحيث Φ ≡Φ':

${\displaystyle \Phi '=(\forall x')(\exists y')Q(x',y')\wedge (\forall x)(\forall y)(\forall u)(\exists v)(P)(Q(x,y)\rightarrow \psi )}$

الآن، Φ' لها الشكل ، حيث (S) و (S') عبارة عن سلاسل كمية، وρ وρ' خاليان من الكم، وعلاوة على ذلك ، لا يوجد متغير من (S) في ρ' ولا يوجد متغير من (S') في ρ. في ظل هذه الظروف، فإن كل صيغة من الشكل ، حيث (T) عبارة عن سلسلة من الكميات تحتوي على جميع الكميات في (S) و(S') متداخلة فيما بينها بأي شكل، ولكن مع الحفاظ على الترتيب النسبي داخل (S) و(S')، ستكون معادلة للصيغة الأصلية Φ'(هذه نتيجة أساسية أخرى في حساب المسند من الدرجة الأولى نعتمد عليها). بمعنى آخر، نشكل Ψ على النحو التالي: ${\displaystyle (S)\rho \wedge (S')\rho '}$${\displaystyle (T)(\rho \wedge \rho ')}$

${\displaystyle \Psi =(\forall x')(\forall x)(\forall y)(\forall u)(\exists y')(\exists v)(P)Q(x',y')\wedge (Q(x,y)\rightarrow \psi )}$

ولدينا . ${\displaystyle \Phi '\equiv \Psi }$

الآن هي صيغة من الدرجة k وبالتالي بالافتراض إما قابلة للدحض أو قابلة للإرضاء. إذا كانت قابلة للإرضاء في البنية M ، إذن، بالنظر إلى ، نرى أن قابلة للإرضاء أيضًا. إذا كانت قابلة للدحض، فإن ، تكون كذلك أيضًا ، والتي تعادلها؛ وبالتالي قابلة للإثبات. الآن يمكننا استبدال جميع حالات Q داخل الصيغة القابلة للإثبات ببعض الصيغة الأخرى المعتمدة على نفس المتغيرات، وسنظل نحصل على صيغة قابلة للإثبات. ( هذه نتيجة أساسية أخرى لحساب المسند من الدرجة الأولى. واعتمادًا على الصيغة الخاصة المعتمدة لحساب التفاضل والتكامل، يمكن اعتبارها تطبيقًا بسيطًا لقاعدة "الاستبدال الوظيفي" للاستدلال، كما في ورقة جودل، أو يمكن إثباتها من خلال النظر في الدليل الرسمي لـ ، واستبدال جميع حالات Q فيه ببعض الصيغة الأخرى بنفس المتغيرات الحرة، وملاحظة أن جميع البديهيات المنطقية في الدليل الرسمي تظل بديهيات منطقية بعد الاستبدال، ولا تزال جميع قواعد الاستدلال تنطبق بنفس الطريقة. ) ${\displaystyle \Psi }$${\displaystyle \Psi }$${\displaystyle \Psi \equiv \Phi '\equiv \Phi \wedge \Phi \rightarrow \varphi }$${\displaystyle \varphi }$${\displaystyle \Psi }$${\displaystyle \Phi }$${\displaystyle \neg \Phi }$${\displaystyle \neg \Phi }$${\displaystyle \neg \Phi }$

في هذه الحالة الخاصة، نستبدل Q(x',y') في بالصيغة . هنا (x,y | x',y') تعني أنه بدلاً من ψ نكتب صيغة مختلفة، حيث يتم استبدال x وy بـ x' وy'. يتم استبدال Q(x,y) ببساطة بـ . ${\displaystyle \neg \Phi }$${\displaystyle (\forall u)(\exists v)(P)\psi (x,y\mid x',y')}$${\displaystyle (\forall u)(\exists v)(P)\psi }$

${\displaystyle \neg \Phi }$ثم يصبح

${\displaystyle \neg ((\forall x')(\exists y')(\forall u)(\exists v)(P)\psi (x,y\mid x',y')\wedge (\forall x)(\forall y)((\forall u)(\exists v)(P)\psi \rightarrow (\forall u)(\exists v)(P)\psi ))}$

وهذه الصيغة قابلة للإثبات؛ بما أن الجزء الذي يقع تحت النفي وبعد الإشارة يمكن إثباته بوضوح، والجزء الذي يقع تحت النفي وقبل الإشارة هو بوضوح φ، فقط مع استبدال x و y بـ x' و y' ، نرى أن ذلك قابل للإثبات، وφ قابل للدحض. لقد أثبتنا أن φ إما قابل للإرضاء أو قابل للدحض، وهذا يختتم إثبات المبرهنة . ${\displaystyle \wedge }$${\displaystyle \wedge }$${\displaystyle \neg \varphi }$

لاحظ أنه لم يكن بوسعنا استخدام Q(x',y') بدلاً من ذلك منذ البداية، لأن هذه الحالة لم تكن لتسمح لنا بتكوين صيغة جيدة . ولهذا السبب لا يمكننا استخدام الحجة التي تظهر في التعليق الذي يسبق الإثبات بشكل ساذج. ${\displaystyle (\forall u)(\exists v)(P)\psi (x,y\mid x',y')}$${\displaystyle \Psi }$

كما هو موضح في المبرهنة أعلاه، نحتاج فقط إلى إثبات نظريتنا للصيغ φ في R من الدرجة 1. لا يمكن أن تكون φ من الدرجة 0، لأن الصيغ في R ليس لها متغيرات حرة ولا تستخدم رموز ثابتة. لذا فإن الصيغة φ لها الشكل العام:

${\displaystyle (\forall x_{1}\ldots x_{k})(\exists y_{1}\ldots y_{m})\varphi (x_{1}\ldots x_{k},y_{1}\ldots y_{m}).}$

الآن نُعرّف ترتيبًا لمجموعات الأعداد الطبيعية المكونة من k على النحو التالي: يجب أن يكون صحيحًا إذا كان أي من أو أو و يسبقه في الترتيب المعجمي . [ يشير هنا إلى مجموع حدود المجموعة.] يتم الإشارة إلى المجموعة n بهذا الترتيب بواسطة . ${\displaystyle (x_{1}\ldots x_{k})<(y_{1}\ldots y_{k})}$${\displaystyle \Sigma _{k}(x_{1}\ldots x_{k})<\Sigma _{k}(y_{1}\ldots y_{k})}$${\displaystyle \Sigma _{k}(x_{1}\ldots x_{k})=\Sigma _{k}(y_{1}\ldots y_{k})}$${\displaystyle (x_{1}\ldots x_{k})}$${\displaystyle (y_{1}...y_{k})}$${\displaystyle \Sigma _{k}(x_{1}\ldots x_{k})}$${\displaystyle (a_{1}^{n}\ldots a_{k}^{n})}$

اضبط الصيغة على النحو التالي . ثم ضعها على النحو التالي ${\displaystyle B_{n}}$${\displaystyle \varphi (z_{a_{1}^{n}}\ldots z_{a_{k}^{n}},z_{(n-1)m+2},z_{(n-1)m+3}\ldots z_{nm+1})}$${\displaystyle D_{n}}$

${\displaystyle (\exists z_{1}\ldots z_{nm+1})(B_{1}\wedge B_{2}\wedge \cdots \wedge B_{n}).}$

المقدمة : لكل n ، . ${\displaystyle \varphi \rightarrow D_{n}}$

الإثبات : بالاستقراء على n ؛ لدينا ، حيث ينطبق الاستدلال الأخير عن طريق الاستبدال بالمتغير، لأن ترتيب الثنائيات يكون بحيث . ولكن الصيغة الأخيرة تعادل φ. ${\displaystyle D_{n}\Leftarrow D_{n-1}\wedge (\forall z_{1}\ldots z_{(n-1)m+1})(\exists z_{(n-1)m+2}\ldots z_{nm+1})B_{n}\Leftarrow D_{n-1}\wedge (\forall z_{a_{1}^{n}}\ldots z_{a_{k}^{n}})(\exists y_{1}\ldots y_{m})\varphi (z_{a_{1}^{n}}\ldots z_{a_{k}^{n}},y_{1}\ldots y_{m})}$${\displaystyle (\forall k)(a_{1}^{n}\ldots a_{k}^{n})<(n-1)m+2}$${\displaystyle D_{n-1}\wedge }$

بالنسبة للحالة الأساسية، من الواضح أنها نتيجة تكميلية لـ φ أيضًا. لذا فإن الفرضية مثبتة. ${\displaystyle D_{1}\equiv (\exists z_{1}\ldots z_{m+1})\varphi (z_{a_{1}^{1}}\ldots z_{a_{k}^{1}},z_{2},z_{3}\ldots z_{m+1})\equiv (\exists z_{1}\ldots z_{m+1})\varphi (z_{1}\ldots z_{1},z_{2},z_{3}\ldots z_{m+1})}$

الآن إذا كان قابلاً للدحض لبعض n ، فيترتب على ذلك أن φ قابل للدحض. من ناحية أخرى، افترض أن غير قابل للدحض لأي n . إذن لكل n هناك طريقة ما لتعيين قيم الحقيقة للافتراضات الفرعية المميزة (مرتبة حسب ظهورها الأول في ؛ تعني "المتميزة" هنا إما مسندات مميزة، أو متغيرات حدود مميزة) في ، بحيث تكون صحيحة عندما يتم تقييم كل اقتراح بهذه الطريقة. ويترتب على هذا اكتمال المنطق الأساسي للافتراضات . ${\displaystyle D_{n}}$${\displaystyle D_{n}}$${\displaystyle E_{h}}$${\displaystyle D_{n}}$${\displaystyle B_{k}}$${\displaystyle D_{n}}$

سنُظهر الآن أنه يوجد مثل هذا التعيين لقيم الحقيقة إلى ، بحيث تكون جميعها صحيحة: تظهر بنفس الترتيب في كل ؛ سنحدد استقرائيًا تعيينًا عامًا لها من خلال نوع من "تصويت الأغلبية": نظرًا لوجود عدد لا نهائي من التعيينات (واحد لكل ) تؤثر على ، إما أن يكون عدد لا نهائي منها صحيحًا، أو أن يكون عدد لا نهائي منها يجعلها خاطئة وأن يكون عدد محدود منها فقط صحيحًا. في الحالة الأولى، نختار أن تكون صحيحة بشكل عام؛ وفي الحالة الثانية نعتبرها خاطئة بشكل عام. ثم من بين العدد اللانهائي n الذي تم تعيين نفس قيمة الحقيقة له إلى كما في التعيين العام، نختار تعيينًا عامًا إلى بنفس الطريقة. ${\displaystyle E_{h}}$${\displaystyle D_{n}}$${\displaystyle E_{h}}$${\displaystyle D_{n}}$${\displaystyle D_{n}}$${\displaystyle E_{1}}$${\displaystyle E_{1}}$${\displaystyle E_{1}}$${\displaystyle E_{1}}$${\displaystyle E_{h-1}}$${\displaystyle E_{h}}$

يجب أن يؤدي هذا التعيين العام إلى أن تكون كل واحدة من و صحيحة، لأنه إذا كانت واحدة من خاطئة بموجب التعيين العام، فستكون خاطئة أيضًا لكل n > k . لكن هذا يتناقض مع حقيقة أنه بالنسبة للمجموعة المحدودة من التعيينات العامة التي تظهر في ، يوجد عدد لا نهائي من n حيث يتطابق التعيين الذي يجعل صحيحًا مع التعيين العام. ${\displaystyle B_{k}}$${\displaystyle D_{k}}$${\displaystyle B_{k}}$${\displaystyle D_{n}}$${\displaystyle E_{h}}$${\displaystyle D_{k}}$${\displaystyle D_{n}}$

من هذا التعيين العام، الذي يجعل كل شيء صحيحًا، نبني تفسيرًا لمسندات اللغة التي تجعل φ صحيحًا. سيكون عالم النموذج هو الأعداد الطبيعية . يجب أن يكون كل مسند i-ary صحيحًا للأعداد الطبيعية على وجه التحديد عندما يكون الاقتراح إما صحيحًا في التعيين العام، أو غير معين به (لأنه لا يظهر أبدًا في أي من ). ${\displaystyle D_{k}}$${\displaystyle \Psi }$${\displaystyle (u_{1}\ldots u_{i})}$${\displaystyle \Psi (z_{u_{1}}\ldots z_{u_{i}})}$${\displaystyle D_{k}}$

في هذا النموذج، تكون كل الصيغ صحيحة من حيث البناء. ولكن هذا يعني أن φ نفسها صحيحة في النموذج، نظرًا لأن النطاق يشمل جميع k-tuples الممكنة للأعداد الطبيعية. لذا فإن φ قابلة للرضا، وقد انتهينا. ${\displaystyle (\exists y_{1}\ldots y_{m})\varphi (a_{1}^{n}\ldots a_{k}^{n},y_{1}...y_{m})}$${\displaystyle a^{n}}$

يمكننا كتابة كل B _i على النحو التالي Φ( x ₁ ... x _k , y ₁ ... y _m ) لبعض x s، والتي يمكننا أن نسميها "الحجج الأولى" و y s والتي يمكننا أن نسميها "الحجج الأخيرة".

خذ B ₁ على سبيل المثال. "حججها الأخيرة" هي z ₂ و z ₃ ... z _{m +1} ، ولكل تركيبة ممكنة من k من هذه المتغيرات يوجد بعض j بحيث تظهر كـ "حجج أولى" في B _j . وبالتالي، بالنسبة لـ n ₁ كبيرة بما يكفي ، فإن D _{n 1} لها الخاصية التي تجعل "الحجج الأخيرة" لـ B ₁ تظهر، في كل التركيبات الممكنة لـ k منها، كـ "حجج أولى" في B _j s الأخرى ضمن D _n . لكل B _i يوجد D _{n i} بالخاصية المقابلة.

لذلك في نموذج يلبي جميع D _n s، توجد كائنات تتوافق مع z ₁ و z ₂ ... وتظهر كل مجموعة من k من هذه الكائنات على أنها "حجج أولى" في بعض B _j ، مما يعني أنه لكل k من هذه الكائنات z _{p 1} ... z _{p k} يوجد z _{q 1} ... z _{q m} ، مما يجعل Φ( z _{p 1} ... z _{p k} و z _{q 1} ... z _{q m} ) مُرضية. من خلال أخذ نموذج فرعي بهذه الكائنات z ₁ و z ₂ ... فقط، يكون لدينا نموذج يُرضي  φ .

قام جودل بتقليص صيغة تحتوي على حالات من مسند المساواة إلى حالات لا تحتوي عليها في لغة ممتدة. تتضمن طريقته استبدال صيغة φ تحتوي على بعض حالات المساواة بالصيغة

${\displaystyle (\forall x)Eq(x,x)\wedge (\forall x,y,z)[Eq(x,y)\rightarrow (Eq(x,z)\rightarrow Eq(y,z))]}$ ${\displaystyle \wedge (\forall x,y,z)[Eq(x,y)\rightarrow (Eq(z,x)\rightarrow Eq(z,y))]}$

${\displaystyle \wedge }$

${\displaystyle (\forall x_{1}\ldots x_{k},y_{1}\ldots x_{k})[(Eq(x_{1},y_{1})\wedge \cdots \wedge Eq(x_{k},y_{k}))\rightarrow (A(x_{1}\ldots x_{k})\equiv A(y_{1}\ldots y_{k}))]}$

${\displaystyle \wedge \cdots \wedge }$

${\displaystyle (\forall x_{1}\ldots x_{m},y_{1}\ldots x_{m})[(Eq(x_{1},y_{1})\wedge \cdots \wedge Eq(x_{m},y_{m}))\rightarrow (Z(x_{1}\ldots x_{m})\equiv Z(y_{1}\ldots y_{m}))]}$

${\displaystyle \wedge }$

${\displaystyle \varphi '.}$

هنا نشير إلى المسندات التي تظهر في φ (مع صيغها الخاصة)، وφ' هي الصيغة φ مع استبدال جميع حالات المساواة بالمسند الجديد معادلة . إذا كانت هذه الصيغة الجديدة قابلة للدحض، فإن φ الأصلية كانت كذلك أيضًا؛ وينطبق الشيء نفسه على قابلية الإشباع، حيث يمكننا أخذ حاصل إشباع نموذج الصيغة الجديدة من خلال علاقة التكافؤ التي تمثل معادلة . هذا الحاصل محدد جيدًا فيما يتعلق بالمسندات الأخرى، وبالتالي سوف يرضي الصيغة الأصلية φ. ${\displaystyle A\ldots Z}$${\displaystyle k\ldots m}$

كما نظر جودل في الحالة التي توجد فيها مجموعة لا نهائية قابلة للعد من الصيغ. وباستخدام نفس الاختزالات المذكورة أعلاه، كان قادرًا على النظر فقط في الحالات التي تكون فيها كل صيغة من الدرجة 1 ولا تحتوي على استخدامات المساواة. بالنسبة لمجموعة قابلة للعد من الصيغ من الدرجة 1، يمكننا تعريفها على أنها أعلاه؛ ثم تعريفها على أنها إغلاق . ثم تم تنفيذ بقية الإثبات كما في السابق. ${\displaystyle \varphi ^{i}}$${\displaystyle B_{k}^{i}}$${\displaystyle D_{k}}$${\displaystyle B_{1}^{1}\ldots B_{k}^{1},\ldots ,B_{1}^{k}\ldots B_{k}^{k}}$

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

• جودل، ك (1929). Über die Vollständigkeit des Logikkalküls (أطروحة دكتوراه). جامعة فيينا.الدليل الأول على نظرية الاكتمال.
• جودل ، ك (1930). "Die Vollständigkeit der Axiome des logischen Funktionenkalküls". Monatshefte für Mathematik (باللغة الألمانية). 37 (1): 349-360. دوى :10.1007/BF01696781. جي اف ام  56.0046.04. S2CID  123343522.المادة نفسها الموجودة في الرسالة، إلا أن الأدلة كانت مختصرة، وشروحات أكثر إيجازًا، وحذف المقدمة الطويلة.

• موسوعة ستانفورد للفلسفة : "كورت جودل" - بقلم جولييت كينيدي .
• سيرة MacTutor: كورت جودل.