پی‌آمد

مدل اعداد طبیعی همراه با جمع و ضرب و تالی را در نظر بگیرید.

1. فرض کنید یک زبان به اندازه کافی صوری‌پذیر (مکانیکی، رشته‌ای از نمادها) با معناشناسی مناسب نسبت به این مدل داریم.
2. یک مجموعه قاعده استنتاج هم در نظر بگیرید که از یک رشته نماد، یک رشته نماد جدید را به صورت مکانیکی نتیجه می‌دهد.
3. فرض کنید این قواعد استنتاج درستی را هم رعایت می‌کنند.
4. فرض کنید این قواعد استنتاج تمامیت را هم رعایت می‌کنند. یعنی همه جملات همیشه درست را می‌توان استنتاج کرد (در نتیجه اگر هر مدلی که A را برقرار کند، B را هم برقرار کند آنگاه از A به B استنتاجی هم وجود دارد)
5. با این قواعد استنتاج یک زیرنظریه از نظریه اعداد را در نظر بگیرید که توانایی انجام جمع و ضرب در نظریه اعداد را دارد (قضایای اصلی حساب را می‌توان در این زیرنظریه اثبات کرد).

فرضها همین‌قدر مینیمال و انتزاعی هستند! حالا با این فرضهای مینیمال و انتزاعی، می‌توان نشان داد که هر جمله راجع به نظریه اعداد خودش یک عدد یکتا (عدد گودل) دارد. این صرفا به این فرض 1 وابسته است. می‌توان نشان داد زیرنظریه مذکور در فرض 5 توانایی لازم برای نمایش هر قاعده استنتاجی شبیه قواعد استنتاج 2 در خودش دارد، به این معنی که اگر عدد جمله A را #A بنامیم، و عدد یکتای جمله B را #B بنامیم، می‌توان به جای الگوریتم استنتاج B از A ، محاسبه #B را از روی #A انجام داد، بنا بر این به جای استنتاج تنها محاسبه کرد بدون این که به رشته نمادها یا خود قواعد استنتاج ارجاع داد.

با همین نتایج و فرضهای ساده می‌توان نشان داد که مدل اعداد طبیعی نه تنها تصمیم پذیر بلکه حتی تعریف‌پذیر هم نیست، به این معنی که هیچ فرمولی در زبان فرض 1 نمی‌توان نوشت که این فرمول فقط و فقط وقتی برقرار باشد که عدد گودل ورودی آن مربوط به یک جمله درست در اعداد طبیعی باشد. خُب حالا این به چه درد می‌خورد؟

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

در منطق و زبان مرتبه دوم و بالاتر اوضاع بدتر می‌شود. می‌توان نشان داد قدرت بیان این منطق چنان بالا است که می‌توان مدل اعداد طبیعی را در آن به صورت اصل‌پذیر متناهی نوشت، یعنی تعدادی جمله به عنوان اصل موضوعه نظریه اعداد در نظر بگیرید، آنگاه نشان داده‌اند تمام مدل‌های این اصول موضوعه با هم یک‌ریخت است. حالا با توجه به این که حالا اگر با این اصول موضوعه شروع به استنتاج کنیم، با توجه به فرض تمامیت در 4 آنگاه می‌تواند تمام صدق‌های نظریه اعداد را با قواعد استنتاج 2 به دست بیاورد (چون هر مدل جمله‌های اصول موضوعه در صدق و کذب گزاره‌ها با مدل اصلی اعداد طبیعی مشترک است، پس اگر تمامیت برقرار باشد آنگاه می‌توان هر صدق نظریه اعداد را به دست آورد). اما این یعنی تصمیم‌پذیری نظریه اعداد که می‌دانیم حتی تعریف‌پذیر هم نیست. بنا بر این برای منطق مرتبه دوم، یکی از فرضهای 2 3 4 را باید کنار بگذاریم (فرض 1 که خود زبان مرتبه 2 است و فرض 5 را هم به راحتی می‌توان ذیل فرض 1 گنجاند) یعنی منطق مرتبه دوم و بالاتر، و هر منطق و زبانی که به اندازه کافی قوی باشد که نظریه اعداد را با متناهی تا اصل بیان کرد، یا درست نیست یا تمام نیست یا نظریه برهان الگوریتمی‌(قواعد استنتاج) ندارد!

پ.ن: چرا نوشتم؟ فشار گشتن به دنبال خانه چنان آزاردهنده بود که ترجیح دادم به این موضوع پناه ببرم تا کمی‌حالم بهتر شود و یادم برود که در این دنیای خاکی با تمام اقتضائات ملال‌آورش زنده‌ام. مضاف بر این که همیشه در ذهنم بود که ربط دقیق قضیه گودل با محدودیت منطق مرتبه بالا نیست، هیچ وقت این قدر دقیق صورتبندی نکرده بودم.