پی‌آمد

دیروز و پریروز برای بچه‌های اتاق دکتری‌مان راجع به قضیه گودل کلی حرف زدم و حرف زدیم. در همین حرف زدن‌ها توصیفی از قضیه گودل به ذهنم رسید که احساس می‌کنم قلب و عُمق قضیه گودل است بدون نیاز به جزئیات فنی آن (گرچه این فهم و توصیفات هیچ وقت بدون درگیر شدن با جزئیات به دست نمی‌آید)

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

مثلا فرض کنید کسی ادعا کند فرمولی چون N وجود دارد که اگر عدد گودل یک جمله (همان عددی که به هر جمله نسبت می‌دهیم) در آن صدق کند حتما آن جمله در نظریه اعداد راست است و اگر عدد گودل آن جمله در N صدق نکند حتما آن جمله در نظریه اعداد نادرست  یا کاذب است. اگر چنین فرمولی وجود داشته باشد من به راحتی فرمول نقیض آن مثل B را می‌سازم که اگر عدد گودل یک جمله در B صدق کند آنگاه آن جمله در نظریه اعداد نادرست است یا کاذب است و برعکس. اگر چنین Nی وجود داشته باشد قطعا چنین Bی وجود دارد. حالا می‌ماند ساخت جمله «من کاذب هستم». ساخت این جمله از روی جمله B(S) ،یا ترجمه‌اش که می‌شود: «S کاذب است» ،چندان سخت نیست. اگرچه چون B فقط راجع به جملات نظر می‌دهد نه فرمول‌ها (و خود B یک فرمول است به این معنی که صدق و کذب عبارت «S کاذب است» وابسته به S است) ساخت جمله «من کاذب هستم» آنچنان هم سرراست نیست اما چندان هم سخت نیست: چون من می‌توانم به کمک B که یک فرمول در نظریه اعداد است صدق و کذب جمله‌های نظریه اعداد را بفهمم، آنگاه می‌توانم صدق و کذب فرمول‌هایی که در خودشان صدق می‌کنند یا نمی‌کنند را هم بسجنم کافی است عدد گودل هر فرمول مثل A(v) را در خودش جاگذاری کنم و سپس جمله حاصل را (در واقع عدد گودلش را) در B جاگذاری کنم، یعنی اگر عدد گودل فرمول A(v) برابر a باشد آنگاه معنی B(A(a)) در واقع «A(a) کاذب است» است.  بنابر این می‌توان به راحتی فرمولی بسازم که بگوید «فرمول A(v) در خودش صدق نمی‌کند»، نام این فرمول را Bp(A(v)) بگذارید، پس معنی Bp(A(v)) این است که «جاگذاری فرمول A(v) در خودش کاذب است». حالا اگر کودکانه بپرسیم که اگر فرمول Bpرا در خودش جاگذاری کنیم چه می‌شود؟ ترجمه Bp(Bp) می‌شود «جاگذاری فرمول Bp در خودش کاذب است» اما این همان «جاگذاری فرمول Bp در خودش» است و این یعنی جمله «من کاذب هستم» به دست آمده :)) بنا بر این چنین B و چنین Nی وجود ندارد و اعداد طبیعی تعریف پذیر نیست با هیچ الگوریتمی در هیچ زبانی!

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

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

درسی که من از این قضیه و این بیان می‌گیرم این است که صوری سازی می‌تواند ما را به شدت محدود کند گرچه جلو کژتابی و زمین خوردن را می‌گیرد اما به قیمت این که به ما می‌گوید اصلا راه نروید!

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