قضایای ناتمامیت گودل: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Fatranslator (بحث | مشارکت‌ها) جز ربات:افزودن الگو ناوباکس {{فرامنطق}}+ |
|||
خط ۳:
== قضیه اول ناتمامیت گودل ==
قضیهٔ اول ناتمامیت گودل، شاید مشهورترین نتیجه در منطق [[ریاضیات]] باشد، که بیان می‌کند:
:''فرض کنید K یک [[نظریه]] در زبان حساب باشد که به نحوی بازگشتی قابل اصل بندی باشد و قضایای اصلی حساب در آن اثبات شوند. در این صورت اگر K سازگار باشد، جمله‌ای مانند G وجود خواهد داشت به قسمی که:''
:''الف) اگر K نظریه‌ای سازگار باشد G در K اثبات پذیر نیست.
:''ب) اگر K نظریه‌ای [[ω ـ سازگاری|ω ـ سازگار]] باشد<ref>ω ـ سازگاری یک ویژگی قویتر از سازگاری است.</ref> نقیض G در K اثبات پذیر نیست.
خط ۱۹:
به خاطر این دو معنای کلمهٔ تصمیم ناپذیر، گاهی کلمهٔ مستقل به جای تصمیم ناپذیر برای برداشت اول به کار می‌رود. استفاده از کلمهٔ مستقل کمی ابهام‌برانگیز است. با این حال برخی از آن برای صرفاً اثبات ناپذیر بودن (چه قابل رد باشد یا نباشد)، استفاده می‌کنند.
کار ترکیبی گودل و [[پاول کهن]] (Paul Cohen) پیدا کردن دو نمونه از گزاره‌های تصمیم ناپذیر را نتیجه داد: [[فرضیه
در سال ۱۹۳۶، [[آلن تورینگ]] ثابت کرد که مسئلهٔ غیر مداوم(halting problem) -این پرسش که یک [[دستگاه تورینگ]] در یک برنامه متوقف می‌شود یا نه- تصمیم ناپذیر است. این نتیجه بعداً به [[قضیه رایس|قضیهٔ رایس]] تعمیم یافت.
| |||