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