قضایای ناتمامیت گودل

Article on other languages:

• مبرهنة_عدم_الاكتمال_لغودل
• Теорема_на_Гьодел_за_непълнота
• Teorema_d'incompletesa_de_Gödel
• Gödelovy_věty_o_neúplnosti
• Gödelscher_Unvollständigkeitssatz
• Gödel's_incompleteness_theorems
• Teoremoj_de_nekompleteco
• Teoremas_de_la_incompletitud_de_Gödel
• Gödelin_epätäydellisyysteoreema
• Théorème_d'incomplétude_de_Gödel
• Teorema_da_incompletude_de_Gödel
• משפטי_האי_שלמות_של_גדל
• Gödelovi_teoremi_nepotpunosti
• Gödel_első_nemteljességi_tétele
• Godel-teorio
• Teoremi_di_incompletezza_di_Gödel
• ゲーデルの不完全性定理
• გოდელის_არასრულობის_თეორემები
• 불완전성_정리
• Onvolledigheidsstellingen_van_Gödel
• Teoreme_de_Godel
• Twierdzenie_Gödla
• Teorema_da_Incompletude_de_Gödel
• Теоремы_Гёделя_о_неполноте
• Gödelova_veta_o_neúplnosti
• Геделове_теореме_о_непотпуности
• Gödels_ofullständighetssats
• ทฤษฎีบทความไม่สมบูรณ์ของเกอเดล
• Gödel'in_eksiklik_teoremi
• Теореми_Геделя_про_неповноту
• 哥德尔不完备定理

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

در منطق ریاضی، قضایای ناتمامیت گدل، که توسط کورت گدل در سال ۱۹۳۱ ثابت شدند.این قضایا در فلسفهٔ ریاضیات از اهمیت به سزای برخوردارند و دلیل اصلی این اهمیت، رد برنامهٔ هیلبرت(Hilbert's program)برای یافتن مجموعه‌ای جامع و استوار از بدیهیات است.برخی نویسندگان مثلJ. R. Lucasدر این مورد که این قضایا مفاهیمی در حوزهٔ فلسفه و شناخت شناسی، مانند رد هر گونه نظریه ی کلی گرایی، مطرح کرده‌اند، که البته کمتر مورد قبول واقع شده‌اند.

قضیه اول ناتمامیت گدل

قضیه اول ناتمامیت گدل، شاید مشهور ترین نتیجه در منطق ریاضیات نباشد، که بیان می‌کند:

برای هر صور استوار، نظریهٔ شمارش پذیری بازگشتی که اصول حسابی را ثابت می‌کند، یک گزارهٔ حسابی می‌توان یافت که درست است اما قابل اثبات در نظریه نیست.این بدین معناست که یک نظریه تولید شده که قابلیت توضیح حساب بنیادی را دارد، نمی تواند هم جامع و هم استوار باشد.

در این جا، «نظریه» به معنای مجموعه‌ای نا متناهی از گزاره‌ها است، که برخی از آنها بدون اثبات پذیرفته می‌شوند(که بدیهیات خوانده می‌شوند)، و برخی دیگر(قضایا)از بدیهیات منتج می‌شوند.«قابل اثبات بودن در نظریه»یعنی«اشتقاق پذیر بودن از بدیهیات و مفاهیم اولیهٔ نظریه به کمک استاندارد منطق مرتبه اول(first-order logic)».یک نظریه «استوار» است، در صورتی که هیچ گاه یک تناقض را اثبات نکند.«قابل ایجاد»به این معناست که فر آیندی وجود دارد که می‌تواند گزاره را به وسیلهٔ بدیهیات، مفاهیم اولیهٔ موجود و منطق مرتبه اول تولید کند.گزارهٔ با نتیجهٔ درست اما غیر قابل اثبات، جملهٔ گدل خوانده می‌شود.این فرضیه که میتوان اعضای نظریه را شمرد، یعنی می توان برنامه‌ای کامپیوتری نوشت، که تمامی اعضای نظریه را لیست کند که البته شمردن بدیهیات کافی خواهد بود، زیرا قضایا از بدیهیات مشتق می‌شوند.اگر بخواهیم به طور کلی قضیه اول را تشریح کنیم، جمله گدل Gقابل اثبات به وسیله نظریه Tنیست.اگر Gبه کمک بدیهیات Tقابل اثبات باشد، آنگاه یک قضیه در Tمحسوب می‌شود، و در واقع خود را نقض می‌کند، و به همین خاطر Tنمی تواند استوار باشد.اگر Tاستوار باشد، آنگاه Gنمی تواند در آن ثابت شود که این یعنیG درست خواهد بود، بنابراین اثبات پذیر بودن در Tمعنای درستی از درستی به ما عرضه نمی‌کند.در واقع Tجامع نیست. حال اگر G را بهT بیفزاییم و مجموعهٔ جدیدی تولید کنیم، باز هم میتوانیم یه گزارهٔ جدید گدل برای مجموعهٔ فعلی ارائه کنیم و جامع بودن آن را نقض کنیم.

قضیه ناتمامیت دوم

این قضیه می‌گوید:

برای هر نظریه T که شمارش پذیر بازگشتی صوری است و شامل اصول حسابی بنیادی و همچنین اصولی معین در مورد اثبات پذیری صوری است، Tشامل گزاره‌ای در مورد غیر استوار بودن خود خواهد بود اگر و تنها اگر Tاستوار نباشد.

(اثبات بخش «اگر») اگر T استوار نباشد، آنگاه همه چیز قابل اثبات است، از جمله این که Tغیر استوار است.(اثبات بخس«تنها اگر»:)اگر Tاستوار باشد، آنگاه Tشامل گزارهٔ استوار بودن خود نیست.این از قضیهٔ اول نتیجه گرفته می‌شود.

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

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

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

در سال ۱۹۳۶، Alan Turing ثابت کرد که مسئله غیر مداوم(halting problem)-این پرسش که یک دستگاه تورینگ در یک برنامه متوقف می‌شود یا نه-تصمیم نا پذیر است.این نتیجه بعدا به قضیهٔ رایس تعمیم یافت.

در سال ۱۹۷۷، نشان داده شد که مسئلهٔ وایت هد در نظریهٔ گروه‌ها تصمیم نا پذیر است.

دستگاهها و ذهن‌ها

برخی نویسندگان مثل J. R. Lucasبر این باور اند که قضایای گدل در مورد هوش انسان نیز درست هستند.بیشتر مباحثات در این زمینه‌است که آیا ذهن باشر هم ارز با دستگاه تورینگ، یا قضیهٔ کلیسا-تورینگ(Church-Turing thesis)، یا هر دستگاه متناهی دیگر است یا نه.اگر این گونه باشد و این دستگاه استوار هم باشد، آنگاه قضایای گدل می‌توانند در مورد آن به کار روند. Hilary Putnam پیشنهاد کرد که قضایا ی گدل در مورد ذهن باشر نمیتواند به کار رود، چون اشتباه می‌کند بنابرین استوار نیست.، شاید بتوان آن را در مورد توانایی باشر در علم یا ریاضیات در کل به کار برد. اگر ما بر این باور باشیم که استوار است، آنگاه نمی‌توانیم استواری آن را ثابت کنیم، یا نمی‌توانیم آن را به صورت دستگاه تورینگ نشان دهیم.

پست مدرنیسم و فلسفهٔ اقلیمی

گاهی پژوهش‌هائی در مورد تأیید قضایای گدل از نظرهای مشابه که ورای ریاضیات و منطق هستند، انجام می‌شود. برای مثال، Régis Debray آن را در سیاست به کار برده‌است. تعدادی از مؤلفین مانند Torkel Franzen، Alan Sokalو Jean Bricmont، Ophelia Benson وJeremy Stangroomبا این گونه بسط دادن این قضایا مخالف اند.

نظریه‌های همه چیز در فیزیک

Stanley Jaki، و بعد‌ها به دنبال استفان هاوکینگ و دیگران، در این مورد که از قضیه گدل می‌توان نتیجه گرفت که حتی پیچیده‌ترین فرمول‌های فیزیک ناکامل هستند، بنا بر این نظریه‌ای نهایی که بتوان آن را به عنوان تعدادی متناهی اصل فرموله کرد، یافت نمی‌شود.

همچنین مشاهده کنید

• proof sketch for incompleteness theoreoms
• godel number
• consistency proof
• completeness theoreoms

منابع

• ‎

  Ebbinghaus, H. -D., Flum, J., and Thomas, W. Mathematical logic, Springer-Verlag New York Inc., ۱۹۸۴. ISBN: ۰-۳۸۷-۹۶۱۷۰-۴

  این نوشتار در زمینهٔ ریاضیات خُرد است. با گسترش آن به ویکی‌پدیا کمک کنید.

  --Amirali shambayati ‏۳ ژوئیهٔ ۲۰۰۸، ساعت ۱۴:۵۶ (UTC)