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