در منطق ریاضی، قضایای ناتمامیت گودل، توسط کورت گودل در سال ۱۹۳۱ ثابت شدند. این قضایا در فلسفهٔ ریاضیات از اهمیت به‌سزایی برخوردارند و دلیل اصلی این اهمیت، رد برنامهٔ هیلبرت برای یافتن مجموعه‌ای جامع و استوار از اصول موضوع برای کل ریاضیات است.
قضیه اول ناتمامیت گودل
قضیهٔ اول ناتمامیت گودل، شاید مشهورترین نتیجه در منطق ریاضیات باشد، که بیان می‌کند:
برای هر صور استوار، نظریهٔ شمارش پذیری بازگشتی که اصول حسابی را ثابت می‌کند، یک گزارهٔ حسابی می‌توان یافت که درست است اما قابل اثبات در نظریه نیست. این بدین معناست که یک نظریهٔ تولید شده که قابلیت توضیح حساب بنیادی را دارد، نمی‌تواند هم جامع و هم استوار باشد.
در این جا، «نظریه» به معنای مجموعه‌ای نامتناهی از گزاره‌ها است، که برخی از آنها بدون اثبات پذیرفته می‌شوند(که بدیهیات خوانده می‌شوند)، و برخی دیگر(قضایا)از بدیهیات منتج می‌شوند.«قابل اثبات بودن در نظریه» یعنی «اشتقاق‌پذیر بودن از بدیهیات و مفاهیم اولیهٔ نظریه به کمک استاندارد منطق مرتبه اول (first-order logic)». یک نظریه «استوار» است، در صورتی که هیچ‌گاه یک تناقض را اثبات نکند. «قابل ایجاد» به این معناست که فرآیندی وجود دارد که می‌تواند گزاره را به وسیلهٔ بدیهیات، مفاهیم اولیهٔ موجود و منطق مرتبه اول تولید کند. گزارهٔ با نتیجهٔ درست اما غیر قابل اثبات، جملهٔ گودل خوانده می‌شود. این فرضیه که می‌توان اعضای نظریه را شمرد، یعنی می‌توان برنامه‌ای کامپیوتری نوشت، که تمامی اعضای نظریه را لیست کند که البته شمردن بدیهیات کافی خواهد بود، زیرا قضایا از بدیهیات مشتق می‌شوند. اگر بخواهیم به طور کلی قضیهٔ اول را تشریح کنیم، جملهٔ گودل G قابل اثبات به وسیلهٔ نظریهٔ T نیست.اگر G به کمک بدیهیات T قابل اثبات باشد، آنگاه یک قضیه در T محسوب می‌شود و در واقع خود را نقض می‌کند و به همین خاطر T نمی تواند استوار باشد. اگر T استوار باشد، آنگاه G نمی‌تواند در آن ثابت شود که این یعنی G درست خواهد بود. بنابراین اثبات‌پذیر بودن در T معنای درستی از «درستی» به ما عرضه نمی‌کند. در واقع T جامع نیست. حال اگر G را به T بیفزاییم و مجموعهٔ جدیدی تولید کنیم، باز هم می‌توانیم یک گزارهٔ جدید گودل برای مجموعهٔ فعلی ارایه کنیم و جامع بودن آن را نقض کنیم.
قضیه ناتمامیت دوم
این قضیه می‌گوید:
برای هر نظریهٔ T که شمارش‌پذیرِ بازگشتی صوری است و شامل اصول حسابی بنیادی و همچنین اصولی معین در مورد اثبات‌پذیری صوری است، T شامل گزاره‌ای در مورد غیر استوار بودن خود خواهد بود اگر و تنها اگر T استوار نباشد.
(اثبات بخش «اگر») اگر T استوار نباشد، آنگاه همه چیز قابل اثبات است، از جمله این که T غیر استوار است.(اثبات بخش «تنها اگر»:) اگر T استوار باشد، آنگاه T شامل گزارهٔ استوار بودن خود نیست. این از قضیهٔ اول نتیجه گرفته می‌شود.
مثال‌هایی از گزاره‌های تصمیم ناپذیر
دو برداشت مختلف از کلمهٔ «تصمیم ناپذیر» وجود دارد. اولین برداشت مربوط به قضایای گودل است، برای قضیه‌ای که نه اثبات‌پذیر است و نه می‌توان آن را رد کرد. دومین برداشت مربوط به نظریهٔ شمارش پذیری است و در مورد مسائل تصمیم گیری است، که مجموعه‌های نامتناهی شمارا از پرسش‌هایی هستند که هر کدام جواب بله یا خیر دارند. یک مسئله را تصمیم ناپذیر گویند هر گاه هیچ تابع محاسبه پذیری که بتواند به همهٔ پرسش‌های مجموعهٔ مسئله پاسخ درست دهد، موجود نباشد. ارتباط بین این دو برداشت در این است که اگر یک مسئلهٔ تصمیم، تصمیم ناپذیر باشد، آنگاه هیچ دستگاه صوری جامعی که برای هر پرسش 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)، و بعدها به دنبال استیون هاوکینگ و دیگران، بر این باورند که از قضیهٔ گودل می‌توان نتیجه گرفت که حتی پیچیده‌ترین فرمول‌های فیزیک، ناکامل هستند. بنابرین نظریه‌ای نهایی که بتوان آن را به عنوان تعدادی متناهی اصل فرموله کرد، یافت نمی‌شود.