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

== مثال‌هایی از گزاره‌های تصمیم ناپذیر ==

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

 

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