قضایای ناقص بودن گودل دو قضیه از منطق ریاضی هستند که محدودیتهای ذاتی هر سیستم رسمی بدیهی رسمی را نشان می دهند که قادر به مدل سازی حسابی اساسی است . این نتایج ، که توسط Kurt Gödel در سال 1931 منتشر شد ، هم در منطق ریاضی و هم در فلسفه ریاضیات مهم است . قضایا به طور گسترده ، اما نه جهانی ، تفسیر می شوند که نشان می دهد برنامه هیلبرت برای یافتن مجموعه ای کامل و مداوم از بدیهیات برای همه ریاضیات غیرممکن است.

اولین قضیه ناقص بودن بیان می کند که هیچ سیستم مداوم از بدیهیات که قضایای آنها با یک روش مؤثر ذکر شود (مثلاً الگوریتم ) قادر به اثبات تمام حقایق در مورد حساب اعداد طبیعی نیست . در مورد چنین سیستم رسمی سازگار ، همیشه عباراتی در مورد اعداد طبیعی وجود دارد که صحیح هستند ، اما در سیستم غیرقابل اثبات هستند. قضیه ناقصی دوم ، پسوند اول ، نشان می دهد که سیستم نمی تواند قوام خودش را نشان دهد.

با استفاده از یک استدلال مورب ، قضایای ناقص بودن گودل اولین مورد از چندین قضیه نزدیک به محدودیتهای سیستمهای رسمی بود. آنها با قضیه غیرقابل انکارپذیری تارسکی در مورد ناشناخته بودن رسمی حقیقت ، اثبات کلیسا مبنی بر اینکه Entscheidungsproblem هیلبرت غیرقابل حل است ، و قضیه تورینگ مبنی بر وجود هیچ الگوریتمی برای حل مسئله متوقف شد .

 

فهرست

سیستم های رسمی: کامل ، سازگاری و اگزوماتیک شدن مؤثر [ ویرایش ]

قضایای ناقص بودن در مورد سیستمهای رسمی كه از پیچیدگی كافی برای بیان حسابی اولیه اعداد طبیعی برخوردار هستند و سازگار و به طور مؤثر اگزایماتیز هستند ، این مفاهیم را كه در زیر شرح داده شده است ، اعمال می شود. به خصوص در چارچوب منطق مرتبه اول ، سیستمهای رسمی نیز به تئوریهای رسمی گفته می شوند . به طور کلی ، یک سیستم رسمی یک دستگاه قیاسی است که از مجموعه ای از بدیهیات و همچنین قواعد دستکاری نمادین (یا قواعد استنتاج) تشکیل شده است که می تواند مشتق قضایای جدید از بدیهیات باشد. یک نمونه از چنین سیستم ، حساب مرتبه اول Peano است ، سیستمی که در آن همه متغیرها برای نشان دادن اعداد طبیعی در نظر گرفته شده اند. در سیستمهای دیگر مانند نظریه مجموعهفقط برخی از جملات سیستم رسمی اظهاراتی درباره اعداد طبیعی بیان می کنند. قضایای ناقص بودن درمورد قابلیت اثبات رسمی در این سیستم ها است ، نه اینکه در مورد "پایداری" به معنای غیر رسمی باشد.

چندین ویژگی که یک سیستم رسمی ممکن است داشته باشد از جمله کامل بودن ، ثبات و وجود یک اگزوماتیزاسیون مؤثر است. قضایای ناقص بودن نشان می دهد كه سیستم هایی كه دارای مقدار كافی حسابی هستند ، نمی توانند هر سه این خصوصیات را داشته باشند.

آکسیوماتیزاسیون مؤثر [ ویرایش ]

گفته می شود که اگر سیستم مجموعه ای از قضایای آن مجموعه ای بصورت شمارش پذیر بازگشتی باشد ، یک سیستم رسمی بطور مؤثر Axiomatized (که به اصطلاحاً تولید می شود ) نیز شناخته می شود (Franzén 2005 ، ص 112).

این بدان معناست که یک برنامه رایانه ای وجود دارد که در اصل می تواند تمام قضایای سیستم را بدون ذکر هر گزاره ای که قضیه نیست ، شمارش کند. نمونه هایی از تئوری های تولید شده به طور موثر شامل حساب ریاضی Peano و نظریه مجموعه Zermelo-Fraenkel (ZFC) است.

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

کامل بودن [ ویرایش ]

مجموعه ای از بدیهیات (به صورت نحوی یا نفی -) کامل است ، اگر برای هر جمله ای که به زبان اصول وجود دارد ، آن جمله یا نفی آن از اصل و اساس آن قابل اثبات است (اسمیت 2007 ، ص 24). این مفهومی است که برای اولین قضیه ناقصیت گودل مرتبط است. این نباید با کمال معنایی اشتباه گرفته شود ، به این معنی که مجموعه ای از بدیهیات تمام اصطلاحات معنایی زبان معین را اثبات می کند. گادل در قضیه كامل خود ثابت كرد كه منطق مرتبه اول از نظر معنایی كامل است. اما از نظر نحوی کاملاً کامل نیست ، زیرا جملات قابل بیان در زبان منطق مرتبه اول وجود دارد که نه تنها از بدیهیات منطق قابل اثبات و رد نیست.

در یک سیستم منطقی صرف انتظار داشتن کامل بودن نحوی پوچ است. اما در سیستم ریاضیاتی ، اندیشمندانی مانند هیلبرت معتقد بودند که فقط زمان لازم است که چنین اکسسوماتیسم را پیدا کنیم که به فرد اجازه دهد یا اثبات یا رد کند (با اثبات نفی خود) هر یک از فرمول های ریاضی.

یک سیستم رسمی ممکن است از نظر طراحی کاملاً ناقص باشد ، همانطور که منطق به طور کلی وجود دارد. یا ممکن است ناقص باشد زیرا تمام بدیهیات لازم کشف نشده یا درج نشده است. به عنوان مثال ، هندسه اقلیدسی بدون فرضیه موازی ناقص است ، زیرا برخی از عبارات در زبان (مانند فرضیه موازی خود به خود) از بدیهیات باقی مانده قابل اثبات نیست. به همین ترتیب ، تئوری سفارشات خطی متراکم کامل نیست ، اما با یک اصل بدیهی اضافی کامل می شود که بیان می کند هیچ نقطه پایانی در دستور وجود ندارد. فرضیه زنجیره بیانیه در زبان است ZFCاین در ZFC قابل اثبات نیست ، بنابراین ZFC کامل نیست. در این حالت ، هیچ نامزد مشخصی برای بدیهیات جدید وجود ندارد که مسئله را برطرف کند.

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

قوام [ ویرایش ]

مجموعه ای از بدیهیات (به سادگی) سازگار است اگر بیانیه ای وجود ندارد به گونه ای که هم اظهارات و هم نفی آن از بدیهیات قابل اثبات باشد و در غیر این صورت متناقض باشد.

حساب Peano به طرز قابل توجهی از ZFC سازگار است ، اما از درون خودش نیست. به طور مشابه، ZFC است قابل اثبات نیست از درون خود سازگار است، اما ZFC + "وجود دارد وجود دارد وجود دارد کاردینال غیر قابل دسترس " ثابت می کند ZFC سازگار است چرا که اگر κ حداقل مانند کاردینال، پس از آن است V κ نشسته در داخل جهان فون نویمان است مدل از ZFC، و اگر یک الگوی داشته باشد ، یک تئوری سازگار است.

اگر کسی تمام عبارات را به زبان حسابی Peano به عنوان بدیهیات در نظر بگیرد ، پس این تئوری کامل است ، دارای یک مجموعه ای از شمایل بدیهی بازگشتی است و می تواند علاوه بر و ضرب را توصیف کند. با این حال ، سازگار نیست.

نمونه های دیگری از تئوری های متناقض از پارادوکس ها ناشی می شوند که وقتی طرح اصلی بدیهی از درک بدون محدودیت در تئوری مجموعه فرض می شود نتیجه می گیرند.

سیستم های حاوی حساب [ ویرایش ]

قضایای ناقص بودن فقط مربوط به سیستمهای رسمی است که قادر به اثبات جمع آوری کافی از حقایق در مورد اعداد طبیعی هستند. یک مجموعه کافی مجموعه ای از قضایای است رابینسون حساب Q . برخی از سیستم ها ، مانند حساب Peano ، می توانند به طور مستقیم اظهاراتی درباره اعداد طبیعی بیان کنند. دیگران ، مانند نظریه مجموعه ZFC ، می توانند عبارات مربوط به اعداد طبیعی را به زبان خود تفسیر کنند. هر یک از این گزینه ها برای قضایای ناقص بودن مناسب است.

نظریه زمینه های جبری بسته بسته از یک ویژگی خاص ، کامل ، سازگار است و دارای مجموعه ای از نامحدود اما به صورت بازگشتی قابل شمارش از بدیهیات است. اما رمزگذاری اعداد صحیح در این تئوری امکان پذیر نیست و این تئوری نمی تواند حسابی از اعداد صحیح را توصیف کند. نمونه مشابه نظریه میدانهای بسته واقعی است که در اصل معادل اصول تارسکی برای هندسه اقلیدسی است . بنابراین خود هندسه اقلیدسی (در فرمول تارسکی) نمونه ای از یک نظریه کامل ، سازگار و مؤثر آکسیوماتیزه است.

سیستم حسگر Presburger شامل مجموعه ای از بدیهیات برای اعداد طبیعی و فقط با عمل اضافی است (ضرب حذف شده است). حسابی Presburger کاملاً کامل ، سازگار و با بازگشت بی شماری است و می تواند علاوه بر رمزگذاری ضرب اعداد طبیعی ، علاوه بر رمزگذاری آن نیست ، نشان می دهد که برای قضایای گودل شخص نیاز به نظریه دارد تا نه تنها علاوه بر بلکه ضرب را رمزگذاری کند.

دن ویلارد (2001) برخی از خانواده های ضعیف سیستم های حساب شده را مورد بررسی قرار داده است که اجازه می دهد تا به اندازه کافی حسابی به عنوان روابط برای رسمی سازی شماره گودل قدرت داشته باشند ، اما به اندازه کافی قوی نیستند که به عنوان یک تابع ضرب شوند ، و بنابراین در اثبات قضیه ناقصی دوم موفق نیستند. این سیستم ها سازگار و قادر به اثبات سازگاری خود هستند (به نظریه های خود تأیید مراجعه کنید ).

اهداف متناقض [ ویرایش ]

در انتخاب مجموعه ای از بدیهیات ، یک هدف این است که بدون اثبات نتایج نادرست بتوانیم هرچه بیشتر نتایج صحیح را اثبات کنیم. به عنوان مثال ، ما می توانیم مجموعه ای از بدیهیات واقعی را تصور کنیم که به ما امکان می دهد هر ادعای حسابی واقعی را در مورد اعداد طبیعی اثبات کنیم (اسمیت 2007 ، ص 2). در سیستم استاندارد منطق مرتبه اول ، مجموعه ای از متناقضات متناقض هر جمله ای را به زبان خود اثبات می کند (این را گاهی اوقات اصطلاح انفجار خوانده می شود ) ، و به این ترتیب به طور خودکار کامل می شود. مجموعه ای از بدیهیات که کاملاً کامل و سازگار است ، با این حال ، مجموعه ای از حداکثر قضایای غیر متناقض را اثبات می کند (هینمن 2005 ، ص 143).

الگویی که در بخش های قبلی با حسابی Peano ، ZFC و ZFC + نشان داده شده است "وجود یک کاردینال غیرقابل دسترسی وجود دارد" به طور کلی نمی توان شکسته شد. در اینجا ZFC + "وجود یک کاردینال غیرقابل دسترسی" نمی تواند به خودی خود ثابت شود. این همچنین کامل نیست ، همانطور که در ZFC نشان داده شده است "یک تئوری کاردینال غیرقابل دسترسی وجود دارد" فرضیه پیوسته حل نشده است.

اولین قضیه ناقص بودن نشان می دهد که ، در سیستمهای رسمی که می توانند حسابی اساسی را بیان کنند ، هرگز نمی توان فهرست نهایی کاملی و مداوم از بدیهیات را ایجاد کرد: هر بار که یک عبارت اضافی و سازگار به عنوان یک اصل اضافه شود ، عبارات واقعی دیگری وجود دارد که هنوز نمی توانند حتی با بدیهیات جدید ثابت شود. اگر اصطلاحاتی اضافه شود که سیستم را کامل کند ، این کار را با هزینه ساختن سیستم ناسازگار انجام می دهد. حتی ممکن نیست یک لیست نامتناهی از بدیهیات کامل ، سازگار و مؤثر اگزایوماتیک باشد.

منبع

https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems