منطق ریاضی 4
جمعه, ۲۶ بهمن ۱۳۹۷، ۰۱:۴۴ ق.ظ
معناشناسی منطق گزاره‌ها صرفا «درستی» گزاره‌ها را بر اساس تابع ارزش گزاره‌های اتمی تعریف میکند همچنین اگر هر مدلی که مجموعه آ از گزاره‌ها را «راست» کند گزاره ب را نیز راست کند معادل است با این که ب نتیجه معناشاسانه آ است. اما راه دیگری هم برای بررسی درستی گزاره‌ها و ارتباط آنها با مجموعه دیگری از گزاره‌ها وجود دارد که بیشتر به «تفکر ریاضی» و مدل ریاضی «اثبات ریاضی» شبیه است: تعریف استنتاج؛ چگونه از گزاره یا گزاره‌هایی، مجموعه دیگری از گزاره یا گزاره‌ها را نتیجه بگیریم؟ تعریف استنتاج به گونه‌های مختلفی اتفاق می‌افتد، یا چون دستگاه هیلبرت مجموعه‌ای از اصول موضوعه‌ها داریم به علاوه یک قاعده استنتاج (که گزاره‌های جدید با همین قاعده استنتاج ساخته میشود) یا مثل دستگاه اسنتنتاج طبیعی فقط قاعده اسنتتاج داریم که گزاره های جدید میسازد. بعد از تعریف استنتاج (که کاملا متفاوت از ماهیت معناشناسی است) قسمت اعظم این بخش اختصاص داشت به این سوال که «آیا این دو تعریف از استنتاج، یعنی درستی یا حقیقت و اسنتنتاج یا برهان با هم معادل هستند یا نه؟» به عبارتی آیا این دو جمله با هم معادل هستند: «ب نتیجه معناشناسانه آ است» و «برای گزاره ب استنتاجی از آ وجود دارد».
یکی از قسمت‌های این سوال، یعنی این که «برهانی برای ب از آ وجود دارد» نتیجه می‌دهد که «ب نتیجه معناشناسنه آ است» به نظر بدیهی می‌رسد. کافی است با بازگشت نشان دهیم که هر قدم استنتاج گزاره‌ای به دست می‌دهد که نتیجه معناشناسنه گزاره قبلی است، این قضیه به قضیه «درستی» معروف است. یعنی آنچه با استنتاج به دست می‌آید لزوما قواعد «درست» بودن را رعایت میکند.
عکس سوال اما غیر بدیهی است، یعنی به این راحتی مشخص نیست که اگر «ب نتیجه معناشناسنه آ است» برقرار باشد لزوما نتیجه بدهد که «برای ب استنتاجی از آ وجود دارد» یا به طور معادل بدیهی نیست که برای هر نتیجه معناشناسانه میتوان استنتاجی داشت یا خیر؟واقعیت این است که اثبات این قسمت پر زحمت‌تر از اثبات قضیه «درستی» است و این نشان از همین بدیهی نبودن دارد. طرح کلی اثبات از این قرار است که نشان دهیم پاسخ مثبت به این سوال معادل با این است که «هر مجموعه سازگار از گزاره‌ها مدل دارد» سپس این قسمت را (که به لم وجود مدل معروف است) اثبات کنیم* معادل بودن این دو عبارت خیلی عجیب نیست، البته بهتر است برای این که اثبات واضح‌تر باشد لم وجود مدل را جور دیگری بیان کنیم که من اسمش را میگذارم لم عدم وجود مدل :)) (در واقع عکس نقیض لم وجود مدل است) «هر مجموعه از گزاره‌ها که هیچ مدلی نداشته باشد لزوما ناسازگار است» مخصوصا با توجه به این که هیچ مدلی تناقض را برقرار نمی کند، اگر برای مجموعه‌ای از گزاره‌ها هیچ مدلی وجود نداشته باشد مثل این است که تناقض نتیجه معناشناسانه آن مجموعه است، بنا بر این لم عدم وجود مدل تبدیل میشود به این که «اگر نتیجه معناشناسنه مجموعه ای از گزاره ها تناقض باشد آنگاه تناقض قابل استنتاج است یا آن مجموعه ناسازگار است» که من این بیان را از دو جهت خیلی بیشتر دوست دارم یکی این که قیافه آن کاملا شبیه قضیه تمامیت است (بنا بر این معادل بودنش واضح‌تر است) دوم این که ناسازگاری برای من خوش تعریف‌تر از سازگاری است. حالا معادل بودن لم عدم وجود مدل با قضیه تمامیت واضح است: فرض کنید هر مدلی که مجموعه گزاره آ را برقرار کند گزاره ب را هم برقرار میکند، آنگاه هیچ مدلی برای مجموعه گزاره آ و نقیض گزاره ب وجود ندارد، حالا اگر لم عدم وجود مدل برقرار باشد میتوان نتیجه گرفت که گزاره‌های آ و نقیض ب ناسازگار هستند و تناقض را نتیجه می‌دهند در نتیجه گزاره‌های آ لزوما ب را نتیجه می‌دهند که صورت قضیه تمامیت است. از طرفی شکل خاصی از قضیه تمامیت همان لم عدم وجود مدل است: شکلی که در آن میگوید «اگر نتیجه معناشناسانه گزاره آ تناقض باشد آنگاه استنتاجی برای تناقض از آ وجود دارد» به همین سادگی!
برای اثبات خودِ لم وجود مدل کلی عملیات غیر بدیهی انجام میشود: اولا از مفهومی نه چندان بدیهی به نام مجموعه گزاره ماکسیمال استفاده می شود (یک جورهایی یعنی مجموعه ای که تمام گزاره های درست را در خود دارد) بعد اثبات می کند که برای هر مجموعه سازگار از گزاره‌ها مجموعه‌ای ماکسیمال سازگار وجود دارد که مجموعه اولیه زیر مجموعه آن مجموعه ماکسیمال است(با استفاده از اصل انتخاب یا معادلهای آن، مجموعه ماکسیمال گزاره ها هر گزاره‌ای که منجر به تناقض نشود را به مجموعه قبلی اضافه میکند این حتی شامل اتمهایی میشود که در مجموعه گزاره اولیه نیستند، اضافه کردن همه عبارتها :)) واقعا چی فکر کردن با خودشون؟) و در نهایت نشان می‌دهد میتوان مدلی برای مجموعه ماکسیمال سازگار ساخت (این «میتوان» با استقرا انجام میشود، گزاره های اتمی و سپس هر گزاره‌ای که با اینها ساخته میشود مدل دارد، و این مدل داشتن به خاطر سازگاری مجموعه به هم نمی خورد). این قضیه پر دردسر به قضیه تمامیت مشهور است، تمامیت به این معنی که منطق گزاره ها و روش‌های استنتاج، می‌تواند «تمام» همانگو ها را استنتاج کند یا تعیین کند که راست است یا خیر. اهمیت اینجاست که همانگو ها را میتوان به صورت معناشناسانه به راحتی یافت اما به لحاظ استنتاجی این قضیه است که تضمین می کند برای تمام همانگوها اسنتنتاجی وجود دارد (به عبارتی تمام همانگونها اثبات شدنی یا استنتاج شدنی هستند) اما آیا روشی وجود دارد که برای هر همانگو، استنتاجی ساخت؟ خوشبختانه بله، و این تا حدی ما را از شر این اثبات خلاص میکند.
البته منطق گزاره ها به یک معنی هم کامل یا تمام نیست، یعنی منطق گزاره ها نمی‌تواند راجع به هر گزاره ای استنتاجی برای آن یا نقیض اش ارائه کند.
از این به بعد نوبت منطق مرتبه اول و قضایای درستی و تمامیت برای منطق مرتبه اول است.
* سازگار بودن مجموعه‌ای از گزاره ها به نظر خیلی بدیهی نیست، سازگاری یعنی از مجموعه‌ای از گزاره‌ها نتوان تناقض را استنتاج کرد و اگر بشود یعنی مجموعه ناسازگار است، این که اگر تناقض از گزاره‌ها منتج شود یعنی مجموعه گزاره ها ناسازگار است را قبول دارم اما آیا میتوان چک کرد که هیچ استنتاجی تناقض را نتیجه نمی‌دهد؟ به عبارتی آیا نتیجه تمام استنتاجها را داریم که بدانیم تناقض بین آنها هست یا خیر؟ به همین خاطر هم درون اثبات از مجموعه بیریختی مثل مجموعه ماکسیمال استفاده می‌کنند که نتیجه تمام استنتاجها را دارد، اما درون این مجموعه چطور میتوان جست و جو کرد؟ به همین خاطر هم هست که ناچاریم در این قسمت از اصل انتخاب استفاده کنیم که بسیار مناقشه آمیز است و به اصطلاح ساختی نیست.
