قضیه تعریف‌ناپذیری تارسکی و منطق مرتبه بالاتر

 

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

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 گنجاند) یعنی منطق مرتبه دوم و بالاتر، و هر منطق و زبانی که به اندازه کافی قوی باشد که نظریه اعداد را با متناهی تا اصل بیان کرد، یا درست نیست یا تمام نیست یا نظریه برهان الگوریتمی (قواعد استنتاج) ندارد!

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

فلسفه براوئر

 

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

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

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

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

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

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

 

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

** اتفاقا هر دوی این نسخه‌ها مبادی فلسفی دارند، به این معنی اگر با تکیه بر چنین تزهایی «فیزیکیات ابطالگرا» را همچین چیزی بسازیم و بگوییم «این فلسفی‌ترین مکتب فیزیکی است»، نتایج مزخرفی به دست می‌آید. تمام قدرت فیزیک در این است که خودش را به چنین قیودی محدود نمی‌کند.

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

قضیه گودل

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

 

همه داستان از جایی شروع می‌شود که گودل نشان می‌دهد هر زیرنظریه‌ای خاص از نظریه اعداد که در آن ضرب و تقسیم نمایش‌پذیر باشد این قدرت را دارد تا عبارت‌های ریاضی (به شرط این که به اندازه کافی صوری‌سازی شده باشد) را برای هر زبان شمارا رمزگذاری کرده و استنتاج‌ها و اثبات‌ها را با محاسبه انجام دهد. یعنی من به هر عبارت در هر زبان صوری می‌توانم یک عدد نسبت بدهم که عدد گودل عبارت است سپس به جای استنتاج از جمله 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 را نمی‌تواند در خودش اثبات کرد و این باز یعنی هر نظام ریاضی که بتواند نظریه اعداد را بسازد، (دست کم آن زیرنظریه‌ای که ضرب و تقسیم دارد) آنگاه این نظام نمی‌تواند سازگاری خودش را ثابت کند.

 

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

 

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

منطق ریاضی8 و آخر:منطق مرتبه دو و بالاتر

خب خوشبختانه فصل منطق مرتبه ۲ سریع تمام شد تا یک سال و دو هفته دست به گریبان بودنم با این موضوع تا حدی پایان یابد و بالاخره بتوانم به سراغ کتابهای دیگری که در کتابخانه خاک می‌خورند بروم. البته دلیل سریع تمام شدنش غیر از نحیف بودن این فصل این هم بود که قبلا پیش پیش خوانده بودم. راستش موضوع زیادی دستگیرم نشد که بنویسم چون هر دو کتاب خیلی خلاصه و سربسته نوشته بودند. اما چیزهایی که فهمیدم را می‌نویسم تا داشته باشم:

 

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

 

اما مشکلاتی هم در مقابل این قدرت بیان بالا وجود دارد، اولین مشکل از قدرت بیان زیاد این منطق سرچشمه می‌گیرید! در این منطق برخلاف منطق مرتبه اول می‌توان جمله «بی‌نهایت شی وجود دارد» را فرمال کرد (در نتیجه می‌توان جمله «متناهی شی وجود دارد» را هم بر خلاف منطق مرتبه اول فرمال کرد) مشکل چیست؟ فرض کنید من مجموعه جمله‌های زیر را داشته باشم:

 

1. نقیض «بی‌نهایت شی وجود دارد» (یعنی «متناهی تا شی وجود دارد»)

 

2.حداقل دو شی متمایز وجود دارد

 

3.حدااقل سه شی متمایز وجود دارد

 

و الی آخر، هر زیرمجموعه متناهی از این مجموعه جمله‌ها مدل دارد اما مدلی وجود ندارد که همه این مجموعه جمله‌ها را با هم برقرار کند. بنا بر این قضیه فشردگی که می‌گفت «اگر هر زیرمجموعه متناهی از یک مجموعه جمله مدل داشته باشد آنگاه کل آن مجموعه جمله هم مدل دارد» برقرار نیست، اما ما می‌دانیم قضیه فشردگی از قضیه تمامیت منطق ناشی می‌شود یعنی اگر در هر دستگاه منطقی با هر مرتبه‌ای قضیه تمامیت برقرار باشد آنگاه قضیه فشردگی هم باید برقرار باشد بنابر این در منطق مرتبه دو تمامیت برقرار نیست، به این معنی که نمی‌توان تمام همان‌گوها را استنتاج کرد!

 

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

 

مشکل دیگری هست که این را در ویکی خواندم: ظاهرا می‌توان نشان داد هیچ منطق مرتبه بالاتری نمی‌تواند وجود داشته باشد که هر سه این خواص را با هم داشته باشد:

 

1. کامل باشد (قضیه تمامیت برقرار باشد)

 

2. درست باشد (قضیه درستی برقرار باشد)

 

3. نظریه برهان الگوریتمی (بخوانید بازگشتی) داشته باشد.

 

چرا که در غیر این صورت با توجه به این که نظریه اعداد در منطق مرتبه دو متناهیا اصل پذیر است در صورت برقراری این سه شرط باید جملات درست در نظریه اعداد بازگشتی باشند اما قضیه گودل نشان می‌دهد که نیست!

 

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

 

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

 

پ.ن:هووووف، بالاخره تمام شد، خُب، موضوع و کتاب بعدی چه باشد؟ :))

منطق ریاضی 7 :تصمیم ناپذیری و قضیه گودل

 

و بالاخره بعد از چهار ماه جان کندن لابه لای کارهای دانشگاه و پروژه برقی‌ام این فصل را خواندم، هوراااااااا، علی رغم این که فکر می‌کردم به خاطر پدری که در بخش منطق مرتبه اول از من در آمد، این قسمت سرازیری است و سریع می‌خوانم اما کلا یک فضای دیگر بود، در واقع اصلا ربطی به منطق مرتبه اول ندارد و پدرم هم در اینجا در آمد! این قسمت را متاسفانه فقط کتاب اندرتون داشت و همین کار را برایم بیشتر مشکل می‌کرد.

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

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

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

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

هر رابطه‌ای که در یک نظریه اصل‌پذیر متناهی نمایش‌پذیر است، در TAE  نیز نمایش‌پذیر است!

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

 هر رابطه‌ی تصمیم‌پذیری بازگشتی است!

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

اما برویم سراغ تصمیم ناپذیری برای شروع بیاید یک لم ثابت کنیم، لم نقطه ثابت: برای هر فرمول دلخواه در نظریه اعداد مثل B(v)  (که v متغیر فرمول است) می‌توان جمله‌ای مثل s یافت که s برقرار است اگر و فقط اگر B(#s) برقرار باشد (#s یعنی عدد گودل جمله s) برای اثبات کافی است بدانیم تابعی وجود دارد که به ازای هر فرمول A(v) (که v متغیر آزاد فرمول است) مقدار #A(#A) را محاسبه می‌کند (واقعا در TAE محاسبه پذیر است، باور کنید!) اسم این تابع را f می‌گذارم که ورودی‌اش فرمول است (در واقع عدد گودل فرمول) و خروجی‌اش عدد گودل همان فرمول وقتی که عدد گودل خودش درون خودش جایگذاری شده یعنی اگر عدد گودل فرمول A(v)، r  باشد آنگاه A(r) یک جمله است و f(r)=#(A(r)). حالا فرمول جدید C(t)را در نظر بگیرید که فقط وقتی برقرار است که B(f(t)) برقرار باشد (این فرمول قطعا وجود دارد به زبان شهودی C(t)=B(f(t)) است). فرض کنید عدد گودل این فرمول q است یعنی q=#C(t) حالا اگر این عدد را درون خود فرمول C(t)جای‌گذاری کنیم چه می‌شود؟ طبق تعریفِ C، C(q) اگر و فقط اگر B(f(q)) و با توجه به این که f(q)=#C(q) آنگاه C(q) اگر و فقط اگر B(#C(q)) و این یعنی C(q) همان جمله s است! پس لم اثبات شد.

خُب حالا این لم به چه دردی می‌خورد؟ فرض کنید کسی ادعا کند نظریه اعداد (یعنی نظریه ساختاری با صفر و یک و تالی و جمع و ضرب) نمایش‌پذیر است  و این یعنی فرمولی وجود دارد مثل N(t) که عدد گودل یک جمله مثل G را می‌گیرد و برقرار است اگر G در نظریه اعداد برقرار باشد و برقرار نیست اگرG  در نظریه اعداد برقرار نباشد، فرض کنید B معادل نقیض N باشد یعنی B(t) برقرار است اگر و فقط اگر ورودی‌اش عدد گودل جمله‌ای نادرست از نظریه اعداد باشد. حال با استفاده از لم بالا برای B می‌دانیم جمله‌ای مثل s در نظریه اعداد وجود دارد که B(#s) برقرار است اگر  فقط اگر s برقرار باشد. حالا اگر s جمله‌ای باشد که در نظریه اعداد برقرار است به این معنی است که B(#s) باید برقرار باشد اما این تناقض است چون طبق تعریف B،  B(#s) برقرار است اگر و فقط اگر s جمله‌ای نادرست از نظریه اعداد باشد و برعکس، اگر s واقعا جمله‌ای نادرست از نظریه اعداد باشد آنگاه B(#s) طبق تعریف B باید برقرار باشد اما می‌دانیم B(#s)  برقرار است اگر و فقط اگر s برقرار باشد (یعنی جمله‌ای درست از نظریه اعداد باشد) با توجه به این تناقض چنین B وجود نداشته و چنین N هم وجود ندارد بنابراین نظریه اعداد نه تنها بازگشتی نیست بلکه حتی عدد گودل جمله های درست اساسا تعریف پذیر نیست.

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

اما حالا کاربرد قضیه گودل چیست؟ این همه زور زدیم و حرف زدیم تا تازه فقط درون نظریه اعداد اثباتش کنیم اما قرار است چه کار کند؟ خُب قدم به قدم پیامدهایش را بررسی می‌کنیم:

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

دوم، باز برگردیم به نظریه مجموعه‌ها، اثباتی شبیه به اثبات گودل برای ناتمام بودن نظریه مجموعه‌ها هست که نتیجه بدتری دارد، و آن این که اثبات سازگاری نظریه مجموعه‌ها درون خودش غیرممکن است. فرض کنید رابطه‌ای دوتایی مثل D داریم به این معنی که D(a,c) برقرار است اگر و فقط اگر a عدد گودل فرمول A(v) باشد و c عدد گودل استنتاجی برای  A(a) باشد. (بله، استنتاج‌ها هم خودشان عدد گودل دارند که از عدد گودل عبارت متفاوت است) تصور این که رابطه D بازگشتی است سخت نیست. بنابراین فرمولی مثل d وجود دارد که d(a,c) برقرار است اگر و فقط اگر c عدد گودل استنتاجی برای A(a) باشد (a عدد گودل فرمول A(v) است) حال این فرمول را در نظر بگیرید:

«به ازای هر c داریم که d(a,c) برقرار نیست»

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

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

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

پ.ن باقی‌مانده: حالا فقط منطق مرتبه دو مانده که درست بخوانم و بعد از بیش از یک سال پرونده منطق ریاضی خواندنم را ببندم تا به باقی زندگی‌ام برسم، کتاب راحت تر بخوانم و خوشحال‌تر باشم! امیدوارم این تخمین که «منطق مرتبه دو سریع تمام می‌شود» مثل تخمین «تصمیم‌ناپذیری سریع تمام می‌شود» نباشد.

مسئله مونتی‌هال یا دو بز و یک ماشین+کامنت منطق ریاضی!

اگر فیلم 21 را دیده باشید احتمالا این مسئله را هم شنیده‌اید:

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

شهود اولیه ما می‌گوید که بعد از حذف در شماره 3 دو گزینه وجود دارد: یا ماشین پشت در شماره 1 است یا در شماره 2 و احتمال هر کدام مساوی است و پنجاه درصد است بنا بر این قوانین احتمال به شما کمکی نمی‌کند که بدانید ماشین پشت کدام در قرار دارد. اما در واقع جواب مسئله همان طور که استیو اسِلوین اولین بار مطرح کرده این است که احتمال وجود ماشین پشت در شماره 2 دو برابر بیشتر از انتخاب اول شما یعنی در شماره 1 است بنا بر این باید انتخاب‌تان را عوض کنید!

اما چرا؟ جواب مسئله در واقع این گونه است، فرض کنید ماشین از ابتدا پشت در شماره 2 قرار دارد، سه حالت با احتمال مساوی وجود دارد:

1. . شما در 1 را انتخاب می‌کنید و مجری در 3 را پوچ می‌کند (در این حالت باید انتخاب‌تان را عوض کنید)
   
2.  شما در 3 را انتخاب می‌کنید و مجری در 1 را پوچ می‌کند (در این حالت هم باید انتخاب‌تان را عوض کنید)
3.   شما در 2 را انتخاب می‌کنید و مجری در 1 یا 3 را پوچ می‌کند (در این حالت نباید انتخاب‌تان را عوض کنید)
   

می‌بینید که از این سه حالت با احتمال مساوی، فقط یک حالت وجود دارد که در آن نباید انتخابتان را عوض کنید و در دو حالت دیگر باید عوض کنید بنا بر این ماشین به احتمال 66 درصد پشت دری است که انتخاب نکرده‌اید!

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

اگر این ادعا صحیح باشد که احتمال هر دو گزینه مساوی است بنا بر این با تکرار بازی به دفعات زیاد تعداد دفعاتی که مرد برنده شده با تعداد دفعاتی که زن برنده شده برابر است، اما این ادعا به وضوح درست نیست: شما همیشه در انتخاب اول یک سوم یا 33 درصد احتمال دارد که ماشین را انتخاب کنید، با توجه به این که مرد حرفش را عوض نمی‌کند (حتی بعد از باز شدن دری دیگر) بنا بر این باز شدن دری دیگر تفاوتی در وضعیت مرد ایجاد نمی‌کند و مرد همیشه به احتمال 33 درصد برنده خواهد شد، اما خانم با توجه به جواب قبلی 66 درصد احتمال برنده شدن دارد.

اما سوال اول هنوز سر جایش است: اشکال استدلال اول که منجر به نتیجه 50 درصد می‌شد دقیقا کجاست؟ شاید بشود گفت ایراد اینجاست که ما مسئله را بعد از پوچ شدن یکی از گزینه‌ها دوباره بازتعریف می‌کنیم و تبدیل می‌کنیم به یک سوال دو گزینه‌ای با احتمال برابر و فراموش می‌کنیم که مجری در هر صورت مجبور است دری را باز کند، اگر شما قبل از انتخابتان از مجری بخواهید دری را باز کند آن وقت حتما احتمال انتخاب شما 50 درصد است اما بعد از این که شما انتخاب می‌کنید مجری مجبور است دری را باز کند که پشت آن ماشین نیست و 66 درصد احتمال دارد که شما دری اشتباه را انتخاب کنید بنابر این 66 درصد مواقع مجری هیچ آزادی برای انتخاب ندارد و باید دری مشخص را پوچ کند که ماشین پشت آن نیست بنا بر این 66 درصد مواقع مجری با زبان بی‌زبانی به شما می‌گوید دری دیگر را انتخاب کنید! اما 33 درصد مواقع هم شما درست انتخاب کرده‌اید و مجری آزادی کاملی دارد که یکی از گزینه‌های پوچ را باز کند. به زبان نظریه احتمال شما نباید احتمال شرطی را این گونه مطرح کنید: «احتمال حضور ماشین بین در 1 و 2 اگر در 3 پوچ باشد» چون در 3 به صورت تصادفی پوچ نشده بلکه بعد از انتخاب شما پوچ شده (یعنی مجری در پوچ کردن آزادی ندارد و انتخاب شما در این که کدام در را پوچ کند نقش بازی می‌کند، بنا بر این احتمال حذف شده توسط مجری به طور یکسان بین انتخاب شما و انتخاب دیگر پخش نمی‌شود چون شما با انتخاب اول خود تقارن گزینه‌ها را به هم زده‌اید)

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

اَکنالجمِنت: ویت اِسپشیال تَنکث تو سارا که جواب این مسئله مونتی هال را وقتی خودم درست فهمیدم که تلاش کردم برای سارا توضیح بدهم.

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

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

منطق ریاضی 4

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

یکی از قسمت‌های این سوال، یعنی این که «برهانی برای ب از آ وجود دارد» نتیجه می‌دهد که «ب نتیجه معناشناسنه آ است» به نظر بدیهی می‌رسد. کافی است با بازگشت نشان دهیم که هر قدم استنتاج گزاره‌ای به دست می‌دهد که نتیجه معناشناسنه گزاره قبلی است، این قضیه به قضیه «درستی» معروف است. یعنی آنچه با استنتاج به دست می‌آید لزوما قواعد «درست» بودن را رعایت می‌کند.

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

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

البته منطق گزاره ها به یک معنی هم کامل یا تمام نیست، یعنی منطق گزاره ها نمی‌تواند راجع به هر گزاره ای استنتاجی برای آن یا نقیض اش ارائه کند.

از این به بعد نوبت منطق مرتبه اول و قضایای درستی و تمامیت برای منطق مرتبه اول است.

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

منطق ریاضی 3

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

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

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

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

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

پ.ن: دارد جالبتر میشود.

 

*برگردم؟ کجا برگردم، به زندگی؟ به زندگی که با هر نفس و هر روزی که می‌گذرد یک قدم به مرگ نزدیکتر می‌شوم؟

منطق ریاضی دو

این روزها به دلیلِ مشغله‌ی بلاحَدّم اصلا فرصت تمرکز روی موضوع منطق ریاضی ندارم اما الان دوباره فرصتی دست داد تا یک ساعتی موضوع را ادامه بدهم (صد البته کنار مترو-اتوبوس خوانی این کتاب).

 

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

 

پس منطق ریاضی چیزی ایستاده بالای سرِ ریاضی نیست، آنچه ریاضی از آن تبعیت می‌کند همان چند قاعده ترکیب صدق و کذب است، «منطق ریاضی» چیزی شبیهِ خودِ ریاضی است اما خُب نتایج جالبی هم دارد، مثل وجود گزاره‌های تصمیم ناپذیر در شرایطی خاص که ترغیبم می‌کند این خوانشم از منطق ریاضی را ادامه بدهم.

 

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

 

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

 

پ.ن: موازی این افکار با دیدن پُرفِسور سایان که ادعای امام زمانی هم کرده این به ذهنم رسید که حالا همه‌ی این نقدها درست، اما بالاخره بین مزخرف گویی و غیرمزخرف‌گویی باید فرقی باشد، شاید فرقش را باید مورد به مورد بررسی کرد و هیچ قاعده‌ی کلی وجود ندارد اما بالاخره فرقی بینشان هست.

منطق ریاضی

 

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

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

مقدمه کتاب، استدلالی مبتذل را به عنوان نمونه‌ای از استدلال قیاسی معتبر ارائه می‌کند:

هر انسانی فانی است

ارسطو انسان است

پس ارسطو فانی است

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

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

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

پ.ن1:دیشب که کتاب را برداشتم و مقدمه‌اش را دیدم کلی ایده به ذهنم سرازیر شد راجع به ریاضی و منطق، بعضی‌هایشان را نوشتم، اگر این نوشته‌ها حین خواندنِ کتاب ادامه پیدا کنند همه‌شان را با عنوان «یادداشت‌های در باب منطق ریاضی» یا چیزی در این مایه‌ها ادامه می‌دهم.

پ.ن2: بدبخت شدم! وسطِ این همه کار موضوع به این جذابی را دست گذاشتم.