قضایای ناتمامیت گودل

قضیهٔ اول ناتمامیت گودل، شاید مشهورترین نتیجه در منطق ریاضیات باشد، که بیان می‌کند:

فرض کنید K یک نظریه در زبان حساب باشد که به نحوی بازگشتی قابل اصل بندی باشد و قضایای اصلی حساب در آن اثبات شوند. در این صورت اگر K سازگار باشد، جمله‌ای مانند G وجود خواهد داشت به قسمی که:

الف) اگر K نظریه‌ای سازگار باشد G در K اثبات پذیر نیست.

ب) اگر K نظریه‌ای ω ـ سازگار باشد نقیض G در K اثبات پذیر نیست.

بنابراین اگرK نظریه‌ای ω ـ سازگار باشد G یک جمله تصمیم ناپذیر از K است. (Mendelson. p. 206)

در این‌جا، «نظریه» به معنای تعدادی قواعد استنتاج، تعدادی علائم و مجموعه‌ای نامتناهی از گزاره‌ها است، که تعدادی متناهی از این گزاره‌ها بدون اثبات پذیرفته می‌شوند (که اصول موضوع خوانده می‌شوند)، و برخی دیگر از گزاره‌ها از اصول موضوع به دست می‌آیند؛ به این گزاره‌ها که با کمک قواعد استنتاج از اصول موضوع به دست می‌آیند قضیه می‌گوییم. «اثبات پذیر بودن در نظریه» یعنی «اشتقاق‌پذیر بودن از اصول موضوع نظریه به کمک قواعد استنتاج نظریه». یک نظریه «سازگار» است، در صورتی که هیچ‌گاه یک تناقض را اثبات نکند. بنا بر قضیه ناتمامیت اول گودل، هیچ نظریه اصل موضوعی که حداقل قضایای اساسی حساب را بتواند اثبات کند وجود ندارد که همه قضایا را اثبات یا رد کند. به عبارتی در هر نظام اصل موضوعی ریاضی جملاتی تصمیم ناپذیر وجود دارند. طبق منطق کلاسیک و منطق ارسطویی هر گزاره‌ای یا صادق است یا کاذب. قضیه ناتمامیت اول می‌گوید که نظام‌های اصل موضوعی که قابلیت نشان دادن توابع بازگشتی را داشته باشند نمی‌توانند چنین تصمیمی دربارهٔ گزاره‌های حساب بگیرند. یعنی جملاتی در این نظام‌ها وجود دارند که نه اثبات‌پذیرند و نه انکارپذیر. می‌توان نشان داد که اگر G را به K بیفزاییم و مجموعهٔ جدیدی تولید کنیم، باز هم می‌توانیم یک گزارهٔ جدید گودل برای مجموعهٔ فعلی ارائه کنیم که در نظریه جدید نه اثبات پذیر باشد و نه انکارپذیری و جامع بودن آن را نقض کنیم.

قضیه ناتمامیت دوم گودل می‌گوید:

فرض کنید K یک نظریه در حساب باشد که قضایای اصلی حساب در آن اثبات شوند. در این صورت اگر K سازگار باشد، گزاره‌ای که بیانگر سازگاری Kاست یک جمله تصمیم ناپذیر خواهد بود. به عبارتی هیچ نظام سازگار به اندازه کافی قوی که بتواند توابع بازگشتی را نمایش دهد قادر نیست سازگاری خود را اثبات کند.

دو برداشت مختلف از کلمهٔ «تصمیم ناپذیر» وجود دارد. اولین برداشت مربوط به قضایای گودل است، برای قضیه‌ای که نه اثبات‌پذیر است و نه می‌توان آن را رد کرد. دومین برداشت مربوط به نظریهٔ شمارش پذیری است و در مورد مسائل تصمیم‌گیری است، که مجموعه‌های نامتناهی شمارا از پرسش‌هایی هستند که هر کدام جواب بله یا خیر دارند. یک مسئله را تصمیم ناپذیر گویند هر گاه هیچ تابع محاسبه پذیری که بتواند به همهٔ پرسش‌های مجموعهٔ مسئله پاسخ درست دهد، موجود نباشد. ارتباط بین این دو برداشت در این است که اگر یک مسئلهٔ تصمیم، تصمیم ناپذیر باشد، آنگاه هیچ دستگاه صوری جامعی که برای هر پرسش A در مسئله که «جواب A بله‌است» یا «جواب A خیر است»، یافت نمی‌شود. به خاطر این دو معنای کلمهٔ تصمیم ناپذیر، گاهی کلمهٔ مستقل به جای تصمیم ناپذیر برای برداشت اول به کار می‌رود. استفاده از کلمهٔ مستقل کمی ابهام‌برانگیز است. با این حال برخی از آن برای صرفاً اثبات ناپذیر بودن (چه قابل رد باشد یا نباشد)، استفاده می‌کنند.

کار ترکیبی گودل و پاول کهن (Paul Cohen) پیدا کردن دو نمونه از گزاره‌های تصمیم ناپذیر را نتیجه داد: فرضیهٔ پیوستار که نه اثبات پذیر و نه قابل رد در ZFC است و اصل انتخاب که در ZF (کل ZFC به جز اصل انتخاب) اثبات ناپذیر و رد نشدنی است. گودل در سال ۱۹۴۰ ثابت کرد که هیچ‌کدام از این گزاره‌ها نمی‌توانند در مجموعهٔ نظریهٔ ZFC یا ZF رد شوند. در دههٔ ۱۹۶۰، کهن ثابت کرد که هیچ‌کدام در ZF قابل اثبات نیستند، و فرضیهٔ تسلسل نیز در ZFC‍ قابل اثبات نیست.

در سال ۱۹۳۶، آلن تورینگ ثابت کرد که مسئلهٔ غیر مداوم(halting problem) -این پرسش که یک دستگاه تورینگ در یک برنامه متوقف می‌شود یا نه- تصمیم ناپذیر است. این نتیجه بعداً به قضیهٔ رایس تعمیم یافت.

در سال ۱۹۷۷، نشان داده شد که مسئلهٔ وایت هد در نظریهٔ گروه‌ها تصمیم ناپذیر است.

برخی نویسندگان مثل J. R. Lucas بر این باورند که قضایای گودل در مورد هوش انسان نیز درست هستند. بیشتر مباحثات در این زمینه است که آیا ذهن بشر هم‌ارز با دستگاه تورینگ، یا تز چرچ-تورینگ یا هر دستگاه متناهی دیگر است یا نه. اگر این گونه باشد و این دستگاه استوار هم باشد، آنگاه قضایای گودل می‌توانند در مورد آن به کار روند. هیلاری پاتنم پیشنهاد کرد که قضایای گودل در مورد ذهن بشر نمی‌تواند به کار رود، چون اشتباه می‌کند و بنابرین استوار نیست. شاید بتوان آن را در مورد توانایی بشر در علم یا ریاضیات در کل به کار برد. اگر ما بر این باور باشیم که استوار است، آنگاه نمی‌توانیم استواری آن را ثابت کنیم، یا نمی‌توانیم آن را به صورت دستگاه تورینگ نشان دهیم.

گاهی پژوهش‌هایی در مورد تأیید قضایای گودل از نظرهای مشابه که ورای ریاضیات و منطق هستند، انجام می‌شود. برای مثال، Régis Debray آن را در سیاست به کار برده‌است. تعدادی از مؤلفین مانند Torkel Franzen, Alan Sokalو Jean Bricmont, Ophelia Benson وJeremy Stangroom با این گونه بسط دادن این قضایا مخالفند.

Stanley Jaki، و بعدها به دنبال استیون هاوکینگ و دیگران، بر این باورند که از قضیهٔ گودل می‌توان نتیجه گرفت که حتی پیچیده‌ترین فرمول‌های فیزیک، ناکامل هستند. بنابرین نظریه‌ای نهایی که بتوان آن را به عنوان تعدادی متناهی اصل فرموله کرد، یافت نمی‌شود.