قضایای ناتمامیت گودل: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
برچسب: نیازمند بازبینی |
جز ویرایش و تصحیح (جزئی) |
||
خط ۳:
== قضیه اول ناتمامیت گودل ==
قضیهٔ اول ناتمامیت گودل، شاید مشهورترین نتیجه در منطق ریاضیات باشد، که بیان میکند:
:''فرض کنید K یک [[نظریه]] در حساب باشد که قضایای اصلی حساب در آن اثبات شوند. در این صورت اگر
:''الف) اگر K نظریهای سازگار باشد G در K اثبات پذیر نیست.
:''ب) اگر K نظریهای [[ω ـ سازگاری|ω ـ سازگار]] باشد <ref> ω ـ سازگاری یک ویژگی قویتر از سازگاری است. </ref> نقیض G در K اثبات پذیر نیست.
خط ۹:
در این جا، «نظریه» به معنای تعدادی قواعد استنتاج، تعدادی علائم و مجموعهای نامتناهی از [[گزاره|گزارهها]] است، که تعدادی متناهی از این گزارهها بدون اثبات پذیرفته میشوند(که [[اصل موضوع|اصول موضوع]] خوانده میشوند)، و برخی دیگر از گزارهها از اصول موضوع به دست میآیند؛ به این گزارهها که با کمک قواعد استنتاج از اصول موضوع به دست میآیند [[قضیه]] میگوییم. «[[اثبات پذیر]] بودن در نظریه» یعنی «اشتقاقپذیر بودن از اصول موضوع نظریه به کمک قواعد استنتاج نظریه». یک نظریه «[[سازگار]]» است، در صورتی که هیچگاه یک [[تناقض]] را اثبات نکند. بنا بر قضیه ناتمامیت اول گودل، هیچ نظریه اصل موضوعی که حداقل قضایای اساسی حساب را بتواند اثبات کند وجود ندارد که همه قضایا را اثبات یا رد کند. به عبارتی در هر نظام اصل موضوعی ریاضی جملاتی تصمیم ناپذر وجود دارند. طبق [[منطق کلاسیک]] و [[منطق ارسطو|منطق ارسطویی]] هر گزارهای یا صادق است و یا کاذب. قضیه ناتمامیت اول میگوید که نظامهای اصل موضوعی که قابلیت نشان دادن [[تابع بازگشتی|توابع بازگشتی]] را داشته باشند نمیتوانند چنین تصمیمی درباره گزارههای حساب بگیرند. یعنی جملاتی در این نظامها وجود دارند که نه اثباتپذیرند و نه انکارپذیر.
میتوان نشان داد که اگر G را به
== قضیه ناتمامیت دوم ==
قضیه ناتمامیت دوم گودل میگوید:
:''فرض کنید K یک [[نظریه]] در حساب باشد که قضایای اصلی حساب در آن اثبات شوند. در این صورت اگر
== مثالهایی از گزارههای تصمیم ناپذیر ==
|